Linear, Cone and Semidefinite Programming

On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints

  • Gabriele Eichfelder
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

    The well-known result stating that any non-convex quadratic problem over the nonnegative orthant with some additional linear and binary constraints can be rewritten as linear problem over the cone of completely positive matrices (Burer, 2009) is generalized by replacing the nonnegative orthant with an arbitrary closed convex cone. This set-semidefinite representation result implies new semidefinite … Read more

    On Computation of Performance Bounds of Optimal Index Assignment

  • Hans D Mittelmann
  • Xiaolin Wu
  • J. Wang
  • X. Wang
    • Categories Applications - Science and Engineering, Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in- stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a … Read more

    A Polynomial Arc-Search Interior-Point Algorithm for Linear Programming

  • Yaguang Yang
    • Categories Linear Programming Tags , , ,

    In this paper, ellipse is used to approximate the central path of the linear programming. An interior-point algorithm is devised to search the optimizers along the ellipse. The algorithm is proved to be polynomial with the complexity bound $O(n^{\frac{1}{2}}\log(1/\epsilon))$. Numerical test is conducted for problems in Netlib. For most tested Netlib problems, the result shows … Read more

    A Polynomial Arc-Search Interior-Point Algorithm for Convex Quadratic Programming

  • Yaguang Yang
    • Categories Linear Programming Tags , ,

    Arc-search is developed for linear programming in \cite{yang09, yang10}. The algorithms search for optimizers along an ellipse that are approximations of the central path. In this paper, the arc-search method is applied to primal-dual path-following interior-point method for convex quadratic programming. A simple algorithm with iteration complexity $O(\sqrt{n}\log(1/\epsilon))$ is devised. Several improvements on the simple … Read more

    Infeasible Constraint-Reduced Interior-Point Methods for Linear Optimization

  • Meiyun Y. He
  • André L. Tits
    • Categories Linear Programming

    Constraint-reduction schemes have been proposed for the solution by means of interior-point methods of linear programs with many more inequality constraints than variables in standard dual form. Such schemes have been shown to be provably convergent and highly efficient in practice. A critical requirement of these schemes is the availability of an initial dual-feasible point. … Read more

    First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints

  • Chao Ding
  • Defeng Sun
  • Jane J. Ye
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper we consider a mathematical program with semidefinite cone complementarity constraints (SDCMPCC). Such a problem is a matrix analogue of the mathematical program with (vector) complementarity constraints (MPCC) and includes MPCC as a special case. We derive explicit expressions for the strong-, Mordukhovich- and Clarke- (S-, M- and C-)stationary conditions and give constraint … Read more

    On Duality Theory for Non-Convex Semidefinite Programming

  • Chengjin Li
  • Wenyu Sun
  • Raimundo Sampaio
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    In this paper, with the help of convex-like function, we discuss the duality theory for nonconvex semidefinite programming. Our contributions are: duality theory for the general nonconvex semidefinite programming when Slater’s condition holds; perfect duality for a special case of the nonconvex semidefinite programming for which Slater’s condition fails. We point out that the results … Read more

    A Robust Algorithm for Semidefinite Programming

  • Xuan Vinh Doan
  • Henry Wolkowicz
  • Serge Kruk
    • Categories Optimization Software Benchmark, Semi-definite Programming Tags , ,

    Current successful methods for solving semidefinite programs, SDP, are based on primal-dual interior-point approaches. These usually involve a symmetrization step to allow for application of Newton’s method followed by block elimination to reduce the size of the Newton equation. Both these steps create ill-conditioning in the Newton equation and singularity of the Jacobian of the … Read more

    Simultaneous Column-and-Row Generation for Large-Scale Linear Programs with Column-Dependent-Rows

  • Ş. İlker Birbil
  • Kerem Bülbül
  • Ibrahim Muter
  • Guvenc Sahin
    • Categories Linear Programming

    In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many … Read more