Convex Optimization Page 1
CONVEX OPTIMIZATION
Chapter 2 – Convex Sets
Basics
o A set is affine if it contains any line through two of its point. Alternatively,
x1 , , x n Î , q+ = 1 q1x1 + + qn x n Î .
o The affine hull of a set of points is the set of all affine combinations of these
points.
o The affine dimension of a set is the dimension of its affine hull. Its relative
interior is its interior relative to its affine hull
relint = {x Î C : B(x , r ) Ç aff Í for some r > 0}
o The most general form of a convex combination is (x ) , where (x Î ) = 1 .
o A set is a cone if x Î , q ³ 0 qx Î
{
The set (x , t ) : x £ t } is a norm cone associated with a particular norm.
The conic hull of {xi } is {l1x1 + + lk xk : l ³ 0 } .
o A hyperplane is a set of the form {x : a ⋅ x = b } . Hyperplane with normal vector
a, offset b from the origin; can be written as {x : a ⋅ (x - x 0 ) = 0} = x 0 + a ^
o Given k + 1 affinely independent pints (ie: vi - v0 linearly independent), the k-
dimensional simplex determined by these points is = {å qi vi : qi ³ 0, q+ = 1} .
We can describe this as a polyhedron as follows:
Write B = éëêv1 - v0 , , vk - v0 ùûú and q ¢ = éêëq1 , , qk ùúû . All points x Î can
then be expressed as x = v0 + Bq ¢ provided q ¢ ³ 0 and 1 ⋅ q ¢ £ 1
B has rank k (by assumptions) and k < n, and so there exists a A Î n´n
é A B ù éI ù
such that AB = êê 1 úú = êê úú .
êëA2B úû êë 0 úû
Daniel Guetta
,Convex Optimization Page 2
Multiplying the boxed equation by A, we get q ¢ = A1x - A1v0 and
A2x = A2v0 . We can therefore express q ¢ ³ 0 and 1 q ¢ £ 0 as linear
inequalities. Together with A2x = A2v0 , they define the polyhedron.
Operations that preserve convexity
o Intersection (including infinite intersection) – also preserve subspaces, affine
sets and convex cones:
Example: The positive semidefinite cone n+ can be written as
{X Î
z ¹0 n }
: z Xz ³ 0 . Each set in the intersection is convex (since
the defining equations are linear), and so n+ is convex.
Example: = x Î m : { åx i
cos(it ) £ 1 for t Î [- p3 , p3 ] } can be written
as t Î[- p , p ]
3 3
{X Î n
: -1 £ (cos t, , cos mt ) ⋅ x £ 1} , and so is convex.
o Affine functions: An affine function has the form f (x ) = Ax + b . The image
and inverse image of a convex set under such a function is convex.
Example: 1 + 2 = {x + y : x Î 1 , y Î 2 } is the image of
1 ´ 2 = {(x1 , x 2 ) : x1 Î 1 , x 2 Î 2 } under f (x1 , x 2 ) = x1 + x 2 .
Example: {x : Ax £ b,Cx = d } is the inverse image of + ´ {0} under
f (x ) = (b - Ax, d - Cx ) .
Example: {x : A(x ) = x A + + x A
1 1 n n
B } is the inverse image of the
positive semidefinite cone n+ under f (x ) = B - A(x ) .
{ }
Example: x : (x - xc ) P (x - xc ) £ 1 , where P Î n++ is the image of a
unit Euclidean ball under f (u ) = P 1/2u + xc .
o Perspective function: f (z, t ) = z / t , where t > 0. It normalizes the last
component of a vector to 1 and then gets rid of that component. The image of a
convex set under the perspective function is convex.
o Linear-fractional function: A linear-fractional function is formed by compsing
that perspective function with an affine function. They take the form
f (x ) = (Ax + b) / (c ⋅ x + d ) , with domain {x : c ⋅ x + d > 0} .
Daniel Guetta
,Convex Optimization Page 3
Separating & Supporting Hyperplanes
o Theorem: If Ç ¹ Æ then $a ¹ 0 and b such that a ⋅ x £ b "x Î and
a ⋅ x ³ b "x Î . In some cases, strict separation is possible (ie: the inequalities
become strict).
o {
Example: Consider an affine set = Fu + g : u Î m } and a convex set
which are disjoint. Then by our Theorem, there exists a ¹ 0 and b such that
a ⋅ x £ b "x Î and a ⋅ [Fu + g ] ³ b a Fu ³ b - a ⋅ g "u . The only way a
linear function can be bounded below is if it’s 0 – as such, a F = 0 , and
b £ a ⋅g .
o Theorem: Consider two convex sets and . Provided at least one of them is
open, they are disjoint if and only if there exists a separating hyperplane.
Proof: Consider the open set – a ⋅ x cannot be 0 for any x in that set, else it
would be greater than 0 for a point close to x. Thus, a ⋅ x is strictly less than 0
for all points in the open set.
o Example: Consider Ax < b . This has a solution if and only if
{
= b - Ax : x Î n } and = m++ do not intersect. By the Theorem, this is
true if and only if there exists l ¹ 0 and m Î such that l ⋅ y £ m "y Î and
l ⋅ y ³ m "y Î . In other words, there is not separating hyperplane iff
l ¹0 l ³0 Al = 0 l b £ 0
Thus, only one of this sytem and Ax < b can have a solution.
Chapter 3 – Convex Functions
Basics
o We extend a convex/concave function by setting it to +/– ¥ outside its domain.
o Theorem: f is convex over convex iff f (y ) ³ f (x ) + f (x ) (y - x ) over .
Proof: choose x1, x2 and convex comb z. Apply equation with y = z and
x = x i . Multiply one equation by l , other by 1 - l . Add the two. Take x,
y. By convexity f (x + t[y - x ]) £ (1 - t )f (x ) + tf (y ) for t Î (0,1) . Re-arrange to get
Daniel Guetta
, Convex Optimization Page 4
f(y) on one side, divide by t, take limit as t 0 . General case consider
g(t ) = f (ty + (1 - t )x ) and g ¢(t ) = f (ty + (1 - t )x ) (y - x ) . Apply previous
result with y = 1 and x = 0. Apply inequality with ty + (1 - t )x and
ty + (1 - t)x . This implies an inequality about g that makes it convex.
o Theorem: 2 f (x ) 0 over convex f convex over .
Proof: f (y ) = f (x ) + f (x ) ⋅ (y - x ) + 12 (y - x ) éê2 f (ex + (1 - e)y )ùú (y - x ) for
ë û
e Î [0,1] . If 2 f is positive definite, get FOC for convexity.
Convex functions
The following functions are convex
Function Parameters Convex/concave… …on domain
eax aÎ convex
a > 1 or a < 0 convex (0, ¥)
xa
0<a<1 concave (0, ¥)
| x |p p>1 convex
log x concave (0, ¥)
x log x convex (0, ¥)
a ⋅x +b (ie: any affine function) both n
(ie: any norm) convex n
log (å e ) xi
(the log-sum-exp func.) convex n
( x )
1/n
i
(the geometric mean) concave (0, ¥)n
log det X (the log determinant) convex X Î n++
Same as fi, providing they are all
å w f (x )
i i
wi > 0
concave/convex
Ways to find convexity:
o Directly verify definition
o Check the Hessian: for example, for f (x , y ) = x 2 / y
2 êé y -xy ùú é ù
2
2
f (x , y ) = 3 ê =
2 é
y -x ùê y ú0
2 ú ê úû ê-x ú
y ëê-xy x ûú y 3 ë ëê úû
Daniel Guetta
CONVEX OPTIMIZATION
Chapter 2 – Convex Sets
Basics
o A set is affine if it contains any line through two of its point. Alternatively,
x1 , , x n Î , q+ = 1 q1x1 + + qn x n Î .
o The affine hull of a set of points is the set of all affine combinations of these
points.
o The affine dimension of a set is the dimension of its affine hull. Its relative
interior is its interior relative to its affine hull
relint = {x Î C : B(x , r ) Ç aff Í for some r > 0}
o The most general form of a convex combination is (x ) , where (x Î ) = 1 .
o A set is a cone if x Î , q ³ 0 qx Î
{
The set (x , t ) : x £ t } is a norm cone associated with a particular norm.
The conic hull of {xi } is {l1x1 + + lk xk : l ³ 0 } .
o A hyperplane is a set of the form {x : a ⋅ x = b } . Hyperplane with normal vector
a, offset b from the origin; can be written as {x : a ⋅ (x - x 0 ) = 0} = x 0 + a ^
o Given k + 1 affinely independent pints (ie: vi - v0 linearly independent), the k-
dimensional simplex determined by these points is = {å qi vi : qi ³ 0, q+ = 1} .
We can describe this as a polyhedron as follows:
Write B = éëêv1 - v0 , , vk - v0 ùûú and q ¢ = éêëq1 , , qk ùúû . All points x Î can
then be expressed as x = v0 + Bq ¢ provided q ¢ ³ 0 and 1 ⋅ q ¢ £ 1
B has rank k (by assumptions) and k < n, and so there exists a A Î n´n
é A B ù éI ù
such that AB = êê 1 úú = êê úú .
êëA2B úû êë 0 úû
Daniel Guetta
,Convex Optimization Page 2
Multiplying the boxed equation by A, we get q ¢ = A1x - A1v0 and
A2x = A2v0 . We can therefore express q ¢ ³ 0 and 1 q ¢ £ 0 as linear
inequalities. Together with A2x = A2v0 , they define the polyhedron.
Operations that preserve convexity
o Intersection (including infinite intersection) – also preserve subspaces, affine
sets and convex cones:
Example: The positive semidefinite cone n+ can be written as
{X Î
z ¹0 n }
: z Xz ³ 0 . Each set in the intersection is convex (since
the defining equations are linear), and so n+ is convex.
Example: = x Î m : { åx i
cos(it ) £ 1 for t Î [- p3 , p3 ] } can be written
as t Î[- p , p ]
3 3
{X Î n
: -1 £ (cos t, , cos mt ) ⋅ x £ 1} , and so is convex.
o Affine functions: An affine function has the form f (x ) = Ax + b . The image
and inverse image of a convex set under such a function is convex.
Example: 1 + 2 = {x + y : x Î 1 , y Î 2 } is the image of
1 ´ 2 = {(x1 , x 2 ) : x1 Î 1 , x 2 Î 2 } under f (x1 , x 2 ) = x1 + x 2 .
Example: {x : Ax £ b,Cx = d } is the inverse image of + ´ {0} under
f (x ) = (b - Ax, d - Cx ) .
Example: {x : A(x ) = x A + + x A
1 1 n n
B } is the inverse image of the
positive semidefinite cone n+ under f (x ) = B - A(x ) .
{ }
Example: x : (x - xc ) P (x - xc ) £ 1 , where P Î n++ is the image of a
unit Euclidean ball under f (u ) = P 1/2u + xc .
o Perspective function: f (z, t ) = z / t , where t > 0. It normalizes the last
component of a vector to 1 and then gets rid of that component. The image of a
convex set under the perspective function is convex.
o Linear-fractional function: A linear-fractional function is formed by compsing
that perspective function with an affine function. They take the form
f (x ) = (Ax + b) / (c ⋅ x + d ) , with domain {x : c ⋅ x + d > 0} .
Daniel Guetta
,Convex Optimization Page 3
Separating & Supporting Hyperplanes
o Theorem: If Ç ¹ Æ then $a ¹ 0 and b such that a ⋅ x £ b "x Î and
a ⋅ x ³ b "x Î . In some cases, strict separation is possible (ie: the inequalities
become strict).
o {
Example: Consider an affine set = Fu + g : u Î m } and a convex set
which are disjoint. Then by our Theorem, there exists a ¹ 0 and b such that
a ⋅ x £ b "x Î and a ⋅ [Fu + g ] ³ b a Fu ³ b - a ⋅ g "u . The only way a
linear function can be bounded below is if it’s 0 – as such, a F = 0 , and
b £ a ⋅g .
o Theorem: Consider two convex sets and . Provided at least one of them is
open, they are disjoint if and only if there exists a separating hyperplane.
Proof: Consider the open set – a ⋅ x cannot be 0 for any x in that set, else it
would be greater than 0 for a point close to x. Thus, a ⋅ x is strictly less than 0
for all points in the open set.
o Example: Consider Ax < b . This has a solution if and only if
{
= b - Ax : x Î n } and = m++ do not intersect. By the Theorem, this is
true if and only if there exists l ¹ 0 and m Î such that l ⋅ y £ m "y Î and
l ⋅ y ³ m "y Î . In other words, there is not separating hyperplane iff
l ¹0 l ³0 Al = 0 l b £ 0
Thus, only one of this sytem and Ax < b can have a solution.
Chapter 3 – Convex Functions
Basics
o We extend a convex/concave function by setting it to +/– ¥ outside its domain.
o Theorem: f is convex over convex iff f (y ) ³ f (x ) + f (x ) (y - x ) over .
Proof: choose x1, x2 and convex comb z. Apply equation with y = z and
x = x i . Multiply one equation by l , other by 1 - l . Add the two. Take x,
y. By convexity f (x + t[y - x ]) £ (1 - t )f (x ) + tf (y ) for t Î (0,1) . Re-arrange to get
Daniel Guetta
, Convex Optimization Page 4
f(y) on one side, divide by t, take limit as t 0 . General case consider
g(t ) = f (ty + (1 - t )x ) and g ¢(t ) = f (ty + (1 - t )x ) (y - x ) . Apply previous
result with y = 1 and x = 0. Apply inequality with ty + (1 - t )x and
ty + (1 - t)x . This implies an inequality about g that makes it convex.
o Theorem: 2 f (x ) 0 over convex f convex over .
Proof: f (y ) = f (x ) + f (x ) ⋅ (y - x ) + 12 (y - x ) éê2 f (ex + (1 - e)y )ùú (y - x ) for
ë û
e Î [0,1] . If 2 f is positive definite, get FOC for convexity.
Convex functions
The following functions are convex
Function Parameters Convex/concave… …on domain
eax aÎ convex
a > 1 or a < 0 convex (0, ¥)
xa
0<a<1 concave (0, ¥)
| x |p p>1 convex
log x concave (0, ¥)
x log x convex (0, ¥)
a ⋅x +b (ie: any affine function) both n
(ie: any norm) convex n
log (å e ) xi
(the log-sum-exp func.) convex n
( x )
1/n
i
(the geometric mean) concave (0, ¥)n
log det X (the log determinant) convex X Î n++
Same as fi, providing they are all
å w f (x )
i i
wi > 0
concave/convex
Ways to find convexity:
o Directly verify definition
o Check the Hessian: for example, for f (x , y ) = x 2 / y
2 êé y -xy ùú é ù
2
2
f (x , y ) = 3 ê =
2 é
y -x ùê y ú0
2 ú ê úû ê-x ú
y ëê-xy x ûú y 3 ë ëê úû
Daniel Guetta
