查詢結果分析
來源資料
頁籤選單縮合
題 名 | A Path-Following Interior Point Algorithm for Smooth Convex Programming=一個解圓滑凸規劃的沿路徑內點法 |
---|---|
作 者 | 朱亮儒; | 書刊名 | 師大學報 |
卷 期 | 41 1996.06[民85.06] |
頁 次 | 頁393-434 |
分類號 | 319.711 |
關鍵詞 | 解圓滑凸規劃; 沿路徑內點法; Smooth convex programming; Path-following interior point algorithm; Complementarity problem; Maximal complementary solution; |
語 文 | 英文(English) |
中文摘要 | 本文主要在探討數學規劃中,近年來常被用來找近似解的內點法。在本論文中我 們推廣Monteiro和Adler的沿路徑內點法(path-following interi or point algorithm) 以求解圓滑凸規劃問題,並分析探討其運算次數(arithmetic operation)之複雜性 (complexity),在原問題有一嚴格可行解的條件下,我們證明這種內點法僅需要 ○(□l)迭代次數(iterations),且整個運算過程僅需○(n�爐)個算數運算 (arithmetic operations)。其結果應用在凸二次規劃(convex quadratic programming) 或線性規劃(linear programming)問題時是最理想化的。更進一步地,我們的內點法所產 生的每一極限點都是其對應的互補問題(complementarityproblem)的最大互補解。 |
英文摘要 | We extend the Monteiro-Adler path-following interior point algorithm for solving smooth convex programming. Under a kind of strict feasibility assumption, we show that the algorithm under modification requires a total of ○(□l) number of iterations, and the total arithmetic operations are not more than ○(n�爐), where l is the initial input size. As an application to usual linear or convex quadratic programming, this algorithm solves the pair of primal and dual problems in at most ○(□L) iterations, and the total arithmetic operations are shown to be of the order of ○(n�鶉), where L is the input size. Moreover, we show that any sequence (x��,s��) generated by the algorithm is bounded, and that every cluster point is a maximal complementary solution in the sense of McLinden [16,17]. |
本系統中英文摘要資訊取自各篇刊載內容。