凸二次规划的一种宽邻域预估-校正算法

凸二次规划的一种宽邻域预估-校正算法

周意元,张明望*,吕艳丽,赵玉琴

三峡大学理学院, 湖北宜昌 443002

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 张明望

A wide-neighborhood predictor-corrector algorithm for convex quadratic programming

ZHOU Yi-yuan， ZHANG Ming-wang*， LU¨ Yan-li， ZHAO Yu-qin

College of Science, China Three Gorges University, Yichang 443002, Hubei, China

Received:1900-01-01 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: ZHANG Ming-wang

摘要/Abstract

摘要： Zhao对线性规划提出了一种基于邻近度量函数最小值的宽邻域预估-校正算法, 并证明了算法的多项式复杂性。基于他的思路,将此方法拓展到凸二次规划,设计了一种新的基于邻近度量函数最小值的宽邻域预估-校正算法。由于新算法的迭代方向向量Δx,Δs不再满足正交性,因此算法的收敛性分析不同于线性规划的情形,同时也证明了新算法具有已知的最好迭代复杂性Onln(x0)Ts0ε,初步数值实验验证了算法的有效性。

关键词: 凸二次规划, 数值实验, 迭代复杂性, 宽邻域, 预估-校正算法

Abstract: Zhao presented a wide-neighborhood predictor-corrector algorithm for linear programming via the least values of proximity measure functions, and he also proved the algorithm has the polynomial iteration complexity. Zhao′s algorithm was extended to convex quadratic programming and a new wide-neighborhood predictor-corrector algorithm was presented based on the minimums of proximity measure functions.　Since the new search direction Δx and Δs are no longer orthogonal, the convergence analysis is different from that of the linear programming. The new algorithm has been proved to retain the sofar best known iteration complexity of Onln(x0)Ts0ε iterations. Moreover, a rough numerical experiment shows the feasibility and efficiency of this new algorithm.

Key words: numerical experiment, iteration complexity, wide-neighborhood, predictor-corrector algorithm, convex quadratic programming

中图分类号:

O221

周意元,张明望*,吕艳丽,赵玉琴 . 凸二次规划的一种宽邻域预估-校正算法[J]. J4, 2008, 43(9): 73-80 .

ZHOU Yi-yuan,ZHANG Ming-wang*,LU¨ Yan-li,ZHAO Yu-qin . A wide-neighborhood predictor-corrector algorithm for convex quadratic programming[J]. J4, 2008, 43(9): 73-80 .

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	丁凤霞,程浩. 椭圆方程柯西问题磨光正则化参数的后验选取[J]. 山东大学学报（理学版）, 2018, 53(2): 18-24.
[2]	胡强,张明望*,李卫滑. 求解凸二次规划的一种二阶Mehrotra型预估-校正算法[J]. J4, 2011, 46(2): 89-96.
[3]	陆瑶1,李德生2,杨洋1. 非线性SchrÖdinger方程的Fourier谱逼近[J]. J4, 2011, 46(1): 119-126.
[4]	. 线性规划的宽邻域预估校正算法[J]. J4, 2009, 44(7): 66-70.