最优化理论与方法3(2014-3)

̀《最优化理论与方法》讲义(下-续)第六章常用约束最优化方法考虑一般的约束最优化问题，其数学模型为1.6,,2,1,0,,2,1,0..minmjXhliXgtsXfji求解约束优化问题，就是要在可行域mjXhliXgXDji,,2,1,0;,,2,1,0/中，找一个可行点*X使目标函数Xf取得最小值。此时称**,XfX为问题1.6的最优解。由处理约束条件的办法不同，约束优化方法也可分为直接法和间接法两大类。间接法的基本思想是将约束优化问题首先转换为一系列的无约束优化问题，然后利用无约束优化方法来求解，逐渐逼近约束问题的最优解。这些算法一般比较复杂，但由于它们可以采用计算效率高、稳定性好的无约束优化方法，故可用于求解高维的优化问题。直接法的基本思想是构造一迭代过程，使每次迭代点都在可行域D中，且一步一步地降低目标函数值，直到求得最优解。这类方法很多，如约束坐标轮换法，复合形法等。这类方法一般是算法简单，对目标函数和约束函数无特殊要求，但计算量大，需用机时较多，不适用维数较高的问题，而且一般用于求解只含不等式约束的优化问题。6.1外点罚函数法对于问题1.6，本节所述方法的基本策略是，根据约束特点(等式或不等式)构造某种“罚函数”，然后把它加到目标函数中去，使得对约束最优化问题的求解转化为对一系列无约束问题极小点或者无限地向可行域靠近，或者一直保持在可行集内移动，直到收敛于原来约束最优化问题极小点。一、外点罚函数法基本原理对问题1.6，构造一函数为XMXfMXFkk,其中2.61212liiimjjXguXgXhX在式2.6中，X又称为惩罚函数。时当，时当DXDXX0,0，时当，时当010,0XgXgXguiii0kM是一个逐渐增大的参数，kMXF,称为惩罚因子，又称为问题1.6的增广目标函数。显然，增广目标函数kMXF,是定义在nR上的一个无约束函数。由增广目标函数kMXF,的构造知：·当DX时，XfMXFk,，此时kMXF,的最优解就是问题1.6的最优解；·当DX时，kMXF,的最优解就不一定是问题1.6的最优解。但是研究当DX时，kMXF,的最优解我们是不感兴趣的。为此规定：当DX时，kMXF,在X点处的函数值迅速增大。换句话说，可行域外的任一点X处的函数值kMXF,都相当大。此时要求kMXF,在nR中的最优解，只能让点X回到D内才有可能求得kMXF,在nR中的最优解，然而一旦当点X回到D内，即DX，此时kMXF,就与问题1.6就有相同的最优解。当DX时，kMXF,迅速变大是通过罚因子M来实现。简言之，外点罚函数法的思想是：当点DX时，设法加大不可行点处的函数值，使不可行点不能成为kMXF,在nR中的最优解。一般地，在用外点罚函数法求解问题1.6时，首先构造增广目标函数kMXF,，然后按照无约束优化方法求解。如果求出kMXF,的最优解为MX，则判断MX是否属于D。如果DXM，则MX是问题1.6的最优解；如果DXM，则不是问题1.6的最优解。此时说明原来的罚因子给小了，需加大罚因子，使得kkMM1，然后再重新计算kMXF,的最优解。二、外点罚函数法迭代步骤已知问题1.6，构造增广目标函数XMXfMXFkk,其中惩罚函数X按式2.6构造，给定终止限(可取610)。Step1选定初始点0X，初始罚因子1M(可取11M)，罚因子放大系数10C，置1k；Step2假设已获迭代点1kX，以1kX为初始点，求解无约束问题kMXF,min，设其极小点为kX；Step3若kkXfX,，XMk，则kX就是所要求的最优解，输出打印kX，停机；否则，转Step4；Step4置1,1kkCMMkk，转Step2。三、举例例1求解01..min22221xXhtsxxXf解：可以看出，本题的约束最优解为0.1,1,0**XfXT现用外点罚函数法解这个约束优化问题。构造增广目标函数2222211,xMxxMXFkk由此0,021xFxF解得TkkkMMMX1,0*给定一个罚因子kM，即可求得极小点kMX*，可以看出kMX*不是可行点，且有TkMMXk1,0lim*右图给出了不同kM时kMX*的的轨迹。它有助于进一步理解用外点罚函数法求极小点序列kMX*时怎样收敛于约束最优点*X。．例2用外点罚函数法求02..1min2xtsxxf解:增广目标函数为221,22xuxMxMxFkk按阶跃函数的定义，时当时当22121,222xxMxxxMxFkk对于1010，，kM，下图画出了kMxF,的图形．由图可以看出，kMxF,的极小点MX全不属于可行域。因此只须考虑2x的情况。实际上，对于固定的kM，令02212,'xMxMxFkkx由此解得kkMMMxk121这就是对于固定的kM，求得kMxF,的极小点。例如，当0kM时，1kMx；当1kM时，23kMx；当10kM时，1121kMx。若令kM时，则2kMx。这里的2*x，就是本例的极小点。四、外点罚函数法有关说明在外点罚函数中，是通过一系列惩罚因子,1,0,kMk求kMxF,的极小点来逼近原约束问题的最优点。这一系列的无约束极小点kMX*将从约束可行域外部向约束边界运动，实际上，随着罚因子的增大，迫使惩罚项的值逐渐减小，从而使kMxF,的极小点kMX*沿着某一运动轨迹逐渐接近等式约束面与起作用的不等式约束面上的最优点*X。当kM趋于无穷大时，kMxF,的极小点就是原问题的最优点*X。容易提出这样的问题：既然越大越好，那么迭代一开始就把kM取得很大，似乎求解一次无约束问题就可以求得到约束问题的最优解，可以少解几次无约束问题。但是可以证明，kM越大，增广目标函数的Hesse矩阵的条件数越坏，给无约束问题求解增加越来越大的困难，甚至无法求解。因此，在迭代开始时又不得不把kM取得小一些。无疑，这增加了计算量，这正是外点罚函数法的弱点。此外，当Xf在D处无定义时，kMxF,的性质变得很复杂。另一方面，由于外点罚函数法是从D外迭代点逼近D内最优解，所以在寻优的过程中不能直接观察到D内点的变化情况，也无法求得近似最优解。6.2内点罚函数法内点罚函数法刚好克服了外点罚函数法的不足之处，内点罚函数法的迭代过程均在可行域D内进行，它是通过在D内寻找一串点列krX来逼近最优解*X。一、内点罚函数法基本原理首先在D的边界设置一道障碍，当从可行域D中的某点0X出发进行迭代时，每当迭代点靠近D的边界时，便被此边界上的障碍(形如绝壁)阻挡碰回，这种阻挡碰回实质上也是一种惩罚，换句话说，所谓阻挡碰回就是当迭代点靠近D的边界时，离边界越近函数值增加越大，特别当迭代点到达边界上时，函数值变为无穷大。由此可以想象不可能在靠近D的边界上取得最优解，只能在远离D的边界内找到最优解。按照这种想法，对于3.6,,2,10..minliXgtsXfi构造如下增广目标函数liikkXgrXfrXF11,其中，0kr称为障碍因子，liiXg11称为障碍函数。下面我们来分析krXF,是否符合内点罚函数法的构造设想。显然krXF,和Xf都定义在D内，kr取值较小时，当迭代点远离边界，XfrXFk,，此时krXF,的最优解可作为问题3.6的近似最优解；但当迭代点靠近D的边界时，由krXF,的构造知，即使kr取值很小，但0Xgi，即Xgi1使得krXF,的函数值变得很大，此时显然不可能在区域D的边界附近求得krXF,的最优解，于是迫使迭代点被阻挡碰回到远离区域D的边界去寻优。用式子表示即是当障碍因子021vrrr逐渐减小时，有XfrXFkrk,lim0且*0limXrXkrk4.6式4.6中krX为krXF,的极小值点序列，*X为问题3.6的最优解。二、内点罚函数法迭代步骤已知对问题3.6，构造增广目标函数liikkXgrXfrXF11,给定终止条件0(可取610)。Step1选定初始点DX0，初始障碍因子101r，障碍因子的缩小系数1c(可取1.0c)，置1k；Step2假设已获迭代点1kX，以1kX为初始点，求解krXF,min，设其最优解为krX；Step3若likikrXgr11，则krX是问题3.6的最优解，打印输出kkrXfrX,，停机；否则，转Step4；Step4置1,1kkcrrkk，转Step2。二、举例用内点罚函数法求解:构造增广目标函数2221214,xxrxxrXFkk由0,021xFxF解得TkkkkkrrrrrX28,2822*给定一个罚因子kr，即可求得一极小点krX*。右图给出不同罚因子时krX*的轨迹。可看出krX*在可行域内，且随着kr逐渐逼近于0，krX*逐渐逼近理论最优点TX2-2-*，。三、内点罚函数法有关说明1222112min()..()40fXxxstgXxx，．①内点罚函数法的优点在于每次迭代都是可行点，当迭代到一定次数时，尽管可能没有达到约束最优点，但可以被接受为一个较好的近似最优点。②在实际应用中，按该点求得的解可能比初始解有很大的改进，因而被工程技术人员接受，作为一种最优设计方案。③然而，内点罚函数法要求初始点位于可行域内部，即所有的约束需按严格不等式满足。这对于简单的优化问题是不难解决的，因为原设计方案可能是用常规设计方法求得的，虽然不是最优，但一般是可行的，因此就可将原方案作为初始点。但对复杂的优化问题，由于变量和约束较多，要想得到一个可行的初始点，并不十分容易，这时就要采用求解可行点的算法。在内点罚函数法中，障碍函数的定义域是约束可行域。因此，在求krXF,的最优解时，并不是求它在整个n维欧氏空间中的最优解，而是求在约束可行域liXgXDi,,2,1,0/上的极小点。这是因为障碍函数liiXg11在D的边界上无定义，而在D的外部某些项为负，并且可取绝对值任意大的负值，从而使krXF,趋于，所以krXF,在全空间nR内的极小点是不存在的。因此，在用无约束优化方法求krXF,的最优解时，要防止越过约束边界而搜索到非可行域中去，这就要求在一维搜索时，要适当控制步长，保证搜索在可行域内进行。6.3混合罚函数法前面介绍了外点罚函数法和内点罚函数法。外点罚函数法的初始点可以任选，适用于求解具有等式约束与不等式约束的优化问题；而内点罚函数法要求初始点在可行域内，适用于求解不等式约束优化问题。为了综合外点罚函数法与内点罚函数法的优点，常将两种算法结合起来使用，这样便形成了混合罚函数法。一、混合罚函数法基本原理对于同时具有不等式约束和等式约束的优化问题，混合罚函数法采用的罚函数形式又分为内点形式和外点形式两种。下面介绍内点形式的混合罚函数，即mjjkliikkXhrXgrXfrXF12111,采用内点形式的混合罚函数时，混合初始点0X应选为满足各个不等式约束条件的点，障碍因子k