约束优化

传统方法的实现如牛顿法、梯度法等，其基本思想就是将动态的转化为静态的，将多目标转化为单目标，由点及面的搜索思想。

传统方法存在如下问题：

(1) 传统的基于梯度的优化方法(如可行方向法、约束变尺度法)对约束条件的处理往往是先寻找一个可行且下降的方向，然后沿此方向进行线性搜索，并重复上述步骤以得到问题的最优解，然而该最优解往往是局部最优的。

(2) 对于许多实际的约束优化问题，一方面，由于目标函数往往形式复杂，不仅问题的维数比较高，而且优化曲面中存在多个极小点，这使得传统的基于梯度的算法难以奏效。另一方面，实际问题中目标函数往往是不连续或不可微，有些问题目标函数甚至没有解析表达式，传统算法难以解决这类问题。

(3) 由于约束的存在，使得决策变量的可行搜索空间不规则(如非凸，不连通等)，从而增加了搜索到最优解的难度，有时甚至很难找到可行解。

简介

进化算法是一种智能的全局优化方法，它对函数本身性质要求非常低，往往只要求目标函数值是可以计算的，不要求它具有连续性、可微性及其它解析性质，同时它又是基于群体进化的算法，因此可采用进化算法解决约束优化问题。用进化算法解决约束优化问题的关键在于如何进行有效的约束处理，即如何有效均衡在可行区域与不可行区域的搜索。

常见的用于求解约束优化问题的进化算法有罚函数法、遗传算法、进化策略、进化规划、蚁群算法和粒子群算法等。

与传统方法相比的优势

(1) 在一般情况下，进化算法能否收敛到全局最优解与初始群体无关，而传统优化方法则依赖于初始解；

(2) 进化算法具有全局搜索能力，而很多传统优化方法往往会陷入局部最优；

(3) 进化算法的适用范围广，能有效地解决不同类型的问题，而传统优化方法在设计时往往就只能解诀某一类型的问题。

存在的不足

(1) 进化算法中的参数，如群体规模、进化代数、重组概率、变异概率等，往往需要根据经验设定，且在一定程度上与问题相关；

(2) 进化算法的收敛问题，进化算法求解实际问题时的收敛性判定缺乏理论指导。 2100433B

不失一般性，约束优化问题可以描述为如下形式：

其中 x 是决策变量，f( x )是目标函数，

若对某一

当f(x)为线性函数时称为线性规划问题，反之如果是非线性则为非线性规划问题。当约束问题包含一个目标函数时，称为单目标约束优化问题；当约束问题包含多个目标函数时，称为多目标约束优化问题。

约束最优化问题就是求目标函数

约束最优化问题的解法有两种：

约束最优化问题化约束最优化问题为无约束最优化问题

例1 最大面积 设长方形的长、宽之和等于

解: 这就是一个约束最优化问题：设长方形的长为x，宽为y，求目标函数A=xy在条件x y=a之下的最大值。

由于从约束条件x y=a中容易解出y=a-x，代入目标函数

由

从上述例子可以看出化约束最优化问题为无约束最优化问题的思路：从约束条件

但是，这种方法有局限性，因为有时从约束条件

约束最优化问题拉格朗日乘数法

这一方法的思路是：把求约束最优化问题转化为求无约束最优化问题，看它应该满足什么样的条件"para" label-module="para">

设

为了便于记忆，并能容易地写出方程组(1)，我们构造一个函数

于是，我们把用拉格朗日乘数法求解约束最优化问题的步骤归纳如下：

①构造拉格朗日函数

②解方程组

③根据实际问题的性质，在可能极值点处求极值 。2100433B

约束最优化问题(constrained optimization problem)是指具有约束条件的非线性规划问题。极小化问题的一般形式为