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 nonconvex for
 Finite sets are nonconvex (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, Speration 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 halfspaces 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.