On quadratic andO\left( {\sqrt {nL} } \right) convergence of a predictor—corrector algorithm for LCP

Recently several new results have been developed for the asymptotic (local) convergence of polynomial-time interior-point algorithms. It has been shown that the predictor—corrector algorithm for linear programming (LP) exhibits asymptotic quadratic convergence of the primal—dual gap to zero, without any assumptions concerning nondegeneracy, or the convergence of the iteration sequence. In this paper we prove a similar result for the monotone linear complementarity problem (LCP), assuming only that a strictly complementary solution exists. We also show by example that the existence of a strictly complementarity solution appears to be necessary to achieve superlinear convergence for the algorithm.Research supported in part by NSF Grants DDM-8922636 and DDM-9207347, and an Interdisciplinary Research Grant of the University of Iowa, Iowa Center for Advanced Studies.     

A simplified homogeneous and self-dual linear programming algorithm and its implementation

We present a simplification and generalization of the recent homogeneous and self-dual linear programming (LP) algorithm. The algorithm does not use any Big-M initial point and achieves -iteration complexity, wheren andL are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, our code solves NETLIB problems, feasible or infeasible, starting simply fromx=e (primal variables),y=0 (dual variables),z=e (dual slack variables), wheree is the vector of all ones. We describe our computational experience in solving these problems, and compare our results with OB1.60, a state-of-the-art implementation of interior-point algorithms.Research supported in part by NSF Grant DDM-9207347 and by an Iowa College of Business Administration Summer Grant.Part of this work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, USA, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Convergence behavior of interior-point algorithms

We show that most interior-point algorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. These algorithms include all path-following algorithms and some potential reduction algorithms. The result also holds for the monotone complementarity problem if a strict complementarity solution exists. In general, the limit point is a solution that maximizes the number of its nonzero components among all solutions.Research supported in part by NSF Grant DDM-8922636, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.     

A quadratically convergent O(\sqrt n L)-iteration algorithm for linear programming

Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.Supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.Supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Supported in part by NSF Grant DMS-9102761 and DOE Grant DE-FG05-91ER25100.     

On the finite convergence of interior-point algorithms for linear programming

It has been shown [8] that numerous interior-point algorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. In this note we further establish a theoretical base for Gay's test (Gay, 1989) to identify the optimal face, and develop a new termination procedure to obtain an exact solution on the optimal face. We also report some numerical results for solving a set of LP test problems, each of which has a highly degenerate and unbounded optimal face.Research supported in part by NSF Grant DDM-8922636, The Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.     

A lower bound on the number of iterations of long-step primal-dual linear programming algorithms

Recently, Todd has analyzed in detail the primal-dual affine-scaling method for linear programming, which is close to what is implemented in practice, and proved that it may take at leastn ^1/3 iterations to improve the initial duality gap by a constant factor. He also showed that this lower bound holds for some polynomial variants of primal-dual interior-point methods, which restrict all iterates to certain neighborhoods of the central path. In this paper, we further extend his result to long-step primal-dual variants that restrict the iterates to a wider neighborhood. This neigh-borhood seems the least restrictive one to guarantee polynomiality for primal-dual path-following methods, and the variants are also even closer to what is implemented in practice.Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550.This author is supported in part by NSF Grant DDM-9207347. Part of thiw work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002 RID="†" ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.     

Fast convergence of the simplified largest step path following algorithm

Each master iteration of a simplified Newton algorithm for solving a system of equations starts by computing the Jacobian matrix and then uses this matrix in the computation ofp Newton steps: the first of these steps is exact, and the other are called “simplified”. In this paper we apply this approach to a large step path following algorithm for monotone linear complementarity problems. The resulting method generates sequences of objective values (duality gaps) that converge to zero with Q-orderp+1 in the number of master iterations, and with a complexity of iterations. Corresponding author. Research done while visiting the Delft Technical University, and supported in part by CAPES — Brazil.     

Linear liftings for non-complete probability spaces

We show that it is consistent with ZFC thatL ^∞(Y,B,ν) has no linear lifting for many non-complete probability spaces (Y,B,ν), in particular forY=[0,1]^A,B=Borel subsets ofY, ν=usual Radon measure onB. Research supported by UPEI Senate Grant no 602101, by the Research Institute for Mathematical Sciences at Bar-Ilan University, and by the Landau Center for Mathematical Research in Analysis (supported by the Minerva Foundation). The author would like to thank the organizers of the Winter Institute on the Set Theory of the Reals for their hospitality while part of this research was being carried out. Partially supported by the Foundation for Basic Research of the Israel Academy of Science. Publication number 437.     

Newton-KKT interior-point methods for indefinite quadratic programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a “primal” affine-scaling algorithm (à la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285–300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a “barrier” version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems suggest that the proposed algorithms may be of great practical interest. The work of the first author was supported in part by the School of Computational Science of Florida State University through a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110–1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p∈[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/ε). This work was supported in part by the National Natural Science Foundation of China under Grant No. 10871098.     

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.     

On Central-Path Proximity Measures in Interior-Point Methods

One of the main ingredients of interior-point methods is the generation of iterates in a neighborhood of the central path. Measuring how close the iterates are to the central path is an important aspect of such methods and it is accomplished by using proximity measure functions. In this paper, we propose a unified presentation of the proximity measures and a study of their relationships and computational role when using a generic primal-dual interior-point method for computing the analytic center for a standard linear optimization problem. We demonstrate that the choice of the proximity measure can affect greatly the performance of the method. It is shown that we may be able to choose the algorithmic parameters and the central-path neighborhood radius (size) in such a way to obtain comparable results for several measures. We discuss briefly how to relate some of these results to nonlinear programming problems. The first author was partially supported by Simón Bolívar University, Venezuelan National Council for Sciences and Technology (CONICIT) Grant PG97-000592, Center for Research on Parallel Computing of Rice University, and TU Delft. The authors thank Amr El Bakry, Richard Tapia, Adolfo Quiroz, and Pedro Berrizbeitia for discussions and suggestions. They acknowledge the observations and comments of the editors and an anonymous referee.     

A globally convergent approximately active search algorithm for solving mathematical programs with linear complementarity constraints

Summary. In this paper, we propose a new algorithm for solving mathematical programs with linear complementarity constraints. The algorithm uses a method of approximately active search and introduces the idea of acceptable descent face. The main advantage of the new algorithm is that it is globally convergent without requiring strong assumptions such as nondegeneracy or linear independence condition. Numerical results are presented to show the effectiveness of the algorithm.Mathematics Subject Classification (2000): 90C30, 90C33, 65K05This research is partially supported by City University of Hong Kong under its Strategic Research Grant #7001339 and the National Natural Science Foundation of China grant # 10171108 and # 70271014     

The curvature integral and the complexity of linear complementarity problems

In this paper, we propose a predictor—corrector-type algorithm for solving the linear complementarity problem (LCP), and prove that the actual number of iterations needed by the algorithm is bounded from above and from below by a curvature integral along the central trajectory of the problem. This curvature integral is not greater than, and possibly smaller than, the best upper bound obtained in the literature to date.Corresponding author.This author's research was partially supported by Research Grant No. RP920068, National University of Singapore, Singapore.     

A New Path-Following Algorithm for Nonlinear P*Complementarity Problems

Based on the recent theoretical results of Zhao and Li [Math. Oper. Res., 26 (2001), pp. 119—146], we present in this paper a new path-following method for nonlinear P* complementarity problems. Different from most existing interior-point algorithms that are based on the central path, this algorithm tracks the “regularized central path” which exists for any continuous P* problem. It turns out that the algorithm is globally convergent for any P* problem provided that its solution set is nonempty. By different choices of the parameters in the algorithm, the iterative sequence can approach to different types of points of the solution set. Moreover, local superlinear convergence of this algorithm can also be achieved under certain conditions. The research of the first author was supported by The National Natural Science Foundation of China under Grant No. 10201032 and Grant No. 70221001. The research of the second author was supported by Grant CUHK4214/01E, Research Grants Council, Hong Kong. An erratum to this article is available at .     

Sub-quadratic convergence of a smoothing Newton algorithm for the <Emphasis Type="Italic">P</Emphasis><Subscript><Emphasis Type="Italic">0</Emphasis></Subscript>– and monotone LCP

Given , the linear complementarity problem (LCP) is to find such that (x, s) 0,s=Mx+q,x^Ts=0. By using the Chen-Harker-Kanzow-Smale (CHKS) smoothing function, the LCP is reformulated as a system of parameterized smooth-nonsmooth equations. As a result, a smoothing Newton algorithm, which is a modified version of the Qi-Sun-Zhou algorithm [Mathematical Programming, Vol. 87, 2000, pp. 1–35], is proposed to solve the LCP with M being assumed to be a P₀-matrix (P₀–LCP). The proposed algorithm needs only to solve one system of linear equations and to do one line search at each iteration. It is proved in this paper that the proposed algorithm has the following convergence properties: (i) it is well-defined and any accumulation point of the iteration sequence is a solution of the P₀–LCP; (ii) it generates a bounded sequence if the P₀–LCP has a nonempty and bounded solution set; (iii) if an accumulation point of the iteration sequence satisfies a nonsingularity condition, which implies the P₀–LCP has a unique solution, then the whole iteration sequence converges to this accumulation point sub-quadratically with a Q-rate 2–t, where t(0,1) is a parameter; and (iv) if M is positive semidefinite and an accumulation point of the iteration sequence satisfies a strict complementarity condition, then the whole sequence converges to the accumulation point quadratically.This authors work is supported by the Hong Kong Research Grant Council and the Australian Research Council.This authors work is supported by Grant R146-000-035-101 of National University of Singapore.Mathematics Subject Classification (1991): 90C33, 65K10     

A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties

In this paper, we construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system. The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge, such properties have not appeared in the existing literature for smoothing-type algorithms. This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited

Recently, Zhang, Tapia, and Dennis (Ref. 1) produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above-mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.Dedicated to the Memory of Magnus R. Hestenes, 1906–1991This research was supported in part by NSF Cooperative Agreement CCR-88-09615 and was initiated while the first author was at Rice University as a Visiting Member of the Center for Research in Parallel Computation.The authors thank Yinyu Ye for constructive comments and discussions concerning this material.This author was supported in part by NSF Grant DMS-91-02761 and DOE Grant DE-FG05-91-ER25100.This author was supported in part by AFOSR Grant 89-0363, DOE Grant DE-FG05-86-ER25017, and ARO Grant 9DAAL03-90-G-0093.     

Vertical decomposition of arrangements of hyperplanes in four dimensions

We show that, for any collection ℋ ofn hyperplanes in ℜ⁴, the combinatorial complexity of thevertical decomposition of the arrangementA(ℋ) of ℋ isO(n ⁴ logn). The proof relies on properties of superimposed convex subdivisions of 3-space, and we also derive some other results concerning them. Work on this paper by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Leonidas Guibas was also supported by National Science Foundation Grant CCR-9215219. Work by Micha Sharir was also supported by National Science Foundation Grant CCR-91-22103, and by grants from the G.I.F.—the German Isreali Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Jiří Matouŝek was done while he was visiting Tel Aviv University, and its was partially supported by a Humboldt Research Fellowship. Work on this paper by Dan Halperin was carried out while he was at Tel Aviv University.