248 research outputs found
Nonlinear Forward-Backward Splitting with Momentum Correction
No full textThe nonlinear, or warped, resolvent recently explored by Giselsson and
B\`ui-Combettes has been used to model a large set of existing and new monotone
inclusion algorithms. To establish convergent algorithms based on these
resolvents, corrective projection steps are utilized in both works. We present
a different way of ensuring convergence by means of a nonlinear momentum term,
which in many cases leads to cheaper per-iteration cost. The expressiveness of
our method is demonstrated by deriving a wide range of special cases. These
cases cover and expand on the forward-reflected-backward method of
Malitsky-Tam, the primal-dual methods of V\~u-Condat and Chambolle-Pock, and
the forward-reflected-Douglas-Rachford method of Ryu-V\~u. A new primal-dual
method that uses an extra resolvent step is also presented as well as a general
approach for adding momentum to any special case of our nonlinear
forward-backward method, in particular all the algorithms listed above
Nonlinear Forward-Backward Splitting with Momentum Correction
No full textThe nonlinear, or warped, resolvent recently explored by Giselsson and Bùi-Combettes has been used to model a large set of existing and new monotone inclusion algorithms. To establish convergent algorithms based on these resolvents, corrective projection steps are utilized in both works. We present a different way of ensuring convergence by means of a nonlinear momentum term, which in many cases leads to cheaper per-iteration cost. The expressiveness of our method is demonstrated by deriving a wide range of special cases. These cases cover and expand on the forward-reflected-backward method of Malitsky-Tam, the primal-dual methods of Vũ-Condat and Chambolle-Pock, and the forward-reflected-Douglas-Rachford method of Ryu-Vũ. A new primal-dual method that uses an extra resolvent step is also presented as well as a general approach for adding momentum to any special case of our nonlinear forward-backward method, in particular all the algorithms listed above
Execution time certification for gradient-based optimization in model predictive control
No full textWe consider model predictive control (MPC) problems with linear dynamics, polytopic constraints, and quadratic objective. The resulting optimization problem is solved by applying an accelerated gradient method to the dual problem. The focus of this paper is to provide bounds on the number of iterations needed in the algorithm to guarantee a prespecified accuracy of the dual function value and the primal variables as well as guaranteeing a prespecified maximal constraint violation. The provided numerical example shows that the iteration bounds are tight enough to be useful in an inverted pendulum application
Large-Scale and Distributed Optimization
No full textThis book presents tools and methods for large-scale and distributed optimization. Since many methods in "Big Data" fields rely on solving large-scale optimization problems, often in distributed fashion, this topic has over the last decade emerged to become very important. As well as specific coverage of this active research field, the book serves as a powerful source of information for practitioners as well as theoreticians. Large-Scale and Distributed Optimization is a unique combination of contributions from leading experts in the field, who were speakers at the LCCC Focus Period on Large-Scale and Distributed Optimization, held in Lund, 14th–16th June 2017. A source of information and innovative ideas for current and future research, this book will appeal to researchers, academics, and students who are interested in large-scale optimization
Adaptive Nonlinear Model Predictive Control with Suboptimality and Stability Guarantees
No full textTheory for Adaptive Nonlinear Model Predictive Control is developed based on the relaxed dynamic programming inequality. The adaptivity in the controller lies in the choice of control horizon. The control horizon is chosen such that a variation of the relaxed dynamic programming inequality holds for all time steps along the closed loop trajectory. This provides guarantees for asymptotic stability and closed loop suboptimality above a certain pre-specified level
Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM
No full textDouglas-Rachford splitting and the alternating direction method of multipliers (ADMM) can be used to solve convex optimization problems that consist of a sum of two functions. Convergence rate estimates for these algorithms have received much attention lately. In particular, linear convergence rates have been shown by several authors under various assumptions. One such set of assumptions is strong convexity and smoothness of one of the functions in the minimization problem. The authors recently provided a linear convergence rate bound for such problems. In this paper, we show that this rate bound is tight for the class of problems under consideration
Tight global linear convergence rate bounds for Douglas–Rachford splitting
No full textRecently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive
Optimal preconditioning and iteration complexity bounds for gradient-based optimization in model predictive control
No full textIn this paper, optimization problems arising in model predictive control (MPC) and in distributed MPC aresolved by applying a fast gradient method to the dual of the MPC optimization problem. Although the development of fast gradient methods has improved the convergence rate of gradient-based methods considerably, they are still sensitive to ill-conditioning of the problem data. Since similar optimization problems are solved several times in the MPC controller, the optimization data can be preconditioned offline to improve the convergence rate of the fast gradient method online. A natural approach to precondition the dual problem is to minimize the condition number of the Hessian matrix. However, in MPC the Hessian matrix usually becomes positive semi-definite only, i.e., the condition number is infinite and cannot be minimized. In this paper, we show how to optimally precondition the optimization data by solving a semidefinite program, where optimally refers to the preconditioning that minimizes an explicit iteration complexity bound. Although the iteration bounds can be crude, numerical examples show that the preconditioning can significantly reduce the number of iterations needed to achieve a prespecified accuracy of the solution
A generalized distributed accelerated gradient method for distributed model predictive control with iteration complexity bounds
No full textMost distributed optimization methods used for distributed model predictive control (DMPC) are gradient based. Gradient based optimization algorithms are known to have iterations of low complexity. However, the number of iterations needed to achieve satisfactory accuracy might be significant. This is not a desirable characteristic for distributed optimization in distributed model predictive control. Rather, the number of iterations should be kept low to reduce communication requirements, while the complexity within an iteration can be significant. By incorporating Hessian information in a distributed accelerated gradient method in a well-defined manner, we are able to significantly reduce the number of iterations needed to achieve satisfactory accuracy in the solutions, compared to distributed methods that are strictly gradient-based. Further, we provide convergence rate results and iteration complexity bounds for the developed algorithm
- …
