凸二次半定规划一个新的原始对偶路径跟踪算法

本文提出求解凸二次半定规划的一个新的原始对偶路径跟踪算法.在每次迭代中,通过求解一个线性方程组产生搜索方向.在一定条件下证明算法产生的迭代点列落在中心路径的邻域内,且算法至多经■次迭代可得到一个ε-最优解.     

二次半定规划的原始对偶内点算法的H..K..M搜索方向的存在唯一性

主要是将半定规划(Semidefinite Programming,简称SDP)的内点算法推广到二次半定规划(Quadratic Semidefinite Programming,简称QSDP),重点讨论了其中搜索方向的产生方法.首先利用Wolfe对偶理论推导得到了求解二次半定规划的非线性方程组,利用牛顿法求解该方程组,得到了求解QSDP的内点算法的H..K..M搜索方向,接着证明了该搜索方向的存在唯一性,最后给出了搜索方向的具体计算方法.     

一类二次半定规划内点算法的搜索方向

利用牛顿法求解一类二次半定规划的扰动KKT方程组,得出这类二次半定规划原始-对偶路径跟踪算法搜索方向求解的统一形式,以及HKM搜索方向和NT搜索方向存在唯一的充分条件,最后给出了计算搜索方向的表达式,和特殊情况下搜索方向的计算方法.     

解半定规划的二次摄动方法

半定规划在系统论,控制论,组合优化,和特征值优化等领域有着广泛的应用。本文将半定规划摄动成二次半定规划,它的唯一解恰为原问题的解,并且对其偶问题等价于一个线性对称的投影方程,可方便地用投影收缩方法求解,从而获得原半定规划问题的解。文章给出了算法及其收敛性分析,数值试验结果表明摄动方法是解半定规划的一种有效的方法。     

二次半定规划的增广拉格朗日算法

基于变换X=VV~T,本文将半定规划问题转换为非线性规划问题,提出了解决此问题的增广拉格朗日算法,并证明了算法的线性收敛性.在此算法中,每一次迭代计算的子问题利用最速下降搜索方向和满足wolf条件的线性搜索法求最优解.数值实验表明,此算法是行之有效的,且优于内点算法.     

一种新的求解凸二次规划的原始-对偶多项式内点算法

对凸二次规划问题提出了一种新的原始-对偶路径跟踪算法,算法迭代方向的求解是不同于传统的牛顿法,而是借助于一种新的工具找到搜寻方向.最后证明了算法具有多项式复杂性.     

多目标半定规划的最优性条件及对偶理论

在不变凸的假设下来讨论多目标半定规划的最优性条件、对偶理论以及非凸半定规划的最优性条件．首先给出了非凸半定规划的一个KKT条件成立的充分必要条件, 并利用此定理证明了其最优性必要条件．其次讨论了多目标半定规划的最优性必要条件、充分条件, 并对其建立Wolfe对偶模型, 证明了弱对偶定理和强对偶定理．     

凸二次规划问题逆问题的模型与解法

本文分别考虑带非负约束和不带大量负约束凸二次规划问题逆问题。首先得到各个逆问题的数学模型,然后对不同的模型给出不同的求解方法。     

凸半定规划中关于非奇异性的一个等价条件

本文将给出凸半定规划中关于非奇异性的一个等价条件,它可以看作线性半定规划中非奇异性的等价条件的推广.     

求解凸二次规划问题的一种加权路径跟踪内点算法

基于Darvay提出用加权路径跟踪内点算法解线性规划问题的相关工作,本文致力于将此算法推广于解凸二次规划问题,并证明此算法具有局部二次收敛速度和目前所知的最好的多项式时间算法复杂性.     

一种新的可分凸二次规划的不可行内点算法

本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) .     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

A Non-Interior Path Following Method for Convex Quadratic Programming Problems with Bound Constraints

We propose a non-interior path following algorithm for convex quadratic programming problems with bound constraints based on Chen-Harker-Kanzow-Smale smoothing technique. Conditions are given under which the algorithm is globally convergent or globally linearly convergent. Preliminary numerical experiments indicate that the method is promising.     

A Class of Infeasible Interior Point Algorithms for Convex Quadratic Programming

This article proposes a class of infeasible interior point algorithms for convex quadratic programming, and analyzes its complexity. It is shown that this algorithm has the polynomial complexity. Its best complexity is O(nL).     

多目标半定规划的加权中心路径法

对于线性型多目标半定规划问题，引进加权中心路径的概念，并利用单目标半定规划的中心路径法，提出了求解多目标半定规划问题的加权中心路径法，先得型对一个叔向量的有效解，然后在此基础上，提出了通过一次迭代得到对应一定范围内其他任意权向量的有效解的一步修正方法．     

基于代数等价变换下的凸二次规划不可行内点算法

基于代数等价变换和在KMM算法的框架基础上,在原始-对偶内点方法的牛顿方程里嵌入一种自调节功能.从而对凸二次规划提出了一种新的迭代方向的不可行内点算法,并证明了算法的全局收敛性.     

改进共轭梯度法求解无约束二次凸规划问题

针对共轭梯度法求解无约束二次凸规划时,在构造共轭方向上的局限性,对共轭梯度法进行了改进.给出了构造共轭方向的新方法,利用数学归纳法对新方法进行了证明.同时还给出了改进共轭梯度法在应用时的基本计算过程,并对方法的收敛性进行了证明.通过实例求解,说明了在求解二次无约束凸规划时,该方法相比共轭梯度法具有一定的优势.