An Analytic Center Quadratic Cut Method for the Convex Quadratic Feasibility
Problem.
Faranak Sharifi Mokhtarian and Jean-Louis Goffin
We consider a quadratic cut method based on analytic centers for two
cases of convex quadratic feasibility problems. In the first case, the
convex set is defined by a finite yet large number of convex quadratic
inequalities. We extend quadratic cut algorithm of Luo and
Sun~\cite{LS1} for solving such problems by placing or translating the
quadratic cuts directly through the current approximate center. We
show that our algorithm has the same polynomial worst case complexity
as theirs~\cite{LS1}. In the second case, the convex set is defined by
an infinite number of certain strongly convex quadratic
inequalities. We adapt the same quadratic cut method for the first
case to the second one. We show that in the second case the quadratic
cut algorithm is a fully polynomial approximation scheme.
Furthermore, we show that in both cases, at each iteration, the total
number of (damped) Newton steps required to update from one
approximate analytic center to another is at most $O(1)$.
GERAD Tech. report G-2000-18, 19 pp, april 2000.
Contact: [email protected]