Duality primal problem

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. 

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 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. 

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. 

The weak duality theorem provides the lower-upper bound relationship between the dual and the primal problem. The conditions needed so as to attain equality between the dual and primal solutions are provided by the following strong duality theorem. 

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). 

The objective function /( ) and the inequality constraint g(x) are convex since f(x) is separable quadratic (sum of quadratic terms, each of which is a linear function of xi, x2,X3, respectively) and g(x) is linear. The equality constraint h(x) is linear. The primal problem is also stable since v(0) is finite and the additional stability condition (Lipschitz continuity-like) is satisfied since f(x) is well behaved and the constraints are linear. Hence, the conditions of the strong duality theorem are satisfied. This is why... 

Remark 4 Note that due to the strong duality theorem we do not need to solve the problems for Zj, L[ since their optimum solutions are identical to the ones of the corresponding feasible and infeasible primal problems with respect to x, respectively. 

Note that we do not not need to solve for Lk since due to strong duality its solution is identical to the one of the corresponding primal problem P y )-... 

Part 1, comprised of three chapters, focuses on the fundamentals of convex analysis and nonlinear optimization. Chapter 2 discusses the key elements of convex analysis (i.e., convex sets, convex and concave functions, and generalizations of convex and concave functions), which are very important in the study of nonlinear optimization problems. Chapter 3 presents the first and second order optimality conditions for unconstrained and constrained nonlinear optimization. Chapter 4 introduces the basics of duality theory (i.e., the primal problem, the perturbation function, and the dual problem) and presents the weak and strong duality theorem along with the duality gap. Part 1 outlines the basic notions of nonlinear optimization and prepares the reader for Part 2. 

An example of duality in quadratic programming is Primal problem... 

Theorem A.2 Weak duality For any feasible solution x of the primal problem (A.l) and for any feasible solution X, fi, of the dual problem (A.8), the following holds... 

For nonconvex programs, the difference between the optimal objective function values of the dual and primal problems ((p (X, p )-f(x ))is called duality gap. For nonconvex programs of engineering applications, the duality gap is usually relatively small (Conejo et al. 2002). 

Feasible x) and y) give upper and lower bounds on the optimal value of the objective function, which in the 2-RDM problem is the ground-state energy in a finite basis set. The primal and dual solutions, x) and y), sie feasible if they satisfy the primal and dual constraints in Eqs. (107) and (108), respectively. The difference between the feasible primal and the dual objective values, called the duality gap fi, which equals the inner product of the vectors x) and z). 

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 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. 

The term duality is often used to invoke a contrast between two related concepts. Duality is one of the most fundamental concepts in mathematical programming and establishes a connection between two symmetric programs, namely, the primal and dual problem. 

---