A Newton-type Method for Constrained Optimization

Titus Pința

Newton differentiability subsumes all aspects of Newton's method

• $F:\bbRn \to \bbRn$ is Newton differentiable at $\xbar$ with $\mathcal{H}F$

1. $F$ is $\mathcal{C^{1}}$, $\mathcal{H}F = \nabla F$
2. $F$ is semismooth

   $F$ is Lipschitz, has directional derivatives and \[ \lim_{x \to \xbar}\frac{\|F'(x; x - \xbar) - F'(\xbar; x - \xbar)\|}{\|x - \xbar\|} = 0 \]

   with $\mathcal{H}F = F'$
3. $F$ is tame (definable in an $o$-minimal structure)

   Collection of subsets of $\gdef\bbR{\mathbb{R}}\bbR^n$, for all $n$, closed under boolean operations, expansions, projections, and polynomial images

   with $\mathcal{H}F = F'$

• $F:\bbRn \to \bbRn$ is Newton differentiable at $\xbar$ with $\mathcal{H}F$

4. ¹ \[ F(x, y) = \begin{bmatrix} 4(x^2 - y) + 2(x - 1) \\ -2(x^2 - y) \end{bmatrix} \quad \mathcal{H}F(x, y) = \left\{2 \begin{bmatrix} 1 + 4 x^2 & -2 x \\ -2 x & 1 \end{bmatrix}\right\} \]
   ¹ R. Bergmann, O. P. Ferreira, E. M. Santos, and J. C. O. Souza. "The difference of convex algorithm on Hadamard manifolds". In: J. Optim. Theory Appl. 201 (2021), pp. 221–251
5. \[\gdef\Id{\operatorname{Id}} F(x) = \left \{ \begin{array}{rl} x & \quad x \in \mathbb{Q}, \\ -x & \quad x \in \bbR \setminus \mathbb{Q} \end{array} \right. \quad \mathcal{H}F(x) = \left \{ \begin{array}{rl} 1 & \quad x \in \mathbb{Q}, \\ -1 & \quad x \in \bbR \setminus \mathbb{Q} \end{array} \right. \]
6. $F$ is Lipschitz, with $\mathcal{H}F = \alpha\Id$ (then $F$ is
   weakly Newton differentiable
   )

• $F:\bbRn \to \bbRn$ is Newton differentiable at $\xbar$ with $\mathcal{H}F$

4. ¹ \[ F(x, y) = \begin{bmatrix} 4(x^2 - y) + 2(x - 1) \\ -2(x^2 - y) \end{bmatrix} \quad \mathcal{H}F(x, y) = \left\{2 \begin{bmatrix} 1 + 4 x^2 & -2 x \\ -2 x & 1 \end{bmatrix}\right\} \]
   ¹ R. Bergmann, O. P. Ferreira, E. M. Santos, and J. C. O. Souza. "The difference of convex algorithm on Hadamard manifolds". In: J. Optim. Theory Appl. 201 (2021), pp. 221–251
5. \[\gdef\Id{\operatorname{Id}} F(x) = \left \{ \begin{array}{rl} x & \quad x \in \mathbb{Q}, \\ -x & \quad x \in \bbR \setminus \mathbb{Q} \end{array} \right. \quad \mathcal{H}F(x) = \left \{ \begin{array}{rl} 1 & \quad x \in \mathbb{Q}, \\ -1 & \quad x \in \bbR \setminus \mathbb{Q} \end{array} \right. \]
6. $F$ is Lipschitz, with $\mathcal{H}F = \alpha\Id$ (then $F$ is
   weakly Newton differentiable
   )

1. $F$ is Lipschitz, with $\mathcal{H}F = \alpha\Id$ (then $F$ is
   weakly Newton differentiable
   )

6. $F$ is Lipschitz, with $\mathcal{H}F = \alpha\Id$

For $F = \nabla f$, then $\mathcal{N}_{\alpha \Id}x = x - \alpha^{-1} \nabla f(x)$

then $\nabla f$ is weakly Newton differentiable and Newton's method converges linearly

• $F:\bbRn \to \bbRn$ is Newton differentiable at $\xbar$ with $\mathcal{H}F$

• $F(\xbar) = 0$

• $F(\xbar) = 0$

Modified Newton Methods

Quasi-Metric Spaces

$\gdef\bbM{\mathbb{M}}H:\bbM \times \bbM \to \bbRn$ is called pseudo-linear if $H(x, x) = 0$

$H^{-}:\bbM \times \bbRn \to \bbM$ is a quasi-inverse if $H^{-}(x, 0) = 0$

$F:\bbM \to \bbRn$ is Newton differentiable at $\xbar$ if there is $\mathcal{H}F$ with \[ \lim_{x \to \xbar}\sup_{H \in \mathcal{H}F(x)}\frac{\|F(x) - F(\xbar) - H(x, \xbar)\|}{\dist(x, \xbar)} = 0 \]

Constrained Optimization

Warm Up

\[ \gdef\minim{\operatorname{minimize}} \gdef\st{\operatorname{subject\ to}} \gdef\minimize#1#2#3{{\begin{array}{ll}% \displaystyle{\underset{#1}{\minim}}\quad& #2 \\% \st & #3% \end{array}}} \gdef\minprob#1#2{\begin{array}{ll}% \displaystyle{\minim_{#1}}\quad& #2 \\% \end{array}} \minimize{x \in \bbRn}{f(x)}{Ax = b}\]

Consider $\tilde{f}:\bbR^{n - m} := \ker A \to \bbR$, $\tilde{f} = f|_{Ax = b}$

Remains to relate $\nabla \tilde{f}$ and $\nabla^2 \tilde{f}$ to $f$

\[\gdef\proj{\operatorname{P}} \nabla \tilde{f} = \proj_{\ker A} \nabla f \qquad \nabla^2 \tilde{f} = \proj_{\ker A} \circ \nabla^2 f \circ \proj_{\ker A} \]

\[ \mathcal{N}_{f}x := x - {(\proj_{\ker A} \circ \nabla^2 f(x) \circ \proj_{\ker A})}^{-1} \proj_{\ker A} \nabla f(x) \]

\[ \minimize{x \in \bbRn}{f(x)}{G(x) = 0} \]

using LinearAlgebra
using Kyrilov

function step(x, F, H, G, J)
    Jₓ = J(x)
    J⁺ = pinv(Jₓ)
    xᴾ = x - J⁺ * G(x)
    P = I - J⁺ * Jₓ

    b = P * F(xᴾ)
    A = P * H(xᴾ) * P

    d = Kyrilov.minres(A, -b)

    return xᴾ + d
end
  

\[\gdef\sker{\operatorname{sker}} \minimize{x \in \bbRn}{f(x)}{G(x) \preceq 0} \]

Regularity: Newton Differentiability

$+$

Operator Splitting

$\Rightarrow$

Constrained Optimization