Optimization 3 - Convex Analysis

Convex Analysis Review Notes

Or, everything you ever needed to know from… Convex analysis?

Convex Sets

Let . The set is called Convex if for any and , it holds that

A set is convex if, from everywhere in S, all other points are visible. If two points in are chosen, and a line drawn between them, all points on that line should also be in .

If a point can be found such that , then is not convex.

Properties of Convex Sets

  • The set is a convex set
  • The empty set is a convex set
  • The set is convex for every value of
  • The set is non-convex for
  • Finite sets are non-convex (why?)
  • The intersection of two convex sets is also a convex set.


Convex and Affine Hulls and Combinations

Let .

  • An Affine Combination of the points is a vector satisfying:

If the weights additionally satisfy for all , then is called a Convex Combination

  • The Affine Hull, denoted by , is the smallest affine subspace of that includes
    • is the set of all convex combinations of points in
  • The Convex Hull, denoted by , is the smallest convex set that includes
    • is the set of all convex combinations of points in
  • CarathĂ©odory’s Theorem: Let , where . Then can be expressed as a convex combination of or fewer elements.
  • Simmilarly, let , where . Then can be expressed as a affine combination of or fewer elements.

Properties thereof

  • The affine hull of three or more points in not all lying in the same line is itself
  • The affine hull of three or more points in not all lying in the same line is the plane in intersecting those points.
  • The affine hull of an affine space is the space itself.
  • The convex hull of a convex space is the space itself.

Polytopes and Polyhedron

  • A subset of is a Polytope if it is the convex hull of finitely many points in

In layman’s terms, a Polytope is the geometric structure in created by the convex hull . That’s still kinda confusing, so consider these examples:

  • Any polygon in is a polytope
  • A cube, a tetrahedron, and pyramids are all polytopes in
  • circles are not polytopes in
  • Simmilarly spheres are not polytopes in

A point of a convex set is called an Extreme Point if for , , it follows that In other words, an extreme point is a point that is not an interior point of any line segment lying entirely in the polytope P

This section really needs pictures, unfortunately.

  • Let and let be the polytope . Then is equal to the convex hull of the extreme points of

  • A subset of is called a Polyhedron if there exists a matrix and a vector such that

  • Algebraic Characterization of Extreme Points: Let , where has and . Furthermore let be the equality subsystem of . Then is an extreme point of if and only if

  • Let be a polyhedron. The number of points in is uncountably infinite (why?). The number of extreme points of a polyhedron is finite (why?)

    • Let and . The number of extreme points of is less than . More specifically, the number of extreme points of never exceeds the number of objects can be chosen from a set of options.
  • The convex hull of the extreme points of a polyhedron is a polytope.

Cones, Representation Theorem, Seperation Theorem, and Farkas’ Lemma

Cones have a special definition in convex analysis. A subset of is a Polyhedral Cone if and only if for all and

With this definition, we can make a few important definitions:

  • Representation Theorem: Let and . Let , denote the convex hull of the extreme points of , and . If then

In other words, every polyhedron with at least one extreme point () is the sum of a polytope () and a polyhedral cone ().

  • A set is a polytope if and only if it is a bounded polyhedron.

  • Seperation Let and be nonempty sets in , and let be a hyperplane in . Then the following are true:
    • H is said to Seperate and if for all and for all
    • H is said to Properly Seperate and if in addition
    • H is said to Stricly Seperate and if for all and for all
    • H is said to Strongly Seperate and if, for some for all and for all
  • Seperation Theorem: Suppose the set is nonempty, closed and convex. Suppose a point does not lie in . Then there exists a vector and such that and for all

In other words, if a point does not lie in a closed and convex set , then there exists a hyperplane that completely seperates from

  • Let be a closed and convex set. Then is the intersection all half-spaces containing

  • Farkas’ Lemma: Let and . Then Exactly one of the following systems has a solution, and the other is inconsistent:

Convex Functions

Suppose that a set . A continuous function is convex at if for and ,

In other words, a convex function is a function that is always “lower” than it’s linear interpolation.

From the definition, it also follows that is convex on if and only if, for ,

  • A function of many variables is convex or concave if it is twice differentiable.

Sources

@book{andréasson2005introduction,
title={An Introduction to Continuous Optimization},
author={Andr{\'e}asson, N. and Evgrafov, A. and Patriksson, M.},
isbn={9789144044552},
url={https://books.google.com/books?id=dxdCHAAACAAJ},
year={2005},
publisher={Professional Publishing Svc.}
}
@misc{ wiki:xxx,
author = "Wikipedia",
title = "Convex set --- Wikipedia{,} The Free Encyclopedia",
year = "2015",
url = "https://en.wikipedia.org/w/index.php?title=Convex_set&oldid=686390268",
note = "[Online; accessed 25-January-2016]"
}
@misc{ wiki:xxx,
author = "Wikipedia",
title = "Carathéodory's theorem (convex hull) --- Wikipedia{,} The Free Encyclopedia",
year = "2016",
url = "https://en.wikipedia.org/w/index.php?title=Carath%C3%A9odory%27s_theorem_(convex_hull)&oldid=698633316",
note = "[Online; accessed 25-January-2016]"
}
http://math.caltech.edu/Simon_Chp8.pdf
@misc{292941,
TITLE = {How to determine whether a function of many variables is convex or non-convex?},
AUTHOR = {Peder (http://math.stackexchange.com/users/59704/peder)},
HOWPUBLISHED = {Mathematics Stack Exchange},
NOTE = {URL:http://math.stackexchange.com/q/292941 (version: 2013-02-02)},
EPRINT = {http://math.stackexchange.com/q/292941},
URL = {http://math.stackexchange.com/q/292941}
}