A Class of Large-Update and Small-Update Primal-Dual Interior-Point Algorithms for Linear Optimization

Y. Q. Bai, G. Lesaja (), C. Roos, G. Q. Wang and M. El Ghami
Additional contact information
Y. Q. Bai: Shanghai University
G. Lesaja: Georgia Southern University
C. Roos: Delft University of Technology
G. Q. Wang: Shanghai University
M. El Ghami: University of Bergen

Journal of Optimization Theory and Applications, 2008, vol. 138, issue 3, No 2, 359 pages

Abstract: Abstract In this paper we present a class of polynomial primal-dual interior-point algorithms for linear optimization based on a new class of kernel functions. This class is fairly general and includes the classical logarithmic function, the prototype self-regular function, and non-self-regular kernel functions as special cases. The analysis of the algorithms in the paper follows the same line of arguments as in Bai et al. (SIAM J. Optim. 15:101–128, [2004]), where a variety of non-self-regular kernel functions were considered including the ones with linear and quadratic growth terms. However, the important case when the growth term is between linear and quadratic was not considered. The goal of this paper is to introduce such class of kernel functions and to show that the interior-point methods based on these functions have favorable complexity results. They match the currently best known iteration bounds for the prototype self-regular function with quadratic growth term, the simple non-self-regular function with linear growth term, and the classical logarithmic kernel function. In order to achieve these complexity results, several new arguments had to be used.

Keywords: Linear optimization; Interior-point methods; Primal-dual methods; Complexity; Kernel functions (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-008-9389-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joptap:v:138:y:2008:i:3:d:10.1007_s10957-008-9389-z

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-008-9389-z

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().