Sequential Lagrangian Conditions for Convex Programs with Applications to Semidefinite Programming

In this paper it is shown that, in the absence of any regularity condition, sequential Lagrangian optimality conditions as well as a sequential duality results hold for abstract convex programs. The significance of the results is that they yield the standard optimality and duality results for convex programs under a simple closed-cone condition that is much weaker than the well-known constraint qualifications. As an application, a sequential Lagrangian duality, saddle-point conditions, and stability results are derived for convex semidefinite programs.The authors are grateful to the referee and Professor Franco Giannessi for valuable comments and constructive suggestions which have contributed to the final preparation of the paper.     

Necessary and Sufficient Constraint Qualification for Surrogate Duality

In mathematical programming, constraint qualifications are essential elements for duality theory. Recently, necessary and sufficient constraint qualifications for Lagrange duality results have been investigated. Also, surrogate duality enables one to replace the problem by a simpler one in which the constraint function is a scalar one. However, as far as we know, a necessary and sufficient constraint qualification for surrogate duality has not been proposed yet. In this paper, we propose necessary and sufficient constraint qualifications for surrogate duality and surrogate min–max duality, which are closely related with ones for Lagrange duality.     

Bounded Lagrange multiplier rules for general nonsmooth problems and application to mathematical programs with equilibrium constraints

In this paper, a general optimization problem is considered to investigate the conditions which ensure the existence of Lagrangian vectors with a norm not greater than a fixed positive number. In addition, the nonemptiness and boundedness of the multiplier sets together with their exact upper bounds is characterized. Moreover, three new constraint qualifications are suggested that each of them follows a degree of boundedness for multiplier vectors. Several examples at the end of the paper indicate that the upper bound for Lagrangian vectors is easily computable using each of our constraint qualifications. One innovation is introducing the so-called bounded Lagrangian constraint qualification which is stated based on the nonemptiness and boundedness of all possible Lagrangian sets. An application of the results for a mathematical program with equilibrium constraints is presented.     

Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems

In this paper we first establish a Lagrange multiplier condition characterizing a regularized Lagrangian duality for quadratic minimization problems with finitely many linear equality and quadratic inequality constraints, where the linear constraints are not relaxed in the regularized Lagrangian dual. In particular, in the case of a quadratic optimization problem with a single quadratic inequality constraint such as the linearly constrained trust-region problems, we show that the Slater constraint qualification (SCQ) is necessary and sufficient for the regularized Lagrangian duality in the sense that the regularized duality holds for each quadratic objective function over the constraints if and only if (SCQ) holds. A new theorem of the alternative for systems involving both equality constraints and two quadratic inequality constraints plays a key role. We also provide classes of quadratic programs, including a class of CDT-subproblems with linear equality constraints, where (SCQ) ensures regularized Lagrangian duality.     

Duality Theorems for Separable Convex Programming Without Qualifications

In the research of mathematical programming, duality theorems are essential and important elements. Recently, Lagrange duality theorems for separable convex programming have been studied. Tseng proves that there is no duality gap in Lagrange duality for separable convex programming without any qualifications. In other words, although the infimum value of the primal problem equals to the supremum value of the Lagrange dual problem, Lagrange multiplier does not always exist. Jeyakumar and Li prove that Lagrange multiplier always exists without any qualifications for separable sublinear programming. Furthermore, Jeyakumar and Li introduce a necessary and sufficient constraint qualification for Lagrange duality theorem for separable convex programming. However, separable convex constraints do not always satisfy the constraint qualification, that is, Lagrange duality does not always hold for separable convex programming. In this paper, we study duality theorems for separable convex programming without any qualifications. We show that a separable convex inequality system always satisfies the closed cone constraint qualification for quasiconvex programming and investigate a Lagrange-type duality theorem for separable convex programming. In addition, we introduce a duality theorem and a necessary and sufficient optimality condition for a separable convex programming problem, whose constraints do not satisfy the Slater condition.     

Necessary and sufficient constraint qualifications for solvability of systems of infinite convex inequalities

In this paper we present constraint qualifications which completely characterize the Farkas–Minkowski and the locally Farkas–Minkowski convex (possibly infinite) inequality systems posed in topological vector spaces. The number of constraints and the dimension of the linear space are arbitrary (possibly infinite). The constraint qualifications considered in this paper are expressed in terms of the solvability of certain parametric convex (linear) systems and the uniform strong duality or the uniform min–max duality relative to the Lagrange (Haar) dual problems of suitable convex (linear) parametric optimization problems.     

Zero duality gap in surrogate constraint optimization: A concise review of models

Surrogate constraint relaxation was proposed in the 1960s as an alternative to the Lagrangian relaxation for solving difficult optimization problems. The duality gap in the surrogate relaxation is always as good as the duality gap in the Lagrangian relaxation. Over the years researchers have proposed procedures to reduce the gap in the surrogate constraint. Our aim is to review models that close the surrogate duality gap. Five research streams that provide procedures with zero duality gap are identified and discussed. In each research stream, we will review major results, discuss limitations, and suggest possible future research opportunities. In addition, relationships between models if they exist, are also discussed.     

Optimality conditions for nondifferentiable convex semi-infinite programming

This paper gives characterizations of optimal solutions to the nondifferentiable convex semi-infinite programming problem, which involve the notion of Lagrangian saddlepoint. With the aim of giving the necessary conditions for optimality, local and global constraint qualifications are established. These constraint qualifications are based on the property of Farkas-Minkowski, which plays an important role in relation to certain systems obtained by linearizing the feasible set. It is proved that Slater's qualification implies those qualifications.     

Nonlinear Lagrangian Theory for Nonconvex Optimization

The Lagrangian function in the conventional theory for solving constrained optimization problems is a linear combination of the cost and constraint functions. Typically, the optimality conditions based on linear Lagrangian theory are either necessary or sufficient, but not both unless the underlying cost and constraint functions are also convex.We propose a somewhat different approach for solving a nonconvex inequality constrained optimization problem based on a nonlinear Lagrangian function. This leads to optimality conditions which are both sufficient and necessary, without any convexity assumption. Subsequently, under appropriate assumptions, the optimality conditions derived from the new nonlinear Lagrangian approach are used to obtain an equivalent root-finding problem. By appropriately defining a dual optimization problem and an alternative dual problem, we show that zero duality gap will hold always regardless of convexity, contrary to the case of linear Lagrangian duality.     

Surrogate duality for robust optimization

Robust optimization problems, which have uncertain data, are considered. We prove surrogate duality theorems for robust quasiconvex optimization problems and surrogate min–max duality theorems for robust convex optimization problems. We give necessary and sufficient constraint qualifications for surrogate duality and surrogate min–max duality, and show some examples at which such duality results are used effectively. Moreover, we obtain a surrogate duality theorem and a surrogate min–max duality theorem for semi-definite optimization problems in the face of data uncertainty.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

Stable and Total Fenchel Duality for Composed Convex Optimization Problems

In this paper, we consider the composed convex optimization problem which consists in minimizing the sum of a convex function and a convex composite function. By using the properties of the epigraph of the conjugate functions and the subdifferentials of convex functions, we give some new constraint qualifications which completely characterize the strong Fenchel duality and the total Fenchel duality for composed convex optimiztion problem in real locally convex Hausdorff topological vector spaces.     

Converse duality in Banach space

Two theorems on converse duality are obtained for mathematical programs in Banach spaces. The proofs are based on a Banach-space generalization of the F. John necessary condition for a constrained minimum. No use is made of Kuhn-Tucker constraint qualifications. In the second theorem, the primal program contains a nonlinear equality constraint, and a converse duality theorem is obtained, using a modified concept of convexity; this result appears new, even for finite-dimensional programs. The results are applied to a problem in optimal control.     

Farkas’ lemma for separable sublinear inequalities without qualifications

We show that the celebrated Farkas lemma for linear inequality systems continues to hold for separable sublinear inequality systems. As a consequence, we establish a qualification-free characterization of optimality for separable sublinear programming problems which include classes of robust linear programming problems. We also deduce that the Lagrangian duality always holds for these programming problems without qualifications.     

Lagrange duality in canonical DC programming

We study Lagrange duality theorems for canonical DC programming problems. We show two types Lagrange duality results by using a decomposition method to infinite convex programming problems and by using a previous result by Lemaire (1998)  [6]. Also we observe these constraint qualifications for the duality theorems.     

On the sufficiency of finite support duals in semi-infinite linear programming

We consider semi-infinite linear programs with countably many constraints indexed by the natural numbers. When the constraint space is the vector space of all real valued sequences, we show that the finite support (Haar) dual is equivalent to the algebraic Lagrangian dual of the linear program. This settles a question left open by Anderson and Nash (1987). This result implies that if there is a duality gap between the primal linear program and its finite support dual, then this duality gap cannot be closed by considering the larger space of dual variables that define the algebraic Lagrangian dual. However, if the constraint space corresponds to certain subspaces of all real-valued sequences, there may be a strictly positive duality gap with the finite support dual, but a zero duality gap with the algebraic Lagrangian dual.     

带消失约束的区间值优化问题的最优性条件与对偶定理

本文考虑一类带消失约束的非光滑区间值优化问题(IOPVC)。在一定的约束条件下得到了问题(IOPVC)的LU最优解的必要和充分性最优性条件,研究了其与Mond-Weir型对偶模型和Wolfe型对偶模型之间的弱对偶,强对偶和严格逆对偶定理,并给出了一些例子来阐述我们的结果。     

Augmented Lagrangian functions for constrained optimization problems

In this paper, in order to obtain some existence results about solutions of the augmented Lagrangian problem for a constrained problem in which the objective function and constraint functions are noncoercive, we construct a new augmented Lagrangian function by using an auxiliary function. We establish a zero duality gap result and a sufficient condition of an exact penalization representation for the constrained problem without the coercive or level-bounded assumption on the objective function and constraint functions. By assuming that the sequence of multipliers is bounded, we obtain the existence of a global minimum and an asymptotically minimizing sequence for the constrained optimization problem.     

向量映射的鞍点和Lagrange对偶问题

本文研究拓扑向量空间广义锥-次类凸映射向量优化问题的鞍点最优性条件和Lagrange对偶问题,建立向量优化问题的Fritz John鞍点和Kuhn-Tucker鞍点的最优性条件及其与向量优化问题的有效解和弱有效解之间的联系。通过对偶问题和向量优化问题的标量化刻画各解之间的关系,给出目标映射是广义锥-次类凸的向量优化问题在其约束映射满足广义Slater约束规格的条件下的对偶定理。     

Liberating the Subgradient Optimality Conditions from Constraint Qualifications

In convex optimization the significance of constraint qualifications is evidenced by the simple duality theory, and the elegant subgradient optimality conditions which completely characterize a minimizer. However, the constraint qualifications do not always hold even for finite dimensional optimization problems and frequently fail for infinite dimensional problems. In the present work we take a broader view of the subgradient optimality conditions by allowing them to depend on a sequence of ε-subgradients at a minimizer and then by letting them to hold in the limit. Liberating the optimality conditions in this way permits us to obtain a complete characterization of optimality without a constraint qualification. As an easy consequence of these results we obtain optimality conditions for conic convex optimization problems without a constraint qualification. We derive these conditions by applying a powerful combination of conjugate analysis and ε-subdifferential calculus. Numerical examples are discussed to illustrate the significance of the sequential conditions.