Optimization
Intro

Optimization

Linear Programming

Integer Linear Programming Problems

Convex Optimization

Remarks

We can
assume without much loss of generality that

Examples

A two player game.

Example

This is a linear program

Weighted bipartite matching

Problem:

Formulation

Maximize

subject to

This is an integer programming formulation.

3D
Modelling

Problem

Formulation

Maximize

subject to

Remark

The 3D Matching Problem is NP-hard and hence integer linear
programming is NP-hard.

Diophantine Equations

Problem (Hilbert's 10th)

Formulation

Distance from Feasibility

Problem

Formulation

This is a convex optimization problem

September-10-12

3:03 PM

Diophantine Equation

Problem (Hilbert's 10th)

Linear
Algebra Review

Proof of Theorem

Additionally,
Gaussian Elimination can be performed carefully (by triangularizing without
scaling) such that all intermediate values are small.

September-12-12

2:57 PM

Remark

Fundamental Theorem of Linear Algebra

Solutions to Linear Systems

Support

Theorem

The size of a solution

Permutation Definition of Determinant

Crammer's Rule

For a
matrix equation

the
solution is

Systems of
Inequalities

Proof of Theorem

Easy part:
(1) and (2) cannot both hold.

It remains
to prove that if (1)  does not hold
then (2) does.

Restatement

Proceed by
Induction:

Now,

As required.

This proves Farkas' Lemma

Proof of Theorem (2)

So (1) is
equivalent to

By the
Farkas' Lemma, this is equivalent to:

That is,

That is

Note to Self

Proof
works in reverse:

Proof of Theorem (3)

Then (1)
is equivalent to

By the
Farkas' Lemma, this is equivalent to:

September-14-12

2:59 PM

Theorem (Farkas' Lemma; Theorem 2.7)

Exactly
one of the following hold.

Variable Elimination (Fourier-Motzkin)

Removing a
variable from a system of linear inequalities

Rewrite
the inequalities as

Equivalently

Other Forms of Farkas' Lemma

Theorem (2)

Exactly
one of the following hold:

Theorem (3)

Exactly
one of the following hold

Proof: Exercise

Geometry

By the
theorem

Equivalently,

Equivalently,

Equivalently,

Theorem

Separating Hyperplane Theorem

Prove
later

Linear
Programming

Example

Problem

How in
general can we prove that a given solution is optimal?

Equivalently,
how can we generate upper-bounds on the value?

Answer

Take linear
combinations of the constraints.

Remark

The problem
of determining the best bound on the objective function via linear
combination of constraints is a linear programming problem.

Take the
linear combination:

We want

^

(objective
function)

The dual of
(P) is

Unboundedness

Example

In general,
this is not always possible for unbounded sets

September-19-12

2:55 PM

Linear Program

Note

Remark

The problem
of determining the best bound on the objective function via linear
combination of constraints is a linear programming problem.

Theorems of
LP

September-21-12

3:02 PM

Theorem

"Fundamental Theorem of Linear
Programming"

Every LP
is either

infeasible,

unbounded, or

has an optimal
solution.

Lemma 1

Consider
an LP

(here (P) is unbounded)

As far as I can tell, this is not a xor.

Lemma 2

Consequence

Geometry

Claim

Theorem

Note

Corollary 1

Consider
the LP

Either

Corollary 2

Consider
the LP

Corollary 3 (Unboundedness Theorem)

Consider
the LP:

Polytopes

Proof of Corollary 4

Proof of Corollary 5

Note that

This is
a cone (since you can scale valid inequalities by non-negative numbers)

Now define

Claim

Proof

Example Proof of Carathéodory's Theorem (n=2)

Split
polygon into triangles, each point is in one of the triangles and can be
written as combination of three points of triangle.

Proof of Helly's Theorem

September-28-12

2:43 PM

Polytope

A bounded
polyhedron is a polytope.

Corollary 4

Every
polytope is the convex hull of its extreme points.

Proof

Corollary 5

Valid Inequality

Lemma 1

(See
Homework Problems page)

Corollary

Carathéodory's Theorem

Proof:
assignment 2 (or see MATH 245)

Theorem

Proof:
assignment 2

Equivalently

Corollary

Proof

Helly's Theorem

Duality

Proof of Weak Duality Theorem

Proof of Corollary 1

Contrapositive
is obvious

Proof of Strong Duality Theorem

Multiply
the rows of (1):

Claim

Proof:

Exercise (Use Farkas' Lemma)

then

Proof of Strong Duality Theorem for Standard
Inequality Form

Proof of Corollary

which is
in standard inequality form.

Yet Other Forms

The dual
of (P) is

October-03-12

2:30 PM

Duality

Consider
the LP

Dual

The dual of (P) is the linear program

Weak Duality Theorem

Corollary 1

Corollary 2

Corollary 3

Strong Duality Theorem

Relationship between Primary and Dual

(P) \
(D)

infeasible

unbounded

optimal

infeasible

Yes -
exercise

Yes

No -
exercise

unbounded

Yes

No

No

optimal

No

No

Yes

Alternate Forms

Consider
the following LPs

Claim

Standard Inequality Form

Standard Equality Form

Theorem (Strong Duality for Standard Inequality
Form)

Corollary

Theorem (Strong Duality for Standard Equality Form)

Proof

Exercise

Constructing Duals

non-neg.
var.

non-pos.
var

free
variable

non-neg.
var.

≥
constraint

non-pos.
var.

≤
constraint

free
variable

=
constraint

Complementary
Slackness

Proof of Complementary Slackness Theorem

Consider

and its
dual

Proof of
Standard Inequality form CST

Conversely,

Proof of Standard Equality Form CST

and apply
the original complementary slackness theorem. ■

October-10-12

2:31 PM

Complementary Slackness Theorem

Standard Inequality Form

Proof: Exercise

Standard Equality Form

Simplex
Method

Proof of Optimality Theorem

Finding a Basic Feasible Solution

Output: A
basic feasible solution

Step 1

Step 2

Step 3

Repeat from
step 1

Simplex Method

Goal

Simplex Method Example

(Here we
are eliminating the basic variables from the objective function.)

The basic
solution is

and the
objective value is 14

Eliminate
the new basic variables from the objective function

October-10-12

2:54 PM

Consider

and its
dual

Basic Solution

There is
a unique solution to

this is the basic dual
solution.

Optimality Theorem

Remarks

Claim

Proof

⇒ By
definition

Simplex Method

Using the
linear program definitions given at the top of the page.

Where

Note that

Optimality

Iteration

Note that
the unique solution to

Unboundedness

Update

Now we
repeat.

Termination
of the Simplex Method

October-17-12

3:12 PM

Termination

At each iteration
the objective value does not decrease

There are examples
where the Simplex Method cycles

That is, it
revisits a basis

The easiest way to
avoid cycles is to pick entering variables randomly amongst the
choices.

Nondegeneracy

Note

Hirsch Conjecture (1957)

This is the
graph-theory distance (how many edges you need to traverse.)

False (Proved in 2010)

The
1-skeleton is the frame of lines between vertices that could be traversed by
the Simplex Algorithm.

Problems

Is there
a polynomial bound on the diameter of the 1-skeleton?

Is there a
"pivoting rule" for the simplex Method that gives a
polynomial-time algorithm?

Pivoting rule is the rule for selecting an entering variable of
possible choices.

Perturbation Method

Idea: We
carefully select the leaving variable in order to avoid cycling. This is
achieved by perturbing b.

Consider

Polynomial Ordering

Claim

Another Way to Avoid Cycling

Break ties
when choosing entering and leaving variables by taking the one of minimum
subscript.

Theorem (Bland)

The
smallest subscript rule avoids cycling.

Proof of Claim

Feasibility

Finding a Feasible Solution

Consider

We have
algorithms for

Given a
feasible solution, find a basic feasible solution.

How do you
find a feasible solution?

Consider
the following auxiliary problem

Note that

Remark

Information Returned by SM

If has
optimal solution, it will give you the solution and the feasible dual
solution.

If
unbounded if will find an unbounded ray.

Recall: Farkas' Lemma

Exactly one
of the following has a solution

Note: this
gives  a (more) constructive proof of
the Farkas' Lemma

October-19-12

2:35 PM

Information Returned by SM

If has
optimal solution, it will give you the solution and the feasible dual
solution.

If
unbounded if will find an unbounded ray.

Midterm
Review

October-22-12

2:33 PM

Integer
Programming

Proof of Lemma (1)

Proof of Theorem

October-26-12

2:33 PM

Integer Program

An integer
program is a problem of the form

Linear Programming Relaxation

Drop the
integer constraint.

The linear
programming relaxation is

Notation

equality
is "rare".

Integral

A
polyhedron is integral if its extreme
points are integral. (That is, all entries are integers).

Lemma (1)

Totally Unimodular Matrices

A matrix
is totally unimodular (TU) iff each of its square submatrices has
determinant 0, 1, or -1.

In
particular, the entries are 0, 1, -1

Theorem

Modifying TU Matrices

Lemma (2)

Proof of Lemma (2)

By
minimality, each column contains has two nonzero entries (otherwise expanding
the determinant at that column would give a smaller matrix with the same
property.

Graph
Theory

October-29-12

2:32 PM

Incidence Matrix

Vertices on
rows, edges on columns. 1 if that edge is incident on that vertex, 0
otherwise.

Bipartite Graph

Theorem

The
incidence matrix of a bipartite graph is TU.

Remark

Matching

Matching Polyhedra

Note that

Theorem (Summary)

r-Regular

Theorem

Cover

König's Theorem

In a
bipartite graph, the maximum size of a matching is equal to the minimum size
of a cover.

Min-Cost
Matching

October-31-12

2:51 PM

Minimum-Cost Perfect Matching

Problem

We will
assume that G has a perfect matching.

(Either
find one with an un-weighted algorithm or throw in very high weight edges)

Min-Cost Matching

and its
dual

We call
these reduced costs.

Complementary Slackness

Claim

Min-cost perfect matching?

Prove this

Algorithm

Overview

Neighbour Set

Hall's Theorem

Algorithm for
Min-Cost Perfect Matching

November-05-12

2:33 PM

Min Cost Perfect Matching

and its dual

Lemma

Hall's Theorem

Assumption

We have an
efficient algorithm for Hall's Theorem.

See MATH
239/249

Algorithm

Remarks

(So we keep an integral dual solution)

See CO 450

The min
cost perfect matching problem can be solved in polynomial time, even for
non bipartite graphs.

See CO
450.

This has
exponentially many constraints, but is still solvable in polynomial time
so long as the constraints are given implicitly (only generated when
needed).

Directed
Graphs

November-05-12

3:06 PM

Directed Graph

Incidence Matrix

Notation

Inflow

(s,t)-flow

Problem

This is a
linear program

Note that
if the edge capacities are integer then this is an integer linear program.

(s,t)-cut

Claim

Max-Flow Min-Cut Theorem

Complexity
Theory

LP Feasibility Problems

IP Feasibility

Bipartite Matching Problem

Clique Problem

Examples of NP problems

Bipartite
matching problem

Give the matching

Clique
problem

Give the clique

LP
feasibility problems

Give a solution,
whose size is small

Proof of Claim: LP feasibility is in NP

(by changing
variables. This does not change the size of the solution)

∎

Example

Bipartite
Matching is in co-NP

By the
Farkas Lemma,

This
"reduces" NOT(LP feasibility) to an instance of LP feasibility of a
similar size ∎

Example

Construct
an instance  of IP feasibility

This
reduces the Clique Problem to IP feasibility.

Sketch of Proof of Cook's Theorem

Algorithm
to verify (I, C) runs in polynomial time with polynomial memory.

Linear
inequalities are used to describe feasible transitions according to the model
of computation, and to describe the accepting state.

Now this is
a IP feasibility problem.

Exercise

November-09-12

2:57 PM

Decision Problems

A decision problem is a yes/no question on a
countable set of instances; the "size" of an instance is the length
of a binary encoding.

Polynomial-Time

An
algorithm is polynomial time if its running time is bounded by a polynomial
in the size of the input. P is the set of all decision problems that can be
shown to be polynomial time.

Claim

LP
feasibility is in NP

Exercise

Show that
IP is in NP

Find a
rational half-line

Nondeterministic Polynomial time

Claim

LP
feasibility is in co-NP

Major Conjectures

Polynomial Time Reduction

NP-Completeness

Theorem (Cook)

IP
feasibility is NP-complete

(Cook used
"3-SAT")

Formalism

A* denotes
the set of finite words in A

Problem

A problem
is any subset of  A* (these are the
yes-instances).

(not we are
only replace on instance).

Algorithm

An algorithm is a sequence

Step 2:
Stop

Nonlinear
Optimization

Recall that

By rewriting as

Small
problems can be nontrivial

e.g.

Proof of Theorem

∎

Exercises

Proof of Separating Hyperplane Theorem

Exercise

Proof Sketch of Theorem (3)

Now
continuous as in the proof of the separating Hyperplane Theorem. ∎

November-16-12

2:32 PM

Nonlinear Optimization Problem

Inf / Sup

Compactness

Bolzano-Weierstrass Theorem

Corollary (Weierstrass)

Nearest Point

Theorem

Separating Hyperplane Theorem

Boundary of a Set

Theorem (3)

Strong Cost
Splitting Theorem

November-23-12

2:32 PM

Strong Cost Splitting Theorem

(Necessary
and Sufficient Conditions for optimality in convex optimization)

Lemma 1

Proof

Exercise
(see previous page)

Tangent Cone

Remarks

This definition is
nonstandard but agrees with the usual definition on convex sets.

Theorem 2

Note

Consider
the example of the two balls.

Convex Cones

Separating Hyperplane Theorem for Cones

Duality for Cones

Remarks

Lemma 3

Lemma 4

Duality Theorem For Cones

Normal Cone

Note that:

Lemma 5

Sum of Sets

Exercise

Remark

Lemma 6

Lemma 7

Lemma 8

Theorem

Has
essentially the same proof as the above.

Claim

Exercise

Show that the above theorem and claim imply the Strong
Duality Theorem

Convex
Optimization Algorithms

November-30-12

2:32 PM

Assumptions

Remarks

Consider a
linear program

Feasibility Problems

Note that:

consider the feasibility problem:

Ellipsoid Method

Method to
Solve Feasibility Problem

Ellipsoid

Positive Definite

Useful Facts

Idea

find a
feasible solution, or

Linear Programming Feasibility

Facts:

Remark

The above
facts, together with the ellipsoid method prove that linear programming can be
solved in polynomial time.

For more
details see CO 471 or CO 463

What's next in C&0

Highly
recommended:

CO 450
Combinatorial Optimization (Fall)

Network flows

Matching

Matroid optimization

Travelling Salesman
Problems

CO 463 Convex
Optimization (Fall)

Ellipsoid method

Duality

CO 471
Semidefinite Optimization (Summer)

Optimization with
quadratic constraints

linear programming
theory extends naturally

applications in graph
theory

Recommended

CO 466
Continuous Optimization

CO 452
Integer Programming

Applied
Courses

CO 456 Game
Theory

CO 454
Scheduling

Shameless
advertising

CO 446
Matroid Theory