- | ||||
|
![]()
|
An Adaptive Self-Regular Proximity Based Large-Update IPM for LO
Maziar Salahi (msalahi Abstract: Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. However, there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results with respect to the update strategies of the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy the best known theoretical worst-case iteration bound but their performance in computational practice is poor, while the so-called large-update IPMs have superior practical performance but with relatively weaker theoretical results. This gap was reduced by Peng, Roos, and Terlaky \cite{Pengbook} who introduced a new family of Self-Regular (SR) proximity functions based IPMs. In this paper, by restricting us to linear optimization, we propose an adaptive single step large-update IPM for a class of SR-proximities. At each step our algorithm chooses the target value adaptively and the update is a large update. The new algorithm does not do any inner iterations, unlike other large update methods. An $\O\br{qn^{\frac{q+1}{2q}}\log{\frac{n}{\e}}}$ worst-case iteration bound of the algorithm is established, where $q$ is the barrier degree of the SR-proximity. For a special choice of $q$ the best complexity for large-update IPMs is established. Keywords: Linear Optimization, Primal-Dual Interior-Point Method, Self-Regular Proximity Function, Polynomial Complexity Category 1: Linear, Cone and Semidefinite Programming Citation: AdvOl-Report#2003/4(Advanced Optimization Lab, Department of Computing and Software McMaster University): Submitted to Math. Programming. Download: [Postscript][PDF] Entry Submitted: 11/28/2003 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |