A ROBUST SUPERLINEARLY CONVERGENT ALGORITHM FOR LINEARLY CONSTRAINED OPTIMIZATION PROBLEMS UNDER DEGENERACY  

作　　者：曾庆光 贺国平 吴方 

出　　处：《Acta Mathematicae Applicatae Sinica》1998年第4期363-373,共11页应用数学学报（英文版）

摘　　要：In this paper, the problem of minimizing a convex function subject to general linear constraints is considered. An algorithm which is an extension of the method described in [4] is presented. And a new dual simplex procedure with lexicographic scheme is proposed to deal with the degenerative case in the sense that the gradients of active constraints at the iteration point are dependent. Unlike other methods, the new algorithm possesses the following important property that, at any iteration point generated by the algorithm, one can choose a set of the most suitable basis and from it one can drop all constraints which can be relaxed, not only one constraint once. This property will be helpful in decreasing the computation amount of the algorithm. The global convergence and superlinear convergence of this algorithm are proved,without any assumption of linear independence of the gradients of active constraints.In this paper, the problem of minimizing a convex function subject to general linear constraints is considered. An algorithm which is an extension of the method described in [4] is presented. And a new dual simplex procedure with lexicographic scheme is proposed to deal with the degenerative case in the sense that the gradients of active constraints at the iteration point are dependent. Unlike other methods, the new algorithm possesses the following important property that, at any iteration point generated by the algorithm, one can choose a set of the most suitable basis and from it one can drop all constraints which can be relaxed, not only one constraint once. This property will be helpful in decreasing the computation amount of the algorithm. The global convergence and superlinear convergence of this algorithm are proved,without any assumption of linear independence of the gradients of active constraints.

关 键 词：Linearly constrained optimization problem DEGENERACY dual simplex method superlinear convergence 

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