Towards non-symmetric conic optimization

Abstract

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 cases. We suggest using the primal correction process to find a scaling point. This point is used to compute a strictly feasible primal–dual pair by simple projection. Then, we define an affine-scaling direction and perform a prediction step. This is the only moment when the dual barrier is used. Thus, we need only to compute its value, which can even be done approximately. In the second part of the paper, we develop a 4n-self-concordant barrier for an n-dimensional p-cone, which can be used for numerical testing of the proposed technique.

Keywords:

• convex optimization
• conic problems
• interior-point methods
• long-step path-following methods
• self-concordant barriers
• self-scaled barriers
• affine-scaling direction
• p-norm minimization

Acknowledgements

The author thanks Laurence Wolsey for the useful comments on the text and the anonymous referees for their suggestions. The research results presented in this paper have been supported by the grant ‘Action de recherche concertè ARC 04/09-315’ from the ‘Direction de la recherche scientifique – Communautè française de Belgique’. The scientific responsibility rests with the author.

Notes

We mean the cones which cannot be obtained as the intersections of the symmetric cones by linear subspaces.

This can be justified, for example, by the results given in Section 4.1.5 in 7. Indeed, the damped Newton method converges quadratically from any point τ with . In view of Theorem 4.1.13 given in 7, the latter inequality follows from .