Complexity analysis of a full-Newton step interior-point method for linear optimization
- PDF / 584,366 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 66 Downloads / 187 Views
Complexity analysis of a full-Newton step interior-point method for linear optimization Zsolt Darvay1 · Ingrid-Magdolna Papp1 · Petra-Renáta Takács1
© Akadémiai Kiadó, Budapest, Hungary 2016
Abstract This paper concerns a short-update primal-dual interior-point method for linear optimization based on a new search direction. We apply a vector-valued function generated by a univariate function on the nonlinear equation of the system which defines the central path. The common way to obtain the equivalent form of the central path is using the square root function. In this paper we consider a new function formed by the difference of the identity map and the square root function. We apply Newton’s method in order to get the new directions. In spite of the fact that the analysis is more difficult in this case, we prove that the complexity of the algorithm is identical with the one of the best known methods for linear optimization. Keywords Linear optimization · Interior-point method · Full-Newton step · Search direction · Polynomial complexity Mathematics Subject Classification
90C05 · 90C51
1 Introduction The area of linear optimization (LO) has become very active since Karmarkar’s [27] first interior-point method (IPM) was published on this subject. Later on, a large amount of papers appeared and the most important results were summarized in the monographs written by Roos, Terlaky and Vial [46], Wright [57] and Ye [58]. It turned out that IPMs are more efficient in practice than pivot algorithms in the case of large sparse problems. Illés and Terlaky [26] presented a comparison between the IPMs and pivot methods from practical and theoretical point of view. Nowadays, state-of-the-art implementations of interior-point solvers are available. Lustig et al. [34,35] as well as Mehrotra [38] made important contributions
B 1
Zsolt Darvay [email protected] Faculty of Mathematics and Computer Science, Babe¸s-Bolyai University, No. 1 Mihail Kog˘alniceanu Street, 400084 Cluj-Napoca, Romania
123
Zs. Darvay et al.
to this field. Some significant aspects of implementations techniques were presented by Andersen et al. [7], by Mészáros [39] and by Gondzio and Terlaky [18], respectively. Recently, the algorithms proposed for solving LO problems have been extended to more general optimization problems such as semidefinite optimization (SDO), second-order cone optimization (SOCO), symmetric optimization (SO) and linear complementarity problems (LCPs). Nesterov and Nemirovskii [41] introduced the concept of self-concordant barrier functions in order to define IPMs for solving convex optimization problems. Klerk [30] proposed a general framework for solving SDO problems. Beside this, he studied the concept of self-dual embeddings for SDO. Alizadeh and Goldfarb [6] used Euclidean Jordan algebras in order to investigate the theory of SOCO. Schmieta and Alizadeh [47] extended the commutative class of primal-dual IPMs for SDO proposed by Monteiro and Zhang [40] to SO. Furthermore, Vieira [50] presented different IPMs for SO based o
Data Loading...
