Method of analytic centers for quadratically constrained convex quadratic programs

Sanjay Mehrotra*, Jie Sun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

An interior point method is developed for maximizing a concave quadratic function order convex quadratic constraints. The algorithm constructs a sequence of nested convex sets and finds their approximate centers using a partial Newton step. Given the first convex set and its approximate center, the total arithmetic operations required to converge to an approximate solution are of order O(√m(m + n)n2 ln ε), where m is the number of constraints, n is the number of variables, and ε is determined by the desired tolerance of the optimal value and the size of the first convex set. A method to initialize the algorithm is also proposed so that the algorithm can start from an arbitrary (perhaps infeasible) point.

Original languageEnglish (US)
Pages (from-to)529-544
Number of pages16
JournalSIAM Journal on Numerical Analysis
Volume28
Issue number2
DOIs
StatePublished - Jan 1 1991

ASJC Scopus subject areas

  • Numerical Analysis

Fingerprint Dive into the research topics of 'Method of analytic centers for quadratically constrained convex quadratic programs'. Together they form a unique fingerprint.

Cite this