On Conically Ordered Convex Programs

In this paper we study a special class of convex optimization problems called {\em conically ordered convex programs}\/ (COCP), where the feasible region is given as the level set of a vector-valued nonlinear mapping, expressed as a nonnegative combination of convex functions. The nonnegativity of the vectors is defined using a pre-described conic ordering. The new model extends the ordinary convex programming models where the feasible sets are the level sets of convex functions, and it also extends the famous linear conic optimization models. We introduce a condition on the barrier function for the order-defining cone, termed as the {\em cone-consistent property}. The relationship between the cone-consistent barriers and the self-concordance barriers is investigated. We prove that if the order-defining cone admits a self-concordant and cone-consistent barrier function, and moreover, if the constraint functions are all convex quadratic then the overall composite barrier function is self-concordant. The problem is thus solvable in polynomial time, following Nesterov and Nemirovski, by means of the path-following method. If the constraint functions are not quadratic, but {\em harmonically convex}, then we propose a variant of Iri-Imai type potential reduction method. To facilitate the analysis, in addition to the self-concordance and the cone-consistence conditions, we assume that the barrier function for the order-defining cone is so that the image of the cone under its Hessian matrix is contained in the dual cone. All these conditions are satisfied by the familiar self-scaled cones. Under these conditions we show that the Iri-Imai type potential reduction algorithm converges in polynomial time. Duality issues related to this class of optimization problems are discussed as well.


Technical Report Series SEEM2003-09 Department of Systems Engineering & Engineering Management The Chinese University of Hong Kong May 2003



View On Conically Ordered Convex Programs