[科普中国]-约束极值问题

带有约束条件的极值问题称为约束极值问题，也叫规划问题。若某非线性规划的目标函数为自变量x的二次函数，约束条件又全是线性的，就称这种规划为二次规划。

定义带有约束条件的极值问题称为约束极值问题，也叫规划问题。

若某非线性规划的目标函数为自变量x的二次函数，约束条件又全是线性的，就称这种规划为二次规划。

求解求解约束极值问题要比求解无约束极值问题困难得多。为了简化其优化工作，可采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其他方法。

库恩-塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为最优点的必要条件，但一般它并不是充分条件（对于凸规划，它既是最优点存在的必要条件，同时也是充分条件）。1

罚函数法转化简介利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术(Sequential Uneonstrained Minization Tech—nique，SUMT)。

罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法。外部罚函数法是从非可行解出发逐渐移动到可行区域的方法。内部罚函数法也称为障碍罚函数法，这种方法是在可行域内部进行搜索，约束边界起到类似围墙的作用，如果当前解远离约束边界时，则罚函数值是非常小的，否则罚函数值接近无穷大的方法。

常用函数法由于进化计算中通常采用，因此主要介绍外部罚函数法。

在进化计算中，研究者选择外部罚函数法的原因主要是该方法不需要提供初始可行解。

需要提供初始可行解则是内部罚函数法的主要缺点。由于进化算法应用到实际问题中可能存在搜索可行解就是NP难问题，因此这个缺点是非常致命的。

外部罚函数法一般形式为：B(x)=f(x)+[∑riGi+∑cjHj]

其中B(x)是优化过程中新的目标函数，Gi和Hj分别是约束条件gi(x)和hj(x)的函数，ri和cj是常数，称为罚因子。Gi和Hj最常见的形式是Gi**=max[0, gi(x)]a；Hj=|hj(x)|b，其中a和b一般是1或者2**。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学