约束优化问题的求解方法一、搜索法二、复合形法三、罚函数方法四、序列二次规划1/20
1/20 一、搜索法 二、复合形法 三、罚函数方法 四、序列二次规划 约束优化问题的求解方法
一、约束优化方法概述无约束优化方法是优化方法中最基本最核心的部分。但是。在工程实际中，优化问题大都是属于有约束的优化问题，即其设计变量的取值要受到一定的限制。用于求解约束优化问题最优解的方法称为约束优化方法。1、约束优化问题min f(x)h,(x)= 0, j=1,2..",Js.tg;(x)≤0, i=1,2...,Ih,(x) = 0, j=1,2..",J约束集、约束域或可行域X =(xg;(x)≤0, i=1,2..., I2
2 一、约束优化方法概述 无约束优化方法是优化方法中最基本最核心 的部分。但是，在工程实际中，优化问题大都是属 于有约束的优化问题，即其设计变量的取值要受到 一定的限制，用于求解约束优化问题最优解的方法 称为约束优化方法。 约束集、约束域或可行域 1、约束优化问题 = = = g x i I h x j J f x i j ( ) 0 1,2 , ( ) 0 1,2 , s.t min ( ) ， ， } ( ) 0 1,2 , ( ) 0 1,2 , { g x i I h x j J X x i j = = = = ，
2、约束优化方法的分类约束优化方法按求解原理的不同回以分为直接法和间接法两类。(1)直接法在约束条件所限制的可行域内直接求解目标函数的复合形最优解。如：随机方向搜索法、坐标轮换法、法等。适应性：只能求解不等式约束优化问题的最优解优化策略：选取初始点、确定搜索方向及步长。构造选代序列 xk+1=x+αkpk满足(1) f(x+α,ph)<f(xh)(2)xk+αkpk EX即每次产生的迭代点必须在可行域中并且当前迭代点的目标函数值较前一点是下降的。3
3 2、约束优化方法的分类 约束优化方法按求解原理的不同可以分为直接法 和间接法两类。 即每次产生的迭代点必须在可行域中并且当前迭代 点的目标函数值较前一点是下降的。 (1)直接法 在约束条件所限制的可行域内直接求解目标函数的 最优解。如：随机方向搜索法、坐标轮换法、复合形 法等。 适应性：只能求解不等式约束优化问题的最优解。 构造迭代序列 满足(1) （2） 优化策略：选取初始点、确定搜索方向及步长。 k k k 1 k x x p + = + ( ) ( ) k k k k f x p f x + x p X k k k +
(2)间接法·基本思想是将约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进行求解·可以求解等式约束优化问题和一般约束优化问题。·如：广义拉格朗日乘子法，罚函数法,序列二次规划法等?
(2)间接法 • 基本思想是将约束优化问题通过一定的方法进 行改变，将约束优化问题转化为无约束优化问 题，再采用无约束优化方法进行求解。 • 可以求解等式约束优化问题和一般约束优化问 题。 • 如：广义拉格朗日乘子法,罚函数法,序列二次 规划法等 4
三、约束随机方向搜索法“瞎子爬山”约束随机方向搜索法类似与在可行域内，任意选择一个初始点，以给定的初始步长沿按某种方法产生的随机方向取得探索，若该点同时满足下降性和可行性要求，表示点探索成功。并以它作为新的起始点，继续按上面的迭代公式在方向上获得新的探索成功点。直至达到某搜索点不能同时满足下降性可行性要求时停正。此时废弃该搜索点并退回到前一个搜索成功点作为该方向搜索中的最终成功点：以上述最终点为起点，再产生另一随机方向，重复以上过程，得到沿方向的最终成功点。经过若干循环，点列必最后逼近约束最优点。5
三、约束随机方向搜索法 • 约束随机方向搜索法类似与“瞎子爬山” 。 • 在可行域内，任意选择一个初始点. • 以给定的初始步长沿按某种方法产生的随机方向取 得探索，若该点同时满足下降性和可行性要求，表 示点探索成功。并以它作为新的起始点，继续按上 面的迭代公式在方向上获得新的探索成功点。直至 达到某搜索点不能同时满足下降性可行性要求时停 止。此时废弃该搜索点并退回到前一个搜索成功点 作为该方向搜索中的最终成功点. 以上述最终点为 起点，再产生另一随机方向，重复以上过程，得到 沿方向的最终成功点。经过若干循环，点列必最后 逼近约束最优点。 5
四、约束坐标轮换法坐标轮换法又称变量轮换法，它是把一个n维无约束最优化问题转化为依次沿相应的n个坐标轴方向的一维最优化问题，并反复进行若干轮循环迭代来求解的直接搜索法。6
四、约束坐标轮换法 坐标轮换法又称变量轮换法，它是把一个 n维无约束最优化问题转化为依次沿相应 的n个坐标轴方向的一维最优化问题，并 反复进行若干轮循环迭代来求解的直接搜 索法。 6
死点：该点已经逼近约束边界基本思路（以二维为例说明）其后的选代点无论沿何方向，都不可能同时满足适用性及可行性X24在可行域任取一点Y°，取一个初始的要求。步长α，按=+ae，取得沿坐标轴第一个送代点，检查该点是否满足：可行性条件：XEDX2xiX3适用性条件：F（X）<F(X°）若两者均满足，步长加倍，送代计+算X,=X"+2αe，只要送代点满X足条件，加倍增大步长，继续送代获得新点：当送代点不满足条件，取前一个送代点，转而沿，坐标轴方法搜索，不满足条件时取负步长进行如图所示，直到逼近最优点*X1?约束坐标轮换法虽然方法简单、算法明确，便于设计，但当维见“死点”，导致出现伪最优点。数较高时收敛速度慢，还会出现为辨别输出最优点的真伪，可以用K-T条件检验。7
7 基本思路（以二维为例说明）： 约束坐标轮换法虽然方法简单、算法明确，便于设计，但当维 数较高时收敛速度慢，还会出现“死点”，导致出现伪最优点。 死点：该点已经逼近约束边界， 其后的迭代点无论沿何方向，都 不可能同时满足适用性及可行性 的要求。 为辨别输出最优点的真伪，可以用K-T条件检验
五、复合形法复合形法是求解约束优化问题的一种重要的直接法1、基本思想：在可行域内构造一个具有个顶点的初始复合形。对复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点，并用此48点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直至逼近最优点
五、复合形法 复合形法是求解约束优化问题的一种重要的直接法. 1、基本思想： 在可行域内构造一个具有k个顶点的初始复合形。对复 合形各顶点的目标函数值进行比较，去掉目标函数值 最大的顶点（称最 坏点），然后按一定法 则求出目标函数值下降 的可行的新点，并用此 点代替最坏点，构成新 的复合形，复合形就向 最优点移动一步，直至 逼近最优点。 8 1 2 3 4 5 6 7 8
2、初始复合形的构成，要构成初始复合形，实际上就是确定个可行点作为复合形的顶点·顶点数目一般在n+1≤k≤2n范围内。·对于维数较低的优化问题，因顶点数目较少，可以由设计者自行凑出可行点作为复合形顶点。但对于维数较高的优化问题，这种方法常常很困难。一般采用构成复合形的随机方法·该方法是先产生K个随机点，然后再把那些非可行随机点调入可行域内，最终使k个随机点都成为可行点而构成初始复合形
2、初始复合形的构成 • 要构成初始复合形，实际上就是确定k个可行点 作为复合形的顶点. • 顶点数目一般在n+1 k 2n范围内。 • 对于维数较低的优化问题，因顶点数目较少，可 以由设计者自行凑出可行点作为复合形顶点。 • 但对于维数较高的优化问题，这种方法常常很困 难。一般采用构成复合形的随机方法。 • 该方法是先产生k个随机点，然后再把那些非可 行随机点调入可行域内，最终使k个随机点都成 为可行点而构成初始复合形。 9
3、构成复合形的随机方法：（1）产生k个随机点·利用标准随机函数产生在（0，1）区间内均匀分布的随机数i，然后产生区间（a;，b）内的随机变量Xi，x=a;;(b;-a)，l，2，...，n。以这n个随机变量为坐标构成随机点xl。·同理，再次产生在（0，1）区间内均匀分布的随机数，然后获得区间（a，b）内的随机点x2，依次类推,可以获得k个随机点xl、x2、x3、…、xk。·产生k个随机点总共需要产生kxn个随机数。·用上述方法产生的随机点不一定是可行点。高10
3、构成复合形的随机方法： （1）产生k个随机点 10 • 利用标准随机函数产生在（0，1）区间内均匀分布 的随机数i，然后产生区间（ai，bi）内的随机变量 xi，xi=ai+ i (bi - ai )，i=1，2，.，n。以这n个随机 变量为坐标构成随机点x 1 。 • 同理，再次产生在（0，1）区间内均匀分布的随机 数i，然后获得区间（ai，bi）内的随机点x 2，依次 类推,可以获得k个随机点x 1 、 x 2 、 x 3 、.、 x k 。 • 产生k个随机点总共需要产生kn个随机数。 • 用上述方法产生的随机点不一定是可行点