interior point methods

Implementation of Interior-point Methods for LP based on Krylov Subspace Iterative Solvers with Inner-iteration Preconditioning

  • Yiran Cui
  • Takashi Tsuchiya
  • Ken Hayami
  • Keiichi Morikuni
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We apply novel inner-iteration preconditioned Krylov subspace methods to the interior-point algorithm for linear programming (LP). Inner-iteration preconditioners recently proposed by Morikuni and Hayami enable us to overcome the severe ill-conditioning of linear equations solved in the final phase of interior-point iterations. The employed Krylov subspace methods do not suffer from rank-deficiency and therefore no … Read more

    On geometrical properties of preconditioners in IPMs for classes of block-angular problems

  • Jordi Castro
  • Stefano Nasini
    • Categories Linear Programming Tags , , , ,

    One of the most efficient interior-point methods for some classes of block-angular structured problems solves the normal equations by a combination of Cholesky factorizations and preconditioned conjugate gradient for, respectively, the block and linking constraints. In this work we show that the choice of a good preconditioner depends on geometrical properties of the constraints structure. … Read more

    A Distributed Interior-Point KKT Solver for Multistage Stochastic Optimization

  • Hübner Jens
  • Martin Schmidt
  • Marc C. Steinbach
    • Categories Finance and Economics, Parallel Algorithms, Stochastic Programming Tags , , , ,

    Multistage stochastic optimization leads to NLPs over scenario trees that become extremely large when many time stages or fine discretizations of the probability space are required. Interior-point methods are well suited for these problems if the arising huge, structured KKT systems can be solved efficiently, for instance, with a large scenario tree but a moderate … Read more

    Constrained Optimization with Low-Rank Tensors and Applications to Parametric Problems with PDEs

  • Sebastian Garreis
  • Michael Ulbrich
    • Categories Optimization of Systems modeled by PDEs, Stochastic Programming, Systems governed by Differential Equations Optimization Tags , , , , , , ,

    Low-rank tensor methods provide efficient representations and computations for high-dimensional problems and are able to break the curse of dimensionality when dealing with systems involving multiple parameters. We present algorithms for constrained nonlinear optimization problems that use low-rank tensors and apply them to optimal control of PDEs with uncertain parameters and to parametrized variational inequalities. … Read more

    A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen

  • Reinaldo Morabito
  • Pedro Munari
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , , , , ,

    We address a variant of the vehicle routing problem with time windows (VRPTW) that includes the decision of how many deliverymen should be assigned to each vehicle. In this variant, the service time at each customer depends on the size of the respective demand and on the number of deliverymen assigned to visit this customer. … Read more

    Regularized Interior Proximal Alternating Direction Method for Separable Convex Optimization Problems

  • Felipe Álvarez
  • Julio López
  • Natalia Ruiz
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , ,

    In this article we present a version of the proximal alternating direction method for a convex problem with linear constraints and a separable objective function, in which the standard quadratic regularizing term is replaced with an interior proximal metric for those variables that are required to satisfy some additional convex constraints. Moreover, the proposed method … Read more

    A polynomial primal-dual affine scaling algorithm for symmetric conic optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    The primal-dual Dikin-type affine scaling method was originally proposed for linear optimization and then extended to semidefinite optimization. Here, the method is generalized to symmetric conic optimization using the notion of Euclidean Jordan algebras. The method starts with an interior feasible but not necessarily centered primal-dual solution, and it features both centering and reducing the … Read more

    A priori bounds on the condition numbers in interior-point methods

  • Florian Jarre
    • Categories Linear Programming, Semi-definite Programming Tags , ,

    Interior-point methods are known to be sensitive to ill-conditioning and to scaling of the data. This paper presents new asymptotically sharp bounds on the condition numbers of the linear systems at each iteration of an interior-point method for solving linear or semidefinite programs and discusses a stopping test which leads to a problem-independent “a priori” … Read more

    A Constraint-reduced Algorithm for Semidefinite Optimization Problems using HKM and AHO directions

  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , ,

    We develop a new constraint-reduced infeasible predictor-corrector interior point method for semidefinite programming, and we prove that it has polynomial global convergence and superlinear local convergence. While the new algorithm uses HKM direction in predictor step, it adopts AHO direction in corrector step to obtain faster approach to the central path. In contrast to the … Read more

    A Constraint-Reduced Algorithm for Semidefinite Optimization Problems with Superlinear Convergence

  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , ,

    Constraint reduction is an essential method because the computational cost of the interior point methods can be effectively saved. Park and O’Leary proposed a constraint-reduced predictor-corrector algorithm for semidefinite programming with polynomial global convergence, but they did not show its superlinear convergence. We first develop a constraint-reduced algorithm for semidefinite programming having both polynomial global … Read more