基于半定规划原始对偶内点法的一种新的核函数

正迄今为止,半定规划问题(SDP)成为了数学规划领域最热门的研究课题之一.半定规划之所以得到越来越多的研究者的关注得益于以下的原因:首先,在Karmarkar的突破性的文章中,他提出了一种有效的处理线性规划问题的多项式算法——内点法(IPM).在这之后,许多的研究者比如Nesterov、Nemirovsky和Todd开始研究和分析如何去利用内     

非线性凸半定规划的割平面算法

先把一般的非线性凸半定规划转化成目标函数是线性函数的非线性凸半定规划,然后用割平面算法求解转化后的半定规划．最后证明了割平面算法的收敛性．     

凸二次规划问题基于核函数的全牛顿步内点算法

针对凸二次规划问题,构造了新的核函数.通过构造的核函数来确定搜索方向和逼近度量,接着给出了求解凸二次规划问题的全牛顿步内点算法,最后给出了算法的复杂性界.     

用于线性优化的基于核函数的动态步长原-对偶内点算法

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.     

用微分代数方法求解半定规划

探讨先用大M法转化原半定规划问题,然后用微分代数方法求解,数值实验结果表明,用微分代数方法求解半定规划是切实可行的。     

一类二次半定规划Gauss-Newton方向的存在唯一性

本文在半定规划中的Gauss-Newton搜索方向的基础上研究一类特殊的二次半定规划(QSDP)求解问题,基于矩阵论和和凸规划理论中原始-对偶算法的NT搜索方向将此类二次半定规划问题转化为求解线性半定规划的最小二乘问题,为了验证此理论的可行性本文验证了Gauss-Newton搜索方向在最小二乘问题中的存在性和唯一性。     

解特殊凸二次半定规划的正则法

本文将利用论文[4]中所讨论的用以解线性半定规划问题的Moreau-Yosida正则法来求解一类特殊的凸二次半定规划问题.进一步,本文还给出了这种方法的全局收敛性分析以及初步的数值试验结果.     

求解广义线性互补问题的一种内点算法

将Yoshise A.提出的求解线性互补问题(LCP)的内点算法进行了推广,由此给出了一种求解广义线性互补问题(GLCP)的内点算法--路径跟踪法.分析了算法对于GLCP的可行性,并在较弱的条件下,证明了该算法具有多项式复杂性.     

宽域不可行内点算法的复杂性

本文讨论求解Ｐ＊（ｋ）阵线性互补问题的宽域不可行内点算法。通过引进辅助系列,给出了算法的迭代方向的上界估计,进而通过使用高阶校正技术,给出了算法的复杂性。     

一类二次约束二次半定规划最优性条件

在Lagrange对偶理论基础上,讨论一类二次约束二次半定规划的对偶规划及其最优性条件,并证明了原规划与对偶规划之间具有零对偶间隙,为利用最优性条件设计算法提供了一个途径。     

一类关于半正定规划的多项式原对偶内点算法

1 Introduction Interior-point methods (IPMs) for semidefinite opti-mization (SDO) have been studied intensively,due totheir polynomial complexity and practical efficiency.In the past decade , SDO has become a popular re-search area in mathematical programming when it be-came clear that the algorithm for linear opti mization(LO) can often be extended to the more general SDOcase. Other two factors are also responsible for thisincreasing interest in SDO. Firstly, SDO has a wideapplication…     

线性约束凸规划的一个新原-对偶路径-跟踪内点算法

In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization （LCCO） is presented. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, only full-Newton steps are used. Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O（√nlog n/ε）.     

凸二次规划的一个新原-对偶内点算法

In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization (CQO) based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method (IPM) to O (√nlognlogn/ε), which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.     

一种新的求解P＊（k）阵原始一对偶路径跟踪算法

对P＊（k）阵线性互补问题提出了一种新的原始一对偶路径跟踪算法,算法是基于一种新的工具找到搜寻方向和中心路径邻域,并证明了此算法的迭代复杂性为O（√n log [n＋4（1＋k）δ2/ε] μ0）,与目前最好的算法迭代复杂性一致。     

Primal-dual interior-point algorithms with dynamic step-size based on kernel functions for linear programming

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming (LP) problems. The algorithms are based on a few kernel functions, including both self-regular functions and non-self-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynamic step size are more efficient than those with fixed step size. Project supported by Dutch Organization for Scientific Research (Grant No.613.000.010)     

A predictor-corrector interior-point algorithm for monotone variational inequality problems

Mehrotra's recent suggestion of a predictor-corrector variant of primal-dual interior-point method for linear programming is currently the interior-point method of choice for linear programming. In this work the authors give a predictor-corrector interior-point algorithm for monotone variational inequality problems. The algorithm was proved to be equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require the initial iteration to be feasible. Numerical results of experiments are presented.