A HYBRID ADAPTIVE ALGORITHM FOR LINEAR OPTIMIZATION

Maziar Salahi () and Tamás Terlaky ()
Additional contact information
Maziar Salahi: Department of Mathematics, Faculty of Sciences, University of Guilan, P.O. Box 1914, Rasht, Iran
Tamás Terlaky: Department of Industrial and Systems Engineering, Lehigh University, USA

Asia-Pacific Journal of Operational Research (APJOR), 2009, vol. 26, issue 02, 235-256

Abstract: Recently, using the framework of self-regularity, Salahi in his Ph.D. thesis proposed an adaptive single step algorithm which takes advantage of the current iterate information to find an appropriate barrier parameter rather than using a fixed fraction of the current duality gap. However, his algorithm might do at most one bad step after each good step in order to keep the iterate in a certain neighborhood of the central path. In this paper, using the same framework, we propose a hybrid adaptive algorithm. Depending on the position of the current iterate, our new algorithm uses either the classical Newton search direction or a self-regular search direction. The larger the distance from the central path, the larger the barrier degree of the self-regular search direction is. Unlike the classical approach, here we control the iterates by guaranteeing certain reduction of the proximity measure. This itself leads to a one dimensional equation which determines the target barrier parameter at each iteration. This allows us to have a large update algorithm without any need for safeguard or special steps. Finally, we prove that our hybrid adaptive algorithm has an$\mathcal{O}\Big(n^\frac{71}{100}\, {\rm log}\, n\, {\rm log}\, \frac{(x^0)^Ts^0}{\epsilon}\Big)$worst case iteration complexity.

Keywords: Linear optimization; interior point methods; self-regular functions; polynomial complexity (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595909002183
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:26:y:2009:i:02:n:s0217595909002183

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595909002183

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().