主要内容年代pan>
约束非线性优化算法
<年代pan id="csh_constrained" class="anchor_target">
约束优化的定义
gydF4y2Ba约束最小化是求一个向量的问题x这是标量函数的局部极小值f(x),但须受容许范围的限制x:
下列一项或多项成立:<年代pan class="inlineequation">c(x)≤0,量表信(x) = 0,·x≤b,Aeq·x=说真的,l≤x≤u年代pan>.在半无限规划中还有更多的约束条件;看到fsemf问题的表述与算法.
年代ect我on>
fmincon信任区域反射算法<年代ect我on itemprop="content">
非线性极小化的信赖域方法
优化工具箱™求解器中使用的许多方法都是基于<年代pan class="emphasis">信任区域,年代pan>一个简单而强大的优化概念。
gydF4y2Ba为了理解信任域优化方法,考虑无约束最小化问题,最小化f(x),其中函数接受向量参数并返回标量。假设你在一个点上x在n-空间,你想要改进,例如,移动到一个函数值较低的点。基本思想是近似f用一个更简单的函数问,合理地反映了函数的行为f在一个社区N周围的点x.这个邻域是信任域。试验步骤年代是通过最小化(或近似最小化)N.这是信任域子问题,
|
(1)年代trong> |
当前点被更新为x+年代如果<年代pan class="inlineequation">f(x+年代) <f(x)年代pan>;否则,当前点保持不变N,缩小信任区域,并重复试步计算。
gydF4y2Ba定义特定信任区域方法的关键问题是最小化f(x)是如何选择和计算近似问(在当前点定义x),如何选择和修改信任区域N,以及如何准确求解信任域子问题。本节主要讨论无约束问题。后面的部分将讨论由于变量存在约束而引起的其他复杂性。
gydF4y2Ba在标准信任域方法([48]),二阶近似问是由泰勒近似的前两项定义的F在x;附近N通常为球形或椭球形。在数学上,信任域子问题是典型的表述
|
(2)年代trong> |
在哪里g是的梯度f在目前的情况下x,H为Hessian矩阵(二阶导数的对称矩阵),D为对角比例矩阵,Δ为正标量,‖。‖是2-norm。好的算法是用来求解的方程2(见[48]);的所有特征值的计算H牛顿过程应用于特征方程
这种算法提供了一个精确的解决方案方程2.然而,它们需要的时间与的若干因式分解成正比H.因此,对于大规模的问题,需要一种不同的方法。几种近似和启发式策略,基于方程2,已在文献([42]而且[50]).最优化工具箱求解器所遵循的近似方法是将信任域子问题限制在二维子空间中年代([39]而且[42]).一旦子空间年代算好了,功解出来了吗方程2即使需要完整的特征值/特征向量信息(因为在子空间中,问题只是二维的)也是微不足道的。现在主要的工作已经转移到子空间的确定上。
二维子空间年代是在一个预条件共轭梯度过程描述如下。解算器定义年代由。张成的线性空间年代<年代ub>1而且年代<年代ub>2,在那里年代<年代ub>1在梯度的方向上g,年代<年代ub>2要么是近似的牛顿方向,即解
|
(3)年代trong> |
或者一个方向负曲率,
|
(4)年代trong> |
这种选择背后的哲学年代是强迫全局收敛(通过最陡的下降方向或负曲率方向),实现快速的局部收敛(通过牛顿步长,当它存在时)。
gydF4y2Ba利用信任域的思想,可以很容易地给出无约束最小化的草图:
表述二维信任域子问题。
解决方程2确定试验步骤年代.
如果<年代pan class="inlineequation">f(x+年代) <f(x)年代pan>,然后<年代pan class="inlineequation">x=x+年代年代pan>.
Δ调整。
重复这四个步骤直到收敛。信任域维度Δ按照标准规则进行调整。特别是,如果不接受试验步骤,则会减少,即,<年代pan class="inlineequation">f(x+年代)≥f(x)年代pan>.看到[46]而且[49]关于这方面的讨论。
gydF4y2Ba优化工具箱求解器处理一些重要的特殊情况f有专门的函数:非线性最小二乘,二次函数和线性最小二乘。然而,基本的算法思想与一般情况下是相同的。这些特殊情况将在后面的小节中讨论。
年代ect我on>
预条件共轭梯度法
求解大型对称正定线性方程组的常用方法<年代pan class="inlineequation">惠普=-g年代pan>为预处理共轭梯度法(PCG)。这种迭代方法需要计算形式的矩阵-向量乘积的能力2022世界杯八强谁会赢?H·v在哪里v是一个任意向量。对称正定矩阵米是一个<年代pan class="emphasis">预调节器年代pan>为H.也就是说,<年代pan class="inlineequation">米=C<年代up>2年代pan>,在那里<年代pan class="inlineequation">C<年代up>1HC<年代up>1年代pan>是一个条件良好的矩阵或具有聚类特征值的矩阵。
gydF4y2Ba在最小化的背景下,你可以假设黑森矩阵H是对称的。然而,H只有在强极小化函数附近才保证是正定的。PCG算法在遇到负(或零)曲率方向时退出,即<年代pan class="inlineequation">d<年代up>T高清≤0.PCG输出方向p是负曲率的方向还是牛顿系统的近似解<年代pan class="inlineequation">惠普=-g年代pan>.在这两种情况下,p有助于定义在中讨论的信任区域方法中使用的二维子空间非线性极小化的信赖域方法.
年代ect我on>
线性等式约束
线性约束使无约束最小化的情况变得复杂。然而,前面描述的基本思想可以以一种干净和有效的方式进行。优化工具箱求解器中的信任域方法生成严格可行的迭代。
gydF4y2Ba一般的线性等式约束最小化问题可以写成
|
(5)年代trong> |
在哪里一个是一个米- - - - - -- - - - - -------n矩阵(<年代pan class="inlineequation">米≤n年代pan>).一些优化工具箱求解器进行预处理一个的一种基于LU分解的技术来去除严格的线性依赖一个<年代up>T[46].在这里一个被认为是有等级的米.
gydF4y2Ba用来求解的方法方程5与无约束方法有两个显著的区别。首先,一个初始可行点x<年代ub>0,使用稀疏最小二乘步骤计算,那么<年代pan class="inlineequation">斧头<年代ub>0=b年代pan>.其次,将算法PCG替换为简化预处理共轭梯度(RPCG),参见[46]的零空间中,为了计算近似约简的牛顿步长(或负曲率方向)一个).线性代数的关键步骤涉及求解这种形式的方程组
|
(6)年代trong> |
在哪里<年代pan class="inlineequation">
接近一个(小的非零一个设置为零,提供秩不丢失)和C稀疏对称正定近似是H,也就是说,<年代pan class="inlineequation">C=H年代pan>.看到[46]为更多的细节。
年代ect我on>
箱约束
盒子约束问题是这样的形式
|
(7)年代trong> |
在哪里l是一个下界的向量,和u是有上界的向量。的部分(或全部)组成部分l可以等于-∞和的部分(或全部)的分量u可以等于∞。该方法生成一系列严格可行点。在实现鲁棒收敛行为的同时,使用了两种技术来保持可行性。首先,用缩放的修正牛顿步长代替无约束牛顿步长来定义二维子空间年代).第二,反射用来增加步长。
gydF4y2Ba伸缩修正牛顿步是由考察库恩-塔克必要条件而产生的方程7,
|
(8)年代trong> |
在哪里
和向量v(x)的定义如下,对于每个<年代pan class="inlineequation">1≤我≤n年代pan>:
如果<年代pan class="inlineequation">g<年代ub>我年代ub>< 0而且<年代pan class="inlineequation">u<年代ub>我年代ub><∞年代pan>然后<年代pan class="inlineequation">v<年代ub>我年代ub>=x<年代ub>我年代ub>--- - - -u<年代ub>我年代ub>年代pan>
如果<年代pan class="inlineequation">g<年代ub>我年代ub>≥0而且<年代pan class="inlineequation">l<年代ub>我年代ub>>-∞年代pan>然后<年代pan class="inlineequation">v<年代ub>我年代ub>=x<年代ub>我年代ub>--- - - -l<年代ub>我年代ub>年代pan>
如果<年代pan class="inlineequation">g<年代ub>我年代ub>< 0而且<年代pan class="inlineequation">u<年代ub>我年代ub>=∞年代pan>然后<年代pan class="inlineequation">v<年代ub>我年代ub>= 1
如果<年代pan class="inlineequation">g<年代ub>我年代ub>≥0而且<年代pan class="inlineequation">l<年代ub>我年代ub>=-∞年代pan>然后<年代pan class="inlineequation">v<年代ub>我年代ub>= 1