An adaptive self-regular proximity based large-update IPM for LO.

Primal-dual interior-point methods (IPMs) have shown their power in solving large classes of optimization problems. However, there is still a discrepancy between the practical behavior of these algorithms and their theoretical worst-case complexity results with respect to the update strategies of the dua-lity gap parameter in the algorithm. Recently, this discrepancy was significantly reduced by Peng, J., Roos, C. and Terlaky, T., 2002, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms (Princeton, NJ: Princeton University Press) who introduced a new family of self-regular (SR)-proximity functions based IPMs. In this paper, based on a class of SR proximities, we propose an adaptive single-step large-update SR-IPM that is very close to what is used in the McIPM software package. At each step, our algorithm always chooses a large-update of the target value adaptively depending on the position of the current iterate. This adaptive choice of the target value is different from the one what is presented in Peng, J., Roos, C. and Terlaky, T., 2002, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms (Princeton, NJ: Princeton University Press), where the target μ value is reduced by a fix factor when the iterate is sufficiently well centered. An 𝒪( qn ( q +1)/2 q log( n /ℇ)) worst-case iteration bound of the algorithm is established, where q is the barrier degree of the SR-proximity. For q = log n , our algorithm achieves the so far best complexity for large-update IPMs. Email: salahim@math.mcmaster.ca [ABSTRACT FROM AUTHOR]