interior point methods

Convex Optimization Methods for Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Ming Yuan
    • Categories Convex Optimization, Nonsmooth Optimization, Statistics Tags , , , , , ,

    In this paper, we study convex optimization methods for computing the trace norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection (FES) method, recently proposed by Yuan et al. [17], conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and … Read more

    A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region

  • Eissa Nematollahi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , ,

    By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ “sharp” turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension … Read more

    Limiting behavior and analyticity of weighted central paths in semidefinite programming

  • Margaréta Halická
  • Mária Trnovská
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    In this paper we analyze the limiting behavior of infeasible weighted central paths in semidefinite programming under the assumption that a strictly complementary solution exists. We show that the paths associated with the “square root” symmetrization of the weighted centrality condition are analytic functions of the barrier parameter $\mu$ even at $\mu=0$ if and only … Read more

    An Information Geometric Approach to Polynomial-time Interior-point Algorithms: Complexity Bound via Curvature Integral

  • Atsumi Ohara
  • Takashi Tsuchiya
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

    In this paper, we study polynomial-time interior-point algorithms in view of information geometry. Information geometry is a differential geometric framework which has been successfully applied to statistics, learning theory, signal processing etc. We consider information geometric structure for conic linear programs introduced by self-concordant barrier functions, and develop a precise iteration-complexity estimate of the polynomial-time … Read more

    Properties of a Cutting Plane Method for Semidefinite Programming

  • John E. Mitchell
  • Kartik Krishnan Sivaramakrishnan
    • Categories Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , , ,

    We analyze the properties of an interior point cutting plane algorithm that is based on a semi-infinite linear formulation of the dual semidefinite program. The cutting plane algorithm approximately solves a linear relaxation of the dual semidefinite program in every iteration and relies on a separation oracle that returns linear cutting planes. We show that … Read more

    An Interior-Point Method for Large Scale Network Utility Maximization

  • Stephen Boyd
  • Daniel O' Neill
  • Nikolaos Trichakis
  • Argyrios Zymnis
    • Categories Convex Optimization, Network Optimization Tags , ,

    We describe a specialized truncated-Newton primal-dual interior-point method that solves large scale network utility maximization problems, with concave utility functions, efficiently and reliably. Our method is not decentralized, but easily scales to problems with a million flows and links. We compare our method to a standard decentralized algorithm based on dual decomposition, and show by … Read more

    Regularization and Preconditioning of KKT Systems Arising in Nonnegative Least-Squares Problems

  • Stefania Bellavia
  • Jacek Gondzio
  • Benedetta Morini
    • Categories Bound-constrained Optimization Tags , , , ,

    A regularized Newton-like method for solving nonnegative least-squares problems is proposed and analysed in this paper. A preconditioner for KKT systems arising in the method is introduced and spectral properties of the preconditioned matrix are analysed. A bound on the condition number of the preconditioned matrix is provided. The bound does not depend on the … Read more

    Exploiting separability in large-scale linear support vector machine training

  • Jacek Gondzio
  • Kristian Woodsend
    • Categories Data-Mining, Quadratic Programming Tags , , ,

    Linear support vector machine training can be represented as a large quadratic program. We present an efficient and numerically stable algorithm for this problem using interior point methods, which requires only O(n) operations per iteration. Through exploiting the separability of the Hessian, we provide a unified approach, from an optimization perspective, to 1-norm classification, 2-norm … Read more

    A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations

  • Dianne P. O'Leary
  • Simon P. Schurr
  • André L. Tits
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this work we develop a primal-dual short-step interior point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the barrier function is either impossible or too expensive. As our main contribution, we show that if approximate gradients and Hessians can be computed, and the relative errors in … Read more

    Convergence Analysis of an Interior-Point Method for Nonconvex Nonlinear Programming

  • Hande Benson
  • Arun Sen
  • David F. Shanno
    • Categories Constrained Nonlinear Optimization Tags , ,

    In this paper, we present global and local convergence results for an interior-point method for nonlinear programming. The algorithm uses an $\ell_1$ penalty approach to relax all constraints, to provide regularization, and to bound the Lagrange multipliers. The penalty problems are solved using a simplified version of Chen and Goldfarb’s strictly feasible interior-point method [6]. … Read more