A simple constraint qualification in infinite dimensional programming

A new, simple, constraint qualification for infinite dimensional programs with linear programming type constraints is used to derive the dual program; see Theorem 3.1. Applications include a proof of the explicit solution of the best interpolation problem presented in [8].     

A constraint qualification for convex programming

1. IntroductionLet X be the n-dimensional Euclidean space Rad. Denote the transpose of the columnvector y by yT. Suppose that R7 and nit R= are the n-dimensional vector sets with nonnegative and positive components, whose elements are denoted by y 3 0 and y > 0, respectively.Write R for the nonnegative real number set.Consider a nondiffereatiable convex programming problem:We assume that f(x), gi(x),..', g.(x) are finite reaLvalued continuous, convex functions on X, but not necessarily d…     

Characterization of optimality in convex programming without a constraint qualification

Necessary and sufficient conditions of optimality are given for convex programming problems with no constraint qualification. The optimality conditions are stated in terms of consistency or inconsistency of a family of systems of linear inequalities and cone relations.This research was supported by Project No. NR-047-021, ONR Contract No. N00014-67-A-0126-0009 with the Center for Cybernetics Studies, The University of Texas; by NSF Grant No. ENG-76-10260 at Northwestern University; and by the National Research Council of Canada.     

Optimality conditions and the basic constraint qualification for quasiconvex programming

In this paper, we consider optimality conditions and a constraint qualification for quasiconvex programming. For this purpose, we introduce a generator and a new subdifferential for quasiconvex functions by using Penot and Volle’s theorem.     

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.     

On the Guignard constraint qualification for mathematical programs with equilibrium constraints

We recapitulate the well-known fact that most of the standard constraint qualifications are violated for mathematical programs with equilibrium constraints (MPECs). We go on to show that the Abadie constraint qualification is only satisfied in fairly restrictive circumstances. In order to avoid this problem, we fall back on the Guignard constraint qualification (GCQ). We examine its general properties and clarify the position it occupies in the context of MPECs. We show that strong stationarity is a necessary optimality condition under GCQ. Also, we present several sufficient conditions for GCQ, showing that it is usually satisfied for MPECs.     

Augmented Lagrangian methods under the constant positive linear dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented. The authors were supported by PRONEX - CNPq / FAPERJ E-26 / 171.164/2003 - APQ1, FAPESP (Grants 2001/04597-4, 2002/00094-0, 2003/09169-6, 2002/00832-1 and 2005/56773-1) and CNPq.     

Numerical examples of the behavior of REQP on nonlinear programming problems involving linear dependence among the constraint normals

This report illustrates, by means of numerical examples, the behavior of the constrained minimization algorithm REQP in situations where the active constraint normals are not linearly independent. The examples are intended to demonstrate that the presence of the penalty parameter in the equations for calculating the Lagrange multiplier estimates enables a useful search direction to be computed. This is shown to be true, whether the dependence among the constraint normals occurs at the solution or in some other region.     

On zero duality gap in surrogate constraint optimization: The case of rational-valued functions of constraints

This paper is concerned with the constrained optimization problem. A detailed discussion of surrogate constraints with zero duality gaps is presented. Readily available surrogate multipliers are considered that close the duality gaps where constraints are rational-valued. Through illustrative examples, the sources of duality gaps are examined in detail. While in the published literature, in many situations conclusions have been made about the existence of non-zero duality gaps, we show that taking advantage of full problem information can close the duality gaps. Overlooking such information can produce shortcomings in the research in which a non-zero duality gap is observed. We propose theorems to address the shortcomings and report results regarding implementation issues.     

Second-order and related extremality conditions in nonlinear programming

This paper is concerned with the problem of characterizing a local minimum of a mathematical programming problem with equality and inequality constraints. The main object is to derive second-order conditions, involving the Hessians of the functions, or related results where some other curvature information is used. The necessary conditions are of the Fritz John type and do not require a constraint qualification. Both the necessary conditions and the sufficient conditions are given in equivalent pairs of primal and dual formulations.This research was partly supported by Project No. NR-947-021, ONR Contract No. N00014-75-0569, with the Center for Cybernetic Studies, and by the National Science Foundation, Grant No. NSF-ENG-76-10260.     

Mixed duality without a constraint qualification for minimax fractional programming

Without the need of a constraint qualification, we establish the necessary and sufficient optimality conditions for minimax fractional programming. Using these optimality conditions, we construct a mixed dual model which unifies the Mond–Weir dual, Wolfe dual and a parameter dual models. Several duality theorems are established. Consequently, this article partly solves the problem posed by Lai et al. [H.C. Lai, J.C. Liu and K. Tanaka (1999). Duality without a constraint qualification for minimax fractional programming. Journal of Optimization Theory and Applications, 101, 109–125.].     

A generalized karush-kuhn-tucki optimality condition without constraint qualification using tl approximate subdifferential

A generalized Karush-Kuhn-Tucker first order optimality condition is established for an abstract cone-constrained programming problem involving locally Lipschitz functions using the approximate subdifferential. This result is obtained without recourse to a constraint qualification by imposing additional generalized convexity conditions on the constraint functions. A new Fritz John optimality condition is developed as a precursor to the main result. Several examples are provided to illustrate the results along with a discussion of applications to concave minimization problems and to stochastic programming problems with nonsmooth data.     

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.     

Error bounds for nondifferentiable convex inequalities under a strong Slater constraint qualification

A global error bound is given on the distance between an arbitrary point in then-dimensional real spaceR ⁿ and its projection on a nonempty convex set determined bym convex, possibly nondifferentiable, inequalities. The bound is in terms of a natural residual that measures the violations of the inequalities multiplied by a new simple condition constant that embodies a single strong Slater constraint qualification (CQ) which implies the ordinary Slater CQ. A very simple bound on the distance to the projection relative to the distance to a point satisfying the ordinary Slater CQ is given first and then used to derive the principal global error bound. This material is based on research supported by National Science Foundation Grant CCR-9322479 and Air Force Office of Scientific Research grant F49620-97-1-0326.     

A heuristic algorithm for a chance constrained stochastic program

A chance constrained stochastic program is considered that arises from an application to college enrollments and in which the objective function is the expectation of a linear function of the random variables. When these random variables are independent and normally distributed with mean and variance that are linear in the decision variables, the deterministic equivalent of the problem is a nonconvex nonlinear knapsack problem. The optimal solution to this problem is characterized and a greedy-type heuristic algorithm that exploits this structure is employed. Computational results show that the algorithm performs well, especially when the normal random variables are approximations of binomial random variables.     

Nonsmooth multiobjective programming and constraint qualifications

We consider a nonsmooth multiobjective programming problem with inequality and set constraints. By using the notion of convexificator, we extend the Abadie constraint qualification, and derive the strong Kuhn-Tucker necessary optimality conditions. Some other constraint qualifications have been generalized and their interrelations are investigated.     

A semistrong sufficiency condition for optimality in nonconvex programming and its connection to the perturbation problem

What happens when a nonconvex program, having a local solutionx ⁰ at which the gradients of the binding constraints are linearly independent, but without strict complementarity hypothesis, is perturbed? Under a relatively weak second-order assumption (some nonnegative second-order terms are supposed to be strictly positive), the perturbed problem has, in the neighborhood ofx ⁰, a finite number of local minima, situated on curves that are connected to some pseudo-solutions of the tangent quadratic problem.     

A general multiplier rule

An extension of a general multiplier rule derived by Gittleman, which in turn is an extension of a theorem due to Hestenes, is proved. The extension requires a less complicated definition of derived set.     

Relation between the constant rank and the relaxed constant rank constraint qualifications

This article discusses a relation between the constant rank constraint qualification (CRCQ) and the recently proposed relaxed constant rank constraint qualification (RCRCQ). We show that a parametric constraint system satisfying the RCRCQ is locally diffeomorphic to a system satisfying the CRCQ. We use this result to extend some existing results for the CRCQ to the RCRCQ, establish a relation between the RCRCQ and the Mangasarian–Fromovitz constraint qualification, and obtain a weakened version of the Aubin property under the RCRCQ.