约束优化方法.ppt

1、第六章第六章 约束优化方法约束优化方法约束优化方法概述约束优化方法概述随机方向法随机方向法复合形法复合形法可行方向法可行方向法惩罚函数法惩罚函数法6.1 约束优化方法概述约束优化方法概述无约束优化方法是优化方法中最基本最核心的部分。在工程实际中，优化问题大都属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。约束 优化设计的数序模型为：优化设计的数序模型为：根据求解方式的不同，根据求解方式的不同， 约束优化方法可以分为：约束优化方法可以分为：直接解法和间接解法直接解法和间接解法1、直接法只能求解不等式约束优化问题的最优解。其根本做法是在约

2、束条件所限制的可行域内直接求解目标函数的最优解。如：约束坐标轮换法、复合形法等。其基本要点：选取初始点 x0 、确定可行搜索方向 d及适当步长 。每次迭代计算均按以下基本迭代格式进行xk+1 = xk + kdk (k = 1, 2, )可行搜索方向：当设计点沿该方向作微量移动时， 目标函数值下降， 且不越出可行域。特点：1）求解在可行域内进行， 当前设计点总比初始设计点好；2）若目标函数为凸函数， 可行域为凸集， 可保证获得全域最优解；3）要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点， 且目标函数有定义。2、间接法、间接法该方法可以求解等式约束优化问题和一般约束优化问题

3、。其基本思想是将该方法可以求解等式约束优化问题和一般约束优化问题。其基本思想是将约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进行求解。如：惩罚函数法题，再采用无约束优化方法进行求解。如：惩罚函数法基本迭代过程，基本迭代过程， 将约束优化问题转化成新的无约束目标函数将约束优化问题转化成新的无约束目标函数式中式中为转化后的目标函数为转化后的目标函数分别为约束函数分别为约束函数gj(x), hk(x)经过加权处理后构成的某种形经过加权处理后构成的某种形式的复合函数或泛函数式的复合函数或

4、泛函数 1， 2为加权因子为加权因子 。例例 6.1 求约束优化问题求约束优化问题 minf(x) = (x12)2 + (x2 1)2 s.t. h(x) = x1 + 2x2 2 = 0 的最优解。的最优解。解：解： 该问题的最优解为该问题的最优解为 x* = 1.6 0.2T, f(x*) = 0.8。 由图由图 6-3a可知，可知， 约束最约束最优点优点 x*为目标函数等值线与等式约束函数（直线）的交点。为目标函数等值线与等式约束函数（直线）的交点。用间接法求解时，用间接法求解时， 可取可取 1 = 0.8，转换后的新目标函数为，转换后的新目标函数为(x, 2) = (x12)2 +

5、(x2 1)2 + 0.8(x1 + 2x2 2 )可以用解析法求可以用解析法求 min(x, 2) , 令 = 0，得到/x1 = 2 (x12) +0.8 = 0/x2 = 2 (x12) +1.6 = 0求得的无约束最优解为求得的无约束最优解为 x* = 1.6 0.2T, (x*， 2) = 0.8。其结果与原约束最。其结果与原约束最优解相同。优解相同。特点特点 ：1） 由于无约束优化方法的日趋成熟，由于无约束优化方法的日趋成熟， 使得间接解法有了可使得间接解法有了可靠的基础；靠的基础；2） 可以有效地处理具有等式约束的约束优化问题；可以有效地处理具有等式约束的约束优化问题；3）存在的

6、主要问题，）存在的主要问题， 选取加权因子较为困难。选取加权因子较为困难。 加权因子选加权因子选取不当，取不当， 会影响收敛速度和计算精度，甚至会导致计算失败会影响收敛速度和计算精度，甚至会导致计算失败。6.2 随机方向法本方法是在可行域内利用随机产生的可行方向进行搜索的一种直接解法，用于求解这类约束优化设计问题。在可行域内选择一个初始点 x0， 利用随机数的概率特性， 产生若干个随机方向，并从中找出一个能使目标函数值下降最快的随机方向作为可行搜索方向， 记作 d1。从初始点 x0出发， 沿方向 d1按给定的初始步长 取试探点 x = x0 + d1检查 x点的适用性和可行性，即检查f(x)

7、f(x0), x D?若满足， 则以 x为新的起点， 即 x0 x。 继续按上面的迭代式在 d1方向上获取新点。 重复上述步骤，迭代点可沿 d1方向前进， 直至到达某迭代点不能同时满足适用性和可行性条件时为止，退到前一点作为改方向搜索中的最终成功点， 记作 x1.将 x1作为新的始点 x0 x1，再产生另一随机方向 d2, 以步长 0重复以上过程， 直到沿 d2方向得到最终成功点 x3。如此循环， 点列 x1、 x2、 必将逼近约束极值点 x*。一、一、 随机数的产生随机数的产生首先令首先令 r1 = 235, r2 = 236, r3 = 237, 取取 r = 2657863 (r为小于为

8、小于 r1的正奇数），的正奇数）， 然后按一下步骤计算然后按一下步骤计算令令 r5r若若 r r3, 则则 rr r3若若 r r2, 则则 rrr2 若若 r r1, 则则 rrr1则则 q = r/r1q即为即为 (0, 1)区间内的伪随机数。利用区间内的伪随机数。利用 q, 容易求得任意区间容易求得任意区间 (a, b)内的伪随机内的伪随机数，数， 其计算公式为其计算公式为x = a + q(ba) （ 6-5）（ 6-4）这部分内容为产生伪随机数的数学模型，可写成子程序。或者大家可以直接利用算法语言中自带的产生随机数的子程序。二、初始点的选择随机方向法的初始点 x0必须是一个可行点，满

9、足全部不等式约束条件。当约束条件较为复杂，用人工不易选择可行初始点时，可用计算机随机选择的方法来产生。其计算步骤如下：1）输入设计变量的下限值和上限值，即 ai xi bi (i = 1, 2, ,n)2）在区间（ 0， 1）内产生 n个伪随机数 qi (i = 1, 2, , n)3）计算随机点 x的分量 xi = ai + qi (bi ai) (i = 1, 2, , n)4) 判别随机点 x是否可行，若可行取 x0 x; 否则转步骤 2）重新计算。（ 6-6）三、可行搜索方向的产生三、可行搜索方向的产生从从 k (k n) 个随机方向中，选取一个较好的方向。计算步骤为：个随机方向中，选

10、取一个较好的方向。计算步骤为：1）在（）在（ -1， 1）区间内产生伪随机数）区间内产生伪随机数 rij ( i =1, 2, , n; j = 1, 2, , k), rij = 2qi - 1计算随机单位向量计算随机单位向量 ej2) 取一试验步长取一试验步长 0，按下式计算，按下式计算 k个随机点个随机点3）检验）检验 k个随机点个随机点 xj (j = 1, 2, , k)是否为可行点，除去非可行点，是否为可行点，除去非可行点， 计算余计算余下的可行随机点的目标函数值，下的可行随机点的目标函数值， 比较其大小，比较其大小， 选出目标函数值最小的点选出目标函数值最小的点 xL.4) 比较比较 xL和和 x0 两点的目标函数值，两点的目标函数值， 若若 f(xL) f(x0), 取取 xL和和 x0 的连线方向作的连线方向作为可行搜索方向；为可行搜索方向； 若若 f(xL) f(x0), 则将步长则将步长 0缩小，缩小， 转步骤转步骤 1重新计算，重新计算， 直直至至 f(xL) f(x0)为止。为止。 如果如果 0缩小到很小（例如缩小到很小（例如 106），仍然找不到一个），仍然找不到一个 xL, 使使 f(xL) f(x0), 则说明则说明 x0是一个局部极小点，是一个局部极小点， 此时可更换初始点，此时可更换初始点， 转步骤转步骤 1.（ 6-8）（ 6-7）