Optimization Online


Solution of monotone complementarity and general convex programming problems using modified potential reduction interior point method

Kuo-Ling Huang (jupiters1117***at***northwestern.edu)
Sanjay Mehrotra (mehrotra***at***iems.northwestern.edu)

Abstract: We present a homogeneous algorithm equipped with a modified potential function for the monotone complementarity problem. We show that this potential function is reduced by at least a constant amount if a scaled Lipschitz condition is satis ed. A practical algorithm based on this potential function is implemented in a software package named iOptimize. The implementation in iOptimize maintains global linear polynomial-time convergence properties while achieving practical performance. When compared with a mature software package Mosek (barrier solver version, iOptimize solves convex quadratic programming problems, convex quadratically constrained quadratic programming problems, and general convex programming problems in fewer iterations. Moreover, several problems for which Mosek fails are solved to optimality.

Keywords: quadratic programs, quadratically constrained quadratic programs, convex programs, homogeneous algorithms, interior point methods

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Address: Dept. of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 60208 Email: mehrotra@iems.northwestern.edu

Download: [PDF]

Entry Submitted: 04/12/2012
Entry Accepted: 04/12/2012
Entry Last Modified: 01/23/2013

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 Optimization Society