Approximation algorithms, Part 2 This is the continuation of Approximation algorithms, Part 1. Here you will learn linear programming duality applied to the design of some approximation algorithms, and semidefinite programming applied to Maxcut. By taking the two parts of this course, you will be exposed to a range of problems at the foundations of theoretical computer science, and to powerful design and analysis techniques. Upon completion, you will be able to recognize, when faced with a new combinatorial optimization problem, whether it is close to one of a few known basic problems, and will be able to design linear programming relaxations and use randomized rounding to attempt to solve your own problem. The course content and in particular the homework is of a theoretical nature without any programming assignments. This is the second of a two-part course on Approximation Algorithms.
Properties of LP duality
Loading...
From the course by École normale supérieure
Approximation Algorithms Part II
42 ratings
From the lesson
Linear Programming Duality
This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality.
Meet the Instructors
Claire Mathieu
[MUSIC]
We have seen on the special example, how to construct a new
Linear program called the dual of the original Linear program.
Now let us continue exploring the properties of duality.
This, was our original example and that was the dual that we built.
What was the property of the dual that guided our construction?
The property was that, if you take any feasible x,
any a feasible y the feasible y's are bound the best possible value.
The main value of all feasible axises and
that is true for all y's, including the one that maximizes this value.
Therefore, we have the following lemma.
If we look at the minimum value of the objective function of the primal LP, it is
greater than or equal to the maximum value of the objective function of the dual LP.
That is called the weak duality theorem in the general case and
it is a very useful observation.
We actually proved it in this special case by reasoning.
So, you can see that it is not a very difficult statement.
It's really a lemma more than a theorem.
Now, we have worked on constructing the dual of a special example
that was a minimization linear problem.
What happens if we try to take the dual
of a linear program that is a maximization linear program?
Does the same principle also work?
Let's try it.
So,we have a maximization problem.
Namely, the one we just built, this one.
So, let's try to start from this maximization linear program and
construct it's dual by a similar reasoning.
In other words, we have to think about
bounding the value of the optimal feasible solution.
How do we prove a lower bound?
For a maximization problem, it's easy.
All we have to do is exhibit a feasible vector (y1,y2) that's
satisifes all constraints.
And then its value will be less than equal maximum possible value.
So, that's the lower bound.
How do we prove another bound?
For the upper bound, it's a little more complicated.
So again, what we will do is construct a convex combination of the constraints,
1', 2', 3', such that the coefficient of y1 is at least 10.
And the coefficient of y2 is at least 6.
Notice that before, when we are working on the other linear program, we were trying
to have a coefficient of x1 be at most something and x2 be at most something.
Now, it's at least 10 and at least 6.
And then what happens?
So, we multiply z1 times constraint 1 prime.
z2 times constraint 2 prime.
z3 times constraint 3 prime such that,
the resulting coefficient of y1,
z1-z2+3z3 is at least 10.
This 10 and the resulting coefficient
of y2 is at least 6, this 6.
Then, once we have that, we can deduce an upper bound for the optimal value.
How?
The right hand side, 7z1 plus z2 plus 5z3,
will be an upper bound on the optimal value of this linear program.
So that, with that reasoning, we deduce the dual
linear program of that problem.
The best upper bound, the the tightest one, is the one that is minimum.
Minimize the 7z1+z2+5z3 such that two
constraints are satisfied, z1-z2+3z3 is a least 10 and 5 z1+2z2-z3 is at least 6.
And the zI's are all non-negative.
That new Linear program.
It's a minimization LP and that is called the dual of the one that we started from.
So now we have two examples of duality.
We started from a minimization problem and
we built a maximization problem, the dual LP.
Now, we started from a maximization problem and
we built a minimization problem, the dual LP.
But there is a surprise here.
If we put all this side by side, the LP we started from,
the dual reconstructed, then that was our example of a maximizational key.
The dual that we built, the dual of the dual.
Then, the dual of the dual is the primal.
Up to renaming z1, z2, z3 and calling them x1, x2, x3.
It's exactly the same thing.
So, the dual of the dual is the primal.
That is a general property of duality.
It's actually an invariate of duality.
It works not just for linear programming duality, but also for
planar graph duality or other dual structures that exist in mathematics.
Whenever something is called dual,
you can be sure that the dual of the dual is the primal.
So that is one property of linear programming duality.
Now we will see some other properties by looking at the geometry of duality.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
