第7章--约束问题的优化方法

第7章 约束问题的优化方法7.1 可行方向法7.1.1 可行方向法的基本思想可行方向法是一类算法,可看作无约束下降算法的自然推广。典型策略是从可行点出发，沿着下降可行方向进行搜索，求出使目标函数值下降的新的可行点考虑只含线性约束的非线性规划问题： （1）为非线性函数，.注1：线性约束规格保证了优化问题（1）的可行方向集、线性化可行方向集以及序列化可行方向集是等同的。当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。目前已经提出许多可行方向法，用来处理具有线性约束的非线性规划问题。搜索方向选择方式不同形成不同的可行方向法：（1）Zoutendijk可行方向法（2）Rosen梯度投影法（3）Wolfe既约梯度法可行方向的判定：定理1：设是问题（1）的可行解，在点处有，其中，则非零向量为处的可行方向的充要条件是，证明：必要性：设非零向量是处的可行方向根据可行方向的定义，使得对每个有为可行点，即，.由于，由上式得到又由得到. 充分性：设，.由于，则，使得对于所有的,成立.根据假设及，得到.上述两式组合起来就是.又由及可知表明是可行点，因此是处的可行方向7.1.2 Zoutendijk可行方向法Zoutendijk子问题：根据定理1，如果非零向量同时满足, ，,则是处的下降可行方向Zoutendijk可行方向法把确定搜索方向归结为求解线性规划问题 （2）在（2）式中，显然是可行解，可推知目标函数最优值必定小于或等于零如果目标函数最优值小于零，则得到下降可行方向；否则，如果目标函数最优值为零，则x是K-T点定理2：考虑问题（1），设是可行解，在点处有，其中，则为K-T点的充要条件是问题（2）的目标函数最优值为零一维搜索步长的确定：设为处一个下降可行方向后继点迭代公式：的取值原则：(l)保持迭代点的可行性；(2)使目标函数值尽可能减小根据上述原则，可以通过求解一维搜索问题来确定步长： （3）由于是可行方向，因此，(3)式中第2个约束是多余的在点处，把不等式约束区分为起作用约束和不起作用约束：，(3)式中第1个约束可以写成 （4）由于为可行方向，以及，因此自然成立约束条件（4）简化为问题（3）简化为 （5）根据（5）式的约束条件，容易求出的上限，令 由知. (5)式的约束条件写成：由此得到的上限：问题（3）最终简化成： （6）给定问题（1）和一个可行点以后，可以通过求解问题（2）得到下降可行方向，通过求解问题（6）确定沿此方向进行一维搜索的步长初始可行点的确定：为求（1）式的一个可行点，引入人工变量（向量）和，解辅助线性规划 （7）如果（7）式的最优解，那么就是（1）式的一个可行解可行方向法的计算步骤：(l)给定初始可行点，置.(2)在点处把A和b分解成和，使得，计算 (3)求解线性规划问题得到最优解. (4)如果，则停止计算，为K-T点，否则，进行步骤（5）. (5)计算的上限，在上作一维搜索：得到最优解，令 (6)置，返回步骤（2）.例：用Zoutendijk可行方向法解下列问题：取初始可行点.第1次迭代：，在处，起作用约束和不起作用约束的系数矩阵及右端分别为，；，先求在处的下降可行方向： 即 由单纯形方法求得最优解：再求步长: 解一维搜索问题得到：令 第2次迭代：，在处，起作用约束和不起作用约束的系数矩阵及右端分别为，；，求在处的下降可行方向：由单纯形方法求得最优解：沿搜索，求步长: 解一维搜索问题得到：.令 第3次迭代：，；，求在处的下降可行方向：由单纯形方法求得最优解：根据定理1，是K-T点。该例是凸规划，是最优解，目标函数最优值.将可行方向法推广到非线性约束情形：考虑不等式约束问题 （8）定理3：设x是问题（8）的可行解，是在处起作用约束下标集，又设函数,在处可微，函数在处连续，如果，则d是下降可行方向根据定理3，求下降可行方向归结为求解LP问题 （9）设（9）式的最优解为如果，则是在x处的下降可行方向；如果，相应的x必为Fritz John点定理4：设x是问题（9）的可行解，则x是Fritz John点的充要条件是问题（9）的目标函数最优值等于零步长的确定，仍然需要求解一维搜索问题其中 （10）计算步骤：(l)给定初始可行点，置. (2)令，解线性规划问题得最优解，若，则停止计算，为Fritz John 点；否则，进行步骤（3）. (3)求解一维搜索问题其中由（10）式确定，得到最优解（4）令，置，返回步骤（2）.Zoutendijk算法的收敛问题：不能保证Zoutendijk方法迭代产生的序列收敛于K-T点Topkis-Veinott修正Topkis和Veinott把求方向的线性规划改成紧约束和非紧约束在确定下降可行方向中均起作用，并且在接近非紧约束边界时，不至发生方向突然改变修正方法计算步骤：(l)给定初始可行点，置. (2)解线性规划问题得最优解.(3)若，则停止计算，为Fritz John 点；否则，进行步骤（4）.(4)求解一维搜索问题其中由（10）式确定，得到最优解（5）令，置，返回步骤（2）.Topkis-Veinott修正方法的收敛性:定理5: 考虑问题（8），设函数连续可微，又设是Topkis-Veinott算法产生的序列，则的任一聚点是Fritz John点7.2 惩罚函数法7.2.1 惩罚函数法的基本思想惩罚函数法的基本思想：借助罚函数把约束问题转化为无约束问题，进而用无约束最优化方法来求解考虑约束问题 （1）求解的一种途径是由目标函数和约束函数组成辅助函数，把原来的约束问题转化为极小化辅助函数的无约束问题对于等式约束问题： （2）可定义辅助函数参数是很大的正数（2）式转化为无约束问题 （3）求解问题（3）能够得到问题(2)的近似解对于不等式约束问题： （4）定义辅助函数（4）式转化为无约束问题 （5）通过（5）式求得（4）式的近似解一般情形（1）式）：可定义辅助函数其中连续函数和满足条件：函数和的典型取法：为给定常数通常取作 . 约束问题（1）转化为无约束问题 （6）称为罚项，称为罚因子，而称为罚函数。 当x为可行点时，有；当x不是可行点时，是很大的正数，它的存在是对点脱离可行域的一种惩罚，作用是在极小化过程中迫使迭代点靠近可行域求解问题（6）能够得到约束问题（1）的近似解。越大，近似效果越好。7.2.2 乘子法1 乘子法的基本思想考虑只有等式约束问题（2）.运用乘子法事先需要定义增广Lagrange函数（乘子罚函数）: (7)与Lagrange函数的区别在于增加罚项;与罚函数的区别在于增加了乘子项注1：增广Lagrange函数与Lagrange函数及罚函数具有不同的性态，即对于，只要取足够大的罚因子，不必趋向无穷大，就可通过极小化，求得问题（2）的局部最优解为证明上述结论，先给出如下假设：设是等式约束问题（2）的一个局部最优解，且满足二阶充分条件，即存在乘子，使得且对每一个满足的非零向量d ，有其中，定理1：设和满足问题（2）的局部最优解的二阶充分条件，则存在，使得对所有的，是的严格局部极小点反之，若存在点，使得且对于某个，是的无约束极小点，又满足极小点的二阶充分条件，则是问题（2）的严格局部最优解证明：需要用到矩阵理论的相关知识和二阶充分条件的定义。注2：根据定理1，如果知道最优乘子 ，那么只要取充分大的罚因子，不需趋向无穷大，就能通过极小化求出问题（2）的解注3：确定最优乘子一般方法：先给定充分大的和Lagrange乘子的初始估计v，然后在迭代过程中修正v，力图使v趋向.修正v的公式：设在第k次迭代中，Lagrange乘子向量的估计为，罚因子取，得到的极小点这时有对问题（2）最优解，当线性无关，应有假如，则必有一般来说，并非是，因此该等式并不成立但由此可以给出修正乘子v的公式，令 （7）然后再进行第k+1次迭代，求的极小点这样做下去，可望, 从而如果不收敛，或者收敛太慢，则增大参数，再进行迭代收敛快慢一般用来衡量2 等式约束问题乘子法计算步骤（1）给定初始点，乘子向量初始估计，参数，允许误差，常数, ，置. （2）以为初点，解无约束问题得解. （3）若 ,则停止计算，得到点；否则，进行步骤（4）. （4）若，则置，转步骤（5）；否则，进行步骤（5）.（5）用（7）式计算，置，转步骤（2）. 例1：用乘子法求解下列问题：增广Lagrange函数取罚因子，令Lagrange乘子的初始估计，由此出发求最优乘子及问题的最优解.以下用解析方法求函数的极小点第1次迭代：容易求得的极小点为第k次迭代：取乘子，增广Lagrange函数的极小点为现在通过修正求，由（7）式，有易证当时，序列收敛，且同时，得到最优乘子.问题的最优解注4：在实际计算中，应注意的取值如果太大，则会给计算带来困难；如果太小，则收敛减慢，甚至出现不收敛情形.3 不等式约束问题的乘子法考虑只有不等式约束的问题(4).为利用关于等式约束问题得到的结果，引入变量，把问题（4）化为等式约束问题这样可定义增广Lagrange函数问题（4）转化为求解 (8)将关于y求极小，由此解出y，并代入（8）式，将其化为只关于x求极小的问题为此求解用配方法将化为（9）为使关于取极小，取值如下：当时，当时，综合以上两种情形，即 将上式代入（9）式，由此定义增广Lagrange函数将问题（4）转化为求解无约束问题： 4 一般约束问题的乘子法对于既含有不等式约束又含有等式约束的问题（1），定义增广Lagrange函数 在迭代中，与只有等式约束问题类似，取定充分大的参数，通过修正第k次迭代中的乘子和，得到第次迭代中的乘子和乘子和修正公式： (10)计算步骤与等式约束情形相同例2：用乘子法求解下列问题：增广Lagrange函数为令 得到的无约束极小点 取，得到的极小点： 修正，令求得的极小点以此类推，设在第k次迭代取乘子，求得的极小点修正，得到显然，按上式迭代得到的序列是收敛的.令，则 及 注5：在乘子法中，由于参数不必趋向无穷大就能求得约束问题的最优解，因此不出现罚函数法中的病态计算经验表明，乘子法优于罚函数法，受到广大使用者的欢迎7.3 序列二次规划法7.3.1 序列二次规划法的基本思想序列二次规划法（SQP）的基本思想：在迭代点处构造一个二次规划（QP）子问题，近似原来的约束优化问题；通过求解该QP子问题，获得约束优化问题的一个改进迭代点；不断重复这个过程，直到求出满足一定要求的迭代点。考虑一般的约束优化问题 （1）直觉：利用泰勒展开在迭代点构造QP子问题： （2）令，则（2）等价于二次规划：求出最优解为，则新的迭代点为：7.3.2 Lagrange-Newton法等式约束的Lagrange-Newton法求解非线性方程组的Newton迭代公式为可以证明：解方程组的Newton法具有局部二次收敛性。考虑等式约束最优化问题： （3）问题（3）的Lagrange函数为 令表示在处的Jacobi矩阵，即设为（3）的解且行满秩，则存在使得是（3）的K-T点，即 （4）令，则函数的Jacobi矩阵为求解非线性方程组（4）的Newton迭代公式为： （5）是如下线性方程组的解： （6）称由（5）-（6）式建立的求解约束最优化问题（3）的算法为Lagrange-Newton法.Lagrange-Newton法不易于直接用于不等式约束最优化问题，需要导出Lagrange-Newton法的另一种形式.(与QP挂钩)由约束最优化问题的K-T条件不难看出：Lagrange-Newton法迭代公式（5）-（6）计算的是如下QP问题的解： （7）且是相应于等式约束的Lagrange乘子.求解等式约束问题（3）的Newton法可等价地叙述为：先求二次规划（7）的K-T点，然后由（5）式确定.对问题（7）的任何可行点，有问题（7）等价于二次规划 （8）二次规划问题（8）的K-T条件为： （9）比较（5）、（7）、（9）式，可看出：求解非线性方程组（4）的Lagrange-Newton法可等价地叙述为：求QP问题（8）的K-T点，令，由此产生迭代序列，称此Lagrange-Newton法为求解等式约束问题（3）的SQP算法.一般约束优化问题的Lagrange-Newton法对一般约束优化问题，在当前点构造如下QP子问题： （10）解上述QP子问题，得到解及对应的乘子和，产生新的迭代点，其中.该算法称为求解约束问题（1）的局部Newton-SQP算法.注1：子问题（10）的目标函数是问题（1）的Lagrange函数的二次近似，而不是我们通常认为的仅是问题（1）的目标函数的二次近似.基于Lagrange-Newton法的局部SQP算法步骤：（1）取初始点，置.（2）若满足约束问题（1）的K-T条件（从计算角度应考察），则停止计算，得到；否则，转步骤（3）.（3）解QP子问题（10），得到解.（4）令，转步骤（2）.注2：遗留问题：（i）如何求解QP子问题（后面再讨论）？（ii）如果初始点取得不恰当，即使原问题可行，也可导致QP子问题不相容。QP子问题不相容（可行域为空）如何处理？例1：对于约束，在点处，线性化近似约束为，不相容！7.3.3 Wilson-Han-Powell法在构造QP子问题（10）时，需要计算Lagrange函数在迭代点的Hesse矩阵，这种计算工作量比较大。借鉴无约束优化的拟牛顿法在迭代过程中利用对称正定矩阵替代Hesse矩阵的思想，韩世平（S.P. Han）1976年基于Lagrange-Newton法提出了一种利用对称正定矩阵替代矩阵的序列二次规划法（也称为约束拟牛顿法，约束变尺度法）.Wilson在1963年较早地考虑了Lagrange-Newton法. 后来Powell在1977年修正了Han的方法，故将这种序列二次规划法称为Wilson-Han-Powell(WHP)方法对于一般的约束问题（1），WHP方法需要构造如下的QP子问题： （11）利用子问题（11）的解作为搜索方向。WHP方法除了用矩阵替代矩阵外，新的迭代点不直接按计算，而是由一维搜索确定步长，新的迭代点为.由于这些改进，WHP方法在一定条件下具有全局收敛性. 相对于Lagrange-Newton法（局部SQP算法），WHP方法称为全局SQP算法.（11）式确定的具有一个比较好的性质：它是许多罚函数（价值函数，Merit Function）的下降方向.WHP方法中一种罚函数形式如下(范数-1罚函数)： （12）为罚因子.利用该罚函数作一维搜索确定步长.WHP方法的计算步骤：（1）初始化：给定初始点，对称正定矩阵，容许误差和满足的非负序列；取参数，置.(2)收敛性检验：求解二次规划子问题（11），得到最优解.若，则得到原来约束优化问题的一个近似K-T点，算法停止；否则，转步骤（3）.（3）改进迭代点：利用（12）式的罚函数,按照某种线性搜索规则确定步长，使得置.(4)修正矩阵：利用矩阵，在和点的其它信息，计算对称正定矩阵；令，转步骤（2）.注3：遗留问题：（1） 如何求解QP子问题（11）？（后面讨论）（2） 如何修正获得？（3） 如何处理QP子问题不相容？（1）的修正方法：的修正有多种方法：（i）基于拟牛顿校正公式的方法（ii）基于增广Lagrange函数的方法（iii）基于既约Hesse矩阵的方法只介绍基于拟牛顿校正公式的方法.对于的修正，一方面，应为Lagrange函数的Hesse矩阵的近似；另一方面，要保持的对称正定性，使得相应的QP子问题是一个严格的凸二次规划问题.类似于无约束问题的拟牛顿法，令然后可利用BFGS等公式计算. (BFGS公式) 注4：与无约束问题不同的是：这种修正不能保证条件（曲率条件）成立，因此，即使对称正定，也不能保证正定.为了克服此困难，1978年Powell利用和的一个凸组合代替，记为（13）修正后的BFGS公式（称为截断BFGS修正） (14)（2）QP子问题不相容的处理：Powell提出了一种处理方法：引进辅助变量，解LP： （15）为该问题的可行解，故（15）式的最优解总是存在的，记为，显然有.显然原子问题（11）（或（10）相容当且仅当.（i）若或很小，则改变初始点重新开始，此情况的发生常常因原问题是不相容的；（ii）若，则将子问题（11）中的约束条件用（15）中的约束条件代替，即子问题取为（16）其中取为中的一个定值.例2：对于约束，在点处，求如下线性规划最优解为.若取，则对应的QP子问题（16）是相容的.7.3.4 二次规划的求解方法二次规划（QP）是非线性规划中一种特殊情形，目标函数是二次函数，约束是线性函数。许多现实问题本身可建模为二次规划。QP是前面讨论的SQP的基础，在每一迭代步，均要求解一个QP子问题。QP的算法较多，如：（1）Lagrange方法（2）起作用集方法（3）Lemke方法（4）路径跟踪法1Lagrange方法（求解等式约束QP问题）考虑QP问题 （17）为n阶对称矩阵，为矩阵，秩为.该问题的Lagrange函数为令，得到方程组将此方程组写成 （18）系数矩阵称为Lagrange矩阵.设Lagrange矩阵可逆，可表示为由式，推得假设逆矩阵存在，由上述关系可得的表达式 （19） （20） （21）（18）式两端乘以Lagrange矩阵的逆，得到问题的解 （22） （23）的另一种表达式：设是问题（17）的任一可行解，即满足，在此点目标函数的梯度利用和，可将（22）、（23）改写为 （24） （25）例3：用Lagrange法求解，可计算出 由（19）-（21）式算得，再根据（22）式，计算问题的最优解2起作用集方法（具有不等式约束的QP问题）考虑具有不等式约束的QP问题： （26）为n阶对称正定矩阵，为矩阵，秩为. 该问题不能直接用Lagrange方法求解，求解的策略之一，是用起作用集方法将它转化为求解等式约束问题.起作用集方法的基本思想：在每次迭代中，以已知的可行点为起点，把在该点起作用约束作为等式约束，在此约束下极小化目标函数，而其余的约束暂且不管，求得新的比较好的可行点后，再重复以上做法。设在第次迭代中，已知可行点，在该点起作用约束指标集用表示.这时需求解等式约束问题 （27）表示矩阵A的第i行，也是在处起作用约束函数的梯度.将坐标原点移至，令，则 （28）问题（27）等价于求校正量的问题： （29）解此二次规划问题，求出最优解，然后区别不同的情形，决定下面应采取的步骤. （1）如果是可行点，且，则在第次迭代中，已知点取作 （2）如果不是可行点，则令方向，沿搜索. 令沿方向搜索步长确定方法：基本要求：保持点的可行性.的取值应使得对于每个，有 （30）已知是可行点，故.（1）当时，对于任意非负数，（30）式总成立；（2）当时，只要取正数对于每个，（30）式成立. 记 是问题（29）的最优解，为在第次迭代中得到较好的可行点，应取 （31）并