Linear, Cone and Semidefinite Programming

Trust-Region Problems with Linear Inequality Constraints: Exact SDP Relaxation, Global Optimality and Robust Optimization

  • V. Jeyakumar
  • Guoyin Li
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having … Read more

    A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

  • Volker Kaibel
  • Stefan Weltge
    • Categories Linear Programming, Polyhedra Tags , , , ,

    We establish that the extension complexity of the nXn correlation polytope is at least 1.5^n by a short proof that is self-contained except for using the fact that every face of a polyhedron is the intersection of all facets it is contained in. The main innovative aspect of the proof is a simple combinatorial argument … Read more

    Large-scale optimization with the primal-dual column generation method

  • Jacek Gondzio
  • Pedro Munari
  • Pablo Gonzalez-Brevis
    • Categories Convex Optimization, Linear Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation. A reduction in the number of calls … Read more

    A Convex Optimization Approach for Computing Correlated Choice Probabilities with Many Alternatives

  • Selin Damla Ahipasaoglu
  • Karthik Natarajan
  • Xiaobo Li
    • Categories Applications - OR and Management Sciences, Robust Optimization, Semi-definite Programming Tags , ,

    A popular discrete choice model that incorporates correlation information is the Multinomial Probit (MNP) model where the random utilities of the alternatives are chosen from a multivariate normal distribution. Computing the choice probabilities is challenging in the MNP model when the number of alternatives is large and simulation is used to approximate the choice probabilities. … Read more

    Stability of Polynomial Differential Equations: Complexity and Converse Lyapunov Questions

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , , , ,

    We consider polynomial differential equations and make a number of contributions to the questions of (i) complexity of deciding stability, (ii) existence of polynomial Lyapunov functions, and (iii) existence of sum of squares (sos) Lyapunov functions. (i) We show that deciding local or global asymptotic stability of cubic vector fields is strongly NP-hard. Simple variations … Read more

    Steepest Edge as Applied to the Standard Simplex Method

  • Gavriel Yarmish
    • Categories Linear Programming Tags , , , , , , ,

    In this paper we discuss results and advantages of using steepest edge column choice rules and their derivatives. We show empirically, when we utilize the steepest edge column choice rule for the tableau method, that the density crossover point at which the tableau method is more efficient than the revised method drops to 5%. This … Read more

    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

    A Semidefinite Hierarchy for Containment of Spectrahedra

  • Kai Kellner
  • Thorsten Theobald
  • Christian Trabandt
    • Categories Semi-definite Programming Tags , , , , ,

    A spectrahedron is the positivity region of a linear matrix pencil, thus defining the feasible set of a semidefinite program. We propose and study a hierarchy of sufficient semidefinite conditions to certify the containment of a spectrahedron in another one. This approach comes from applying a moment relaxation to a suitable polynomial optimization formulation. The … Read more

    Approximate cone factorizations and lifts of polytopes

  • João Gouveia
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave … Read more

    A new semidenite programming relaxation for the quadratic assignment problem and its computational perspectives

  • Etienne de Klerk
  • Renata Sotirov
  • Uwe Truetsch
    • Categories Linear, Cone and Semidefinite Programming Tags ,

    Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB test set has come from mixed integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidenite programming bounds for QAP have also been studied in some detail, but their computational impact has been limited so far, mostly due to the … Read more