interior point method

Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems with application to linear matrix inequalities

  • Chee-Khian Sim
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    In the literature, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual and the NT direction, to solve semi-definite programs (SDPs) can be shown by (i) assuming that the given SDP is nondegenerate and modifying these algorithms [10], or (ii) considering special classes of SDPs, such … Read more

    A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems

  • Qi Wang
  • Frank E. Curtis
  • Daniel P. Robinson
  • Vyacheslav Kungurtsev
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization in Data Science Tags , ,

    A stochastic-gradient-based interior-point algorithm for minimizing a continuously differentiable objective function (that may be nonconvex) subject to bound constraints is presented, analyzed, and demonstrated through experimental results. The algorithm is unique from other interior-point methods for solving smooth (nonconvex) optimization problems since the search directions are computed using stochastic gradient estimates. It is also unique … Read more

    A Sparse Interior Point Method for Linear Programs arising in Discrete Optimal Transport

  • Filippo Zanetti
  • Jacek Gondzio
    • Categories Convex Optimization, Linear Programming, Transportation Tags , , , ,

    Discrete Optimal Transport problems give rise to very large linear programs (LP) with a particular structure of the constraint matrix. In this paper we present an interior point method (IPM) specialized for the LP originating from the Kantorovich Optimal Transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we … Read more

    Condensed interior-point methods: porting reduced-space approaches on GPU hardware

  • François Pacaud
  • Sungho Shin
  • Michel Schanen
  • Daniel A. Maldonado
  • Mihai Anitescu
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    The interior-point method (IPM) has become the workhorse method for nonlinear programming. The performance of IPM is directly related to the linear solver employed to factorize the Karush–Kuhn–Tucker (KKT) system at each iteration of the algorithm. When solving large-scale nonlinear problems, state-of-the art IPM solvers rely on efficient sparse linear solvers to solve the KKT … Read more

    A Preconditioned Iterative Interior Point Approach to the Conic Bundle Subproblem

  • Christoph Helmberg
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The conic bundle implementation of the spectral bundle method for large scale semidefinite programming solves in each iteration a semidefinite quadratic subproblem by an interior point approach. For larger cutting model sizes the limiting operation is collecting and factorizing a Schur complement of the primal-dual KKT system. We explore possibilities to improve on this by … Read more