On polyhedral extension of some LP theorems

McLinden (Mathematical Programming 24 (1982) 162–176) has extended theorems of Tucker (1956) and Williams (1970) on the complementarity behaviour of feasible and optimal solutions to a pair of canonical linear programs to proper convex polyhedral functions. He achieved this by heavily using the well-developed machinery of convex analysis. In this note, we prove most of his results mainly using linear programming theory.     

On the number of solutions to a class of linear complementarity problems

In this note, we consider the linear complementarity problemw = Mz + q, w 0, z 0, w ^T z = 0, when all principal minors ofM are negative. We show that for such a problem for anyq, there are either 0, 1, 2, or 3 solutions. Also, a set of sufficiency conditions for uniqueness is stated.The work of both authors is partially supported by a grant from the National Science Foundation, MCS 77-03472.     

Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.     

On the average number of steps of the simplex method of linear programming

The goal is to give some theoretical explanation for the efficiency of the simplex method of George Dantzig. Fixing the number of constraints and using Dantzig's self-dual parametric algorithm, we show that the number of pivots required to solve a linear programming problem grows in proportion to the number of variables on the average. Supported in part by NSF Grant #MCS-8102262.     

Sensitivity theorems in integer linear programming

We consider integer linear programming problems with a fixed coefficient matrix and varying objective function and right-hand-side vector. Among our results, we show that, for any optimal solution to a linear program max{wx: Axb}, the distance to the nearest optimal solution to the corresponding integer program is at most the dimension of the problem multiplied by the largest subdeterminant of the integral matrixA. Using this, we strengthen several integer programming proximity results of Blair and Jeroslow; Graver; and Wolsey. We also show that the Chvátal rank of a polyhedron {x: Axb} can be bounded above by a function of the matrixA, independent of the vectorb, a result which, as Blair observed, is equivalent to Blair and Jeroslow's theorem that each integer programming value function is a Gomory function.Supported by a grant from the Alexander von Humboldt Stiftung.Since September 1985: Department of Operations Research, Upson Hall, Cornell University, Ithaca, NY 14853, USA.Partially supported by the Sonderforschungbereich 21 (DFG), Institut für Ökonometrie und Operations Research of the University of Bonn, FR Germany.     

Column aggregation and primal decomposition in linear programming: some observations

In this paper we present a way to interpret column aggregation schemes in linear programming as a special kind of primal decomposition. This relation between aggregation and decomposition is obtained through a reformulation of the original problem by the introduction of auxiliary variables. The relation between aggregation and decomposition yields a natural iterative aggregation scheme, where weights updating can be done in different ways. We describe several weight updating schemes and illustrate three of them within an iterative aggregation technique with a numerical example. Finally we point out some new research issues that appear when the aggregation process is viewed in this decomposition framework     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

Stability of the linear complementarity problem at a solution point

In this paper we study the behavior of a solution of the linear complementarity problem when data are perturbed. We give characterizations of strong stability of the linear complementarity problem at a solution. In the case of stability we give sufficient and necessary conditions.     

Generalization of some duality theorems in nonlinear programming

Pseudoconvexity of a function on one set with respect to some other set is defined and duality theorems are proved for nonlinear programming problems by assuming a certain kind of convexity property for a particular linear combination of functions involved in the problem rather than assuming the convexity property for the individual functions as is usually done. This approach generalizes some of the well-known duality theorems and gives some additional strict converse duality theorems which are not comparable with the earlier duality results of this type. Further it is shown that the duality theory for nonlinear fractional programming problems follows as a particular case of the results established here.     

Computational complexity of LCPs associated with positive definite symmetric matrices

Murty in a recent paper has shown that the computational effort required to solve a linear complementarity problem (LCP), by either of the two well known complementary pivot methods is not bounded above by a polynomial in the size of the problem. In that paper, by constructing a class of LCPs—one of ordern forn 2—he has shown that to solve the problem of ordern, either of the two methods goes through 2 ⁿ pivot steps before termination.However that paper leaves it as an open question to show whether or not the same property holds if the matrix,M, in the LCP is positive definite and symmetric. The class of LCPs in whichM is positive definite and symmetric is of particular interest because of the special structure of the problems, and also because they appear in many practical applications.In this paper, we study the computational growth of each of the two methods to solve the LCP, (q, M), whenM is positive definite and symmetric and obtain similar results.This research is partially supported by Air Force Office of Scientific Research, Air Force Number AFOSR-78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation thereon.     

A dual perturbation view of linear programming

Solving standard-form linear prograrns via perturbation of the primal objective function has received much attention recently. In this paper, we investigate a new perturbation scheme which obtains a dual optimal solution by perturbing the dual feasible domain under different norms. A dual-to-primal conversion formula is also provided. We show that this new perturbation scheme actually generalizes the primal entropic perturbation approach to linear programming.Partially sponsored by the North Carolina Supercomputing Center 1994 Cray Research Grant and the National Textile Center Research Grant.     

The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

On the symmetric travelling salesman problem II: Lifting theorems and facets

Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of then-city travelling salesman polytope retains its facetial property for the (n + m)-city travelling salesman polytope, wherem 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of then-city travelling salesman problem, wheren is an arbitrary integer.     

An unconstrained convex programming view of linear programming

The major interest of this paper is to show that, at least in theory, a pair of primal and dual -optimal solutions to a general linear program in Karmarkar's standard form can be obtained by solving an unconstrained convex program. Hence unconstrained convex optimization methods are suggested to be carefully reviewed for this purpose.     

Some experiments with the pathological linear programs of N. Zadeh

Computational results are presented which show that N. Zadeh's pathological examples for the simplex algorithm apparently take a number of pivots approximately proportional to the number of columns in the tableau when its column order is randomized.     

The complementary unboundedness of dual feasible solution sets in convex programming

F.E. Clark has shown that if at least one of the feasible solution sets for a pair of dual linear programming problems is nonempty then at least one of them is both nonempty and unbounded. Subsequently, M. Avriel and A.C. Williams have obtained the same result in the more general context of (prototype posynomial) geometric programming. In this paper we show that the same result is actually false in the even more general context of convex programming — unless a certain regularity condition is satisfied.We also show that the regularity condition is so weak that it is automatically satisfied in linear programming (prototype posynomial) geometric programming, quadratic programming (with either linear or quadratic constraints),l _p -regression analysis, optimal location, roadway network analysis, and chemical equilibrium analysis. Moreover, we develop an equivalent regularity condition for each of the usual formulations of duality.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-73-2516.     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.     

Proper,reflecting and absorbing facts of complementary cones

A common approach in studying the linear complementarity problem is via the geometry of the complementary cones. In the case of nondegeneracy, the concept of a ‘proper facet’ and a ‘reflecting facet’ have proven useful. This paper extends these concepts to the degenerate case. Under degeneracy, a facet may turn out to be neither proper nor reflecting, but, a third type which we designate as ‘absorbing’. Previous results in this area can be easily extended using these more general definitions.     

A class of methods for linear programming

A class of methods is presented for solving standard linear programming problems. Like the simplex method, these methods move from one feasible solution to another at each iteration, improving the objective function as they go. Each such feasible solution is also associated with a basis. However, this feasible solution need not be an extreme point and the basic solution corresponding to the associated basis need not be feasible. Nevertheless, an optimal solution, if one exists, is found in a finite number of iterations (under nondegeneracy). An important example of a method in the class is the reduced gradient method with a slight modification regarding selection of the entering variable.