在這份論文中, 我們會讀到非凸性最小值問題的最佳解條件。考慮的將是如何推廣梯度的概念, 下界函數的概念, 以及Farkas’ 引理等。我們得到針對非凸性且不可微的函數做最佳化的推廣型KKT 條件。這個推廣主要以 Jeyakumar, Rubinov, and Wu所介紹的L-subdifferential, S-property 和solvability property 的觀念為基礎, 但是我們著重於這些抽象性質與幾何的連結性及幾何上的解釋。特別對於非凸性的二次最小值問題, 我們會從圖形上與Fang, Gao, Sheu, and Wu介紹的正交對偶理論做個比較。

In this thesis, we study the global optimality conditions for non-convex minimization problems. With the extended concept of gradient, lower bound function, and Farkas’ lemma, we have the extended KKT conditions for characterizing the non-convex, non-differentiable function. The extension is based on the concept of L-subdifferential, S-property, and solvability property, introduced by Jeyakumar, Rubinov, and Wu, but we have focused on the geometrical connections and interpretation of those abstract properties. The concepts are particularly applied for non-convex quadratic minimization problems and we have made comparisons with the canonical duality theory, introduced by Fang, Gao, Sheu, and Wu, by figures.

[1] Bazaraa, Mokhtar S., Sherali, Hanif D., and Shetty, C. M. (2006), Nonlinear programming, Hoboken, NJ:Wiley-Interscience [JohnWiley & Sons], third edition, theory and algorithms.

[2] Ben-Tal, Aharon and Nemirovski, Arkadi (2001), Lectures on modern convex optimization, MPS/SIAM Series on Optimization, Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), analysis, algorithms, and engineering applications.

[3] Bertsekas, Dimitri P. (2003), Convex analysis and optimization, Athena Scientific, Belmont, MA, with Angelia Nedi’c and Asuman E. Ozdaglar.

[4] Fang, Shu-Cherng, Gao, David Yang, Sheu, Ruey-Lin, and Wu, Soon-Yi (2008), “Canonical dual approach to solving 0-1 quadratic programming problems”, J. Ind. Manag. Optim., 4(1), 125–142.

[5] Hiriart-Urruty, Jean-Baptiste (1998), “Conditions for global optimality. II”, J.Global Optim., 13(4), 349–367, workshop on Global Optimization (Trier, 1997).

[6] Ill’es, T. and Kassay, G. (1994), “Farkas type theorems for generalized convexities”, Pure Math. Appl., 5(2), 225–239.

[7] (1999), “Theorems of the alternative and optimality conditions for convexlike and general convexlike programming”, J. Optim. Theory Appl., 101(2), 243–257.

[8] Jeyakumar, V., Rubinov, A. M., and Wu, Z. Y. (2006), “Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints”, J. Global Optim., 36(3), 471–481.

[9] (2007), “Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions”, Math. Program., 110(3, Ser. A), 521–541.

[10] Jeyakumar, V. and Srisatkunarajah, S. (2009), “Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma”, Optim. Lett., 3(1), 23–33.

[11] Luenberger, David G. and Ye, Yinyu (2008), Linear and nonlinear programming, nternational Series in Operations Research & Management Science, 116, New York: Springer, third edition.

[12] P’olik, Imre and Terlaky, Tam’as (2007), “A survey of the S-lemma”, SIAM Rev., 49(3), 371–418 (electronic).

[13] Polyak, B. T. (1998), “Convexity of quadratic transformations and its use in control and optimization”, J. Optim. Theory Appl., 99(3), 553–583.