序列二次规划法

序列二次规划算法1序列二次规划法简介非线性规划问题是目标函数或约束条件中包含非线性函数的规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不像线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。当目标函数和约束条件具有良好的分析性质时，人们喜欢用间接法分析与求解约束最优化问题。利用间接法求解最优化问题的途径一般有两种，另一种途径是在可行域内使目标函数下降的迭代点法，如可行点法。另一种是利用目标函数和约束条件构造增广目标函数，借此将约束最优化问题转化为无约束最优化问题，然后利用求解无约束最优化问题的方法间接求解新目标函数的局部最优解或稳定点，如人们所熟悉的惩罚函数法，乘子法和序列二次规划等。序列二次规划算法是目前公认的求解约束非线性优化问题的最有效方法之一，与其它优化算法相比，其最突出的优点是收敛性好、计算效率高、边界搜索能力强，受到了广泛重视及应用。但其迭代过程中的每一步都需要求解一个或多个二次规划子问题。一般地，由于二次规划子问题的求解难以利用原问题的稀疏性、对称性等良好特性，随着问题规模的扩大，其计算工作量和所需存贮量是非常大的。因此，目前的序列二次规划方法一般只适用于中小型问题。另外，由于大型二次规划问题的求解通常使用迭代法，所需解的精度越高，花费的时间就越多，稳定性也就越差，相对线性方程组的求解理论来说，二次规划的求解是不完善的。2序列二次规划的研究最优化理论及方法是一个具有广泛应用背景的研究领域。它研究诸如从众多的方案中选出最优方案等问题，常见的各种模型如线性规划，二次规划，非线性规划，多目标规划等。最优化理论及方法已经在经济计划，工程设计，生产管理，交通运输等领域得到了广泛的应用，吸引了很多学者的研究。一般非线性约束的数学规划问题是：min()..()0(1,2,...,)()0(1,2,...,)uvfXstgXuphXvm其中nXR是决策变量，()fX是目标函数，()ugX，()vhX分别是不等式约束函数和等式约束函数。在求解上述问题的诸多算法中序列二次规划(SQP)是最有效的一类方法之一由于它具有超线性收敛速度,对它的研究一直是非线性规划的一个热点,许多学者对它进行了研究和改进序列二次规划（SQP）算法最早由Wilson（1963）提出。Wilson提出了Newton-SQP方法。60年代末和70年代初，随着解无约束优化问题的拟Newton法的发展，拟Newton-SQP算法的研究引起了学者们的高度重视。Polomares-Mangasarian（1976）提出了一类拟Newton-SQP方法。在该类方法中，他采用对Lagrange函数的整体Hesse矩阵（即既对x又对Lagrange乘子的Hesse矩阵）的近似进行修正的方法来修正。Han（1976，1977）证明了PSB-SQP和BFGS-SQP方法的局部收敛性。而且，若采用精确罚函数进行搜索，则算法具有全局收敛性。自此，SQP算法的研究受到了广泛的重视。迄今为止，SQP算法的研究工作已取得了丰硕的成果。SQP算法的主要优点之一是它的全局收敛性和局部超线性收敛性。为使算法具有全局收敛性，通常要求子问题（QP）中的矩阵H对称正定。使得（QP）产生的方向S是某个效益函数的下降方向。另一方面，若矩阵H对称正定，则子问题（QP）是一个严格凸二次规划。此时，该问题有唯一解。而且，其求解也相对容易。因此，研究矩阵H的对称正定性是一项非常重要的工作。并己引起了学者们的重视。Powell（1976）提出了一个修正的BFGS公式。该公式可保证产生的矩阵是对称正定的。数值计算的结果表明利用该修正公式的SQP算法的数值效果较好。然而该算法的局部收敛性质尚不清楚。Coleman和Conn（1984）提出了一种既约Hessian-SQP方法。即用一系列的正定矩阵去逼近解[*,*]S处的既约Hessian矩阵。Noeedal和Overton（1985）提出了单边及双边的投影Hessian方法。在单边投影Hessian方法中证明了局部1-步超线性收敛性而在双边投影Hessian方法中证明了在某种假设条件下的2-步超线性收敛性质。但他的BFGS修正公式是在满足一定的修正准则才进行修正。Xie和Byrd（1999）在RHSQP方法的基础上加上线性搜索得到全局收敛性算法。他并且把Nocedal和Overton的修正法则改为了一种新的修正法则一正曲率法则。这样能得到更好的数值结果。并且证明了当利用两个常用的效益函数，Flether效益函数和1l精确罚函数进行线性搜索时，算法具有全局收敛性和R-线性收敛性。R.Fontecilla（1988）提出了一种2-步超线性收敛算法。与Coleman和Conn不同之处在于他将步长犷分为互相垂直的两个向量：即水平方向的步长kh和垂直方向的步长kv。且仅利用水平方向的步长kh对H进行修正。与coleman和Conn不同之处在于对kS进行分解时他使用了一个正交投影算子而不是标准正交基，比较容易满足连续性条件。比前者适用的范围更广。而且，他把这一方法用在了几种不同的乘子修正公式中。在二阶充分条件下，证明了该算法是2-步超线性收敛的。若在每一次迭代中再计算一次约束函数的值，则算法为1-步超线性收敛。但没有全局收敛性研究。3序列二次规划算法推导过程序列二次规划（SQP）算法是将复杂的非线性约束最优化问题转化为比较简单的二次规划（QP）问题求解的算法。所谓二次规划问题就是目标函数为二次函数，约束函数为线性函数的最优化问题。二次规划问题是最简单的非线性约束最优化问题。3.1序列二次规划算法思想非线性约束最优化问题：min()..()0(1,2,...,)()0(1,2,...,)uvfXstgXuphXvm（1-1）利用泰勒展开把非线性约束问题式（1-1）的目标函数在迭代点Xk简化成二次函数，把约束函数简化成线性函数后得到的就是如下的二次规划问题：T2TTT1min()[]()[]()[]2..()[]()0(1,2,...,)()[]()0(1,2,...,)kkkkkkkkuukkkvvfXXXfXXXfXXXstgXXXgXuphXXXhXvm（1-2）此问题是原约束最优化问题的近似问题，但其解不一定是原问题的可行点。为此，令kSXX将上述二次规划问题变成关于变量的S的问题，即T2TTT1min()()()2..()()0(1,2,...,)()()0(1,2,...,)kkkkuukkvvfXSfXSfXSstgXSgXuphXShXvm（1-3）令2Teq12T12Teq12T12()()[(),(),...,()][(),(),...,()][(),(),...,()][(),(),...,()]kkkkkmkkkpkkkmkkkpHfXCfXAhXhXhXAgXgXgXBhXhXhXBgXgXgX（1-4）将式（1-4）变成二次规划问题的一般形式，即TTeqeq1min2..SHSCSstASBASB（1-5）求解此二次规划问题，将其最优解*S作为原问题的下一个搜索方向kS，并在该方向上进行原约束问题目标函数的约束一维搜索，就可以得到原约束问题的一个近似解1kX。反复这一过程，就可以求得原问题的最优解。上述思想得以实现的关键在于如何计算函数的二阶导数矩阵H，如何求解式（1-5）所示的二次规划问题。3.2二阶导数矩阵的计算二阶导数矩阵的近似计算可以利用拟牛顿（变尺度）法中变尺度矩阵计算的DFP公式TT1TT[][][][]kkkkkkkkkkkkkXXHqqHHHqXqHq（1-6）或BFGS公式1TTTTTTT1[][][][][][][]kkkkkkkkkkkkkkkkkkkHHXXXqXXqHqHqqXqHXq（1-7）3.3二次规划问题的求解二次规划问题式（1-7）的求解分为以下两种情况。（1）等式约束二次规划问题TTeqeq1min()2..fXSHSCSstASB（1-8）其拉格朗日函数为TTTeqeq1min(S,)()2LSHSCSASB由多元函数的极值条件(S,)0L得Teqeqeq00HSCAASB写成矩阵形式，即Teqeqeq0CHASBA（1-9）式（1-9）其实就是以T[,]S为变量的线性方程组，而且变量数和方程数都等于nm。由线性代数知，此方程要么无解，要么有惟一解。如果有解，利用消元变换可以方便的地求出该方程的惟一解，记作11T[,]kkS。根据k-t条件，若此解中的乘子向量1k不全为零，则1kS就是等式约束二次规划问题式（1-8）的最优解*S，即1*kSS。（2）一般约束二次规划问题对于一般约束下的二次规划问题式（1-5），在不等式约束条件中找出迭代点kX的起作用的约束，将等式约束和起作用的约束组成新的约束条件，构成新的等式约束问题：TT11min()2..=knijjjiEIjfXSHSCSstasb（1-10）其中，E代表等式约束下的集合，kI代表不等式约束中起作用约束的下标集合。此式即式（1-8），可以用同样的方法求解。在求得式（1-10）的解11T[,]kkS之后，根据k-t条件，若解中对应原等式约束条件的乘子不全为零，对应起作用约束条件的乘子不小于零，则1kS就是所求一般约束二次规划问题式（1-5）的最优解*S。综上所述，在迭代点kX上先进行矩阵kH的变更，在构造和求解相应的二次规划子问题，并该子问题最优解*S作为下一次迭代的搜索方向kS。然后在该方向上对原非线性最优化问题目标函数进行约束一维搜索，得到下一个迭代点1kX，并判断收敛精度是否满足。重复上述过程，直到迭代点1kX最终满足终止准则，得到原非线性最约束问题的最优解*X为止。这种算法称为二次规划法，它是目前求解非线性约束最优化问题的常用方法，简称SQP法。序列二次规划算法的迭代步奏如下：○1给定初始点0X、收敛精度，令0HI（单位矩阵），置0k.○2在点kX简化原问题为二次规划问题式（1-10）。○3求解二次规划问题，并令*kSS。○4在方向kS上对原问题目标函数进行约束一维搜索，得点1kX。○5终止判断，若1kX满足给定的精度的终止准则，则令1*kXX，1*()kffX，输出最优解，终止计算，否则转○6。○6按式（1-6）或（1-7）修正1kH，令1kk，转○2继续迭代。4MATLAB程序%**************************************************************************************%**************************************************************************************function[d,mu,lam,val,k]=qpsubp(dfk,Bk,Ae,hk,Ai,gk)%功能：求解二次规划子问题%输入：dfk是xk处的梯度，Bk是第k次近似Hesse阵，Ae，hk线性等式约束%的有关参数，Ai，gk是线性不等式约束的有关参数%输出：d，val分别是是最优解和最优值，mu,lam是乘子向量，k是迭代次数%功能：求解二次规划子问题%输入：dfk是xk处的梯度，Bk是第k次近似Hesse阵，Ae,hk线性等式约束%的有关参数，Ai,gk是线性不等式约束的有关参数%输出：d，val分别是是最优解和最优值，mu,lam是乘子向量，k是迭代次数.n=length(dfk);l=length(hk);m=length(gk);gamma=0.05;epsilon=1.0e-6;rho=0.5