Abstract of My Doctor Thesis
Quadratic optimization constitutes one of the most important areas of nonlinear
programming. Quadratic optimization problems (abbreviated by QOPs) cover not
only direct applications of economics, engineering, and other fields, but various
important nonconvex mathematical programs. Though several kinds of QOPs have
attracted many researchers since the 1970s, there are only a few solution techniques
for solving the most general class of QOPs because of their theoretical and practical
difficulties.
Recently, Kojima and Tun\c{c}el [1998] proposed quite unconventional
outer-approximation procedures; successive convex relaxation methods (abbreviated by
SCRMs) for solving general QOPs,and established a theoretical framework of their
methods. However, their methods remain theoretical because they require tremendous
numerical computation.
This thesis investigates SCRMs in further detail by highlighting the following
issues (i)-(iv) to derive ``better'' procedures than existing techniques.
Here a ``better'' procedure means that it attains a more accurate approximation
for the optimal objective function value of a QOP with less computational time.
(i) Computational complexity analysis on conceptual SCRMs proposed by
Kojima-Tun\c{c}el.
(ii) Dissolving some remaining concerns of conceptual SCRMs, which lead to
practical SCRMs.
(iii) Devising special SCRMs for bilevel programs.
(iv) Implementing SCRMs on a parallel computing system.
The study of (i) showed that the amount of computation which a conceptual SCRM
requires is mainly affected by the size of an initial relaxed region including
the feasible region of a given QOP. Under the study of (ii), practical versions
of SCRMs were implemented on computer. Numerical results demonstrated that the
methods could provide relatively good approximation for optimal objective function
values in most test problems, compared with the popular reformulation-linearization
technique. The study of (iii) proposed an equivalent transformation from a bilevel
quadratic optimization problem to a one-level QOP. An exploitation of the special
structure in the transformed QOP accelerates the SCRM and generates tighter
approximation. The study of (iv) paid attention to the structure of SCRMs suitable
to parallel computing. The SCRMs, implemented on a PC cluster, handled larger-sized
problems which other SCRMs had not dealt with.