Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

A stable method for solving certain constrained least squares problems

This paper presents a feasible descent algorithm for solving certain constrained least squares problems. These problems are specially structured quadratic programming problems with positive semidefinite Hessian matrices that are allowed to be singular. The algorithm generates a finite sequence of subproblems that are solved using the numerically stable technique of orthogonal factorization with reorthogonalization and Given's transformation updating.This material is based upon work supported by the National Science Foundation under Grant No. MCS 78-06716 and by the International Institute for Applied Systems Analysis.     

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.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

Q-Learning Algorithms with Random Truncation Bounds and Applications to Effective Parallel Computing

Motivated by an important problem of load balancing in parallel computing, this paper examines a modified algorithm to enhance Q-learning methods, especially in asynchronous recursive procedures for self-adaptive load distribution at run-time. Unlike the existing projection method that utilizes a fixed region, our algorithm employs a sequence of growing truncation bounds to ensure the boundedness of the iterates. Convergence and rates of convergence of the proposed algorithm are established. This class of algorithms has broad applications in signal processing, learning, financial engineering, and other related fields. G. Yin’s research was supported in part by the National Science Foundation under Grants DMS-0603287 and DMS-0624849 and in part by the National Security Agency under Grant MSPF-068-029. C.Z. Xu’s research was supported in part by the National Science Foundation under Grants CCF-0611750, DMS-0624849, CNS-0702488, and CRI-0708232. L.Y. Wang’s research was supported in part by the National Science Foundation under Grants ECS-0329597 and DMS-0624849 and by the Michigan Economic Development Council.     

Optimal solution approximation for infinite positive-definite quadratic programming

We consider a general doubly-infinite, positive-definite, quadratic programming problem. We show that the sequence of unique optimal solutions to the natural finite-dimensional subproblems strongly converges to the unique optimal solution. This offers the opportunity to arbitrarily well approximate the infinite-dimensional optimal solution by numerically solving a sufficiently large finite-dimensional version of the problem. We then apply our results to a general time-varying, infinite-horizon, positive-definite, LQ control problem.This work was supported in part by the National Science Foundation under Grants ECS-8700836, DDM-9202849, and DDM-9214894.     

Spectral conditioning and pseudospectral growth

Using the language of pseudospectra, we study the behavior of matrix eigenvalues under two scales of matrix perturbation. First, we relate Lidskii’s analysis of small perturbations to a recent result of Karow on the growth rate of pseudospectra. Then, considering larger perturbations, we follow recent work of Alam and Bora in characterizing the distance from a given matrix to the set of matrices with multiple eigenvalues in terms of the number of connected components of pseudospectra. J. V. Burke’s research was supported in part by National Science Foundation Grant DMS-0505712. A. S. Lewis’s research was supported in part by National Science Foundation Grant DMS-0504032. M. L. Overton’s research was supported in part by National Science Foundation Grant DMS-0412049.     

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 relaxation method for nonconvex quadratically constrained quadratic programs

We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

A successive projection method

It is of both theoretical and practical interest to find the projection of a point to the intersection of a finite number of closed convex sets by a sequence of projections to the individual sets successively. In this paper we study such a method and analyze its convergence properties. A main feature of the method is its capability to decompose the projection problem into several small ones. For some structured sparse problems these small subproblems can be solved independently and the presented method has a potential use in parallel computation.This material is based on work supported in part by the National Science Foundation under Grant DMS-8602419 and by the Center for Supercomputing Research and Development, University of Illinois.     

Index formulas for geometric Dirac operators in Riemannian foliations

With regards to certain Riemannian foliations we consider Kasparov pairings of leafwise and transverse Dirac operators. Relative to a pairing with a transversal class we commence by establishing an index formula for foliations with leaves of nonpositive sectional curvature. The underlying ideas are then developed in a more general setting leading to pairings of images under the Baum-Connes map in geometricK-theory with transversal classes. Several ideas implicit in the work of Connes and Hilsum-Skandalis are formulated in the context of Riemannian foliations. From these we establish the notion of a dual pairing inK-homology and a theorem of the Grothendieck-Riemann-Roch type.R. G. D. was supported by The National Science Foundation under Grant No. DMS-9304283.J. F. G. and F. W. K. were supported in part by The National Science Foundation under Grant No. DMS-9208182.F. W. K. was also supported in part by an Arnold O. Beckman Research Award from the Research Board of the University of Illinois.     

Defect series and nonrational Hilbert modular threefolds

This material is based on work supported by the National Science Foundation under Grant No. DMS-9115349. The Government has certain rights in this material     

Defects of cusp singularities and the classification of Hilbert modular threefolds

This material is based on work supported by the National Science Foundation under Grant No. DMS-9008689. The Government has certain rights in this material     

Consolidation rates for two interacting systems in the plane

Summary This paper is a sequel of a paper of Cox and Griffeath “diffusive clustering in the two dimensional voter model”. We continue our study of the voter model and coalescing random walks on the two dimensional integer lattice. Some exact asymptotics concerning the rate of clustering in the former process and the coalescence rate of the latter are derived. We use these results to prove a limit law, announced in that earlier paper, concerning the size of the largest square centered at the origin which is of solid color at a large time t. Partially supported by the National Science Foundation under Grant DMS-831080 Partially supported by the National Science Foundation under Grant DMS-841317 Partially supported by the National Science Foundation under Grant DMS-830549     

Projection and restriction methods in geometric programming and related problems

Mathematical programming problems with unattained infima or unbounded optimal solution sets are dual to problems which lackinterior points, e.g., problems for which the Slater condition fails to hold or for which the hypothesis of Fenchel's theorem fails to hold. In such cases, it is possible to project the unbounded problem onto a subspace and to restrict the dual problem to an affine set so that the infima are not altered. After a finite sequence of such projections and restrictions, dual problems are obtained which have bounded optimal solution sets andinterior points. Although results of this kind have occasionally been used in other contexts, it is in geometric programming (both in the original psynomial form and the generalized form) where such methods appear most useful. In this paper, we present a treatment of dual projection and restriction methods developed in terms of dual generalized geometric programming problems. Analogous results are given for Fenchel and ordinary dual problems.This research was supported in part by Grant No. AFOSR-73-2516 from the Air Force Office of Scientific Research and by Grant No. NSF-ENG-76-10260 from the National Science Foundation.The authors wish to express their appreciation to the referees for several helpful comments.     

A note on duality in disjunctive programming

We state a duality theorem for disjunctive programming, which generalizes to this class of problems the corresponding result for linear programming.This work was supported by the National Science Foundation under Grant No. MPS73-08534 A02 and by the US Office of Naval Research under Contract No. N00014-75-C-0621-NR047-048.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.     

Verifiability and strong verifiability

Research supported by National Science Foundation Grant No. DMS-8908670.     

Computing the geodesic center of a simple polygon

The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon withn vertices in timeO(n logn).Work on this paper by the first author has been supported by National Science Foundation Grant No. DMS-8501947. Work on this paper by the second author has been supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Part of the work on this paper by the first two authors has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Work on this paper by the third author has been supported by the Fonds zur Förderung der wissenschaftlichen Forschung (FWF), Project S32/01.     

A nonconforming finite element method for a two-dimensional curl–curl and grad-div problem

A numerical method for a two-dimensional curl–curl and grad-div problem is studied in this paper. It is based on a discretization using weakly continuous P ₁ vector fields and includes two consistency terms involving the jumps of the vector fields across element boundaries. Optimal convergence rates (up to an arbitrary positive ) in both the energy norm and the L ₂ norm are established on graded meshes. The theoretical results are confirmed by numerical experiments. The work of the first author was supported in part by the National Science Foundation under Grant No. DMS-03-11790 and by the Humboldt Foundation through her Humboldt Research Award. The work of the third author was supported in part by the National Science Foundation under Grant No. DMS-06-52481.