Consider the linear programming problem minimize CTX subject to Ax-b=0 -X 0 (10 pts) (a) Write...

 

Transcribed Image Text:

Consider the linear programming problem minimize CTX subject to Ax-b=0 -X ≤0 (10 pts) (a) Write down the KKT condition for the problem. (8 pts) (b) Use part (a) to show that if there exists an optimal feasible solution to the linear program, then there exists a feasible solution to the corresponding dual problem that achieves an objective function value that is the same as the optimal value of the primal (compare this with Theorem 17.1). (7 pts) (c) Use parts a and b to prove that if x* is an optimal feasible solutions of the primal, then there exists a feasible solution * to the dual such that (cT - 2*A)x* = 0 (compare this with Theorem 17.3). Consider the linear programming problem minimize CTX subject to Ax-b=0 -X ≤0 (10 pts) (a) Write down the KKT condition for the problem. (8 pts) (b) Use part (a) to show that if there exists an optimal feasible solution to the linear program, then there exists a feasible solution to the corresponding dual problem that achieves an objective function value that is the same as the optimal value of the primal (compare this with Theorem 17.1). (7 pts) (c) Use parts a and b to prove that if x* is an optimal feasible solutions of the primal, then there exists a feasible solution * to the dual such that (cT - 2*A)x* = 0 (compare this with Theorem 17.3).

Answer rating: 100% (QA)

a The KKT condition for the problem is x is an optimal feasible solution if and only if 1 Ax b 0 2 C... View the full answer