interior point methods

Enlarging Neighborhoods of Interior-Point Algorithms for Linear Programming via Least Values of Proximity measure Functions

  • Yun-Bin Zhao
    • Categories Linear Programming Tags , , ,

    It is well known that a wide-neighborhood interior-point algorithm for linear programming performs much better in implementation than those small-neighborhood counterparts. In this paper, we provide a unified way to enlarge the neighborhoods of predictor-corrector interior-point algorithms for linear programming. We prove that our methods not only enlarge the neighborhoods but also retain the so-far … Read more

    Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System

  • Alexandre Belloni
  • Robert M. Freund
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    We present a general theory for transforming a homogeneous conic system F: Ax = 0, x \in C, x \ne 0, to an equivalent system via projective transformation induced by the choice of a point in a related dual set. Such a projective transformation serves to pre-condition the conic system into a system that has … Read more

    A NEW BARRIER FOR A CLASS OF SEMIDEFINITE PROBLEMS

  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Semi-definite Programming Tags , , ,

    We introduce a new barrier function to solve a class of Semidefinite Optimization Problems (SOP) with bounded variables. That class is motivated by some (SOP) as the minimization of the sum of the first few eigenvalues of symmetric matrices and graph partitioning problems. We study the primal-dual central path defined by the new barrier and … Read more

    On Mehrotra-Type Predictor-Corrector Algorithms

  • Jiming Peng
  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper we discuss the polynomiality of Mehrotra-type predictor-corrector algorithms. We consider a variant of the original prototype of the algorithm that has been widely used in several IPM based optimization packages, for which no complexity result is known to date. By an example we show that in this variant the usual Mehrotra-type adaptive … Read more

    Local Analysis of the Feasible Primal-Dual Interior-Point Method

  • R. Silva
  • Luis Nunes Vicente
  • J. Soares
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper we analyze the rate of local convergence of the Newton primal-dual interior-point method when the iterates are kept strictly feasible with respect to the inequality constraints. It is shown under the classical conditions that the rate is q-quadratic when the functions associated to the inequality constraints define a locally concave feasible region. … Read more

    Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems

  • Robert M. Freund
  • Fernando Ordóñez
  • Kim-Chuan Toh
    • Categories Semi-definite Programming Tags , ,

    We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the … Read more

    Sensitivity analysis in convex quadratic optimization: simultaneous perturbation of the objective and right-hand-side vectors

  • Alireza Ghaffari Hadigheh
  • Oleksandr Romanko
  • Tamás Terlaky
    • Categories Finance and Economics, Linear Programming, Quadratic Programming Tags , , , , , ,

    In this paper we study the behavior of Convex Quadratic Optimization problems when variation occurs simultaneously in the right-hand side vector of the constraints and in the coefficient vector of the linear term in the objective function. It is proven that the optimal value function is piecewise-quadratic. The concepts of transition point and invariancy interval … Read more

    Some Disadvantages of a Mehrotra-Type Primal-Dual Corrector Interior Point Algorithm for Linear Programming

  • Coralia Cartis
    • Categories Linear Programming Tags , ,

    The Primal-Dual Corrector (PDC) algorithm that we propose computes on each iteration a corrector direction in addition to the direction of the standard primal-dual path-following interior point method (Kojima et al., 1989) for Linear Programming (LP), in an attempt to improve performance. The new iterate is chosen by moving along the sum of these directions, … Read more

    Two-Stage Stochastic Semidefinite Programming and Decomposition Based Interior Point Methods

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Semi-definite Programming, Stochastic Programming Tags , , ,

    We introduce two-stage stochastic semidefinite programs with recourse and present a Benders decomposition based linearly convergent interior point algorithms to solve them. This extends the results of Zhao, who showed that the logarithmic barrier associated with the recourse function of two-stage stochastic linear programs with recourse behaves as a strongly self-concordant barrier on the first … Read more

    On generalized branching methods for mixed integer programming

  • Zhifeng Li
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , ,

    In this paper we present a restructuring of the computations in Lenstra’s methods for solving mixed integer linear programs. We show that the problem of finding a good branching hyperplane can be formulated on an adjoint lattice of the Kernel lattice of the equality constraints without requiring any dimension reduction. As a consequence the short … Read more