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

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

引言

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

第一类问题：在数据处理中经常遇到寻求回归方程的问题，即根据一组实验数据建立两个或多个物理量（俗称因素）之间的在统计意义上的依赖关系式。例如一个量 $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
公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！

最后编辑于：2020.02.04 15:36:56

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,590评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 86,808评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,151评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,779评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,773评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,656评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,022评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,678评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 41,038评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,659评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,756评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,411评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,005评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,973评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,203评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,053评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,495评论 2赞 343

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

引言

最小二乘问题的解法

推荐阅读更多精彩内容