Introduction to Optmization
Lecture 2 Simplex Method & Duality
1
Last time
Question: Is the convex hull of infinite number of points a convex set?
2
Last time
Question: Is the convex hull of infinite number of points a convex set?
Answer: Yes, but one needs a more general definition of convex hull without resorting to the convex combination.
3
Last time
Question: Is the convex hull of infinite number of points a convex set?
Answer: Yes, but one needs a more general definition of convex hull without resorting to the convex combination.
4
Last time: High level overview of simplex method
5
Last time: High level overview of simplex method
6
Last time: Bases and Vertices
7
Given the standard form representation of a polytope
Last time: Bases and Vertices
8
Given the standard form representation of a polytope
Last time: Bases and Vertices
9
Given the standard form representation of a polytope
What does this mean?
Last time: Bases and Vertices
10
Last time: Bases and Vertices
11
We have m+n constraints, but only need n independent constraints to determine a vertex.
Last time: Bases and Vertices
12
We have m+n constraints, but only need n independent constraints to determine a vertex.
We take m columns from Ax = b and n-m columns from x > 0.
Last time: Bases and Vertices
13
We have m+n constraints, but only need n independent constraints to determine a vertex.
We take m columns from Ax = b and n-m columns from x > 0.
Last time: Bases and Vertices
14
We take m columns from Ax = b and n-m columns from x > 0.
Last time: Bases and Vertices
15
We take m columns from Ax = b and n-m columns from x > 0.
Assuming other constraints are not active, then we get the new linear system from the active constraints.
Last time: Bases and Vertices
16
We take m columns from Ax = b and n-m columns from x > 0.
Assuming other constraints are not active, then we get the new linear system from the active constraints.
Let’s go back to understand the theorem
17
Let’s go back to understand the theorem
18
Let’s go back to understand the theorem
19
This tells us how to construct a vertex.
20
This tells us how to construct a vertex.
21
We make the following observations
22
We make the following observations
23
We make the following observations
24
A quick reminder on degeneracy
25
A quick reminder on degeneracy
26
Last time: High level overview of simplex method
27
When does a vertex exist?
28
When does a vertex exist?
29
When does a vertex exist?
30
The proof is simple. Please read the textbook.
This has insteresting implication:
31
This has insteresting implication:
32
Why?
This has insteresting implication:
33
Why?
Bounded = Not contain a line.
Standard form = x > 0 (hence independent constraints.)
We know that the basic feasible solution exists. How to find the first one?
34
Recall that the standard LP takes form:
We know that the basic feasible solution exists. How to find the first one?
35
Consider the next problem:
Recall that the standard LP takes form:
We know that the basic feasible solution exists. How to find the first one?
36
Consider the next problem:
Recall that the standard LP takes form:
Claim:
How to find the first basic feasible solution in three steps?
37
How to find the first basic feasible solution in three steps?
38
How to find the first basic feasible solution in three steps?
39
Last time: High level overview of simplex method
40
First, we need to define a feasible direction.
41
What does the feasible direction look like at a vertex with basis B?
First, we need to define a feasible direction.
42
What does the feasible direction look like at a vertex with basis B?
Then we denote x with indices in the basis,
And for x with indices outside of the basis,
43
Recall that two vertex are adjacent only if the bases differ by only one column.
44
Recall that two vertex are adjacent only if the bases differ by only one column.
Therefore, we can move at most in n-m directions. (Why? How many zeros in x are there?)
45
Recall that two vertex are adjacent only if the bases differ by only one column.
Therefore, we can move at most in n-m directions. (Why? How many zeros in x are there?)
Therefore, we can simply pick a direction from one of the non-basis coordinates.
46
Recall that two vertex are adjacent only if the bases differ by only one column.
Therefore, we can move at most in n-m directions. (Why? How many zeros in x are there?)
Therefore, we can simply pick a direction from one of the non-basis coordinates.
47
Recall that two vertex are adjacent only if the bases differ by only one column.
Therefore, we can move at most in n-m directions. (Why? How many zeros in x are there?)
To figure out the value of d in the basis indices, we can use feasibility of d.
48
Recall that two vertex are adjacent only if the bases differ by only one column.
Therefore, we can move at most in n-m directions. (Why? How many zeros in x are there?)
To figure out the value of d in the basis indices, we can use feasibility of d.
49
Recall that two vertex are adjacent only if the bases differ by only one column.
Therefore, we can move at most in n-m directions. (Why? How many zeros in x are there?)
50
Recall that two vertex are adjacent only if the bases differ by only one column.
Therefore, we can move at most in n-m directions. (Why? How many zeros in x are there?)
51
Therefore, to move in direction in the coordinate j where j is not in the basis, we can easily compute the corresponding feasible direction as:
Among all the n-m directions, which one should we pick?��
52
Among all the n-m directions, which one should we pick?��We should pick the one that minimizes the objective.��
53
Among all the n-m directions, which one should we pick?��We should pick the one that minimizes the objective.��How do we tell whether the objective decreases?
54
55
56
57
58
59
Only directions out of the basis can lead to descent!!
Last time: High level overview of simplex method
60
If we found an optimal solution, then
61
If we found an optimal solution, then
62
If we found an optimal solution, then
63
If we found an optimal solution, then
64
If we found an optimal solution, then
65
66
67
Next question, how far should we move in d, if d is a descent direction?��
68
Next question, how far should we move in d, if d is a descent direction?��As much as possible.������
69
Next question, how far should we move in d, if d is a descent direction?��As much as possible.�����
70
Next question, how far should we move in d, if d is a descent direction?��As much as possible.���We would then run into two cases.���
71
Next question, how far should we move in d, if d is a descent direction?��As much as possible.���We would then run into two cases.���
72
Next question, how far should we move in d, if d is a descent direction?��As much as possible.���We would then run into two cases.���
73
Optimal value is unbounded!
Next question, how far should we move in d, if d is a descent direction?��As much as possible.���We would then run into two cases.���
74
Optimal value is unbounded!
In the second case, we almost completed an iteration, except that we need to update the basis.
75
Then we can construct the new bases by replacing B(𝓁) with j for the updated x.
Why? What constraints are now active?
Why is the new basis valid?
76
Why is the new basis valid?
77
Proof of (a) continued
78
Proof of (a) continued
79
Proof of (b)
80
Simplex method
81
Simplex method
82
Simplex method
83
Simplex method
84
Simplex method
85
Simplex method
86
Simplex method
87
We are left with only two questions:
Does the algorithm terminate in finite time?
Does the algorithm give the valid solution?
88
We are left with only two questions:
Does the algorithm terminate in finite time?
Does the algorithm give the valid solution?
89
Does the algorithm terminate in finite time?�
90
Does the algorithm terminate in finite time?�
91
Does the algorithm terminate in finite time?�
92
Does the algorithm terminate in finite time?�
93
One can check that the following rule avoids cycling.
94
We are left with only two questions:
Does the algorithm terminate in finite time?
Does the algorithm give the valid solution?
95
Finally, why does the algorithm generate valid solution?
96
First, if there is an x that gives the optimal solution, then the algorithm can find it.
The proof of the theorem: 3 steps
97
The proof of the theorem: 3 steps
98
#2 Q doesn't contain a line, has extreme point.
The proof of the theorem: 3 steps
99
#3 Any extreme point of Q is an extreme point of P.
The proof of the theorem: 3 steps
100
#3 Any extreme point of Q is an extreme point of P.
The proof of the theorem: 3 steps
101
#3 Any extreme point of Q is an extreme point of P.
Therefore, we get the following statement.
102
Therefore, we get
We cared about:��The Algorithm can be implemented with elementary math operations.�
103
Simplex method
We cared about:��The Algorithm can be implemented with elementary math operations.��The algorithm is correct and terminate in finite time.�
104
Simplex method
We cared about:��The Algorithm can be implemented with elementary math operations.��The algorithm is correct and terminate in finite time.��We didn’t focus on:�
105
Simplex method
We cared about:��The Algorithm can be implemented with elementary math operations.��The algorithm is correct and terminate in finite time.��We didn’t focus on:��Can we solve the problem faster?��Is the problem in P or NP?�
106
Simplex method
We cared about:��The Algorithm can be implemented with elementary math operations.��The algorithm is correct and terminate in finite time.��We didn’t focus on:��Can we solve the problem faster?��Is the problem in P or NP?��But this is the starting point of mathematical programming: implement practical algorithms to solve real problems with the power of computers.�
107
Simplex method
We will talk about how to solve LP faster.��
108
We will talk about how to solve LP faster.��But before that, we need to understand a very important concept in convex problems: Duality
109
Motivating example:
110
Motivating example:
111
Motivating example:
112
Motivating example:
113
Lagrangian
114
Lagrangian
115
Lagrangian
116
Duality
117
Duality
118
Duality
119
120
121
We do the same trick and penalize constraint violation.
122
We do the same trick and penalize constraint violation.
Can we solve the problem for fixed p?
123
124
125
126
127
128
129
130
Primal Probelm
Dual Probelm
131
Primal Probelm
Dual Probelm
If we follow the above steps for other general LP problems, we can have a recipe for generating dual problems.
132
Key observations
133
# Primal Constraints = # Dual Variables
# Primal Variables = # Dual Constraints
A few more examples:
134
# Primal Constraints = # Dual Variables
# Primal Variables = # Dual Constraints
A key property for Duality:"the dual of the dual is the primal”�
135
A key property for Duality:"the dual of the dual is the primal”�
136
The proof is nothing beyond following the recipe twice.
A key property for Duality:"the dual of the dual is the primal”�
137
The proof is nothing beyond following the recipe twice.
But how would the dual problem help us understand the primal problem itself?
This is known as the duality theorem
138
Proof of weak duality
139
Primal Probelm
Dual Probelm
Proof of weak duality
140
Primal Probelm
Dual Probelm
Proof of weak duality
141
Primal Probelm
Dual Probelm
Proof of weak duality
142
Primal Probelm
Dual Probelm
A simple corollary:
143
A simple corollary:
144
Prove by contradiction.
A second simple corollary:
145
A second simple corollary:
146
Why?
The above is simple. �
147
The above is simple. �But we can get a much stronger result.
148
The above is simple. �But we can get a much stronger result.
149
One of the most important theorems in optimization. Developed by von Neumann 1947 in game theory, and Gale, Kuhn, Tucker 1951 in LP.
There are many proofs. We use the standard one via Farkas’ Lemma.
150
(a) implies not (b)
151
(a) implies not (b)
152
(a) implies not (b)
153
Not (a) implies (b)
Consider a pair of primal-dual problems：
Dual Primal
154
Not (a) implies (b)
Consider a pair of primal-dual problems：
Dual Primal
155
Not (a) implies (b)
Consider a pair of primal-dual problems：
Dual Primal
156
Not (a) implies (b)
Consider a pair of primal-dual problems：
Dual Primal
157
Not (a) implies (b)
Consider a pair of primal-dual problems：
Dual Primal
158
Not (a) implies (b)
Consider a pair of primal-dual problems：
Dual Primal
159
Now we completed this proof
160
Now we completed this proof
161
Now we completed this proof
162
Now we completed this proof
163
If we rephrase Farkas’ Lemma, we get a corollary
164
If we rephrase Farkas’ Lemma, we get a corollary
165
We use the above to prove strong duality.
Strong duality
166
Strong duality
there exists a feasible dual variable p, that achieves the same loss as the optimal primal solution.
167
Strong duality
there exists a feasible dual variable p, that achieves the same loss as the optimal primal solution. Why?
168
Strong duality
there exists a feasible dual variable p, that achieves the same loss as the optimal primal solution. Why? By weak duality
169
170
171
172
173
174
175
176
Strong duality
there exists a feasible dual variable p, that achieves the same loss as the optimal primal solution. Proof is done.
177