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?

$\endgroup$
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}

$\endgroup$
  • $\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 '18 at 14:43
  • 1
    $\begingroup$ Yes, I had already wondered about the minus sign. I fixed it. $\endgroup$ – Wolfgang Bangerth Mar 13 '18 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 '18 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 '18 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 '18 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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