在這篇論文，我們討論在單一個非凸性二次限制式下求解二次目標式的廣域最小值,並希望藉由找出對偶問題的解來反推原非凸性問題的最佳解。我們提供一個比傳統Slater條件更廣的同餘對角化觀念,並證明在此推廣條件下仍能有效使用對偶訊息來解答原問題。這其中的一個關鍵步驟是當反推出的解和對偶問題的解產生對偶間隙時,可以利用「邊界化」的手法找到一個新的沒有對偶間隙的解,而這同時也是原問題的廣域最小解。我們進一步分析出這個非凸性問題事實上等價於一個具線性限制式的凸規劃問題,這也意味著單一個限制式下的二次規劃問題是一個具有較好結構的非凸性問題。最後,我們將這個工作與Stern和Wolkowicz 1995年所發表的結果做相關的回顧和比較。

In this thesis, we discuss the minimum of a quadratic object function with one nonconvex quadratic constraint. We want to find the primal optimal solution via its corresponding canonical dual solution. We propose the relaxed assumption, simultaneously diagonalization via congruence (SDC), rather than traditional Slater condition. Under this relaxed assumption, we prove that we can still use information from dual problem to find the primal optimal solution. The key point is when the primal solution we found via its corresponding dual solution is not the optimal solution, we can apply ``boundirification technique' to find another solution with no duality gap, and this is also the primal optimal solution. With further analysis, this primal nonconvex problem in fact equals a linearly constrained convex problem, which means a quadratic object function with one quadratic constraint is a nice-structured nonconvex problem. Finally, we have a related review and comparison to Stern and Wolkowicz's result in 1995.

[1] A. Beck and Y.C. Eldar, Strong duality nonconvex quadratic optimization with two quadratic constraints. SIAM J. Optim., 17(3), 2006, 844-860.
[2] A. Ben-Tal and M. Teboulle, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Mathematical Programming 72, 1996, 51-63.
[3] S.C. Fang, D.Y. Gao, R.L. Sheu and S.Y. Wu, Canonical dual approach to solve 0-1 quadratic programming problems, J. Industrial and Management Optimization, 4(1), 2008, 125-142.
[4] S.C. Fang, D.Y. Gao, R.L. Sheu and W. Xing, Global optimization for a class of fractional programming problems. Journal of Global Optimization, 45(3), 2009, 337-353.
[5] V. Jeyakumar, A.M. Rubinov and Z.Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions. Math. Program, 2006, 521-541.
[6] S.C. Fang, G.X. Lin, R.L. Sheu and W. Xing, Canonical dual solutions for the double well potential problem, preprint.
[7] G. C. Fehmers, L. P. J. Kamp, and F. W. Sluijter, An algorithm for quadratic optimization with one quadratic constraint and bounds on the variables. Inverse Problems, 14, 1998, 893-901.
[8] C. Fortin and H.Wolkowicz, The trust region subproblem and semidefinite programming. Optimization Methods and Software. 19(1), 2004, 41-67. 57
[9] D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization. Journal of Global Optimization, 17, 2000, 127-160.
[10] D. Y. Gao, Canonical duality theory and solutions to constrainted nonconvex quadratic programming. Journal of Global Optimization, 29, 2004, 377-399.
[11] D. M. Gay, Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput., 2(2), 1981, 186-197.
[12] G. H. Golub and U. Von Matt, Quadratically constrained least squares and quadratic problems. Numerische Mathematik, 59, 1991, 186-197.
[13] J.-B. Hiriart-Urruty, Potpourri of conjectures and open questions in nonlinear analysis and optimization. SIAM Review, 49(2), 2007, 255-273.
[14] J.M. Mart´inez, Local minimizers of quadratic functions on euclidean balls and spheres. SIAM J. Optimization, 4, 1994, 159-176.
[15] J.J. More and D.C. Sorensen, Computing a trust region step. SIAM J. Sci. Statist. Comput., 4, 1983, 553-572.
[16] R.J. Stern and H. Wolkowicz, Indefinite trust region subproblems and nonsymmetric perturbations. SIAM J. Optim., 5(2), 1995, 286-313.
[17] J.F. Sturm and S. Zhang, On cones of nonnegative quadratic functions. Mathematics of Operations Research, 28(2), 2003, 246-267.
[18] F. Uhlig, A recurring theorem about pairs of quadratic forms and extension: A survey, Linear Algebra Appl., 25, 1979, 219-237.
[19] Frank Uhlig, Simultaneous Block Diagonalization of Two Real Symmetric Matrices, Linear Algebra and Its Applications, (1973), 281-289.
[20] Z. Wang, S.C. Fang, D.Y. Gao and W. Xing, Global extremal conditions for multiinteger quadratic programming. J. Industrial and Management Optimization, 4(2), 2008 213-225. 58
[21] W. Xing, S.C. Fang, D.Y. Gao, R.L. Sheu and L. Zhang, Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted.
[22] M.S. Bazaraa, H.D. Sherali and C.M. Shetty Nonlinear Programming 3rd edition, Wiley- Interscience, U.S.A., 2006.
[23] I.M. Gelfand and S.V. Silverman, Calculus of Variation, Dover Publications, Inc, New York, 1991.
[24] D.G. Luenberger, Linear and Nonlinear programming, Addison-Wesley Publishing Company, 1984.
[25] R.G. Bartle, The Element of Real Analysis second edition, Central Book Company, Taipei, Taiwan, 1978.
[26] R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, New York, 1985.
[27] Y. Ye and S. Zhang, New results on quadratic minimizations, SIAM J. Optim., 14(1) (2003), 245-267.
[28] V. Jeyakumar, A.M. Rubinov and Z.Y. Wu, Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints, Journal of Global Optimization, (2006), 471-481.
[29] Louis Brickman, On The Field of Values of a Matrix. AMS, 1961, 61-66.
[30] E. Phan-huy-Hao, Quadratically Constrained Quadratic Programming: Some Applications and Method for Solution. Zeitschrift f¨ur Operations Research, 1982, 105-119.
[31] Y. Ye and S. Zhang, New results on quadratic minimization. SIAM J. Optim., 14(1), 2003, 245-267.
[32] Joe-Mei Feng, Gang-Xuan Lin, Ruey-Lin Sheu and Yong Xia, Duality and Solutions for Quadratic Programming over One Non-Homogeneous Quadratic Constraint, submitted.