Research on Optimization Algorithms

摘要

This is a summary of research carried out under this grant. Some of the results are: for linear complementarity problems, existing pivot algorithms like Lemke's complementary pivot method, Murty's principal pivoting method, Cottle-Dantzig principal pivoting method, Vander Heyden's variable dimension algorithm, are all exponential growth algorithms in the worst case even on very nice classes f problems. Polynomially bounded ellipsoid methods have been developed for solving convex quadratic programs or linear complementarity problems associated with positive semidefinite matrices. A practically efficient critical index algorithm based on orthogonal projections has been developed for linear complementarity problems associated with positive definite symmetric matrices. Efficient blossom algorithms have been developed for edge covering problems and 1-matching/covering problems in undirected networks, as well as efficient subroutines for performing various types of sensitivity analysis. A computer package for 1-matching/covering algorithms suitable for large scale applications has been developed. A bounding strategy for the set covering problem based on the 1-matching/covering problem and Lagrangean relaxation has been developed. Efficient linear time algorithms have been developed for checking the adjacency of two given 1-matching/covering incidence vectors on the 1-matching/covering polytope.