self-concordant barriers

Domain-Driven Solver (DDS): a MATLAB-based Software Package for Convex Optimization Problems in Domain-Driven Form

  • Mehdi Karimi
  • Levent Tunçel
    • Categories Convex and Nonsmooth Optimization, Optimization Software and Modeling Systems Tags , , , ,

    Domain-Driven Solver (DDS) is a MATLAB-based software package for convex optimization problems in Domain-Driven form [11]. The current version of DDS accepts every combination of the following function/set constraints: (1) symmetric cones (LP, SOCP, and SDP); (2) quadratic constraints; (3) direct sums of an arbitrary collection of 2-dimensional convex sets defined as the epigraphs of … Read more

    Primal-Dual Interior-Point Methods for Domain-Driven Formulations: Algorithms

  • Mehdi Karimi
  • Levent Tunçel
    • Categories Convex Optimization Tags , , ,

    We study infeasible-start primal-dual interior-point methods for convex optimization problems given in a typically natural form we denote as Domain-Driven formulation. Our algorithms extend many advantages of primal-dual interior-point techniques available for conic formulations, such as the current best complexity bounds, and more robust certificates of approximate optimality, unboundedness, and infeasibility, to Domain-Driven formulations. The … Read more

    On self-concordant barriers for generalized power cones

  • Scott Roy
  • Lin Xiao
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In the study of interior-point methods for nonsymmetric conic optimization and their applications, Nesterov introduced the power cone, together with a 4-self-concordant barrier for it. In his PhD thesis, Chares found an improved 3-self-concordant barrier for the power cone. In addition, he introduced the generalized power cone, and conjectured a nearly optimal self-concordant barrier for … Read more

    Interior-point algorithms for convex optimization based on primal-dual metrics

  • Tor G.J. Myklebust
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    We propose and analyse primal-dual interior-point algorithms for convex optimization problems in conic form. The families of algorithms we analyse are so-called short-step algorithms and they match the current best iteration complexity bounds for primal-dual symmetric interior-point algorithm of Nesterov and Todd, for symmetric cone programming problems with given self-scaled barriers. Our results apply to … Read more

    Einstein-Hessian barriers on convex cones

  • Roland Hildebrand
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    On the interior of a regular convex cone $K \subset \mathbb R^n$ there exist two canonical Hessian metrics, the one generated by the logarithm of the characteristic function, and the Cheng-Yau metric. The former is associated with a self-concordant logarithmically homogeneous barrier on $K$ with parameter of order $O(n)$, the universal barrier. This barrier is … Read more

    Local superlinear convergence of polynomial-time interior-point methods for hyperbolic cone optimization problems

  • Yurii Nesterov
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper, we establish the local superlinear convergence property of some polynomial-time interior-point methods for an important family of conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier function, which must have {\em negative curvature}. We propose a new path-following predictor-corrector scheme, which work only … 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

    Self-Concordant Barriers for Convex Approximations of Structured Convex Sets

  • Arkadi Nemirovski
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We show how to approximate the feasible region of structured convex optimization problems by a family of convex sets with explicitly given and efficient (if the accuracy of the approximation is moderate) self-concordant barriers. This approach extends the reach of the modern theory of interior-point methods, and lays the foundation for new ways to treat … Read more

    Nonsymmetric potential-reduction methods for general cones

  • Yurii Nesterov
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper we propose two new nonsymmetric primal-dual potential-reduction methods for conic problems. Both methods are based on {\em primal-dual lifting}. This procedure allows to construct a strictly feasible primal-dual pair linked by an exact {\em scaling} relation even if the cones are not symmetric. It is important that all necessary elements of our … Read more

    Constructing self-concordant barriers for convex cones

  • Yurii Nesterov
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we develop a technique for constructing self-concordant barriers for convex cones. We start from a simple proof for a variant of standard result on transformation of a $\nu$-self-concordant barrier for a set into a self-concordant barrier for its conic hull with parameter $(3.08 \sqrt{\nu} + 3.57)^2$. Further, we develop a convenient composition … Read more