An algorithm for robust explicit/multi-parametric model predictive control

A new algorithm for robust explicit/multi-parametric Model Predictive Control (MPC) for uncertain, linear discrete-time systems is proposed. Based on previous work on Dynamic Programming (DP), multi-parametric Programming and Robust Optimization, the proposed algorithm features, (i) a DP reformulations of the MPC optimization problem, (ii) a robust reformulation of the constraints, and (iii) a multi-parametric programming step, where the control variables are obtained as explicit functions of the state variable, such that the state and input constraints are satisfied for all admissible values of the uncertainty. A key feature of the proposed procedure is that, as opposed to previous methods, it only solves a convex multi-parametric programming problem for each stage of the DP procedure.     

基于动态规划的约束优化问题多参数规划求解方法及应用

结合动态规划和单步多参数二次规划, 提出一种新的约束优化控制问题多参数规划求解方法. 一方面能得到约束线性二次优化控制问题最优控制序列与状态之间的显式函数关系, 减少多参数规划问题求解的工作量; 另一方面能够同时求解得到状态反馈最优控制律. 应用本文提出的多参数二次规划求解方法, 建立无限时间约束优化问题状态反馈显式最优控制律. 针对电梯机械系统振动控制模型做了数值仿真计算.     

Globally optimal nonlinear model predictive control based on multi-parametric disaggregation

Nonlinear model predictive control is appropriate for controlling highly nonlinear processes, particularly when operating conditions change frequently. If the problem is nonconvex, the controller must lead the process to a global, rather than a local optimum. This work deals with computation of the control actions which lead to the global optimum via the normalized multi-parametric disaggregation technique. The continuous process model is transformed into a nonlinear programming (NLP) problem via discretization which uses an implicit integration method. The NLP problem is relaxed into a mixed integer linear programming (MILP) model. Iterations between solving MILP (lower bound) and using its solution as a starting point for a local nonlinear optimizer (which computes the upper bound) continue until the gap is closed (an l₁-norm objective function is used). Controller performance is illustrated by several examples. Relative simplicity of the algorithm makes it possible to be implemented by a wide audience.     

Methodology for robust multi-parametric control in linear continuous-time systems

This paper presents an extension of the recent multi-parametric (mp-)NCO-tracking methodology by Sun et al. [Comput. Chem. Eng. 92 (2016) 64–77] for the design of robust multi-parametric controllers for constrained continuous-time linear systems in the presence of uncertainty. We propose a robust-counterpart formulation and solution of multi-parametric dynamic optimization (mp-DO), whereby the constraints are backed-off based on a worst-case propagation of the uncertainty using either interval analysis or ellipsoidal calculus and an ancillary linear state feedback. We address the case of additive uncertainty, and we discuss approaches to dealing with multiplicative uncertainty that retain tractability of the mp-NCO-tracking design problem, subject to extra conservativeness. In order to assist with the implementation of these controllers, we also investigate the use of data classifiers based on deep learning for approximating the critical regions in continuous-time mp-DO problems, and subsequently searching for a critical region during on-line execution. We illustrate these developments with the case studies of a fluid catalytic cracking (FCC) unit and a chemical reactor cascade.     

基于多参数规划的显式模型预测系统设计的可行域扩张算法

基于约束线性优化控制问题的多参数二次规划求解方法, 提出设计显式模型预测控制系统的可行域逐步扩张算法. 首先建立一种求取优化控制问题输出不变集的迭代算法. 以该输出不变集作为多参数规划问题中状态区域约束限制的初始条件, 通过反复求解多参数规划问题和不断改变状态区域约束限制, 能够逐步扩大显式模型预测控制系统的无限时间可行区域, 直到可行域不再继续扩大. 算法收敛时设计得到的显式模型预测控制系统在其所有的状态分区上都是无限时间可行的. 通过数值仿真计算, 验证本文提出算法的有效性.     

Explicit output-feedback nonlinear predictive control based on black-box models

Nonlinear model predictive control (NMPC) algorithms are based on various nonlinear models. A number of on-line optimization approaches for output-feedback NMPC based on various black-box models can be found in the literature. However, NMPC involving on-line optimization is computationally very demanding. On the other hand, an explicit solution to the NMPC problem would allow efficient on-line computations as well as verifiability of the implementation. This paper applies an approximate multi-parametric nonlinear programming approach to explicitly solve output-feedback NMPC problems for constrained nonlinear systems described by black-box models. In particular, neural network models are used and the optimal regulation problem is considered. A dual-mode control strategy is employed in order to achieve an offset-free closed-loop response in the presence of bounded disturbances and/or model errors. The approach is applied to design an explicit NMPC for regulation of a pH maintaining system. The verification of the NMPC controller performance is based on simulation experiments.     

An algorithm for multi-parametric quadratic programming and explicit MPC solutions

Explicit solutions to constrained linear model predictive control problems can be obtained by solving multi-parametric quadratic programs (mp-QP) where the parameters are the components of the state vector. We study the properties of the polyhedral partition of the state space induced by the multi-parametric piecewise affine solution and propose a new mp-QP solver. Compared to existing algorithms, our approach adopts a different exploration strategy for subdividing the parameter space, avoiding unnecessary partitioning and QP problem solving, with a significant improvement of efficiency.     

Stabilizing low complexity feedback control of constrained piecewise affine systems

Piecewise affine (PWA) systems are powerful models for describing both non-linear and hybrid systems. One of the key problems in controlling these systems is the inherent computational complexity of controller synthesis and analysis, especially if constraints on states and inputs are present. In addition, few results are available which address the issue of computing stabilizing controllers for PWA systems without placing constraints on the location of the origin.This paper first introduces a method to obtain stability guarantees for receding horizon control of discrete-time PWA systems. Based on this result, two algorithms which provide low complexity state feedback controllers are introduced. Specifically, we demonstrate how multi-parametric programming can be used to obtain minimum-time controllers, i.e., controllers which drive the state into a pre-specified target set in minimum time. In a second segment, we show how controllers of even lower complexity can be obtained by separately dealing with constraint satisfaction and stability properties. To this end, we introduce a method to compute PWA Lyapunov functions for discrete-time PWA systems via linear programming. Finally, we report results of an extensive case study which justify our claims of complexity reduction.     

A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry

The molten iron allocation problem (MIAP) is to allocate molten iron from blast furnaces to steel-making furnaces. The allocation needs to observe the release times of the molten iron defined by the draining plan of the blast furnaces and the transport time between the iron-making and steel-making stages. Time window constraints for processing the molten iron must be satisfied to avoid freezing. The objective is to find a schedule with minimum total weighted completion time. This objective reflects the practical consideration of improving steel-making efficiency and reducing operation cost caused by the need for reheating. Such a problem can be viewed as a parallel machine scheduling problem with time windows which is known to be NP-hard. In this paper, we first formulate the molten iron allocation problem as an integer programming model and then reformulate it as a set partitioning model by applying the Dantzig–Wolfe decomposition. We solve the problem using a column generation-based branch-and-price algorithm. Since the subproblem of column generation is still NP-hard, we propose a state-space relaxation-based dynamic programming algorithm for the subproblem. Computational experiments demonstrate that the proposed algorithm is capable of solving problems with up to 100 jobs to optimality within a reasonable computation time.     

构造移动通信中降低能耗的前缀码的动态规划加速

动态规划是一种常用的寻找问题最优解的算法设计方案。当将动态规划中的各个子问题考虑成有向图上的节点时,我们可以将动态规划看作是一个有向无圈图。一些问题的动态规划的有向无圈图有着特殊的结构,我们可以利用这些结构加速动态规划。本文考虑了一种从基站将能源"转移"到移动通信宿主的二进制编码方案构造时采用的动态规划。移动通信中,常常需要考虑优化通信编码方案来降低移动通信宿主的能耗。本文研究的编码方案通过以下方式降低能耗:基站猜测移动通信宿主所要发出的信息并询问宿主,而宿主则在一定的情况下才做出回应,以此来降低宿主发送信息的能耗。对于有n个单词的编码,我们的算法比之前提出的算法降低了O(n2)的时间复杂度。     

Tight complexity analysis of the relocation problem with arbitrary release dates

The paper considers makespan minimization on a single machine subject to release dates in the relocation problem, originated from a resource-constrained redevelopment project in Boston. Any job consumes a certain amount of resource from a common pool at the start of its processing and returns to the pool another amount of resource at its completion. In this sense, the type of our resource constraints extends the well-known constraints on resumable resources, where the above two amounts of resource are equal for each job. In this paper, we undertake the first complexity analysis of this problem in the case of arbitrary release dates. We develop an algorithm, based on a multi-parametric dynamic programming technique (when the number of parameters that undergo enumeration of their values in the DP-procedure can be arbitrarily large). It is shown that the algorithm runs in pseudo-polynomial time when the number m of distinct release dates is bounded by a constant. This result is shown to be tight: (1) it cannot be extended to the case when m is part of the input, since in this case the problem becomes strongly NP-hard, and (2) it cannot be strengthened up to designing a polynomial time algorithm for any constant m>1, since the problem remains NP-hard for m=2. A polynomial-time algorithm is designed for the special case where the overall contribution of each job to the resource pool is nonnegative. As a counterpart of this result, the case where the contributions of all jobs are negative is shown to be strongly NP-hard.     

Mixed coordination method for long-horizon optimal control problems

We present a new approach to solving long-horizon, discrete-time optimal control problems using the mixed coordination method. The idea is to decompose a long-horizon problem into subproblems along the time axis. The requirement that the initial state of a subproblem equal the terminal state of the preceding subproblem is relaxed by using Lagrange multipliers. The Lagrange multipliers and initial state of each subproblem are then selected as high-level variables. The equivalence of the two-level formulation and the original problem is proved for both convex and non-convex cases. The low-level subproblems are solved in parallel using extended differential dynamic programming (DDP). An efficient way to find the gradient and hessian of a low-level objective function with respect to high-level variables is developed. The high-level problem is solved using the modified Newton method. An effective procedure is developed to select initial values of multipliers based on the initial trajectory. The method can convexify the high-level problem while maintaining the separability of an originally non-convex problem. The method performs better and faster than one-level DDP for both convex and non-convex test problems.     

Application of an explicit min-max MPC to a scaled laboratory process

Min-max model predictive control (MMMPC) requires the on-line solution of a min-max problem, which can be computationally demanding. The piecewise affine nature of MMMPC has been proved for linear systems with quadratic performance criterion. This paper shows how to move most computations off-line obtaining the explicit form of this control law by means of a heuristic algorithm. These results are illustrated with an application to a scaled laboratory process with dynamics fast enough to preclude the use of numerical solvers.     

基于伪谱法的滑翔轨迹多级迭代优化策略

伪谱法可实时求解具有高度非线性动态特性的飞行器最优轨迹;以X-51A相似飞行器模型为研究对象,采用增量法与查表插值建立纵向气动力模型,伪谱法与序列二次规划算法求解滑翔轨迹最优控制问题;提出使用多级迭代优化策略,为序列二次规划算法求解伪谱法参数化得到的大规模非线性规划问题提供初值,弥补序列二次规划算法在求解大规模非线性规划问题过程中,出现的初值敏感、收敛速度减慢等问题。通过与传统方法求解出的状态量与控制量仿真飞行状态进行对比,证明了多级迭代优化策略的有效性和高效性,该策略在实际工程应用中取得了良好效果。     

多指标动态规划的交互式满意置换率法

提出了一种新的求解多指标动态规划问题的算法,它是由多目标静态规划的交互式满意 置换率法[1]推广得到的.通过增加附加状态变量进行数学模型转换,将单指标动态规划问题 转化为静态规划问题,再进行迭代.这样既减少了计算量,又使各指标间的置换关系易于求 得.所提方法在人机交互过程中对决策者的要求不高,对于一类常见的多指标动态规划问题, 可以迅速获得满意的解.     

Adaptive composite suboptimal control for linear singularly perturbed systems with unknown slow dynamics

In this article, using singular perturbation theory and adaptive dynamic programming (ADP) approach, an adaptive composite suboptimal control method is proposed for linear singularly perturbed systems (SPSs) with unknown slow dynamics. First, the system is decomposed into fast‐ and slow‐subsystems and the original optimal control problem is reduced to two subproblems in different time‐scales. Afterward, the fast subproblem is solved based on the known model of the fast‐subsystem and a fast optimal control law is designed by solving the algebraic Riccati equation corresponding to the fast‐subsystem. Then, the slow subproblem is reformulated by introducing a system transformation for the slow‐subsystem. An online learning algorithm is proposed to design a slow optimal control law by using the information of the original system state in the framework of ADP. As a result, the obtained fast and slow optimal control laws constitute the adaptive composite suboptimal control law for the original SPSs. Furthermore, convergence of the learning algorithm, suboptimality of the adaptive composite suboptimal control law and stability of the whole closed‐loop system are analyzed by singular perturbation theory. Finally, a numerical example is given to show the feasibility and effectiveness of the proposed methods.     

A trust-region algorithm combining line search filter technique for nonlinear constrained optimization

In this paper, we propose a trust-region algorithm in association with line search filter technique for solving nonlinear equality constrained programming. At current iteration, a trial step is formed as the sum of a normal step and a tangential step which is generated by trust-region subproblem and the step size is decided by interior backtracking line search together with filter methods. Then, the next iteration is determined. This is different from general trust-region methods in which the next iteration is determined by the ratio of the actual reduction to the predicted reduction. The global convergence analysis for this algorithm is presented under some reasonable assumptions and the preliminary numerical results are reported.     

Neurodynamic programming and tracking control scheme of constrained-input systems via a novel event-triggered PI algorithm

In this paper, a new event-triggered approach for neurodynamic programming and optimal tracking control problem of constrained-input systems is proposed, where the desired trajectory can be generated as a large class of useful command trajectories. Firstly, the complex tracking problem is converted to a stabilizing control optimization problem by reconstructing a novel augmented tracking system with discounted performance index. Secondly, instead of the conventional time-driven control, an event-triggered policy iteration (PI) algorithm is designed to drive the system dynamic to track the reference trajectory, which requires less computation and fewer transmissions during the solving. Thirdly, the novel tracking control can be bounded as desired, which overcomes the unconstrained steady-state control from the general adaptive dynamic programming based tracking solution. Moreover, only critic neural network is used in the implementation of iteration learning, which simplifies the actor-critic architecture and reduces computational load. And by the means of Lyapunov method, the ultimately boundedness of the tracking system under the event-triggered PI algorithm is proved. Finally, the developed approach is applied to track a sinusoidal waveform and a periodic rectangular step signal in the simulations, where the effectiveness is also demonstrated.     

连铸-轧制混流生产模式下轧批调度问题的分支-定价算法

研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.     

Optimal control of a deterministic multiclass queuing system for which several queues can be served simultaneously

We consider the optimal control problem of emptying a deterministic single server multiclass queuing system without arrivals. We assume that the server is able to serve several queues simultaneously, each at its own rate, independent of the number of queues being served.We show that the optimal sequence of modes is ordered by the rate of cost decrease. However, queues are not necessarily emptied. We propose a dynamic programming approach for solving the problem, which reduces the multi-parametric QP (mpQP) to a series of problems that can be solved readily.