Java数据结构代写 | 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 xbe 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 xis the solution of (P) and (λ, ν) is the solution of (D), and that strong duality holds.

Problem 2

Consider the following minimization problem over Rn


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 xR2 . 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) = blank

(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.