无约束最优化(五) 最小二乘法问题的解法

作者: 小小何先生 | 来源:发表于2019-12-07 16:57 被阅读0次

在数据处理中，经常遇到寻求回归方程的问题，即根据一组实验数据，建立两个或多个物理量(舒称因素)之间的在统计意义上的依赖关系式。

引言

最小二乘模型可以解决两类实际问题。

第一类问题：在数据处理中经常遇到寻求回归方程的问题，即根据一组实验数据建立两个或多个物理量（俗称因素）之间的在统计意义上的依赖关系式。例如一个量 $y$ 与另一个或几个量 $t_{1},···，t_{l}$ 有关系。这类问题的一般性描述如下。假定要建立量 $y$ 与 $l$ 个量 $t_{1},···，t_{l}$ 之间的依赖关系式，设方程为：
$y = F(t_{1},t_{2},···，t_{l};x_{1},x_{2},···，x_{n})$
其中 $F$ 的形式事先给定， $x_{1}，···，x_{n}$ 是待定参数。有 $m( > n)$ 组实验数据：
$\left[t_{1}^{(i)}, t_{2}^{(i)}, \cdots, t_{l}^{(i)} ; y^{(i)}\right]^{T}, \quad i=1,2, \cdots, m$
其中 $t_{1},···，t_{l}$ 是试验中的已知数据，而 $y$ 是实验后得到的结果。问题是，如何确定 $n$ 个参数 $x_{1},x_{2},···，x_{n}$ 从而建立起回归方程。把第 $i$ 个实验点的自变量 $t_{1}^{(i)}, t_{2}^{(i)}, \cdots, t_{l}^{(i)}$ 代入到其中就会得到相应的函数值。
$\tilde{y}^{(i)}=F\left(t_{1}^{(i)}, t_{2}^{(i)}, \cdots, t_{l}^{(i)} ; x_{1}, x_{2}, \cdots, x_{n}\right)$
$\tilde{y}^{(i)}$ 是真实值 $y^{i}$ 的假设值。当然希望它们之差的绝对的假设值。当然希望它们之差的绝对
$\min \sum_{i=1}^{m}\left[F\left(t_{1}^{(i)}, t_{2}^{(i)}, \cdots, t_{j}^{(i)} ; x_{1}, x_{2}, \cdots, x_{n}\right)-y^{(i)}\right]^{2}$
是非常自然的事情。这就是最小二乘模型。令
$f_{i}\left(x_{1}, \cdots, x_{n}\right)=F\left(t_{1}^{(i)}, \cdots, t_{i}^{(i)} ; x_{1}, \cdots, x_{n}\right)-y^{(i)}$
则最小二乘模型变为
$\min \sum_{i=1}^{m} f_{i}^{2}\left(x_{1}, \cdots, x_{n}\right)$
令 $x=(x_{1},x_{2},···x_{n})^{T}$ ， $f(x)=\left(f_{1}(x), \cdots, f_{m}(x)\right)^{T}$ 则又变成
$\min \sum_{i=1}^{m} f(x)^{T}f(x)$
求它的最优解即称为求解最小二乘问题，将最优解 $x=(x_{1}^{*},x_{2}^{*},···x_{n}^{*})^{T}$ 代入到 $y = F(t_{1},t_{2},···，t_{l};x_{1},x_{2},···，x_{n})$ 中所得 $y = F(t_{1},t_{2},···，t_{l};x_{1}^{*},x_{2}^{*},···x_{n}^{*})$ 即为回归方程。显然最小二乘问题是无约束规划，但由于其特殊结构，有其特殊的求解方法。

当所有的 $f_{i}\left(x_{1}, \cdots, x_{n}\right)=F\left(t_{1}^{(i)}, \cdots, t_{i}^{(i)} ; x_{1}, \cdots, x_{n}\right)-y^{(i)}$ 均是 $x_{1},x_{2},···x_{n}$ 的线性函数时，称为线性最小二乘问题，否则，称为非线性最小二乘问题。

第二类问题：求解方程组（数学问题）
$\left.\begin{array}{l}{f_{1}\left(x_{1}, x_{2}, \cdots, x_{n}\right)=0} \\ {f_{2}\left(x_{1}, x_{2}, \cdots, x_{n}\right)=0} \\ {\vdots} \\ {f_{m}\left(x_{1}, x_{2}, \cdots, x_{n}\right)=0}\end{array}\right\}$
如是线性方程组，则为 $Ax-b=0$ ，当 $R(A) < R(A,b)$ 时，无解，但确实需要求解它。《线性代数》无办法。如是非线性方程组，在数学上求迭代解也非常麻烦，为此求解
$\min \sum_{i=1}^{m} f_{i}^{2}\left(x_{1}, \cdots, x_{n}\right)$
是非常自然的事情。它也是一个最小二乘问题。

最小二乘问题的解法

(1) 线性最小二乘问题

当 $f(x)$ 取线性函数形式，即 $f(x)=Ax-b$ ， $A_{m \times n}$ ，则线性最小二乘问题为 $min(Ax-b)^{T}(Ax-b)$ 。其极小点的解 $x^{*}$ 有以下充要条件： $A^{T} A x^{*}=A^{T} b$ 。

(2) 非线性最小二乘问题

假定选定初始点 $x_{0}$ 后，经过 $k$ 次迭代已求得 $x_{k}$ 。现在考虑 $x_{k+1}$ 的求法。与Newton法的基本思想相类似，把 $f(x)$ 线性化，用线性最小二乘问题的解去逼近非线性最小二乘问题的解。具体做法如下。

把 $f(x)$ 的第 $i$ 个分量在 $x_{k}$ 点处作Taylor级数展开，即
$f_{i}(x) \approx f_{i}\left(x_{k}\right)+\nabla f_{i}\left(x_{k}\right)^{T}\left(x-x_{k}\right), \quad i=1,2, \cdots m$
即有
$\left\{\begin{array}{l}{f_{1}(x) \approx f_{1}\left(x_{k}\right)+\left(\frac{\partial f_{1}\left(x_{k}\right)}{\partial x_{1}}, \cdots, \frac{\partial f_{1}\left(x_{k}\right)}{\partial x_{n}}\right)\left(x-x_{k}\right)} \\ {\vdots} \\ {f_{m}(x) \approx f_{m}\left(x_{k}\right)+\left(\frac{\partial f_{m}\left(x_{k}\right)}{\partial x_{1}}, \cdots, \frac{\partial f_{m}\left(x_{k}\right)}{\partial x_{n}}\right)\left(x-x_{k}\right)}\end{array}\right.$
令 $f(x)=\left(f_{1}(x), \cdots, f_{m}(x)\right)^{T}$ ，
$A_{k}=A\left(x_{k}\right)=\left[\begin{array}{cccc}{\frac{\partial f_{1}\left(x_{k}\right)}{\partial x_{1}}} & {\frac{\partial f_{1}\left(x_{k}\right)}{\partial x_{2}}} & {\cdots} & {\frac{\partial f_{1}\left(x_{k}\right)}{\partial x_{n}}} \\ {\partial f_{2}} & {\frac{\partial f_{2}\left(x_{k}\right)}{\partial x_{2}}} & {\cdots} & {\frac{\partial f_{2}\left(x_{k}\right)}{\partial x_{n}}} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ {\frac{\partial f_{m}\left(x_{k}\right)}{\partial x_{1}}} & {\frac{\partial f_{m}\left(x_{k}\right)}{\partial x_{2}}} & {\cdots} & {\frac{\partial f_{m}\left(x_{k}\right)}{\partial x_{n}}}\end{array}\right]$
则上式可写成矩阵-向量形式
$f(x) \approx f(x_{k}) + A_{k}(x-x_{k})$
称 $A_{k}$ 是向量值函数 $f(x)=(f_{1}(x), ···， f_{m}(x))^{T}$ 在点 $x_{k}$ 处的Jacobi矩阵。从而求解：
$min(f_{k}+A_{k}(x-x_{k}))^{T}(f_{k}+A_{k}(x-x_{k})$
将它的最优解作为下一个迭代点 $x_{k+1}$ 。显然
$\begin{array}{l}{\min \left(f_{k}+A_{k}\left(x-x_{k}\right)\right)^{T}\left(f_{k}+A_{k}\left(x-x_{k}\right)\right)} \\ {=\min \left(A_{k} x-\left(A_{k} x_{k}-f_{k}\right)\right)^{T}\left(A_{k} x-\left(A_{k} x_{k}-f_{k}\right)\right)}\end{array}$
是线性最小二乘问题，可由上一段方法求解。因此 $x_{k+1}$ 必满足方程
$A_{k}^{T}A_{k}x=A_{k}^{T}(A_{k}x_{k}-f_{k})=A_{k}^{T}A_{k}x_{k}-A_{k}^{T}f_{k}$
如果 $A_{k}^{T}A_{k}$ 是可逆的，则：
$x_{k+1}=\left(A_{k}^{T} A_{k}\right)^{-1}\left[A_{k}^{T} A_{k} x_{k}-A_{k}^{T} f_{k}\right]=x_{k}-\left(A_{k}^{T} A_{k}\right)^{-1} A_{k}^{T} f_{k}$
这相当于 $x_{k+1}=x_{k}+p_{k}$ 搜索方向为 $p_{k}=-(A_{k}^{T}A_{k})^{-1}A_{k}^{T}f_{k}$ 步长为1的过程。

称它为非线性最小二乘问题的Gauss-Newton迭代公式，而由这个公式所产生的算法称为Gauss-Newton法。当 $f(x)$ 满足一定的条件，并且 $x_{0}$ 充分靠近极小点 $x^{*}$ 时，Gauss-Newton法是收敛的。

需要指出的是，即使在每次迭代中 $A_{k}^{T}A_{k}$ 都是可逆的，也保证不了算法是下降算法。特别是当初始点 $x_{0}$ 远离极小点 $x^{*}$ 时，算法很可能发散。但是，当 $A_{k}^{T}A_{k}$ 可逆时，所确定的 $p_{k}$ 是目标函数在点 $x_{k}$ 处的下降方向。

我的微信公众号名称：深度学习与先进智能决策
微信公众号ID：MultiAgent1024
公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！

无约束最优化(五) 最小二乘法问题的解法

引言

最小二乘问题的解法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

最优化