Theorems of the alternative for conic integer programming

Farkas’ Lemma is a foundational result in linear programming, with implications in duality, optimality conditions, and stochastic and bilevel programming. Its generalizations are known as theorems of the alternative. There exist theorems of the alternative for integer programming and conic programming. We present theorems of the alternative for conic integer programming. We provide a nested procedure to construct a function that characterizes feasibility over right-hand sides and can determine which statement in a theorem of the alternative holds.     

Proving Strong Duality for Geometric Optimization Using a Conic Formulation

Geometric optimization¹ is an important class of problems that has many applications, especially in engineering design. In this article, we provide new simplified proofs for the well-known associated duality theory, using conic optimization. After introducing suitable convex cones and studying their properties, we model geometric optimization problems with a conic formulation, which allows us to apply the powerful duality theory of conic optimization and derive the duality results valid for geometric optimization.     

Duality Theorems on Multi-objective Programming of Generalized Functions

The form of a dual problem of Mond-Weir type for multi-objective programming problems of generalized functions is defined and theorems of the weak duality, direct duality and inverse duality are proven.     

Strong duality in robust semi-definite linear programming under data uncertainty

This article develops the deterministic approach to duality for semi-definite linear programming problems in the face of data uncertainty. We establish strong duality between the robust counterpart of an uncertain semi-definite linear programming model problem and the optimistic counterpart of its uncertain dual. We prove that strong duality between the deterministic counterparts holds under a characteristic cone condition. We also show that the characteristic cone condition is also necessary for the validity of strong duality for every linear objective function of the original model problem. In addition, we derive that a robust Slater condition alone ensures strong duality for uncertain semi-definite linear programs under spectral norm uncertainty and show, in this case, that the optimistic counterpart is also computationally tractable.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

Distributionally robust chance constraint with unimodality-skewness information and conic reformulation

Moment-based ambiguity sets are mostly used in distributionally robust chance constraints (DRCCs). Their conservatism can be reduced by imposing unimodality, but the known reformulations do not scale well. We propose a new ambiguity set tailored to unimodal and seemingly symmetric distributions by encoding unimodality-skewness information, which leads to conic reformulations of DRCCs that are more tractable than known ones based on semi-definite programs. Besides, the conic reformulation yields a closed-form expression of the inverse of unimodal Cantelli's bound.     

Lifting for conic mixed-integer programming

Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify the computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative orthants, conic lifting reduces to the lifting for linear integer programming as one may expect.     

Space tensor conic programming

Space tensors appear in physics and mechanics. Mathematically, they are tensors in the three-dimensional Euclidean space. In the research area of diffusion magnetic resonance imaging, convex optimization problems are formed where higher order positive semi-definite space tensors are involved. In this short paper, we investigate these problems from the viewpoint of conic linear programming (CLP). We characterize the dual cone of the positive semi-definite space tensor cone, and study the CLP formulation and the duality of positive semi-definite space tensor conic programming.     

On zero duality gap in nonconvex quadratic programming problems

We present in this paper new sufficient conditions for verifying zero duality gap in nonconvex quadratically/linearly constrained quadratic programs (QP). Based on saddle point condition and conic duality theorem, we first derive a sufficient condition for the zero duality gap between a quadratically constrained QP and its Lagrangian dual or SDP relaxation. We then use a distance measure to characterize the duality gap for nonconvex QP with linear constraints. We show that this distance can be computed via cell enumeration technique in discrete geometry. Finally, we revisit two sufficient optimality conditions in the literature for two classes of nonconvex QPs and show that these conditions actually imply zero duality gap.     

Cuts for mixed 0-1 conic programming

In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomory cuts for mixed 0-1 conic programs have interesting implications for comparing the semidefinite programming and the linear programming relaxations of combinatorial optimization problems, e.g. we show that all the subtour elimination inequalities for the traveling salesman problem are rank-1 Gomory cuts with respect to a single semidefinite constraint. We also include results from our preliminary computational experiments with these cuts.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

The minimal cone for conic linear programming

It is known that the minimal cone for the constraint system of a conic linear programming problem is a key component in obtaining strong duality without any constraint qualification. For problems in either primal or dual form, the minimal cone can be written down explicitly in terms of the problem data. However, due to possible lack of closure, explicit expressions for the dual cone of the minimal cone cannot be obtained in general. In the particular case of semidefinite programming, an explicit expression for the dual cone of the minimal cone allows for a dual program of polynomial size that satisfies strong duality. In this paper we develop a recursive procedure to obtain the minimal cone and its dual cone. In particular, for conic problems with so-called nice cones, we obtain explicit expressions for the cones involved in the dual recursive procedure. As an example of this approach, the well-known duals that satisfy strong duality for semidefinite programming problems are obtained. The relation between this approach and a facial reduction algorithm is also discussed.     

Solving asymmetric variational inequalities via convex optimization

Using duality, we reformulate the asymmetric variational inequality (VI) problem over a conic region as an optimization problem. We give sufficient conditions for the convexity of this reformulation. We thereby identify a class of VIs that includes monotone affine VIs over polyhedra, which may be solved by commercial optimization solvers.     

均衡约束数学规划问题的一类广义Mond-Weir型对偶理论

针对均衡约束数学规划模型难以满足约束规范及难于求解的问题,基于Mond和Weir提出的标准非线性规划的对偶形式,利用其S稳定性,建立了均衡约束数学规划问题的一类广义Mond-Weir型对偶,从而为求解均衡约束优化问题提供了一种新的方法.在Hanson-Mond广义凸性条件下,利用次线性函数,分别提出了弱对偶性、强对偶性和严格逆对偶性定理,并给出了相应证明.该对偶化方法的推广为研究均衡约束数学规划问题的解提供了理论依据.     

Conic Formulation for l p -Norm Optimization

In this paper, we formulate the l _p -norm optimization problem as a conic optimization problem, derive its duality properties (weak duality, zero duality gap, and primal attainment) using standard conic duality and show how it can be solved in polynomial time applying the framework of interior-point algorithms based on self-concordant barriers.     

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.     

Solving 0–1 semidefinite programs for distributionally robust allocation of surgery blocks

We allocate surgery blocks to operating rooms (ORs) under random surgery durations. Given unknown distribution of the duration of each block, we investigate distributionally robust (DR) variants of two types of stochastic programming models using a moment-based ambiguous set. We minimize the total cost of opening ORs and allocating surgery blocks, while constraining OR overtime via chance constraints and via an expected penalty cost in the objective function, respectively in the two types of models. Following conic duality, we build equivalent 0–1 semidefinite programming (SDP) reformulations of the DR models and solve them using cutting-plane algorithms. For the DR chance-constrained model, we also derive a 0–1 second-order conic programming approximation to obtain less conservative solutions. We compare different models and solution methods by testing randomly generated instances. Our results show that the DR chance-constrained model better controls average and worst-case OR overtime, as compared to the stochastic programming and DR expected-penalty-based models. Our cutting-plane algorithms also outperform standard optimization solvers and efficiently solve 0–1 SDP formulations.     

Universal duality in conic convex optimization

Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +∞ and −∞. In contrast, for optimization problems over nonpolyhedral convex cones, a nonzero duality gap can exist when either the primal or the dual is feasible. For a pair of dual conic convex programs, we provide simple conditions on the ``constraint matrices' and cone under which the duality gap is zero for every choice of linear objective function and constraint right-hand side. We refer to this property as ``universal duality'. Our conditions possess the following properties: (i) they are necessary and sufficient, in the sense that if (and only if) they do not hold, the duality gap is nonzero for some linear objective function and constraint right-hand side; (ii) they are metrically and topologically generic; and (iii) they can be verified by solving a single conic convex program. We relate to universal duality the fact that the feasible sets of a primal convex program and its dual cannot both be bounded, unless they are both empty. Finally we illustrate our theory on a class of semidefinite programs that appear in control theory applications. This work was supported by a fellowship at the University of Maryland, in addition to NSF grants DEMO-9813057, DMI0422931, CUR0204084, and DoE grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

Unifying Optimal Partition Approach to Sensitivity Analysis in Conic Optimization

We study convex conic optimization problems in which the right-hand side and the cost vectors vary linearly as functions of a scalar parameter. We present a unifying geometric framework that subsumes the concept of the optimal partition in linear programming (LP) and semidefinite programming (SDP) and extends it to conic optimization. Similar to the optimal partition approach to sensitivity analysis in LP and SDP, the range of perturbations for which the optimal partition remains constant can be computed by solving two conic optimization problems. Under a weaker notion of nondegeneracy, this range is simply given by a minimum ratio test. We discuss briefly the properties of the optimal value function under such perturbations.     

Duality in infinite dimensional linear programming

We consider the class of linear programs with infinitely many variables and constraints having the property that every constraint contains at most finitely many variables while every variable appears in at most finitely many constraints. Examples include production planning and equipment replacement over an infinite horizon. We form the natural dual linear programming problem and prove strong duality under a transversality condition that dual prices are asymptotically zero. That is, we show, under this transversality condition, that optimal solutions are attained in both primal and dual problems and their optimal values are equal. The transversality condition, and hence strong duality, is established for an infinite horizon production planning problem.This material is based on work supported by the National Science Foundation under Grant No. ECS-8700836.