A robust superlinearly convergent algorithm for linearly constrained optimization problems under degeneracy

In this paper, the problem of minimizing a convex function subject to general linear constraints is considered. A new dual simplex procedure with a 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 computational effort 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.