有约束优化的求解算法 | 彩潭有鲤的札记

type

status

date

slug

summary

投影法

优化问题的通用迭代公式其中，是关于的函数。的取值不受任何特定集合的限制。由于有约束优化问题要求决策变量必须在预先设定的约束集取值因此这种算法无法直接用于求解有约束优化问题。

考虑优化问题：

如果用以上算法解决此约束问题，那么迭代点的可能不满足约束条件。因此，需要对上述算法进行改进，把约束条件考虑进来。一种比较简单的改进方式就是引人投影：

如果在约束集内，则令；否则将其投影到中，并将投影结果作为。

考虑一种特殊的约束集约束集是中的一个“方框”，称为框式约束。对于点，定义则点称为到上的投影，称为投影算子。是中最接近 的点。利用投影算子，可对前面的无约束优化问题求解算法进行改进：

采用这种迭代方式，每步的迭代点都在约束集内。基于此，上述算法称为投影算法。

一般情况，可定义到上的投影

在这种情况下, 也是中“最接近” 的点。该投影算子仅在某些特定类型的约束集下存在明确定义，如闭凸集。对于某些集合 , 无法显式求解。如果能够明确定义投影算子，就可以应用如下所示的投影算法:

在某些情况下，投影存在明确的计算公式。比如，前面已经给出了框式约束下的投影算子。再如，当是一个线性簇时，投影也有明确的公式。通常情况下，即使明确定义了投影 , 计算某个点的投影可能也并不容易，很多时候投影的计算不得不采用数值方法，而利用数值方法求解本身可能就是一个数值优化问题。实际上，的计算可能与求解原优化问题一样困难。比如，考虑如下优化问题: minimize subject to 很明显，这一问题的解可写为。如果 , 则计算投影与求解这一优化问题是等价的。

梯度法中使用的投影法

已知向量是函数在处的最快下降方向。其迭代公式为，为步长。在最速下降法中，步长为。

将投影算子引入梯度法，可得如下迭代公式称为投影梯度法。

求解含线性约束优化问题的投影梯度法

形如

的优化问题，其中。

约束集合，约束集这种特定结构决定了可以利用正交投影算子

投影可定义为如下正交投影算子矩阵：

正交投影算子有两个重要性质：

设 , 那么当且仅当时, ，即。此外，当且仅当，有，即。

在无约束优化问题中，点是局部极小点的一阶必要条件是。在仅含等式约束的优化问题中，拉格朗日条件起到一阶必要条件的作用。当约束集为的形式时，拉格朗日条件可以写成

为可行点，当且仅当满足拉格朗日条件时，。

在迭代点处，投影梯度算法的迭代公式为

在有约束优化问题中，向量不一定是一个可行方向。可行方向集是矩阵的零空间，应先将向量投影到上。投影等价于左乘矩阵，可按上述公式更新。

在投影梯度算法中，如果是可行的，则每个都是可行的，即对于任意，恒有

投影梯度法沿着方向更新，是函数在所定义的表面上，在处的最速下降方向。

投影最速下降法是投影梯度算法的一种，其步长为

设是投影最速下降法产生的序列，如果，则。

如果对于某个k，有，说明点满足拉格朗日条件，可作为算法的停止准则。

当且仅当时，点是凸函数在约束集上的全局极小点。

拉格朗日法

基于拉格朗日函数的求解方法的基本思路是利用梯度法在更新决策变量的同时更新拉格朗日乘子向量。

仅含等式约束优化问题的拉格朗日法

仅含等式约束的优化问题其中，。

拉格朗日函数为

拉格朗日法更新方程

含不等式约束优化问题的拉格朗日法

含不等式约束的优化的优化问题其中，。

拉格朗日函数为

拉格朗日法更新方程其中，，针对每个元素进行操作

罚函数法

一般形式的有约束优化问题

将有约束优化问题近似处理为如下的无约束优化问题其中，是大于零的常数，是给定函数。

求解无约束优化问题，把得到的解近似作为原问题的极小点。常数称为惩罚因子，函数称为罚函数。

对于一般形式的有约束优化问题，如果满足下列3个条件，则称函数为罚函数。

函数是连续的

对所有，成立

，当且仅当是可行点（即）

罚函数的作用在于对可行集之外的点进行“惩罚”。

选择罚函数

有约束优化问题其中，

利用约束函数来构造罚函数，构造方式为其中，称为绝对值罚函数，其等于，是对所有无法满足的约束条件进行求和。

库朗-贝尔特拉米罚函数能够确保可微

惩罚因子越大，违反约束点受罚越重，近似解就与真正解越接近。当惩罚因子时，罚函数法得到的就是有约束问题的真正解。

分析一般意义下的罚函数法

在分析之前，先引人一些符号和记法。用表示优化问题的一个解(全局极小点)。为此问题的罚函数。对，令是一个给定的正数。

定义伴随函数 : 对于每个都可构造一个伴随的无约束优化问题：用表示的极小点。

假设是一个非减序列，即对于任意，有，那么, 对于任意下列不等式成立：

目标函数连续，当时，。那么，序列的任意收敛子序列的极限是约束优化问题的一个解。

如果进行无限多次极小化计算，随着惩罚因子，那么能保证任何收敛子序列的极限都是有约束优化问题的极小点。显然，这一定理在实际应用中是受限的。实际上，利用罚函数法求解无约束优化问题的最优解时, 期望只通过一次极小化计算便可求得最优解，进而得到原问题的最优解。换可话说，在为一个给定常数的情况下，通过求解伴随的无约束优化问题[最小化 ]，获得原问题的精确解。可以证明，这的确是可以做到的，这种情况下的罚函数称为精确的罚函数。但是，精确的罚函数要求是不可微的。