| 求解凸二次规划的一种二阶Mehrotra型预估一校正算法 |
| |
| 引用本文： | 胡强,张明望,李卫滑.求解凸二次规划的一种二阶Mehrotra型预估一校正算法[J].山东大学学报(自然科学版),2011(2):89-96,100. |
| |
| 作者姓名： | 胡强 张明望 李卫滑 |
| |
| 作者单位： | 三峡大学理学院,湖北宜昌443002 |
| |
| 基金项目： | 湖北省自然科学基金资助项目（2008CDZ047） |
| |
| 摘 要： | 给出了求解凸二次规划的一种二阶Mehrotra型预估一校正算法。该算法受Salahi等人对线性规划提出的相应算法启发，引入了安全步策略，保证了校正步步长有适当下界，从而具有多项式复杂性。由于算法迭代方向不正交，算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后，通过一些新的技术性引理，证明了算法在最坏情况下的迭代复杂性为O（n^3/2log（x^0）^TS^0/ε）.
|
| 关 键 词： | 凸二次规划 预估一校正算法 内点算法 二阶Mehrotra型算法 多项式复杂性 |
A second-order Mehrotra-type predictor-corrector algorithm for solving convex quadratic programming |
| |
| HU Qiang,ZHANG Ming-wang,LI Wei-hua.A second-order Mehrotra-type predictor-corrector algorithm for solving convex quadratic programming[J].Journal of Shandong University(Natural Science Edition),2011(2):89-96,100. |
| |
| Authors: | HU Qiang ZHANG Ming-wang LI Wei-hua |
| |
| Institution: | (College of Science, China Three Gorges University, Yichang 443002, Hubei, China) |
| |
| Abstract: | A second-order Mehrotra-type predictor-corrector algorithm for solving convex quadratic programming is presented. Based on the work of Salahi et al., a safe strategy is introduced in the algorithm, which guarantees a positive desirable lower bound for the maximum feasible step in the corrector step and subsequently polynomial complexity. Since the search directions of the algorithm are not orthogonal, the way of computing the barrier parameter, as well as the complexity analysis is different from that in the linear case. Finally, through some technical lemmas, it is shown that the iteration complexity of the algorithm is O（n^3/2log（x^0）^TS^0/ε）in the worst case. |
| |
| Keywords: | convex quadratic optimization predictor-corrector methods interior point methods second order Mehrotra-type methods polynomial complexity |
| 本文献已被 维普 等数据库收录！ |
