A STABLE AND EFFICIENT METHOD FOR SOLVING A CONVEX QUADRATIC PROGRAM WITH APPLICATION TO OPTIMAL CONTROL

作者：Shahzad Amir^*; Kerrigan Eric C; Constantinides George A

来源：SIAM Journal on Optimization, 2012, 22(4): 1369-1393.

DOI：10.1137/11082960X

• interior point methods
• quadratic programming
• ill-conditioning
• large-scale problems
• inexact methods
• iterative methods
• predictive control

A method is proposed for reducing the cost of computing search directions in an interior point method for a quadratic program. The KKT system is partitioned and modified, based on the ratios of the slack variables and dual variables associated with the inequality constraints, to produce a smaller, approximate linear system. Analytical and numerical results are included that suggest the distribution of eigenvalues of the new, approximate system matrix is improved, which makes it more amenable to being solved with an iterative linear solver. For this purpose, new preconditioners are also presented to allow iterative methods, such as MINRES, to be used. Numerical results indicate that the computational complexity of the proposed method scales well when applied to a finite horizon discrete-time optimal control problem with linear dynamics, quadratic cost, and linear inequality constraints, which arises in model predictive control applications.

• 出版日期2012