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. 

This section presents the formulation of the primal problem, the definition and properties of the perturbation function, the definition of stable primal problem, and the existence conditions of optimal multiplier vectors. 

Remark 1 Fory = 0, v 0) corresponds to the optimal value of the primal problem (P). Values of the perturbation function v(y) at other points different than the origin y = 0 are useful on the grounds of providing information on sensitivity analysis or parametric effects of the perturbation vector y. 

Definition 4.1.1 The primal problem (P) is stable if v(0) is finite and there exists a scalar L > 0 such that... 

Remark 2 If the objective function f(x) is sufficiently well behaved, then the primal problem (P) will be stable regardless of how poorly behaved the constraints are. For instance, if f(x) = c, then (P) is stable as long as the constraints are feasible. 

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. 

Note that the intersection point of I and z3, denoted as (P ) in the figure, is the image of the optimal solution of the primal problem (P),... 

Remark 1 The value of (/Zi, fi2) that intersects the ordinate at the maximum possible value in Figure 4.1 is the supporting hyperplane of I that goes through the point P, which is the optimal solution to the primal problem (P). 

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

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

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

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

The basic idea in Generalized Benders Decomposition GBD is the generation, at each iteration, of an upper bound and a lower bound on the sought solution of the MINLP model. The upper bound results from the primal problem, while the lower bound results from the master problem. The primal problem corresponds to problem (6.2) with fixed y-variables (i.e., it is in the jr-space only), and its solution provides information about the upper bound and the Lagrange... 

This section presents the theoretical development of the Generalized Benders Decomposition GBD. The primal problem is analyzed first for the feasible and infeasible cases. Subsequently, the theoretical analysis for the derivation of the master problem is presented. 

The primal problem results from fixing the y variables to a particular 0-1 combination, which we denote as yk where k stands for the iteration counter. The formulation of the primal problem P(yk), at iteration k is... 

Remark 1 Note that due to conditions Cl and C3(i), the solution of the primal problem P yk) is its global solution. 

If the primal problem at iteration k is feasible, then its solution provides information on xk, f(xk, yk ), which is the upper bound, and the optimal multiplier vectors k, for the equality and inequality constraints. Subsequently, using this information we can formulate the Lagrange function as... 

Note that infeasibility in the primal problem is detected when a solution of (FP) is obtained for which its objective value is greater than zero. 

The solution of the feasibility problem (FP) provides information on the Lagrange multipliers for the equality and inequality constraints which are denoted as Ak,fik respectively. Then, the Lagrange function resulting from on infeasible primal problem at iteration k can be defined as... 

Remark 2 It should be noted that two different types of Lagrange functions are defined depending on whether the primal problem is feasible or infeasible. Also, the upper bound is obtained only from the feasible primal problem. 

Remark 1 Note that v y) is parametric in the y variables and therefore, from its definition corresponds to the optimal value of problem (6.2) for fixed y (i.e., the primal problem P(yk) fory = yk). 

Remark 5 The dual representation of the set V needs to be invoked so as to generate a collection of regions that contain it (i.e., system (6.7) corresponds to the set of constraints that have to be incorporated for the case of infeasible primal problems. 

Having introduced the dual representation of the set V, which corresponds to infeasible primal problems, we can now invoke the dual representation of o(y). 

In the previous section we discussed the primal and master problem for the GBD. We have the primal problem being a (linear or) nonlinear programming NLP problem that can be solved via available local NLP solvers (e.g., MINOS 5.3). The master problem, however, consists of outer and inner optimization problems, and approaches towards attaining its solution are discussed in the following. 

The master problem has as constraints the two inner optimization problems (i.e., for the case of feasible primal and infeasible primal problems) which, however, need to be considered for all A and all p > 0 (i.e., feasible primal) and all (A, p) A (i.e., infeasible). This implies that the master problem has a very large number of constraints. 

---