GYDF4y2Ba约束极小化问题是寻找一个向量的问题
符合下列条件的:
最优化工具箱™求解器中使用的许多方法都基于
GYDF4y2Ba为了理解信任域优化方法,考虑无约束极小化问题,最小化
当前点被更新为
GYDF4y2Ba定义特定信赖域最小化方法的关键问题
GYDF4y2Ba在标准信赖域方法中(
在哪里
这样的算法提供了一个精确的解决方案
这种选择背后的哲学
GYDF4y2Ba使用信任区域思想的无约束最小化的草图现在很容易给出:
构建二维信任域子问题。
解决
如果
Δ调整。
这四个步骤重复,直到收敛。信任区域维度Δ根据标准规则进行调整。特别是,如果试验步骤不被接受,它就会减少,即:
GYDF4y2Ba最优化工具箱求解器处理一些重要的特殊情况
求解大型、对称、正定线性方程组的一种流行方法
GYDF4y2Ba在最小化的情况下,你可以假设Hessian矩阵
线性约束使描述的无约束极小化情况复杂化。然而,前面描述的基本思想可以以一种干净有效的方式进行。最优化工具箱求解器中的信任区域方法生成严格可行的迭代。
GYDF4y2Ba给出了一般线性等式约束极小化问题
在哪里
GYDF4y2Ba用来求解的方法
在哪里
方框约束问题是这样的
在哪里
GYDF4y2Ba缩放的修正牛顿阶跃是通过考察库恩-塔克必要条件得到的
在哪里
和向量
如果
如果
如果
如果
非线性系统
GYDF4y2Ba缩放的修正牛顿阶跃
在
和
在这里
GYDF4y2Ba第二,
在约束优化中,总的目标是将问题转化为一个更容易的子问题,然后将其作为迭代过程的基础进行求解。一大类早期方法的一个特点是,通过对约束边界附近或之外的约束使用惩罚函数,将约束问题转化为基本的无约束问题。以这种方式,约束问题通过一系列参数化的无约束优化来解决,这些优化在(序列的)极限内收敛到约束问题。这些方法现在被认为是相对低效的,并已被专注于解决问题的方法所取代
GYDF4y2Ba指GP(
除了原有的约束
GYDF4y2Ba第一个方程描述了目标函数与解点主动约束之间的梯度的抵消。对于要取消的梯度,拉格朗日乘数(
KKTGYDF4y2Ba方程的解构成了许多非线性规划算法的基础。这些算法试图直接计算拉格朗日乘数。约束拟牛顿方法通过拟牛顿更新过程积累KKT方程的二阶信息来保证超线性收敛。这些方法通常被称为顺序二次规划(SQP)方法,因为QP子问题在每个主要迭代中被解决(也被称为迭代二次规划、递归二次规划和约束变量度量方法)。
GYDF4y2Ba这个
SQP方法代表了非线性规划方法的发展现状。Schittkowski
GYDF4y2Ba根据比格斯的研究
GYDF4y2Ba鉴于GP中的问题描述(
在这里你简化
(14) |
这个子问题可以用任何QP算法来解决(例如,
x
步长参数
GYDF4y2Ba使用SQP,非线性约束问题通常比无约束问题的迭代次数更少。其中一个原因是,由于可行区域的限制,优化器可以对搜索方向和步长做出明智的决定。
GYDF4y2Ba考虑
与无约束情况下的140次迭代相比,SQP实现在96次迭代中解决了这个问题。
图5-3,非线性约束Rosenbrock函数的SQP方法
SQP的实现包括三个主要阶段,我们将在以下小节简要讨论:
更新Hessian矩阵。在每一次主要迭代中,拉格朗日函数的Hessian的正定拟牛顿近似,
在哪里
鲍威尔
在哪里
和增加
GYDF4y2Ba功能fmincon
fminimax,fgoalattain,费塞米夫所有用SQP。如果显示 被设置为“国际热核实验堆” 在选项 ,然后给出函数值和最大约束违背量等各种信息。当Hessian必须用前一步骤的第一阶段进行修改以保持它的正定时,那么黑森改良 会显示出来。如果Hessian必须再次使用上述方法的第二阶段进行修改,那么黑森修改两次会显示出来。当QP子问题不可行时,则不可行会显示出来。这种显示通常不会引起关注,但表明问题是高度非线性的,收敛时间可能比通常更长。有时候消息没有更新 ,显示“?
几乎是零。这可能表明问题设置是错误的,或者您正在试图最小化一个非连续函数。二次规划的解决方案。 在每个主要的迭代SQP方法,解决如下形式的QP问题,其中A.我指的是我 第四排M——------N矩阵A..
(18)
最优化工具箱函数中使用的方法是一种主动的集合策略(也称为投影方法),类似于Gill等人的方法[18] 和[17] .对线性规划(LP)和二次规划(QP)问题进行了改进。
GYDF4y2Ba解决过程包括两个阶段。第一阶段包括可行点(如果存在)的计算。第二阶段包括生成收敛于解的可行点迭代序列。在这种方法中,一个活动集,
,这是对解决方案点处的活动约束(即约束边界上的约束)的估计。实际上,所有QP算法都是活动集方法。强调这一点是因为存在许多不同的方法,这些方法在结构上非常相似,但描述术语却大不相同。
在每个迭代更新K,用来形成搜索方向的基础
.相等约束始终保持在活动集中
.变量的符号
是用来区分它和DK在SQP方法的主要迭代中。搜索方向
,并使目标函数最小化,同时保持在任何主动约束边界上。的可行子空间
是由基组成的吗ZK哪些列正交于活动集的估计
(例如,
).的列的任意组合的线性和形成的搜索方向ZK,保证保持在主动约束的边界上。
GYDF4y2Ba矩阵ZK是最后形成的吗M–L矩阵QR分解的列
,在那里L是活动约束和约束的数量l < m.也就是说,ZK是由
(19)
在哪里
一次ZK找到后,将显示新的搜索方向
寻求最小化Q(D)在哪里
是在主动约束的零空间中。也就是说,
是列的线性组合ZK:
为向量P.
GYDF4y2Ba如果你把这个二次函数看成是P,通过替换
,你有
(20)
对它求导P收益率
(21)
∇Q(P)
被称为二次函数的投影梯度,因为它是在由定义的子空间中投影的梯度ZK.这个词
叫做投影黑森。假设Hessian矩阵H是正定的(这是SQP实现中的情况),那么函数的最小值是多少Q(P定义的子空间ZK发生在∇Q(P) = 0 ,它是线性方程组的解
(22)
然后对该形式采取步骤
(23)
在每次迭代时,由于目标函数的二次性质,只有两种步长选择α.这是团结前进的一步
函数的最小值的精确步是否限制在零空间
.如果可以在不违反约束的情况下采取这样的步骤,那么这就是QP (方程18 ).否则,继续前进
到最近的约束小于单位,在下一次迭代时一个新的约束被包含在活动集中。任意方向到约束边界的距离
是由
(24)
它是为不在激活集中的约束定义的,并且方向
为约束边界,即:
.
GYDF4y2Ba当N在活动集中包含独立约束,没有极小值的位置,拉格朗日乘子,λK,满足非奇异线性方程组
(25)
如果所有的元素λK是积极的,xK为QP (方程18 ).然而,如果有λK为负,且组件不对应相等约束,则从活动集中删除相应的元素,并寻找新的迭代。
初始化。 该算法需要一个可行的起始点。如果从SQP方法中得到的当前点是不可行的,那么可以通过求解线性规划问题找到一个点
(26)
的符号A.我表示我矩阵的第一行A..你可以找到一个可行点(如果存在的话)方程26 通过设置x转换为满足相等约束的值。您可以通过求解由等式约束集形成的线性方程组的过定或过定来确定这个值。如果这个问题有一个解决方案,那么松弛变量γ设为该点的最大不等式约束。
针对LP问题,可以修改前面的QP算法,将搜索方向设置为每次迭代的最陡下降方向GK为目标函数的梯度(等于线性目标函数的系数)。
(27)
如果使用前面的LP方法找到可行点,则进入主QP阶段。搜索方向
用搜索方向初始化
从解线性方程组中发现
(28)
在哪里GK目标函数的梯度是否在当前迭代中xK(例如,HxK+C).
GYDF4y2Ba如果对QP问题没有找到可行的解决方案,则搜索方向为主要的SQP程序
被认为是最小化的γ.
直线搜索和优点函数。 QP子问题的解决方案产生一个向量DK,用于形成一个新的迭代
(29)
步长参数αK是为了在a价值函数。韩寒使用的价值函数[22] 和鲍威尔[33] 在此实现中使用下列形式。
(30)
鲍威尔建议设置惩罚参数
(31)
这允许QP解决方案中不活跃但最近活跃的约束作出积极贡献。在这个实现中,惩罚参数R我初始设置为
(32)
在哪里
表示欧几里得范数。
GYDF4y2Ba这确保了较小梯度的约束对惩罚参数的贡献更大,这将是解决方案点上的主动约束的情况。
fmincon SQP算法
GYDF4y2Ba这个sqp 算法(几乎相同sqp-legacy 算法)类似于有效集 算法(有关说明,请参阅fmincon活动集算法 ).的基本sqp 算法在Nocedal和Wright的第18章中进行了描述[31] .
GYDF4y2Ba这个sqp 算法本质上和sqp-legacy 算法,但有不同的实现。通常情况下,sqp 执行时间更快,内存使用量比sqp-legacy .
GYDF4y2Ba最重要的区别是sqp 和有效集 算法是:
关于界的严格可行性
这个sqp 算法的每一步迭代都在有边界约束的区域内进行。此外,有限差分步也是有界的。界限不严格;一步可以恰好在一个边界上。当你的目标函数或非线性约束函数是未定义的或在受边界约束的区域之外是复杂的时,这种严格的可行性是有益的。
非双结果的稳健性
在它的迭代过程中sqp 算法可以尝试采取失败的步骤。这意味着您提供的目标函数或非线性约束函数返回值为正 ,楠 ,或复数。在这种情况下,算法会尝试进行更小的步长。
重构线性代数例程
这个sqp 算法使用一组不同的线性代数例程来解决二次规划子问题,方程14 。这些例程在内存使用和速度方面都比有效集 例程。
重新制定的可行性程序
这个sqp 算法中有两种新的求解方法方程14 当约束不满足时。
这个sqp 该算法将目标函数和约束函数结合成一个价值函数。该算法试图最小化约束条件下的价值函数。这个修改过的问题可以引出一个可行的解决方案。然而,这种方法比原来的问题有更多的变量,所以问题的规模方程14 增加。增大的规模会减缓子问题的求解速度。这些例程是基于Spellucci的文章[60] 和语气[61] .这个sqp 算法为价值函数设置惩罚参数方程30 根据在[41] .
假设不满足非线性约束,并且尝试的步骤导致约束违背增长。这个sqp 该算法尝试使用约束的二阶近似来获得可行性。二阶技术可以得到一个可行的解决方案。然而,这种技术需要对非线性约束函数进行更多的计算,从而会减慢求解速度。
fmincon内点算法
屏障功能
约束极小化的内点方法是求解一系列近似极小化问题。最初的问题是
(33)
为每一个μ>0,近似问题是
(34)
有很多松弛变量s我因为存在不平等约束G.这个s我限制为正,以使迭代保持在可行域内。作为μ减小到零,最小值Fμ应该接近最小值F.加上的对数项称为a屏障功能。此方法如中所述[40] ,[41] ,[51] .GYDF4y2Ba近似的问题方程34 是一系列等式约束问题。这些问题比原来的不等式约束问题更容易解决方程33 .
GYDF4y2Ba为了解决近似问题,该算法在每次迭代中使用两种主要步骤中的一种:
默认情况下,算法首先尝试采取直接步骤。如果不能,则尝试CG步骤。不采取直接步骤的一种情况是,近似问题在当前迭代附近不是局部凸的。
GYDF4y2Ba在每次迭代时,算法减少a优值函数例如
(35)
的参数
可以随着迭代次数的增加而增加,以迫使解朝着可行的方向发展。如果一个尝试的步骤没有降低价值函数,算法拒绝尝试的步骤,并尝试新的步骤。GYDF4y2Ba如果目标函数或非线性约束函数返回一个复值NaN, Inf或在迭代时返回一个错误xJ,算法拒绝xJ.拒绝具有同样的效果,如果价值函数没有充分减少:算法然后尝试一个不同的,更短的步骤。包装任何可能出错的代码试一试 -抓 :
function val = userFcn(x) try val =…%代码可以错误捕获val = NaN;结束
目标和约束必须产生适当的(双 )的值。
直接一步
下面的变量用于定义直接步骤:
H表示的拉格朗日的HessianFμ
:
(36)
JG表示约束函数的雅可比矩阵G.
JH表示约束函数的雅可比矩阵H.
s=诊断接头(s)
.
λ为约束相关的拉格朗日乘子向量G
Λ=诊断接头(λ)
.
Y为所关联的拉格朗日乘子向量H.
E表示与的大小相同的向量G.
定义直接步骤(Δx,Δs) :
(37)
这个方程直接来自于试图求解方程2 和方程3 使用线性化的拉格朗日。
GYDF4y2Ba通过对第二个变量进行预乘,可以对方程进行对称化Δ年代通过s1.:
(38)
为了解这个方程(Δx,Δs) ,算法对矩阵进行LDL分解。(见例3 - D的结构 在MATLAB®低密度脂蛋白函数引用页面。)这是计算上最昂贵的步骤。这种因式分解的结果之一是决定投影的黑森是否为正定;如果不是,算法使用共轭梯度步长,如共轭梯度步 .
更新障碍参数
有一个近似的问题方程34 解决原来的问题,势垒参数μ应该随着迭代的进行而减少到0。该算法有两个屏障参数更新选项,您可以使用BarrierParamUpdate 选择:“单调” (默认),预估的 .
GYDF4y2Ba这个“单调” 选项减少参数μ只要在前面的迭代中,近似问题得到了足够精确的解决,就按1/100或1/5的倍数计算。当算法只需要一次或两次迭代就可以达到足够的精度时,选择1/100,否则选择1/5。准确性的衡量是下面的测试,即所有的右边的项的大小方程38 还不到μ:
请注意
fmincon覆盖你的BarrierParamUpdate 选择“单调” 当下列任一情况发生时:
该问题没有不等式约束,包括边界约束。
这个SubproblemAlgorithm 选择是“重心” .
本节的其余部分将讨论预估的 更新屏障参数的算法μ.其机理类似于线性规划预估 算法。
GYDF4y2Ba通过调整牛顿步长中的线性化误差,预测-校正步长可以加速现有的Fiacco-McCormack(单调)方法。预测器-校正器模式的效果有两方面:它(经常)改进步进方向,同时使用中心参数σ自适应更新屏障参数,以鼓励迭代沿着“中心路径”。参见Nocedal和Wright关于线性规划的预测-校正步骤的讨论,以了解为什么中心路径允许更大的步长,从而加快收敛速度。
GYDF4y2Ba预测步长采用线性化的步长μ= 0,表示没有barrier函数:
定义ɑs和ɑλ为不违反非负性约束的最大步长。
现在从预测器步骤计算互补性。
(39)
在哪里M为约束的数量。
GYDF4y2Ba第一校正器步长为牛顿寻根线性化中忽略的二次项进行调整
为了纠正二次误差,求解了校正器步进方向的线性系统。
第二校正步骤是定心步骤。定心校正是基于变量的σ在等式的右边
在这里,σ被定义为
在哪里μP定义在方程中方程39 ,
.
GYDF4y2Ba为了防止势垒参数下降过快,潜在地破坏算法的稳定性,算法保留了定心参数σ1./1.00以上。这就产生了势垒参数μ减少不超过1/100的系数。
GYDF4y2Ba在算法上,第一次校正和定心步骤是相互独立的,所以它们是一起计算的。此外,预测器和两个校正器步骤的矩阵在左边是相同的。在算法上,矩阵被分解一次,这个分解被用于所有这些步骤。
GYDF4y2Ba该算法由于步长增大了价值函数的值而拒绝了所提出的预测-校正步长方程35 或者计算出的惯性是不正确的(问题看起来是非凸的)。在这些情况下,算法尝试采取不同的步骤或共轭梯度步骤。
共轭梯度步
用共轭梯度法求解近似问题方程34 与其他共轭梯度计算相似。在这种情况下,算法对两者都进行调整x和s,把裤子留着s积极的。该方法是在受线性化约束的情况下,最小化信赖域内近似问题的二次逼近。
GYDF4y2Ba具体地说,让R表示信任区域的半径,并让其他变量定义为直接一步 .该算法通过近似求解KKT方程得到拉格朗日乘子
在最小二乘的意义上,服从于λ是积极的。然后再走一步(Δx,Δs) 约解决
(40)
受线性化约束
(41)
来解决方程41 ,算法试图最小化半径为的区域内线性化约束的范数R.然后方程40 是在约束条件匹配的情况下求解的吗方程41 ,呆在半径的信任区域内R,保持s严格正的。具体算法和推导请参见[40] ,[41] ,[51] .关于共轭梯度的另一种描述,请参阅预条件共轭梯度法 .
内点算法的选择
下面是内部点算法中几个选项的含义和效果。
HonorBounds-当设置为真正的 ,每个迭代都满足您设置的约束。当设置为假 时,算法在中间迭代过程中可能会违反界。
HessianApproximation—当设置为:
“蓄热”,fmincon 用稠密的拟牛顿近似计算Hessian。
“lbfgs”,fmincon 通过有限内存的大规模准牛顿近似计算Hessian。
“fin-diff-grads”,fmincon 通过梯度的有限差分计算hessian -time -vector乘积;其他选项需要适当设置。
HessianFcn—fmincon 使用中指定的函数句柄HessianFcn 来计算Hessian。看到包括麻布 .
HessianMultiplyFcn-给出一个单独的hessian时间向量计算函数。有关详细信息,请参见包括麻布 和黑森乘法函数 .
SubproblemAlgorithm-确定是否尝试直接牛顿步。默认设置为“分解” 允许尝试此类型的步骤。设置“重心” 只允许共轭梯度步骤。
有关选项的完整列表,请参见内点算法 在fmincon 选项
.
fminbnd算法
fminbnd 是一个求解器,可在任何MATLAB安装。它求解一维有界区间内的局部最小值。它不是基于衍生品。相反,它使用黄金分割搜索和抛物线插值。
问题的表述和算法
fseminf问题公式化
费塞米夫用附加类型的约束来解决优化问题fmincon .的制定fmincon 是
这样C(x)≤0,ceq(x) = 0,·x≤B,Aeq·x=说真的,L≤x≤U.
费塞米夫 将下列半无限约束加到已经给出的约束上。为WJ在一或二维有界区间或矩形中我J,对于连续函数的向量K(x,W) ,约束条件为
KJ(x,WJ)≤0WJ∈我J.
术语“维数”费塞米夫 问题是指约束集的最大维数我:1.如果全部我J是否为间隔,如果至少为1则为2我J是一个长方形。向量的大小K不涉及维度的概念。
GYDF4y2Ba之所以称之为半无限规划,是因为变量的数量是有限的(x和WJ),而是无限的约束。这是因为x是在一组连续的区间或矩形上吗我J,其中包含无限多的点,因此存在无限多的约束:KJ(x,WJ)≤0 对于无穷多个点WJ.
GYDF4y2Ba你可能会认为一个有无限个约束条件的问题是不可能解决的。费塞米夫 解决这个问题的方法是将问题重新表述成一个等价的问题,这个问题有两个阶段:最大和最小。半无限约束被重新表述为
(42)
在|K|是向量的分量数K;即半无限约束函数的个数。固定x,这是一个普通的在有界区间或矩形上的最大值。
费塞米夫 通过分段二次或三次逼近进一步简化问题κJ(x,WJ) 的功能KJ(x,WJ) ,对于每一个x解算者访问的地方。费塞米夫 只考虑插值函数的最大值κJ(x,WJ) ,而不是KJ(x,WJ) ,在方程42 .这将原始问题,即最小化半无限约束函数,简化为具有有限个数约束的问题。
采样点。 半无限约束函数必须提供一组采样点,用于进行二次或三次逼近。为了做到这一点,它应该包括:
最初的间距s 采样点之间W
一种生成抽样点集的方法W从s
最初的间距s 是一个|K|2.矩阵。这个JTH排s 表示约束函数相邻采样点的间距KJ.如果KJ取决于一维WJ设置年代(j, 2) = 0 .费塞米夫 更新矩阵s 在随后的迭代。
费塞米夫 使用矩阵s 生成采样点W,然后使用它创建近似值κJ(x,WJ) .用来生成W从s 是否应该保持相同的间隔或矩形我J在优化。
创建采样点的示例。 考虑一个有两个半无限约束的问题,K1..和K2...K1..有一维W1..,K2..有二维W2...下面的代码生成一个抽样集W1..=2.至12:
当isnan(s(1,1)) s(1,1) = 0.2时,初始采样间隔为%;(1、2)= 0;end %采样集w1 = 2:s(1,1):12;
费塞米夫指定s 作为楠 当它第一次调用约束函数时。对此进行检查允许您设置初始采样间隔。
GYDF4y2Ba下面的代码生成一个抽样集W2..在一个正方形中,每个分量从1到100,最初第一个分量比第二个分量取样更频繁:
isnan(s(1,1)) s(2,1) = 0.2;s (2, 2) = 0.5;end %采样集w2x = 1:s(2,1):100;w2y = 1: s (2, 2): 100;(天气,王寅)= meshgrid (w2x w2y);
以上代码片段可以简化如下:
%初始采样间隔如果isnan(s(1,1)) s = [0.2 0;0.2 0.5];end %采样集w1 = 2:s(1,1):12;w2x = 1: s (2,1): 100;w2y = 1: s (2, 2): 100;(天气,王寅)= meshgrid (w2x w2y);
fseminf算法
费塞米夫从本质上讲,将半无限规划问题简化为fmincon .费塞米夫 采用以下步骤求解半无限规划问题:
的现值x,费塞米夫 确定所有的WJ,我使插值κJ(x,WJ,我) 为局部最大值。(最大值指的是变化W固定x.)
费塞米夫在解中采用一个迭代步骤fmincon 问题:
这样C(x)≤0,ceq(x) = 0,·x≤B,Aeq·x=说真的,L≤x≤U,在那里C(x的所有极大值增广κJ(x,WJ) 接管所有WJ∈我J等于最大值除以J和我的κJ(x,WJ,我) .
费塞米夫检查在新点是否满足任何停止条件x(停止迭代);如果没有,则继续执行步骤4。
费塞米夫检查半无限约束离散化是否需要更新,并适当更新采样点。这提供了一个更新的近似κJ(x,WJ) .然后继续到第1步。