hidden convexity

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 contributions … Read more

    Hidden convexity in a class of optimization problems with bilinear terms

  • Bram L. Gorissen
  • Meike Reusken
  • Dick den Hertog
    • Categories Nonlinear Optimization, Robust Optimization Tags , , ,

    In this paper we identify a new class of nonconvex optimization problems that can be equivalently reformulated to convex ones. These nonconvex problems can be characterized by convex functions with bilinear arguments. We describe several examples of important applications that have this structure. A reformulation technique is presented which converts the problems in this class … Read more

    A Revisit to Quadratic Programming with One Inequality Quadratic Constraint via Matrix Pencil

  • Lin Gang-Xuan
  • Sheu Ruey-Lin
  • Hsia Yong
    • Categories Global Optimization Theory, Quadratic Programming Tags , , , , ,

    The quadratic programming over one inequality quadratic constraint (QP1QC) is a very special case of quadratically constrained quadratic programming (QCQP) and attracted much attention since early 1990’s. It is now understood that, under the primal Slater condition, (QP1QC) has a tight SDP relaxation (PSDP). The optimal solution to (QP1QC), if exists, can be obtained by … Read more

    Hidden convexity in partially separable optimization

  • Aharon Ben-Tal
  • Dick den Hertog
  • Monique Laurent
    • Categories Constrained Nonlinear Optimization, Quadratic Programming, Robust Optimization Tags , ,

    The paper identifies classes of nonconvex optimization problems whose convex relaxations have optimal solutions which at the same time are global optimal solutions of the original nonconvex problems. Such a hidden convexity property was so far limited to quadratically constrained quadratic problems with one or two constraints. We extend it here to problems with some … Read more

    Hidden convexity in partially separable optimization

  • Aharon Ben-Tal
    • Categories Constrained Nonlinear Optimization, Quadratic Programming, Robust Optimization Tags , ,

    The paper identifies classes of nonconvex optimization problems whose convex relaxations have optimal solutions which at the same time are global optimal solutions of the original nonconvex problems. Such a hidden convexity property was so far limited to quadratically constrained quadratic problems with one or two constraints. We extend it here to problems with some … Read more

    Immunizing conic quadratic optimization problems against implementation errors

  • Aharon Ben-Tal
  • Dick den Hertog
    • Categories Quadratic Programming, Robust Optimization Tags , , , , ,

    We show that the robust counterpart of a convex quadratic constraint with ellipsoidal implementation error is equivalent to a system of conic quadratic constraints. To prove this result we first derive a sharper result for the S-lemma in case the two matrices involved can be simultaneously diagonalized. This extension of the S-lemma may also be … Read more