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.     

Lattices in rank one Lie groups over local fields

We prove that if is theK-rational points of aK-rank one semisimple group over a non archimedean local fieldK, thenG has cocompact non-arithmetic lattices and if char(K)>0 also non-uniform ones. We also give a general structure theorem for lattices inG, from which we confirm Serre's conjecture that such arithmetic lattices do not satisfy the congruence subgroup property.Partially supported by a grant from the Bi-national Science Foundation U.S.-Israel.     

A globally and quadratically convergent affine scaling method for linearℓ 1 problems

Recently, various interior point algorithms related to the Karmarkar algorithm have been developed for linear programming. In this paper, we first show how this interior point philosophy can be adapted to the linear ₁ problem (in which there are no feasibility constraints) to yield a globally and linearly convergent algorithm. We then show that the linear algorithm can be modified to provide aglobally and ultimatelyquadratically convergent algorithm. This modified algorithm appears to be significantly more efficient in practise than a more straightforward interior point approach via a linear programming formulation: we present numerical results to support this claim.This paper was presented at the Third SIAM Conference on Optimization, in Boston, April 1989.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University, and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.Research partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.     

Sample-path optimization of convex stochastic performance functions

In this paper we propose a method for optimizing convex performance functions in stochastic systems. These functions can include expected performance in static systems and steady-state performance in discrete-event dynamic systems; they may be nonsmooth. The method is closely related to retrospective simulation optimization; it appears to overcome some limitations of stochastic approximation, which is often applied to such problems. We explain the method and give computational results for two classes of problems: tandem production lines with up to 50 machines, and stochastic PERT (Program Evaluation and Review Technique) problems with up to 70 nodes and 110 arcs. Sponsored by the National Science Foundation under grant number CCR-9109345, by the Air Force Systems Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAL03-92-G-0408, and by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Sponsored by a Wisconsin/Hilldale Research Award, by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144, and the Air Force Systems Command, USAF, under grant number F49620-93-1-0068. Sponsored by the National Science Foundation under grant number DDM-9201813.     

Feedback stabilization of distributed semilinear control systems

This paper considers feedback stabilization for the semilinear control system HereA is the infinitesimal generator of a linearC ⁰ semigroup of contractions on a Hilbert spaceH andB : H H is a nonlinear operator. A sufficient condition for feedback stabilization is given and applications to hyperbolic boundary value problems are presented.This research was sponsored in part by grant no. MCS76-07012 from the U.S. National Science Foundation.     

Implementation of a continuation method for normal maps

This paper presents an implementation of a nonsmooth continuation method of which the idea was originally put forward by Alexander et al. We show how the method can be computationally implemented and present numerical results for variational inequality problems in up to 96 variables. The research reported here was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAH04-95-1-0149, and by the National Science Foundation under grant number CCR-9109345. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the sponsoring agencies or the U.S. Government.     

An interior point algorithm ofO(\sqrt m \left| {\ln \varepsilon } \right|) iterations forC 1-convex programming

We present a theoretical result on a path-following algorithm for convex programs. The algorithm employs a nonsmooth Newton subroutine. It starts from a near center of a restricted constraint set, performs a partial nonsmooth Newton step in each iteration, and converges to a point whose cost is within accuracy of the optimal cost in iterations, wherem is the number of constraints in the problem. Unlike other interior point methods, the analyzed algorithm only requires a first-order Lipschitzian condition and a generalized Hessian similarity condition on the objective and constraint functions. Therefore, our result indicates the theoretical feasibility of applying interior point methods to certainC ¹-optimization problems instead ofC ²-problems. Since the complexity bound is unchanged compared with similar algorithms forC ²-convex programming, the result shows that the smoothness of functions may not be a factor affecting the complexity of interior point methods.This author's work is supported in part by the National Science Foundation of the USA under grant DDM-8721709.This author's work is supported in part by the Australian Research Council.     

Rate of divergence of some integrals

Lower bounds for the absolute values of the functions and , where is the Möbius function and is the Manholdt function, are obtained.Translated fromMatematicheskie Zametki, Vol. 58, No. 2, pp. 243–255, August, 1995.S. V. Konyagin's work was supported by grant No. MC5000 of the International Science Foundation and by grant No. 93-01-002400 of the Russian Foundation for Basic Research.     

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.     

Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.     

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D

The detour and spanning ratio of a graph G embedded in measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe O(nlog n) time algorithms for computing the detour and spanning ratio of a planar polygonal path. By generalizing these algorithms, we obtain O(nlog ² n)-time algorithms for computing the detour or spanning ratio of planar trees and cycles. Finally, we develop subquadratic algorithms for computing the detour and spanning ratio for paths, cycles, and trees embedded in , and show that computing the detour in is at least as hard as Hopcroft’s problem. This research was partly funded by CRM, FCAR, MITACS, and NSERC. P.A. was supported by NSF under grants CCR-00-86013 EIA-99-72879, EIA-01-31905, and CCR-02-04118, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.-Israeli Binational Science Foundation. R.K. was supported by DFG grant Kl 655/14-1. M.S. was supported by NSF Grants CCR-97-32101 and CCR-00-98246, by a grant from the U.S.-Israeli Binational Science Foundation (jointly with P.A.), by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Some of these results have appeared in a preliminary form in [2, 20].     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

Second-order epi-derivatives of integral functionals

Epi-derivatives have many applications in optimization as approached through nonsmooth analysis. In particular, second-order epi-derivatives can be used to obtain optimality conditions and carry out sensitivity analysis. Therefore the existence of second-order epi-derivatives for various classes of functions is a topic of considerable interest. A broad class of composite functions on ⁿ called fully amenable functions (which include general penalty functions composed withC ² mappings, possibly under a constraint qualification) are now known to be twice epi-differentiable. Integral functionals appear widely in problems in infinite-dimensional optimization, yet to date, only integral functionals defined by convex integrands have been shown to be twice epi-differentiable, provided that the integrands are twice epi-differentiable. Here it is shown that integral functionals are twice epi-differentiable even without convexity, provided only that their defining integrands are twice epi-differentiable and satisfy a uniform lower boundedness condition. In particular, integral functionals defined by fully amenable integrands are twice epi-differentiable under mild conditions on the behavior of the integrands.This work was supported in part by the National Science Foundation under grant DMS-9200303.     

Conditions of topological conjugacy of gradient-like diffeomorphisms on irreducible 3-manifolds

In this paper, we obtain the topological classification of gradient-like diffeomorphisms and the conditions of topological conjugacy of Morse-Smale diffeomorphisms with finite sets of heteroclinic trajectories on three-dimensional manifolds.Translated fromMatematicheskie Zametki, Vol. 59, No. 1, pp. 73–80, January, 1996.This research was partially supported by the Russian Foundation for Basic Research under grant No. 93-01-01-407, by the International Science Foundation under grant R99000, and by the Foundation Cultural Initiative.     

A chaos hypothesis for some large systems of random equations

Summary This paper is about the behavior of solutions to large systems of linear algebraic and differential equations when the coefficients are random variables. We will prove a law of large numbers and a central limit theorem for the solutions of certain algebraic systems, and the weak convergence to a Gaussian process for the solution of a system of differential equations. Some of the results were surprisingly difficult to prove, but they are all easily anticipated from a chaos hypothesis: i.e. an assumption of near independence for the components of the solutions of large systems of weakly coupled equations.Supported by the National Science Foundation under grant MCS76-80762, by the U.S. Air Force under grant AFOSR 78-3514 and the U.S. Army under grant DAAG 2980-K-0006     

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.     

Limit theorems for sums of dependent random variables

Summary In Lai and Stout [7] the upper half of the law of the iterated logarithm (LIL) is established for sums of strongly dependent stationary Gaussian random variables. Herein, the upper half of the LIL is established for strongly dependent random variables {X _i} which are however not necessarily Gaussian. Applications are made to multiplicative random variables and to f(Z _i ) where the Z _i are strongly dependent Gaussian. A maximal inequality and a Marcinkiewicz-Zygmund type strong law are established for sums of strongly dependent random variables X _i satisfying a moment condition of the form E¦S _a,n ¦^pg(n), where , generalizing the work of Serfling [13, 14].Research supported by the National Science Foundation under grant NSF-MCS-78-09179Research supported by the National Science Foundation under grant NSF-MCS-78-04014     

Complexity analysis of a linear complementarity algorithm based on a Lyapunov function

We consider a path following algorithm for solving linear complementarity problems with positive semi-definite matrices. This algorithm can start from any interior solution and attain a linear rate of convergence. Moreover, if the starting solution is appropriately chosen, this algorithm achieves a complexity of O( L}) iterations, wherem is the number of variables andL is the size of the problem encoding in binary. We present a simple complexity analysis for this algorithm, which is based on a new Lyapunov function for measuring the nearness to optimality. This Lyapunov function has itself interesting properties that can be used in a line search to accelerate convergence. We also develop an inexact line search procedure in which the line search stepsize is obtainable in a closed form. Finally, we extended this algorithm to handle directly variables which are unconstrained in sign and whose corresponding matrix is positive definite. The rate of convergence of this extended algorithm is shown to be independent of the number of such variables.This research is partially supported by the U.S. Army Research Office, contract DAAL03-86-K-0171 (Center for Intelligent Control Systems), and by the National Science Foundation, grant NSF-ECS-8519058.     

Newton's method for a class of nonsmooth functions

This paper presents and justifies a Newton iterative process for finding zeros of functions admitting a certain type of approximation. This class includes smooth functions as well as nonsmooth reformulations of variational inequalities. We prove for this method an analogue of the fundamental local convergence theorem of Kantorovich including optimal error bounds.The research reported here was sponsored by the National Science Foundation under Grants CCR-8801489 and CCR-9109345, by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and F49620-93-1-0068, by the U. S. Army Research Office under Grant No. DAAL03-92-G-0408, and by the U. S. Army Space and Strategic Defense Command under Contract No. DASG60-91-C-0144. The U. S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Circles through two points that always enclose many points

This paper proves that any set of n points in the plane contains two points such that any circle through those two points encloses at least points of the set. The main ingredients used in the proof of this result are edge counting formulas for k-order Voronoi diagrams and a lower bound on the minimum number of semispaces of size at most k.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565, by the second author has been partially supported by the Digital Equipment Corporation, by the fourth author has been partially supported by the Office of Naval Research under Grant N00014-86K-0416.