Nondifferential optimization via adaptive smoothing

The problem of minimizing a nondifferential functionx f(x) (subject, possibly, to nondifferential constraints) is considered. Conventional algorithms are employed for minimizing a differential approximationf off (subject to differentiable approximations ofg). The parameter is adaptively reduced in such a way as to ensure convergence to points satisfying necessary conditions of optimality for the original problem.This research was supported by the UK Science and Engineering Research Council, the National Science Foundation under Grant No. ECS-8121149, and the Joint Services Electronics Program, Contract No. F49620-79-C-0178.     

A quadratic approximation method for minimizing a class of quasidifferentiable functions

Summary An unconstrained nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities arise from terms of the form max [f ₁(x), ...,f _n (x)], which may enter nonlinearly in the objective function. Local convex polyhedral upper approximations to the objective function are introduced. These approximations are used in an iterative method for solving the problem. The algorithm proceeds by solving quadratic programming subproblems to generate search directions. Approximate line searches ensure global convergence of the method to stationary points. The algorithm is conceptually simple and easy to implement. It generalizes efficient variable metric methods for minimax calculations.     

Algorithms for optimization problems with exclusion constraints

This paper proposes algorithms for minimizing a continuously differentiable functionf(x): ⁿ subject to the constraint thatx does not lie in specified bounded subsets of ⁿ . Such problems arise in a variety of applications, such as tolerance design of electronic circuits and obstacle avoidance in the selection of trajectories for robot arms. Such constraints have the form . The function is not continuously differentiable. Algorithms based on the use of generalized gradients have considerable disadvantages because of the local concavity of at points where the set {j|g ^j (x)=(x)} has more than one element. Algorithms which avoid these disadvantrages are presented, and their convergence is established.This research was sponsored in part by the National Science Foundation under Grant ECS-81-21149, the Air Force Office of Scientific Research (AFSC), United States Air Force under Contract F49620-79-C-0178, the Office of Naval Research under Grant N00014-83-K-0602, the Air Force Office of Scientific Research under Grant AFOSR-83-0361, and the Semiconductor Research Consortium under Grant SRC-82-11-008.     

Constrained extrema of bilinear functionals

LetA be an operator on a finite dimensional unitary space. This paper contains results on the set of values taken on by the conjugate bilinear functional (A x, y) asx andy range over all unit vectors with prescribed inner product. By analyzing the same problem for the induced functional on the Grassmannian, results on non-principal subdeterminants are also obtained.The research of this author was supported by the U.S. Air Force Office of Scientific Research under Grant AFOSR 72-2164.     

Geometric convergence to e−z by rational functions with real poles

Summary In this paper, we show that there exists a sequence of rational functions of the formR _n(z)=p_n–1(z)/(1+z/n)ⁿ,n=1, 2, ..., with degp _n–1n–1, which converges geometrically toe ^–z in the uniform norm on [0, +), as well as on some infinite sector symmetric about the positive real axis. We also discuss the usefulness of such rational functions in approximating the solutions of heat-conduction type problems.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688, and by the University of South Florida Research Council.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Energy Research and Development Administration (ERDA) under Grant E(11-1)-2075.     

Locking effects in the finite element approximation of elasticity problems

Summary We consider the finite element approximation of the 2D elasticity problem when the Poisson ratiov is close to 0.5. It is well-known that the performance of certain commonly used finite elements deteriorates asv0, a phenomenon calledlocking. We analyze this phenomenon and characterize the strength of the locking androbustness of varioush-version schemes using triangular and rectangular elements. We prove that thep-andh-p versions are free of locking with respect to the error in the energy norm. A generalization of our theory to the 3D problem is also discussed.The work of this author was supported in part by the Office of Naval Research under Naval Research Grant N00014-90-J-1030The work of this author was supported in part by the Air Force Office of Scientific Research, Air Force Systems Command, U.S. Air Force, under grant AFOSR 89-0252     

Existence,uniqueness and continuity of solutions of integral equations. An addendum

Summary This note corrects au error in the continuous dependence theorem of an earlier paper on the subject stated in the title. Here it is shows that the topology of one of the spaces of functions can be modified in order to obtain the desired continuity results. This research was support in part by the National Aeronautics Space Administration under Grant No. NGL-40-002-015, and in part by the U. S. Air Force under Grant No. AF-AFOSR-67-0693A. This research was supported in part by the National Science Foundation under Grant No. GP-3904 and GP-7041 and in part by the U.S. Army under Grant No. D1-31-124-ARO-D-265. Entrata in Redazione il 10 aprile 1970.     

Product type quadrature formulas

This paper is concerned with the numerical approximation of integrals of the form _a ^b f(x)g(x)dx by means of a product type quadrature formula. In such a formula the functionf (x) is sampled at a set ofn+1 distinct points and the functiong(x) at a (possibly different) set ofm+1 distinct points. These formulas are a generalization of the classical (regular) numerical integration rules. A number of basic results for such formulas are stated and proved. The concept of a symmetric quadrature formula is defined and the connection between such rules and regular quadrature formulas is discussed. Expressions for the error term are developed. These are applied to a specific example.The work of the first author was supported in part by NIH Grant No. FRO 7129-01 and that of the second author in part by U.S. Army Ballistic Research Laboratories Contract DA-18-001-AMC-876 X.     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Series expansions of solutions of the heat equation inn dimensions

Summary This paper is an extensions of a recent result byD. V. Widder andP. C. Rosenbloom concerning the expansion of a solution u(x, t) of the heat equation, u_x ^x=u_t, in series of polyonomial solutions. Whereas that result involved two variables only, the present one permits an arbitrary finite number of variables. It is found that the polynomial solutions of the heat equation in n dimensions are factorable into polynomials in two variables. The expansion problem may be considered as an investigation of the space spanned by linear combinations of these factorable solutions To Enrico Bompiani on his scientific Jubilee This research was supported (in part) by the U. S. Air Force, through the Air Force Office of Scientific Research, Air Research and Development Command, under Contract AF 49(638)-574. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Geometric convergence of rational approximations toe −z in infinite sectors

Summary In this paper, we study the geometric convergence of rational approximations toe ^–z in infinite sectors symmetric about the positive real axis.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688, and by the University of South Florida Research CouncilResearch supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Atomic Energy Commission under Grant AT (11-1)-2075     

Approximation procedures based on the method of multipliers

In this paper, we consider a method for solving certain optimization problems with constraints, nondifferentiabilities, and other ill-conditioning terms in the cost functional by approximating them by well-behaved optimization problems. The approach is based on methods of multipliers. The convergence properties of the methods proposed can be inferred from corresponding properties of multiplier methods with partial elimination of constraints. A related analysis is provided in this paper.This work was supported in part by the Joint Services Electronics Program (US Army, US Navy, and US Air Force) under Contract No. DAAB-07-72-C-0259, and by the National Science Foundation under Grant No. ENG-74-19332.     

Outer approximation algorithm for nondifferentiable optimization problems

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ⁿ can be expressed as minimizing max{g(x, y)|y X}, whereg is a support function forf[f(x) g(x, y), for ally X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.This research was supported by the Science and Engineering Research Council, UK, and by the National Science Foundation under Grant No. ECS-79-13148.     

A priori estimates for truncation error of continued fractionsK(1/b n )

A priori estimates are obtained for the truncation error of continued fractions of the formK(1/b _n ), with complex elementsb _n . The method employed is based on the calculation of bounds for successive diameters of a sequence of nested disks, where then-th approximant of the continued fraction is contained in then-th disk. Numerical examples are given to illustrate useful procedures and typical error estimates for continued fraction expansions of the complex logarithm and the ratio of consecutive Bessel functions.This research was supported by the National Science Foundation under Grant No. GP-9009 and by the United States Air Force through the Air Force Office of Scientific Research under Grant No. AFOSR-70-1888.     

A posteriori error estimation with finite element methods of lines for one-dimensional parabolic systems

Summary Consider the solution of one-dimensional linear initial-boundary value problems by a finite element method of lines using a piecewiseP ^th -degree polynomial basis. A posteriori estimates of the discretization error are obtained as the solutions of either local parabolic or local elliptic finite element problems using piecewise polynomial corrections of degreep+1 that vanish at element ends. Error estimates computed in this manner are shown to converge in energy under mesh refinement to the exact finite element discretization error. Computational results indicate that the error estimates are robust over a wide range of mesh spacings and polynomial degrees and are, furthermore, applicable in situations that are not supported by the analysis.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 90-0194; by the U.S. Army Research Office under Contract Number DAAL03-91-G-0215; and by the National Science Foundation under Institutional Infrastructure Grant Number CDA-8805910     

On the sharpness of theorems concerning zero-free regions for certain sequences of polynomials

Summary In this paper, we establish the sharpness of a theorem concerning zero-free parabolic regions for certain sequences of polynomials satisfying a three-term recurrence relation. Similarly, we establish the sharpness of a zero-free sectorial region for certain sequences of Padé approximants toe ^z .Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Energy Research and Development Administration (ERDA) under Grant E(11-1)-2075     

Bounds on the number of cycles of length three in a planar graph

LetG be ap-vertex planar graph having a representation in the plane with nontriangular facesF ₁,F ₂, …,F _r. Letf ₁,f ₂, …,f _r denote the lengths of the cycles bounding the facesF ₁,F ₂, …,F _r respectively. LetC ₃(G) be the number of cycles of length three inG. We give bounds onC ₃(G) in terms ofp,f ₁,f ₂, …,f _r. WhenG is 3-connected these bounds are bounds for the number of triangles in a polyhedron. We also show that all possible values ofC ₃(G) between the maximum and minimum value are actually achieved. This research was supported in part by the U.S.A.F. Office of Scientific Research, Systems Command, under Grant AFOSR-76-3017 and the National Science Foundation under Grant ENG79-09724.     

Infinitely constrained optimization problems

A generalized cutting-plane algorithm designed to solve problems of the form min{f(x) :x X andg(x,y) 0 for ally Y} is described. Convergence is established in the general case (f,g continuous,X andY compact). Constraint dropping is allowed in a special case [f,g(·,y) convex functions,X a convex set]. Applications are made to a variety of max-min problems. Computational considerations are discussed.Dr. Falk's research was supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under AFOSR Contract No. 73–2504.     

The upper envelope of voronoi surfaces and its applications

Given a setS ofsources (points or segments) in 211C;^d, we consider the surface in 211C; ^d+1 that is the graph of the functiond(x)=min _pS (x, p) for some metric. This surface is closely related to the Voronoi diagram, Vor(S), ofS under the metric. The upper envelope of a set of theseVoronoi surfaces, each defined for a different set of sources, can be used to solve the problem of finding the minimum Hausdorff distance between two sets of points or line segments under translation. We derive bounds on the number of vertices on the upper envelope of a collection of Voronoi surfaces, and provide efficient algorithms to calculate these vertices. We then discuss applications of the methods to the problems of finding the minimum Hausdorff distance under translation, between sets of points and segments.The first author was supported in part by NSF PYI Grant IRI-9057928 and matching funds from General Electric, Kodak, and Xerox, and by U.S. Air Force Contract AFOSR-91-0328. The second and third authors were supported by the Fund for Basic Research administered by the Israeli Academy of Sciences. The second author was also supported by a fellowship from the Pikkowski-Valazzi Fund and by the Eshkol Grant 04601-90 from the Israeli Ministry of Science and Technology. The third author was also supported by Office of Naval Research Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, by grants from the U.S.-Israeli Binational Science Foundation, from the Basic Research Fund administered by the Israeli Academy of Sciences, and from G.I.F., the German-Israeli Foundation for Scientific Research and Development.