interior point methods

On the Relationship between Bilevel Decomposition Algorithms and Direct Interior-Point Methods

  • Victor DeMiguel
  • Francisco Javier Nogales
    • Categories Constrained Nonlinear Optimization, Multidisciplinary Design Optimization Tags , , ,

    Engineers have been using \emph{bilevel decomposition algorithms} to solve certain nonconvex large-scale optimization problems arising in engineering design projects. These algorithms transform the large-scale problem into a bilevel program with one upper-level problem (the master problem) and several lower-level problems (the subproblems). Unfortunately, there is analytical and numerical evidence that some of these commonly used … Read more

    On Implementing Self-Regular Proximity Based Feasible IPMs

  • Jiming Peng
  • Tamás Terlaky
  • Guoqing Zhang
  • Xiaohang Zhu
    • Categories Linear Programming, Optimization Software Benchmark Tags , ,

    Self-regular based interior point methods present a unified novel approach for solving linear optimization and conic optimization problems. So far it was not known if the new Self-Regular IPMs can lead to similar advances in computational practice as shown in the theoretical analysis. In this paper, we present our experiences in developing the software package … Read more

    Solving Nonlinear Portfolio Optimization Problems with the Primal-Dual Interior Point Method

  • Jacek Gondzio
  • Andreas Grothey
    • Categories Finance and Economics, Nonlinear Optimization, Stochastic Programming Tags , , ,

    Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear … Read more

    Fortran subroutines for network flow optimization using an interior point algorithm

  • Joaquim J. Júdice
  • João Patrício
  • Luis F. Portugal
  • Mauricio G.C. Resende
  • Geraldo Veiga
    • Categories Network Optimization, Optimization Software and Modeling Systems Tags , ,

    We describe FORTRAN subroutines for network flow optimization using an interior point network flow algorithm. We provide FORTRAN and C language drivers, as well as C language functions that, together with the subroutines, make up PDNET (Portugal, Resende, Veiga, and Júdice, 2000). The algorithm is described in detail and its implementation is outlined. Usage of … Read more

    An Efficient Interior-Point Method for Convex Multicriteria Optimization Problems

  • Jörg Fliege
    • Categories Convex Optimization, Multi-Criteria Optimization Tags , , , ,

    In multicriteria optimization, several objective functions, conflicting with each other, have to be minimized simultaneously. We propose a new efficient method for approximating the solution set of a multiobjective programming problem, where the objective functions involved are arbitary convex functions and the set of feasible points is convex. The method is based on generating warm-start … Read more

    Interior Point and Semidefinite Approaches in Combinatorial Optimization

  • Kartik Krishnan
  • Tamás Terlaky
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    Interior-point methods (IPMs), originally conceived in the context of linear programming have found a variety of applications in integer programming, and combinatorial optimization. This survey presents an up to date account of IPMs in solving NP-hard combinatorial optimization problems to optimality, and also in developing approximation algorithms for some of them. The surveyed approaches include … Read more

    Convergence of infeasible-interior-point methods for self-scaled conic programming

  • Bharath Kumar Rangarajan
  • Michael J. Todd
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We present results on global and polynomial-time convergence of infeasible-interior-point methods for self-scaled conic programming, which includes linear and semidefinite programming. First, we establish global convergence for an algorithm using a wide neighborhood. Next, we prove polynomial complexity for the algorithm with a slightly narrower neighborhood. Both neighborhoods are related to the wide (minus infinity) … Read more

    Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers

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

    In this paper, we consider a modified version of a well-known long-step primal-dual infeasible IP algorithm for solving the linear program $\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$, where the search directions are computed by means of an iterative linear solver applied to a preconditioned normal system of equations. … Read more

    A limited memory algorithm for inequality constrained minimization

  • Paul Armand
  • Philippe Segalat
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    A method for solving inequality constrained minimization problems is described. The algorithm is based on a primal-dual interior point approach, with a line search globalization strategy. A quasi-Newton technique (BFGS) with limited memory storage is used to approximate the second derivatives of the functions. The method is especially intended for solving problems with a large … Read more

    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