An Early Termination Technique for ADMM in Mixed Integer Conic Programming

Yuwen Chen and Paul Goulart

@inproceedings{CG:2022b,
  author = {Chen, Yuwen and Goulart, Paul},
  title = {An Early Termination Technique for ADMM in Mixed Integer Conic Programming},
  booktitle = {2022 European Control Conference (ECC)},
  year = {2022},
  pages = {60-65},
  url = {https://ieeexplore.ieee.org/abstract/document/9838218},
  doi = {10.23919/ECC55457.2022.9838218}
}

The branch-and-bound (B&B) method is a commonly used technique in mixed-integer programming, whose performance is known to improve substantially if early termination methods can be applied to accelerate the pruning of branches. We propose an early termination technique that estimates a lower bound of the objective of current node problem and can stop the computation early instead of solving it to optimality. We show that our proposed technique can be generalized to ADMM-based mixed integer conic programming and speed up convergence in practice.

Burer-Monteiro ADMM for Large-scale Diagonally Constrained SDPs

Yuwen Chen and Paul Goulart

@inproceedings{CG:2022,
  author = {Chen, Yuwen and Goulart, Paul},
  title = {Burer-Monteiro ADMM for Large-scale Diagonally Constrained SDPs},
  booktitle = {2022 European Control Conference (ECC)},
  year = {2022},
  pages = {66-71},
  doi = {10.23919/ECC55457.2022.9838160}
}

We propose a bilinear decomposition for the Burer-Monteiro method for semidefinite programming and combine it with the Alternating Direction Method of Multipli-ers. Bilinear decomposition reduces the degree of the augmented Lagrangian from four to two, which makes each of the sub-problems a quadratic programming and hence computationally efficient. Our approach is able to solve a class of large-scale SDPs with diagonal constraints. We prove that our ADMM algorithm converges globally to the set of first-order stationary points, and show empirically that the algorithm returns a globally optimal solution for diagonally constrained SDPs.

Safeguarded Anderson acceleration for parametric nonexpansive operators

Michael Garstka, Mark Cannon and Paul Goulart

@inproceedings{GCG:2022,
  author = {Garstka, Michael and Cannon, Mark and Goulart, Paul},
  title = {Safeguarded Anderson acceleration for parametric nonexpansive operators},
  booktitle = {2022 European Control Conference (ECC)},
  year = {2022},
  pages = {435-440},
  url = {https://ieeexplore.ieee.org/abstract/document/9838320},
  doi = {10.23919/ECC55457.2022.9838320}
}

This paper describes the design of a safeguarding scheme for Anderson acceleration to improve its practical performance and stability when used for first-order optimisation methods. We show how the combination of a non-expansiveness condition, conditioning constraints, and memory restarts integrate well with solver algorithms that can be represented as fixed point operators with dynamically varying parameters. The performance of the scheme is demonstrated on seven different QP and SDP problem types, including more than 500 problems. The safeguarded Anderson acceleration scheme proposed in this paper is implemented in the open-source ADMM-based conic solver COSMO.

Stochastic output feedback MPC with intermittent observations

Shuhao Yan, Mark Cannon and Paul J. Goulart

@article{YCG:2022,
  author = {Shuhao Yan and Mark Cannon and Paul J. Goulart},
  title = {Stochastic output feedback MPC with intermittent observations},
  journal = {Automatica},
  year = {2022},
  volume = {141},
  pages = {110282},
  url = {https://www.sciencedirect.com/science/article/pii/S0005109822001285},
  doi = {10.1016/j.automatica.2022.110282}
}

This paper designs a model predictive control (MPC) law for constrained linear systems with stochastic additive disturbances and noisy measurements, minimising a discounted cost subject to a discounted expectation constraint. It is assumed that sensor data is lost with a known probability. Taking into account the data losses modelled by a Bernoulli process, we parameterise the predicted control policy as an affine function of future observations and obtain a convex linear-quadratic optimal control problem. Constraint satisfaction and a discounted cost bound are ensured without imposing bounds on the distributions of the disturbance and noise inputs. In addition, the average long-run undiscounted closed loop cost is shown to be finite if the discount factor takes appropriate values. We analyse robustness of the proposed control law with respect to possible uncertainties in the arrival probability of sensor data and we bound the impact of these uncertainties on constraint satisfaction and the discounted cost. Numerical simulations are provided to illustrate these results.