Additively decomposed quasiconvex functions

Letf be a real-valued function defined on the product ofm finite-dimensional open convex setsX ₁, ,X _m .Assume thatf is quasiconvex and is the sum of nonconstant functionsf ₁, ,f _m defined on the respective factor sets. Then everyf _i is continuous; with at most one exception every functionf _i is convex; if the exception arises, all the other functions have a strict convexity property and the nonconvex function has several of the differentiability properties of a convex function.We define the convexity index of a functionf _i appearing as a term in an additive decomposition of a quasiconvex function, and we study the properties of that index. In particular, in the case of two one-dimensional factor sets, we characterize the quasiconvexity of an additively decomposed functionf either in terms of the nonnegativity of the sum of the convexity indices off ₁ andf ₂, or, equivalently, in terms of the separation of the graphs off ₁ andf ₂ by means of a logarithmic function. We investigate the extension of these results to the case ofm factor sets of arbitrary finite dimensions. The introduction discusses applications to economic theory.     

Minimal helix surfaces in <Emphasis Type="Italic">N</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>×ℝ

An immersed surface M in N ⁿ ×ℝ is a helix if its tangent planes make constant angle with ∂ _t . We prove that a minimal helix surface M, of arbitrary codimension is flat. If the codimension is one, it is totally geodesic. If the sectional curvature of N is positive, a minimal helix surfaces in N ⁿ ×ℝ is not necessarily totally geodesic. When the sectional curvature of N is nonpositive, then M is totally geodesic. In particular, minimal helix surfaces in Euclidean n-space are planes. We also investigate the case when M has parallel mean curvature vector: A complete helix surface with parallel mean curvature vector in Euclidean n-space is a plane or a cylinder of revolution. Finally, we use Eikonal f functions to construct locally any helix surface. In particular every minimal one can be constructed taking f with zero Hessian.     

An extension of Alexandrov?s theorem on second derivatives of convex functions

If f is a function of n variables that is locally L¹ approximable by a sequence of smooth functions satisfying local L¹ bounds on the determinants of the minors of the Hessian, then f admits a second order Taylor expansion almost everywhere. This extends a classical theorem of A.D. Alexandrov, covering the special case in which f is locally convex.     

Initial-value problems for linear partial difference equations

The method presented in [4] for the solution of linear difference equations in a single variable is extended to some equations in two variables. Every linear combination of a given functionf and of its partial differences can be obtained by the discrete convolution product off by a suitable functionl (which depends on the considered linear combination), and we want to solve in a convolutional form difference equations in the whole plane. However, the convolution of two functions may not be possible if their supports contain half straight lines with opposite directions. To avoid this, we take four sets of functions corresponding to the quadrants such thatl belong to every set, every set endowed with the convolution and with the usual addition is a ring, and there is an inverse ofl in each of the four rings. This is attained by taking, for each ring, a set of functions whose supports belong to suitable cones. After choosing such rings, a very natural initial-value first-order Cauchy Problem (in partial differences) is reduced to a convolutional form. This is done either by a direct method or by introducing the forward difference functions _i f(i=1,2) in a general way depending on the shape of the support off so that Laplace-like formulas with initial and final values) hold. Applications to difference equations in the whole plane and to partial differential problems are made.     

A note on functions whose local minima are global

In this note, we introduce a new class of generalized convex functions and show that a real functionf which is continuous on a compact convex subsetM of ⁿ and whose set of global minimizers onM is arcwise-connected has the property that every local minimum is global if, and only if,f belongs to that class of functions.     

Über Mittelwerte multiplikativer zahlentheoretischer Funktionen mehrerer Variablen

In [8] the author extended the concept of neighbouring functions (cp. [9]) to the case of several variables. Using these results it is shown that under some weak conditions a multiplicative functionf in two variables has a mean-value different from zero if and only if the two multiplicative functionsf ₁(n)=f(n, 1) andf ₂(n)=f(1,n) have mean-values different from zero. Applications to theorems ofDelange [3],Elliott [6] andDaboussi [1] are given.     

Pressure and equilibrium states for countable state markov shifts

We give a general definition of the topological pressureP _top (f, S) for continuous real valued functionsf: X→ℝ on transitive countable state Markov shifts (X, S). A variational principle holds for functions satisfying a mild distortion property. We introduce a new notion of Z-recurrent functions. Given any such functionf, we show a general method how to obtain tight sequences of invariant probability measures supported on periodic points such that a weak accumulation pointμ is an equilibrium state forf if and only if εf ⁻ dμ<∞. We discuss some conditions that ensure this integrability. As an application we obtain the Gauss measure as a weak limit of measures supported on periodic points.     

Functions of bounded boundary rotation

Classes of functionsU _k, which generalize starlike functions in the same manner that the classV _k of functions with boundary rotation bounded bykπ generalizes convex functions, are defined. The radius of univalence and starlikeness is determined. The behavior off _α(z) = ∫ ₀ ^z [f'(t)]^α dt is determined for various classes of functions. It is shown that the image of |z|<1 underV _kfunctions contains the disc of radius 1/k centered at the origin, andV _k functions are continuous in |z|≦1 with the exception of at most [k/2+1] points on |z|=1.     

On the Lipschitzian properties of polyhedral multifunctions

In this paper, we show that for a polyhedral multifunctionF:R ⁿ →R ^m with convex range, the inverse functionF ⁻¹ is locally lower Lipschitzian at every point of the range ofF (equivalently Lipschitzian on the range ofF) if and only if the functionF is open. As a consequence, we show that for a piecewise affine functionf:R ⁿ →R ⁿ ,f is surjective andf ⁻¹ is Lipschitzian if and only iff is coherently oriented. An application, via Robinson's normal map formulation, leads to the following result in the context of affine variational inequalities: the solution mapping (as a function of the data vector) is nonempty-valued and Lipschitzian on the entire space if and only if the solution mapping is single-valued. This extends a recent result of Murthy, Parthasarathy and Sabatini, proved in the setting of linear complementarity problems. Research supported by the National Science Foundation Grant CCR-9307685.     

Univalent mappings associated with the Roper-Suffridge extension operator

The Roper-Suffridge extension operator provides a way of extending a (locally) univalent functionfεH(U) to a (locally) biholomorphic mappingF∈H(B_n). In this paper, we give a simplified proof of the Roper-Suffridge theorem: iff is convex, then so isF. We also show that iff∈S ^*, theF is starlike and that iff is a Bloch function inU, thenF is a Bloch mapping onB _n. Finally, we investigate some open problems. Partially supported by the Natural Sciences and Engineering Research Council of Canada under grant A9221.     

Topological Complexity with Continuous Operations

The topological complexity of algorithms is studied in a general context in the first part and for zero-finding in the second part. In the first part thelevel of discontinuityof a functionfis introduced and it is proved that it is a lower bound for the total number of comparisons plus 1 in any algorithm computingfthat uses only continuous operations and comparisons. This lower bound is proved to be sharp if arbitrary continuous operations are allowed. Then there exists even a balanced optimal computation tree forf. In the second part we use these results in order to determine the topological complexity of zero-finding for continuous functionsfon the unit interval withf(0) ·f(1) < 0. It is proved that roughly log₂log₂?⁻¹comparisons are optimal during a computation in order to approximate a zero up to ?. This is true regardless of whether one allows arbitrary continuous operations or just function evaluations, the arithmetic operations {+, −, *, /}, and the absolute value. It is true also for the subclass of nondecreasing functions. But for the subclass of increasing functions the topological complexity drops to zero even for the smaller class of operations.     

Measured creatures

We prove that two basic questions on outer measure are undecidable. First we show that consistently every sup-measurable functionf: ℝ² → ℝ is measurable. The interest in sup-measurable functions comes from differential equations and the question for which functionsf: ℝ² → ℝ the Cauchy problemy′=f(x,y), y(x₀)=y₀ has a unique almost-everywhere solution in the classAC _t(ℝ) of locally absolutely continuous functions on ℝ. Next we prove that consistently every functionf: ℝ → ℝ is continuous on some set of positive outer Lebesgue measure. This says that in a strong sense the family of continuous functions (from the reals to the reals) is dense in the space of arbitrary such functions. For the proofs we discover and investigate a new family of nicely definable forcing notions (so indirectly we deal with nice ideals of subsets of the reals—the two classical ones being the ideal of null sets and the ideal of meagre ones). Concerning the method, i.e., the development of a family of forcing notions, the point is that whereas there are many such objects close to the Cohen forcing (corresponding to the ideal of meagre sets), little has been known on the existence of relatives of the random real forcing (corresponding to the ideal of null sets), and we look exactly at such forcing notions. The first author thanks The Hebrew University of Jerusalem for support during his visits to Jerusalem and the KBN (Polish Committee of Scientific Research) for partial support through grant 2P03A03114. The research of the second author was partially supported by the Israel Science Foundation. Publication 736.     

On the Slowly Well Orderedness of εo

For α < ε₀, N_α denotes the number of occurrences of ω in the Cantor normal form of α with the base ω. For a binary number-theoretic function f let B(K; f) denote the length n of the longest descending chain (α₀, …, α_n–1) of ordinals <ε₀ such that for all i < n, Nα_i ≤ f (K, i). Simpson [2] called ε₀ as slowly well ordered when B (K; f) is totally defined for f (K; i) = K · (i+ 1). Let |n| denote the binary length of the natural number n, and |n|_k the k-times iterate of the logarithmic function |n|. For a unary function h let L(K; h) denote the function B (K; h₀(K; i)) with h₀(K, i) = K + |i| · |i|_h(i). In this note we show, inspired from Weiermann [4], that, under a reasonable condition on h, the functionL (K; h) is primitive recursive in the inverse h^–1 and vice versa.     

Quermassintegrals of a random polytope in a convex body

Let K be a convex body in \mathbbRⁿ \mathbb{R}^n with volume |K| = 1 |K| = 1 . We choose N 3 n+1 N \geq n+1 points x₁,?, x_N x_1,\ldots, x_N independently and uniformly from K, and write C(x₁,?, x_N) C(x_1,\ldots, x_N) for their convex hull. Let f : \mathbbR⁺ ? \mathbbR⁺ f : \mathbb{R^+} \rightarrow \mathbb{R^+} be a continuous strictly increasing function and 0 ￡ i ￡ n-1 0 \leq i \leq n-1 . Then, the quantity¶¶E (K, N, f °W_i) = ò_K ?ò_K f[W_i(C(x₁, ?, x_N))]dx_N ?dx₁ E (K, N, f \circ W_{i}) = \int\limits_{K} \ldots \int\limits_{K} f[W_{i}(C(x_1, \ldots, x_N))]dx_{N} \ldots dx_1 ¶¶is minimal if K is a ball (W_i is the i-th quermassintegral of a compact convex set). If f is convex and strictly increasing and 1 ￡ i ￡ n-1 1 \leq i \leq n-1 , then the ball is the only extremal body. These two facts generalize a result of H. Groemer on moments of the volume of C(x₁,?, x_N) C(x_1,\ldots, x_N) .     

Convex minimization under Lipschitz constraints

We consider the problem of minimizing a convex functionf(x) under Lipschitz constraintsf _i (x)0,i=1,...,m. By transforming a system of Lipschitz constraintsf _i (x)0,i=l,...,m, into a single constraints of the formh(x)-x²0, withh(·) being a closed convex function, we convert the problem into a convex program with an additional reverse convex constraint. Under a regularity assumption, we apply Tuy's method for convex programs with an additional reverse convex constraint to solve the converted problem. By this way, we construct an algorithm which reduces the problem to a sequence of subproblems of minimizing a concave, quadratic, separable function over a polytope. Finally, we show how the algorithm can be used for the decomposition of Lipschitz optimization problems involving relatively few nonconvex variables.     

Almost Optimal Differentiation Using Noisy Data

We study differentiation of functionsfbased on noisy dataf(t_i)+_i. We recoverf^(k)either at a single point or on the interval [0, 1] inL₂-norm. Under stochastic assumptions onfand_i, we determine the order of the errors of the best linear methods which use n noisy function values. Polynomial interpolation for the pointwise problem and smoothing splines for the problem inL₂-norm are shown to be almost optimal. The analysis involves worst case estimates in reproducing kernel Hilbert spaces and a Landau inequality.     

Extensions of the measurable choice theorem by means of forcing

Using the method of forcing of set theory, we prove the following two theorems on the existence of measurable choice functions: LetT be the closed unit interval [0,1] and letm be the usual Lebesgue measure defined on the Borel subsets ofT. Theorem1. LetS⊂T×T be a Borel set such that for alltεT,S _t ^def={x|(t,x)εS} is countable and non-empty. Then there exists a countable series of Lebesgue-measurable functionsf _n: T→T such thatS _t={f_n(t)|nεω} for alltε[0,1],W _x={y|(x,y)εW} is uncountable. Then there exists a functionh:[0,1]×[0,1]→W with the following properties: (a) for each xε[0,1], the functionh(x,·) is one-one and ontoW _x and is Borel measurable; (b) for eachy, h(·, y) is Lebesgue measurable; (c) the functionh is Lebesgue measurable.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Imperfect conjugate gradient algorithms for extended quadratic functions

Summary Generalized conjugate gradient algorithms which are invariant to a nonlinear scaling of a strictly convex quadratic function are described. The algorithms when applied to scaled quadratic functionsfR _n R ₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹(R ₁) an arbitrary strictly monotone functionh generate the same direction vectors as for the functionF without perfect steps.     

A global optimization approach for solving the convex multiplicative programming problem

We consider a convex multiplicative programming problem of the form% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaGG7bGaam% OzamaaBaaaleaacaaIXaaabeaakiaacIcacaWG4bGaaiykaiabgwSi% xlaadAgadaWgaaWcbaGaaGOmaaqabaGccaGGOaGaamiEaiaacMcaca% GG6aGaamiEaiabgIGiolaadIfacaGG9baaaa!4A08!\[\{ f_1 (x) \cdot f_2 (x):x \in X\} \]where X is a compact convex set of ⁿ and f ₁, f ₂ are convex functions which have nonnegative values over X.Using two additional variables we transform this problem into a problem with a special structure in which the objective function depends only on two of the (n+2) variables. Following a decomposition concept in global optimization we then reduce this problem to a master problem of minimizing a quasi-concave function over a convex set in ² ₂. This master problem can be solved by an outer approximation method which requires performing a sequence of simplex tableau pivoting operations. The proposed algorithm is finite when the functions f _i, (i=1, 2) are affine-linear and X is a polytope and it is convergent for the general convex case.Partly supported by the Deutsche Forschungsgemeinschaft Project CONMIN.