interior point methods

Interior point methods for sufficient LCP in a wide neighborhood of the central path with optimal iteration complexity

  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Three interior point methods are proposed for sufficient horizontal linear complementarity problems (HLCP): a large update path following algorithm, a first order corrector-predictor method, and a second order corrector-predictor method. All algorithms produce sequences of iterates in the wide neighborhood of the central path introduced by Ai and Zhang. The algorithms do not depend on … Read more

    A new warmstarting strategy for the primal-dual column generation method

  • Jacek Gondzio
  • Pablo Gonzalez-Brevis
    • Categories Cutting Plane Approaches, Linear Programming Tags , , , ,

    This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … 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

    Weighted complementarity problems – a new paradigm for computing equilibria

  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper introduces the notion of a weighted Complementarity Problem (wCP), which consists in finding a pair of vectors $(x,s)$ belonging to the intersection of a manifold with a cone, such that their product in a certain algebra, $x\circ s$, equals a given weight vector $w$. When $w$ is the zero vector, then wCP reduces … Read more

    Interior-Point Methods for Nonconvex Nonlinear Programming: Primal-Dual Methods and Cubic Regularization

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

    In this paper, we present a primal-dual interior-point method for solving nonlinear programming problems. It employs a Levenberg-Marquardt (LM) perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the LM perturbation is equivalent to replacing the Newton step by a … Read more

    Solution of monotone complementarity and general convex programming problems using modified potential reduction interior point method

  • Kuo-Ling Huang
  • Sanjay Mehrotra
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , ,

    We present a homogeneous algorithm equipped with a modified potential function for the monotone complementarity problem. We show that this potential function is reduced by at least a constant amount if a scaled Lipschitz condition is satis ed. A practical algorithm based on this potential function is implemented in a software package named iOptimize. The implementation … Read more

    Interior-Point Methods for Nonconvex Nonlinear Programming: Cubic Regularization

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

    In this paper, we present a barrier method for solving nonlinear programming problems. It employs a Levenberg-Marquardt perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the Levenberg-Marquardt perturbation is equivalent to replacing the Newton step by a cubic regularization … Read more

    Warmstarting the Homogeneous and Self-Dual Interior Point Method for Linear and Conic Quadratic Problems

  • Erling D. Andersen
  • Yinyu Ye
  • Anders Skajaa
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Second-Order Cone Programming Tags , , ,

    We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when comparing to … Read more

    Interior Point Methods for Optimal Experimental Designs

  • Zhaosong Lu
  • Ting Kei Pong
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming, Statistics Tags , , , , ,

    In this paper, we propose a primal IP method for solving the optimal experimental design problem with a large class of smooth convex optimality criteria, including A-, D- and p th mean criterion, and establish its global convergence. We also show that the Newton direction can be computed efficiently when the size of the moment … Read more

    Curvature Integrals and Iteration Complexities in SDP and Symmetric Cone Programs

  • Satoshi Kakihara
  • Atsumi Ohara
  • Takashi Tsuchiya
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper, we study iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithms in SDP and symmetric cone programs by way of curvature integrals. The curvature integral is defined along the central path, reflecting the geometric structure of the central path. The idea to exploit the curvature of the central path for the analysis of iteration … Read more