Optimal Parameter Selection for ADMM: Quadratically Constrained Quadratic Program

We propose two new algorithms for solving quadratically constrained quadratic programming (QCQP) problems arising from real-time optimization based control such as model predictive control or interpolating control. The proposed algorithms are based on the Alternating Direction Method of Multipliers (ADMM). ADMM is a powerful tool for solving a wide class of constrained optimization problems. There are two main challenges when applying ADMM: i) its performance depends greatly on the efficiency of solving the sub-optimization problems associated with the ADMM at each iteration; ii) it is not trivial to find the correct penalty parameters. For the first challenge, we provide a way to reformulate the original QCQP problem into a form such that there exist analytical solutions for the sub-optimization problems. Hence, the computational cost per iteration is low. For the second challenge, we provide two procedures to compute systematically the penalty parameters. In the first procedure, a closed-form expression for the optimal constant scalar parameter is derived in terms of the matrix condition number. In the second one, the penalty parameters are adaptively tuned to achieve fast convergence. The results are validated via numerical simulations.