A new result in the theory and computation of the least-norm solution of a linear program

By perturbing properly a linear program to a separable quadratic program, it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overrelaxation) algorithms. The main result of this paper gives an effective computational criterion to check whether the solutions of the perturbed quadratic programs provide the least-norm solution of the original linear program.This research was sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based upon work supported by the National Science Foundation, Grant Nos. DCR-84-20963 and DMS-82-109050, and by the Italian National Research Council (CNR).The author wishes to thank Professor O. L. Mangasarian for his helpful comments which helped to improve the paper.     

A note on a quadratic formulation for linear complementarity problems

In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known.     

Finding a strict feasible solution of a linear semidefinite program

This study deals with the performance of projective interior point methods for linear semidefinite program. We propose a modification in the initialization phases of the method in order to reduce the computation time.This purpose is confirmed by numerical experiments showing the efficiency which are presented in the last section of the paper.     

Basic-set algorithm for a generalized linear complementarity problem

In this paper, the authors develop a new direct method for the solution of a BLCP, that is, a linear complementarity problem (LCP) with upper bounds, when its matrix is a symmetric or an unsymmetricP-matrix. The convergence of the algorithm is established by extending Murty's principal pivoting method to an LCP which is equivalent to the BLCP. Computational experience with large-scale BLCPs shows that the basic-set method can solve efficiently large-scale BLCPs with a symmetric or an unsymmetricP-matrix.     

A strictly improving linear programming Phase I algorithm

Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called basic) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs.When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.     

Generalization of Murty's direct algorithm to linear and convex quadratic programming

Murty's algorithm for the linear complementarity problem is generalized to solve the optimality conditions for linear and convex quadratic programming problems with both equality and inequality constraints. An implementation is suggested which provides both efficiency and tight error control. Numerical experiments as well as field tests in various applications show favorable results.The author thanks K. G. Murty for his encouragement and helpful comments.     

A randomized algorithm for fixed-dimensional linear programming

We give a (Las Vegas) randomized algorithm for linear programming in a fixed dimensiond for which the expected computation time is , where lim _{d d} = 0. This improves the corresponding worst-case complexity, . The method is based on a recent idea of Clarkson. Two variations on the algorithm are examined briefly.     

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.     

A linear program for the two-hub location problem

This paper considers the discrete two-hub location problem. We need to choose two hubs from a set of nodes. The remaining nodes are to be connected to one of the two hubs which act as switching points for internodal flows. A configuration which minimizes the total flow cost needs to be found. We show that the problem can be solved in polynomial time when the hub locations are fixed. Since there are at most ways to choose the hub locations, the two-hub location problem can be solved in polynomial time. We transform the quadratic 0–1 integer program of the single allocation problem in the fixed two-hub system into a linear program and show that all extreme points of the polytope defined by the LP are integral. Also, the problem can be transformed into a minimum cut problem which can be solved efficiently by any polynomial time algorithm.     

A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations

Existing global optimization techniques for nonconvex quadratic programming (QP) branch by recursively partitioning the convex feasible set and thus generate an infinite number of branch-and-bound nodes. An open question of theoretical interest is how to develop a finite branch-and-bound algorithm for nonconvex QP. One idea, which guarantees a finite number of branching decisions, is to enforce the first-order Karush-Kuhn-Tucker (KKT) conditions through branching. In addition, such an approach naturally yields linear programming (LP) relaxations at each node. However, the LP relaxations are unbounded, a fact that precludes their use. In this paper, we propose and study semidefinite programming relaxations, which are bounded and hence suitable for use with finite KKT-branching. Computational results demonstrate the practical effectiveness of the method, with a particular highlight being that only a small number of nodes are required. This author was supported in part by NSF Grants CCR-0203426 and CCF-0545514.     

A linear programming reformulation of the standard quadratic optimization problem

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note, we show that the SQO problem may be reformulated as an (exponentially sized) linear program (LP). This reformulation also suggests a hierarchy of polynomial-time solvable LP’s whose optimal values converge finitely to the optimal value of the SQO problem. The hierarchies of LP relaxations from the literature do not share this finite convergence property for SQO, and we review the relevant counterexamples.     

一个新的求解线性规划最小二乘算法

§1Introduction Currently,therearetwopopularapproachesinlinearprogramming:pivotalgorithm andinterior-pointalgorithm.Manyoftheirvariantsdevelopedbothintheoryand applicationsarestillinprogress.Thepivotmethodobtainstheoptimalsolutionviamoving consecutivelytoabettercorner-pointinthefeasibleregion,anditsmodificationstryto improvethespeedofattainingtheoptimality.Incontrast,theinterior-pointalgorithmis claimedasaninterior-pointapproach,whichgoesfromafeasiblepointtoafeasiblepoint throughtheinterioroft…     

Implementing proximal point methods for linear programming

We describe the application of proximal point methods to the linear programming problem. Two basic methods are discussed. The first, which has been investigated by Mangasarian and others, is essentially the well-known method of multipliers. This approach gives rise at each iteration to a weakly convex quadratic program which may be solved inexactly using a point-SOR technique. The second approach is based on the proximal method of multipliers, originally proposed by Rockafellar, for which the quadratic program at each iteration is strongly convex. A number of techniques are used to solve this subproblem, the most promising of which appears to be a two-metric gradient-projection approach. Convergence results are given, and some numerical experience is reported.This research was supported by National Science Foundation, Grant Nos. ASC-87-14009 and DMS-86-19903, and by Air Force Office of Scientific Research, Grant No. AFOSR-ISSA-87-0092. Part of this work was performed at Argonne National Laboratory. Computation was partly performed at the Pittsburgh Supercomputer Center under NSF Grant No. DMS-88-0033P and at the Argonne Advanced Computing Research Facility, whose support is gratefully acknowledged. The author thanks Olvi Mangasarian and Renato DeLeone for helpful discussions, and Jorge Moré for his valuable advice on the algorithms discussed in Section 3. The contributions of a referee, who provided helpful comments on an earlier version of this paper, are also acknowledged.     

Deriving an unconstrained convex program for linear programming

Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions.     

A constraint generation algorithm for large scale linear programs using multiple-points separation

In order to solve linear programs with a large number of constraints, constraint generation techniques are often used. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. In this paper, we present a separation procedure that uses several points to generate violated constraints. The complexity of this separation procedure and of some related problems is studied. Also, preliminary computational results about the advantages of using multiple-points separation procedures over traditional separation procedures are given for random linear programs and survivable network design. They illustrate that, for some specific families of linear programs, multiple-points separation can be computationally effective.     

A meta-control algorithm for generating approximate solutions to binary integer programming problems

Binary integer program problems, which are known to be difficult to solve, have long been an important research area. We use a new approach with continualization techniques to find approximate solutions to binary integer programming problems. The algorithm constructs a sequence of approximations to a solution using a meta-control approach that has low polynomial time complexity. The algorithm is illustrated with a BIP example.     

A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming

In this paper we propose a new iterative method for solving a class of linear complementarity problems:u 0,Mu + q 0, u^T(Mu + q)=0, where M is a givenl ×l positive semidefinite matrix (not necessarily symmetric) andq is a givenl-vector. The method makes two matrix-vector multiplications and a trivial projection onto the nonnegative orthant at each iteration, and the Euclidean distance of the iterates to the solution set monotonously converges to zero. The main advantages of the method presented are its simplicity, robustness, and ability to handle large problems with any start point. It is pointed out that the method may be used to solve general convex quadratic programming problems. Preliminary numerical experiments indicate that this method may be very efficient for large sparse problems.On leave from the Department of Mathematics, University of Nanjing, Nanjing, People's Republic of China.     

A variable-metric variant of the Karmarkar algorithm for linear programming

The most time-consuming part of the Karmarkar algorithm for linear programming is the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karmarkar algorithm that uses standard variable-metric techniques in an innovative way to approximate this projection. In limited tests, this modification greatly reduces the number of matrix factorizations needed for the solution of linear programming problems. Research sponsored by DOE DE-AS05-82ER13016, ARO DAAG-29-83-K-0035, AFOSR 85-0243. Research sponsored by ARO DAAG-29-83-K-0035, AFOSR 85-0243, Shell Development Company.