Constraint qualifications

Constraint Qualification For a local optimum to satisfy the KKT conditions, an additional regularity condition is required on the constraints. This can be defined in several ways. A typical condition is that the active constraints at x be linearly independent i.e., the matrix [Vh(x ) I VgA(x )] is full column rank, where gA is the vector of inequality constraints with elements that satisfy g x ) = 0. With this constraint qualification, the KKT multipliers (X, v) are guaranteed to be unique at the optimal solution. 

Problem (8.15) must satisfy certain conditions, called constraint qualifications, in order for Equations (8.17)-(8.18) to be applicable. One constraint qualification (see Luenberger, 1984) is that the gradients of the equality constraints, evaluated at x, should be linearly independent. Now we can state formally the first order necessary conditions. 

This section presents first the formulation and basic definitions of constrained nonlinear optimization problems and introduces the Lagrange function and the Lagrange multipliers along with their interpretation. Subsequently, the Fritz John first-order necessary optimality conditions are discussed as well as the need for first-order constraint qualifications. Finally, the necessary, sufficient Karush-Kuhn-Dicker conditions are introduced along with the saddle point necessary and sufficient optimality conditions. 

To remove this weakness of the Fritz John necessary conditions, we need to determine the required restrictions under which fi0 is strictly positive (fi0 > 0). These restrictions are called first-order constraint qualifications and will be discussed in the following section. 

Remark 1 Note that in the Kuhn-Tucker constraint qualification w(t) is a once-differentiable arc which starts at x. Then, the Kuhn-Tucker constraint qualification holds if z is tangent to w(r) in the constrained region. 

Remark 2 The linear independence constraint qualification as well as the Slater s imply the Kuhn-Tucker constraint qualification. 

Remark 1 Note that the saddle point sufficiency conditions do not require either additional convexity assumptions or a constraint qualification like condition. Note also that the saddle point sufficiency conditions do not require any differentiability on the Lagrange function. If in addition, the functions /(jc), h(x),g(x) are differentiable, and hence the Lagrange function is differentiable, and (3c, A,p) is a Karush-Kuhn-Tucker Saddle point, then it is a Karush-Kuhn-Tucker point [i.e., it is a solution of (3.3) and it satisfies the constraint qualification]. 

In this section, we discuss the need for second-order optimality conditions, and present the second-order constraint qualification along with the second-order necessary optimality conditions for problem (3.3). 

A constraint qualification required by the KKT conditions is satisfied since we have one constraint and its gradient... 

Then, the second-order constraint qualification holds at x if z is the tangent of a twice differentiable arc w(r) that starts at x, along which... 

Remark 1 The second-order constraint qualification at x, as well as the first-order constraint qualification, are satisfied if the gradients... 

Illustration 3.2.11 This example is taken from Fiacco and McCormick (1968), and it demonstrates that the second-order constraint qualification does not imply the first-order Kuhn-Tucker constraint qualification. 

The first-order Kuhn-Tucker constraint qualification is not satisfied since there are no arcs pointing in the constrained region which is a single point, and hence there are no tangent vectors z contained in the constraint region. The second-order constraint qualification holds, however, since there are no nonzero vectors orthogonal to all three gradients. 

Let it be a local optimum of problem (3.3), the functions f(x),h(x),g(x) be twice continuously differentiable, and the second-order constraint qualification holds at x. If there exist Lagrange multipliers A, fi satisfying the KKT first-order necessary conditions ... 

Remark 1 This theorem points out that stability is not only a necessary but also sufficient constraint qualification, and hence it is implied by any constraint qualification used to prove the necessary optimality conditions. 

Remark 4 Condition C3 is satisfied if a first-order constraint qualification holds for the resulting problem (6.2) after fixing y T n V. 

C3 A constraint qualification (e.g., Slater s) holds at the solution of every nonlinear programming problem resulting from (6.13) by fixing y. 

The constraint qualification assumption, which holds at the solution of every primal problem for fixed y E Y n V, coupled with the convexity of f(x) and g(x), imply the following Lemma ... 

Since a constraint qualification (condition 3) holds at the solution of every primal problem P(yk) for every y e Fn V, then the projection problem (6.45) has the same solution as the problem ... 

Remark 3 Note that the inner problem in (6.46) is v(y) with linearized objective and constraints around xk. The equivalence in solution between (6.45) and (6.46) is true because of the convexity condition and the constraint qualification. 

Remark 1 Note that the condition C3 is not required for finite convergence of the GOA/EP. This is because in exact penalty functions a constraint qualification does not form part of the first-order necessary conditions. However, note that C3 is needed to ensure that the solution (jc, y ) of the GOA/EP algorithm also solves (6.40). 

Since the master problem in OA and its variants has many more constraints than the master problem in GBD and its variants, the lower bound provided by OA is expected to be better than the lower bound provided by the GBD. To be fair, however, in the comparison between GBD and OA we need to consider the variant of GBD that satisfied the conditions of OA, namely, separability and linearity of they variables as well as the convexity condition and the constraint qualification, instead of the general GBD algorithm. The appropriate variant of GBD for comparison is the v2-GBD under the conditions of separability and linearity of they vector. Duran and Grossmann (1986a) showed that... 

In the previous section we showed that if convexity holds along with quasi-convexity of Tkh(x) < 0 and the constraint qualification, then the OA/ER terminates in fewer iterations than the v2-GBD since the lower bound of the OA/ER is better than the one of the v2-GBD. 

If the convexity conditions are satisfied along with the constraint qualification then the GBD variants and the OA attain their global optimum. 

In summary, condition 1 gives a set of n algebraic equations, and conditions 2 and 3 give a set of m constraint equations. The inequality constraints are converted to equalities using h slack variables. A total of M + m constraint equations are solved for n variables and m Lagrange multipliers that must satisfy the constraint qualification. Condition 4 determines the value of the h slack variables. This theorem gives an indirect problem in which a set of algebraic equations is solved for the optimum of a constrained optimization problem. 

Arrow, K.J., L. Hurwicz, and H. Uzawa, "Constraint Qualification in Maximization Problems," Naval Research Logistics Quarterly 8 (June 1961), 175-190. 

---