|
|||||
|
|
| 基于一个新核函数的半定规划的内点算法的复杂性分析 | |
| 引用本文： | 钱忠根,白延琴,王国强.基于一个新核函数的半定规划的内点算法的复杂性分析[J].上海大学学报(英文版),2008,12(5):388-394. |
| 作者姓名： | 钱忠根 白延琴 王国强 |
| 基金项目： | 国家自然科学基金，上海市重点学科建设项目，上海市高校优秀青年教师后备人选科研项目 |
| 摘 要： | Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case. |
| 关 键 词： | 新核函数 半定规划 内点算法 复杂性分析 |
| 收稿时间： | 2006-12-22 |
| 修稿时间： | 2007-03-08 |
Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization |
|
| QIAN Zhong-gen,BAI Yan-qin,WANG Guo-qiang.Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization[J].Journal of Shanghai University(English Edition),2008,12(5):388-394. | |
| Authors: | QIAN Zhong-gen BAI Yan-qin WANG Guo-qiang |
| Institution: | 1. Department of Basic Courses, Jiangsu Teachers University of Technology, Changzhou 213001, P. R. China 2. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China 3. College of Vocational Technology, Shanghai University of Engineering Science, Shanghai 200437, P. R. China |
| Abstract: | Interior-point methods (IPMs) for linear optimization (LO) and semidefinite optimization (SDO) have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods (IPMs) for semidefinite optimization (SDO) is designed. And the iteration complexity of the algorithm as O(n3/4 log n/ε) with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O(n log n/ε) in large-updates case. |
| Keywords: | interior-point algorithm primal-dual method semidefinite optimization (SDO) polynomial complexity |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ | |
| 点击此处可从《上海大学学报(英文版)》浏览原始摘要信息 | |
| 点击此处可从《上海大学学报(英文版)》下载免费的PDF全文 | |