求解一般半正定二次规划的数值稳定方法

针对非光滑优化中捆集算法之二次规划子问题数值求解的困难，详细研究了求解半正定二次规划问题的积极性，提出了一系列矩阵分解的存储方法和校正方法，较好地克服了半正定矩阵奇异性带来的数值求解的困难，在求解捆集算法的半正定二次规划子问题中取得了很好的效果，所提出的算法具有较强的实用性。     

摄动的强次可行序列二次规划算法

利用最优性与可行性衡量的凸组合提出了一个新的摄动参数更新技术,从而去掉了传统强次可行序列二次规划算法的全局收敛性分析中需要Lagrange函数近似Hesse阵正定或一致正定的较强假设。且在适当条件下,算法仍具备超线性收性。     

一个修正的强次可行SQCQP算法

提出了一个修正的强次可行序列二次约束二次规划(SQOQP)算法.通过设计一个新的矩阵修正策略,算法在全局收敛性分析中不需要假设目标函数的(近似)Hesse阵正定或一致正定.在适当条件下,算法具备超线性收敛性.     

一类特殊规划的求解算法

二次规划问题是一类重要的优化问题,是NP困难的.通过对已有算法的理解与分析,在假设原问题的Hessian矩阵正定的条件下,作者给出了求解二次规划问题的一种新算法,并讨论了算法的收敛性.     

二次凸规划的迭代解

线性互补问题的投影Jacobi松弛算法应用于求解不等式约束的二次规划问题,对称半正定的二次规划问题由K-T条件可以转化为P_0-矩阵的非对称线性互补问题(LCP),通过求解带扰动项的P-矩阵的非对称线性互补问题得到二次规划的最优解。最后给出一些数值结果。     

一般二次规划的一种分解算法

提出了求解一般二次规划问题的一种分解迭代算法.算法的主要思想是对问题的Hessian矩阵G进行正则分裂,即G=N H并且满足N-H是正定的.在每次迭代中用一个易于求解的矩阵N代替G进行计算.在矩阵G是正定的条件下,算法具有线性收敛性质,产生的迭代点列收敛到原问题的最优解.当矩阵G不正定时,算法产生的点列收敛到问题的稳定点.     

半正定矩阵算术平方根的表示

利用特征根的Lagrange插值多项式，给出了半正定矩阵算法平方根的表示，即公式解，避免了求过渡矩阵的繁琐过程。当特征根难以求出而特征根的对称式易求时，半正定矩阵的算法平方根可直接由矩阵的本谢的性质来表示。     

利用交替方向法求解H权重最近相关系数矩阵问题

由于计算H权重的半正定矩阵锥投影比较困难,目前求解带有H权重的最近相关系数矩阵问题的方法很少且比较复杂.考虑用交替方向法求解该问题,每次迭代只需求解一个有显式解的二次规划问题和一个不带权重的半正定矩阵锥投影,计算简单,易于实现.为提高计算速度,还考虑了改进的交替方向法.此外,通过数值实验对交替方向法与现有方法进行了比较,说明了交替方向法对解决带有H权重的最近相关系数矩阵问题的有效性.     

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

五、无约束二次规划问题的算法在这一章我们将介绍求解二次函数f(x)=p'x+1/2x'Cx在R~n中的最优点的几种算法。研究这个问题除了它本身的需要外,还对于研究一般的无约束非线性规划问题的算法有重要意义。因为无约束的非线性规划问题的不少算法是由二次规划的算法推广而成的。下面介绍的算法都能保证从任意初始点出发,经过有限次迭代运算后到达二次目标函数的最优点,或者能够判断出二次函数无最优点。因此在实用上,这几种算法的效果是很好的。 5.1.转轴方法根据本文定理2.2(见本刊1985年第一期),二次函数f(x)如有极小解,则矩阵C必为半正定矩阵;反之,二次函数f(x)如有极大解,则C必为半负定矩阵。定理2.2还指出,二     

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

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

优化问题的序列线性方程组解法

拟牛顿算法是求解无约束优化问题的有效算法.序列二次规划方法是将拟牛顿算法应用于求解约束优化的推广与发展,它保持了拟牛顿算法的超线性收敛速度而成为约束优化的重要算法类.序列线性方程组方法则是它的进一步发展,目的在于每步求迭代方向dk时避免求解计算量较大的二次子规划.现在序列线性方程组方法仍在研究和发展,目的是简化算法结构、减少计算量,同时保持算法的优良性质.     

带有二次约束的一类特殊三次规划问题的全局最优性充分条件

利用拉格朗目函数和L次微分的方法,研究了带有二次约束的一类特殊三次规划问题的全局最优性条件。首先刻画出该类三次规划问题的拉格朗日函数的抽象次微分,从而得到了带有二次约束的三次规划问题的全局最优性充分条件。最后举例说明如何利用本文所给出的全局最优性充分条件来判定当前可行解就是全局最优解。     

半无限极大极小离散化问题的一个非单调SQCQP算法

针对序列二次规划(SQP)算法在处理结构复杂、 非线性程度较大的半无限极大极小离散化问题时计算效率较低的不足, 提出一种非单调序列二次约束二次规划(SQCQP)算法, 并在适当的条件下证明算法的收敛性. 数值实验结果表明, 在离散水平为100的情形下, 非单调类SQCQP算法在减少迭代次数和计算时间等方面均优于SQP算法.     

一类修正Hager-Zhang共轭梯度法的收敛性及其数值实验

为有效提高求解无约束优化问题的计算效率, 提出一类新的修正Hager-Zhang共轭梯度法, 该算法不依赖线搜索, 具有充分下降性和信赖域性质. 理论研究结果表明, 在常规假设条件下, 新算法不仅在弱Wolfe-Powell线搜索下对一般函数全局收敛, 且对一致凸函数具有R-线性收敛速度. 数值实验结果表明, 新算法比经典Hager-Zhang算法及其两个修正算法性能更优.     

求不定二次规划问题全局解的新的分支定界算法

提出了求解不定二次规划问题一个新的分支定界算法.利用D.C.分解和正定阵的Cholesky分解把问题转化为可分离形式,并导出Lagrangian对偶界,给出基于Lagrangian对偶界和矩形对分的分支定界算法,同时给出初步数值实验结果.     

带有二次约束的一般二次规划问题的松弛分枝定界方法

考虑带有二次约束的一般二次规划问题的求解，当约束条件为非凸二次函数时，对原问题中的某个二次约束进行凸二次松驰，或在原问题的约束条件中增加一个球约束，使得原问题的可行域包含在松驰二次规划问题的可行域内。采用椭球剖分策略剖分可行域为小 椭球，用投影次梯度算法解松驰二次规划问题的拉格朗日对偶问题，从而获得原问题的一个下界。原问题最优值的一个上界可从迭代过程中的可行点得到，并在迭代过程中得到调整。该算法或在原问题最优值的一个上下界相同时终止，得到原问题的整体最优解；或产生一无限序列，其任一聚点都是原问题的整体最优解。     

受扰动双线性离散系统的多目标最优控制

研究了双线性离散系统的多目标最优控制问题,给出了一种基于受扰动系统的两级最优控制算法.两级算法的下级用动态规划求解具有双线性二次型结构的辅助La-grangian 问题,上级通过迭代调整辅助Lagrangian问题中的参数向量,不断重复这个过程,直至从非劣解集中挑出最优解.最后,仿真实例证明了该算法的有效性.     

有界凸域上非凸二次整体规划问题的单纯形剖分算法

把非凸二次规划问题等价地转变成一个带有调整因子u的规划问题 ,特别当调空因子u取得适当大时 ,该问题转变成一个D、C规划问题 ,进而可以通过解凸二次规划来确定原问题整体最优值的下界 由此建立了有界凸域上非凸二次整体规划问题的单纯形剖分算法 ,并对此算法的收敛性进行了分析     

求解最大割问题的分枝定界算法

最大割问题是图论中的一个典型的NP困难问题。文中基于最大割问题的半定规划松弛模型，给出了最大割问题的一种二次规划松弛模型，并且理论证明了提出的二次规划松弛模型要优于半定规划松弛模型。在谈模型的基础上，利用分枝定界算法求解最大割问题。对小规模和中等规模的最大割问题分别作数值实验。实验表明分枝定界算法能够给出最大割问题一个好的近似解，是求解中小规模最大割问题的有效方法。