(3.236.231.14) 您好!臺灣時間:2021/04/15 08:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林剛玄
研究生(外文):Gang-XuanLin
論文名稱:單一個二次型限制式的二次優化問題通解
論文名稱(外文):A Complete Solution to Quadratic Programming with One Inequality Quadratic Constraint
指導教授:許瑞麟許瑞麟引用關係
指導教授(外文):Ruey-Lin Sheu
學位類別:博士
校院名稱:國立成功大學
系所名稱:數學系應用數學碩博士班
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2018
畢業學年度:105
語文別:英文
論文頁數:69
中文關鍵詞:二次型限制式的二次優化不帶有限制式的非線性優化信賴區域法矩陣束同餘對角化
外文關鍵詞:Quadratically constrained quadratic programunconstrained nonlinear programmingtrust region methodmatrix pencilsimultaneously diagonalizable via congruence
相關次數:
  • 被引用被引用:0
  • 點閱點閱:61
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
這篇論文中主要是針對單一的非凸二次型限制式的非凸二次型優化問題 (QP1QC). 這問題從西元 1990 年左右起於一個叫信賴區域法 (trust region method). 信賴區域法是一個求不帶有限制式的非線性優化問題的區域最優解, 而 (QP1QC) 則為信賴區域法中所產生的核心問題. 為求得與 (QP1QC) 相同型態的問題的全域最優解, 傳統的牛頓疊代法曾經被拿來當成求解的主要方法將近數百餘年, 但我們都知道牛頓法的收練斂性是有限制的: 如果不幸地, 當起始的疊代點猜測得不好, 離最優解太遠時, 牛頓法有可能會發散. 無論如何, 信賴區域法是一個不受起始疊代點的位置限制而仍然全域收斂的方法. 信賴區域法所產生的問題, 在理論上時常利用半正定優化問題 (semi-definite programming, SDP問題) 再搭配單秩分解 (rank-one decomposition) 的方法求之. 雖然, 將原始問題轉換成SDP問題時, 整個問題的維度是原始問題維度的平方倍, 也就是說, SDP鬆弛方法伴隨著昂貴的矩陣計算問題與儲存問題, 但SDP問題與單秩分解二者仍然是近數十年來優化問題時常被拿來使用的主流技巧. 這篇論文中所討論的 (QP1QC) 問題, 我們利用矩陣束 (matrix pencil) 當工具, 在問題的原始空間解之. 因此, 此方法的優點便是省下矩陣的儲存空間與計算量. 我們也利用相同的方法去刻劃出雙勢能井問題 (double (energy) well potential problem) 的全域最優解集合與其對偶的完整特徵. 雙勢能井問題從許多自然現像所產生, 如物理裡的彈性力學中與化學裡的 van der Waals’ force 問題.
This dissertation focused on nonconvex quadratic optimization subject to one nonconvex quadratic constraint. The problem arises from the trust region method which, since 1990, has been the central issue for finding a local minimum of an unconstrained nonlinear programming. Traditional Newton’s method has dominated for hundreds of years for the same type of problems, but it suffers from being divergent when the initial guess is unluckily far off the target. The trust region method, however, enjoys the global convergence without depending on the location of the initial point. The trust region method is often solved, in theory, by a semi-definite programming reformulation followed by a rank-one decomposition. Both are state of the art optimization technique for the most recent decade. Nevertheless, the SDP relaxation suffers from expensive matrix computation due to the necessity to square the dimension of the original problem. Our analysis toward the problem uses the matrix pencil as the tool and solves the problem in the original space. Therefore, it has the advantage of saving computational cost. We also applied the same analytical method to solve the double (energy) well potential problem with a complete characterization to the global optimal set and to the duality. The double well problem has appeared in many natural phenomena such as elastic mechanics and van der Waals’ force in chemistry.
1 Introduction 1
1.1 Trust Region Method and Formulations 2
1.2 Notations 4
2 Preliminaries 5
2.1 Solve (QP1QC) via Semi-Definite Programming 6
2.2 Solve (QP1QC) via Lagrange Dual Problem 11
2.2.1 Solutions to (QP1QC) via Dual Approach 14
3 New Results on Matrix Pencil and SDC 25
3.1 (QP1QC) Violating Primal Slater Condition 25
3.2 (QP1QC) under Primal Slater Condition 29
3.2.1 Matrix Pencils 29
3.2.2 Solving (QP1QC) via Matrix Pencils 38
3.2.3 Numerical Example to Solving (QP1QC) via Matrix Pencils 47
3.3 (QP1QC) without SDC 57
4 Applications of QP1QC 62
5 Conclusions 65
References 66
[1] R. I. Becker, “Necessary and sufficient conditions for the simultaneous diagonability of two quadratic forms, Linear Algebra and its Applications, 30, 129-139, Apr. 1980.

[2] A. Ben-Tal and M. Teboulle, “Hidden convexity in some nonconvex quadratically constrained quadratic programming, Mathematical Programming, 72: (1), 51-63, Jan. 1996.

[3] T. Bodineau, “On the van der Waals theory of surface tension, Markov Processes and Related Fields, 8: (2), 319-338, 2002.

[4] S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, “Linear matrix inequalities in system and control theory, Studies in Applied and Numerical Mathematics, SIAM, 15, 1994.

[5] S. Boyd and L. Vandenberghe, “Convex optimization, Cambridge University Press, 2004.

[6] J. I. Brauman, “Some historical background on the double-well potential model, Journal of Mass Spectrometry, 30: (12), 1649-1651, Dec. 1995.

[7] R. H. Byrd, R. B. Schnabel and G. A. Shultz, “A trust region algorithm for nonlinearly constrained optimization, SIAM Journal on Numerical Analysis, 24: (5), 1152-1170, 1987.

[8] R. H. Byrd, R. B. Schnabel and G. A. Shultz, “Approximate solution of the trust region problem by minimization over two-dimensional subspaces, Mathematical Programming, 40: (1), 247-263, Jan. 1988.

[9] S. C. Fang, D. Y. Gao, G. X. Lin, R. L. Sheu and W. Xing, “Double well potential function and its optimization in the n-dimensional real space - part I, Journal of Industrial and Management Optimization (JIMO), 13: (3), 1291-1305, Jul. 2017.

[10] 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: (4), 893-901, Aug. 1998.

[11] J. M. Feng, G. X. Lin, R. L. Sheu and Y. Xia, “Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint, Journal of Global Optimization 54: (2), 275-293, Oct. 2012.

[12] C. Fortin and H. Wolkowicz, “The trust region subproblem and semidefinite programming, Optimization Methods and Software, 19: (1), 41-67, 2004.

[13] D. Y. Gao and H. Yu, “Multi-scale modelling and canonical dual finite element method in phase transitions of solids, International Journal of Solids and Structures, 45: (13), 3660-3673, Jun. 2008.

[14] D. M. Gay, “Computing optimal locally constrained steps, SIAM Journal on Scientific and Statistical Computing, 2: (2), 186-197, 1981.

[15] G. H. Golub and U. von Matt, “Quadratically constrained least squares and quadratic problems, Numerische Mathematik, 59: (1), 561-580, Dec. 1991.

[16] C. Helmberg, “Semidefinite programming, European Journal of Operational Research, 137: (3), 461-482, Mar. 2002.

[17] A. Heuer and U. Haeberlen, “The dynamics of hydrogens in double well potentials: The transition of the jump rate from the low temperature quantum-mechanical to the high temperature activated regime, The Journal of Chemical Physics, 95: (6), 4201-4214, Sep. 1991.

[18] J.-B. Hiriart-Urruty, “Potpourri of conjectures and open questions in nonlinear analysis and optimization, SIAM Review, 49: (2), 255-273, Apr. 2007.

[19] R. A. Horn and C. R. Johnson, “Matrix analysis, Cambridge University Press, 1990.

[20] R. L. Jerrard, “Lower bounds for generalized Ginzburg-Landau functionals, SIAM Journal on Mathematical Analysis, 30: (4), 721-746, 1999.

[21] K. Kaski, K. Binder and J. D. Gunton, “A study of a coarse-grained free energy functional for the three-dimensional Ising model, Journal of Physics A: Mathematical and General, 16: (16), 623-627, 1983.

[22] J. M. Mart´ınez, “Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM Journal on Optimization, 4: (1), 159-176, 1994.

[23] J. J. Mor´ e, “Generalizations of the trust region problem, Optimization Methods and Software, 2: (3-4), 189-209, Jan. 1993.

[24] J. J. Mor´ e and D. C. Sorensen, “Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4: (3), 553-572, 1983.

[25] Y. Nesterov and A. Nemirovskii, “Interior-point polynomial algorithms in convex programming, Studies in Applied and Numerical Mathematics, SIAM, 1994.

[26] E. O. Omojokun, “Trust region algorithms for optimization with nonlinear equality and inequality constraints, Ph. D. Thesis, University of Colorado at Boulder, 1989.

[27] I. P´ olik and T. Terlaky, “A survey of the S-lemma, SIAM Review, 49: (3), 371-418, 2007.

[28] N. Z. Shor, “Quadratic optimization problems, Soviet Journal of Computer and Systems Sciences, 25: (6), 1-11, Nov. 1987.

[29] R. J. Stern and H. Wolkowicz, “Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM Journal on Optimization, 5: (2), 286-313,
1995.

[30] J. F. Sturm and S. Zhang, “On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28: (2), 246-267, 2003.

[31] F. Uhlig, “A recurring theorem about pairs of quadratic forms and extensions: a survey, Linear Algebra and its Applications, 25, 219-237, Jun. 1979.

[32] L. Vandenberghe and S. Boyd, “Semidefinite programming, SIAM Review, 38: (1), 49-95, Mar. 1996.

[33] Y. Xia, R. L. Sheu, S. C. Fang and W. Xing, “Double well potential function and its optimization in the n-dimensional real space - part II, Journal of Industrial and Management Optimization (JIMO), 13: (3), 1307-1328, Jul. 2017.

[34] W. Xing, S. C. Fang, R. L. Sheu and L. Zhang, “Canonical dual solutions to quadratic optimization over one quadratic constraint Asia-Pacific Journal of Operational Research, 32: (1), Feb. 2015.

[35] Y. Ye and S. Zhang, “New results on quadratic minimization, SIAM Journal on Optimization, 14: (1), 245-267, 2003.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔