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














































































































学霸联盟