Search

type:FULL LENGTH PAPER Series A, This paper analyzes block-coordinate proximal gradient methods for minimizing the sum of a separable smooth function and a (nonseparable) nonsmooth function, both of which are allowed to be nonconvex. The main tool in our analysis is the forwardbackward envelope, which serves as a particularly suitable continuous and real-valued Lyapunov function. Global and linear convergence results are established when the cost function satisfies the Kurdyka–Łojasiewicz property without imposing convexity requirements on the smooth function. Two prominent special cases of the investigated setting are regularized finite sum minimization and the sharing problem; in particular, an immediate byproduct of our analysis leads to novel convergence results and rates for the popular Finito/MISO algorithm in the nonsmooth and nonconvex setting with very general sampling strategies.

We introduce a new stochastic gradient algorithm, SAAGA, and investigate its employment for solving Stochastic MPC problems and multi-stage stochastic optimization programs in general. The method is particularly attractive for scenario-based formulations that involve a large number of scenarios, for which “batch” formulations may become inefficient due to high computational costs. Benefits of the method include cheap computations per iteration and fast convergence due to the sparsity of the proposed problem decomposition.

Operator splitting techniques have recently gained popularity in convex optimization problems arising in various control fields. Being fixed-point iterations of nonexpansive (NE) operators, such methods suffer many well known downsides, which include high sensitivity to ill conditioning and parameter selection, and consequent low accuracy and robustness. As universal solution we propose SuperMann, a Newton-type algorithm for finding fixed points of NE operators. It generalizes the classical Krasnosel'ski ˇı–Mann scheme, enjoys its favorable global convergence properties and requires exactly the same oracle. It is based on a novel separating hyperplane projection tailored for nonexpansive mappings which makes it possible to include steps along any direction. In particular, when the directions satisfy a Dennis–Mor´e condition we show that SuperMann converges superlinearly under mild assumptions, which, surprisingly, do not entail nonsingularity of the Jacobian at the solution butmerelymetric subregularity. As a result, SuperMann enhances and robustifies all operator splitting schemes for structured convex optimization, overcoming their well known sensitivity to ill conditioning.

We introduce Bella, a locally superlinearly convergent Bregman forward-backward splitting method for minimizing the sum of two nonconvex functions, one of which satisfies a relative smoothness condition and the other one is possibly nonsmooth. A key tool of our methodology is the Bregman forward-backward envelope (BFBE), an exact and continuous penalty function with favorable first- and second-order properties, which enjoys a nonlinear error bound when the objective function satisfies a Lojasiewicz-type property. The proposed algorithm is of linesearch type over the BFBE along user-defined update directions and converges subsequentially to stationary points and globally under the Kurdyka-Lojasiewicz condition. Moreover, when the update directions are superlinear in the sense of Facchinei and Pang [Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I, Springer, New York, 2003], owing to the given nonlin- ear error bound unit stepsize is eventually always accepted and the algorithm attains superlinear convergence rates even when the limit point is a nonisolated minimum.

We employ the proximal averaged Newton-type method for optimal control (PANOC) to solve obstacle avoidance problems in real time. We introduce a novel modeling framework for obstacle avoidance which allows us to easily account for generic, possibly nonconvex, obstacles involving polytopes, ellipsoids, semialgebraic sets and generic sets described by a set of nonlinear inequalities. PANOC is particularly well-suited for embedded applications as it involves simple steps, its implementation comes with a low memory footprint and its fast convergence meets the tight runtime requirements of fast dynamical systems one encounters in modern mechatronics and robotics. The proposed obstacle avoidance scheme is tested on a lab-scale autonomous vehicle.

Operator splitting algorithms are enjoying wide acceptance in signal processing for their ability to solve generic convex optimization problems exploiting their structure and leading to efficient implementations. These algorithms are instances of the Krasnosel’ski˘ı-Mann scheme for finding fixed points of averaged operators. Despite their popularity, however, operator splitting algorithms are sensitive to ill conditioning and often converge slowly. In this paper we propose a line search primaldual method to accelerate and robustify the Chambolle-Pock algorithm based on SuperMann: a recent extension of the Krasnosel’ski ˘ı-Mann algorithmic scheme. We discuss the convergence properties of this new algorithm and we showcase its strengths on the problem of image denoising using the anisotropic total variation regularization.

The decomposition of tensors into simple rank-1 terms is key in a variety of applications in signal processing, data analysis and machine learning. While this canonical polyadic decomposition (CPD) is unique under mild conditions, including prior knowledge such as nonnegativity can facilitate interpretation of the components. Inspired by the effectiveness and efficiency of Gauss–Newton (GN) for unconstrained CPD, we derive a proximal, semismooth GN type algorithm for nonnegative tensor factorization. Global convergence to local minima is achieved via backtracking on the forward-backward envelope function. If the algorithm converges to the global optimum, we show that Q-quadratic rates are obtained in the exact case. Such fast rates are verified experimentally, and we illustrate that using the GN step significantly reduces number of (expensive) gradient computations compared to proximal gradient descent.

We propose ZeroFPR, a nonmonotone linesearch algorithm for minimizing the sum of two nonconvex functions, one of which is smooth and the other possibly nonsmooth. ZeroFPR is the first algorithm that, despite being fit for fully nonconvex problems and requiring only the black-box oracle of forward-backward splitting (FBS) — namely evaluations of the gradient of the smooth term and of the proximity operator of the nonsmooth one — achieves superlinear convergence rates under mild assumptions at the limit point when the linesearch directions satisfy a Dennis-Moré condition, and we show that this is the case for Broyden’s quasi-Newton directions. Our approach is based on the forward-backward envelope (FBE), an exact and strictly continuous penalty function for the original cost. Extending previous results we show that, despite being nonsmooth for fully nonconvex problems, the FBE still enjoys favorable first- and second-order properties which are key for the convergence results of ZeroFPR. Our theoretical results are backed up by promising numerical simulations. On large-scale problems, by computing linesearch directions using limited-memory quasi-Newton updates our algorithm greatly outperforms FBS and its accelerated variant (AFBS).

We propose a Newton-type alternating minimization algorithm (NAMA) for solving structured nonsmooth convex optimization problems where the sum of two functions is to be minimized, one being strongly convex and the other composed with a linear mapping. The proposed algorithm is a line-search method over a continuous, realvalued, exact penalty function for the corresponding dual problem, which is computed by evaluating the augmented Lagrangian at the primal points obtained by alternatingminimizations. As a consequence, NAMA relies on exactly the same computations as the classical alternating minimization algorithm (AMA), also known as the dual-proximal gradient method. Under standard assumptions, the proposed algorithm converges with global sublinear and local linear rates, while under mild additional assumptions, the asymptotic convergence is superlinear, provided that the search directions are chosen according to quasi-Newton formulas. Due to its simplicity, the proposed method is well suited for embedded applications and large-scale problems. Experiments show that using limited-memory directions in NAMA greatly improves the convergence speed over AMA and its accelerated variant.

Although originally designed and analyzed for convex problems, the alternating direction method of multipliers (ADMM) and its close relatives, Douglas-Rachford splitting (DRS) and Peaceman-Rachford splitting (PRS), have been observed to perform remarkably well when applied to certain classes of structured nonconvex optimization problems. However, partial global convergence results in the nonconvex setting have only recently emerged. In this paper we show how the Douglas-Rachford envelope (DRE), introduced in 2014, can be employed to unify and considerably simplify the theory for devising global convergence guarantees for ADMM, DRS and PRS applied to nonconvex problems under less restrictive conditions, larger prox-stepsizes and over-relaxation parameters than previously known. In fact, our bounds are tight whenever the over-relaxation parameter ranges in (0, 2]. The analysis of ADMM uses a universal primal equivalence with DRS that generalizes the known duality of the algorithms.

The economic crisis in Greece resulted in a change in residential heating fuels utilized, which in turn resulted in a change of air quality over Greater Athens Area. The aim of this study was to investigate the effects of economic crisis in air quality over Attica by examining the change in air pollutants’ concentrations before, during, and after the onset of the economic crisis in Greece and to associate this change with the change in fuels used for residential heating. For this purpose, I analyzed six MODIS L1B datasets with 500m spatial resolution, one for each year studied, MODIS AOT and NDVI products, at 10 km and 500 m spatial resolution respectively. Additionally, I used AQMS measurements and CORINE 2000 Land Cover dataset. To densify the ground monitoring network, virtual stations were identified according to Narashid et al (2006) criteria. Through OLS regressions, air pollutants’ concentration were estimated for the virtual stations and, subsequently, for the whole map of Great Athens Area (GAA) for the chosen time periods. Subsequently, the association between the change in fuel consumption and the change in pollutant concentrations between the examined periods was performed, based on Kakaras et al (2013) emissions ratios for each fuel utilized in residential heating that indirectly indicate fuel types utilized in the residential heating systems. Primary results show that during the whole period examined (2007-2012) SO2 concentrations were increased in most parts of GAA, while NO2 and PM10 were decreased. CO concentrations were stable in most zones of GAA. Where the fuels used for residential heating are concerned, the use of wood and pellet has increased in most urban areas of GAA, while the use of heating oil and natural gas appear to be decreased. Keywords: Economic Crisis, Air Quality, Satellite Data, Virtual Stations, Regression Analysis, Air pollutants mapping, anthropogenic factors., Effects of economic crisis in heating systems and air pollution The economic crisis in Greece has resulted in changes in the use of fuel for residential heating systems, resulting in change in air quality over the capital of Greece, Athens. This study investigated these effects of the economic crisis and examined how the change in air quality that occurred is associated with the change in heating fuels utilized. Methodology The study employed satellite imagery and relevant products in conjunction with land use maps and ground station measurements of pollutant concentrations to estimate pollutant concentration changes over Athens and determine how the use of heating fuels has changed during the onset of the economic crisis in Greece. A key methodology used in the study is the definition of virtual stations, locations with physical characteristics similar to locations where actual pollutant measurement stations are located. Virtual stations enable the densification of the network of measurement stations used in regressions within the analysis, increasing accuracy of the results. Results The analysis examined the spatial concentrations of pollutants over Athens before, during, and after the onset of the economic crisis. For most examined pollutants, the concentrations demonstrate changes between the examined periods. The results of the study showed a significant decrease in petrol consumption during the onset of the economic crisis throughout Athens. Natural gas consumption remained relatively stable, while wood consumption as a heating fuel presents a generally stable consumption with many large areas exhibiting increase. These areas can, also, justify the appearance of haze in Athens during winter months, that became evident during the onset of the economic crisis. Keywords: Geography, GIS, atmospheric pollution, economic crisis, Greece, household heating systems, heating fuel Advisor: Jonathan Seaquist Master degree project 30 credits in Geographical Information Sci

This paper studies the sample complexity of the stochastic Linear Quadratic Regulator when applied to systems with multiplicative noise. We assume that the covariance of the noise is unknown and estimate it using the sample covariance, which results in suboptimal behaviour. The main contribution of this paper is then to bound the suboptimality of the methodology and prove that it decreases with 1/N, where N denotes the amount of samples. The methodology easily generalizes to the case where the mean is unknown and to the distributionally robust case studied in a previous work of the authors. The analysis is mostly based on results from matrix function perturbation analysis.

We propose a learning-based, distributionally robust model predictive control approach towards the design of adaptive cruise control (ACC) systems. We model the preceding vehicle as an autonomous stochastic system, using a hybrid model with continuous dynamics and discrete, Markovian inputs. We estimate the (unknown) transition probabilities of this model empirically using observed mode transitions and simultaneously determine sets of probability vectors (ambiguity sets) around these estimates, that contain the true transition probabilities with high confidence. We then solve a risk-averse optimal control problem that assumes the worst-case distributions in these sets. We furthermore derive a robust terminal constraint set and use it to establish recursive feasibility of the resulting MPC scheme. We validate the theoretical results and demonstrate desirable properties of the scheme through closed-loop simulations., Comment: Accepted for publication in the IFAC World Congress 2020; extended version with proofs

We propose BIBPA, a block inertial Bregman proximal algorithm for minimizing the sum of a block relatively smooth function (that is, relatively smooth concerning each block) and block separable nonsmooth nonconvex functions. We prove that the sequence generated by BIBPA subsequentially converges to critical points of the objective under standard assumptions, and globally converges when the objective function is additionally assumed to satisfy the Kurdyka-{\L}ojasiewicz (K{\L}) property. We also provide the convergence rate when the objective satisfies the {\L}ojasiewicz inequality. We apply BIBPA to the symmetric nonnegative matrix tri-factorization (SymTriNMF) problem, where we propose kernel functions for SymTriNMF and provide closed-form solutions for subproblems of BIBPA., Comment: 18 pages

We present Optimization Engine (OpEn): an open-source code generation tool for real-time embedded nonconvex optimization, which implements a novel numerical method. OpEn combines the proximal averaged Newton-type method for optimal control (PANOC) with the penalty and augmented Lagrangian methods to compute approximate stationary points of nonconvex problems. The proposed method involves very simple algebraic operations such as vector products, has a low memory footprint and exhibits very good convergence properties that allow the solution of nonconvex problems on embedded devices. OpEn's core solver is written is Rust - a modern, high-performance, memory-safe and thread-safe systems programming language - while users can call it from Python, MATLAB, C, C++ or over a TCP socket., Comment: IFAC World Congress 2020, Berlin

We introduce Constr-DRKM, a deep kernel method for the unsupervised learning of disentangled data representations. We propose augmenting the original deep restricted kernel machine formulation for kernel PCA by orthogonality constraints on the latent variables to promote disentanglement and to make it possible to carry out optimization without first defining a stabilized objective. After illustrating an end-to-end training procedure based on a quadratic penalty optimization algorithm with warm start, we quantitatively evaluate the proposed method's effectiveness in disentangled feature learning. We demonstrate on four benchmark datasets that this approach performs similarly overall to $\beta$-VAE on a number of disentanglement metrics when few training points are available, while being less sensitive to randomness and hyperparameter selection than $\beta$-VAE. We also present a deterministic initialization of Constr-DRKM's training algorithm that significantly improves the reproducibility of the results. Finally, we empirically evaluate and discuss the role of the number of layers in the proposed methodology, examining the influence of each principal component in every layer and showing that components in lower layers act as local feature detectors capturing the broad trends of the data distribution, while components in deeper layers use the representation learned by previous layers and more accurately reproduce higher-level features.

We present a data-driven model predictive control scheme for chance-constrained Markovian switching systems with unknown switching probabilities. Using samples of the underlying Markov chain, ambiguity sets of transition probabilities are estimated which include the true conditional probability distributions with high probability. These sets are updated online and used to formulate a time-varying, risk-averse optimal control problem. We prove recursive feasibility of the resulting MPC scheme and show that the original chance constraints remain satisfied at every time step. Furthermore, we show that under sufficient decrease of the confidence levels, the resulting MPC scheme renders the closed-loop system mean-square stable with respect to the true-but-unknown distributions, while remaining less conservative than a fully robust approach., Comment: Accepted at 59th IEEE Conference on Decision and Control (CDC 2020); extended version