Second-order optimality for set-constrained optimization

29 Views Asked by At

Let $X\subset\Bbb R^n$ be a nonempty closed set and $f\colon X\to\Bbb R$ be a twice continuously differentiable function. Consider the following optimization problem:

$$ \text{(P):}\qquad \min_{x\in X} \quad f(x). $$

For a given $S\subset\Bbb R^n$ and $x\in S$, the contingent cone to $S$ at $x$ is defined by

$$ T_S(x):=\lim\sup_{t\downarrow 0}\frac{S-x}{t}=\{d\in\Bbb R^n\mid \exists t_k\downarrow 0, d_k\to d\text{ with } x+t_kd_k\in S\}. $$

For $x\in S$ and $d\in T_S(x)$, the outer second-order tangent set to $S$ in the direction $d$ is defined by

$$ T^2_S(x;d):=\lim\sup_{t\downarrow 0}\frac{S-x-td}{t^2/2} =\{ w\in\Bbb R^n\mid\exists t_k\downarrow 0,v_k\to w\text{ s.t. } x+t_kd+\frac{1}{2}t_k^2v_k\in S \}, $$

which is also written in the form:

$$ T^2_S(x;d)=\{ w\in\Bbb R^n \mid \exists t_k\downarrow 0,\mathrm{dist}(x+t_kd+\frac{1}{2}t_k^2w, S)=o(t_k^2)\}. $$

Now I want to show the following assertion:

Let $\bar{x}\in X$ be a locally optimal solution of (P). Then, for all $d\in T_X(\bar{x})$ with $\nabla f(\bar{x})^\top d=0$, one has

$$ \nabla f(\bar{x})^\top w+d^\top \nabla^2 f(\bar{x})d\ge 0\quad\forall w\in T^2_X(\bar{x},d). $$


I tried to prove the above theorem as follows but I could not:

Let $x^k:=\bar{x}+t_kd+\frac{1}{2}t_k^2v_k\in X$, where $d\in T_X(\bar{x})$ and for some $t_k$ converging to 0.

By the twice differentiability of $f$, we have

$$ f(x^k)=f(\bar{x})+\nabla f(\bar{x})^\top (x^k-\bar{x})+\frac{1}{2}(x^k-\bar{x})^\top\nabla^2 f(\bar{x})(x^k-\bar{x})+o(\|x^k-\bar{x}\|^2), $$

where $o(\|t\|)$ such that $o(\|t\|)/\|t\|\to 0$ as $t\downarrow 0$.

Since $\bar{x}$ is a locally optimal solution to (P), for sufficient large $k$ it follows from $f(x^k)-f(\bar{x})\ge 0$ that

$$ 0\le\nabla f(\bar{x})^\top (x^k-\bar{x})+\frac{1}{2}(x^k-\bar{x})^\top\nabla^2 f(\bar{x})(x^k-\bar{x})+o(\|x^k-\bar{x}\|^2). $$

By substituting $x^k-\bar{x}$ for $t_kd+\frac{1}{2}t_k^2v_k$ we have

$$ 0\le\nabla f(\bar{x})^\top (t_k d+\frac{1}{2}t^2_kv_k)+\frac{1}{2}(t_k d+\frac{1}{2}t^2_kv_k)^\top\nabla^2 f(\bar{x})(t_k d+\frac{1}{2}t^2_kv_k)+o(\|t_k d+\frac{1}{2}t^2_kv_k\|^2). $$

It follows from $\nabla f(\bar{x})^\top d=0$ that by dividing both sides by $t_k^2$ and x2, we have

$$ 0\le\nabla f(\bar{x})^\top v_k+d^\top\nabla^2 f(\bar{x})d+(t_kd +\frac{1}{4}t_k^2v_k)^\top\nabla^2 f(\bar{x})v_k +o(\|t_k d+\frac{1}{2}t^2_kv_k\|^2). $$

I cannot complete the proof beyond this point.

I would appreciate if you are interested and try to show this.

Thank you.