一种改进的求解含等式约束凸二次规划问题的Lemke算法  

An Improved Lemke Algorithm for Convex Quadratic Programming With Equality Constraints

作　　者：张斌[1] 华中生[1] 

机构地区：[1]中国科学技术大学商学院,安徽合肥230026

出　　处：《中国科学技术大学学报》2004年第6期668-677,共10页JUSTC

基　　金：国家自然科学基金资助项目(70172041);安徽省自然科学基金资助项目(03042308)

摘　　要：通过对经典的Lemke互补转轴算法求解含有等式约束的凸二次规划问题的分析,发现所得到的线性互补问题(LCP)可能是退化的.由Lemke算法求解(LCP)问题的迭代过程,通过六个命题说明了含有等式约束的凸二次规划问题对应的(LCP)问题退化的原因,并对经典的Lemke算法的迭代过程进行修正,提出了一种改进的Lemke算法,这种算法能有效地搜索到含等式约束凸二次规划问题的最优解.Through analyzing the process of solving convex quadratic programming with equality constraints by classical Lemke pivot algorithm,we found that the corresponding linear complementarity problem (LCP) may be degenerate.By analyzing the iteration process of Lemke algorithm and proving six propositions,we illustrated the reason why (LCP) is degenerate,amended the iteration process of Lemke algorithm and proposed an improved Lemke algorithm,by which the optimal solution to convex quadratic programming with equality constraints can be obtained effectively.

关 键 词：凸二次规划 等式约束 线性互补问题 Lemke法 

分 类 号：O224[理学—运筹学与控制论]