Dual Problem

In some circumstances, it is useful to transform the original problem, which is usually called the primal problem  

One important application of this ability to transform a constrained optimization problem into an equivalent (dual) problem is linear programming (Chapter 10), where both the objective function and all constraints are linear. 

For example, the following linear programming problems are the duals of each other  

An important feature that links primal and dual problems is that, once a feasible point has been assigned for the primal problem and another has been assigned for the dual problem, the value of the objective functions calculated in these points is always F 4 if one of the two points is not the solution of its problem. 

the guarantee that the solution has been reached is 

---

Besides, the property p[w] = [w] has already been proved. Let us consider the second (dual) problem in (3.226). We assume that qG K is a parameter and seek the solution w G of the following problem,... 

Again we are faced with the dual problem first, to calculate the quantity of heat, q and, second, to decide the uncertainty in q. 

Linear Programming.28—A linear programming problem as defined in matrix notation requires that a vector x 0 (non-negativity constraints) be found that satisfies the constraints Ax <, b, and maximizes the linear function cx. Here x = (xx, , xn), A = [aiy] (i = 1,- -,m j = 1,- , ), b - (61 - -,bm), and c = (cu- -,c ) is the cost vector. With the original (the primal) problem is associated the dual problem yA > c, y > 0, bij = minimum, where y yx,- , ym)-A duality theorem 29 asserts that if either the primal or the dual has a solution then the values of the objective functions of both problems at the optimum are the same. It is a relatively easy matter to obtain the solution vector of one problem from that of the other. 

In the original problem one usually has m < n. Thus, the vertices of the region of solution lie on the coordinate planes. This follows from the fact that, generally, in n dimensions, n hyperplanes each of dimension (n — 1) intersect at a point. The dual problem defines a polytope in m-dimensional space. In this case not all vertices need lie on the coordinate planes. 

Vg (x°)-x Vgt(x°)-x° for all x. This linear programming problem has the dual problem of finding > 0 which minimize... 

Downward displacement operator, 399 Drell, S. D., 724 Druyvesteyn distribution, 49 Druyvesteyn, M. J49 Dual problem in linear programming, 304... 

Linear algebraic problem, 53 Linear displacement operator, 392 Linear manifolds in Hilbert space, 429 Linear momentum operator, 392 Linear operators in Hilbert space, 431 Linear programming, 252,261 diet problem, 294 dual problem, 304 evaluation of methods, 302 in matrix notation, simplex method, 292... 

In physical objects involving thermal and fluid flow systems, the dual problem of how the heater is represented, and boiling as a local-instantaneous effect, should be considered. The temperature variations on the chip surface are a key characteristic of... 

Murtagh (M9) pointed out that rounding errors and storage limitations restrict the applicability of such techniques to networks of approximately 100 pipe sections or less. As an alternative he proposed to solve the following dual problem ... 

The virtue of this theorem is that it reduces the dual problem to the question of solving the Euler equation PQ = 0, a second-order algebraic equation for the... 

Nonlinear optimization problems have two different representations, the primal problem and the dual problem. The relation between the primal and the dual problem is provided by an elegant duality theory. This chapter presents the basics of duality theory. Section 4.1 discusses the primal problem and the perturbation function. Section 4.2 presents the dual problem. Section 4.3 discusses the weak and strong duality theorems, while section 4.4 discusses the duality gap. 

Remark 4 The convexity property of v(y) is the fundamental element for the relationship between the primal and dual problems. A number of additional properties of the perturbation function v(y) that follow easily from its convexity are... 

This section presents the formulation of the dual problem, the definition and key properties of the dual function, and a geometrical interpretation of the dual problem. 

Remark 2 The dual problem consists of (i) an inner minimization problem of the Lagrange function with respect to x 6 X and (ii) on outer maximization problem with respect to the vectors of the Lagrange multipliers (unrestricted A, and ft > 0). The inner problem is parametric in A and fi. For fixed x at the infimum value, the outer problem becomes linear in A and ft. 

The geometrical interpretation of the dual problem provides important insight with respect to the dual function, perturbation function, and their properties. For illustration purposes, we will consider the primal problem (P) consisting of an objective function /(x) subject to constraints gi(x) < 0 and g2(x) < 0 in a single variable x. 

For the geometrical interpretation of the dual problem, we will consider particular values for the Lagrange multipliers i, fi2 associated with the two inequality constraints (fa > 0, fa > 0), denoted as fa, fa. 

Remark 2 It is not always possible to obtain the optimal value of the dual problem being equal to the optimal value of the primal problem. This is due to the form that the image set I can take for different classes of mathematical problems (i.e., form of objective function and constraints). This serves as a motivation for the weak and strong duality theorems to be presented in the following section. 

In the previous section we have discussed geometrically the nature of the primal and dual problems. In this section, we will present the weak and strong duality theorems that provide the relationship between the primal and dual problem. 

Remark 1 Any feasible solution of the dual problem (D) represents a lower bound on the optimal value of the primal problem (P). 

Remark 3 This lower-upper bound feature between the dual and primal problems is very important in establishing termination criteria in computational algorithms. In particular applications, if at some iteration feasible solutions exist for both the primal and the dual problems and are close to each other in value, then they can be considered as being practically optimal for the problem under consideration. 

Remark 4 This important lower-upper bound result for the dual-primal problems that is provided by the weak duality theorem, is not based on any convexity assumption. Hence, it is of great use for nonconvex optimization problems as long as the dual problem can be solved efficiently. 

Remark 1 Result (ii) precludes the existence of a gap between the primal problem and dual problem values which is denoted as duality gap. It is important to note that nonexistence of duality gap is guaranteed under the assumptions of convexity of f(x))g(x), affinity of h(x), and stability of the primal problem (P). 

Remark 2 Result (iii) provides the relationship between the perturbation function v(y) and the set of optimal solutions (A, p) of the dual problem (D). 

Remark 3 If the primal problem (P) has an optimal solution and it is stable, then using the theorem of existence of optimal multipliers (see section 4.1.4), we have an alternative interpretation of the optimal solution (A, p) of the dual problem (D) that (A, p) are the optimal Lagrange multipliers of the primal problem (P). 

Remark 6 The geometrical interpretation of the primal and dual problems clarifies the weak and strong duality theorems. More specifically, in the vicinity of y — 0, the perturbation function v(y) becomes the 23-ordinate of the image set I when zi and z2 equal y. In Figure 4.1, this ordinate does not decrease infinitely steeply as y deviates from zero. The slope of the supporting hyperplane to the image set I at the point P, (-pi, -p2), corresponds to the subgradient of the perturbation function u(y) at y = 0. 

Remark 1 The difference in the optimal values of the primal and dual problems can be due to a lack of continuity of the perturbation function v(y) at y = 0. This lack of continuity does not allow the existence of supporting hyperplanes described in the geometrical interpretation section. 

Notice though that the optimal value of the dual problem cannot equal that of the primal due to the loss of lower semicontinuity of the perturbation function v(y) aty = 0. 

---