2
$\begingroup$

A variant of Newton's method for solving the equality constrained problem \begin{equation} \begin{array}{ll} \min &f(x) \\ \text{s.t.} & h(x) = 0 \end{array} \end{equation}

is as follows:

\begin{equation} \begin{array}{ll} x_{k+1} = x_k - \alpha \left(\nabla_{xx}L(x_k,\lambda_k)\right)^{-1}\nabla_xL(x_k,\lambda_k), \\ \lambda_{k+1} = \lambda_k + \alpha \left(\nabla h(x)^T\nabla_{xx}L(x_k,\lambda_k)\nabla h(x)\right)^{-1} \nabla_{\lambda}L(x_k,\lambda_k), \end{array} \end{equation} where $L$ is the augmented Lagrangian function \begin{equation} L(x,\lambda) = f(x) + \lambda^{T}h(x) + \frac{\mu}{2}\|h(x)\|^2, \end{equation} and $\nabla h(x)^T\nabla_{xx}L(x_k,\lambda_k)\nabla h(x)$ is the dual Hessian.

I am curious about how to prove the global convergence of Newton's method in this scenario. For instance, we can easily prove the convergence of the gradient method: \begin{equation} \begin{array}{ll} x_{k+1} = x_k - \alpha \nabla_xL(x_k,\lambda_k), \\ \lambda_{k+1} = \lambda_k + \alpha \nabla_{\lambda}L(x_k,\lambda_k), \end{array} \end{equation}

by showing that the gradient norm $\|\nabla L(x,\lambda)\|^2 = \|\nabla_x L(x,\lambda) \|^2 + \|\nabla_\lambda L(x,\lambda) \|^2$ is actually decreasing.

Or more generally, if we have the updates \begin{equation} \begin{array}{ll} x_{k+1} = x_k - A_k \nabla_xL(x_k,\lambda_k), \\ \lambda_{k+1} = \lambda_k + B_k \nabla_{\lambda}L(x_k,\lambda_k), \end{array} \end{equation} where $A_k$, $B_k$ are positive semidefinite matrices, can we obtain some convergence results?

I have tried some numerical experiments and the results show that Newton's method does converge at least linearly. But I don't know how to show that mathematically.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .