Active-set (AS) methods for quadratic programming (QP) are particularly suitable for real-time optimization, as they provide a high-quality solution in a finite number of iterations. However, they add or remove one constraint at each iteration, which makes them inefficient when the number of constraints and variables grows. Block principal pivoting (BPP) methods perform instead multiple changes in the working set in a single iteration, resulting in a much faster execution time. The infeasible primal–dual method proposed by Kunisch and Rendl (KR) (Kunisch and Rendl, 2003) is a BPP method for box-constrained QP that is particularly attractive when reducing the time for finding an accurate solution is crucial, such as in linear model predictive control (MPC) applications. However, the method is guaranteed to converge only under very restrictive sufficient conditions, and tight bounds on the worst-case complexity are not available. For a given set of box-constrained QP’s that depend on a vector of parameters, such as those that arise in linear MPC, this paper proposes an algorithm that computes offline the exact number of iterations and flops needed by the KR method in the worst-case, and the region of the parameter space for which the method converges or is proved to cycle.

Complexity and Convergence Certification of a Block Principal Pivoting Method for Box-Constrained Quadratic Programs

G. Cimini;A. Bemporad
2019-01-01

Abstract

Active-set (AS) methods for quadratic programming (QP) are particularly suitable for real-time optimization, as they provide a high-quality solution in a finite number of iterations. However, they add or remove one constraint at each iteration, which makes them inefficient when the number of constraints and variables grows. Block principal pivoting (BPP) methods perform instead multiple changes in the working set in a single iteration, resulting in a much faster execution time. The infeasible primal–dual method proposed by Kunisch and Rendl (KR) (Kunisch and Rendl, 2003) is a BPP method for box-constrained QP that is particularly attractive when reducing the time for finding an accurate solution is crucial, such as in linear model predictive control (MPC) applications. However, the method is guaranteed to converge only under very restrictive sufficient conditions, and tight bounds on the worst-case complexity are not available. For a given set of box-constrained QP’s that depend on a vector of parameters, such as those that arise in linear MPC, this paper proposes an algorithm that computes offline the exact number of iterations and flops needed by the KR method in the worst-case, and the region of the parameter space for which the method converges or is proved to cycle.
2019
Quadratic programming; Active-set methods; Block principal pivoting methods; Linear model predictive control; Complexity certification
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0005109818305247-main.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Nessuna licenza
Dimensione 795.77 kB
Formato Adobe PDF
795.77 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11771/13269
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
social impact