On nonconvex optimization problems with separated nonconvex variables

A mathematical programming problem is said to have separated nonconvex variables when the variables can be divided into two groups: x=(x ₁,...,x _n ) and y=( y ₁,...,y _n ), such that the objective function and any constraint function is a sum of a convex function of (x, y) jointly and a nonconvex function of x alone. A method is proposed for solving a class of such problems which includes Lipschitz optimization, reverse convex programming problems and also more general nonconvex optimization problems.     

Longest convex chains

Assume X_n is a random sample of n uniform, independent points from a triangle T. The longest convex chain, Y, of X_n is defined naturally (see the next paragraph). The length |Y| of Y is a random variable, denoted by L_n. In this article, we determine the order of magnitude of the expectation of L_n. We show further that L_n is highly concentrated around its mean, and that the longest convex chains have a limit shape. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Weighted Polynomial Approximation for Convex External Fields

It is proven that if Q is convex and w(x)= exp(-Q(x)) is the corresponding weight, then every continuous function that vanishes outside the support of the extremal measure associated with w can be uniformly approximated by weighted polynomials of the form w ⁿ P _n . This solves a problem of P. Borwein and E. B. Saff. Actually, a similar result is true locally for any parts of the extremal support where Q is convex. February 10, 1998. Date revised: July 23, 1998. Date accepted: August 17, 1998.     

The central limit theorem for Carleman’s equation

The purpose of this paper is to discuss the analogy between the law of large numbers and the central limit theorem of classical probability theory on the one hand and the hydrodynamical approximations in the statistical mechanics of gases on the other. The chief illustration is provided by Carleman's model [2] for which the central limit approximation is a kind of non-linear Brownian motion regulated by ∂n/∂t=(n'/n)^′. Research supported by the National Science Foundation under NSF Grant NSF-GP-37069X1.     

Subdivision algorithms and the kernel of a polyhedron

The kernelK of a convex polyhedronP ₀, as defined by L. Fejes Tóth, is the limit of the sequence (P _n), whereP _n is the convex hull of the midpoints of the edges ofP _n−1. The boundary ∂K of the convex bodyK is investigated. It is shown that ∂K contains no two-dimensional faces and that ∂K need not belong toC ². The connection with similar algorithms from CAD (computer aided design) is explained and utilized. R. J. Gardner was supported in part by a von Humboldt fellowship.     

Uniformly converging random variables for weakly converging laws

 Let {P _n , n ?ℕ} be a sequence of Borel probability measures on a compact and connected metric space X. We show that in case the measures P _n converge weakly to a fully supported limit measure P, there exist uniformly converging random variables X _n , n ?ℕ with these given laws. Connectivity and compactness are necessary conditions for our theorem to hold. We also present a decent generalization. We prove our theorem by means of a comparison of the Prokhorov and the so-called minimal L ^∞ metric. Then we only need to use the Strassen-Dudley theorem and Kellerer's measure extension theorem for decomposable families. Received: 2 November 2000 / Revised version: 5 January 2002/ Published online: 1 July 2002     

Test for properness using residue calculus

We will consider global problems in the ringK[X ₁, …,X _n] on the polynomials with coefficients in a subfieldK ofC. LetP=(P ₁, …,P _n):K ⁿ →K ⁿ be a polynomial map such that (P ₁,…,P _n) is a quasi-regular sequence generating a proper ideal, the main thing we do is to use the algebraic residues theory (as described in [5]) as a computational tool to give some result to test when a map (P ₁, …,P _n) is a proper map by computing a finite number of residue symbols.     

An extension of a result of ribe

It is proved that for every 1≦p<∞, 1≦q<∞ and for every sequence {p _n}, 1≦p _n<∞,p _n→p, the spaceX=(Σ⊕l _{p n}) _q (resp.U=(Σ⊕L _{p n}(0, 1)) _q ) is uniformly homeomorphic toX⊕l _p (resp.U⊕L _p(0, 1)). This extends Ribe’s result from the casep=1 to generalp<∞ and thus provides examples of uniformly convex, uniformly homeomorphic Banach spaces which are not Lipschitz equivalent.     

Limit theorems for empirical processes

Summary The empirical measure P _n for iid sampling on a distribution P is formed by placing mass n ^–1 at each of the first n observations. Generalizations of the classical Glivenko-Cantelli theorem for empirical measures have been proved by Vapnik and ervonenkis using combinatorial methods. They found simple conditions on a class C to ensure that sup {|P _n (C) – P(C)|: C C} converges in probability to zero. They used a randomization device that reduced the problem to finding exponential bounds on the tails of a hypergeometric distribution. In this paper an alternative randomization is proposed. The role of the hypergeometric distribution is thereby taken over by the binomial distribution, for which the elementary Bernstein inequalities provide exponential boundson the tails. This leads to easier proofs of both the basic results of Vapnik-ervonenkis and the extensions due to Steele. A similar simplification is made in the proof of Dudley's central limit theorem forn ^1/2(P P _n –P)— a result that generalizes Donsker's functional central limit theorem for empirical distribution functions.This research was supported in part by the Air Force Office of Scientific Research, Contract No. F49620-79-C-0164     

The Empty Hexagon Theorem

Let P be a finite set of points in general position in the plane. Let C(P) be the convex hull of P and let Cⁱ_P be the ith convex layer of P. A minimal convex set S of P is a convex subset of P such that every convex set of P ∩ C(S) different from S has cardinality strictly less than |S|. Our main theorem states that P contains an empty convex hexagon if C¹_P is minimal and C⁴_P is not empty. Combined with the Erdos-Szekeres theorem, this result implies that every set P with sufficiently many points contains an empty convex hexagon, giving an affirmative answer to a question posed by Erdos in 1977.     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.     

Affinely Regular Polygons as Extremals of Area Functionals

For any convex n-gon P we consider the polygons obtained by dropping a vertex or an edge of P. The area distance of P to such (n−1)-gons, divided by the area of P, is an affinely invariant functional on n-gons whose maximizers coincide with the affinely regular polygons. We provide a complete proof of this result. We extend these area functionals to planar convex bodies and we present connections with the affine isoperimetric inequality and parallel X-ray tomography.     

Non-conflicting ordering cones and vector optimization in inductive limits

Let (E, ξ)= ind (E_n, ξ_n) be an inductive limit of a sequence (E_n, ξ_n)_{n∈ N} of locally convex spaces and let every step (E_n, ξ_n) be endowed with a partial order by a pointed convex (solid) cone S_n. In the framework of inductive limits of partially ordered locally convex spaces, the notions of lastingly efficient points, lastingly weakly efficient points and lastingly globally properly efficient points are introduced. For several ordering cones, the notion of non-conflict is introduced. Under the requirement that the sequence (S_n)_{n∈ N} of ordering cones is non-conflicting, an existence theorem on lastingly weakly efficient points is presented. From this, an existence theorem on lastingly globally properly efficient points is deduced.     

Convergence theorems for the Birkhoff integral

We give sufficient conditions for the interchange of the operations of limit and the Birkhoff integral for a sequence (f _n ) of functions from a measure space to a Banach space. In one result the equi-integrability of f _n ’s is involved and we assume f _n → f almost everywhere. The other result resembles the Lebesgue dominated convergence theorem where the almost uniform convergence of (f _n ) to f is assumed.     

On the unlinking conjecture of independent polynomial functions

The celebrated U-conjecture states that under the N_n(0,I_n) distribution of the random vector X=(X₁,…,X_n) in Rⁿ, two polynomials P(X) and Q(X) are unlinkable if they are independent [see Kagan et al., Characterization Problems in Mathematical Statistics, Wiley, New York, 1973]. Some results have been established in this direction, although the original conjecture is yet to be proved in generality. Here, we demonstrate that the conjecture is true in an important special case of the above, where P and Q are convex nonnegative polynomials with P(0)=0.     

The Compression Property for Affine Variational Inequalities

In 1965, Gale and Nikaidô showed that for any n × n P-matrix A, the only nonnegative vector that A sends into a nonpositive vector is the origin. They applied that result to derive various results including univalence properties of certain nonlinear functions. In this article, we show that an extension of their result holds with the nonnegative orthant replaced by any nonempty polyhedral convex cone. In place of the P-matrix condition, we require a determinantal condition that we call the compression property. When the polyhedral convex cone is the nonnegative orthant, the compression property reduces to the property of being a P-matrix and we recover the Gale-Nikaidô result. We apply the extended theorem to derive tools useful in the analysis of affine variational inequalities over polyhedral convex cones.     

Some remarks on trigonometric interpolation

The object of this paper is to consider the problem of (0, 1, 2, 4) trigonometric interpolation when nodes are taken to bex _kn=(2kπ/n),k=0, 1 …,n−1. Here the interpolatory polynomials are explicitly constructed and the corresponding convergence theorem is proved, which is shown to be best possible in a certain sense. It is interesting to compare these results with those of Saxena [6], where the convergence theorem requires the existence off ^m (x). I take this opportunity to express my thanks to Professor P. Turán for some valuable conversation which led to this work. The author is at present a member of the faculty of the Dept. of Mathematics, University of Florida, Gainesville, U.S.A.     

Expectation of random polytopes

A random polytopeP _n in a convex bodyC is the convex hull ofn identically and independently distributed points inC. Its expectation is a convex body in the interior ofC. We study the deviation of the expectation ofP _n fromC asn→∞: while forC of classC ^k+1,k≥1, precise asymptotic expansions for the deviation exist, the behaviour of the deviation is extremely irregular for most convex bodiesC of classC ¹. Dedicated to my teacher and friend Professor Edmund Hlawka on the occasion of his 80^th birthday     

On the convex approximation property and the asymptotic behavior of nonlinear contractions in Banach spaces

We prove that ifC is a bounded closed convex subset of a uniformly convex Banach space,T:C→C is a nonlinear contraction, andS _n =(I+T+…+T ⁿ⁻¹ )/n, then lim _n ‖S _n (x)−TS _n (x)‖=0 uniformly inx inC. T also satisfies an inequality analogous to Zarantonello’s Hilbert space inequality. which permits the study of the structure of the weak ω-limit set of an orbit. These results are valid forB-convex spaces if some additional condition is imposed on the mapping. Partially supported by NSF Grant MCS-7802305A01.