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.     

Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

Robust least square semidefinite programming with applications

In this paper, we consider a least square semidefinite programming problem under ellipsoidal data uncertainty. We show that the robustification of this uncertain problem can be reformulated as a semidefinite linear programming problem with an additional second-order cone constraint. We then provide an explicit quantitative sensitivity analysis on how the solution under the robustification depends on the size/shape of the ellipsoidal data uncertainty set. Next, we prove that, under suitable constraint qualifications, the reformulation has zero duality gap with its dual problem, even when the primal problem itself is infeasible. The dual problem is equivalent to minimizing a smooth objective function over the Cartesian product of second-order cones and the Euclidean space, which is easy to project onto. Thus, we propose a simple variant of the spectral projected gradient method (Birgin et al. in SIAM J. Optim. 10:1196–1211, 2000) to solve the dual problem. While it is well-known that any accumulation point of the sequence generated from the algorithm is a dual optimal solution, we show in addition that the dual objective value along the sequence generated converges to a finite value if and only if the primal problem is feasible, again under suitable constraint qualifications. This latter fact leads to a simple certificate for primal infeasibility in situations when the primal feasible set lies in a known compact set. As an application, we consider robust correlation stress testing where data uncertainty arises due to untimely recording of portfolio holdings. In our computational experiments on this particular application, our algorithm performs reasonably well on medium-sized problems for real data when finding the optimal solution (if exists) or identifying primal infeasibility, and usually outperforms the standard interior-point solver SDPT3 in terms of CPU time.     

Lagrangian duality for a class of infinite programming problems

First-order necessary conditions of the Kuhn-Tucker type and strong duality are established for a general class of continuous time programming problems. To obtain these results a generalized Farkas' Theorem, stated in terms of convex and dual cones, is implemented in conjunction with a constraint qualification analogous to that found in finite-dimensional programming. The assumptions imposed are weaker than those needed in previous approaches to duality for this type of problem.     

多目标半定规划的最优性条件及对偶理论

在不变凸的假设下来讨论多目标半定规划的最优性条件、对偶理论以及非凸半定规划的最优性条件．首先给出了非凸半定规划的一个KKT条件成立的充分必要条件, 并利用此定理证明了其最优性必要条件．其次讨论了多目标半定规划的最优性必要条件、充分条件, 并对其建立Wolfe对偶模型, 证明了弱对偶定理和强对偶定理．     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

Understanding linear semi-infinite programming via linear programming over cones

In this article, the standard primal and dual linear semi-infinite programming (DLSIP) problems are reformulated as linear programming (LP) problems over cones. Therefore, the dual formulation via the minimal cone approach, which results in zero duality gap for the primal–dual pair for LP problems over cones, can be applied to linear semi-infinite programming (LSIP) problems. Results on the geometry of the set of the feasible solutions for the primal LSIP problem and the optimality criteria for the DLSIP problem are also discussed.     

Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones

We describe an implementation of nonsymmetric interior-point methods for linear cone programs defined by two types of matrix cones: the cone of positive semidefinite matrices with a given chordal sparsity pattern and its dual cone, the cone of chordal sparse matrices that have a positive semidefinite completion. The implementation takes advantage of fast recursive algorithms for evaluating the function values and derivatives of the logarithmic barrier functions for these cones. We present experimental results of two implementations, one of which is based on an augmented system approach, and a comparison with publicly available interior-point solvers for semidefinite programming.     

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.     

A regularized strong duality for nonsymmetric semidefinite least squares problem

The nonsymmetric semidefinite least squares problem (NSDLS) is to find a nonsymmetric semidefinite matrix which is closest to a given matrix in Frobenius norm. It is an extension of the semidefinite least squares problem (SDLS) and has important application in the area of robotics and automation. In this note, by developing the minimal representation of the underlying cone with the linear constraints, we obtain a regularized strong duality with low-dimensional projection for NSDLS. Further, we study the generalized differential properties and nonsingularity of the first order optimality system about the dual problem. These theoretical results demonstrate that we can solve NSDLS as good as the current Lagrangian dual approaches to SDLS.     

Some applications of optimization in matrix theory

We apply a recent characterization of optimality for the abstract convex program with a cone constraint to three matrix theory problems: (1) a generalization of Farkas's lemma; (2) paired duality in linear programming over cones; (3) a constrained matrix best approximation problem. In particular, these results are not restricted to polyhedral or closed cones.     

Duality and existence theory for nondifferentiable programming

Necessary and sufficient conditions of optimality are given for a nonlinear nondifferentiable program, where the constraints are defined via closed convex cones and their polars. These results are then used to obtain an existence theorem for the corresponding stationary point problem, under some convexity and regularity conditions on the functions involved, which also guarantee an optimal solution to the programming problem. Furthermore, a dual problem is defined, and a strong duality theorem is obtained under the assumption that the constraint sets of the primal and dual problems are nonempty.     

Approximate Optimality and Approximate Duality for Quasi Approximate Solutions in Robust Convex Semidefinite Programs

In this paper, we study quasi approximate solutions for a convex semidefinite programming problem in the face of data uncertainty. Using the robust optimization approach (worst-case approach), approximate optimality conditions and approximate duality theorems for quasi approximate solutions in robust convex semidefinite programming problems are explored under the robust characteristic cone constraint qualification. Moreover, some examples are given to illustrate the obtained results.     

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.     

Non-differentiable symmetric duality for multiobjective programming with cone constraints

Two pairs of non-differentiable multiobjective symmetric dual problems with cone constraints over arbitrary cones, which are Wolfe type and Mond–Weir type, are considered. On the basis of weak efficiency with respect to a convex cone, we obtain symmetric duality results for the two pairs of problems under cone-invexity and cone-pseudoinvexity assumptions on the involved functions. Our results extend the results in Khurana [S. Khurana, Symmetric duality in multiobjective programming involving generalized cone-invex functions, European Journal of Operational Research 165 (2005) 592–597] to the non-differentiable multiobjective symmetric dual problem.     

Computational Experience with Ill-Posed Problems in Semidefinite Programming

Many theoretical and algorithmic results in semidefinite programming are based on the assumption that Slater's constraint qualification is satisfied for the primal and the associated dual problem. We consider semidefinite problems with zero duality gap for which Slater's condition fails for at least one of the primal and dual problem. We propose a numerically reasonable way of dealing with such semidefinite programs. The new method is based on a standard search direction with damped Newton steps towards primal and dual feasibility.     

Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme

It is co-NP-complete to decide whether a given matrix is copositive or not. In this paper, this decision problem is transformed into a quadratic programming problem, which can be approximated by solving a sequence of linear conic programming problems defined on the dual cone of the cone of nonnegative quadratic functions over the union of a collection of ellipsoids. Using linear matrix inequalities (LMI) representations, each corresponding problem in the sequence can be solved via semidefinite programming. In order to speed up the convergence of the approximation sequence and to relieve the computational effort of solving linear conic programming problems, an adaptive approximation scheme is adopted to refine the union of ellipsoids. The lower and upper bounds of the transformed quadratic programming problem are used to determine the copositivity of the given matrix.     

Strong duality and minimal representations for cone optimization

The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. In addition, preprocessing is an essential step for efficiency in both simplex type and interior-point methods. However, the theory and preprocessing techniques can fail for cone programming over nonpolyhedral cones. We take a fresh look at known and new results for duality, optimality, constraint qualifications, CQ, and strict complementarity, for linear cone optimization problems in finite dimensions. One theme is the notion of minimal representation of the cone and the constraints. This provides a framework for preprocessing cone optimization problems in order to avoid both the theoretical and numerical difficulties that arise due to the (near) loss of the strong CQ, strict feasibility. We include results and examples on the surprising theoretical connection between duality gaps in the original primal-dual pair and lack of strict complementarity in their homogeneous counterpart. Our emphasis is on results that deal with Semidefinite Programming, SDP.     

Solving Hankel matrix approximation problem using semidefinite programming

Positive semidefinite Hankel matrices arise in many important applications. Some of their properties may be lost due to rounding or truncation errors incurred during evaluation. The problem is to find the nearest matrix to a given matrix to retrieve these properties. The problem is converted into a semidefinite programming problem as well as a problem comprising a semidefined program and second-order cone problem. The duality and optimality conditions are obtained and the primal–dual algorithm is outlined. Explicit expressions for a diagonal preconditioned and crossover criteria have been presented. Computational results are presented. A possibility for further improvement is indicated.     

A New Self-Dual Embedding Method for Convex Programming

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.