(3.236.231.14) 您好！臺灣時間：2021/04/15 08:24

### 詳目顯示:::

:

• 被引用: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 42 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 143 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 574 Applications of QP1QC 625 Conclusions 65References 66