Please use this identifier to cite or link to this item: `http://rportal.lib.ntnu.edu.tw:80/handle/77345300/17563`
 Title: A Path-Following Interior Point Algorithm for Smooth Convex Programming Other Titles: 一個解圓滑凸規劃的沿路徑內點法 Authors: 朱亮儒 Issue Date: Jun-1996 Publisher: 國立臺灣師範大學研究發展處Office of Research and Development Abstract: 本文主要在探討數學規劃中，近年來常被用來找近似解的內點法。在本論文中我們推廣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]. URI: http://rportal.lib.ntnu.edu.tw//handle/77345300/17563 Other Identifiers: B35DACD2-029E-AD58-5023-89859C16A35E Appears in Collections: 師大學報

Files in This Item:
File SizeFormat