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.