网站开发技术创业计划,做购物微信网站,家庭网络建站,石油工程建设协会网站文章目录约束优化#xff1a;约束优化的三种序列无约束优化方法外点罚函数法L2-罚函数法#xff1a;非精确算法对于等式约束对于不等式约束L1-罚函数法#xff1a;精确算法内点罚函数法#xff1a;障碍函数法等式约束优化问题的拉格朗日函数法#xff1a;Uzawas Method fo…
文章目录约束优化约束优化的三种序列无约束优化方法外点罚函数法L2-罚函数法非精确算法对于等式约束对于不等式约束L1-罚函数法精确算法内点罚函数法障碍函数法等式约束优化问题的拉格朗日函数法Uzawas Method for convex optimization参考文献约束优化约束优化的三种序列无约束优化方法
罚函数法是指将约束作为惩罚项加到目标函数中从而转化成熟悉的无约束优化问题。
外点罚函数法
简而言之外点罚函数法是指对于可行域外的点惩罚项为正即对该点进行惩罚对于可行域内的点惩罚项为0即不做任何惩罚。因此该算法在迭代过程中点列一般处于可行域之外惩罚项会促使无约束优化问题的解落在可行域内。罚函数一般由约束部分乘正系数组成通过增大该系数我们可以更严厉地惩罚违反约束的行为从而迫使惩罚函数的最小值更接近约束问题的可行区域。
L2-罚函数法非精确算法
对于等式约束 对于不等式约束 对于一般优化问题则是将上述不等式约束和等式约束的惩罚项加到一起。 什么情况下使用L2-罚函数法 实际优化问题中等式与不等式约束具有物理意义约束违背量不要求特别小在1e-2~1e-3之间可接受就行。例如某优化问题中速度约束v≤10v \leq 10v≤10解v10.01v10.01v10.01也可以接受。
使用该方法时可采用如下两种方式
一步到位即取σ\sigmaσ足够大直接解无约束罚函数P最优化问题此时P最优解是个近似解与实际最优解之间的误差在可接受范围内序列迭代优化例如
σ1⟹P(x,1)\sigma1 \implies P(x,1)σ1⟹P(x,1)解x1∗x1x^{*}_{1}x_1x1∗x1;
σ10⟹P(x,10)\sigma10 \implies P(x,10)σ10⟹P(x,10)上一次迭代x1x_1x1作初值解x2∗x2x^{*}_{2}x_2x2∗x2;
σ100⟹P(x,100)\sigma100 \implies P(x,100)σ100⟹P(x,100)上一次迭代x2x_2x2作初值解x3∗x3x^{*}_{3}x_3x3∗x3;
……直到达到收敛准则。算法伪代码如下 一般情况下具体选择何种方式取决于实际工程问题的精度需求和速度需求。 L2-罚函数法的优缺点 优点
将约束优化问题转化为无约束优化问题当ci(x)c_i(x)ci(x)光滑时可以调用一般的无约束光滑优化问题算法求解;二次罚函数形式简洁直观而在实际中广泛使用。
缺点
需要σ→∞\sigma \rightarrow \inftyσ→∞此时海瑟矩阵条件数过大对于无约束优化问题的数值方法拟牛顿法与共轭梯度法存在数值困难且需要多次迭代求解子问题对于存在不等式约束的P(x,σ)P(x,\sigma)P(x,σ)可能不存在二次可微性质光滑性降低不精确与原问题最优解存在距离。
例子 L1-罚函数法精确算法
由于L2-罚函数法存在数值困难并且与原问题的解存在误差因此考虑精确罚函数法。精确罚函数是一种问题求解时不需要令罚因子趋于正无穷或零的罚函数。换句话说若罚因子选取适当对罚函数进行极小化得到的解恰好就是原问题的精确解。这个性质在设计算法时非常有用使用精确罚函数的算法通常会有比较好的性质。
由于L1-罚函数非光滑因此无约束优化问题P的收敛速度无法保证这实际上就相当于用牺牲收敛速度的方式来换取优化问题P的精确最优解。 内点罚函数法障碍函数法
前面介绍的L1和L2罚函数均属于外点罚函数即在求解过程中允许自变量xxx位于原问题可行域之外当罚因子趋于无穷时子问题最优解序列从可行域外部逼近最优解。自然地如果我们想要使得子问题最优解序列从可行域内部逼近最优解则需要构造内点罚函数。顾名思义内点罚函数在迭代时始终要求自变量xxx不能违反约束因此它主要用于不等式约束优化问题。
如下图所示考虑含不等式约束的优化问题为了使迭代点始终在可行域内当迭代点趋于可行域边界时我们需要罚函数趋于正无穷。常见的罚函数有三种对数罚函数逆罚函数和指数罚函数。对于原问题它的最优解通常位于可行域边界即ci(x)≤0c_i(x) \leq 0ci(x)≤0中至少有一个取到等号此时需要调整惩罚因子σ\sigmaσ使其趋于0这会减弱障碍罚函数在边界附近的惩罚效果。 算法伪代码如下 同样地内点罚函数法也会有类似外点罚函数法的数值困难即当σ\sigmaσ趋于0时子问题P(x,σ)P(x,\sigma)P(x,σ)的海瑟矩阵条件数会趋于无穷因此对子问题的求解将会越来越困难。 等式约束优化问题的拉格朗日函数法Uzawa’s Method for convex optimization
基础预备
凸优化学习笔记一
凸优化学习笔记Lagrange函数、对偶函数、对偶问题、KKT条件
多元函数的极值和鞍点
**若原问题是凸问题则KKT条件是充要条件。**原问题连续凸则拉格朗日函数严格凸原问题的最优值p∗p^*p∗与对偶问题的最优值d∗d^*d∗相等(x∗,λ∗)(x^*,\lambda ^*)(x∗,λ∗)是拉格朗日函数的鞍点同时也是原问题和对偶问题的最优解。 综上分析Uzawa’s Method迭代过程分为两个步骤 {xk1argminxL(x,λk)λk1λkα(Axk1−b)\left\{\begin{array}{l} x^{k1}\underset{x}{\operatorname{argmin}} \mathcal{L}\left(x, \lambda^k\right) \\ \lambda^{k1}\lambda^k\alpha\left(A x^{k1}-b\right) \end{array}\right. {xk1xargminL(x,λk)λk1λkα(Axk1−b) 1给定λk\lambda^kλk求解minxL(x,λk)\min _x \mathcal{L}(x, \lambda^k)minxL(x,λk)无约束优化问题求解得到xk1x^{k1}xk1
2更新λ\lambdaλL(xk1,λ)L(x^{k1},\lambda)L(xk1,λ)关于λ\lambdaλ的梯度为∂L∂λ∣x1Axk1−b\left.\frac{\partial L}{\partial \lambda}\right|_{x1}A x^{k1}-b∂λ∂Lx1Axk1−b若要求解maxλL(xk1,λ)\max _\lambda \mathcal{L}(x^{k1}, \lambda)maxλL(xk1,λ)则沿着梯度上升方向进入步长迭代即λk1λkα(Axk1−b)\lambda^{k1}\lambda^k\alpha\left(A x^{k1}-b\right)λk1λkα(Axk1−b)α\alphaα为迭代步长。
该方法的前提就是原函数连续凸L(x,λ)\mathcal L(x,\lambda)L(x,λ)关于xxx严格凸则minxL(x,λk)\min _x \mathcal{L}(x, \lambda^k)minxL(x,λk)只存在一个最优解可求出唯一xk1x^{k1}xk1进而更新λk1\lambda^{k1}λk1否则xk1x^{k1}xk1会存在多个不知道选择哪个去更新λ\lambdaλ。因此缺点很明显该方法要求原函数必须为连续凸函数梯度上升步长需要调整且收敛速率不能保证。 参考文献
机器人中的数值优化
最优化建模、算法与理论/最优化计算方法
