Study On Complexity Of Some Interior-Point Algorithms In Conic Programming

In interior-point methods(IPMs), there has been an inconsistency between theory and practice:fast algorithms in practice may actually render worse iteration complexity bounds. This dissertation focuses on the efficient interior-point algorithms for solving conic programming problems, including linear programming(LP), semidefinite program-ming(SDP) and symmetric conic programming(SCP).We first propose two new Mehrotra-type predictor-corrector interior-point algo-rithm for LP using two wide neighborhoods of the central path. Both neighborhoods are related to the minus infinity neighborhood. At each iteration, the algorithms com-pute a corrector direction in addition to the classical direction, in an attempt to improve performance. We prove O(√nL) iteration complexity of the algorithms, where n is the number of variables and L is the input data length. This is the first Mehrotra-type predictor-corrector algorithm enjoyed the low iteration bound of O(√nL), the same as the best known complexity results for IPMs. The numerical experiences show that the algorithms have a superior practical performance. Subsequently, we extend one of the Mehrotra-type predictor-corrector algorithms from LP to SDP. The polynomial com-plexity is established for the algorithm using the Nesterov-Todd (NT) direction, which is analogous to the case of LP.Then, we research into the safeguard based Mehrotra-type predictor-corrector algo-rithms for LP. This algorithm incorporates a safeguard in Mehrotra’s original predictor-corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. We point out a mistake in the proof of the key lemma in Koulaei and Terlaky, which extend the safeguard based algorithm to SDP. We modify the maximum step size slightly in the predictor step and propose a new Mehrotra-type predictor-corrector algorithm for SDP. However, in the case of LP, the new predictor step size is still identical with that used by Koulaei and Terlaky. Based on the NT direction, we prove O(nL) iteration complexity of the new algorithm. Fur-thermore, using the machinery of Euclidean Jordan algebras, we further extend the modified algorithm to symmetric cones, which include the nonnegative orthant, the positive semidefinite cone and second-order cone as special cases. It is proved for the NT direction that the algorithm stops after at most O(r logε-1) iteration, where r is the rank of the Jordan algebras and ε is the precision parameter. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter, and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. Our numerical results also provide us an encouraging evidence that our new algorithms may also perform well in practice. Moreover, we present an extension of the second-order Mehrotra-type predictor-corrector algorithm proposed by Salahi and Mahdavi-Amiri for LP to SCP. In our algorithm the safeguard strategy is not necessarily used when the affine scaling step performs poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We extend the new algorithm to symmetric cones and show that, based on the NT direction, the complexity bounds of the algorithm coincide with the case of LP. We also present a new variant of infeasible second-order Mehrotra-type algorithm for SCP. Based on the NT direction, the complexity bounds of the algorithm is O(r2logε-1). If the staring point is feasible, the complexity bound is reduced to O(r logε-1).Finally, we establish polynomial convergence of a new primal-dual infeasible-interior-point algorithm for SCP using wide neighborhood of the central path. The convergence is shown for the "commutative class" of search directions. In particular, the complexity bound is O(r1.5logε-1) for the NT direction, and O(r2logε-1) for the xs and sx directions. If the staring point is feasible, the complexity bound is O(√rlogε-1) for the NT direction, and O(r logε-1) for the xs and sx directions. When the NT search direction is used, we get the first wide neighborhood interior-point algorithm with the same complexity as small neighborhood IPMs over symmetric cones.