کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477680 | 1446178 | 2008 | 20 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: New complexity analysis of IIPMs for linear optimization based on a specific self-regular function New complexity analysis of IIPMs for linear optimization based on a specific self-regular function](/preview/png/477680.png)
Primal–dual interior-point methods (IPMs) have shown their ability in solving large classes of optimization problems efficiently. Feasible IPMs require a strictly feasible starting point to generate the iterates that converge to an optimal solution. The self-dual embedding model provides an elegant solution to this problem with the cost of slightly increasing the size of the problem. On the other hand, infeasible interior point methods (IIPMs) can be initiated by any positive vector, and thus are popular in IPMs based software packages. In this paper we propose an adaptive large-update IIPM based on a specific self-regular proximity function, with barrier degree 1+logn1+logn, that operates in a negative infinity neighborhood of the central path. An O(n32lognlognϵ) worst-case iteration bound of the new algorithm is established. This iteration bound improves the so far best O(n2lognϵ) iterations bound of IIPMs in a large neighborhood of the central path.
Journal: European Journal of Operational Research - Volume 186, Issue 2, 16 April 2008, Pages 466–485