优化作业1

1

对于无约束优化问题，若函数 $f(x)$ 在点 $\bar x$ 可微，如果存在方向 $d$ 使得$\nabla f(x)^Td <0$，证明 $d$ 是点 $\bar x$ 处的一个下降方向.

Taylor expand:

$$\begin{aligned} f(\bar x +ad) &= f(\bar x)+ a \nabla f(\bar x)^Td+ o(\|ad\|)\\ &=f(\bar x)+ a[\nabla f(\bar x )^T d + o(\|ad\|)/a] \end{aligned}$$

when $a\to 0$ : $\quad o(\|ad\|)/a \to 0$
$\because \nabla f(\bar x )^Td < 0$, therefore when $a\in (0,\sigma )$ is small enough

$$\nabla f(\bar x )^T d + o(\|ad\|)/a <0$$

therefore $f(\bar x + ad) < f(x) \quad \square$

2

对正定二次函数 $f(x)=\frac{1}{2}x^TAx+b^T x$ 在点 $x_k$ 求出沿下降方向 $d_k$ 作精确搜索的步长 $a_k$

$$\begin{aligned} f(x_k+ad_k) &=\frac{1}{2}x_k^TAx_k + a^2 d_k^TAdd_k + ad_k^TAx_k + ax_k^TAd_k +b^Tx_k + ab^Td_k\\ f'(a) &= 2a d_k^TAd_k +d_k^TAx_k +x_k^TAD_k+b^Td_k\\ \end{aligned}$$

let $f'(a)=0$ :

$$a=\frac{d_k^TAx_k+x_k^TAd_k+b^Td_k}{-2d_k^TAd_k}$$

3

3.1

$\{2^{-k}\}$线性收敛
when $k\to \infty, \; 2^{-k}\to 0$

$$\lim_{k\to \infty} \frac{\|x_{x+1}-x^*\|}{\|x_k-x^*\|}=\lim_{k\to \infty} \frac{\|2^{-k-1\|}}{\|2^{-k}\|}=\frac{1}{2}$$

3.2

$\{k^{-k}\}$超线性收敛
when $k\to \infty, \; k^{-k}\to 0$

$$\lim_{k\to \infty} \frac{\|x_{x+1}-x^*\|}{\|x_k-x^*\|}=\lim_{k\to \infty} \frac{\|k^{-k-1\|}}{\|k^{-k}\|}=\lim_{k\to \infty} \frac{1}{k}=0$$

3.3

$\{a^{2^k}\}\quad (0<a<1)$ 二阶收敛

$$\lim_{k\to \infty} \frac{\|x_{x+1}-x^*\|}{\|x_k-x^*\|}=\lim_{k\to \infty} \frac{\|a^{2^{k+1}}\|}{\|(a^{2^k})^2\|}=1$$

4

（非精确线搜索步长的存在性）设$f(x_k+ad_k)$在 $a>0$ 时有下界，且 $\nabla f(x_k)^Td_k <0$，则必存在 $a_k$ ，在点$x_k + a_k d_k$ 处满足Wolfe 准则或者 Armijo- Goldstein 准则.

proof:
Wolfe: $f(x_k+ad_k)$在 $a>0$ 时有下界, 则 $l(a) = f(x_k)+ \rho a\nabla f(x_k)^Td_k$ 一定与之相交，记交点为$a_0$ :

$$f(x_k+a_0d_k) = f(x_k)+ \rho a_0\nabla f(x_k)^Td_k$$

由微分中值定理可知，$\exists a_1 \in (0 , a_0)$ 使得

$$f(x_k + a_0 d_k) - f(x_k) = a_0 \nabla f(x_k + a_1 d_k)^T d_k$$

代入得

$$\nabla f(x_k + a_1 d_k)^T d_k= \rho \nabla f(x_k)^Td_k$$

$1>\sigma>\rho>0$ :

$$\rho \nabla f(x_k)^Td_k > \sigma \nabla f(x_k)^Td_k$$

故

$$\nabla f(x_k + a_1 d_k)^T d_k > \sigma\nabla f(x_k)^Td_k$$

A-G: 若 $\rho$ 与0足够近则第一个不等式一定满足, 考虑第二个不等式的情况。
若不然，对于 $\forall a >0$ :

$$f(x_k + ad_k)< f(x_k)+(1-\rho)a\nabla f(x_k)^Td_k$$

when $a\to \infty, \; RHS \to -\infty\quad$
与 $f(x_k+ad_k)$ 在 $a>0$ 时有下界矛盾

5

利用最优性条件求下面函数的稳定点，并确定其类型：

5.1

$f(x) = 2x_1^2 + x_2^2 -2x_1x_2 +2x_1^3 +x_1^4$

$$\nabla f = \begin{pmatrix} 4x_1-2x_2+6x_1^2+4x_1^3\\ 2x_2-2x_1 \end{pmatrix}=0$$

$(0,0), (-1,-1), (-0.5,-0.5)$

$$\nabla^2 f = \begin{pmatrix} 4+12x_1+12x_1^2 &-2\\ -2 & 2x_2 \end{pmatrix}=0$$

$$\nabla^2 f = \begin{pmatrix} 4 &-2\\ -2 & -2 \end{pmatrix} \qquad \begin{pmatrix} 4 &-2\\ -2 & 0 \end{pmatrix} \qquad \begin{pmatrix} 1 &-2\\ -2 & -1 \end{pmatrix}$$

其中 $(0,0)$ 半正定，为极小稳定点。其余不定.

5.2

$f(x)= 2x_1^3 -3x_1^2 -6x_1x_2(x_1-x_2-1)$

$$\nabla f = \begin{pmatrix} 2x_1^2-6x_1-12x_1x_2+6x_2^2+6x_2\\ -6x_1^2+12x_1x_2+6x_1 \end{pmatrix}=0$$

$(0,0), (0,-1), (1,0), (-1,-1)$

$$\nabla^2 f = 6\begin{pmatrix} 2x_1 &x_2-x_1+1\\ x_2-x_1+1 & 2x_1 \end{pmatrix}=0$$

$$\frac{1}{6}\nabla^2 f = \begin{pmatrix} 0 &1\\ 1 & 0 \end{pmatrix} \qquad \begin{pmatrix} 0 &0\\ 0 & 0 \end{pmatrix} \qquad \begin{pmatrix} 2 &-1\\ -1 & 2 \end{pmatrix} \qquad \begin{pmatrix} -2 &1\\ 1 & -2 \end{pmatrix}$$

其中 $(0,0), (0,-1)$ 不定；$(1,0)$ 正定，为极小值点；$(-1,-1)$ 负定，为极大指点。