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

来源 :应用数学 | 被引量 : 0次 | 上传用户:xxj8880430
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(√nlog n log (n/ε)).
其他文献
给定数据(xl, yl ), (x2, y2 ),…, (xm, ym ),考虑一般的损失函数ψ(y-f(x))下,当ψ(z)连续及ξ1 = ψ(y1-f(x1)),ξ2 = ψ(y2 - f(x2 )),…,ξm = ψ(ym-f(xm ))是一个负相关序列时,本文研究了样本误差
本文给出并分析了Poisson随机跳测度驱动的带分数Brown运动的随机比例方程半隐式Euler法的数值解,在局部Lipschitz条件下,证明了在均方意义下半隐式Euler数值解收敛到精确解.
讨论均衡约束最优化问题,利用一个互补函数和扰动技术将原问题转换为非线性等式约束最优化问题,然后利用共轭梯度投影算法的思想,给出了问题的一个求解算法,在适当的条件下,证明了
本文讨论了出现在双色谱中的非线性双曲型守恒律组的如下Cauchy问题{ut+(u/1+u+v)x=0,vt+(v/1+u+v)x=0,初值为u(x,0)=u0(x),v(x,0)=v0(x)的整体光滑解的存在性和唯一性.分析过程基于对角化方法
本文把多步修正特征线法,MMOCAA差分方法及ENO插值相结合,提出了求解对流扩散方程的多步ENO-MMOCAA差分方法.该方法关于时间及空间都具有二阶以上的精度且可避免在解的大梯度附
本文研究基于输出反馈的一类大型互联非线性不确定系统的分散H∞控制问题,通过构造每个子系统收敛的状态观测器,得到分散输出反馈控制器.当反馈控制律作用于该系统时,无扰动输入
本文通过构造新型的Lyapunov-Krasosvskii函数并利用矩阵不等式技巧获得了一类变时滞中立型BAM神经网络的全局稳定性判据,该判据便于应用.数值例子表明,与已有结果相比,该判据具
对于曲边区域上二阶椭圆型问题,本文研究四边形等参有限元逼近格式的收敛性.为了便于单元刚度矩阵和荷载向量的计算,构造几种简单的数值积分格式,并提出一个仅有两个积分点的
令Cα为由在实轴R上连续且满足f(t)exp(-α(t))→0的函数f组成的Banach空间,其中α(t)为非负连续函数.在本文中,我们得到缺项的多项式在Cα中不完备的充分条件.本文的要点在于我们不
对于含约束不等式的最优化问题给出了一种双参数罚函数形式,在文[7]的拟牛顿算法的基础上提出了一个同时改变双参数罚函数的新算法,研究了它的收敛性,数值实验表明了该算法是有