Please use this identifier to cite or link to this item:
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].
Other Identifiers: B35DACD2-029E-AD58-5023-89859C16A35E
Appears in Collections:師大學報

Files in This Item:
File SizeFormat 
ntnulib_ja_L0801_0041_393.pdf843.25 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.