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.
摘要 I
Abstract II
誌謝III
Contents IV
Chapter 1 Introduction 1
Chapter 2 Assumptions and Duality 5
2.1 Assumption Comparison 5
2.2 Canonical Dual Problem 19
Chapter 3 Insights of Boundarification 30
Chapter 4 Hidden convexity 36
Chapter 5 A look at Stern and Wolkowicz’s work 44
5.1 Solution to two-sided constrained problem 44
5.2 Solution to two-sided constrained problem by Stern and Wolkowicz 45
5.2.1 Regular case 48
5.2.2 irregular case 51
5.2.3 conclusion 51
5.3 Necessary conditions by Stern and Wolkowicz 51
Chapter 6 Conclusion and Future Research 56
Bibliography 57
[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.