Information Geometry and Primal-Dual Interior-point Algorithms

In this paper, we study polynomial-time interior-point algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a self-concordant barrier function. Riemannian metric is defined with the Hessian of the barrier function. We introduce two connections $\nabla$ and $\nabla^*$ which roughly corresponds to the primal and … Read more

A decomposition-based warm-start method for stochastic programming

In this paper we propose a warm-start technique for interior point methods applicable to multi-stage stochastic programming problems. The main idea is to generate an initial point for the interior point solver by decomposing the barrier problem associated with the deterministic equivalent at the sec- ond stage and using a concatenation of the solutions of … Read more

An interior-point method for minimizing the sum of piecewise-linear convex functions

We consider the problem to minimize the sum of piecewise-linear convex functions under both linear and nonnegative constraints. We convert the piecewise-linear convex problem into a standard form linear programming problem (LP) and apply a primal-dual interior-point method for the LP. From the solution of the converted problem, we can obtain the solution of the … Read more

Asymptotic expansion for the solution of a penalized control constrained semilinear elliptic problems

In this work we consider the optimal control problem of a semilinear elliptic PDE with a Dirichlet boundary condition, where the control variable is distributed over the domain and is constrained to be nonnegative. The approach is to consider an associated parametrized family of penalized problems, whose solutions define a central path converging to the … Read more

An L1 Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints

We propose an interior-point algorithm based on an elastic formulation of the L1-penalty merit function for mathematical programs with complementarity constraints. The method generalizes that of Gould, Orban and Toint (2003) and naturally converges to a strongly stationary point or delivers a certificate of degeneracy without recourse to second-order intermediate solutions. Remarkably, the method allows … Read more

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

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

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

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

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

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