Solution of Monotone Complementarity and General Convex Programming Problems Using a Modified Potential Reduction Interior Point Method

Kuo-Ling Huang () and Sanjay Mehrotra ()
Additional contact information
Kuo-Ling Huang: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208
Sanjay Mehrotra: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208

INFORMS Journal on Computing, 2017, vol. 29, issue 1, 36-53

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 (SLC) is satisfied. A practical algorithm based on this potential function is implemented in a software package named iOptimize. The implementation in iOptimize maintains global linear and polynomial time convergence properties, while achieving practical performance. It either successfully solves the problem, or concludes that the SLC is not satisfied. When compared with the mature software package MOSEK (barrier solver version 6.0.0.106), 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. We also find that iOptimize detects infeasibility more reliably than the general nonlinear solvers Ipopt (version 3.9.2) and Knitro (version 8.0).

Keywords: quadratic programs; quadratically constrained quadratic programs; convex programs; homogeneous algorithms; interior point methods (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0715 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:1:p:36-53

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().