conic optimization

Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper, we consider block-decomposition first-order methods for solving large-scale conic semidefinite programming problems. Several ingredients are introduced to speed-up the method in its pure form such as: an aggressive choice of stepsize for performing the extragradient step; use of scaled inner products in the primal and dual spaces; dynamic update of the scaled … Read more

    Polynomial Approximations for Continuous Linear Programs

  • Dimitra Bampou
  • Daniel Kuhn
    • Categories Infinite Dimensional Optimization, Semi-definite Programming Tags , , , ,

    Continuous linear programs have attracted considerable interest due to their potential for modelling manufacturing, scheduling and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude time discretization remains the method of choice for solving general (non-separated) problem instances. In this paper we propose a more generic approximation scheme for … Read more

    Epigraphical cones II

  • Alberto Seeger
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    This is the second part of a work devoted to the theory of epigraphical cones and their applications. A convex cone $K$ in the Euclidean space $\mathbb{R}^{n+1}$ is an epigraphical cone if it can be represented as epigraph of a nonnegative sublinear function $f: \mathbb{R}^n\to \mathbb{R}$. We explore the link between the geometric properties of … Read more

    Costs and benefits of robust optimization

  • Ralf Werner
    • Categories Robust Optimization Tags , ,

    In this exposition the robust counterpart approach by Ben-Tal, El Ghaoui and Nemirovski is investigated with respect to its costs and benefits, with the focus on the costs of robustification. Although robust optimization has gained more and more interest among both academics and practitioners and although this certainly represents a well-established theory, it is to … Read more

    An Introduction to a Class of Matrix Cone Programming

  • Chao Ding
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    In this paper, we define a class of linear conic programming (which we call matrix cone programming or MCP) involving the epigraphs of five commonly used matrix norms and the well studied symmetric cone. MCP has recently found many important applications, for example, in nuclear norm relaxations of affine rank minimization problems. In order to … Read more

    Central Swaths (A Generalization of the Central Path)

  • James Renegar
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    We develop a natural generalization to the notion of the central path — a notion that lies at the heart of interior-point methods for convex optimization. The generalization is accomplished via the “derivative cones” of a “hyperbolicity cone,” the derivatives being direct and mathematically-appealing relaxations of the underlying (hyperbolic) conic constraint, be it the non-negative … Read more

    Truss topology design with integer variables made easy

  • Michal Kočvara
    • Categories (Mixed) Integer Nonlinear Programming, Mechanical Engineering, Semi-definite Programming Tags , ,

    We propose a new look at the problem of truss topology optimization with integer or binary variables. We show that the problem can be equivalently formulated as an integer \emph{linear} semidefinite optimization problem. This makes its numerical solution much easier, compared to existing approaches. We demonstrate that one can use an off-the-shelf solver with default … Read more

    Facial reduction algorithms for conic optimization problems

  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Convex Optimization, Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags ,

    To obtain a primal-dual pair of conic programming problems having zero duality gap, two methods have been proposed: the facial reduction algorithm due to Borwein and Wolkowicz [1,2] and the conic expansion method due to Luo, Sturm, and Zhang [5]. We establish a clear relationship between them. Our results show that although the two methods … Read more

    Primal-dual interior-point methods with asymmetric barrier

  • Yurii Nesterov
    • Categories Applications - Science and Engineering Tags , ,

    In this paper we develop several polynomial-time interior-point methods (IPM) for solving nonlinear primal-dual conic optimization problem. We assume that the barriers for the primal and the dual cone are not conjugate. This broken symmetry does not allow to apply the standard primal-dual IPM. However, we show that in this situation it is also possible … Read more

    Lifting for Conic Mixed-Integer Programming

  • Alper Atamturk
  • Vishnu Narayanan
    • Categories (Mixed) Integer Nonlinear Programming, Integer Programming Tags , ,

    Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory … Read more