ECE599/CS539 Nonlinear Optimization (Spring 2021) Final Exam (Due: 6pm on June 13, Sunday) Instruction: Students should provide enough detail of the logical procedure of deriving answers. Answers without sufficient justification will receive partial or no credit. For questions involving MATLAB experiments, provide codes with comments. The maximum possible score is 100. 1. (25 points) Consider a constrained optimization problem: minimizex∈Rn f(x) subject to gi(x) ≤ 0, i = 1, . . . , p hi(x) = 0, i = 1, . . . ,m (1) Suppose that f , gi’s, and hi’s are twice continuously differentiable. In this question, we will derive a simple way to check whether a given feasible point x satisfies the KKT conditions. Let xˉ be a feasible point of (1) and W denote the subset of indices of inequality constraints that are active at xˉ, i.e., W {1, . . . , p} is such that i ∈W if and only if gi(xˉ) = 0. Let q denote the cardinality of W. (a) Prove that if there exist real constants λˉi, i ∈W and μˉ1, . . . , μˉm such that f(xˉ) + ∑ i∈W λˉi gi(xˉ) + m∑ i=1 μˉi hi(xˉ) = 0T (2) and λˉi ≥ 0 for all i ∈W, then xˉ satisfies the KKT conditions of (1). (b) Prove that if xˉ satisfies the KKT conditions of (1), then there exist real constants λˉi, i ∈W and μˉ1, . . . , μˉm such that f(xˉ) + ∑ i∈W λˉi gi(xˉ) + m∑ i=1 μˉi hi(xˉ) = 0T and λˉi ≥ 0 for all i ∈W. (c) Let A denote a (q+m) by n matrix with its first q rows being { gi(xˉ) : i ∈W} and its remaining m rows being h1(xˉ), h2(xˉ), . . . , hm(xˉ). Suppose that A has full row rank, i.e., its rows are linearly independent. Show that if there exist λˉi, i ∈ W, and μˉ1, . . . , μˉm satisfying the equation (2), then they can be obtained as follows: λˉ μˉ = (AAT ) 1A · ( f(xˉ)T ). where λˉ denotes a q-dimensional vector consisting of λˉi, i ∈W, and μˉ := (μˉ1, . . . , μˉm). 1 (d) Discuss the implications of your answers to part (a)-(c) on verifying the KKT conditions of (1) for any given point xˉ. 2. (25 points) This is Exercise 2 in Chapter 13 of our textbook [Luenberger & Ye]. Consider the con- strained problem: minimizex∈Rn f(x) subject to x ∈ S (3) Let {ck} denote a sequence of positive real numbers satisfying (i) ck+1 > ck for all k, and (ii) ck →∞. Let P (x) be a penalty function satisfying (i) P (x) is a continuous function of x, (ii) P (x) = 0 if x ∈ S, and (iii) P (x) > 0 if x /∈ S. In addition, let q(c,x) := f(x) + cP (x). Let be a positive real number, and let {xk} be a sequence such that each xk satisfies q(ck,xk) ≤ [min x q(ck,x)] + . In other words, xk might not be a global minimum point of q(ck,x); however, it at least satisfies that q(ck,xk) minx q(ck,x) is bounded above by (e.g., xk could be a local minimum point of q(ck,x) instead of a global minimum point). Let x denote a global minimum point of (3). Prove that any limit point xˉ of {xk} is (i) feasible and (ii) satisfies f(xˉ) ≤ f(x ) + . (Hint: Using the properties of the penalty method discussed in the lectures, first show that f(xk) + ckP (xk) ≤ f(x ) + . Let xˉ be an arbitrary limit point of {xk}. Then, by definition, there exists K {1, 2, . . . , } such that the subsequence {xk}k∈K converges to xˉ. The above inequality can be used together with the subsequence {xk}k∈K to show that P (xˉ) = 0.) 3. (50 points) Penalty Method. Consider the constrained optimization problem: minx∈R4 1 2 xTQx + bTx subject to ∑4 i=1 x 2 i = 1 xi ≥ 0, i = 1, 2, 3, 4; (4) 2 where Q = 2 1 0 10 1 4 3 0.5 0 3 5 6 10 0.5 6 7 , b = 1 0 2 3 . (5) (a) Write the constrained optimization problem (4) in the standard form by properly defining f , h, g1, . . . , g4: minx∈R4 f(x) subject to h(x) = 0 gi(x) ≤ 0, i = 1, 2, 3, 4; (b) Implement the penalty method with the quadratic penalty function to find a local minimum point of this constrained optimization problem. Provide a pseudocode of your implementation that explains the details of main steps clearly and the stopping criteria. (c) Let xk denote the solution at the end of the k-th iteration of the penalty method. And, let ckP (xk) denote the penalty term value at the end of the k-th iteration. Plot (i) f(xk) versus k, (ii) ckP (xk) versus k, and (iii) P (xk) versus k. And, interpret the plots. (d) Let xfinal denote the solution found by your implementation of the penalty method. Check whether the KKT conditions hold at xfinal (you can use the results of Question 1). Check whether the second order necessary condition holds at xfinal. Also check whether the second order sufficient condition holds at xfinal. 3
