二次规划问题.docx

______________________________________________________________________________________________________________
序列二次规划法
求解一般线性优化问题:

(1.1)
基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通过减少价值函数来获取当前迭代点的移动步长，重复这些步骤直到得到原问题的解。
1.1等式约束优化问题的Lagrange-Newton法
考虑等式约束优化问题

(1.2)
其中都为二阶连续可微的实函数.
记.
则(1.3)的Lagrange函数为：

（1.3）
其中为拉格朗日乘子向量。
约束函数的Jacobi矩阵为：.
对（1.3）求导数，可以得到下列方程组：

（1.4）
现在考虑用牛顿法求解非线性方程（1.4）.
的Jacobi矩阵为：

（1.5）
其中是拉格朗日函数关于的Hessen矩阵.
也称为K-T矩阵。对于给定的点，牛顿法的迭代格式为：.
其中是线性方程组

（1.6）
的解。
注意：只要行满秩且是正定的，那么（1.6）的系数矩阵非奇异，且方程组有唯一解。

引理1：已知矩阵，则对任意满足的非零向量都有的充要条件是存在常数，使得对任意的都有
.
证明略。

鉴于方程组（1.6）的求解数值不稳定，故考虑将它转化成一个严格凸二次规划问题.转化的条件是(1.4)的解点处的最优性二阶充分条件成立，即对满足的任一向量，成立。
再由引理1知：当充分小时，正定。
考虑（1.6）中的用一个正定矩阵来代替，记

则当时，矩阵正定。
（1.6）的第一个展开式为

将上式变形为：

令后得：.
因此，（1.6）等价于

（1.7）
进一步，可以把方程（1.7）转换成如下严格凸二次规划：

（1.8）
方程（1.7）和（1.8）具有同解的。
1.2一般形式的约束优化问题
将1.1节中构造二次规划子问题求解等式约束优化问题的思想推广到一般形式的约束优化问题(1.5)。在给定点后，将约束函数线性化，并对拉格朗日函数进行二次多项式近似，得到下列二次规划子问题：

（1.9）
其中，拉格朗日函数为.
于是，迭代点的校正步以及新的拉格朗日乘子估计量可以分别定义为问题
的一个K-T点和相应的拉格朗日乘子向量。
定理1：给定约束优化问题（1.1）的最优解 和相应的拉格朗日乘子.假定在处，下面的条件成立：
（1） 有效约束的Jacobi矩阵行满秩，其中;
（2） 严格互补松弛条件成立，即
（3） 二阶最优性充分条件成立，即对满足的任一向量，成立.
那么若充分靠近，则二次规划问题(1.9)存在一个局部极小点，使得其对应的有效约束指标集与原问题在处的有效指标集是相同的。

注意：在构造二次规划子问题时，需要计算拉格朗日函数在迭代点处的Hessen矩阵，计算量过大。为了克服这个缺陷，韩世平基于牛顿-拉格朗日法提出了一种利用对称正定矩阵来代替拉格朗日矩阵的序列二次规划法。
对于一般约束优化问题（1.1），在迭代点，构造下列形式的二次规划子问题：
（1.10）
并且用（1.10）的解作为原问题变量在第次迭代过程中的搜索方向。其中有一个好的性质是它许多罚函数（价值函数）的下降方向。例如，对于L1精确罚函数：

其中为罚参数，。
为了保证SQR方法的全局收敛性，通常借助价值函数来确定搜索步长。用来衡量一维搜索的好坏。
算法（一般约束优化问题的SQP方法）
Step 0: 给定初始点对称正定矩阵.
计算
，，.
选择参数容许误差令
Step 1: 求解子问题（1.10）得最优解.
Step 2: 若且,stop,得到(1.1)的一个近似KT点.
Step 3: 对于某种价值函数，选择罚参数，使得是该函数在处的下降方向。
Step 4: Armijo搜索. 令是使下列不等式成立的最小非负整数:

令
Step 5: 计算

以及最小二乘乘子

Step 6: 校正矩阵为.令

其中

参数定义为

Step 7: 令转1.
注意：（step 1）
利用K-T条件，问题(1.10)等价于
（1.11）
第三式是维互补问题，定义光滑函数

其中为光滑参数.令
，
其中
其中表示的第行.记，那么（1.11）问题等价于

则的Jacobi矩阵为

其中,由下式确定：

而，其中由下式确定：

给定参数，定义非负函数

（step 3）中选择价值函数

可令，
任意选择一个，定义罚参数的修正规则为

（step 6）因为BFGS修正公式需要满足曲率条件，即,而可能不满足这一条件，为此有必要对进行修正。

参考文献
[1] 马昌凤.最优化方法及其matlab程序设计.科学出版社.2010.

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！

精品资料