METHODS FOR NON-LINEAR LEAST SQUARES PROBLEMS（一）
分章节更新，剩下两部分一周内上传
1. 介绍和定义
在本手册中，我们考虑了以下问题
定义1.1. 最小二乘问题
寻找
x
?
x^*
x?，即以下式子的局部最小值
F
(
x
)
=
1
2
∑
i
=
1
m
(
f
i
(
x
)
)
2
(1.1)
F(\pmb{x})=\frac{1}{2}\sum_{i=1}^{m}{(f_i(\pmb{x}))^2} \tag{1.1}
F(xxx)=21?i=1∑m?(fi?(xxx))2(1.1)
其中，
f
i
:
R
n
→
R
,
i
=
1
,
.
.
.
f_i:\mathbb{R}^n \to \mathbb{R},i=1,...
fi?:Rn→R,i=1,...,
m
m
m 由函数给定，并且
m
≥
n
m\geq n
m≥n。
F ( x ) F(x) F(x) 的定义中的因子 1 2 \frac{1}{2} 21? 对 x ? x^? x? 没有影响。它是为了方便而引入的。
例子1.1.
最小二乘问题的一个重要来源是数据拟合。例如，考虑如下图所示的数据点 ( t 1 , y 1 ) , . . . , ( t m , y m ) (t_1,y_1),...,(t_m,y_m) (t1?,y1?),...,(tm?,ym?):
此外，我们还得到了一个拟合模型
M
(
x
,
t
)
=
x
3
e
x
1
t
+
x
4
e
x
2
t
M(\pmb{x},t)=x_3 e^{x_1 t}+x_4 e^{x_2 t}
M(xxx,t)=x3?ex1?t+x4?ex2?t
该模型取决于参数
x
=
[
x
1
,
x
2
,
x
3
,
x
4
]
T
x=[x_1,x_2,x_3,x_4]^T
x=[x1?,x2?,x3?,x4?]T。我们假设存在一个
x
?
\pmb{x}^*
xxx?满足
y
i
=
M
(
x
?
,
t
i
)
+
?
i
y_i = M(\pmb{x}^*,t_i)+\epsilon_i
yi?=M(xxx?,ti?)+?i?
其中
{
?
i
}
\{\epsilon_i\}
{?i?}是数据序列的（测量）误差，我们假定其行为类似于 “白噪声”。
对于任何给定的
x
\pmb{x}
xxx,我们可以计算残差
f
i
(
x
)
=
y
i
?
M
(
x
,
t
i
)
=
y
i
?
x
3
e
x
1
t
i
?
x
4
e
x
2
t
i
,
i
=
1
,
.
.
.
,
m
.
\begin{matrix} &f_i(x)=y_i - M(\pmb{x},t_i) \\ &=y_i-x_3 e^{x_1 t_i} -x_4 e^{x_2 t_i}, i=1,...,m. \end{matrix}
?fi?(x)=yi??M(xxx,ti?)=yi??x3?ex1?ti??x4?ex2?ti?,i=1,...,m.?
对于最小二乘法的拟合，参数 x ? \pmb{x}^* xxx? 由最小化残差的平方之和来确定。这可以看作是一个当 n = 4 n=4 n=4 时定义1.1中的问题。 M ( x ? , t ) M(\pmb{x}^*,t) M(xxx?,t) 的图形在图1.1中以实线显示。
最小二乘问题是更一般的问题的一个特殊变体：给定一个函数 F : R n → R F:\mathbb{R}^n \to \mathbb{R} F:Rn→R，找到 F F F 的一个参数，使这个所谓的目标函数或成本函数的值最小。
定义1.2. 全局最小值
给定
F
:
R
n
→
R
F:\mathbb{R^n} \to \mathbb{R}
F:Rn→R。寻找
x
?
=
a
r
g
m
i
n
x
{
F
(
x
)
}
(1.2)
\pmb{x}^*=argmin_{\pmb{x}}\{F(\pmb{x})\} \tag{1.2}
xxx?=argminxxx?{F(xxx)}(1.2)
这个问题在一般情况下很难解决，我们只介绍解决更简单的问题的方法，即寻找 F F F 的局部最小化值，一个在一定区域内给出 F F F 的最小值的参数向量。区域的大小由 δ \delta δ 给出，其中 δ \delta δ 是一个小的正数。
定义1.3. 局部最小值
给定
F
:
R
n
→
R
F:\mathbb{R}^n \to \mathbb{R}
F:Rn→R，寻找
x
?
\pmb{x}^*
xxx? 使得
F
(
x
?
)
≤
F
(
x
)
f
o
r
∣
∣
x
?
x
?
∣
∣
<
δ
(1.3)
F(\pmb{x}^*) \leq F(\pmb{x}) \quad for \quad ||\pmb{x}- \pmb{x}^*||<\delta \tag{1.3}
F(xxx?)≤F(xxx)for∣∣xxx?xxx?∣∣<δ(1.3)
在本介绍的其余部分，我们将讨论优化的一些基本概念。第2章简要回顾了对于通用的代价函数寻找局部最小值的方法。关于更多细节，可以参考 Frandsen et al (2004)。在第三章中，我们给出了专门针对最小二乘问题的方法。
我们假设代价函数
F
F
F 是可微并且平滑的，这使得下面的泰勒展开是有效的，
F
(
x
+
h
)
=
F
(
x
)
+
h
T
g
+
1
2
h
T
H
h
+
O
(
∣
∣
h
∣
∣
3
)
(1.4a)
F(\pmb{x}+ \pmb{h})=F(\pmb{x})+\pmb{h}^T\pmb{g}+\frac{1}{2} \pmb{h}^T\pmb{H}\pmb{h}+\mathit{O}(||\pmb{h}||^3) \tag{1.4a}
F(xxx+hhh)=F(xxx)+hhhTg?g??g+21?hhhTHHHhhh+O(∣∣hhh∣∣3)(1.4a)
除非另有说明， ∣ ∣ ? ∣ ∣ ||\cdot|| ∣∣?∣∣表示2-范数， ∣ ∣ h ∣ ∣ = h 1 2 + . . . + h n 2 ||\pmb{h}||=\sqrt{h_1^2+...+h_n^2} ∣∣hhh∣∣=h12?+...+hn2??。
其中
g
\pmb{g}
g?g??g 是梯度,
g
=
F
˙
(
x
)
=
[
?
F
?
x
1
(
x
)
?
?
F
?
x
n
(
x
)
]
(1.4?b)
\pmb{g} = \dot{F}(\pmb{x})=\begin{bmatrix}\frac{\partial F}{\partial x_1}(\pmb{x}) \\ \vdots \\ \frac{\partial F}{\partial x_n}(\pmb{x})\end{bmatrix} \tag{1.4 b}
g?g??g=F˙(xxx)=?????x1??F?(xxx)??xn??F?(xxx)?????(1.4?b)
H
\pmb{H}
HHH 是海塞矩阵
H
=
F
¨
(
x
)
=
[
?
2
F
?
x
i
?
x
j
(
x
)
]
(1.4?c)
\pmb{H}=\ddot{F}(x)=\begin{bmatrix} \frac{\partial^2 F}{\partial x_i \partial x_j}(\pmb{x})\end{bmatrix} \tag{1.4 c}
HHH=F¨(x)=[?xi??xj??2F?(xxx)?](1.4?c)
如果 x ? \pmb{x}^? xxx? 是一个局部最小值，并且 ∣ ∣ h ∣ ∣ ||\pmb{h}|| ∣∣hhh∣∣ 足够小，那么我们就无法找到一个使得 F F F 值更小的点 x ? + h \pmb{x}^?+\pmb{h} xxx?+hhh。将这一观察与式（1.4a）结合起来我们可以得到
理论1.5. 局部最小值的必要条件
如果
x
?
\pmb{x}^*
xxx? 是局部最小值，则
g
?
=
F
˙
(
x
?
)
=
0
\pmb{g}*=\dot{F}(\pmb{x}^*)=0
g?g??g?=F˙(xxx?)=0
我们对满足必要条件的参数使用一个特殊的名称:
定义1.6. 驻点
如果
g
s
=
F
˙
(
x
s
)
=
0
\pmb{g}_s = \dot{F}(\pmb{x}_s)=0
g?g??gs?=F˙(xxxs?)=0
则
x
s
\pmb{x}_s
xxxs? 被称为
F
F
F 的一个驻点。
因此，局部最小值也是一个驻点，而局部最大值也是如此。一个既不是局部最大值也不是局部最小值的静止点被称为鞍点。为了确定一个给定的驻点是否是局部最小值，我们需要在泰勒级数（1.4a）中包含二阶项。代入
x
s
\pmb{x}_s
xxxs? ，我们看到
F
(
x
s
+
h
)
=
F
(
x
s
)
+
1
2
h
T
H
s
h
+
O
(
∣
∣
h
∣
∣
3
)
(1.7)
F(\pmb{x}_s+\pmb{h})=F(\pmb{x}_s) + \frac{1}{2}\pmb{h}^T\pmb{H}_s \pmb{h}+\mathit{O}(||\pmb{h}||^3) \tag{1.7}
F(xxxs?+hhh)=F(xxxs?)+21?hhhTHHHs?hhh+O(∣∣hhh∣∣3)(1.7)
其中
H
s
=
F
¨
(
x
s
)
\pmb{H}_s = \ddot{F}(\pmb{x}_s)
HHHs?=F¨(xxxs?)
从海塞矩阵的定义（1.4c）可以看出，任何
H
\pmb{H}
HHH 都是一个对称矩阵。如果我们要求
H
s
\pmb{H}_s
HHHs? 是正定的，那么它的特征值需要大于某个数字
δ
>
0
\delta>0
δ>0（见附录A），并且
h
T
H
s
h
≥
δ
∣
∣
h
∣
∣
2
\pmb{h}^T\pmb{H}_s\pmb{h} \geq \delta ||\pmb{h}||^2
hhhTHHHs?hhh≥δ∣∣hhh∣∣2
这表明，对于足够小的 ∣ ∣ h ∣ ∣ ||\pmb{h}|| ∣∣hhh∣∣，（1.7）式右边的第三项将被第二项所支配。这个项是正的，所以我们得到
理论1.8. 局部最小值的充分条件
假设 x s \pmb{x}_s xxxs? 是一个驻点，并且 F ¨ ( x s ) \ddot{F}(\pmb{x}_s) F¨(xxxs?) 是正定的。 那么 x s \pmb{x}_s xxxs? 是一个局部最小值。
如果 H s \pmb{H}_s HHHs? 是负定的，那么 x s \pmb{x}_s xxxs? 就是一个局部最大值。如果 H s \pmb{H}_s HHHs? 是不定的（即它的特征值有正有负），那么 x s \pmb{x}_s xxxs? 是一个鞍点。
