interior point methods

A multi-step interior point warm-start approach for large-scale stochastic linear programming

  • Marco Colombo
  • Andreas Grothey
    • Categories Stochastic Programming Tags , ,

    Interior point methods (IPM) have been recognised as an efficient approach for the solution of large scale stochastic programming problems due to their ability of exploiting the block-angular structure of the augmented system particular to this problem class. Stochastic programming problems, however, have exploitable structure beyond the simple matrix shape: namely the scenarios are typically … Read more

    Matrix-Free Interior Point Method

  • Jacek Gondzio
    • Categories Linear Programming, Quadratic Programming Tags , , , , ,

    In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods … Read more

    An Interior Proximal Method in Vector Optimization

  • Paulo Roberto Oliveira
  • Kely Diana Villacorta
    • Categories Multi-Criteria Optimization Tags , ,

    This paper studies the vector optimization problem of finding weakly ef- ficient points for maps from Rn to Rm, with respect to the partial order induced by a closed, convex, and pointed cone C ⊂ Rm, with nonempty inte- rior. We develop for this problem an extension of the proximal point method for scalar-valued convex … Read more

    Covariance regularization in inverse space

  • Takashi Tsuchiya
  • Genta Ueno
    • Categories Data-Mining, Semi-definite Programming Tags , ,

    This paper proposes to apply Gaussian graphical models to estimate the large-scale normal distribution in the context of data assimilation from a relatively small number of data from the satellite. Data assimilation is a field which fits simulation models to observation data developed mainly in meteorology and oceanography. The optimization problem tends to be huge … Read more

    Numerical block diagonalization of matrix hBcalgebras with application to semidefinite programming

  • Etienne de Klerk
  • Cristian Dobre
  • Dmitrii V. Pasechnik
    • Categories Semi-definite Programming Tags , , ,

    Semidefinite programming (SDP) is one of the most active areas in mathematical programming, due to varied applications and the availability of interior point algorithms. In this paper we propose a new pre-processing technique for SDP instances that exhibit algebraic symmetry. We present computational results to show that the solution times of certain SDP instances may … Read more

    Interior-point method for nonlinear programming with complementarity constraints

  • Ladislav Lukšan
  • Ctirad Matonoha
  • Jan Vlček
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , , ,

    In this report, we propose an algorithm for solving nonlinear programming problems with com-plementarity constraints, which is based on the interior-point approach. Main theoretical results concern direction determination and step-length selection. We use an exact penalty function to remove complementarity constraints. Thus a new indefinite linear system is defined with a tridiagonal low-right submatrix. Inexact … Read more

    An Interior-Point Algorithm for Large-Scale Nonlinear Optimization with Inexact Step Computations

  • Frank E. Curtis
  • Olaf Schenk
    • Categories Nonlinear Optimization, Optimization of Systems modeled by PDEs Tags , , , , , ,

    We present a line-search algorithm for large-scale continuous optimization. The algorithm is matrix-free in that it does not require the factorization of derivative matrices. Instead, it uses iterative linear system solvers. Inexact step computations are supported in order to save computational expense during each iteration. The algorithm is an interior-point approach derived from an inexact … Read more

    An interior-point Lagrangian decomposition method for separable convex optimization

  • Ion Necoara
  • Johan Suykens
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , , ,

    In this paper we propose a distributed algorithm for solving large-scale separable convex problems using Lagrangian dual decomposition and the interior-point framework. By adding self-concordant barrier terms to the ordinary Lagrangian we prove under mild assumptions that the corresponding family of augmented dual functions is self-concordant. This makes it possible to efficiently use the Newton … Read more

    Hybrid MPI/OpenMP parallel support vector machine training

  • Jacek Gondzio
  • Kristian Woodsend
    • Categories Data-Mining, Parallel Algorithms, Quadratic Programming Tags , , ,

    Support Vector Machines are a powerful machine learning technology, but the training process involves a dense quadratic optimization problem and is computationally challenging. A parallel implementation of Support Vector Machine training has been developed, using a combination of MPI and OpenMP. Using an interior point method for the optimization and a reformulation that avoids the … Read more

    Solving multi-objective network flow problems with an interior point method

  • José Rui Figureira
  • Margarida Fonseca
  • Mauricio G.C. Resende
    • Categories Linear Programming, Multi-Criteria Optimization, Network Optimization Tags , , ,

    In this paper we present a primal-dual interior-point algorithm to solve a class of multi-objective network flow problems. More precisely, our algorithm is an extension of the single-objective primal-dual infeasible and inexact interior point method for multi-objective linear network flow problems. A comparison with standard interior point methods is provided and experimental results on bi-objective … Read more