Coordinate descent with arbitrary sampling I: algorithms and complexity†

We study the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer and propose a new randomized coordinate descent method, which we call ALPHA. Our method at every iteration updates a random subset of coordinates, following an arbitrary distribution. No coordinate descent methods capable to handle an arbitrary sampling have been studied in the literature before for this problem. ALPHA is a very flexible algorithm: in special cases, it reduces to deterministic and randomized methods such as gradient descent, coordinate descent, parallel coordinate descent and distributed coordinate descent—both in nonaccelerated and accelerated variants. The variants with arbitrary (or importance) sampling are new. We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.     

Networked model predictive control based on neighbourhood optimization for serially connected large-scale processes

In this paper, two novel networked model predictive control schemes based on neighbourhood optimization are presented for on-line optimization and control of a class of serially connected processes (known as the cascade processes in some references), in which the on-line optimization of the whole system is decomposed into that of several small-scale subsystems in distributed structures. Under network environment, the connectivity of the communication network is assumed to be sufficient for each subsystem to exchange information with its neighbour subsystems. An iterative algorithm for networked MPC and a networked MPC algorithm with one-step delay communication are developed according to different network capacities. The optimality of the iteration based networked MPC algorithm is analyzed and the nominal stability is derived for unconstrained distributed control systems. The nominal stability with one-step delay communication is employed for distributed control systems without the inequality constraints. Finally, an illustrative example and the simulation study of the fuel feed flow control for the walking beam reheating furnace are provided to test the effectiveness and practicality of the proposed networked MPC algorithms.     

Distributed Model Predictive Control Method for Optimal Coordination of Signal Splits in Urban Traffic Networks

Coordination and control approaches based on model predictive control (MPC) have been widely investigated for traffic signal control in urban traffic networks. However, due to the complex non‐linear characters of traffic flows and the large scale of traffic networks, a basic challenge faced by these approaches is the high online computational complexity. In this paper, to reduce the computational complexity and improve the applicability of traffic signal control approaches based on MPC in practice, we propose a distributed MPC approach (DCA‐MPC) to coordinate and optimize the signal splits. Instead of describing the dynamics of traffic flow within each link of the traffic network with a simplified linear model, we present an improved nonlinear traffic model. Based on the nonlinear model, an MPC optimization framework for the signal splits control is developed, whereby the interactions between subsystems are accurately modeled by employing two interconnecting constraints. In addition, by designing a novel dual decomposition strategy, a distributed coordination algorithm is proposed. Finally, with a benchmark traffic network, experimental results are given to illustrate the effectiveness of the proposed method.     

非平衡有向网络的完全分布式凸优化

分布式凸优化问题的目的是如何以分布式方法最小化局部智能体成本函数和,而现有分布式算法的控制步长选取依赖于系统智能体个数、伴随矩阵等全局性信息,有悖于分布式算法的初衷.针对此问题,提出一种基于非平衡有向网络的完全分布式凸优化算法(FDCOA).基于多智能体一致性理论和梯度跟踪技术,设计了一种非负余量迭代策略,使得FDCOA的控制步长收敛范围仅与智能体局部信息相关,进而实现控制步长的分布式设置.进一步分析了FDCOA在固定强连通和时变强连通网络情形下的收敛性.仿真结果表明本文构建的分布式控制步长选取方法对FDCOA在有向非平衡下的分布式凸优化问题是有效的.     

Robust distributed model predictive control of linear systems with structured time-varying uncertainties

In this work, synthesis of robust distributed model predictive control (MPC) is presented for a class of linear systems subject to structured time-varying uncertainties. By decomposing a global system into smaller dimensional subsystems, a set of distributed MPC controllers, instead of a centralised controller, are designed. To ensure the robust stability of the closed-loop system with respect to model uncertainties, distributed state feedback laws are obtained by solving a min–max optimisation problem. The design of robust distributed MPC is then transformed into solving a minimisation optimisation problem with linear matrix inequality constraints. An iterative online algorithm with adjustable maximum iteration is proposed to coordinate the distributed controllers to achieve a global performance. The simulation results show the effectiveness of the proposed robust distributed MPC algorithm.     

Fast adaptive algorithms and networks for class-separability features

In this article, we introduce accelerated algorithms for linear discriminant analysis (LDA) and feature extraction from unimodal multiclass Gaussian data. Current adaptive methods based on the gradient descent optimization technique use a fixed or a monotonically decreasing step size in each iteration, which results in a slow convergence rate. Here, we use a variable step size, optimally computed in each iteration using the steepest descent method, in order to accelerate the convergence of the algorithm. Based on the new adaptive algorithm, we present a self-organizing neural network for adaptive computation of the square root of the inverse covariance matrix (Σ^−1/2) and use it (i) in a network for optimal feature extraction from Gaussian data and (ii) in cascaded form with a principal component analysis network for LDA. Experimental results demonstrate fast convergence and high stability of the algorithm and justify its advantages for on-line pattern recognition applications with stationary and non-stationary input data.     

Distributed MPC for Reconfigurable Architecture Systems via Alternating Direction Method of Multipliers

This paper investigates the distributed model predictive control (MPC) problem of linear systems where the network topology is changeable by the way of inserting new subsystems, disconnecting existing subsystems, or merely modifying the couplings between different subsystems. To equip live systems with a quick response ability when modifying network topology, while keeping a satisfactory dynamic performance, a novel reconfiguration control scheme based on the alternating direction method of multipliers (ADMM) is presented. In this scheme, the local controllers directly influenced by the structure realignment are redesigned in the reconfiguration control. Meanwhile, by employing the powerful ADMM algorithm, the iterative formulas for solving the reconfigured optimization problem are obtained, which significantly accelerate the computation speed and ensure a timely output of the reconfigured optimal control response. Ultimately, the presented reconfiguration scheme is applied to the level control of a benchmark four-tank plant to illustrate its effectiveness and main characteristics.      

Nonlinear model predictive control of a magnetic levitation system

The paper presents a fast nonlinear model predictive control (MPC) scheme for a magnetic levitation system. A nonlinear dynamical model of the levitation system is derived that additionally captures the inductor current dynamics of the electromagnet in order to achieve a high MPC performance both for stabilization and fast setpoint changes of the levitating mass. The optimization algorithm underlying the MPC scheme accounts for control constraints and allows for a time and memory efficient computation of the single iteration. The overall control performance of the levitation system as well as the low computational costs of the MPC scheme is shown both in simulations and experiments with a sampling frequency of 700 Hz on a standard dSPACE hardware.     

Large-scale convex optimal control problems: time decomposition,incentive coordination, and parallel algorithm

A parallel algorithm based on time decomposition and incentive coordination is developed for long-horizon optimal control problems. This is done by first decomposing the original problem into subproblems with shorter time horizon, and then using the incentive coordination scheme to coordinate the interaction of subproblems. For strictly convex problems it is proved that the decomposed problem with linear incentive coordination is equivalent to the original problem, in the sense that each optimal solution of the decomposed problem produces one global optimal solution of the original problem and vice versa. In other words, linear incentive terms are sufficient in this case and impose no additional computation burden on the subproblems. The high-level parameter optimization problem is shown to be nonconvex, despite the uniqueness of the optimal solution and the convexity of the original problem. Nevertheless, the high-level problem has no local minimum, even though it is nonconvex. A parallel algorithm based on a prediction method is developed, and a numerical example is used to demonstrate the feasibility of the approach     

An improved robust model predictive control for linear parameter‐varying input‐output models

This paper describes a new robust model predictive control (MPC) scheme to control the discrete‐time linear parameter‐varying input‐output models subject to input and output constraints. Closed‐loop asymptotic stability is guaranteed by including a quadratic terminal cost and an ellipsoidal terminal set, which are solved offline, for the underlying online MPC optimization problem. The main attractive feature of the proposed scheme in comparison with previously published results is that all offline computations are now based on the convex optimization problem, which significantly reduces conservatism and computational complexity. Moreover, the proposed scheme can handle a wider class of linear parameter‐varying input‐output models than those considered by previous schemes without increasing the complexity. For an illustration, the predictive control of a continuously stirred tank reactor is provided with the proposed method.     

A parallel neuro-controller for DC motors containing nonlinear friction

This paper presents an application of a parallel neuro-controller for compensating the effects induced by the friction in a DC motor system. A back-propagation neural network based on a gradient descent algorithm is employed, and a bound on the tracking error is derived from the analysis of the tracking error dynamics. The parallel neuro-controller is a combination of a linear controller and a neural network controller which compensates for nonlinear friction. The proposed scheme is implemented and tested on an IBM PC-based DC motor control system. The algorithm, simulations, and experimental results are described. The results are relevant for many precision drives, such as those found in industrial robots.     

基于交替方向乘子法的非光滑损失坐标优化算法

交替方向乘子法(ADMM)在机器学习问题中已有一些实际应用。针对大规模数据的处理和非光滑损失凸优化问题,将镜面下降方法引入原ADMM批处理算法,得到了一种新的改进算法,并在此基础上提出了一种求解非光滑损失凸优化问题的坐标优化算法。该算法具有操作简单、计算高效的特点。通过详尽的理论分析,证明了新算法的收敛性,在一般凸条件下其具有目前最优的收敛速度。最后与相关算法进行了对比,实验结果表明该算法在保证解稀疏性的同时拥有更快的收敛速度。     

基于连续时间的二阶多智能体分布式资源分配算法

针对二阶多智能体系统中的分布式资源分配问题, 本文设计两种连续时间算法. 基于KKT (Karush?Kuhn?Tucker, 卡罗需?库恩?塔克)优化条件, 第一种控制算法利用节点局部不等式及其梯度信息来约束节点状态. 与上述梯度方法不同, 第二种控制算法包括一致性梯度下降法和固定时间收敛映射算子, 其中固定时间收敛映射算子确保算法的节点状态在固定时间收敛到局部约束集, 一致性梯度下降法目的是确保节点迭代到资源分配问题最优解. 两种控制算法都对状态无初始值约束, 且控制参数都是常数. 利用凸优化理论和固定时间李雅普诺夫方法, 分别分析了上述控制策略在有向平衡网络条件下的渐近和指数收敛性. 最后通过数值仿真验证了所设计算法在一维和高维资源分配问题的有效性.     

可扩展机器学习的并行与分布式优化算法综述

机器学习问题通常会转换成一个目标函数去求解,优化算法是求解目标函数中参数的重要工具.在大数据环境下,需要设计并行与分布式的优化算法,通过多核计算和分布式计算技术来加速训练过程.近年来,该领域涌现了大量研究工作,部分算法也在各机器学习平台得到广泛应用.本文针对梯度下降算法、二阶优化算法、邻近梯度算法、坐标下降算法、交替方向乘子算法五类最常见的优化方法展开研究,每一类算法分别从单机并行和分布式并行来分析相关研究成果,并从模型特性、输入数据特性、算法评价、并行计算模型等角度对每个算法进行详细对比.随后对有代表性的可扩展机器学习平台中优化算法的实现和应用情况进行对比分析.同时对本文中介绍的所有优化算法进行多层次分类,方便用户根据目标函数类型选择合适的优化算法,也可以通过该多层次分类图交叉探索如何将优化算法应用到新的目标函数类型.最后分析了现有优化算法存在的问题,提出可能的解决思路,并对未来研究方向进行展望.     

On the complexity of parallel coordinate descent

In this work we study the parallel coordinate descent method (PCDM) proposed by Richtárik and Taká? [Parallel coordinate descent methods for big data optimization, Math. Program. Ser. A (2015), pp. 1–52] for minimizing a regularized convex function. We adopt elements from the work of Lu and Xiao [On the complexity analysis of randomized block-coordinate descent methods, Math. Program. Ser. A 152(1–2) (2015), pp. 615–642], and combine them with several new insights, to obtain sharper iteration complexity results for PCDM than those presented in [Richtárik and Taká?, Parallel coordinate descent methods for big data optimization, Math. Program. Ser. A (2015), pp. 1–52]. Moreover, we show that PCDM is monotonic in expectation, which was not confirmed in [Richtárik and Taká?, Parallel coordinate descent methods for big data optimization, Math. Program. Ser. A (2015), pp. 1–52], and we also derive the first high probability iteration complexity result where the initial levelset is unbounded.     

Distributed model predictive control for polytopic uncertain systems subject to actuator saturation

In this paper, we present a distributed model predictive control (MPC) algorithm for polytopic uncertain systems subject to actuator saturation. The global system is decomposed into several subsystems. A set invariance condition for polytopic uncertain system with input saturation is identified and a min–max distributed MPC strategy is proposed. The distributed MPC controller is designed by solving a linear matrix inequalities (LMIs) optimization problem. An iterative algorithm is developed for making coordination among subsystems. Case studies are carried out to illustrate the effectiveness of the proposed algorithm.     

Distributed Model Predictive Control with Actuator Saturation for Markovian Jump Linear System

This paper is concerned with the distributed model predictive control (MPC) problem for a class of discrete-time Markovian jump linear systems (MJLSs) subject to actuator saturation and polytopic uncertainty in system matrices. The global system is decomposed into several subsystems which coordinate with each other. A set of distributed controllers is designed by solving a min-max optimization problem in terms of the solutions of linear matrix inequalities (LMIs). An iterative algorithm is developed to achieve the online computation. Finally, a simulation example is employed to show the effectiveness of the proposed algorithm.      

Synthesis of Mixed Objective Output Feedback Robust Model Predictive Control

Aiming at the constrained polytopic uncertain system with energy‐bounded disturbance and unmeasurable states, a novel synthesis scheme to design the output feedback robust model predictive control(MPC)is put forward by using mixed H₂/H_∞ design approach. The proposed scheme involves an offline design of a robust state observer using linear matrix inequalities(LMIs)and an online output feedback robust MPC algorithm using the estimated states in which the desired mixed objective robust output feedback controllers are cast into efficiently tractable LMI‐based convex optimization problems. In addition, the closed‐loop stability and the recursive feasibility of the proposed robust MPC are guaranteed through an appropriate reformulation of the estimation error bound (EEB). A numerical example subject to input constraints illustrates the effectiveness of the proposed controller.     

基于模型预测控制的含多微电网的能源互联网分布式协同优化

研究了预测不确定性条件下含多个微电网的能源互联网分布式协同调度策略.各微电网都拥有多种智能负荷,如功率可调负荷、可调度负荷和关键负荷;部分微电网含有分布式电源,如微型燃气轮机、风电机组、光伏发电系统等;且部分微电网还拥有储能设备,如电池储能系统.每个微电网都可当做一个独立的实体,拥有自己的运行目标,这些运行目标可表示成混合整数规划模型.提出了基于并行分布式优化的博弈模型以较小的信息通信量协调各微电网带有竞争性的运行目标.在此基础上,引入模型预测控制（MPC）机制以降低能源互联网中风、光等可再生能源输出、负荷需求及电价波动的不确定性产生的不利影响.算例证明了本文所提方法的可行性和有效性.