二次规划的理论与算法(续)

三、二次规划的对偶理论对偶理论是数学规划的重要基础理论之一。线性规划的对偶理论在五十年代初期即已被提出(对偶理论的思想则最初是由Von Neumann在1947年提出的),它对线性规划的算法研究起了推动作用。线性规划的对偶定理指出:     

二次规划的理论与算法(Ⅲ)

四、二次型的正定性和半正定性的判定条件这一节我们叙述几个比较简便实用的判定条件,用于判定二次型的正定性和半正定性,这种判定关系到我们寻求二次规划的最优解时选择哪一种合适的算法。下面的大多数定理在一般的线性代数的书中是没有的。     

二次规划的理论与算法(Ⅵ)

六、带约束的凸二次规划的解法(续)我们现要证明 Lemke 方法的有限步终止性,也就是要证:当 C 是正定矩阵时,经过有限次迭代运算后得到规划(6.20)的最优解.这里我们总假定原规划(6.15)有可行解,再由于C 是正定的,所以规划(6.15)有最优解,所以规划(6.20)也有最优解.如果在迭代中得到的点 y~l 是可行集的内点,即 y~l>0,它满足 q+Qy~l=0,则 y~l 为最优解,此时 J~i=φ.如果 y~l是可行集的边界点,即 J~l≠φ,利用等式(6.21),g(y)在点 y 的梯度可表为λ=sum form i-1 tow_ib_i、其     

二次规划的理论与算法

二次规划问题是指无约束或有线性约束的二次函数的最优化问题。关于二次规划的理论和算法的研究在非线性规划的发展过程中占有相当的地位,这不仅由于一些实际问题可化成二次规划问题,而且一般的带非线性约束的非线性规划可藉助于解一列二次规划来求得原问     

二次规划的理论与算法(Ⅴ)——六、带约束的凸二次规划的解法

以下几章我们将叙述带约束的二次规划的一些基本的常用的求解算法,并且给出这些算法的理论基础,二次规划的算法大体上分为四种类型:一类是基于单纯形转轴的算法,它们是由线性规划的单纯形转轴运算发展而成的,这是因为二次规划具有与线性规划类似的特点;一类是基于主动集(active sets)的算法,这类算法考虑了二次规划作为非线性规划而具有的特点;一类是椭球方法,它们是从线性规划的椭球算法发展而成的。一般而言,前     

半无限规划的递归二次规划算法

本文对于半无限规划问题提出了 WHP 递归二次规划算法,并证明此算法具有整体收敛性。     

二次规划的矩阵分解算法

本文利用广义逆和矩阵的分解理论讨论二次规划问题(QP),并给出了一个求解二次规划问題的矩阵分解算法。     

二次规划的内点算法

介绍了二次规划内点算法的一些最新研究成果，选择了几个有代表性的算法加以分析研究，从而对二次规划的内点算法做出了一个整体概述。     

一类二次二层规划的平衡点算法

Manoel Campelo[1]借助线性规划的单纯形算法,给出了求解线性二层规划的平衡点算法.本文借助线性规划的单纯形法和二次规划的Lemke算法,给出求解一类非线性二层规划的平衡点算法,并给出算例说明算法可行性.     

求解带非凸二次约束的广义二次分式规划最小值的全局算法(英文)

基于最近发展的单调优化理论,提出了求解带非凸二次约束的广义二次分式规划最小值的全局算法,给出了算法的收敛性证明. 数值实验表明了该算法的可行性和有效性.     

序列二次规划(SQP)算法在三维下限分析中的应用

采用有限元法和非线性规划的序列二次规划(SQP)算法，解决了三维可静应力场的构造问题．基于刚塑性假设，采用极限分析下限原理，求解了矩形表面基础的承载力问题．算例分析表明，SQP算法在三维下限法中的应用是可行的．     

时变二次规划的高精度数值算法

提出一种用于求解时变二次规划问题的高精度数值算法.首先,给出求解时变二次规划问题的连续模型;然后,采用新型泰勒差分公式将连续模型离散,得到具有高计算精度的数值算法;最后,通过理论分析和仿真实验表明该数值算法的优越性和有效性,并将所提出的数值算法应用于一个五连杆机械臂的运动控制中.研究结果表明:所提算法的计算稳态误差与采样间隔τ具有O(τ~4)的关系,该数值算法既可以有效地求解时变二次规划问题,又能有效地应用于机械臂的运动控制.     

凸二次规划的投影收缩算法

对于一般的凸二次规划问题,首先结合该问题的对偶问题给出了解的充分必要条件,然后给出了一种解决该问题的投影收缩算法,并证明了该投影收缩算法的总体收敛性。     

二次二层规划的一种混合算法

针对下层为二次凸规划的二层规划问题,先利用遗传算法解决上层规划,然后用内点算法解决下层问题.两种方法结合起来得到一种具有全局收敛性的混合算法,并通过算例说明其有效性.     

正定二次规划的投影最小二乘算法

提出了正定二次规划问题的投影最小二乘算法．该算法先求目标函数无约束优化问题的解，再将此解逐次投影到有效约束的边界．迭代过程中不断更新有效约束，最终得到问题的有效约束集，进而得到问题的解．将该算法应用到FIR滤波器的约束最小二乘设计中，算法分析及约束FIR滤波器的设计例子都表明该算法的计算量远小于目前最流行的二次规划算法——有效集方法．     

二次约束二次规划问题的二元均值松弛定界算法

二次约束二次规划(quadratically constrained quadratic programming,QQP)问题目标函数和约束条件均是非凸的,是一类NP难问题,目前还没有通用的全局收敛准则,从而使得求该问题的全局最优解面临着严峻挑战。文章通过引入辅助乘积变量,将QQP问题等价地转化为带有乘积等式约束的非线性规划(nonlinear programming,NLP)问题;进而在NLP问题中利用二元均值不等式结合函数的性质松弛乘积等式约束后,产生QQP问题的带有辅助变量的松弛线性规划(relaxation linear programming,RLP)问题,由此确定QQP问题的全局最优值的下界,利用超矩形基于线性函数的缩减策略,以增强子超矩形的紧致删除能力;最后给出了该算法的收敛性分析,数值实验结果表明所提出的算法是可行且有效的。     

下层为二次规划的双层规划两阶段算法

分析下层为强凸二次规划的双层规划的特殊性质,得到两点结论:若利用下层问题的KKT条件将其化归为线性互补问题(LCP),可结合LCP的互补旋转算法进一步求解原双层规划;若以线性—二次双层规划为子问题构造信赖域算法,得到的子问题的解在原问题的诱导域中。基于以上两点设计出了两阶段算法,在第一阶段,利用LCP互补旋转算法迅速到达一诱导域极点,在第二阶段,利用信赖域算法收敛到局部极小点。收敛性分析和算例表明,此算法简捷且具有较好的收敛性。     

正定二次规划内点稳定算法

进一步讨论一种新二次规划的内点算法.该算法不同于传统的内点算法:它不含有原始或者对偶变量的逆,因而在靠近解集附近也有定义(well defined).证明了若目标函数的二次部分为标准正定二次型,则在计算迭代方向时,可以把对(m 2n)×(m 2n)阶KKT系统的求解转化为(n-m)×(n-m)阶KKT系统的求解,从而在很大程度上提高算法的效率.