primal-dual interior-point method

Polynomial worst-case iteration complexity of quasi-Newton primal-dual interior point algorithms for linear programming

  • Francisco N. C. Sobral
  • Jacek Gondzio
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    Quasi-Newton methods are well known techniques for large-scale numerical optimization. They use an approximation of the Hessian in optimization problems or the Jacobian in system of nonlinear equations. In the Interior Point context, quasi-Newton algorithms compute low-rank updates of the matrix associated with the Newton systems, instead of computing it from scratch at every iteration. … Read more

    Projected-Search Methods for Bound-Constrained Optimization

  • Michael W Ferry
  • Philip E. Gill
  • Elizabeth Wong
  • Minxin Zhang
    • Categories Bound-constrained Optimization Tags , , , ,

    Projected-search methods for bound-constrained minimization are based on performing a line search along a continuous piecewise-linear path obtained by projecting a search direction onto the feasible region. A potential benefit of a projected-search method is that many changes to the active set can be made at the cost of computing a single search direction. As … Read more

    Stability and accuracy of Inexact Interior Point methods for convex quadratic programming

  • Benedetta Morini
  • Valeria Simoncini
    • Categories Nonlinear Optimization Tags , ,

    We consider primal-dual IP methods where the linear system arising at each iteration is formulated in the reduced (augmented) form and solved approximately. Focusing on the iterates close to a solution, we analyze the accuracy of the so-called inexact step, i.e., the step that solves the unreduced system, when combining the effects of both different … Read more

    Interior-point algorithms for convex optimization based on primal-dual metrics

  • Tor G.J. Myklebust
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    We propose and analyse primal-dual interior-point algorithms for convex optimization problems in conic form. The families of algorithms we analyse are so-called short-step algorithms and they match the current best iteration complexity bounds for primal-dual symmetric interior-point algorithm of Nesterov and Todd, for symmetric cone programming problems with given self-scaled barriers. Our results apply to … Read more

    A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs

  • Dianne P. O'Leary
  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction … Read more

    An interior point method with a primal-dual quadratic barrier penalty function for nonlinear semidefinite programming

  • Atsushi Kato
  • Hiroshi Yabe
  • Hiroshi Yamashita
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper, we consider an interior point method for nonlinear semidefinite programming. Yamashita, Yabe and Harada presented a primal-dual interior point method in which a nondifferentiable merit function was used. By using shifted barrier KKT conditions, we propose a differentiable primal-dual merit function within the framework of the line search strategy, and prove the … Read more

    Using the primal-dual interior point algorithm within the branch-price-and-cut method

  • Jacek Gondzio
  • Pedro Munari
    • Categories Integer Programming Tags , , ,

    Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using … Read more

    Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods

  • Chen Greif
  • Erin Moulding
  • Dominique Orban
    • Categories Convex Optimization, Quadratic Programming Tags , , , , , , ,

    Interior-point methods feature prominently among numerical methods for inequality-constrained optimization problems, and involve the need to solve a sequence of linear systems that typically become increasingly ill-conditioned with the iterations. To solve these systems, whose original form has a nonsymmetric 3×3 block structure, it is common practice to perform block Gaussian elimination and either solve … Read more

    Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization

  • Pierre-Antoine Absil
  • Luke Winternitz
  • AndrĂ© L. Tits
    • Categories Linear Programming Tags , , ,

    In earlier work (Tits et al., SIAM J. Optim., 17(1):119–146, 2006; Winternitz et al., COAP, doi=10.1007/s10589-010-9389-4, 2011), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more constraints … Read more

    Parallel solver for semidefinite programming problem having sparse Schur complement matrix

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
  • Maho Nakata
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , ,

    SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical programming. SDP provides a practical computation framework for many research fields. Some applications, however, require solving large-scale SDPs whose size exceeds the capacity of a single processor in terms of computational time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel version) developed … Read more