Modified predictor-corrector algorithm for locating weighted centers in linear programming

In certain applications of linear programming, the determination of a particular solution, the weighted center of the solution set, is often desired, giving rise to the need for algorithms capable of locating such center. In this paper, we modify the Mizuno-Todd-Ye predictor-corrector algorithm so that the modified algorithm is guaranteed to converge to the weighted center for given weights. The key idea is to ensure that iterates remain in a sequence of shrinking neighborhoods of the weighted central path. The modified algorithm also possesses polynomiality and superlinear convergence.The work of the first author was supported in part by NSF Grant DMS-91-02761 and DOE Contract DE-FG05-91-ER25100.The work of the second author was supported in part by NSF Cooperative Agreement CCR-88-09615.     

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 convergence of the iteration sequence in primal-dual interior-point methods

Recently, numerous research efforts, most of them concerned with superlinear convergence of the duality gap sequence to zero in the Kojima—Mizuno—Yoshise primal-dual interior-point method for linear programming, have as a primary assumption the convergence of the iteration sequence. Yet, except for the case of nondegeneracy (uniqueness of solution), the convergence of the iteration sequence has been an important open question now for some time. In this work we demonstrate that for general problems, under slightly stronger assumptions than those needed for superlinear convergence of the duality gap sequence (except of course the assumption that the iteration sequence converges), the iteration sequence converges. Hence, we have not only established convergence of the iteration sequence for an important class of problems, but have demonstrated that the assumption that the iteration sequence converges is redundant in many of the above mentioned works.This research was supported in part by NSF Coop. Agr. No. CCR-8809615. A part of this research was performed in June, 1991 while the second and the third authors were at Rice University as visiting members of the Center for Research in Parallel Computation.Corresponding author. Research supported in part by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Research supported in part by NSF DMS-9102761 and DOE DE-FG05-91ER25100.Research supported in part by NSF DDM-8922636.     

On the formulation and theory of the Newton interior-point method for nonlinear programming

In this work, we first study in detail the formulation of the primal-dual interior-point method for linear programming. We show that, contrary to popular belief, it cannot be viewed as a damped Newton method applied to the Karush-Kuhn-Tucker conditions for the logarithmic barrier function problem. Next, we extend the formulation to general nonlinear programming, and then validate this extension by demonstrating that this algorithm can be implemented so that it is locally and Q-quadratically convergent under only the standard Newton method assumptions. We also establish a global convergence theory for this algorithm and include promising numerical experimentation.The first two authors were supported in part by NSF Cooperative Agreement No. CCR-8809615, by Grants AFOSR 89-0363, DOE DEFG05-86ER25017, ARO 9DAAL03-90-G-0093, and the REDI Foundation. The fourth author was supported in part by NSF DMS-9102761 and DOE DE-FG02-93ER25171. The authors would like to thank Sandra Santos for painstakingly proofreading an earlier verion of this paper.     

On polynomiality of the Mehrotra-type predictor—corrector interior-point algorithms

Recently, Mehrotra [3] proposed a predictor—corrector primal—dual interior-point algorithm for linear programming. At each iteration, this algorithm utilizes a combination of three search directions: the predictor, the corrector and the centering directions, and requires only one matrix factorization. At present, Mehrotra's algorithmic framework is widely regarded as the most practically efficient one and has been implemented in the highly successful interior-point code OB1 [2]. In this paper, we study the theoretical convergence properties of Mehrotra's interior-point algorithmic framework. For generality, we carry out our analysis on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under the monotonicity assumption, we establish polynomial complexity bounds for two variants of the Mehrotra-type predictor—corrector interior-point algorithms. These results are summarized in the last section in a table.Research supported in part by NSF DMS-9102761, DOE DE-FG05-91ER25100 and DOE DE-FG02-93ER25171.Corresponding author.     

On the convergence rate of Newton interior-point methods in the absence of strict complementarity

In the absence of strict complementarity, Monteiro and Wright [7] proved that the convergence rate for a class of Newton interior-point methods for linear complementarity problems is at best linear. They also established an upper bound of 1/4 for the Q ₁-factor of the duality gap sequence when the steplengths converge to one. In the current paper, we prove that the Q ₁ factor of the duality gap sequence is exactly 1/4. In addition, the convergence of the Tapia indicators is also discussed.This author was supported in part by NSF Coop. Agr. No. CCR-8809615 and AFOSR 89-0363 and the REDI Foundation.This author was supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Visiting member of the Center for Research on Parallel Computations, Rice University, Houston, Texas, 77251-1892. This author was supported in part by DOE DE-FG02-93ER25171.     

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.     

Enhancing energy conserving methods

Recent observations [5] indicate that energy-momentum methods might be better suited for the numerical integration of highly oscillatory Hamiltonian systems than implicit symplectic methods. However, the popular energy-momentum method, suggested in [3], achieves conservation of energy by a global scaling of the force field. This leads to an undesirable coupling of all degrees of freedom that is not present in the original problem formulation. We suggest enhancing this energy-momentum method by splitting the force field and using separate adjustment factors for each force. In case that the potential energy function can be split into a strong and a weak part, we also show how to combine an energy conserving discretization of the strong forces with a symplectic discretization of the weak contributions. We demonstrate the numerical properties of our method by simulating particles that interact through Lennard-Jones potentials and by integrating the Sine-Gordon equation.This work was partly supported by NIH Grant P41RR05969, DOE/NSF Grant DE-FG02-91-ER25099/DMS-9304268, and NSF GCAG/HPCC ASC-9318159.     

Interior-point ℓ 2-penalty methods for nonlinear programming with strong global convergence properties

We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an ℓ₂-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush-Kuhn-Tucker (KKT) point of the barrier subproblem, or a Fritz-John (FJ) point of the original problem that fails to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ); if the penalty parameter tends to infinity, there is a limit point that is either an infeasible FJ point of the inequality constrained feasibility problem (an infeasible stationary point of the infeasibility measure if slack variables are added) or a FJ point of the original problem at which the MFCQ fails to hold. Numerical results are given that illustrate these outcomes. Research supported by the Presidential Fellowship of Columbia University. Research supported in part by NSF Grant DMS 01-04282, DOE Grant DE-FG02-92EQ25126 and DNR Grant N00014-03-0514.     

Current inverse iteration software can fail

Inverse iteration is widley used to compute the eigenvectors of a matrix once accurate eigenvalues are known. We discuss various issues involved in any implementation of inverse iteration for real, symmetric matrices. Current implementations resort to reorthogonalization when eigenvalues agree to more than three digits relative to the norm. Such reorthogonalization can have unexpected consequences. Indeed, as we show in this paper, the implementations in EISPACK and LAPACK may fail. We illustrate with both theoretical and empirical failures. This research was supported, while the author was at the University of California, Berkeley, in part by DARPA Contract No. DAAL03-91-C-0047 through a subcontract with the University of Tennessee, DOE Contract No. DOE-W-31-109-Eng-38 through a subcontract with Argonne National Laboratory, by DOE Grant No. DE-FG03-94ER25219, NSF Grant Nos. ASC-9313958 and CDA-9401156, and DOE Contract DE-AC06-76RLO 1830 through the Environmental Molecular Sciences construction project at Pacific Northwest National Laboraotry (PNNL).     

Motion of level sets by mean curvature III

We continue our investigation [6,7] (see also [4], etc.) of the generalized motion of sets via mean curvature by the level set method. We study more carefully the fine properties of the mean curvature PDE, to obtain Hausdorff measure estimates of level sets and smoothness whenever the level sets are graphs. L. C. E. was supported in part by NSF Grant DMS-86-01532. J. S. was supported in part by NSF Grant DMS-88-02858 and DOE Grant DE-FG02-86ER25015.     

Superlinear convergence of infeasible-interior-point methods for linear programming

At present the interior-point methods of choice are primal—dual infeasible-interior-point methods, where the iterates are kept positive, but allowed to be infeasible. In practice, these methods have demonstrated superior computational performance. From a theoretical point of view, however, they have not been as thoroughly studied as their counterparts — feasible-interior-point methods, where the iterates are required to be strictly feasible. Recently, Kojima et al., Zhang, Mizuno and Potra studied the global convergence of algorithms in the primal—dual infeasible-interior-point framework. In this paper, we continue to study this framework, and in particular we study the local convergence properties of algorithms in this framework. We construct parameter selections that lead toQ-superlinear convergence for a merit function andR-superlinear convergence for the iteration sequence, both at rate 1 + where can be arbitrarily close to one.Research supported in part by NSF DMS-9102761 and DOE DE-FG05-91ER25100.Corresponding author.     

Chapter 6 On the construction of strong complementarity slackness solutions for DEA linear programming problems using a primal-dual interior-point method

A novel approach for solving the DEA linear programming problems using a primaldual interior-point method is presented. The solution found by this method satisfies the Strong Complementarity Slackness Condition (SCSC) and maximizes the product of the positive components among all SCSC solutions. The first property is critical in the use of DEA and the second one contributes significantly to the reliability of the solution.This research was partially supported by NSF Cooperative Agreement No. CCR-88-09615, ARO Grant 9DAAL03-90-G-0093, DOE Grant DEFG05-86-ER25017, and AFOSR Grant 89-0363.Partially supported by Fulbright/LASPAU.     

A model trust-region modification of Newton's method for nonlinear two-point boundary-value problems

The method of quasilinearization for nonlinear two-point boundary-value problems is Newton's method for a nonlinear differential operator equation. A model trust-region approach to globalizing the quasilinearization algorithm is presented. A double-dogleg implementation yields a globally convergent algorithm that is robust in solving difficult problems.This work was supported in part by DOE Contract DE-AS05-82-ER13016 and NSF Grant RII-89-17691 and was part of the author's doctoral thesis at Rice University. It is a pleasure to thank the author's thesis advisors, Professor J. E. Dennis, Jr., and Professor R. A. Tapia.     

Cubically convergent method for locating a nearby vertex in linear programming

Given a point sufficiently close to a nondegenerate basic feasible solutionx* of a linear program, we show how to generate a sequence {p ^k} that converges to the 0–1 vector sign(x*) at aQ-cubic rate. This extremely fast convergence enables us to determine, with a high degree of certainty, which variables will be zero and which will be nonzero at optimality and then constructx* from this information.This research was supported in part by NSF Cooperative Agreement No. CCR-8809615, by AFOSR Grant No. 89-0363, and by DOE Grant No. DEFG05-86ER 25017. The authors would like to thank Bob Bixby for helpful discussions.     

A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming

Cholesky factorization has become the method of choice for solving the symmetric system of linear equations arising in interior point methods (IPMs) for linear programming (LP), its main advantages being numerical stability and efficiency for sparse systems. However in the presence of dense columns there is dramatic loss of efficiency. A typical approach to remedy this problem is to apply the Sherman-Morrison-Woodbury (SMW) update formula to the dense part. This approach while being very efficient, is not numerically stable. Here we propose using product-form Cholesky factorization to handle dense columns. The proposed approach is essentially as stable as the original Cholesky factorization and nearly as efficient as the SMW approach. We demonstrate these properties both theoretically and computationally. A key part of our theoretical analysis is the proof that the elements of the Cholesky factors of the matrices that arise in IPMs for LP are uniformly bounded as the duality gap converges to zero.The doctoral research of this author was supported in part by an IBM Cooperative FellowshipResearch supported in part by NSF Grants DMS 91-06195, DMS 94-14438, DMS 95-27124, DMS 01-04282 and CDA 97-26385 and DOE Grant DE-FG02-92ER25126     

Primal-dual interior point approach for computingl 1-solutions andl ∞-solutions of overdetermined linear systems

This paper concerns solving an overdetermined linear systemA ^T x=b in the leastl ₁-norm orl -norm sense, whereA ^m×n ,m<n. We show that the primal-dual interior point approach for linear programming can be applied, in an effective manner, to linear programming versions of thel ₁ andl -problems. The resulting algorithms are simple to implement and can attain quadratic or superlinear convergence rate. At each iteration, the algorithms must solve a linear system with anm×m positive-definite coefficient matrix of the formADA ^T , whereD is a positive diagonal matrix. The preliminary numerical results indicate that the proposed algorithms offer considerable promise.This research was supported in part by Grants NSF DMS-91-02761 and DOE DE-FG05-91-ER25100.     

A bundle-Newton method for nonsmooth unconstrained minimization

An algorithm based on a combination of the polyhedral and quadratic approximation is given for finding stationary points for unconstrained minimization problems with locally Lips-chitz problem functions that are not necessarily convex or differentiable. Global convergence of the algorithm is established. Under additional assumptions, it is shown that the algorithm generates Newton iterations and that the convergence is superlinear. Some encouraging numerical experience is reported. This work was supported by the grant No. 201/96/0918 given by the Czech Republic Grant Agency.     

Interior-Point Gradient Method for Large-Scale Totally Nonnegative Least Squares Problems

We study an interior-point gradient method for solving a class of so-called totally nonnegative least-squares problems. At each iteration, the method decreases the residual norm along a diagonally-scaled negative gradient direction with a special scaling. We establish the global convergence of the method and present some numerical examples to compare the proposed method with a few similar methods including the affine scaling method.This author was supported in part by DOE/LANL Contract 03891-99-23This author was supported in part by NSF Grant DMS-0442065     

On motivating the Mitchell-Todd modification of Karmarkar's algorithm for LP problems with free variables

In this note, we first observe that the Morshedi-Tapia interpretation of the Karmarkar algorithm naturally offers an extension of the Karmarkar subproblem scaling to problems with free variables. We then note that this extended scaling is precisely the scaling suggested by Mitchell and Todd for problems with free variables. Mitchell and Todd gave no motivation for or justification of this extended scaling.This research was sponsored by NSF Cooperative Agreement No. CCR-88-09615, AFOSR Grant 89-0363, DOE Grant DEFG05-86-ER25017, ARO Grant 9DAAL03-90-G-0093, and COLCIENCIAS CO: 1106-05-307-93.