Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.     

Exploiting nested inequalities and surrogate constraints

The exploitation of nested inequalities and surrogate constraints as originally proposed in Glover [Glover, F., 1965. A multiphase-dual algorithm for the zero–one integer programming problem. Operations Research 13, 879–919; Glover, F., 1971. Flows in arborescences. Management Science 17, 568–586] has been specialized to multidimensional knapsack problems in Osorio et al. [Osorio, M.A., Glover, F., Hammer, P., 2002. Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions. Annals of Operations Research 117, 71–93]. We show how this specialized exploitation can be strengthened to give better results. This outcome results by a series of observations based on surrogate constraint duality and properties of nested inequalities. The consequences of these observations are illustrated by numerical examples to provide insights into uses of surrogate constraints and nested inequalities that can be useful in a variety of problem settings.     

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.     

New strong duality results for convex programs with separable constraints

It is known that convex programming problems with separable inequality constraints do not have duality gaps. However, strong duality may fail for these programs because the dual programs may not attain their maximum. In this paper, we establish conditions characterizing strong duality for convex programs with separable constraints. We also obtain a sub-differential formula characterizing strong duality for convex programs with separable constraints whenever the primal problems attain their minimum. Examples are given to illustrate our results.     

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.     

基于广义几何规划的最小广义信息密度区分问题及其对偶理论

§ 1　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｑｕａｄｒａｔｉｃａｌｌｙｃｏｎｓｔｒａｉｎｅｄａｎｄｅｎｔｒｏｐｙｄｅｎｓｉｔｙｃｏｎｓｔｒａｉｎｅｄｑｕａｄｒａｔｉｃｐｒｏｇｒａｍｔｈａｔｉｓｇｏｉｎｇｔｏｂｅｓｔｕｄｉｅｄｉｎｔｈｉｓｐａｐｅｒｉｓｃｈａｒａｃｔｅｒｉｚｅｄａｓｔｈｅｆｏｌｌｏｗｉｎｇｆｏｒｍ :Ｐｒｏｇｒａｍ (Ｑ)(Ｑ)　　ｍｉｎ　Ｑ0 (ｚ)ｓ .ｔ .　Ｐｊ(ｚ)≤ 0 ,　ｊ =1 ,2 ,...,ｌ,Ｑｉ(ｚ) ≤ 0 ,　ｉ =1 ,2 ,...,ｒ ,ｚ=(ｚ1,...,ｚｎ) Ｔ ≥ 0 ,ｗｈｅｒｅＰｊ(ｚ) = ｎｋ =1ｚｋｌｏｇ ｚｋｅ…     

E-凸多目标规划的最优性及Wolfe型对偶

先引入了一类带不等式和等式约束的E-凸多目标优化问题(MP),给出了该类问题的一个最优性充分条件;其次,建立了该类规划问题(MP)的一类Wolfe型对偶模型(WD),并在E-凸条件下,获得了弱对偶定理,强对偶定理和逆对偶定理.     

Duality gaps in nonconvex stochastic optimization

We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal decomposition. The second group of results concerns large stochastic optimization models with loosely coupled components. The results provide conditions implying relations between the duality gaps of geographical decomposition and the duality gaps for scenario and nodal decomposition, respectively.Mathematics Subject Classification (1991): 90C15Acknowledgments. This work was supported by the Priority Programme Online Optimization of Large Scale Systems of the Deutsche Forschungsgemeinschaft. The authors wish to thank Andrzej Ruszczyski (Rutgers University) for helpful discussions.     

Surrogate duality for vector optimization

Using our theorems (of [12]) on separation of convex sets by linear operators, in the sense of the lexi-cographical order on Rⁿ, we prove some theorems of surrogate duality for vector optimization problems with convex constraints (but no regularity assumption), where the surrogate constraint sets are generalized half-spaces and the surrogate multipliers are linear operators, or isomorphisms, or isometries. In the cae of inequality constraints, we prove that the surrogate multipliers can be taken lexicographically non-negative isometries or non-negative (in the usual order) linear isomorphisms.     

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.     

On duality theory of convex semi-infinite programming

In this article we discuss weak and strong duality properties of convex semi-infinite programming problems. We use a unified framework by writing the corresponding constraints in a form of cone inclusions. The consequent analysis is based on the conjugate duality approach of embedding the problem into a parametric family of problems parameterized by a finite-dimensional vector.     

Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality

In this paper we show that a convexifiability property of nonconvex quadratic programs with nonnegative variables and quadratic constraints guarantees zero duality gap between the quadratic programs and their semi-Lagrangian duals. More importantly, we establish that this convexifiability is hidden in classes of nonnegative homogeneous quadratic programs and discrete quadratic programs, such as mixed integer quadratic programs, revealing zero duality gaps. As an application, we prove that robust counterparts of uncertain mixed integer quadratic programs with objective data uncertainty enjoy zero duality gaps under suitable conditions. Various sufficient conditions for convexifiability are also given.     

Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality

This paper presents a canonical duality theory for solving a general nonconvex quadratic minimization problem with nonconvex constraints. By using the canonical dual transformation developed by the first author, the nonconvex primal problem can be converted into a canonical dual problem with zero duality gap. A general analytical solution form is obtained. Both global and local extrema of the nonconvex problem can be identified by the triality theory associated with the canonical duality theory. Illustrative applications to quadratic minimization with multiple quadratic constraints, box/integer constraints, and general nonconvex polynomial constraints are discussed, along with insightful connections to classical Lagrangian duality. Criteria for the existence and uniqueness of optimal solutions are presented. Several numerical examples are provided.     

Inverse stochastic dominance constraints and rank dependent expected utility theory

We consider optimization problems with second order stochastic dominance constraints formulated as a relation of Lorenz curves. We characterize the relation in terms of rank dependent utility functions, which generalize Yaari's utility functions. We develop optimality conditions and duality theory for problems with Lorenz dominance constraints. We prove that Lagrange multipliers associated with these constraints can be identified with rank dependent utility functions. The problem is numerically tractable in the case of discrete distributions with equally probable realizations. Research supported by the NSF awards DMS-0303545, DMS-0303728, DMI-0354500 and DMI-0354678.     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

A note on strong duality in convex semidefinite optimization: necessary and sufficient conditions

A strong duality which states that the optimal values of the primal convex problem and its Lagrangian dual problem are equal (i.e. zero duality gap) and the dual problem attains its maximum is a corner stone in convex optimization. In particular it plays a major role in the numerical solution as well as the application of convex semidefinite optimization. The strong duality requires a technical condition known as a constraint qualification (CQ). Several CQs which are sufficient for strong duality have been given in the literature. In this note we present new necessary and sufficient CQs for the strong duality in convex semidefinite optimization. These CQs are shown to be sharper forms of the strong conical hull intersection property (CHIP) of the intersecting sets of constraints which has played a critical role in other areas of convex optimization such as constrained approximation and error bounds. Research was partially supported by the Australian Research Council. The author is grateful to the referees for their helpful comments     

Development of a new approach for deterministic supply chain network design

This paper proposes a mixed integer linear programming model and solution algorithm for solving supply chain network design problems in deterministic, multi-commodity, single-period contexts. The strategic level of supply chain planning and tactical level planning of supply chain are aggregated to propose an integrated model. The model integrates location and capacity choices for suppliers, plants and warehouses selection, product range assignment and production flows. The open-or-close decisions for the facilities are binary decision variables and the production and transportation flow decisions are continuous decision variables. Consequently, this problem is a binary mixed integer linear programming problem. In this paper, a modified version of Benders’ decomposition is proposed to solve the model. The most difficulty associated with the Benders’ decomposition is the solution of master problem, as in many real-life problems the model will be NP-hard and very time consuming. In the proposed procedure, the master problem will be developed using the surrogate constraints. We show that the main constraints of the master problem can be replaced by the strongest surrogate constraint. The generated problem with the strongest surrogate constraint is a valid relaxation of the main problem. Furthermore, a near-optimal initial solution is generated for a reduction in the number of iterations.     

A dual approach to solve the fuzzy linear programming problem

A concept of fuzzy objective based on the Fuzzification Principle is presented. In accordance with this concept, the Fuzzy Linear Mathematical Programming problem is easily solved. A relationship of duality among fuzzy constraints and fuzzy objectives is given. The dual problem of a Fuzzy Linear Programming problem is also defined.     

Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints

A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.     

Linear optimal control problem for discrete 2-D systems with constraints

Optimal control problem for linear two-dimensional (2-D) discrete systems with mixed constraints is investigated. The problem under consideration is reduced to a linear programming problem in appropriate Hubert space. The main duality relations for this problem is derived such that the optimality conditions for the control problem are specified by using methods of the linear operator theory. Optimality conditions are expressed in terms of solutions for conjugate system.