位置：成果数据库 > 期刊 > 期刊详情页
半定规划的齐次不可行内点算法
  • ISSN号：2095-6134
  • 期刊名称：《中国科学院大学学报》
  • 时间：0
  • 分类：O221.1[理学—运筹学与控制论;理学—数学]
  • 作者机构：[1]西安电子科技大学数学与统计学院,西安710126, [2]兰州理工大学理学院,兰州730050
  • 相关基金：国家自然科学基金（61072144,61179040）和中央高校基本科研业务费专项基金（K50513100007）资助
作者： 吴岳[1], 刘红卫[1], 谢迪[2]
关键词： 齐次不可行内点算法, 单调互补问题, 半定规划, homogeneous infeasible-starting interior-point algorithm, monotone complementarityproblem, semidefinite programming
中文摘要：

为降低半定规划（SDP）问题的迭代复杂度,并且有更好的数值实验结果,提出一种新的宽邻域上的齐次不可行内点算法.半定规划的KKT条件是单调互补问题（MCP）,通过构造齐次模型（HMCP）以及提出新的宽邻域来解这个齐次模型,得到半定规划问题的最优解.这种算法容易判定原问题是否可行.在NT方向,证明迭代点在新的宽邻域内是收敛的,且迭代复杂度为O（√nlog L）,其中n是SDP问题的维数,L=Tr（X^0S^0）/ε,其中ε是需要的精度,（X0,S0）是迭代起始点.这个复杂度比一般的半定规划不可行算法的迭代复杂度低.提供了数值实验,证明此算法比其他不可行算法具有更好的数值实验结果.

英文摘要：

We propose a homogeneous infeasible-interior-point algorithm for semidefinite programming（SDP） in a new wide neighborhood in order to achieve low iteration complexity and get better experiement numerical results. Complementarity problem （MCP） is the KKT condition of SDP. We sovle MCP by constructing a homogeneous MCP model （HMCP） and proposing a new wide neighborhood. Then we derive the optimal solution of SDP. This algorithm can be easily used to determine whether SDP is feasible or not. At the direction of NT, we prove that the iteration poin is convergent in new wide neighborhood and the iteration complexity is O（√nlog L） , where n is the dimension of SDP andL=Tr（X^0S^0）/εwith 6 being the required precision and （X^0 ,S^0） the initial point. This algorithm has lower complexity degree than other algorithms for SDP. The numerical experiment is provided. We have proved that this algorithm is better than other infeasible-interiorpoint algorithms in numerical experimentel results.

同期刊论文项目
非负矩阵分解的模型选择与算法研究
期刊论文 44 会议论文 1
基于矩阵低秩近似的大规模核/度量学习研究
期刊论文 39 会议论文 3
同项目期刊论文
A feasible decomposition method for constrained equations and its application to complementarity pro
具有O(n～(1/2)L)复杂性的Mehrotra型预估-矫正算法
随机P矩阵和随机P_0矩阵线性互补问题
一种基于L_1稀疏正则化和非负矩阵分解的盲源信号分离新算法
Nonnegative matrix factorization with bounded total variational regularization for face recognition
Convergence of a non-interior smoothing method for variational inequality problems
A nonmonotone derivative-free algorithm for nonlinear complementarity problems based on the new gene
Rank-two residue iteration method for nonnegative matrix factorization
求解最小体积轴向椭球问题的线性收敛算法
求解MEB问题的一种SMO-型方法
求解特定线性互补问题的牛顿KKT内点法
New reformulation and feasible semismooth Newton method for a class of stochastic linear complementa
Non-monotone projection gradient method for non-negative matrix factorization
求解互补问题的一族非单调光滑牛顿法
A new second-order corrector interior-point algorithm for semidefinite programming
An O(root nL) iteration primal-dual second-order corrector algorithm for linear programming
Solving equations via the trust region and its application to a class of stochastic linear complemen
基于改进的SVM学习算法及其在信用评分中的应用
New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programmin
绝对值方程的一种新的半光滑牛顿法(英文)
对称锥规划的邻域跟踪算法
基于LBFGS的求解最小闭包球的光滑化方法
A New Wide Neighborhood Primal-Dual Infeasible-Interior-Point Method for Symmetric Cone Programming
Solving non-negative matrix factorization by alternating least squares with a modified strategy
Modified subspace Barzilai-Borwein gradient method for non-negative matrix factorization
Partial projected Newton method for a class of stochastic linear complementarity problems
New smoothing SVM algorithm with tight error bound and efficient reduced techniques
求解随机线性互补问题的半光滑投影牛顿算法
线性规划基于修正牛顿方向的宽邻域内点算法
弧搜索内点算法
一类Armijo搜索下的混合HS-PRP共轭梯度法
P_＊（κ）线性互补问题的预估-校正内点算法
半定锥上具有O（√nL）复杂性的Mehrotra型预估矫正算法
求解最小闭包球问题改进的SMO-型算法
一种基于L1稀疏正则化和非负矩阵分解的盲源信号分离新算法
Mehrotra-type predictor-corrector algorithms for sufficient linear complementarity problem
新的软间隔AdaBoost弱分类器权重调整算法
Rank-two update algorithms for the minimum volume enclosing ellipsoid problem
Which is better? Regularization in RKHS vs R^ m on Reduced SVMs
Polynomial convergence of Mehrotra-type prediction-corrector infeasible-IPM for symmetric optimizati
Trust-region method for box-constrained semismooth equations and its applications to complementary p
矩阵补全算法研究进展
Kernelization of matrix updates, when and how?
多线性鲁棒主成分分析
Quadratic regularization projected BarzilaiBorwein method for nonnegative matrix factorization
Multilinear robust principal component analysis
一种用于人脸识别的非迭代GLRAM算法
A Mehrotra-type predictor–corrector infeasible-interior-point method with a new one-norm neighborhoo
An efficient monotone projected Barzilai-Borwein method for nonnegative matrix factorization
基于Cholesky分解的K2DPCA人脸识别研究
Polynomial Convergence of Second-Order Mehrotra-Type Predictor-Corrector Algorithms over Symmetric C
INFEASIBLE MEHROTRA-TYPE PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR THE CARTESIAN P-* (kappa)-
A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-de
带有新的迭代格式的内点算法
求解互补问题的一族非单调光滑牛顿法
Polynomial convergence of Mehrotra-type predictor–corrector algorithm for the Cartesian P*(k)-LCP ov
求解随机线性互补问题的半光滑投影牛顿算法
线性规划基于修正牛顿方向的宽邻域内点算法
弧搜索内点算法
低秩矩阵恢复算法综述
期刊信息
  • 《中国科学院大学学报》
  • 中国科技核心期刊
  • 主管单位:中国科学院
  • 主办单位:中国科学院大学
  • 主编：石耀霖
  • 地址：北京玉泉路19号(甲)
  • 邮编：100049
  • 邮箱：journal@gucas.ac.cn
  • 电话：010-88256013
  • 国际标准刊号：ISSN：2095-6134
  • 国内统一刊号：ISSN：10-1131/N
  • 邮发代号:82-583
  • 获奖情况:
  • 国内外数据库收录:
  • 中国中国科技核心期刊,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）
  • 被引量:416