Every arrangement extends to a spread

Supported in part by NSA grant MDA904-89-H-2038, PSC-CUNY grant 662330, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF grant STC88-09648.     

Optimization with unary functions

Most nonlinear programming problems consist of functions which are sums of unary functions of linear functions. Advantage can be taken of this form to calculate second and higher order derivatives easily and at little cost. Using these, high order optimization techniques such as Halley's method can be utilized to accelerate the rate of convergence to the solution. These higher order derivatives can also be used to compute second order sensitivity information. These techniques are applied to the solution of the classical chemical equilibrium problem.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research and by the Office of Naval Research grant N00014-86-K0052.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research.     

Bilinear separation of two sets inn-space

The NP-complete problem of determining whether two disjoint point sets in then-dimensional real spaceR ⁿ can be separated by two planes is cast as a bilinear program, that is minimizing the scalar product of two linear functions on a polyhedral set. The bilinear program, which has a vertex solution, is processed by an iterative linear programming algorithm that terminates in a finite number of steps a point satisfying a necessary optimality condition or at a global minimum. Encouraging computational experience on a number of test problems is reported.This material is based on research supported by Air Force Office of Scientific Research grant AFOSR-89-0410, National Science Foundation grant CCR-9101801, and Air Force Laboratory Graduate Fellowship SSN 531-56-2969.     

Sequential quadratic programming for certain parameter identification problems

We analyze the method of sequential quadratic programming for equality constrained minimization problems in Hilbert spaces of functions, and for the discrete approximations of such problems in the context of an elliptic parameter identification problem. We show how the discretization can be constructed so as to preserve the convergence behavior of the iterates for the infinite dimensional problem in the finite dimensional approximations. We use the structure of the parameter identification problem to reduce the size of the linear system for the SQP step and verify nondegeneracy of the constraints.Supported by National Science Foundation grants #DMS-8601139 and #DMS-8900410, and Air Force Office of Scientific Research grants #AFOSR-ISSA-860074, #AFOSR-ISSA-890044 and #AFOSR-89-0124.Supported by National Science Foundation grants #DMS-8619903, #DMS-8900984 and #ASC-8714009, and Air Force Office of Scientific Research grants #AFOSR-ISSA-870092 and #AFOSR-89-0124.     

On better heuristics for Steiner minimum trees

Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than . This solves a long-standing open problem.Part of this work was done while this author visited the Department of Computer Science, Princeton University, supported in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648, supported in part by NSF grant No. CCR-8920505, and also supported in part by the National Natural Science Foundation of China.     

Dynamic programming for multidimensional stochastic control problems

In this paper we study a general multidimensional diffusion-type stochastic control problem. Our model contains the usual regular control problem, singular control problem and impulse control problem as special cases. Using a unified treatment of dynamic programming, we show that the value function of the problem is a viscosity solution of certain Hamilton-Jacobi-Bellman (HJB) quasivariational inequality. The uniqueness of such a quasi-variational inequality is proved. Supported in part by USA Office of Naval Research grant #N00014-96-1-0262. Supported in part by the NSFC Grant #79790130, the National Distinguished Youth Science Foundation of China Grant #19725106 and the Chinese Education Ministry Science Foundation.     

P.L.-Spheres,convex polytopes,and stress

We describe here the notion of generalized stress on simplicial complexes, which serves several purposes: it establishes a link between two proofs of the Lower Bound Theorem for simplicial convex polytopes; elucidates some connections between the algebraic tools and the geometric properties of polytopes; leads to an associated natural generalization of infinitesimal motions; behaves well with respect to bistellar operations in the same way that the face ring of a simplicial complex coordinates well with shelling operations, giving rise to a new proof that p.l.-spheres are Cohen-Macaulay; and is dual to the notion of McMullen's weights on simple polytopes which he used to give a simpler, more geometric proof of theg-theorem. Supported in part by NSF Grants DMS-8504050 and DMS-8802933, by NSA Grant MDA904-89-H-2038, by the Mittag-Leffier Institute, by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, NSF-STC88-09648, and by a grant from the EPSRC.     

On packing bipartite graphs

G andH, two simple graphs, can be packed ifG is isomorphic to a subgraph of , the complement ofH. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees ofG andH. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.the paper was written while the authors were graduate students at the University of Chicago and was completed while the first author was at M.I.T. The work of the first author was supported in part by the Air Force under Contract OSR-86-0076 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. The work of the second author was supported in part by NSF grant CCR-8706518.     

Crossing families

Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two setsA andB of points in the plane are mutually avoiding if no line subtended by a pair of points inA intersects the convex hull ofB, and vice versa. We show that any set ofn points in general position contains a pair of mutually avoiding subsets each of size at least . As a consequence we show that such a set possesses a crossing family of size at least , and describe a fast algorithm for finding such a family.Research supported in part by DARPA grant N00014-89-J-1988, Air Force AFOSR-89-0271, NSF grant DMS-8606225, and an ONR graduate fellowship. Further, part of this work was conducted at and supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC8809648.     

The cauchy problem for an elliptic parabolic operator

Summary Necessary and sufficient conditions are established for the existence of a solution of a Cauchy problem which is not well posed in the sense of Hadamard. This research was supported in part by National Science Foundation Grant No. GP 5882 and in part by Air Force Contract AF OSR 396-63     

Some singular cauchy problems

Summary Existence and uniqueness theorems for some generalizedEuler-Poisson-Darboux equations are proved and growth and convexity properties of the solutions are studied for multiply subharmonic initial values. This research was supported in part by the United States Air Force through the Air Force Office of Scientific Research of the Air Research and Development Command under Contract No. AF 49 (638)-228, at the University of Maryland, and in part by the National Science Foundation, under a fellowship grant.     

A robust sequential quadratic programming method

The sequential quadratic programming method developed by Wilson, Han and Powell may fail if the quadratic programming subproblems become infeasible, or if the associated sequence of search directions is unbounded. This paper considers techniques which circumvent these difficulties by modifying the structure of the constraint region in the quadratic programming subproblems. Furthermore, questions concerning the occurrence of an unbounded sequence of multipliers and problem feasibility are also addressed.Work supported in part by the National Science Foundation under Grant No. DMS-8602399 and by the Air Force Office of Scientific Research under Grant No. ISSA-860080.Work supported in part by the National Science Foundation under Grant No. DMS-8602419.     

Finite-termination schemes for solving semi-infinite satisfycing problems

The problem of finding a parameter which satisfies a set of specifications in inequality form is sometimes referred to as the satisfycing problem. We present a family of methods for solving, in a finite number of iterations, satisfycing problems stated in the form of semi-infinite inequalities. These methods range from adaptive uniform discretization methods to outer approximation methods.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-8713334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, and the State of California MICRO Program Grant 532410-19900.     

Volume comparison à la Aleksandrov

Sans résumé Supported in part by a grant from the National Science Foundation. Supported in part by a grant from the National Science Foundation and the Sloan Foundation.     

Necessary and sufficient conditions for hyperplane transversals

We prove that a finite family ={B ₁,B ₂, ...,B _n } of connected compact sets in ^d has a hyperplane transversal if and only if for somek there exists a set of pointsP={p ₁,p ₂, ...,p _n } (i.e., ak-dimensional labeling of the family) which spans ^k and everyk+2 sets of are met by ak-flat consistent with the order type ofP. This is a common generalization of theorems of Hadwiger, Katchalski, Goodman-Pollack and Wenger.Supported in part by NSF grant DMS-8501947 and CCR-8901484, NSA grant MDA904-89-H-2030, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648.Supported by the National Science and Engineering Research Council of Canada and DIMACS.     

Complementarity and nondegeneracy in semidefinite programming

Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not imply strict complementarity, as they do in LP. The primal and dual nondegeneracy assumptions imply a range of possible ranks for primal and dual solutionsX andZ. This is in contrast with LP where nondegeneracy assumptions exactly determine the number of variables which are zero. It is shown that primal and dual nondegeneracy and strict complementarity all hold generically. Numerical experiments suggest probability distributions for the ranks ofX andZ which are consistent with the nondegeneracy conditions. Supported in part by the U.S. National Science Foundation grant CCR-9625955. Supported in part by U.S. National Science Foundation grant CCR-9501941 and the U.S. Office of Naval Research grant N00014-96-1-0704. Supported in part by U.S. National Science Foundation grant CCR-9401119.     

Approximating maximum independent sets by excluding subgraphs

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)²). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.A preliminary version of this paper appeared in [9].Supported in part by National Science Foundation Grant CCR-8902522 and PYI Award CCR-9057488.Research done at Rutgers University. Supported in part by Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) fellowship.     

Quadratic programming with one negative eigenvalue is NP-hard

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Haijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.This author's work supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013. A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

A bifurcation analysis of the nonlinear parametric programming problem

The structure of solutions to the nonlinear parametric programming problem with a one dimensional parameter is analyzed in terms of the bifurcation behavior of the curves of critical points and the persistence of minima along these curves. Changes in the structure of the solution occur at singularities of a nonlinear system of equations motivated by the Fritz John first-order necessary conditions. It has been shown that these singularities may be completely partitioned into seven distinct classes based upon the violation of one or more of the following: a complementarity condition, a constraint qualification, and the nonsingularity of the Hessian of the Lagrangian on a tangent space. To apply classical bifurcation techniques to these singularities, a further subdivision of each case is necessary. The structure of curves of critical points near singularities of lowest (zero) codimension within each case is analyzed, as well as the persistence of minima along curves emanating from these singularities. Bifurcation behavior is also investigated or discussed for many of the subcases giving rise to a codimension one singularity.This work was supported by the National Science Foundation through NSF Grants DMS-85-10201 and DMS-87-04679 and by the Air Force Office of Scientific Research through grant number AFOSR-88-0059.     

An algorithm for nonlinear optimization using linear programming and equality constrained subproblems

This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza [10]. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained by making a linear approximation to the ₁ penalty function inside a trust region. In the second stage, an equality constrained quadratic program (EQP) is solved involving only those constraints that are active at the solution of the linear program. The EQP incorporates a trust-region constraint and is solved (inexactly) by means of a projected conjugate gradient method. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEr [1, 15] test set.This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported in part by the EPSRC grant GR/R46641.These authors were supported by National Science Foundation grants CCR-9987818, ATM-0086579 and CCR-0219438 and Department of Energy grant DE-FG02-87ER25047-A004.Report OTC 2002/4, Optimization Technology CenterTo Roger Fletcher, with respect and admiration