(2012-10-27) Convex Sets
A set is convex if it contains every segment between two of its points.
In a linear space over the field of
real numbers, the segment between the points A and
B is the following set:
{ (1-u) A + u B |
u Î [0,1] }
In this, [0,1] denotes the interval
consisting of all real numbers between 0 and 1
(both extremities included).
A subset of a real linear space is said to be convex
if it contains all the segments between every pair of its points.
Convexity is not defined for linear spaces whose scalar fields are not
endowed with a total ordering relation
(e.g., p-adic numbers).
(2016-01-27) Convex Functions
A convex function is almost everywhere second-order differentiable.
A real-valued function f of a vectorial variable is said to be
convex when it's defined over a
convexopen set V
and the following holds:
" A Î V ,
" B Î V ,
" u Î ]0,1[ ,
f ( (1-u) A + u B )
≤
(1-u) f ( A ) + u f ( B )
f is strictly convex
if that inequality is always strict for distinct A & B.
Alexandrov's theorem for n-dimensional Euclidean space :
Aleksandrov's theorem states that, almost everywhere, all second-order partial derivatives
of a convex function exist
and the Hessian matrix
formed by them is positive semi-definite.
For the Euclidean plane, that was first proved in 1936 by
Herbert Busemann
(1905-1994) and
William Feller (1906-1970):
Krümmungseigenschaften konvexer Flächen,
Acta Mathematica, 66, pp. 1-47.
The theorem was extended in 1939 by Alexandrov to any convex real-valued function f
of an n-dimensional Euclidean variable.
(2013-04-18) Aspect ratio (absolute or relative to a given "vertical")
The aspect ratio of a convex body is its length divided by its height.
Technically, the width of a convex shape depends on
the direction with respect to which it is measured:
It's the least possible distance of two parallel planes perpendicular to that direction and surrounding the body.
It's what a sliding calipers measures.
The height of the shape can be given either of the following definitions:
The least width (the measurement direction is called vertical ).
The width along a prescribed direction, identified as vertical a priori.
The former definition is called absolute,
the latter is dubbed relative.
In either case, the length of the body is then defined
as the largest width along an horizontal direction
(a direction is said to be horizontal when it's perpendicular to
the aforementioned vertical direction).
Either way, the aspect ratio of a body is its length to height ratio.
Either flavor of aspect ratio can be a convenient parameter to use
when discussing the geometry of a family of objects.
It makes little sense for nonconvex things, except by considering their
convex hulls.
An absolute aspect ratio is never less than unity.
A relative aspect ratio can be.
Trivia: The Aspect Ratios of a Rectangle
The aspect ratio normally quoted for a rectangle is, in fact, its
relative aspect ratio when the smaller side is vertical.
It's an exercise in elementary
trigonometry (left to the reader)
to show that the absolute aspect ratio differs from that by
a factor of 2 cos2 q ,
where q is the angle between the
longer side and the diagonal (that's between 0° and 45°).
In other words:
Usual aspect ratio = 1 / tg q
Absolute aspect ratio = 1 / sin 2q
Curiously, the absolute aspect ratio of a very shallow rectangle is thus
about half its aspect ratio in the usual sense of the term!
The diameter of a body is simply its largest width.
For example, the diameter of a rectangle is equal to its diagonal.
(2012-10-27) The closed unit ball of a norm.
A nontrivial closed convex set, symmetric about 0,
characterizes a norm.
The unit ball
associated with a norm is defined as the
set of all vectors whose norm is less than or equal to 1.
The basic properties of a norm
always make this a
closedconvex set
symmetric about the origin (i.e., it contains -V
if it contains V )
and containing more than 0 itself (except in the trivial case of the space {0}
of dimension zero).
Conversely (Minkowski)
any such set B uniquely specifies a norm of which it is the
unit ball, the norm of a vector V being
defined as:
|| V || = inf
{ |x| | V Î x B }
The above definition of a norm from a convex, origin-symmetric, closed body
B is called Minkowski's functional.
The notation x B was introduced by Minkowski himself.
It denotes the set of all vectors that are equal to the scalar x
multiplied into some element of B.
Likewise, Minkowski defined the sum A+B of two sets of vectors
as the set of all vectors that can be obtained by adding together an element of
A and an element of B.
Similarly, any well-defined operation on the elements of sets induces a natural
extension of that operation to sets themselves, which is sometimes called a
Minkowski operation on sets
(the most common is Minkowski addition,
which has nice convexity properties).
(2012-10-27) Convex hull (or convex envelope ) :
Conv (S)
The smallest convex set containing a given set of points S.
The intersection of any family of convex sets is itself convex.
(HINT: If two points are in that intersection,
so is the segment between them.)
Therefore, the intersection of all convex sets that contain a set S
of vectors is a convex set containing S. It's clearly the smallest such set.
It's called the convex hull of S
and it's usually denoted Conv (S).
The convex hull of a sum of sets is the sum of their convex hulls:
Conv ( S1 + S2 ) =
Conv ( S1 ) + Conv ( S2 )
A convex hull is not necessarily closed.
(Consider, for example, an open halfspace together with a single point on its boundary.)
The closure of Conv (S) is the convex hull
of the closure of S. It's called the closed convex hull of S :
Conv ( S )
=
Conv ( S )
As discussed next, a closed convex set is the
intersection of all [closed] halfspaces that contain it.
The closure of the convex hull of S (or, equivalently, the
convex hull of the closure of S) is the intersection
of all halfspaces that contain S.
Wikipedia :Shapley-Folkman lemma :
The [Minkowski] sum of many sets is nearly convex.
(2012-11-03) Intersections of closed halfspaces.
Any closed convex set is an intersections of [infinitely many] halfspaces.
An hyperplane separates space into three disjoint regions;
itself and two open halfspaces.
A closed halfspace is obtained as the union of the hyperplane with
either of the two open halfspaces it borders.
When we say that any closed convex set is the intersection of halfspaces,
we're normally thinking about closed ones.
It's "more economical" to do so, but it's not strictly necessary
(since a closed halfspace containing
S is clearly the intersection of infinitely many open halfspaces).
The converse proposition only holds for closed halfspaces, though.
An intersection of any family of closed
sets is guaranteed to be closed (an infinite intersection of open sets could be open,
closed or neither).
(2012-10-27) Polar (or dual )
of a closed convex set.
Duality with respect to Euclidean scalar product (dot product).
In Euclidean space (i.e., real linear space endowed
with a positive-definite scalar product) a linear hyperplane
can be defined as the set of all vectors orthogonal to a prescribed nonzero vector.
An affine hyperplane (or, simply, an hyperplane)
is obtained by adding to some point every vector from such a linear hyperplane.
An hyperplane which does not go through the origin can be characterized
by an othogonal vector H pointing to it from the origin
with a length equal to the inverse of the Euclidean distance from the origin. That hyperplane
is the set of all vectors whose dot-product into H is equal to 1 :
{ V | V.H = 1 }
The hyperplane is the border
of a closed half-plane containing the origin:
{ V | V.H ≤ 1 }
As stated in the previous section, we may always define
any closed convex set C as the intersection
of (possibly infinitely many) such closed half-spaces, namely:
C = { V |
"HÎC' ,
V.H ≤ 1 }
All sets C' that yield C in this way have the same convex hull
C* which is called the polar of C.
The bodies C and C* are polars of each other :
C* = { V |
"HÎC ,
V.H ≤ 1 }
C = { V |
"HÎC* ,
V.H ≤ 1 }
If C and C* are polytopes
(resulting from a finite C' )
then their networks of vertices, edges and faces
are topological duals of each other.
The above describes duality with respect to a sphere (or hypersphere) of unit radius centered
at the origin. Any center and any radius could be used in practice.
(2012-10-27) Minkowski's separation theorem(s)
(Minkowski).
Two disjoint convexes belong to two closed adjoining halfspaces.
If the two disjoint convex sets are neither open nor closed,
the hyperplane at the border of the two halfspaces may intersect both convexes...
Consider, for example, the following bounded planar regions:
{ (x,y) | x2+y2 ≤ 1 and either y > 0 or [ y = 0 & x > 0 ] }
{ (x,y) | x2+y2 ≤ 1 and either y < 0 or [ y = 0 & x < 0 ] }
Each region is convex and the two are disjoint.
Only one straight line (of equation y = 0)
can be drawn "between" them, but it intersects both.
If both sets are closed, one of them can be contained in a closed
halfspace which doesn't intersect the other. [ Conjecture. ]
If at least one of them is compact, then two disjoint
closed convex sets can always be
separated by an hyperplane which doesn't intersect either set
(in fact, infinitely many such hyperplanes exist, in that case).
Two open disjoint convex sets
can always be separated by
at least one hyperplane that doesn't intersect either of them.
(2013-01-01) Strict separation of two closed convex sets :
If one is compact, two closed
convexes are separated by an hyperplane.
The theorem doesn't apply for closed sets if neither is compact. Example:
{ (x,y) | 0 < 1/x ≤ y }
{ (x,y) | y ≤ 0 }
Both regions are convex and closed, yet no straight line separates them.
(HINT: To separate anything from the
lower convex set (blue) a straight line must have zero slope
and positive intercept.)
Proof (two closed convexes, one compact) :
Let A and B be two disjoint convexes
in the vector space E,
such that A is compact and B is closed.
Consider the following function f,
defined for any point M of E :
f (M) = inf { d(M,x) | x Î B }
f is well-defined because any set of nonnegative reals has a lower bound.
It is continuous.
(2013-01-02) Strict separation of two open convexes :
Two disjoint open
convexes are always separated by an hyperplane.