Columbia Business School - First Year of the Doctoral Program in Decisions, Risk and Operations
• Notes based on "Optimization 1", a course I took with Prof Donald Goldfarb in the fall of 2010. The notes also draw heavily on Bestimas and Tsitsiklis' "Introduction to Linear Optimization". These n...
Introduction – Lots of Geometry
Some definitions
o Definition (Convex set): The set Í n if convex if for any x1, x 2 Î and
l Î [0,1] , x(l) = lx1 + (1 - l)x 2 Î . Note that the intersection of a finite
number of convex sets is convex.
o Definition (Convex function): A function f (x ) defined on a convex set
Í n is convex if for any x1, x 2 Î , the linear interpolation between those two
points lies above the curve:
f (lx1 + (1 - l)x 2 ) £ l f (x1 ) + (1 - l)f (x 2 ) l Î [0,1]
x1 x2
o Definition (Cone): A set Î n is a cone if for all x Î and any l ³ 0 ,
lx Î :
1
2
Daniel Guetta, 2010
,Optimization I Notes Page 2
{
The set x Î n : x = Aa, a ³ 0, A Î n´m , a Î m } is the cone generated by the
columns of A.
o Definition (extreme point): An extreme point of the convex set is a point
x Î that cannot be written as a convex combination of other points in .
Not an extreme point
Extreme point
Extreme point
o Definition (Convex Combination): A convex combination of points x1, , xk
is a point x = å i =1 li xi , such that l ³ 0 and å
k k
i =1
li = 1 . The set of convex
combinations of a set points is the smallest convex set containing all the points;
it is called the convex hull of these points.
o {
Definition (Hyperplane): The set = x Î n : a ⋅ x = b, a Î n , b Î } is
{
called a hyperplane with normal a. The set = x Î n : a ⋅ x £ b } is a closed
halfspace, and is its bounding hyperplane.
o Definition (Afine set): A set a Î n is an affine set if for all x1, x 2 Î a and
l Î (-¥, ¥) , x(l) = lx1 + (1 - l)x 2 Î a . A hyperplane is an example of an
affine set. Roughly speaking, an affine set is a subspace that need not contain the
original.
o Definition (Polyhedron): A polyhedron is a set which is the intersection of a
finite number of closed hyperplanes. It is necessarily convex. If the polyhedron is
non-empty and bounded (ie: there exists a large ball it lies inside of), it is called a
polytope.
o Definition (Dimension): The dimension of an affine set a is the maximum
number of linearly independent vectors in a .
o Definition (Supporting hyperplane): A supporting hyperplane of a closed,
convex set is a hyperplane such that Ç ¹ Æ and Í :
Daniel Guetta, 2010
,Optimization I Notes Page 3
o Definition (Face): Let be a non-empty polyhedron and let be any
supporting hyperplane. The intersection Ç = is a face of . The whole
polyhedron could be a face, if the and are both two-dimensional! For
example, the thick line and the point in the example below are both faces of their
respective polyhedra:
2
1
We give special names to faces of particular dimensions:
Face Dimension
Vertex 0
Edge 1
Facet d–1
Another way of looking at the concept of a vertex is as a point x Î that is
such that there exists some c such that c ⋅ x < c ⋅ y for all y Î and y ¹ x . In
other words, we insist Ç =
= x . This simply means that our face is 0-
dimensional, and the definitions are therefore equivalent.
Daniel Guetta, 2010
, Optimization I Notes Page 4
Polyhedra in standard form
o The definition of a polyhedron above (in terms of the intersection of a number of
{
half-spaces) can be written as = Ax £ b : A Î n´m , x Î n , b Î m , where }
the rows of A contain the normals of the various hyperplanes defining the
polyhedron.
o It is often convenient, however, to write the polyhedron in an equivalent standard
{ ¢ ¢
}
form ¢ = A¢x = b : x ³ 0 , A Î n ´m , x Î n , b Î m , where the rows of A are
linearly independent. This involves a number of steps:
Re-write each inequality constraint Arow i ⋅ x £ bi as the equality
Arow i ⋅ x + si = bi , where si > 0. si becomes a new variable.
Eliminate any linearly independent rows in A (this does not alter the
problem – see page 57 of B&T for proof). Note that this implies that, in
standard form, m < n – in other words, the number of constraints is less
than or equal to the number of variables.)
Replace any unconstrained variables xi with two new variables x i+ and x i-
, both constrained to be positive, and add the constraint x i = x i+ - x i- .
[The validity of this step is not entirely obvious, but for the simplex
method, it works].
Algebraic Characterization of Vertices & Extreme Points
o In the previous section, we provided definitions of vertices and extreme points. It
would seem logical that the solution of a linear program should lie at one of these
points. In this section, we see that these concepts are equivalent, and we develop
an algebraic characterization of such points.
o We present two characterizations – the first is in terms of polyhedra in non-
standard form, which is more useful to gain an intuitive grasp of the concept, and
the second in terms of polyhedra in standard form, which we will use hereafter.
o Theorem: Let = {x : Ax ³ b, A¢x = b ¢} be a non-empty polyhedron, and let
x Î . The following three statements are equivalent:
1. x is a vertex
Daniel Guetta, 2010
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.
