Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints

Generalized stationary points of the mathematical program with equilibrium constraints (MPEC) are studied to better describe the limit points produced by interior point methods for MPEC. A primal-dual interior-point method is then proposed, which solves a sequence of relaxed barrier problems derived from MPEC. Global convergence results are deduced under fairly general conditions other than strict complementarity or the linear independence constraint qualification for MPEC (MPEC-LICQ). It is shown that every limit point of the generated sequence is a strong stationary point of MPEC if the penalty parameter of the merit function is bounded. Otherwise, a point with certain stationarity can be obtained. Preliminary numerical results are reported, which include a case analyzed by Leyffer for which the penalty interior-point algorithm failed to find a stationary point.Mathematics Subject Classification (1991):90C30, 90C33, 90C55, 49M37, 65K10     

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.     

Convergence of the homotopy path for a full-Newton step infeasible interior-point method

Roos [C. Roos, A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (4) (2006) 1110-1136 (electronic)] proposed a new primal-dual infeasible interior-point method for linear optimization. This new method can be viewed as a homotopy method. In this work, we show that the homotopy path has precisely one accumulation point in the optimal set. Moreover, this accumulation point is the analytic center of a subset of the optimal set and depends on the starting point of the infeasible interior-point method.     

Q-superlinear convergence of the iterates in primal-dual interior-point methods

Sufficient conditions are given for the Q-superlinear convergence of the iterates produced by primal-dual interior-point methods for linear complementarity problems. It is shown that those conditions are satisfied by several well known interior-point methods. In particular it is shown that the iteration sequences produced by the simplified predictor–corrector method of Gonzaga and Tapia, the simplified largest step method of Gonzaga and Bonnans, the LPF+ algorithm of Wright, the higher order methods of Wright and Zhang, Potra and Sheng, and Stoer, Wechs and Mizuno are Q-superlinearly convergent. Received: February 9, 2000 / Accepted: February 20, 2001?Published online May 3, 2001     

New parameterized kernel functions for linear optimization

Recent studies on the kernel function-based primal-dual interior-point algorithms indicate that a kernel function not only represents a measure of the distance between the iteration and the central path, but also plays a critical role in improving the computational complexity of an interior-point algorithm. In this paper, we propose a new class of parameterized kernel functions for the development of primal-dual interior-point algorithms for solving linear programming problems. The properties of the proposed kernel functions and corresponding parameters are investigated. The results lead to a complexity bounds of ${O\left(\sqrt{n}\,{\rm log}\,n\,{\rm log}\,\frac{n}{\epsilon}\right)}$ for the large-update primal-dual interior point methods. To the best of our knowledge, this is the best known bound achieved.     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

A wide neighborhood interior-point algorithm for linear optimization based on a specific kernel function

This paper presents an interior point algorithm for solving linear optimization problems in a wide neighborhood of the central path introduced by Ai and Zhang (SIAM J Optim 16:400–417, 2005). In each iteration, the algorithm computes the new search directions by using a specific kernel function. The convergence of the algorithm is shown and it is proved that the algorithm has the same iteration bound as the best short-step algorithms. We demonstrate the computational efficiency of the proposed algorithm by testing some Netlib problems in standard form. To best our knowledge, this is the first wide neighborhood path-following interior-point method with the same complexity as the best small neighborhood path-following interior-point methods that uses the kernel function.

     

Combining search directions using gradient flows

 The efficient combination of directions is a significant problem in line search methods that either use negative curvature, or wish to include additional information such as the gradient or different approximations to the Newton direction. In this paper we describe a new procedure to combine several of these directions within an interior-point primal-dual algorithm. Basically, we combine in an efficient manner a modified Newton direction with the gradient of a merit function and a direction of negative curvature, if it exists. We also show that the procedure is well-defined, and it has reasonable theoretical properties regarding the rate of convergence of the method. We also present numerical results from an implementation of the proposed algorithm on a set of small test problems from the CUTE collection. Received: November 2000 / Accepted: October 2002 Published online: February 14, 2003 Key Words. negative curvature – primal-dual methods – interior-point methods – nonconvex optimization – line searches Mathematics Subject Classification (1991): 49M37, 65K05, 90C30     

Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs

An example of an SDP (semidefinite program) exhibits a substantial difficulty in proving the superlinear convergence of a direct extension of the Mizuno—Todd—Ye type predictor—corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to force the generated sequence to converge to a solution tangentially to the central path (or trajectory). A Mizuno—Todd—Ye type predictor—corrector infeasible-interior-point algorithm incorporating this additional restriction for monotone SDLCPs (semidefinite linear complementarity problems) enjoys superlinear convergence under strict complementarity and nondegeneracy conditions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Quadratic Convergence of a Long-Step Interior-Point Method for Nonlinear Monotone Variational Inequality Problems

This paper offers an analysis on a standard long-step primal-dual interior-point method for nonlinear monotone variational inequality problems. The method has polynomial-time complexity and its q-order of convergence is two. The results are proved under mild assumptions. In particular, new conditions on the invariance of the rank and range space of certain matrices are employed, rather than restrictive assumptions like nondegeneracy.     

A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm

Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm²)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported.     

Primal-Dual Path-Following Methods and the Trust-Region Updating Strategy for Linear Programming with Noisy Data

In this article, we consider the primal-dual path-following method and the trust-region updating strategy for the standard linear programming problem. For the rank-deficient problem with the small noisy data, we also give the preprocessing method based on the QR decomposition with column pivoting. Then, we prove the global convergence of the new method when the initial point is strictly primal-dual feasible. Finally, for some rank-deficient problems with or without the small noisy data from the NETLIB collection, we compare it with other two popular interior-point methods, i.e. the subroutine pathfollow.m and the built-in subroutine linprog.m of the MATLAB environment. Numerical results show that the new method is more robust than the other two methods for the rank-deficient problem with the small noise data.     

On the convergence of primal-dual interior-point methods with wide neighborhoods

We study primal-dual interior-point methods for linear programs. After proposing a new primaldual potential function we describe a new potential reduction algorithm. We make connections between the new potential function and primal-dual interior-point algorithms with wide neighborhoods. Then we describe an algorithm that is a slightly modified version of existing primal-dual algorithms using wide neighborhoods. Assuming the optimal solution is non-degenerate, the algorithm is 1-step Q-quadratically convergent. We also study the degenerate case and show that the neighborhoods of the central path stay large as the iterates approach the optimal solutions.Research performed while the author was a Ph.D. student at Cornell University and was supported in part by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027 and also by NSF, AFOSR and ONR through NSF Grant DMS-8920550.     

一类线性与框式约束凸规划问题的原始-对偶内点算法

本文对一类具有线性和框式约束的凸规划问题给出了一个原始-对偶内点算法, 该算法可在任一原始-对偶可行内点启动, 并且全局收敛,当初始点靠近中心路径时, 算法成为中心路径跟踪算法。 数值实验表明, 算法对求解大型的这类问题是有效的。     

A primal-dual interior-point algorithm for quadratic programming

In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001).     

Dynamic updates of the barrier parameter in primal-dual methods for nonlinear programming

We introduce a framework in which updating rules for the barrier parameter in primal-dual interior-point methods become dynamic. The original primal-dual system is augmented to incorporate explicitly an updating function. A Newton step for the augmented system gives a primal-dual Newton step and also a step in the barrier parameter. Based on local information and a line search, the decrease of the barrier parameter is automatically adjusted. We analyze local convergence properties, report numerical experiments on a standard collection of nonlinear problems and compare our results to a state-of-the-art interior-point implementation. In many instances, the adaptive algorithm reduces the number of iterations and of function evaluations. Its design guarantees a better fit between the magnitudes of the primal-dual residual and of the barrier parameter along the iterations.     

A primal-dual interior-point method for linear programming based on a weighted barrier function

One motivation for the standard primal-dual direction used in interior-point methods is that it can be obtained by solving a least-squares problem. In this paper, we propose a primal-dual interior-point method derived through a modified least-squares problem. The direction used is equivalent to the Newton direction for a weighted barrier function method with the weights determined by the current primal-dual iterate. We demonstrate that the Newton direction for the usual, unweighted barrier function method can be derived through a weighted modified least-squares problem. The algorithm requires a polynomial number of iterations. It enjoys quadratic convergence if the optimal vertex is nondegenerate.The research of the second author was supported in part by ONR Grants N00014-90-J-1714 and N00014-94-1-0391.     

Superlinear primal-dual affine scaling algorithms for LCP

We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.Corresponding author. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

A globally convergent primal-dual interior-point filter method for nonlinear programming

In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of merit functions and the updating of penalty parameters.The new algorithm decomposes the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, whose sizes are controlled by a trust-region type parameter. Each entry in the filter is a pair of coordinates: one resulting from feasibility and centrality, and associated with the normal step; the other resulting from optimality (complementarity and duality), and related with the tangential step.Global convergence to first-order critical points is proved for the new primal-dual interior-point filter algorithm.Mathematics Subject Classification (1991): 65K05, 90C06, 90C29, 90C30Support for this author was provided by CRPC grant CCR–9120008.Support for this author was provided by CRPC grant CCR–9120008.Support for this author was provided by Centro de Matemática da Universidade de Coimbra, by FCT under grant POCTI/35059/MAT/2000, by the European Union under grant IST-2000-26063, and by Fundaç\ ao Calouste Gulbenkian. The author would also like to thank the IBM T.J. Watson Research Center and the Institute for Mathematics and Its Applications for their local support.