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

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

一般单调变分不等式的近似邻近外梯度算法

近似邻近点算法是求解单调变分不等式的一个有效方法,该算法通过解决一系列强单调子问题,产生近似邻近点序列来逼近变分不等式的解,而外梯度算法则通过每次迭代中增加一个投影来克服一般投影算法限制太强的缺点,但它们均未能改变迭代步骤中不规则闭凸区域上投影难计算的问题.于是,本文结合外梯度算法的迭代格式,构造包含原投影区域的半空间,将投影建立在半空间上,简化了投影的求解过程,并对新的邻近点序列作相应限制,使得改进的算法具有较好的收敛性.     

一种新修正的求解变分不等式的双次梯度外梯度算法

当可行集为一光滑凸函数的下水平集时, 本文提出一种修正的双次梯度外梯度算法(MTSEGA)用于求解Hilbert空间中单调且Lipschitz连续的变分不等式. MTSEGA在每步迭代过程中仅需计算向半空间的两次投影及一次映射的值. 在与已知算法相同的假设条件下, 证明了新算法产生的序列能弱收敛到相关问题的一个解.     

求解变分不等式和不动点问题的公共元的修正次梯度外梯度算法

该文在实Hilbert空间中引入了一类新的求解变分不等式问题的惯性次梯度外梯度算法.在适当的参数假设下,证明了由该算法所产生的序列强收敛于伪单调变分不等式问题的解集与拟非扩张映射不动点集合的公共元素.最后,给出了数值实验来说明所提算法的有效性.该文所得的结果推广和改进了文献中的一些已有结果.     

关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注

Yair Censor,Aviv Gibali和Simeon Reich为求解变分不等式问题提出了 2-次梯度外梯度算法.关于此算法的收敛性,作者给出了部分证明,有一个问题:由算法产生的迭代点列能否收敛到变分不等式问题的一个解上,没有得到解决.此问题作为一个公开问题在文章"Extensions of Korpelevi...     

一种新的求解变分不等式的惯性双次梯度外梯度算法（英文）

当可行集为一光滑凸函数的下水平集时,文献[Optimization,2020,69(6):1237-1253]提出了一种惯性双次梯度外梯度算法来求解Hilbert空间中的单调且Lipschitz连续的变分不等式问题.该算法在每次迭代中仅需向一个半空间计算两次投影,并得到了算法的弱收敛结果.本文通过使用黏性方法以及在惯性步采用新的步长来修正该算法.在适当的假设条件下证明了新算法所生成的序列能强收敛到变分不等式的一个解.此外,新算法在每次迭代中也仅需向半空间计算两次投影.     

非线性半定规划若干进展

讨论非线性半定规划的四个专题,包括半正定矩阵锥的变分分析、非凸半定规划问题的最优性条件、非凸半定规划问题的扰动分析和非凸半定规划问题的增广Lagrange方法．     

非线性半定规划若干进展

讨论非线性半定规划的四个专题, 包括半正定矩阵锥的变分分析、非凸半定规划问题的最优性条件、非凸半定规划问题的扰动分析和非凸半定规划问题的增广Lagrange方法.     

求解非单调变分不等式的一种半空间投影算法

本文提出了一种求解非单调变分不等式的半空间投影算法,在映射是连续和对偶变分不等式解集非空的假设条件下证明了该算法生成的无穷序列是全局收敛的,并在局部误差界和Lipschitz连续条件下给出了收敛率分析.通过数值实验验证了所提出算法的有效性和可行性.     

求解非凸半定规划的一个非线性Lagrange算法及其收敛性分析

本文提出了一个求解非凸半定规划的非线性Lagrange算法,当二阶充分条件以及严格互补条件成立时,证明了这一算法的收敛性定理.收敛结果表明,当惩罚参数小于某个阀值时,算法是局部收敛的;此外,还给出了解的一个依赖于惩罚参数的误差界.     

非凸半定规划的广义Fakars引理及最优性条件

1引言在本文中,我们用(?),S~n,S_ ~n分别表示有限维向量空间,n阶对称矩阵空间及n阶半正定矩阵锥.我们考虑如下形式的非凸半定规划问题:     

ON SOME PROPERTIES OF SOLUTIONS TO SEMIDEFINITE PROGRAMMING

It is well known that for symmetric linear programming there exists a strictly complementary solution if the primal and the dual problems are both feasible. However, this is not necessary true for symmetric or general semide finite programming even if both the primal problem and its dual problem are strictly feasible. Some other properties are also concerned.     

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

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

求解一类广义线性规划的分裂算法

1　引　　言我们知道,描述常义线性规划问题的数学模型为:mincTxs.tAx=bx≥0　　在经济问题中,线性规划中的向量c往往表示为价格,而在许多实际规划问题中价格向量c往往会在一定范围内扰动.这时,我们可以考虑这样一类广义线性规划问题:minx{maxy∈YyTx}s.tAx=b　x∈X(1)其中,A∈Rm×n,b∈Rm,X={x∈Rn|x≥0},Y是Rn中的一个凸闭子集.有关广义线性规划问题的求解,何在文献[1]中作过一些讨论.我们通过对线性约束Ax=b引入乘子可得到广义线性规划问题(1)定义在X×Y×Rm上的Lagrange函数为:L(x,y,η)=yTx-ηT(Ax-b)(2)　　如果x*是(1)式的…     

关于单调变分不等式的不精确邻近点算法的收敛性分析

We consider a proximal point algorithm(PPA) for solving monotone variational inequalities. PPA generates a sequence by solving a sequence of strongly monotone subproblems .However,solving the subproblems is either expensive or impossible. Some inexact proximal point algorithms(IPPA) have been developed in many literatures. In this paper, we present a criterion for approximately solving subproblems. It only needs one simple additional work on the basis of original algorithm, and the convergence criterion becomes milder. We show that this method converges globally under new criterion provided that the solution set of the problem is nonempty.     

一个求解线性规划的单纯形-内点算法

根据单纯形方法和大步长路径跟踪算法（Ｈｅｒｔｏｇ，Ｒｏｏｓ和Ｔｅｒｌａｋｙ１９９１），对于具有不等式约束的线性规划问题，引进了一个具有组合特性的内点算法．该方法保留了单纯形方法和内点算法的优点，克服了它们的不足，在任何情况下，这个方法都能快速收敛．数值结果也很好地验证了这个结论．     

一类凸规划的多项式预估校正内点法

1、引言 1990年由Mehrotra对线性规划问题提出了一个称为预估校正的方法,并在1992年给出了其数值算法．1993年Mizuno,Todd和Y．Ye．给出了改进的预估校正内点法,使得一个预估步后只跟一个校正步．1994年F．A．Potra给出了不可行预估校正内点法,使得可以从一个不可行的初始点开始算法的迭代,并证明了其为二次收敛．     

A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O(n~(1/2)L) iteration complexity which is the best result for convex quadratic programming so far.     

A FAST SIMPLEX ALGORITHM FOR LINEAR PROGRAMMING

Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule, the steepest-edge rule and Devex rule. Our computational experiments show that the simplex algorithm using a combination of these rules turned out to be even more efficient.