0
$\begingroup$

When solving a reduced KKT system of a nonlinear (and nonconvex) constrained program after eliminating slack and dual variables, how do we actually take the next step in a primal-dual method?

For example, following notation from NW, if the original nonlinear system is like (19.12) \begin{align} \begin{bmatrix} \nabla_{xx}^2 L & 0 & A_E(x)^T & A_I(x)^T \\ 0 & \Sigma & 0 & -I \\ A_E(x) & 0 & 0 & 0 \\ A_I(x) & -I & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} p_x \\ p_s \\ -p_y \\ -p_z \end{bmatrix} = -\begin{bmatrix} \nabla f(x) - A_E(x)^Ty - A_I(x)^T z \\ z - \mu S^{-1}e \\ c_E(x) \\ c_I(x) - s \end{bmatrix}, \end{align}

then I see how a solution gives us a way to update $x,s,y,z$. However, if we solve a reduced system of the form

\begin{align} \begin{bmatrix} \nabla_{xx}^2 L + A_I(x)^T\Sigma A_I(x) & A_E(x)^T \\ A_E(x) & 0 \end{bmatrix} \begin{bmatrix} p_x \\ -p_y \end{bmatrix} = \text{?} \end{align}

then (1) what is the RHS; and (2) how do we update $s,z$?

EDIT: Can I have some help on the details for how we eliminate variables in moving from the larger system to the smaller system?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Once you have $p_x,p_y$, you can use the second and fourth of the block system you show in your question to compute the updates $p_s,p_z$. They satisfy the equations \begin{align} \begin{bmatrix} \Sigma & -I \\ -I & 0 \\ \end{bmatrix} \begin{bmatrix} p_s \\ -p_z \end{bmatrix} = \begin{bmatrix} z - \mu S^{-1}e \\ c_I(x) - s - A_I(x)p_x \end{bmatrix}. \end{align}

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks! And to confirm, I can use the same approach for calculating step size as if I solved the full system outright? Btw -- I made a typo on the last line of my large system, so I believe the lower left $I$ of your program should be $-I$? $\endgroup$
    – jjjjjj
    Mar 12, 2018 at 14:43
  • 1
    $\begingroup$ Yes, I had already wondered about the minus sign. I fixed it. $\endgroup$
    – Wolfgang Bangerth
    Mar 13, 2018 at 2:58
  • $\begingroup$ And yes, once you have all of the updates $p_\ast$ computed as above, you can do a linear search. $\endgroup$
    – Wolfgang Bangerth
    Mar 13, 2018 at 2:59
  • $\begingroup$ Thanks -- as a follow up, when I computed $p^*$ under the full and reduced systems of my original formulation (using the $\Sigma, -I...$ submatrix to get $p^*_s, p^*_y$), I was getting different results (this was for $dim(x) = 10$ so I don't think numerical issues were present). I believe the RHS is wrong for my reduced system? $\endgroup$
    – jjjjjj
    Mar 13, 2018 at 3:19
  • 1
    $\begingroup$ Isn't the reduced system just some Schur complement? You'll have to go through the derivation again. $\endgroup$
    – Wolfgang Bangerth
    Mar 13, 2018 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.