Linear, Cone and Semidefinite Programming

A minimal face constant rank constraint qualification for reducible conic programming

  • Roberto Andreani
  • Gabriel Haeser
  • leomakoto
  • Héctor Ramírez
    • Categories Cone Programming, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , ,

    \(\) In a previous paper [R. Andreani, G. Haeser, L. M. Mito, H. Ramírez, T. P. Silveira. First- and second-order optimality conditions for second-order cone and semidefinite programming under a constant rank condition. Mathematical Programming, 2023. DOI: 10.1007/s10107-023-01942-8] we introduced a constant rank constraint qualification for nonlinear semidefinite and second-order cone programming by considering all … Read more

    Hidden convexity, optimization, and algorithms on rotation matrices

  • Kevin Shu
  • Alex L. Wang
  • Akshay Ramachandran
    • Categories Constrained Nonlinear Optimization, Other Topics, Semi-definite Programming Tags , ,

    \(\) This paper studies hidden convexity properties associated with constrained optimization problems over the set of rotation matrices \(\text{SO}(n)\). Such problems are nonconvex due to the constraint\(X\in\text{SO}(n)\). Nonetheless, we show that certain linear images of \(\text{SO}(n)\) are convex, opening up the possibility for convex optimization algorithms with provable guarantees for these problems. Our main technical … Read more

    Jordan automorphisms and derivatives of symmetric cones

  • Michael Orlitzky
    • Categories Cone Programming Tags , , , ,

    Hyperbolicity cones, and in particular symmetric cones, are of great interest in optimization. Renegar showed that every hyperbolicity cone has a family of derivative cones that approximate it. Ito and Lourenço found the automorphisms of those derivatives when the original cone is generated by rank-one elements, as symmetric cones happen to be. We show that … Read more

    Application of a Gas Market Model with Linear Programming. The Influence of the Dollar Exchange Rate on the Wholesale Price of Natural Gas in Northwest Europe until 2040

  • Maik Günther
    • Categories Finance and Economics, Linear Programming, Optimization of Simulated Systems Tags , , , , , , , , ,

    The price of natural gas at wholesale markets in Northwest Europe is influenced by numerous parameters. The USD to EUR exchange rate is one of these parameters. Using the LP-based gas market model WEGA, this paper will examine the impact of USD exchange rates on wholesale natural gas prices in Northwest Europe from 2025 to … Read more

    Closing Duality Gaps of SDPs through Perturbation

  • Takashi Tsuchiya
  • Bruno F. Lourenço
  • Masakazu Muramatsu
  • Takayuki Okuno
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    \(\) Let \(({\bf P},{\bf D})\) be a primal-dual pair of SDPs with a nonzero finite duality gap. Under such circumstances, \({\bf P}\) and \({\bf D}\) are weakly feasible and if we perturb the problem data to recover strong feasibility, the (common) optimal value function \(v\) as a function of the perturbation is not well-defined at … Read more

    Polyhedral Properties of RLT Relaxations of Nonconvex Quadratic Programs and Their Implications on Exact Relaxations

  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories Global Optimization, Linear Programming, Quadratic Programming Tags , , ,

    We study linear programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. … Read more

    Solving low-rank semidefinite programs via manifold optimization

  • Jie Wang
    • Categories Constrained Nonlinear Optimization, Optimization Software Benchmark, Semi-definite Programming Tags , , , , ,

    We propose a manifold optimization approach to solve linear semidefinite programs (SDP) with low-rank solutions. This approach incorporates the augmented Lagrangian method and the Burer-Monteiro factorization, and features the adaptive strategies for updating the factorization size and the penalty parameter. We prove that the present algorithm can solve SDPs to global optimality, despite of the … Read more

    Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Semi-definite Programming Tags , , , ,

    \(\) We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator \( \text{LS}_+\), with a particular focus on a search for relatively small graphs with high \( \text{LS}_+\)-rank (the least number of iterations of the \( \text{LS}_+\) operator on the fractional stable set polytope to compute … Read more

    Equivalent Sufficient Conditions for Global Optimality of Quadratically Constrained Quadratic Program

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    \(\) We study the equivalence of several well-known sufficient optimality conditions for a general quadratically constrained quadratic program (QCQP). The conditions are classified in two categories. The first one is for determining an optimal solution and the second one is for finding an optimal value. The first category of conditions includes the existence of a … Read more

    Occupation measure relaxations in variational problems: the role of convexity

  • Didier Henrion
  • Milan Korda
  • Martin Kružík
  • Rodolfo Rios-Zertuche
    • Categories Linear, Cone and Semidefinite Programming Tags

    This work addresses the occupation measure relaxation of calculus of variations problems, which is an infinite-dimensional linear programming reformulation amenable to numerical approximation by a hierarchy of semidefinite optimization problems. We address the problem of equivalence of this relaxation to the original problem. Our main result provides sufficient conditions for this equivalence. These conditions, revolving … Read more