论文标题
用标准单纯限制解决二次程序的梯度投影
Gradient Projection for Solving Quadratic Programs with Standard Simplex Constraints
论文作者
论文摘要
优化标准单纯函数的一种重要方法是活动集算法，该算法需要将函数的梯度投射到超平面上，并在单纯X边界的变量上具有符号约束。我们提出了一种新算法，以有效地为此目的投射梯度。此外，我们将提出的梯度投影方法应用于具有标准单纯限制的二次程序（QP），其中梯度投影用于探索可行的区域，并且当我们认为确定最佳的活动集合时，我们将其切换到受约束的共轭梯度加速融合。具体而言，使用两个不同的梯度投影方向来探索单纯形，即投影梯度和减少梯度。我们根据方向之间的角度选择两个方向之一。此外，我们提出了两个条件，以猜测最佳的活动启发。第一个条件是在许多迭代中工作集保持不变，第二个条件是投影梯度和还原梯度之间的角度足够小。基于这些策略，提出了一种新的主动集算法，用于解决标准单纯形的二次程序。
An important method to optimize a function on standard simplex is the active set algorithm, which requires the gradient of the function to be projected onto a hyperplane, with sign constraints on the variables that lie in the boundary of the simplex. We propose a new algorithm to efficiently project the gradient for this purpose. Furthermore, we apply the proposed gradient projection method to quadratic programs (QP) with standard simplex constraints, where gradient projection is used to explore the feasible region and, when we believe the optimal active set is identified, we switch to constrained conjugate gradient to accelerate convergence. Specifically, two different directions of gradient projection are used to explore the simplex, namely, the projected gradient and the reduced gradient. We choose one of the two directions according to the angle between the directions. Moreover, we propose two conditions for guessing the optimal active set heuristically. The first condition is that the working set remains unchanged for many iterations, and the second condition is that the angle between the projected gradient and the reduced gradient is small enough. Based on these strategies, a new active set algorithm for solving quadratic programs on standard simplex is proposed.
