Handed out: 2023-03-13.

Due: Friday 2023-03-22 at 4 pm EDT. Papers must be handed in on-line using the labeled dropbox on Crowdmark.  Each question is handed in as a separate upload. You can either prepare your solutions electronically using, e.g., LaTeX, upload handwritten images from a tablet device, or hand-write them and submit a scan.  In the latter case, please take care that the scan is of good quality with a white background.

1.  (a) Let U = e − ^ne1 , where e ∈ Rn  is the vector of all 1’s and e1  is the first column of the identity matrix.  Let u = U/∥U ∥ . Confirm that uT u = 1.  Then show that

Q = I − 2uuT  is an orthogonal matrix by multiplying QT Q and simplifying.

(b) Show that columns 2 : n of Q from part (a) form an orthonormal basis of e⊥ . [Hint: this will follow from an analysis the first column of Q, i.e., the value of Qe1  combined with the result from Slide 7 of M6.]

(c) Ordinarily matrix-vector multiplication requires 2n2 +O(n) operations, but for some special cases it can be faster. Let 北 ∈ Rn  be arbitrary. Explain how to multiply Q北, where Q is as in part (a)– (b), in O(n) operations by using the formula for Q.  Count the operations (in terms of n) required by your algorithm accurate to the leading term. In other words, determine a running time of the form“an,”where a is a constant that you determine, as well as an explanation.

2. Recall that the SCQP algorithm presented in lecture requires solution of an EQP instance on every iteration. Suppose the null-space method is used an EQP instance, and use the notation from M12: min 北T H北/2 + gT 北 subject to A北 = b, where A ∈ Rp×n   and rank(A) = p.  Recall that the SCQP algorithm needs both 北, the EQP solution, and w, the Lagrange multiplier of the solution. An issue with using the null- space method (versus the full-space or range-space methods) for EQP is that it does not directly produce w . Develop a method to post-process the results of the null-space method in order to obtain w .

Important note: The vector“w”in this question and in SCQP refers to the Lagrange multiplier in M12.  This is different from the vector“w”appearing in M32 in the description of the null-space method.

Suggested approach: Given the solution 北 ∗ to EQP obtained by the null-space method,

w can be found from the equation H北∗ + g = −AT w in M12.  Note that after the null-space method completes, it is guaranteed that H北∗ + g ∈ Range(AT ). The null- space method yields a QR factorization of AT . Use this QR-factorization to solve the equation Hx* +g = −AT w for w . Note that the matrix R in the full QR factorization has more rows (n) than columns (p), so R −1  is undefined. My solution cites the result of PS3Q2.

3. The SCQP algorithm presented in lecture generalizes to the case that H is positive semidefinite but not positive definite, but more cases are needed for the analysis.

Consider the case that H is positive semidefinite but not positive definite and the (EQP)k  subproblem is unbounded below.  In particular, suppose that there exists a nonzero vector p such that xk−1  + αp is feasible for (EQP)k  for all α > 0 and such that (xk−1 + αp)T H(xk−1 + αp)/2 + gT (xk−1 + αp) → −∞ strictly monotonically as t → ∞ . Argue that this case can be handled using the Case 1 analysis of the SCQP algorithm from lecture.  In other words, explain how to define a point xk  with the properties that:

❼ xk  is feasible for both (EQP)k  and SCQP,

❼ Sk−1 ⊊ Sk , and

❼ f(xk ) < f(xk−1).

4.  (a) The SCQP algorithm presented in lecture (positive definite case) requires compu- tation of two scalars, α* in Case 1 and ϵ in Case 2.  The scalar α* > 0 was defined as:

α* = max{α : xk−1 + αp ≥ 0}.

Write a computable formula or pseudocode to obtain α* in terms of xk−1  and p. The formula will presumably involve some kind of loop or “min”statement. The formula needs to identify both α* and i, the index that is driven to 0 when xk−1  is updated to xk .  “Computable” in this sense means that it could be implemented in a Matlab program.

Based on the properties of p established in lecture, include an argument that α* defined by your formula is well defined and is positive.

(b) Download the code for SCQP from the Learn website.  This code is missing the statements to compute α* and i, where i is the position of the entry of xk that is driven to 0 in Case 1. Implement your result from part (a) into the Matlab code.

Once your code is ready, run the test case from the course website.  In my code, the test case required 33 iterations. Also, after termination, verify all the KKT conditions computationally (e.g., type min(z) at the command prompt to check whether any

entries of z are negative; typing max(x .*z) checks complementarity,              norm(  -  )

checks the gradient equation etc.).  Hand in a listing of your code, a printout of the run, and the checks of the KKT conditions.