Optimization Online


On Conically Ordered Convex Programs

Shuzhong Zhang (zhang***at***se.cuhk.edu.hk)

Abstract: 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.

Keywords: convex programming, conic ordering, self-concordant barriers, potential reduction.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

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

Download: [Postscript]

Entry Submitted: 05/26/2003
Entry Accepted: 05/26/2003
Entry Last Modified: 05/26/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society