  


On Conically Ordered Convex Programs
Shuzhong Zhang (zhangse.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 vectorvalued nonlinear mapping, expressed as a nonnegative combination of convex functions. The nonnegativity of the vectors is defined using a predescribed 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 orderdefining cone, termed as the {\em coneconsistent property}. The relationship between the coneconsistent barriers and the selfconcordance barriers is investigated. We prove that if the orderdefining cone admits a selfconcordant and coneconsistent barrier function, and moreover, if the constraint functions are all convex quadratic then the overall composite barrier function is selfconcordant. The problem is thus solvable in polynomial time, following Nesterov and Nemirovski, by means of the pathfollowing method. If the constraint functions are not quadratic, but {\em harmonically convex}, then we propose a variant of IriImai type potential reduction method. To facilitate the analysis, in addition to the selfconcordance and the coneconsistence conditions, we assume that the barrier function for the orderdefining 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 selfscaled cones. Under these conditions we show that the IriImai 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, selfconcordant barriers, potential reduction. Category 1: Linear, Cone and Semidefinite Programming Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Technical Report Series SEEM200309 Department of Systems Engineering & Engineering Management The Chinese University of Hong Kong May 2003 Download: [Postscript] Entry Submitted: 05/26/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  