second-order cone programming

A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs

  • Dianne P. O'Leary
  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction … Read more

    Full stability of locally optimal solutions in second-order cone programming

  • Boris S. Mordukhovich
  • Jiri V. Outrata
  • Ebrahim Sarabi
    • Categories Nonsmooth Optimization Tags , , , , , ,

    The paper presents complete characterizations of Lipschitzian full stability of locally optimal solutions to problems of second-order cone programming (SOCP) expressed entirely in terms of their initial data. These characterizations are obtained via appropriate versions of the quadratic growth and strong second-order sucient conditions under the corresponding constraint quali cations. We also establish close relationships between … Read more

    Mixed Integer Second-Order Cone Programming Formulations for Variable Selection

  • Ryuhei Miyashiro
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming, Statistics Tags , , , , ,

    This paper concerns the method of selecting the best subset of explanatory variables in a multiple linear regression model. To evaluate a subset regression model, some goodness-of-fit measures, e.g., adjusted R^2, AIC and BIC, are generally employed. Although variable selection is usually handled via a stepwise regression method, the method does not always provide the … Read more

    Faster, but Weaker, Relaxations for Quadratically Constrained Quadratic Programs

  • Samuel Burer
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Convex Optimization, Global Optimization, Quadratic Programming Tags , , ,

    We introduce a new relaxation framework for nonconvex quadratically constrained quadratic programs (QCQPs). In contrast to existing relaxations based on semidefinite programming (SDP), our relaxations incorporate features of both SDP and second order cone programming (SOCP) and, as a result, solve more quickly than SDP. A downside is that the calculated bounds are weaker than … Read more

    The Trust Region Subproblem with Non-Intersecting Linear Constraints

  • Samuel Burer
  • Boshi Yang
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Second-Order Cone Programming Tags , , ,

    This paper studies an extended trust region subproblem (eTRS)in which the trust region intersects the unit ball with m linear inequality constraints. When m=0, m=1, or m=2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial … Read more

    VSDP: A Matlab toolbox for verified semidefinite-quadratic-linear programming

  • Viktor Härter
  • Christian Jansson
  • Marko Lange
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , ,

    VSDP is a software package that is designed for the computation of verified results in conic programming. The current version of VSDP supports the constraint cone consisting of the product of semidefinite cones, second-order cones and the nonnegative orthant. It provides functions for computing rigorous error bounds of the true optimal value, verified enclosures of … Read more

    Second-Order-Cone Constraints for Extended Trust-Region Subproblems

  • Kurt M. Anstreicher
  • Samuel Burer
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The classical trust-region subproblem (TRS) minimizes a nonconvex quadratic objective over the unit ball. In this paper, we consider extensions of TRS having extra constraints. When two parallel cuts are added to TRS, we show that the resulting nonconvex problem has an exact representation as a semidefinite program with additional linear and second-order-cone constraints. For … Read more

    The state-of-the-art in conic optimization software

  • Hans D Mittelmann
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , ,

    This work gives an overview over the major codes available for the solution of linear semidefinite (SDP) and second-order cone (SOCP) programs. Some developments since the 7th DIMACS Challenge [9, 17] are pointed out as well as some currently under way. Instead of presenting per- formance tables, reference is made to the ongoing benchmark [19] … Read more

    Symmetry-exploiting cuts for a class of mixed-0/1 second order cone programs

  • Sarah Drewes
  • Sebastian Pokutta
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    We will analyze mixed 0/1 second order cone programs where the fractional and binary variables are solely coupled via the conic constraints. For this special type of mixed-integer second order cone programs we devise a cutting-plane framework based on the generalized Benders cut and an implicit Sherali-Adams reformulation. We show that the resulting cuts are … Read more

    Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs

  • Miguel F. Anjos
  • Bissan Ghaddar
  • Juan C. Vera
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    Several types of relaxations for binary quadratic polynomial programs can be obtained using linear, second-order cone, or semidefinite techniques. In this paper, we propose a general framework to construct conic relaxations for binary quadratic polynomial programs based on polynomial programming. Using our framework, we re-derive previous relaxation schemes and provide new ones. In particular, we … Read more