Search

In this paper we present a new iteration-complexity bound for the Mizuno--Todd--Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program min {cTχ: Aχ = b, &chi ≥ 0 } with decision variable ..., we show that the MTY P-C algorithm, started from a well-centered interior-feasible solution with duality gap nμ0 finds an interior-feasible solution with duality gap less than nn in O (T(μ0/η)+n3.5 log (Χ*A)) iterations, where T(t ) =min {n² log (log t), log t} for all t>0 and Χ*A is a scaling invariant condition number associated with the matrix A. More specifically,Χ*A is the infimum of all the conditions numbers XAD, where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O (n3.5 LA + min {n² log L, L}) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where LA and L are the input sizes of the matrix A and the data (A,b,c ), respectively. This contrasts well with the classical iteration-complexity bound for the MTY P-C algorithm, which depends linearly on L instead of log L. [ABSTRACT FROM AUTHOR]

In this paper, by means of the concept of the working set, which is an estimate of the active set, we propose a feasible sequential linear equation algorithm for solving inequality constrained optimization problems. At each iteration of the proposed algorithm, we first solve one system of linear equations with a coefficient matrix of size m x m (where m is the number of constraints) to compute the working set; we then solve a subproblem which consists of four reduced systems of linear equations with a common coefficient matrix. Unlike existing QP-free algorithms, the subproblem is concerned with only the constraints corresponding to the working set. The constraints not in the working set are neglected. Consequently, the dimension of each subproblem is not of full dimension. Without assuming the isolatedness of the stationary points, we prove that every accumulation point of the sequence generated by the proposed algorithm is a KKT point, of the problem. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. In other words, after finitely many steps, only those constraints which are active at the solution will be involved in the subproblem. Under some additional conditions, we show that the convergence rate is two-step superlinear or even Q-superlinear. We also report some preliminary numerical experiments to show that the proposed algorithm is practicable and effective for the test problems. [ABSTRACT FROM AUTHOR]

In this paper we present a. variant of Vavasis and Ye's layered step path following primal-dual interior-point algorithm for linear programming. Our algorithm is a predictor corrector-type algorithm which uses from time to time the layered least squares (LLS) direction it, place of the affine scaling (AS) direction. It, has the same iteration-complexity bound of Vavasis and Ye's algorithm, namely O(n[sup3.5] log(XA + n)), where n is the number of normegative variables and XA is a certain condition number associated with the constraint matrix A. Vavasis and Ye's algorithm requires explicit knowledge of XA (which is very hard to compute or even estimate) in order to compute the layers for the LLS direction. It, contrast, our algorithm uses the AS direction at the current iterate to determine the layers for the LLS direction, and hence does not require the knowledge of XA. A variant with similar properties and with the same complexity has been developed by Megiddo, Mizuno, and Tsuchiya [Math. Programming, 82 (1998), pp. 339-355]. However, their algorithm needs to compute n LLS directions on every iteration, while ours computes at most one LLS direction on any given iteration. [ABSTRACT FROM AUTHOR]