Continuity of lower envelopes

The purpose of the paper is to give a complete characterization of the continuity of lower envelopes in the infinite dimensional spaces. The characterization of upper or lower semicontinuity of envelopes, when stated in the language of multifunctions, has a dual geometric character which depends on the upper or lower semicontinuity of the corresponding multifunction.     

The weak lower semicontinuity of the Kobayashi distance and its applications

In this paper we prove the lower semicontinuity with respect to the weak topology of the Kobayashi distance in a bounded, convex and open subset of a reflexive Banach space. We apply this result to the Denjoy-Wolff theorem for condensing mappings in the unit open ball in a strictly convex reflexive Banach space with the Kadec-Klee property. Received June 30, 1998 / in final form December 20, 1999 / Published online July 20, 2000     

Convex extensions and envelopes of lower semi-continuous functions

 We define a convex extension of a lower semi-continuous function to be a convex function that is identical to the given function over a pre-specified subset of its domain. Convex extensions are not necessarily constructible or unique. We identify conditions under which a convex extension can be constructed. When multiple convex extensions exist, we characterize the tightest convex extension in a well-defined sense. Using the notion of a generating set, we establish conditions under which the tightest convex extension is the convex envelope. Then, we employ convex extensions to develop a constructive technique for deriving convex envelopes of nonlinear functions. Finally, using the theory of convex extensions we characterize the precise gaps exhibited by various underestimators of $x/y$ over a rectangle and prove that the extensions theory provides convex relaxations that are much tighter than the relaxation provided by the classical outer-linearization of bilinear terms. Received: December 2000 / Accepted: May 2002 Published online: September 5, 2002 RID="*" ID="*" The research was funded in part by a Computational Science and Engineering Fellowship to M.T., and NSF CAREER award (DMI 95-02722) and NSF/Lucent Technologies Industrial Ecology Fellowship (NSF award BES 98-73586) to N.V.S. Key words. convex hulls and envelopes – multilinear functions – disjunctive programming – global optimization     

New bounds for lower envelopes in three dimensions,with applications to visibility in terrains

We consider the problem of bounding the complexity of the lower envelope ofn surface patches in 3-space, all algebraic of constant maximum degree, and bounded by algebraic arcs of constant maximum degree, with the additional property that the interiors of any triple of these surfaces intersect in at most two points. We show that the number of vertices on the lower envelope ofn such surface patches is , for some constantc depending on the shape and degree of the surface patches. We apply this result to obtain an upper bound on the combinatorial complexity of the “lower envelope” of the space of allrays in 3-space that lie above a given polyhedral terrainK withn edges. This envelope consists of all rays that touch the terrain (but otherwise lie above it). We show that the combinatorial complexity of this ray-envelope is for some constantc; in particular, there are at most that many rays that pass above the terrain and touch it in four edges. This bound, combined with the analysis of de Berget al. [4], gives an upper bound (which is almost tight in the worst case) on the number of topologically different orthographic views of such a terrain. Work on this paper by the first author has been supported by a Rothschild Postdoctoral Fellowship. Work on this paper by the second author has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

The Banach envelopes of Besov and Triebel-Lizorkin spaces and applications to partial differential equations

With “hat” denoting the Banach envelope (of a quasi-Banach space) we prove that if 0<p<1, 0<q<1, ℝ, while if 0<p<1, 1≤q<+∞, ∝, and if 1≤p<+∞, 0<q<1, ℝ. Applications to questions regarding the global interior regularity of solutions to Poisson type problems for the three-dimensional Lamé system in Lipschitz domains are presented.     

Almost tight upper bounds for lower envelopes in higher dimensions

We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of the lower envelope ofn such surface patches isO(n ^d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope isO(n ^d-2λ _q (n)) for some constantq depending on the shape and degree of the surfaces (where λ _q (n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running timeO(n ^2+∈), and give several applications of the new bounds. Work on this paper has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

The Minding formula and its applications

We apply the Minding Formula for geodesic curvature and the Gauss-Bonnet Formula to calculate the total Gaussian curvature of certain 2-dimensional open complete branched Riemannian manifolds, the M\cal M surfaces. We prove that for an M\cal M surface, the total curvature depends only on its Euler characteristic and the local behaviour of its metric at ends and branch points. Then we check that many important surfaces, such as complete minimal surfaces in \Bbb Rⁿ{\Bbb R}^n with finite total curvature, complete constant mean curvature surfaces in hyperbolic 3-space H³ (–1) with finite total curvature, are actually branch point free M\cal M surfaces. Therefore as corollaries we give simple proofs of some classical theorems such as the Chern-Osserman theorem for complete minimal surfaces in \Bbb Rⁿ{\Bbb R}^n with finite total curvature. For the reader's convenience, we also derive the Minding Formula.     

The Schur algorithm and its applications

The Schur algorithm and its time-domain counterpart, the fast Cholseky recursions, are some efficient signal processing algorithms which are well adapted to the study of inverse scattering problems. These algorithms use a layer stripping approach to reconstruct a lossless scattering medium described by symmetric two-component wave equations which model the interaction of right and left propagating waves. In this paper, the Schur and fast Chokesky recursions are presented and are used to study several inverse problems such as the reconstruction of nonuniform lossless transmission lines, the inverse problem for a layered acoustic medium, and the linear least-squares estimation of stationary stochastic processes. The inverse scattering problem for asymmetric two-component wave equations corresponding to lossy media is also examined and solved by using two coupled sets of Schur recursions. This procedure is then applied to the inverse problem for lossy transmission lines.The work of this author was supported by the Exxon Education FoundationThe work of this author was supported by the Air Force Office of Scientific Research under Grant AFOSR-82-0135A.     

The convexity principle and its applications

Recently [1, 2] the new convexity principle has been validated. It states that a nonlinear image of a small ball in a Hilbert space is convex, provided that the map is C^1,1 and the center of the ball is a regular point of the map. This result has numerous applications in linear algebra, optimization and control.Dedicated to IMPA on the occasion of its 50^th anniversary     

The Carleman kernel and its applications

We examine the properties of the Carleman kernel and present some applications to the theory of entire functions and difference operators.     

The all-associativity of octonions and its applications

Using an elementary method, we give a new proof of the all-associativity of octonions. As some applications, the known Taylor theorem is improved, and a new definition and new properties of octonionic determinant are also obtained.     

The normed and Banach envelopes of WeakL 1

The space WeakL ¹ consists of all Lebesgue measurable functions on [0,1] such thatq(f)=supcλ{t:|f(t)|>c} c>0 is finite, where λ denotes Lebesgue measure. Let ρ be the gauge functional of the convex hull of the unit ball {f:q(f)≤1} of the quasi-normq, and letN be the null space of ρ. The normed envelope of WeakL ¹, which we denote byW, is the space (WeakL ¹/N, ρ). The Banach envelope of WeakL ¹, , is the completion ofW. We show that is isometrically lattice isomorphic to a sublattice ofW. It is also shown that all rearrangement invariant Banach function spaces are isometrically lattice isomorphic to a sublattice ofW.     

The incidentor coloring of multigraphs and its applications

A new concept of multigraph coloring—an incidentor coloring is developed in this paper. It is shown that this coloring is a generalization of the ordinary edge coloring and that it can be applied for solving some optimization problems in data networks.     

The theory of thermal potentials and its applications

A review by the author of his dissertation presented for the academic degree of doctor of physico-mathematical sciences. A defense of the dissertation was given on February 29, 1968 before the science committee of the V. A. Steklov Institute of Mathematics of the Academy of Sciences of the USSR. Official challengers were A. V. Bitsadze and A. A. Samarskii, Corresponding Members of the Academy of Sciences of the USSR, and V. P. Mikhailov, Doctor of Physico-Mathematical Sciences.Translated from Matematicheskie Zametki, Vol. 4, No.1, pp. 113–123, July, 1968.     

The outer structure of formation and its applications

Acta Mathematica Sinica, English Series -     

Sharp upper and lower bounds for the spectral radius of a nonnegative irreducible matrix and its applications

In this paper, we obtain the sharp upper and lower bounds for the spectral radius of a nonnegative irreducible matrix. We also apply these bounds to various matrices associated with a graph or a digraph, obtain some new results or known results about various spectral radii, including the adjacency spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance signless Laplacian spectral radius of a graph or a digraph.