Optimization Methods - Recitation 3

Recitation 3 1 Duality Theory Intuitively, dual variables can be considered as prices or penalties. Instead of imposing the constraints in the problem explicitly, we can add a penalty to the objective cost whenever a constraint is violated. Question 1 Given the genereal linear programming problem: c
x min s.t. (1) Ax ≥ b Construct its dual problem using Lagrange multiplier method. Solution Consider the function g(p) = minx c
x + p
(b − Ax) for p ∈ Rm +.


We have, g(p) = p b + minx (c − p A)x. �  0
−∞ c
− p
A =

min(c − p A)x = x 0 c
− p
A = 0

� � p b. Therefore, maxp∈Rm g(p) = maxp∈Rm + + :p A=c The problem can be then written as follows: min s.t. b
p p
A = c
p≥0 (2) Question 2 Given a basis B of a standard form problem. 1. What is the primal basic solution? 2. What is the dual basic solution? 3. What are the optimality conditions for this basis? 4. If a primal basic solution is degenerate, what can you say about the corresponding dual basic solutions? 5. If a primal basic feasible solution is not optimal, what can you say about the corresponding dual basic solutions? 1 6. If a primal basic feasible solution is optimal, what can you say about the corresponding dual basic solutions? 7. If a dual basic solution is degenerate, what can you say about the corresponding primal basic solutions? Answer 1. xB = B−1 b
B−1 2. p
= cB 3. Primal feasiblity: B−1 b ≥ 0 Dual feasiblity: c
− p
A ≥ 0
4. There might be more than one dual basic solutions associated with the degenerated primal basic solution. 5. All the bases associated with this primal basic feasible solution is not optimal, which means all the dual basic solutions are infeasible. 6. At least one basis associated with this primal basic feasible solution is optimal, which means at least one dual basic solution is feasible. 7. There are more than one basis associated with this dual basic solution, thus there exists at least one column is basic column in one basis and non basis in another. The reduced cost of this column, therefore, has to be zero. Alternatively, we can see that there are more than m active constraints in the dual problem, which means there are zero reduced costs among those of non-basic variables in the primal problem. Primal and dual simplex methods The primal simplex method works towards dual feasibility while maintaining the primal feasibility. The cost is gradually decreased to the optimal cost. The dual simplex method works towards primal feasibility while maintaining the dual feasibility. The cost is gradually increased to the optimal cost. The primal simplex method can detect the −∞ cost (of the primal problem) while the dual simplex method can detect the (primal) problem infeasibility. 2 Sensitivity Analysis Two optimality conditions for a basis are: 1. Primal feasiblity: B−1 b ≥ 0 2. Dual feasiblity: c
− c
B B−1 A ≥ 0
Change in the cost vector c c → c + δej Primal feasibility is maintained while the dual feasibility could be violated. 1. j ∈ N Only cj is affected, cj → cj + δ. cj + δ ≥ 0 ⇔ δ ≥ cj 2 2. j ∈ B cj = 0. Why? � � ci → ci − δe
k:Bk =Aj B−1 Ai = ci − δ B−1 A ki � � � � ci − δ B−1 A ki ≥ 0 ⇔ B−1 A ki δ ≤ ci A new inequality constraint added a
m+1 x ≥ bm+1 is added 1. If the current optimal satisfies this new constraint, it is also the optimal solution for the new problem. 2. If the new constraint is violated then Surplus variable xn+1 is added: a
m+1 x − xn+1 = bm+1 . Construct initial dual simplex tableau for the new problem: The new basis is � � B 0 B= a
B −1 The new basic solution is (x∗ , a
m+1 x∗ − bm+1 ) Check that the new inverse basis matrix is −1 B � = 0 B−1
aB B−1 −1 � Check that the new reduced cost vector is [c
− c
B B−1 A 0] Check that main part of the new tableau is � � 0 B−1 A −1 B A= a
B B−1 A − a
m+1 −1 3