A relaxed constant positive linear dependence constraint qualification and applications

In this work we introduce a relaxed version of the constant positive linear dependence constraint qualification (CPLD) that we call RCPLD. This development is inspired by a recent generalization of the constant rank constraint qualification by Minchenko and Stakhovski that was called RCRCQ. We show that RCPLD is enough to ensure the convergence of an augmented Lagrangian algorithm and that it asserts the validity of an error bound. We also provide proofs and counter-examples that show the relations of RCRCQ and RCPLD with other known constraint qualifications. In particular, RCPLD is strictly weaker than CPLD and RCRCQ, while still stronger than Abadie’s constraint qualification. We also verify that the second order necessary optimality condition holds under RCRCQ.     

Optimality conditions and constraint qualifications in Banach space

In this paper, necessary optimality conditions for nonlinear programs in Banach spaces and constraint qualifications for their applicability are considered. A new optimality condition is introduced, and a constraint qualification ensuring the validity of this condition is given. When the domain space is a reflexive space, it is shown that the qualification is the weakest possible. If a certain convexity assumption is made, then this optimality condition is shown to reduce to the well-known extension of the Kuhn-Tucker conditions to Banach spaces. In this case, the constraint qualification is weaker than those previously given.This work was supported in part by the Office of Naval Research, Contract Number N00014-67-A-0321-0003 (NRO 47-095).     

First Order Optimality Conditions for Generalized Semi-Infinite Programming Problems

We study first-order optimality conditions for the class of generalized semi-infinite programming problems (GSIPs). We extend various well-known constraint qualifications for finite programming problems to GSIPs and analyze the extent to which a corresponding Karush-Kuhn-Tucker (KKT) condition depends on these extensions. It is shown that in general the KKT condition for GSIPs takes a weaker form unless a certain constraint qualification is satisfied. In the completely convex case where the objective of the lower-level problem is concave and the constraint functions are quasiconvex, we show that the KKT condition takes a sharper form. The authors thank the anonymous referees for careful reading of the paper and helpful suggestions. The research of the first author was partially supported by NSERC.     

Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints

In this paper we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. Various stationary conditions for MPECs exist in literature due to different reformulations. We give a simple proof to the M-stationary condition and show that it is sufficient for global or local optimality under some MPEC generalized convexity assumptions. Moreover, we propose new constraint qualifications for M-stationary conditions to hold. These new constraint qualifications include piecewise MFCQ, piecewise Slater condition, MPEC weak reverse convex constraint qualification, MPEC Arrow-Hurwicz-Uzawa constraint qualification, MPEC Zangwill constraint qualification, MPEC Kuhn-Tucker constraint qualification, and MPEC Abadie constraint qualification.     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

Constraint qualifications for constrained Lipschitz optimization problems and applications to a MPCC

Three constraint qualifications (the weak generalized Robinson constraint qualification, the bounded constraint qualification, and the generalized Abadie constraint qualification), which are weaker than the generalized Robinson constraint qualification (GRCQ) given by Yen (1997) [1], are introduced for constrained Lipschitz optimization problems. Relationships between those constraint qualifications and the calmness of the solution mapping are investigated. It is demonstrated that the weak generalized Robinson constraint qualification and the bounded constraint qualification are easily verifiable sufficient conditions for the calmness of the solution mapping, whereas the proposed generalized Abadie constraint qualification, described in terms of graphical derivatives in variational analysis, is weaker than the calmness of the solution mapping. Finally, those constraint qualifications are written for a mathematical program with complementarity constraints (MPCC), and new constraint qualifications ensuring the C-stationary point condition of a MPCC are obtained.     

Constant-Rank Condition and Second-Order Constraint Qualification

The constant-rank condition for feasible points of nonlinear programming problems was defined by Janin (Math. Program. Study 21:127–138, 1984). In that paper, the author proved that the constant-rank condition is a first-order constraint qualification. In this work, we prove that the constant-rank condition is also a second-order constraint qualification. We define other second-order constraint qualifications.     

A remark on a regularity assumption for the mathematical programming problem in Banach spaces

This paper deals with a recently proposed Slater-like regularity condition for the mathematical programming problem in infinite-dimensional vector spaces (Ref. 1). The attractive feature of this constraint qualification is the fact that it can be considered as a condition only on theactive part of the constraint. We prove that the studied regularity condition is equivalent to the regularity assumption normally used in the study of the mathematical programming problem in infinite-dimensional vector spaces.     

A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING

We propose a multidimensional filter SQP algorithm. The multidimensional filter technique proposed by Gould et al. [SIAM J. Optim., 2005] is extended to solve constrained optimization problems. In our proposed algorithm, the constraints are partitioned into several parts, and the entry of our filter consists of these different parts. Not only the criteria for accepting a trial step would be relaxed, but the individual behavior of each part of constraints is considered. One feature is that the undesirable link between the objective function and the constraint violation in the filter acceptance criteria disappears. The other is that feasibility restoration phases are unnecessary because a consistent quadratic programming subproblem is used. We prove that our algorithm is globally convergent to KKT points under the constant positive generators (CPG) condition which is weaker than the well-known Mangasarian-Fromovitz constraint qualification (MFCQ) and the constant positive linear dependence (CPLD). Numerical results are presented to show the efficiency of the algorithm.     

A Relaxed Constant Positive Linear Dependence Constraint Qualification for Mathematical Programs with Equilibrium Constraints

We introduce a relaxed version of the constant positive linear dependence constraint qualification for mathematical programs with equilibrium constraints (MPEC). This condition is weaker but easier to check than the MPEC constant positive linear dependence constraint qualification, and stronger than the MPEC Abadie constraint qualification (thus, it is an MPEC constraint qualification for M-stationarity). Neither the new constraint qualification implies the MPEC generalized quasinormality, nor the MPEC generalized quasinormality implies the new constraint qualification. The new one ensures the validity of the local MPEC error bound under certain additional assumptions. We also have improved some recent results on the existence of a local error bound in the standard nonlinear program.     

Robust Duality in Parametric Convex Optimization

Modelling of convex optimization in the face of data uncertainty often gives rise to families of parametric convex optimization problems. This motivates us to present, in this paper, a duality framework for a family of parametric convex optimization problems. By employing conjugate analysis, we present robust duality for the family of parametric problems by establishing strong duality between associated dual pair. We first show that robust duality holds whenever a constraint qualification holds. We then show that this constraint qualification is also necessary for robust duality in the sense that the constraint qualification holds if and only if robust duality holds for every linear perturbation of the objective function. As an application, we obtain a robust duality theorem for the best approximation problems with constraint data uncertainty under a strict feasibility condition.     

Necessary and sufficient conditions for some constraint qualifications in quasiconvex programming

In this paper, we investigate relations between constraint qualifications in quasiconvex programming. At first, we show a necessary and sufficient condition for the closed cone constraint qualification for quasiconvex programming (Q-CCCQ), and investigate some sufficient conditions for the Q-CCCQ. Also, we consider a relation between the Q-CCCQ and the basic constraint qualification for quasiconvex programming (Q-BCQ) and we compare the Q-BCQ with some constraint qualifications.     

An extension of the Basic Constraint Qualification to nonconvex vector optimization problems

In this paper a Basic Constraint Qualification is introduced for a nonconvex infinite-dimensional vector optimization problem extending the usual one from convex programming assuming the Hadamard differentiability of the maps. Corresponding KKT conditions are established by considering a decoupling of the constraint cone into half-spaces. This extension leads to generalized KKT conditions which are finer than the usual abstract multiplier rule. A second constraint qualification expressed directly in terms of the data is also introduced, which allows us to compute the contingent cone to the feasible set and, as a consequence, it is proven that this condition is a particular case of the first one. Relationship with other constraint qualifications in infinite-dimensional vector optimization, specially with the Kurcyuscz-Robinson-Zowe constraint qualification, are also given.     

Abadie-Type Constraint Qualification for Mathematical Programs with Equilibrium Constraints

Mathematical programs with equilibrium constraints (MPEC) are nonlinear programs which do not satisfy any of the common constraint qualifications (CQ). In order to obtain first-order optimality conditions, constraint qualifications tailored to the MPECs have been developed and researched in the past. In this paper, we introduce a new Abadie-type constraint qualification for MPECs. We investigate sufficient conditions for this new CQ, discuss its relationship to several existing MPEC constraint qualifications, and introduce a new Slater-type constraint qualifications. Finally, we prove a new stationarity concept to be a necessary optimality condition under our new Abadie-type CQ.Communicated by Z. Q. Luo     

On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.     

多目标规划有效解的Kuhn—Tucker必要条件

本文提出一个新的约束规格,导出可微多目标规划的有效解的Kuhn-Tucker必要条件,并证明在此条件下,有效解是Kuhn-Tucker真有效解。     

Exact Penalty Functions for Convex Bilevel Programming Problems

In this paper, we propose a new constraint qualification for convex bilevel programming problems. Under this constraint qualification, a locally and globally exact penalty function of order 1 for a single-level reformulation of convex bilevel programming problems is given without requiring the linear independence condition and the strict complementarity condition to hold in the lower-level problem. Based on these results, locally and globally exact penalty functions for two other single-level reformulations of convex bilevel programming problems can be obtained. Furthermore, sufficient conditions for partial calmness to hold in some single-level reformulations of convex bilevel programming problems can be given.     

Enhanced Karush–Kuhn–Tucker Conditions for Mathematical Programs with Equilibrium Constraints

In this paper, we study necessary optimality conditions for nonsmooth mathematical programs with equilibrium constraints. We first show that, unlike the smooth case, the mathematical program with equilibrium constraints linear independent constraint qualification is not a constraint qualification for the strong stationary condition when the objective function is nonsmooth. We then focus on the study of the enhanced version of the Mordukhovich stationary condition, which is a weaker optimality condition than the strong stationary condition. We introduce the quasi-normality and several other new constraint qualifications and show that the enhanced Mordukhovich stationary condition holds under them. Finally, we prove that quasi-normality with regularity implies the existence of a local error bound.     

New Constraint Qualifications and Optimality Conditions for Second Order Cone Programs

We introduce three new constraint qualifications for nonlinear second order cone programming problems that we call constant rank constraint qualification, relaxed constant rank constraint qualification and constant rank of the subspace component condition. Our development is inspired by the corresponding constraint qualifications for nonlinear programming problems. We provide proofs and examples that show the relations of the three new constraint qualifications with other known constraint qualifications. In particular, the new constraint qualifications neither imply nor are implied by Robinson’s constraint qualification, but they are stronger than Abadie’s constraint qualification. First order necessary optimality conditions are shown to hold under the three new constraint qualifications, whereas the second order necessary conditions hold for two of them, the constant rank constraint qualification and the relaxed constant rank constraint qualification.

     

A nonsmooth variant of the Mangasarian-Fromovitz constraint qualification

A unified view on constraint qualifications for nonsmooth equality and inequality constrained programs is presented. A fairly general constraint qualification for programs involving B-differential functions is given. Further specification to piecewise differentiable equality constraints and locally Lipschitz continuous inequality constraints yields a nonsmooth version of the Mangasarian-Fromovitz constraint qualification.This work was supported by the Deutsche Forschungsgemeinschaft, DFG-Grant No. Pa 219/5-1.