| 1. |
|
|
| 2. |
- Berglund, Erik, 1993-
(författare)
-
Novel Hessian approximations in optimization algorithms
- 2022
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- There are several benefits of taking the Hessian of the objective function into account when designing optimization algorithms. Compared to using strictly gradient-based algorithms, Hessian-based algorithms usually require fewer iterations to converge. They are generally less sensitive to tuning of parameters and can better handle ill-conditioned problems. Yet, they are not universally used, due to there being several challenges associated with adapting them to various challenging settings. This thesis deals with Hessian-based optimization algorithms for large-scale, distributed and zeroth-order problems. For the large-scale setting, we contribute with a new way of deriving limited memory quasi-Newton methods, which we show can achieve better results than traditional limited memory quasi-Newton methods with less memory for some logistic and linear regression problems. For the distributed setting, we perform an analysis of how the error of a Newton-step is affected by the condition number and the number of iterations of a consensus-algorithm based on averaging, We show that the number of iterations needed to solve a quadratic problem with relative error less than ε grows logarithmically with 1/ε and also with the condition number of the Hessian of the centralized problem. For the zeroth order setting, we exploit the fact that a finite difference estimate of the directional derivative works as an approximate sketching technique, and use this to propose a zeroth order extension of a sketched Newton method that has been developed to solve large-scale problems. With the extension of this method to the zeroth order setting, we address the combined challenge of large-scale and zeroth order problems.
|
|
| 3. |
|
|
| 4. |
- Chaffey, Thomas, et al.
(författare)
-
Circuit analysis using monotone+skew splitting
- 2023
-
Ingår i: European Journal of Control. - 0947-3580.
-
Tidskriftsartikel (refereegranskat)abstract
- It is shown that the behavior of an m-port circuit of maximal monotone elements can be expressed as a zero of the sum of a maximal monotone operator containing the circuit elements, and a structured skew-symmetric linear operator representing the interconnection structure, together with a linear output transformation. The Condat–Vũ algorithm solves inclusion problems of this form, and may be used to solve for the periodic steady-state behavior, given a periodic excitation at each port, using an iteration in the space of periodic trajectories.
|
|
| 5. |
- Chakraborty, Sucharita, et al.
(författare)
-
Efficient downlink power allocation algorithms for cell-free massive mimo systems
- 2021
-
Ingår i: IEEE Open Journal of the Communications Society. - : Institute of Electrical and Electronics Engineers (IEEE). - 2644-125X. ; 2, s. 168-186
-
Tidskriftsartikel (refereegranskat)abstract
- Cell-free Massive MIMO systems consist of a large number of geographically distributed access points (APs) that serve the users by coherent joint transmission. The spectral efficiency (SE) achieved by each user depends on the power allocation: which APs that transmit to which users and with what power. In this article, we revisit the max-min and sum-SE power allocation policies, which have previously been approached using high-complexity general-purpose solvers. We develop and compare several different high-performance low-complexity power allocation algorithms that are appropriate for use in large systems. We propose two new algorithms for sum-SE power optimization inspired by weighted minimum mean square error (WMMSE) minimization and fractional programming (FP). Further, one new FP-based algorithm is proposed for max-min fair power allocation. The alternating direction method of multipliers (ADMM) is used to solve specific convex subproblems in the proposed algorithms. Our ADMM reformulations lead to multiple small-sized subproblems with closed-form solutions. The proposed algorithms find global or local optimal power allocation solutions for large-scale systems but with reduced computational time compared to previous work.
|
|
| 6. |
- Darup, Moritz Schulze, et al.
(författare)
-
Towards real-time ADMM for linear MPC
- 2019
-
Ingår i: 2019 18th European Control Conference, ECC 2019. - 9783907144008 ; , s. 4276-4282
-
Konferensbidrag (refereegranskat)abstract
- We present a novel predictive control scheme for linear constrained systems that uses the alternating direction method of multipliers (ADMM) for online optimization. In contrast to existing works on ADMM-based model predictive control (MPC), we only consider a single ADMM-iteration in every time step. The resulting real-time ADMM scheme is tailored for embedded and fast MPC implementations. The main difference to existing MPC schemes based on real-time iterations is that the proposed controller allows to include state and input constraints of the system. The paper derives the dynamics of the resulting closed-loop system, identifies important parameters of the real-time ADMM, and compares its performance to classical MPC.
|
|
| 7. |
- Doan, Minh Dang, et al.
(författare)
-
A distributed accelerated gradient algorithm for distributed model predictive control of a hydro power valley
- 2013
-
Ingår i: Control Engineering Practice. - : Elsevier BV. - 0967-0661. ; 21:11, s. 1594-1605
-
Tidskriftsartikel (refereegranskat)abstract
- A distributed model predictive control (DMPC) approach based on distributed optimization is applied to the power reference tracking problem of a hydro power valley (HPV) system. The applied optimization algorithm is based on accelerated gradient methods and achieves a convergence rate of O(1/k^2), where k is the iteration number. Major challenges in the control of the HPV include a nonlinear and large-scale model, non-smoothness in the power-production functions, and a globally coupled cost function that prevents distributed schemes to be applied directly. We propose a linearization and approximation approach that accommodates the proposed the DMPC framework and provides very similar performance compared to a centralized solution in simulations. The provided numerical studies also suggest that for the sparsely interconnected system at hand, the distributed algorithm we propose is faster than a centralized state-of-the-art solver such as CPLEX.
|
|
| 8. |
- Fält, Mattias, et al.
(författare)
-
Line Search for Generalized Alternating Projections
- 2016
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- This paper is about line search for the generalized alternating projections (GAP) method. This method is a generalization of the von Neumann alternating projections method, where instead of performing alternating projections, relaxed projections are alternated. The method can be interpreted as an averaged iteration of a nonexpansive mapping. Therefore, a recently proposed line search method for such algorithms is applicable to GAP. We evaluate this line search and show situations when the line search can be performed with little additional cost. We also present a variation of the basic line search for GAP - the projected line search. We prove its convergence and show that the line search condition is convex in the step length parameter. We show that almost all convex optimization problems can be solved using this approach and numerical results show superior performance with both the standard and the projected line search, sometimes by several orders of magnitude, compared to the nominal method.
|
|
| 9. |
- Fält, Mattias, et al.
(författare)
-
Line search for generalized alternating projections
- 2017
-
Ingår i: 2017 American Control Conference, ACC 2017. - 9781509059928 ; , s. 4637-4642
-
Konferensbidrag (refereegranskat)abstract
- This paper is about line search for the generalized alternating projections (GAP) method. This method is a generalization of the von Neumann alternating projections method, where instead of alternating projections, relaxed projections are alternated. The method can be interpreted as an averaged iteration of a nonexpansive mapping. Therefore, a recently proposed line search method for such algorithms is applicable to GAP. We evaluate this line search and show situations when the line search can be performed with little additional cost. We also present a variation of the basic line search for GAP - The projected line search. We prove its convergence and show that the line search condition is convex in the step length parameter. We show that almost all convex optimization problems can be solved using this approach and numerical results show superior performance with both the standard and the projected line search, sometimes by several orders of magnitude, compared to the nominal method.
|
|
| 10. |
- Fält, Mattias, et al.
(författare)
-
Optimal convergence rates for generalized alternating projections
- 2017
-
Ingår i: Proceedings of the IEEE Conference on Decision and Control, 2017. - 9781509028740 - 9781509028733 ; , s. 2268-2274
-
Konferensbidrag (refereegranskat)abstract
- Generalized alternating projections is an algorithm that alternates relaxed projections onto a finite number of sets to find a point in their intersection. We consider the special case of two linear subspaces, for which the algorithm reduces to matrix multiplications. For convergent powers of the matrix, the asymptotic rate is linear and decided by the magnitude of the subdominant eigenvalue. In this paper, we show how to select the three algorithm parameters to optimize this magnitude, and hence the asymptotic convergence rate. The obtained rate depends on the Friedrichs angle between the subspaces and is considerably better than known rates for other methods such as alternating projections and DouglasRachford splitting. We also present an adaptive scheme that, online, estimates the Friedrichs angle and updates the algorithm parameters based on this estimate. A numerical example is provided that supports our theoretical claims and shows very good performance for the adaptive method.
|
|
| 11. |
- Fält, Mattias, et al.
(författare)
-
QPDAS: Dual Active Set Solver for Mixed Constraint Quadratic Programming
- 2019
-
Ingår i: 2019 IEEE Conference on Decision and Control (CDC). - 9781728113982 - 9781728113999 ; , s. 4891-4897
-
Konferensbidrag (refereegranskat)abstract
- We present a method for solving the general mixed constrained convex quadratic programming problem using an active set method on the dual problem. The approach is similar to existing active set methods, but we present a new way of solving the linear systems arising in the algorithm. There are two main contributions; we present a new way of factorizing the linear systems, and show how iterative refinement can be used to achieve good accuracy and to solve both types of sub-problems that arise from semi-definite problems.
|
|
| 12. |
|
|
| 13. |
- Giselsson, Pontus
(författare)
-
A generalized distributed accelerated gradient method for distributed model predictive control with iteration complexity bounds
- 2013
-
Ingår i: [Host publication title missing]. - 0743-1619. ; , s. 327-333
-
Konferensbidrag (refereegranskat)abstract
- Most 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.
|
|
| 14. |
- Giselsson, Pontus, et al.
(författare)
-
Accelerated gradient methods and dual decomposition in distributed model predictive control
- 2013
-
Ingår i: Automatica. - : Elsevier BV. - 0005-1098. ; 49:3, s. 829-833
-
Tidskriftsartikel (refereegranskat)abstract
- We propose a distributed optimization algorithm for mixed L_1/L_2-norm optimization based on accelerated gradient methods using dual decomposition. The algorithm achieves convergence rate O(1/k^2), where k is the iteration number, which significantly improves the convergence rates of existing duality-based distributed optimization algorithms that achieve O(1/k). The performance of the developed algorithm is evaluated on randomly generated optimization problems arising in distributed model predictive control (DMPC). The evaluation shows that, when the problem data is sparse and large-scale, our algorithm can outperform current state-of-the-art optimization software CPLEX and MOSEK.
|
|
| 15. |
- Giselsson, Pontus
(författare)
-
Adaptive Nonlinear Model Predictive Control with Suboptimality and Stability Guarantees
- 2010
-
Ingår i: ; , s. 3644-3649
-
Konferensbidrag (refereegranskat)abstract
- Theory 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.
|
|
| 16. |
- Giselsson, Pontus, et al.
(författare)
-
Distributed Model Predictive Control with Suboptimality and Stability Guarantees
- 2010
-
Ingår i: ; , s. 7272-7277
-
Konferensbidrag (refereegranskat)abstract
- Theory for Distributed Model Predictive Control (DMPC) is developed based on dual decomposition of the convex optimization problem that is solved in each time sample. The process to be controlled is an interconnection of several subsystems, where each subsystem corresponds to a node in a graph. We present a stopping criterion for the DMPC scheme that can be locally verified by each node and that guarantees closed loop suboptimality above a pre-specified level and asymptotic stability of the interconnected system.
|
|
| 17. |
- Giselsson, Pontus, et al.
(författare)
-
Envelope Functions : Unifications and Further Properties
- 2018
-
Ingår i: Journal of Optimization Theory and Applications. - : Springer Science and Business Media LLC. - 0022-3239 .- 1573-2878. ; 178:3, s. 673-698
-
Tidskriftsartikel (refereegranskat)abstract
- Forward–backward and Douglas–Rachford splitting are methods for structured nonsmooth optimization. With the aim to use smooth optimization techniques for nonsmooth problems, the forward–backward and Douglas–Rachford envelopes where recently proposed. Under specific problem assumptions, these envelope functions have favorable smoothness and convexity properties and their stationary points coincide with the fixed-points of the underlying algorithm operators. This allows for solving such nonsmooth optimization problems by minimizing the corresponding smooth convex envelope function. In this paper, we present a general envelope function that unifies and generalizes existing ones. We provide properties of the general envelope function that sharpen corresponding known results for the special cases. We also present a new interpretation of the underlying methods as being majorization–minimization algorithms applied to their respective envelope functions.
|
|
| 18. |
- Giselsson, Pontus
(författare)
-
Execution time certification for gradient-based optimization in model predictive control
- 2012
-
Ingår i: [Host publication title missing]. - 0191-2216. ; , s. 3165-3170
-
Konferensbidrag (refereegranskat)abstract
- We 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.
|
|
| 19. |
- Giselsson, Pontus, et al.
(författare)
-
Generalized Accelerated Gradient Methods for Distributed MPC Based on Dual Decomposition
- 2014
-
Ingår i: Distributed Model Predictive Control Made Easy. - Dordrecht : Springer Netherlands. - 9789400770058 ; , s. 309-325
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- We consider distributed model predictive control (DMPC) where a sparse centralized optimization problem without a terminal cost or a terminal constraint set is solved in distributed fashion. Distribution of the optimization algorithm is enabled by dual decomposition. Gradient methods are usually used to solve the dual problem resulting from dual decomposition. However, gradient methods are known for their slow convergence rate, especially for ill-conditioned problems. This is not desirable in DMPC where the amount of communication should be kept as low as possible. In this chapter, we present a distributed optimization algorithm applied to solve optimization problems arising in DMPC that has significantly better convergence rate than the classical gradient method. This improved convergence rate is achieved by using accelerated gradient methods instead of standard gradient methods and by in a well-defined manner, incorporating Hessian information into the gradient-iterations. We also present a stopping condition to the distributed optimization algorithm that ensures feasibility, stability and closed loop performance of the DMPC-scheme, without using a stabilizing terminal cost or terminal constraint set.
|
|
| 20. |
- Giselsson, Pontus
(författare)
-
Gradient-Based Distributed Model Predictive Control
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The thesis covers different topics related to model predictive control (MPC) and particularly distributed model predictive control (DMPC). One topic of the thesis is gradient-based optimization algorithms for solving the optimization problem arising in DMPC in a distributed manner. The underlying idea is to solve the optimization problem in distributed fashion using dual decomposition, which is a well-known method. Dual decomposition is traditionally used in conjunction with (sub)gradient methods which are known to have bad convergence rate properties, especially for ill-conditioned problem. In this thesis it is shown how to use accelerated gradient methods with dual decomposition, and how to choose the step size parameter optimally in the algorithm. A method to bound the number of iterations needed to guarantee a prespecified accuracy of the solution is also provided. Based on the iteration bound, it is shown how to precondition the problem data optimally to improve conditioning of the problem. These contributions significantly improve the performance of the distributed optimization algorithm compared to dual decomposition with a (sub)gradient method. Another topic of the thesis is to guarantee feasibility and stability when using the developed distributed optimization algorithm in a DMPC context. Traditional methods of proving stability in MPC usually involve terminal cost functions and terminal constraints that are non-separable. These methods are not directly applicable in DMPC based on dual decomposition because of the non-separable terms. Further, dual decomposition does not provide feasible iterations but is guaranteed to be primal feasible only in the limit. These issues have been addressed in the thesis. The stability issue is addressed by showing that for problems without a terminal cost or terminal constraints and if a certain controllability assumption on the stage costs is satisfied, the optimal value function is decreasing in every time step by a prespecified amount. It is also shown how the controllability assumption can be verified by solving a mixed integer linear program. The feasibility issue is addressed by a novel adaptive constraint tightening approach. The adaptive constraint tightening guarantees that a primal feasible solution can be constructed with finite number of algorithm iterations without compromising the stability guarantee. The developed distributed optimization algorithm is evaluated on a hydro power valley benchmark problem. The hydro power valley consists of several dams connected in series where each dam is equipped with a turbine to extract power from the water. The objective is to control the water flow between the dams such that the total power from the turbines matches a power reference while respecting constraints on water levels and water flows. The control problem is formulated as an optimization problem, which is solved in receding horizon fashion using the distributed optimization algorithm presented in the thesis. The performance of the proposed distributed controller is compared to the performance of a centralized controller.
|
|
| 21. |
- Giselsson, Pontus
(författare)
-
Gradient-Based Model Predictive Control in a Pendulum System
- 2012
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Model predictive control (MPC) is applied to a physical pendulum system consisting of a pendulum and a cart. The objective of the MPC controller is to steer the system towards precomputed, time-optimal feedforward trajectories that move the system from one stationary point to another. The sample time of the controller sets hard limitations on the execution time of the optimization algorithm in the MPC controller. The MPC optimization problem is stated as a quadratic program, which is solved using the algorithm presented in [10]. The algorithm in [10] is an accelerated gradient method that is applied to solve a dual formulation of the MPC optimization problem. Experiments show that the optimization algorithm is efficient enough to be implemented in a real-time pendulum application.
|
|
| 22. |
- Giselsson, Pontus, et al.
(författare)
-
Large-scale and distributed optimization : An introduction
- 2018
-
Ingår i: Lecture Notes in Mathematics. - Cham : Springer International Publishing. - 0075-8434. ; 2227, s. 1-10
-
Bokkapitel (refereegranskat)abstract
- The recent explosion in size and complexity of datasets and the increased availability of computational resources has led us to what is sometimes called the big data era. In many big data fields, mathematical optimization has over the last decade emerged as a vital tool in extracting information from the data sets and creating predictors for unseen data. The large dimension of these data sets and the often parallel, distributed, or decentralized computational structures used for storing and handling the data, set new requirements on the optimization algorithms that solve these problems. This has led to a dramatic shift in focus in the optimization community over this period. Much effort has gone into developing algorithms that scale favorably with problem dimension and that can exploit structure in the problem as well as the computational environment. This is also the main focus of this book, which is comprised of individual chapters that further contribute to this development in different ways. In this introductory chapter, we describe the individual contributions, relate them to each other, and put them into a wider context.
|
|
| 23. |
|
|
| 24. |
- Giselsson, Pontus, et al.
(författare)
-
Line Search for Averaged Operator Iteration
- 2016
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Many popular first order algorithms for convex optimization, such as forward-backward splitting, Douglas-Rachford splitting, and the alternating direction method of multipliers (ADMM), can be formulated as averaged iteration of a nonexpansive mapping. In this paper we propose a line search for averaged iteration that preserves the theoretical convergence guarantee, while often accelerating practical convergence. We discuss several general cases in which the additional computational cost of the line search is modest compared to the savings obtained.
|
|
| 25. |
- Giselsson, Pontus, et al.
(författare)
-
Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
- 2017
-
Ingår i: IEEE Transactions on Automatic Control. - 0018-9286. ; 62:2, s. 532-544
-
Tidskriftsartikel (refereegranskat)abstract
- Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods.
|
|
| 26. |
- Giselsson, Pontus, et al.
(författare)
-
Metric selection in fast dual forward-backward splitting
- 2015
-
Ingår i: Automatica. - : Elsevier BV. - 0005-1098. ; 62, s. 1-10
-
Tidskriftsartikel (refereegranskat)abstract
- The performance of fast forward-backward splitting, or equivalently fast proximal gradient methods, depends on the conditioning of the optimization problem data. This conditioning is related to a metric that is defined by the space on which the optimization problem is stated; selecting a space on which the optimization data is better conditioned improves the performance of the algorithm. In this paper, we propose several methods, with different computational complexity, to find a space on which the algorithm performs well. We evaluate the proposed metric selection procedures by comparing the performance to the case when the Euclidean space is used. For the most ill-conditioned problem we consider, the computational complexity is improved by two to three orders of magnitude. We also report comparable to superior performance compared to state-of-the-art optimization software. (C) 2015 Elsevier Ltd. All rights reserved.
|
|
| 27. |
- Giselsson, Pontus
(författare)
-
Model Predictive Control in a Pendulum System
- 2011
-
Ingår i: Proceedings of the 31:th IASTED conference on Modelling, Identification and Control.
-
Konferensbidrag (refereegranskat)abstract
- Model Predictive Control (MPC) is applied to a pendulum system consisting of a pendulum and a cart. The objective of the MPC-controller is to steer the system towards precalculated trajectories that move the system from one operating point to another. The sample time of the controller sets hard limitations on the execution time of the optimization routine in the MPC-controller. The optimization problem to solve is cast as a convex optimization problem that can be efficiently solved to allow for real time implementation. The control scheme is applied to a physical pendulum and cart system and the performance of the proposed controller is compared to optimal performance.
|
|
| 28. |
- Giselsson, Pontus, et al.
(författare)
-
On compositions of special cases of Lipschitz continuous operators
- 2021
-
Ingår i: Fixed Point Theory and Algorithms for Sciences and Engineering. - : Springer Science and Business Media LLC. - 1687-1820 .- 2730-5422. ; 2021:1
-
Tidskriftsartikel (refereegranskat)abstract
- Many iterative optimization algorithms involve compositions of special cases of Lipschitz continuous operators, namely firmly nonexpansive, averaged, and nonexpansive operators. The structure and properties of the compositions are of particular importance in the proofs of convergence of such algorithms. In this paper, we systematically study the compositions of further special cases of Lipschitz continuous operators. Applications of our results include compositions of scaled conically nonexpansive mappings, as well as the Douglas–Rachford and forward–backward operators, when applied to solve certain structured monotone inclusion and optimization problems. Several examples illustrate and tighten our conclusions.
|
|
| 29. |
- Giselsson, Pontus, et al.
(författare)
-
On feasibility, stability and performance in distributed model predictive control
- 2014
-
Ingår i: IEEE Transactions on Automatic Control. - 0018-9286. ; 59:4, s. 1031-1036
-
Tidskriftsartikel (refereegranskat)abstract
- We present a stopping condition to the duality based distributed optimization algorithm presented in [1] when used in a distributed model predictive control (DMPC) context. To enable distributed implementation, the optimization problem has neither terminal constraints nor terminal cost that has become standard in model predictive control (MPC). The developed stopping condition guarantees a prespecified performance, stability, and feasibility with finite number of algorithm iterations. Feasibility is guaranteed using a novel adaptive constraint tightening approach that gives the same feasible set as when no constraint tightening is used. Stability and performance of the proposed DMPC controller without terminal cost or terminal constraints is shown based on a controllability parameter for the stage costs. To enable quantification of the control horizon necessary to ensure stability and the prespecified performance, we show how the controllability parameter can be computed by solving a mixed integer linear program (MILP).
|
|
| 30. |
- Giselsson, Pontus
(författare)
-
Optimal preconditioning and iteration complexity bounds for gradient-based optimization in model predictive control
- 2013
-
Ingår i: [Host publication title missing]. - 0743-1619. ; , s. 358-364
-
Konferensbidrag (refereegranskat)abstract
- In 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.
|
|
| 31. |
- Giselsson, Pontus, et al.
(författare)
-
Optimization of a Pendulum System using Optimica and Modelica
- 2009
-
Konferensbidrag (refereegranskat)abstract
- In this paper Modelica and Optimica are used to solve two different optimal control problems for a system consisting of a pendulum and a cart. These optimizations will demonstrate that Optimica is easy to use and powerful when optimizing systems with highly non-linear dynamics. The optimal control trajectories are applied to a real pendulum and cart system, in open loop as well as in closed loop with an MPC-controller. The experiments show that optimal trajectories from Optimica together with MPC feedback is a suitable control structure when optimal transitions through non-linear dynamics are desired.
|
|
| 32. |
- Giselsson, Pontus
(författare)
-
Output feedback distributed model predictive control with inherent robustness properties
- 2013
-
Ingår i: [Host publication title missing]. - 0743-1619. ; , s. 1691-1696
-
Konferensbidrag (refereegranskat)abstract
- We consider robust output feedback distributed model predictive control (DMPC). The proposed controller is based on the results in [8] in which nominal stability and feasibility was proven for a DMPC-formulation without terminal constraint set or terminal cost in the optimization. We extend these results to show robust stability under state feedback as well as output feedback when dynamics and measurements are affected by bounded noise. The provided numerical example suggests that the region of attraction without terminal constraint set may be significantly larger than if a terminal constraint set is used.
|
|
| 33. |
- Giselsson, Pontus
(författare)
-
Tight global linear convergence rate bounds for Douglas–Rachford splitting
- 2017
-
Ingår i: Journal of Fixed Point Theory and Applications. - : Springer Science and Business Media LLC. - 1661-7738 .- 1661-7746. ; 19:4, s. 2241-2270
-
Tidskriftsartikel (refereegranskat)abstract
- Recently, 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.
|
|
| 34. |
- Giselsson, Pontus
(författare)
-
Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM
- 2016
-
Ingår i: Proceedings of the IEEE Conference on Decision and Control. - 9781479978861 ; 2016, s. 3305-3310
-
Konferensbidrag (refereegranskat)abstract
- Douglas-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.
|
|
| 35. |
- Grommisch, David, et al.
(författare)
-
Defining the contribution of Troy-positive progenitor cells to the mouse esophageal epithelium
- 2024
-
Ingår i: Developmental Cell. - 1534-5807 .- 1878-1551. ; 59:10, s. 6-1283
-
Tidskriftsartikel (refereegranskat)abstract
- Progenitor cells adapt their behavior in response to tissue demands. However, the molecular mechanisms controlling esophageal progenitor decisions remain largely unknown. Here, we demonstrate the presence of a Troy (Tnfrsf19)-expressing progenitor subpopulation localized to defined regions along the mouse esophageal axis. Lineage tracing and mathematical modeling demonstrate that Troy-positive progenitor cells are prone to undergoing symmetrical fate choices and contribute to esophageal tissue homeostasis long term. Functionally, TROY inhibits progenitor proliferation and enables commitment to differentiation without affecting fate symmetry. Whereas Troy expression is stable during esophageal homeostasis, progenitor cells downregulate Troy in response to tissue stress, enabling proliferative expansion of basal cells refractory to differentiation and reestablishment of tissue homeostasis. Our results demonstrate functional, spatially restricted progenitor heterogeneity in the esophageal epithelium and identify how dynamic regulation of Troy coordinates tissue generation.
|
|
| 36. |
- Grussler, Christian, et al.
(författare)
-
Efficient Proximal Mapping Computation for Low-Rank Inducing Norms
- 2022
-
Ingår i: Journal of Optimization Theory and Applications. - : Springer Science and Business Media LLC. - 0022-3239 .- 1573-2878. ; 192:1, s. 168-194
-
Tidskriftsartikel (refereegranskat)abstract
- Low-rank inducing unitarily invariant norms have been introduced to convexify problems with a low-rank/sparsity constraint. The most well-known member of this family is the so-called nuclear norm. To solve optimization problems involving such norms with proximal splitting methods, efficient ways of evaluating the proximal mapping of the low-rank inducing norms are needed. This is known for the nuclear norm, but not for most other members of the low-rank inducing family. This work supplies a framework that reduces the proximal mapping evaluation into a nested binary search, in which each iteration requires the solution of a much simpler problem. The simpler problem can often be solved analytically as demonstrated for the so-called low-rank inducing Frobenius and spectral norms. The framework also allows to compute the proximal mapping of increasing convex functions composed with these norms as well as projections onto their epigraphs.
|
|
| 37. |
- Grussler, Christian, et al.
(författare)
-
Local convergence of proximal splitting methods for rank constrained problems
- 2018
-
Ingår i: 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017. - 9781509028733 ; 2018-January, s. 702-708
-
Konferensbidrag (refereegranskat)abstract
- We analyze the local convergence of proximal splitting algorithms to solve optimization problems that are convex besides a rank constraint. For this, we show conditions under which the proximal operator of a function involving the rank constraint is locally identical to the proximal operator of its convex envelope, hence implying local convergence. The conditions imply that the non-convex algorithms locally converge to a solution whenever a convex relaxation involving the convex envelope can be expected to solve the non-convex problem.
|
|
| 38. |
- Grussler, Christian, et al.
(författare)
-
Low-rank inducing norms with optimality interpretations∗
- 2018
-
Ingår i: SIAM Journal on Optimization. - 1052-6234. ; 28:4, s. 3057-3078
-
Tidskriftsartikel (refereegranskat)abstract
- Optimization problems with rank constraints appear in many diverse fields such as control, machine learning, and image analysis. Since the rank constraint is nonconvex, these problems are often approximately solved via convex relaxations. Nuclear norm regularization is the prevailing convexifying technique for dealing with these types of problem. This paper introduces a family of low-rank inducing norms and regularizers which include the nuclear norm as a special case. A posteriori guarantees on solving an underlying rank constrained optimization problem with these convex relaxations are provided. We evaluate the performance of the low-rank inducing norms on three matrix completion problems. In all examples, the nuclear norm heuristic is outperformed by convex relaxations based on other low-rank inducing norms. For two of the problems there exist low-rank inducing norms that succeed in recovering the partially unknown matrix, while the nuclear norm fails. These low-rank inducing norms are shown to be representable as semidefinite programs. Moreover, these norms have cheaply computable proximal mappings, which make it possible to also solve problems of large size using first-order methods.
|
|
| 39. |
- Grussler, Christian, et al.
(författare)
-
Low-Rank Optimization with Convex Constraints
- 2018
-
Ingår i: IEEE Transactions on Automatic Control. - 0018-9286. ; 63:11, s. 4000-4007
-
Tidskriftsartikel (refereegranskat)abstract
- The problem of low-rank approximation with convex constraints, which appears in data analysis, system identification, model order reduction, low-order controller design and low-complexity modelling is considered. Given a matrix, the objective is to find a low-rank approximation that meets rank and convex constraints, while minimizing the distance to the matrix in the squared Frobenius norm. In many situations, this non-convex problem is convexified by nuclear norm regularization. However, we will see that the approximations obtained by this method may be far from optimal. Here, we propose an alternative convex relaxation that uses the convex envelope of the squared Frobenius norm and the rank constraint. With this approach, easily verifiable conditions are obtained under which the solutions to the convex relaxation and the original non-convex problem coincide. An SDP representation of the convex envelope is derived, which allows us to treat several known problems. Our example on optimal low-rank Hankel approximation/model reduction illustrates that the proposed convex relaxation performs consistently better than nuclear norm regularization as well as balanced truncation.
|
|
| 40. |
- Grussler, Christian, et al.
(författare)
-
Optimality interpretations for atomic norms
- 2019
-
Ingår i: 2019 18th European Control Conference, ECC 2019. - 9783907144008 ; , s. 1473-1477
-
Konferensbidrag (refereegranskat)abstract
- Atomic norms occur frequently in data science and engineering problems such as matrix completion, sparse linear regression, system identification and many more. These norms are often used to convexify non-convex optimization problems, which are convex apart from the solution lying in a non-convex set of so-called atoms. For the convex part being a linear constraint, the ability of several atomic norms to solve the original non-convex problem has been analyzed by means of tangent cones. This paper presents an alternative route for this analysis by showing that atomic norm convexifcations always provide an optimal convex relaxation for some related non-convex problems. As a result, we obtain the following benefits: (i) treatment of arbitrary convex constraints, (ii) potentially obtaining solutions to the non-convex problem with a posteriori success certificates, (iii) utilization of additional prior knowledge through the design or learning of the non-convex problem.
|
|
| 41. |
- Li, Yuchao
(författare)
-
Approximate Solution Methods to Optimal Control Problems via Dynamic Programming Models
- 2021
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Optimal control theory has a long history and broad applications. Motivated by the goal of obtaining insights through unification and taking advantage of the abundant capability to generate data, this thesis introduces some suboptimal schemes via abstract dynamic programming models.As our first contribution, we consider deterministic infinite horizon optimal control problems with nonnegative stage costs. We draw inspiration from the learning model predictive control scheme designed for continuous dynamics and iterative tasks, and propose a rollout algorithm that relies on sampled data generated by some base policy. The proposed algorithm is based on value and policy iteration ideas. It applies to deterministic problems with arbitrary state and control spaces, and arbitrary dynamics. It admits extensions to problems with trajectory constraints, and a multiagent structure.In addition, abstract dynamic programming models are used to analyze $\lambda$-policy iteration with randomization algorithms. In particular, we consider contractive models with infinite policies. We show that well-posedness of the $\lambda$-operator plays a central role in the algorithm. The operator is known to be well-posed for problems with finite states, but our analysis shows that it is also well-defined for the contractive models with infinite states. Similarly, the algorithm we analyze is known to converge for problems with finite policies, but we identify the conditions required to guarantee convergence with probability one when the policy space is infinite regardless of the number of states. Guided by the analysis, we exemplify a data-driven approximated implementation of the algorithm for estimation of optimal costs of constrained linear and nonlinear control problems. Numerical results indicate the potentials of this method in practice.
|
|
| 42. |
- Lindholm, Anna, et al.
(författare)
-
Formulating an Optimization Problem for Minimization of Losses due to Utilities
- 2012
-
Ingår i: 8th IFAC International Symposium on Advanced Control of Chemical Processes 2012. - 9781622762286 ; , s. 55-60
-
Konferensbidrag (refereegranskat)abstract
- Utilities, such as steam and cooling water, are often shared between several production areas at industrial sites, and the effects of disturbances in utilities could thus be hard to predict. In addition, production areas could be connected because of the product flow at the site. This paper introduces a simple modeling approach for modeling the relation between utility operation and production. Using this modeling approach, an optimization problem can be formulated with the objective to minimize the economical losses due to disturbances in utilities by controlling the production of all areas at a site. The formulation of the problem is general, and thus the optimization can be performed for any site with similar structure. The results are useful for investigating the impact of plant-wide disturbances in utilities, and can provide decision support for how to control the production at utility disturbances. To enable online advise to operators on how to control the production, the posed optimization problem is solved in receding horizon fashion.
|
|
| 43. |
- Lindholm, Anna, et al.
(författare)
-
Minimization of economical losses due to utility disturbances in the process industry
- 2013
-
Ingår i: Journal of Process Control. - : Elsevier BV. - 1873-2771 .- 0959-1524. ; 23:5, s. 767-777
-
Tidskriftsartikel (refereegranskat)abstract
- A process industrial site may consist of several production areas, some producing intermediate products for further refinement in other areas, and some producing end products. The areas may share the same utilities, such as steam and cooling water, which means that the areas could be connected both by the flow of products through the site and by the use of the same utilities. Management of utility disturbances thus becomes an interesting topic. In this paper, a simple approach for modeling utilities is suggested and used to formulate a mixed-integer quadratic program (MIQP) that aims at minimizing the total economic loss at the site, due to utility disturbances. The optimization problem is reformulated as an ordinary quadratic program (QP), where auxiliary variables are utilized to avoid the use of integer variables. For suitable choices of the optimization weights, the solutions to the MIQP and the QP are in many cases equal. Two examples are given, where one is a small example inspired by a real site at the specialty chemicals company Perstorp, and the second is a larger problem that aims to show the advantage of the QP formulation when the number of areas, and thus the number of integer variables, becomes large.
|
|
| 44. |
- Lindholm, Anna, et al.
(författare)
-
Production scheduling in the process industry
- 2013
-
Ingår i: Proceedings for 22nd International Conference on Production Research, 2013.
-
Konferensbidrag (refereegranskat)abstract
- The purpose of this paper is to formulate an optimization model for the production scheduling problem at continuous production sites. The production scheduling activity should produce a monthly schedule that accounts for orders and forecasts of all products. The plan should be updated every day, with feedback on the actual production the previous day. The actual daily production may be lower than the planned production due to disturbances, e.g. disruptions in the supply of a utility. The work is performed in collaboration with Perstorp, a world-leading company within several sectors of the specialty chemicals market. Together with Perstorp, a list of specifications for the production scheduling has been formulated. These are formulated mathematically in a mixed-integer linear program that is solved in receding horizon fashion. The formulation of the model aims to be general, such that it may be used for any process industrial site.
|
|
| 45. |
- Morin, Martin, et al.
(författare)
-
Cocoercivity, smoothness and bias in variance-reduced stochastic gradient methods
- 2022
-
Ingår i: Numerical Algorithms. - : Springer Science and Business Media LLC. - 1017-1398 .- 1572-9265. ; 91:2, s. 749-772
-
Tidskriftsartikel (refereegranskat)abstract
- With the purpose of examining biased updates in variance-reduced stochastic gradient methods, we introduce SVAG, a SAG/SAGA-like method with adjustable bias. SVAG is analyzed in a cocoercive root-finding setting, a setting which yields the same results as in the usual smooth convex optimization setting for the ordinary proximal-gradient method. We show that the same is not true for SVAG when biased updates are used. The step-size requirements for when the operators are gradients are significantly less restrictive compared to when they are not. This highlights the need to not rely solely on cocoercivity when analyzing variance-reduced methods meant for optimization. Our analysis either match or improve on previously known convergence conditions for SAG and SAGA. However, in the biased cases they still do not correspond well with practical experiences and we therefore examine the effect of bias numerically on a set of classification problems. The choice of bias seem to primarily affect the early stages of convergence and in most cases the differences vanish in the later stages of convergence. However, the effect of the bias choice is still significant in a couple of cases.
|
|
| 46. |
- Morin, Martin, et al.
(författare)
-
FRUGAL SPLITTING OPERATORS : REPRESENTATION, MINIMAL LIFTING, AND CONVERGENCE
- 2024
-
Ingår i: SIAM Journal on Optimization. - 1052-6234. ; 34:2, s. 1595-1621
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate frugal splitting operators for finite sum monotone inclusion problems. These operators utilize exactly one direct or resolvent evaluation of each operator of the sum, and the splitting operator's output is dictated by linear combinations of these evaluations' inputs and outputs. To facilitate analysis, we introduce a novel representation of frugal splitting operators via a generalized primal-dual resolvent. The representation is characterized by an index and four matrices, and we provide conditions on these that ensure equivalence between the classes of frugal splitting operators and generalized primal-dual resolvents. Our representation paves the way for new results regarding lifting numbers and the development of a unified convergence analysis for frugal splitting operator methods, contingent on the directly evaluated operators being cocoercive. The minimal lifting number is n - 1 - f where n is the number of monotone operators and f is the number of direct evaluations in the splitting. Notably, this lifting number is achievable only if the first and last operator evaluations are resolvent evaluations. These results generalize the minimal lifting results by Ryu and by Malitsky and Tam that consider frugal resolvent splittings. Building on our representation, we delineate a constructive method to design frugal splitting operators, exemplified in the design of a novel, convergent, and parallelizable frugal splitting operator with minimal lifting.
|
|
| 47. |
- Morin, Martin, et al.
(författare)
-
Nonlinear Forward-Backward Splitting with Momentum Correction
- 2023
-
Ingår i: Set-Valued and Variational Analysis. - 1877-0533. ; 31:4
-
Tidskriftsartikel (refereegranskat)abstract
- The 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.
|
|
| 48. |
- Nielsen, Isak
(författare)
-
On Structure Exploiting Numerical Algorithms for Model Predictive Control
- 2015
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- One of the most common advanced control strategies used in industry today is Model Predictive Control (MPC), and some reasons for its success are that it can handle multivariable systems and constraints on states and control inputs in a structured way. At each time-step in the MPC control loop the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem on-line. There exist several optimization methods to solve the CFTOC problem, where two common types are interior-point (IP) methods and active-set (AS) methods. In both these types of methods, the main computational effort is known to be the computation of the search directions, which boils down to solving a sequence of Newton-system-like equations. These systems of equations correspond to unconstrained finite-time optimal control (UFTOC) problems. Hence, high-performance IP and AS methods for CFTOC problems rely on efficient algorithms for solving the UFTOC problems.The solution to a UFTOC problem is computed by solving the corresponding Karush-Kuhn-Tucker (KKT) system, which is often done using generic sparsity exploiting algorithms or Riccati recursions. When an AS method is used to compute the solution to the CFTOC problem, the system of equations that is solved to obtain the solution to a UFTOC problem is only changed by a low-rank modification of the system of equations in the previous iteration. This structured change is often exploited in AS methods to improve performance in terms of computation time. Traditionally, this has not been possible to exploit when Riccati recursions are used to solve the UFTOC problems, but in this thesis, an algorithm for performing low-rank modifications of the Riccati recursion is presented.In recent years, parallel hardware has become more commonly available, and the use of parallel algorithms for solving the CFTOC problem and the underlying UFTOC problem has increased. Some existing parallel algorithms for computing the solution to this type of problems obtain the solution iteratively, and these methods may require many iterations to converge. Some other parallel algorithms compute the solution directly (non-iteratively) by solving parts of the system of equations in parallel, followed by a serial solution of a dense system of equations without the sparse structure of the MPC problem. In this thesis, two parallel algorithms that compute the solution directly (non-iteratively) in parallel are presented. These algorithms can be used in both IP and AS methods, and they exploit the sparse structure of the MPC problem such that no dense system of equations needs to be solved serially. Furthermore, one of the proposed parallel algorithms exploits the special structure of the MPC problem even in the parallel computations, which improves performance in terms of computation time even more. By using these algorithms, it is possible to obtain logarithmic complexity growth in the prediction horizon length.
|
|
| 49. |
- RYU, ERNEST K., et al.
(författare)
-
Operator splitting performance estimation : Tight contraction factors and optimal parameter selection
- 2020
-
Ingår i: SIAM Journal on Optimization. - 1052-6234. ; 30:3, s. 2251-2271
-
Tidskriftsartikel (refereegranskat)abstract
- We propose a methodology for studying the performance of common splitting methods through semidefinite programming. We prove tightness of the methodology and demonstrate its value by presenting two applications of it. First, we use the methodology as a tool for computerassisted proofs to prove tight analytical contraction factors for Douglas-Rachford splitting that are likely too complicated for a human to find bare-handed. Second, we use the methodology as an algorithmic tool to computationally select the optimal splitting method parameters by solving a series of semidefinite programs.
|
|
| 50. |
- Sadeghi, Hamed, et al.
(författare)
-
FORWARD-BACKWARD SPLITTING WITH DEVIATIONS FOR MONOTONE INCLUSIONS
- 2024
-
Ingår i: Applied Set-Valued Analysis and Optimization. - 2562-7775. ; 6:2, s. 113-135
-
Tidskriftsartikel (refereegranskat)abstract
- We propose and study a weakly convergent variant of the forward-backward algorithm for solving structured monotone inclusion problems. Our algorithm features a per-iteration deviation vector, providing additional degrees of freedom. The only requirement on the deviation vector to guarantee convergence is that its norm is bounded by a quantity that can be computed online. This approach offers great flexibility and paves the way for the design of new forward-backward-based algorithms, while still retaining global convergence guarantees. These guarantees include linear convergence under a metric subregularity assumption. Choosing suitable monotone operators enables the incorporation of deviations into other algorithms, such as the Chambolle-Pock method and Krasnosel'skii-Mann iterations. We propose a novel inertial primal-dual algorithm by selecting the deviations along a momentum direction and deciding their size by using the norm condition. Numerical experiments validate our convergence claims and demonstrate that even this simple choice of a deviation vector can enhance the performance compared to, for instance, the standard Chambolle-Pock algorithm. Copy: 2024 Applied Set-Valued Analysis and Optimization.
|
|
