论文标题
一个统一的复杂性认证框架，用于凸二次编程的主动设定方法
A Unifying Complexity Certification Framework for Active-Set Methods for Convex Quadratic Programming
论文作者
论文摘要
在模型预测控制（MPC）中，必须在每个时间步骤解决一个优化问题，在实时应用中，这使得有效地解决这些优化问题并在最差的解决方案时间上具有良好的上限很重要。通常，对于线性MPC问题，所讨论的优化问题是一个二次程序（QP），取决于系统状态和参考信号等参数。一个流行的解决此类QP的方法是活动定点方法，其中求解了一系列方程式系统。我们提出了一种用于计算的算法，用于哪种字节算法的子问题序列将解决感兴趣的每个参数。通过了解这些序列，可以确定有效集合算法需要收敛的最终迭代以及最终的最大时间。通过计算确切的最差迭代迭代数量原始和双重活动算法以达到最佳性所需的确切最差的迭代数量，在一组QP上说明了所提出方法的有用性。
In model predictive control (MPC) an optimization problem has to be solved at each time step, which in real-time applications makes it important to solve these optimization problems efficiently and to have good upper bounds on worst-case solution time. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving such QPs is active-set methods, where a sequence of linear systems of equations is solved. We propose an algorithm for computing which sequence of subproblems an active-set algorithm will solve, for every parameter of interest. By knowing these sequences, a worst-case bound on how many iterations, and ultimately the maximum time, the active-set algorithm requires to converge can be determined. The usefulness of the proposed method is illustrated on a set of QPs, originating from MPC problems, by computing the exact worst-case number of iterations primal and dual active-set algorithms require to reach optimality.
