科学计算作业 五

科学计算

陆一洲 5140309557

6.2

(a) 严格凸
(b) 非凸
(c) 严格凸
(d) 凸

6.3

(a) 全局最小值
(b) 鞍点
(c) 全局最小值
(d) 全局最大值

6.7

可行方向集合：$\{(\Delta x_2-2\Delta x_3, \Delta x_2, \Delta x_3)^T\mid \Delta x_2, \Delta x_3\in \mathbb{R}\}$ $$\nabla f(x^*)^Ts=3(\Delta x_2-2\Delta x_3)-3\Delta x_2+6\Delta x_3=0$$ $$s^TH_f(x^*)s=4\Delta x_2^2 - 8\Delta x_2\Delta x_3 + 6\Delta x_3^2=4(\Delta x_2-\Delta x_3)^2+2\Delta x_3^2\geq 0$$ 综上所述，$x*$是约束中的一个极值。

6.9

(a)
因为 $f$ 是一个二次函数，开口向上，因此它的最小值显然在 $x=A^{-1}b$ 时取得。
又由于 $\nabla f(x)=Ax-b$ 且 $H_f{x}=A$。因此牛顿迭代第一步得到 $$s_0=-x_0+A^{-1}b$$ 从而得到 $$x_1=x_0+s_0=A^{-1}b$$ 所以，对于任意初始点，都可以进一步得到最小值所在点。
(b)
由于 $x_0-x^*$ 是 $A$ 的一个特征向量，因此有 $$A(x_0-x^*)=\lambda(x_0-x^*)$$ ，同时由于矩阵 $A$ 是一个正定对称矩阵，我们可以得到 $\lambda>0$。
根据最速下降法，我们首先求出 $s_0=-\nabla f(x_0)=b-Ax_0$。我们要求出一个 $a_0$ 使其最小。
由于 $$\begin{align*}x_0+a_0s_0&=x_0+a_0(b-Ax_0)\\&=x_0+a_0(b-A(x_0-x^*))\\&=x_0+a_0(-A(x_0-x^*))\\&=x_0-a_0\lambda(x_0-x^*)\end{align*}$$ 当我们取 $a_0=\frac{1}{\lambda}$，即有 $x_0+a_0s_0=x^*$。因此通过一次最速下降法迭代我们就可以得到最优解。

6.12

(a)
令 $x$ 是 $S$ 上一局部最优解而非全局最优解，则 $\exists\ x'$ 满足 $f(x')<f(x)$。
设 $l$ 是连接 $x$ 和 $x'$ 的线段。由于 $f$ 是凸函数，所以 $l$ 上的所有点（不含 $x'$）$x_0$ 均有 $$f(x_0)\leqslant l(x_0)<l(x)=f(x)$$ 所以 $x$ 的邻域内总有 $l$ 上的一点 $x_0$ 使得 $f(x_0)<f(x)$。与 $x$ 是局部最优解矛盾，所以 $x$ 不存在。
(b)
因为严格凸函数同时也是凸函数，由上题可知，局部最优解一定是全集最优解。
设 $\exists\ x,x'(x\neq x')\in S$ 同时为 $f$ 的最优解，设 $l$ 是连接 $x$ 和 $x'$ 的线段。由于 $f$ 是凸函数，所以 $l$ 上的所有点（不含 $x'$）$x_0$ 均有 $$f(x_0)<l(x_0)=l(x)=f(x)$$ 又由于 $f(x_0)\geqslant f(x)$ ，矛盾。所以这样的$x$不存在。

1.

设 $Ly=x$，需要解 $ALy=b$。如果同时乘上 $L'$，那么问题转换成了求解 $L'ALy=L'b$。
那么可以构造函数 $f(y)=\frac{1}{2}y'L'ALy-L'by=0$，求解这个方程的最小值，那么它的最小值就是 $L'AL'y=L'b$ 的解。
根据 $Ly=x$，即可求出原方程解。

2.

使用线性搜索的共轭梯度法。使用函数 $$f(x)=\frac{1}{2}x_1^2+\frac{5}{2}x_2^2$$ 进行计算。得到结果为 $\begin{pmatrix}7.88609e-9\\-1.51722e-9\end{pmatrix}$ 与 最小值 $\begin{pmatrix}0\\0\end{pmatrix}$ 很接近，所以是正确的。