Extremal approximately convex functions and estimating the size of convex hulls

DOI10.1006/AIMA.1999.1836MaRDI QIDQ1969013zbMATH OpenOpenAlexFDO

Authors Ralph Howard, James W. Roberts, S. J. Dilworth

Publication date 3 December 2000

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9807107

approximately convex function approximately convex set convex hull

Convexity of real functions of several variables, generalizations (26B25) Methods involving semicontinuity and convergence; relaxation (49J45) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Approximation by convex sets (52A27) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Abstract: A real valued function

f

defined on a convex

K

is anemconvex function iff it satisfies

f((x+y)/2) le (f(x)+f(y))/2 + 1.

A thorough study of approximately convex functions is made. The principal results are a sharp universal upper bound for lower semi-continuous approximately convex functions that vanish on the vertices of a simplex and an explicit description of the unique largest bounded approximately convex function~

E

vanishing on the vertices of a simplex. A set

A

in a normed space is an approximately convex set iff for all

a, b i n A

the distance of the midpoint

(a + b) / 2

to

A

is

l e 1

. The bounds on approximately convex functions are used to show that in

R^{n}

with the Euclidean norm, for any approximately convex set

A

, any point

z

of the convex hull of

A

is at a distance of at most

[l o g_{2} (n - 1)] + 1 + (n - 1) / 2^{[l o g_{2} (n - 1)]}

from

A

. Examples are given to show this is the sharp bound. Bounds for general norms on

R^{n}

are also given.

Review text

The main result in this paper states that for any norm \(\|\cdot\|\) in \(\mathbb{R}^n\) there is a constant \(C_{\|\cdot\|}\) such that, for every \(A\subset \mathbb{R}^n\) and \(z\) in the convex hull of \(A\), one has \[ \text{dist}(z,A)\leq C_{\|\cdot\|} \sup_{a_0,a_1\in A} \text{dist}(\textstyle{{1\over 2}}(a_0+ a_1), A), \] where \(\text{dist}(x, A):= \inf\{\|x- a\|: a\in A\}\). The sharp constant \(C_{\|\cdot\|}\) satisfies \(\kappa(n-1)\leq C_{\|\cdot\|}\kappa(n)\), with \(\kappa(n)= [\log_2(n)]+ 1+{n\over 2^{[\log_2(n)]}}\) (\([\cdot]\) denoting the greatest integer function), and \(C_{\|\cdot\|}= \kappa(n-1)\) if \(\|\cdot\|\) is the Euclidean norm. The lower bound on \(C_{\|\cdot\|}\) follows from an explicit computation of the largest bounded approximately convex function on the standard \(n\)-dimensional simplex which takes non-positive values on the vertices (a real-valued function \(h\) defined on a convex subset \(E\) of a normed space is said to be approximately convex iff for all \(a,b\in E\) it satisfies \(h({1\over 2}(a+ b))\leq {1\over 2}(h(a)+ h(b)+ 1)\). To apply this computation to the derivation of the main result one considers approximately convex sets, that is, sets \(A\) for which the function \(\text{dist}(.,A)\) is approximately convex.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Extremal approximately convex functions and estimating the size of convex hulls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969013)