MATH-UA 253/MA-UY 3204 - Fall 2022 - Homework #8

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

MATH-UA 253/MA-UY 3204 - Fall 2022 - Homework #8

1.  Prove that a set of first-order necessary conditions for optimality for a pair (x∗ , λ ∗ ) are given by:        ] [λ(x)] =  [b(−)c] .                                                                (2)

2.  Let  Z  ∈ Rn×(n−m)   be such that range(Z)  =  null(A).   Show that if the reduced Hessian  Z ⊤ GZ  is positive definte, then (2) has a unique solution.

3.  Show that if the assumptions for the previous part hold, then x∗ is a strict global minimum for (1).

Problem 2.    Assume G in (1) is positive definite for this problem.  Show that the solution of (2) is given by:

x∗ = G −1A⊤ (AG −1A⊤) AG −1c + G−1  (A⊤ b − c)

λ∗ = (AG −1A⊤) (AG −1c + b) .

(Hint:  compute the block LU factorization of the matrix in (2).)

Problem 3.    Let x be a guess for x∗ , let p = x∗ − x (the optimal step taking us from x to x∗ ), let h = Ax−b (the degree to which the equality constraints are violated), and let g  = c + Gx  (the gradient of the cost function evaluated at x).  Further, let Z ∈ Rn×(n−m)  be a basis matrix for null(A), and let Y ∈ Rn ×m  be a basis matrix for null(A)⊥ .  Decompose p into its part in the Y and Z bases, i.e.  let vY  and vZ  be such that p = YvY  + ZvZ .

1.  Show that (2) can be rewritten as:

] [ ] =  [  ]h(g) .                                                                  (4)

2.  First, show that AYvy  = −h.

3.  Next, show that Z ⊤ GZvz  = −Z⊤ GYvy  − Z ⊤g .

4.  Assume that Z ⊤ GZ is positive definite.  Explain how to solve for p and λ∗ .

Problem 4.    The methods outlined for solving an equality-constrained QP in Problems 2 and 3 are two commonly  used  approaches.   Explain the trade-offs  between these  methods.   What  assumptions  do they require? In terms of the parameters m and n, what is the performance of each method like?