A FEASIBLE ACTIVE SET METHOD FOR STRICTLY CONVEX QUADRATIC PROBLEMS WITH SIMPLE BOUNDS

作者：Hungerlaender P^*; Rendl F

来源：SIAM Journal on Optimization, 2015, 25(3): 1633-1659.

DOI：10.1137/140984439

• primal-dual active set methods
• quadratic programming
• box constraints
• convex programming

A primal-dual active set method for quadratic problems with bound constraints is presented which extends the infeasible active set approach of Kunisch and Rendl [SIAM J. Optim., 14 (2003), pp. 35-52]. Based on a guess of the active set, a primal-dual pair (x, alpha) is computed that satisfies stationarity and the complementary condition. If x is not feasible, the variables connected to the infeasibilities are added to the active set, and a new primal-dual pair (x, alpha) is computed. This process is iterated until a primal feasible solution is generated. Then a new active set is determined based on the feasibility information of the dual variable a. Strict convexity of the quadratic problem is sufficient for the algorithm to stop after a finite number of steps with an optimal solution. Computational experience indicates that this approach also performs well in practice.

• 出版日期2015