Columbia Business School - First Year of the Doctoral Program in Decisions, Risk and Operations
• Condensed Notes roughly following two courses I took - "Foundations of Optimization" (thought by Prof Ciamac Moallemi) and "Convex Optimization" (thought by Prof Garud Iyengar). These notes are also...
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller tandhiwahyono. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $2.60. You're not tied to anything after your purchase.
