求解高维凸二次规划的向量锥方法

本文介绍一种求解高维凸二次规划的可行方向方法．该方法的可行下降方向是由ε有效广义约束向量所张成的锥构造的，它可通过求解一个低维的线性规划得到．最优步长可由简单的公式给出，不必进行精确的线性搜索。只要在最优点处的有效约束数少于４０个，采用本文方法求解高维凸二次规划就具有计算量少，机时节省的优点．对文中给定的算例，向量锥方法比Ｌｅｍｋｅ 互补旋转法，Ｗｏｌｆｅ既约梯度法和Ｗｏｌｆｅ方法节省机时约７０－８０％．

THE VECTOR-CONE METHOD FOR SOLVING THE HIGH-DIMENSIONAL CONVEX QUADRATIC PROGRAMMING

This paper introduces a feasible direction method for solving the high-dimen- sional convex quadratic programming. In this method, the feasible descent direction is formed of the cone spanned by the vectors that correspond to the generalized active epsilon-constraints and is obtained by solving a low-dimensional linear programming. The optimal step length .is given by a simple formula, so it does not perform exact line searches. If the number of the active constraints at the optimum is less than forty, by using the method of this paper, the amount of computation will be reduced and the machine time can be saved for solving the high-dimensional convex quadratic. programming. In the given example of this paper, vector-cone method saved machine time by about seventy to eighty per cent as compared with Lemke's complementary pivoting algorithm ,Wolfe's gradient algorithm and Wolfe's algorithm