Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CIT 594 Module 3 Programming Assignment

Problem 1

Consider the primal problem

(P)minimize f(x) subject to g(x) ≤ 0 and h(x) = 0 where x ∈ Rn

and its dual problem

(D)maximize g(λ, ν) subject to λ ≥ 0 where λ ∈ Rm and ν ∈ Rp.

Note that we do not assume that (P) is convex.

(a) Show that (D) is a convex problem.

(b) Assume that strong duality holds and let x∗ be the solution of (P) and (λ∗, ν∗) be the solution of (D).Show that the triplet (x∗,λ∗, ν∗) satisfifies the KKT conditions.

(c) Assume that (P) is convex and that the triplet (x∗,λ∗, ν∗) satisfifies the KKT conditions. Show that x∗ is the solution of (P) and (λ∗, ν∗) is the solution of (D), and that strong duality holds.

Problem 2

Consider the following minimization problem over Rn

(P)

where z ∈ Rn is a given vector and A ∈ Rp×n, with 1 ≤ p < n, has linearly independent rows.

(a) Is the problem (P) convex? Is the Slater condition satisfified? Justify your answers.

(b) Show that the dual problem of (P) is equivalent to the following minimization problem

(c) Show that z = projX (z) + projX ⊥ (z), where X := range(AT).

Hint: Note how both (P) and (D) can be interpreted as projections onto subspaces.

Problem 3

Consider the following optimization problem

subject to g(x) = 1 − x1 − x2 ≤ 0.

(a) Use the KKT conditions to solve this problem analytically.

(b) Plot the level sets of f by using the contour function for −2 ≤ x1 ≤ 2 and −2 ≤ x2 ≤ 1. On the same fifigure, use plot to draw the boundary of the constraint g and to show the location of the optimal point x∗ ∈ R2 . Submit the plot and the printout of the code used to generate it.

(c) Find the sequence of solutions {xt} obtained using the quadratic penalty method.

Problem 4

Consider the following optimization problem over R2

Consider also the scalar function φ(x2) = 

(a) Is (P) convex? Justify your answer.

(b) Is the function φ coercive? Justify your answer.

(c) Minimize φ over R. Is the solution unique?

(d) Solve (P) by showing the equivalence between (P) and the unconstrained minimization of φ.

(e) Give the expression for the Lagrangian L(x, ν) and solve the dual problem (D).

(f) Does the strong duality hold for (P)? Justify your answer.