interior point methods

Interior-Point Algorithms, Penalty Methods and Equilibrium Problems

  • Hande Benson
  • Arun Sen
  • David F. Shanno
  • Robert J. Vanderbei
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Game Theory Tags , , , ,

    In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPEC’s)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties, present an example … Read more

    The Bundle Method in Combinatorial Optimization

  • Ilse Fischer
  • Franz Rendl
  • Renata Sotirov
  • Gerald Gruber
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Nonsmooth Optimization Tags , ,

    We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a … Read more

    A Comparative Study of New Barrier Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization

  • Y.Q. Bai
  • Cornelis Roos
  • M. Elghami
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    Recently, so-called self-regular barrier functions for primal-dual interior-point methods (IPMs) for linear optimization were introduced. Each such barrier function is determined by its (univariate) self-regular kernel function. We introduce a new class of kernel functions. The class is defined by some simple conditions on the kernel function and its derivatives. These properties enable us to … Read more

    Bounds for the Quadratic Assignment Problem Using the Bundle Method

  • Franz Rendl
  • Renata Sotirov
    • Categories Combinatorial Optimization Tags , , ,

    Semidefinite Programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the Quadratic Assignment Problem suggests SDP as a way to derive tractable relaxation. We recall some SDP relaxations of QAP and solve them approximately using the Bundle Method. The computational results demonstrate the efficiency … Read more

    ON THE LIMITING PROPERTIES OF THE AFFINE-SCALING DIRECTIONS

  • Clóvis Caesar Gonzaga
  • Hugo Lara
  • Levent Tunçel
    • Categories Linear Programming Tags , , ,

    We study the limiting properties of the affine-scaling directions for linear programming problems. The worst-case angle between the affine-scaling directions and the objective function vector provides an interesting measure that has been very helpful in convergence analyses and in understanding the behaviour of various interior-point algorithms. We establish new relations between this measure and some … Read more

    An Interior Point Method for Mathematical Programs with Complementarity Constraints (MPCCs)

  • Lorenz T. Biegler
  • Arvind U. Raghunathan
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , ,

    Interior point methods for nonlinear programs (NLPs) are adapted for solution of mathematical programs with complementarity constraints (MPCCs). The constraints of the MPCC are suitably relaxed so as to guarantee a strictly feasible interior for the inequality constraints. The standard primal-dual algorithm has been adapted with a modified step calculation. The algorithm is shown to … Read more

    Calculation of universal barrier functions for cones generated by Chebyshev systems over finite sets

  • Leonid Faybusovich
  • Michael Gekhtman
    • Categories Linear, Cone and Semidefinite Programming, Semi-infinite Programming Tags , ,

    We explicitly calculate universal barrier functions for cones generated by (weakly) Chebyshev systems over finite sets. We show that universal barrier functions corresponding to Chebyshev systems on intervals are obtained as limits of universal barrier functions of their discretizations. The results are heavily rely upon classical work of M. Krein, A. Nudelman and I.J. Schoenberg … Read more

    A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function

  • Jiming Peng
  • Tamás Terlaky
  • Yun-Bin Zhao
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    It is well known that the so-called first-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. However, the best known iteration complexity of this type of methods is $O\br{n \log\frac{(x^0)^Ts^0}{\varepsilon}}$. It is of interests to investigate whether the complexity … Read more

    Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank

  • Leonid Faybusovich
  • Takashi Tsuchiya
    • Categories Control Applications, Linear, Cone and Semidefinite Programming Tags , , , ,

    We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for “infinite-dimensional second-order cone programs.” We consider as an example a … Read more

    Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
  • Jerome W. O'Neal
    • Categories Linear Programming, Network Optimization Tags , , , , , , ,

    Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more