A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations

In this work we develop a primal-dual short-step interior point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the barrier function is either impossible or too expensive. As our main contribution, we show that if approximate gradients and Hessians can be computed, and the relative errors in … Read more

New stopping criteria for detecting infeasibility in conic optimization

Detecting infeasibility in conic optimization and providing certificates for infeasibility pose a bigger challenge than in the linear case due to the lack of strong duality. In this paper we generalize the approximate Farkas lemma of Todd and Ye from the linear to the general conic setting, and use it to propose stopping criteria for … Read more

Cascading – An adjusted exchange method for robust conic programming

It is well known that the robust counterpart introduced by Ben-Tal and Nemirovski [2] increases the numerical complexity of the solution compared to the original problem. Kocvara, Nemirovski and Zowe therefore introduced in [9] an approximation algorithm for the special case of robust material optimization, called cascading. As the title already indicates, we will show … Read more

Selective Gram-Schmidt orthonormalization for conic cutting surface algorithms

It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly … Read more

Towards nonsymmetric conic optimization

In this paper we propose a new interior-point method, which is based on an extension of the ideas of self-scaled optimization to the general cones. We suggest using the primal correction process to find a {\em scaling point}. This point is used to compute a strictly feasible primal-dual pair by simple projection. Then, we define … Read more

On the Implementation of Interior Point Decomposition Algorithms for Two-Stage Stochastic Conic

In this paper we develop a practical primal interior decomposition algorithm for two-stage stochastic programming problems. The framework of this algorithm is similar to the framework in Mehrotra and \”{Ozevin} \cite{MO04a,MO04b} and Zhao \cite{GZ01}, however their algorithm is altered in a simple yet fundamental way to achieve practical performance. In particular, this new algorithm weighs … Read more

An analytic center cutting plane approach for conic programming

We analyze the problem of finding a point strictly interior to a bounded, fully dimensional set from a finite dimensional Hilbert space. We generalize the results obtained for the LP, SDP and SOCP cases. The cuts added by our algorithm are central and conic. In our analysis, we find an upper bound for the number … Read more

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

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

On exploiting structure induced when modelling an intersection of cones in conic optimization

Conic optimization is the problem of optimizing a linear function over an intersection of an affine linear manifold with the Cartesian product of convex cones. However, many real world conic models involves an intersection rather than the product of two or more cones. It is easy to deal with an intersection of one or more … Read more