一个求解半正定规划问题的新原始一对偶内点算法

在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用。本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始。对偶内点算法。这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用。我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O（√n log n log n/c）和O（√n log n/ε）,这里n是半正定规划问题的维数。最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性。     

一个解半正定规划问题的基于广义对数障碍函数的原始对偶内点算法

本文对经典对数障碍函数推广,给出了一个广义对数障碍函数.基于这个广义对数障碍函数设计了解半正定规划问题的原始-对偶内点算法.分析了该算法的复杂性,得到了一个理论迭代界,它与已有的基于经典对数障碍函数的算法的理论迭代界一致.同时,并给出了一个数值算例,阐明了函数的参数对算法运行时间的影响.     

一个新的求解半正定规划问题的原始对偶内点算法

选择合适的核函数对设计求解线性规划与半正定规划的原始对偶内点算法以及复杂性分析都十分重要.Bai等针对线性规划提出三种核函数,并给出求解线性规划的大步迭代复杂界,但未给出数值算例验证算法的实际效果(Bai Y Q,Xie W,Zhang J.New parameterized kernel functions for linear optimization.J Global Optim,2012.DOI 10.1007/s10898-012-9934-z).基于这三种核函数设计了新的求解半正定规划问题的原始对内点算法.进一步分析了算法关于大步方法的计算复杂性界,同时通过数值算例验证了算法的有效性和核函数所带参数对计算复杂性的影响.     

基于一个有限罚函数的二阶锥优化的原始-对偶内点算法

本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N~(1/2)log N log N/ε)和O(N~(1/2)log N/ε),其中N为二阶锥的个数．     

求解正定式几何规划的同论内点算法

求解正定式几何规划的同论内点算法张希，张可村（西安交通大学科学计算与应用软件系）ＡＨＯＭＯＴＯＰＹＩＮＴＥＲＩＯＲＡＬＧＯＲＩＴＨＭＦＯＲＰＯＳＹＮＯＭＩＡＬＧＥＯＭＥＴＲＩＣＰＲＯＧＲＡＭＭＩＮＧ￥ＺｈａｎｇＸｉ；ＺｈａｎｇＫｅ－ｃｕｎ（Ｄｅｐｔ．...     

一种基于邻近点算法的变步长原始-对偶算法

本文考虑求解一种源于信号及图像处理问题的鞍点问题.基于邻近点算法的思想,我们对原始-对偶算法进行改进,构造一种对称正定且可变的邻近项矩阵,得到一种新的原始-对偶算法.新算法可以看成一种邻近点算法,因此它的收敛性易于分析,且无需较强的假设条件.初步实验结果表明,当新算法被应用于求解图像去模糊问题时,和其他几种主流的高效算法相比,新算法能得到较高质量的结果,且计算时间也是有竞争力的.     

求解两阶段线性规划的原始-对偶分解算法

本介绍一种求解两阶段线性规划的原始-对偶分解算法。该方法在两方面上明显优于传统分解方法。即具有平衡的分解结构和良好的收敛特性。新分解结构将原问题分解为一对受限制的原始和对偶子问题，每一个子问题都保存有对方以前迭代的所有信息，而在传统的主-子分解结构中。子问题只保留主问题传递来的当前信息。新的迭代机制使两个子问题在迭代过程中始终保持单调改善的收敛特性。在相当一般的条件下，新算法可以在有限次迭代中收敛于预先指定的收敛误差之内。     

一类线性与框式约束凸规划问题的原始-对偶内点算法

本文对一类具有线性和框式约束的凸规划问题给出了一个原始-对偶内点算法, 该算法可在任一原始-对偶可行内点启动, 并且全局收敛,当初始点靠近中心路径时, 算法成为中心路径跟踪算法。 数值实验表明, 算法对求解大型的这类问题是有效的。     

参数最短路的原始-对偶算法

本文利用原始－对偶方法,对于含参数λ的网络（Ｖ,Ｅ,ｆ_１-λｆ_２）,给出了某一点至其它各点的参数最短路的求解算法,其时间复杂度为 Ｏ（ｎｍ＋ｎ~２ｌｏｇｎ）．     

一类框式凸规划的原始-对偶内点算法

本文为框式约束的一类凸规划提出了一个新的内点算法,原始－对偶路径跟踪法,并了政算法的迭代复杂性为多项式时间性。     

Primal-dual Interior-point Algorithms for Second-order Cone Optimization Based on a New Parametric Kernel Function

A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O（√Nlog N log N/ε） for large-update methods and O（√Nlog N/ε） for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.     

A Primal-dual Interior-point Algorithm for Symmetric Cone Convex Quadratic Programming Based on the Commutative Class Directions

Acta Mathematicae Applicatae Sinica, English Series - In this paper, we present a neighborhood following primal-dual interior-point algorithm for solving symmetric cone convex quadratic programming...     

使用自正则度量的凸二次规划的原始对偶内点法的多项式复杂性

最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(n√log n log (n/ε)).     

半定规划问题的一种新的预测-校正算法

本文首先将半定规划转化为一个变分不等式问题,在满足单调性和Lipschitz连续的条件下,提出了一种基于Korpelevich-Khobotv算法的新的预测-校正算法,并给出算法的收敛性分析.     

全局收敛的凸规划的原始—对偶不可行内点算法

本对一类凸规划提出了一个原始-对偶不可行内点算法,并证明了算法的全局收敛性。