约束最优化方法

约束最优化问题的求解要比无约束问题的求解复杂得多, 也困难得多, 因而求解方法也更多种多样, 内容更为丰富. 这里只讨论可行方向方法中的简约梯度法和增广目标函数方法中的惩罚函数法.
一: 约束优化问题的最优性条件
KKT最优化条件是Karush[1939]以及Kuhn和Tucker[1951]先后独立发表出來的. 这组最优化条件在Kuhn和Tucker 发表之后才逐渐受到重视, 因此许多书只记载成「Kuhn-Tucker 最优化条件(Kuhn-Tucker conditions)」. KKT条件处理不等式约束时, 可以把它变换成一组等式约束.
KTT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件. 这是一个广义化拉格朗日乘数的成果. 一般地, 一个最优化数学模型的列标准形式如式(1), 所谓 Karush-Kuhn-Tucker 最优化条件,就是指上式的最优点\({{\bf{x}}^ * }\)必须满足下面的条件:
1). 约束条件满足\({g_i}({{\bf{x}}^ * }) \le 0,i = 1,2,…,p\), 以及\(,{h_j}({{\bf{x}}^ * }) = 0,j = 1,2,…,q\)
2). \(\nabla f({{\bf{x}}^ * }) + \sum\limits_{i = 1}^p {{\mu _i}\nabla {g_i}({{\bf{x}}^ * })} + \sum\limits_{j = 1}^q {{\lambda _j}\nabla {h_j}({{\bf{x}}^ * })} = {\bf{0}}\), 其中\(\nabla \)为梯度算子;
3). \({\lambda _j} \ne 0\)且不等式约束条件满足\({\mu _i} \ge 0,\begin{array}{*{20}{c}}
{}
\end{array}{\mu _i}{g_i}({{\bf{x}}^ * }) = 0,\begin{array}{*{20}{c}}
{}
\end{array}i = 1,2,…,p\)
KKT条件第一项是说最优点\({{\bf{x}}^ * }\)必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解, 这一点自然是毋庸置疑的. 第二项表明在最优点\({{\bf{x}}^ * }\), \(\nabla f\)必须是\(\nabla {g_i}\)和\(\nabla {h_j}\)的线性組合, \({\mu _i}\)和\({\lambda _j}\)都叫作拉格朗日乘子. 所不同的是不等式限制条件有方向性, 所以每一个\({\mu _i}\)都必须大于或等于零, 而等式限制条件没有方向性,所以\({\lambda _j}\)没有符号的限制, 其符号要视等式限制条件的写法而定. \({\mu _i}{g_i}({{\bf{x}}^ * }) = 0,\begin{array}{*{20}{c}}
{}
\end{array}i = 1,2,…,p\)称为互补松紧条件.

二: 简约梯度法
带线性约束的非线性规划问题, \({x^k}\)点的搜索方向不仅要像无约束那样是一个下降方向, 而且还要是一个可行方向. 这类算法总称为可行方向法. 简约梯度法的每一次迭代都通过积极约束消去一部分变量, 从而降低最优化问题的维数, 而且每次迭代都产生一个可行下降方向.
简约梯度法的基本思想是Wolfe在1962年作为线性规划单纯形方法的推广而提出来的. 仿照线性规划中的单纯形方法, 每次迭代的当前点\({x^k}\)处, 将\({x^k}\)的\(m\)个最大正分量确定为基变量, 余下的\(n – m\)个分量作为非基变量, 那么目标函数可作为非基变量的函数求负梯度方向. 并依据这一方向构造从\({x^k}\)到\({x^{k + 1}}\)迭代用到的可行下降搜索方向.
具体的推导过程, 这里略过, 可参见刁在筠著III版P136-P144.

三: 惩罚函数法
惩罚函数法求解约束非线性规划问题的思想是, 利用问题中的约束函数做出适当的带有参数的惩罚函数, 然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数.
惩罚函数法有许多类型, 两种最基本的是: 1, 罚函数法, 也称外部惩罚法; 2, 障碍函数法, 也称内部惩罚法.
1). 罚函数法: 对于约束非线性规划问题,
\(\left\{ {\begin{array}{*{20}{c}}
{\min }\\
{s.t.}\\
{}
\end{array}} \right.\begin{array}{*{20}{c}}
{f(x)}\\
{{g_i}(x) \le 0,}\\
{{h_j}(x) = 0,}
\end{array}\begin{array}{*{20}{c}}
{}\\
{i = 1,…p}\\
{j = 1,…q}
\end{array}\)
利用罚函数法构造的增广目标函数可选择为:
\({F_c}(x) = f(x) + c\sum\limits_{i = 1}^p {{{[\max (g(x),0)]}^2} + \frac{c}{2}\sum\limits_{j = 1}^q {{{[{h_j}(x)]}^2}} } \)
2). 障碍函数法
要注意罚函数法产生的点列是从可行域外部逐步逼近最优解. 当在某一个充分大的\({c_k}\)处终止迭代时, 得到的点一般只能近似满足约束条件. 对于某些实际问题来说, 这样的近似最优解是不能被接受的. 为了使迭代点总是可行点, 可以采用障碍函数法, 或称为内部惩罚法. 它的基本思想是, 在可行区域的边界上筑起一道”墙”来, 当迭代点靠近边界时, 所构造的增广目标函数值陡然增大, 于是最优点就被”挡”在可行区域内部了.
简单起见, 仅考虑带不等式约束的非线性规划问题,
\(\left\{ {\begin{array}{*{20}{c}}
{\min }\\
{s.t.}
\end{array}} \right.\begin{array}{*{20}{c}}
{f(x)}\\
{{g_i}(x) \le 0,}
\end{array}\begin{array}{*{20}{c}}
{}\\
{i = 1,…p}
\end{array}\)
当点\(x\)从可行域内部趋于可行域边界时, 至少有一个\({g_i}(x)\)趋于零. 这时构造函数
\(B(x) = – \sum\limits_{i = 1}^p {\frac{1}{{{g_i}(x)}}} \)或\(B(x) = – \sum\limits_{i = 1}^p {\ln [ - {g_i}(x)]} \)
就会无限增大. 于是, 若在原目标函数上加上类似于上面构造的函数, 就会使极小点落在可行域内部. 然而我们最终目的是逐步逼近极小点, 而极小点通常位于可行域的边界上, 因此需要在迭代的过程中逐步减弱\(B(x)\)的影响. 这时需要在添加一项递减且趋于零的正罚参数数列\(\{ {d_k}\} \), 即
\({B_{{d_k}}}(x) = – {d_k}\sum\limits_{i = 1}^p {\frac{1}{{{g_i}(x)}}} \)或\({B_{{d_k}}}(x) = – {d_k}\sum\limits_{i = 1}^p {\ln [ - {g_i}(x)]} \)
障碍函数法构造的增广矩阵为: \({F_{{d_k}}}(x) = f(x) + {B_{{d_k}}}(x)\).

罚函数法适用于一般的带约束非线性规划问题, 上面介绍的障碍函数法仅适用于带不等式约束的非线性规划问题. 有时还把两种方法结合起来使用, 它们都是将一个带约束的优化问题转化为一系列无约束优化问题的方法. 罚函数法的优点是方法结构简单, 对初始点的选取比较自由; 障碍函数法同样有结构简单的优点, 但初始点必须是可行内点.
这两种方法的缺点是: 1. 收敛速度慢; 2. 工作量大; 3. 方法本身造成了数值困难性.

[参考] 1. <运筹学>.刁在筠著
附录: 关于最优性条件的一份较为深入浅出的文稿(出自 复旦大学 冯曲老师)

约束最优化方法》上有 1 条评论

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>