Search

The articles in this special issue focus on security and privacy of distributed algorithms and network systems. The integration of computation, communication, and control technologies has led to the widespread emergence of large scale engineering systems. These network systems are deployed in numerous fields, including electric and smart grids, transportation and smart cities, health-care and manufacturing, and so forth. Due to the rapid growth in number of geographically deployed units, such as sensors, computers and controllers, traditional centralized control and optimization algorithms may not be efficient, robust, or even applicable at all. Instead, distributed control and optimization algorithms offer a promising and desirable approach to operate and guarantee the well functioning of network systems. The aim of this special issue is to provide a window into the recent developments of the fundamentals and applications of security and privacy of distributed algorithms in network systems. [ABSTRACT FROM AUTHOR]

This paper considers the quadratic control problem of discrete-time Markov jump linear systems with constraints on the norm of the state and control variables. We assume that the Markov chain parameter is not available, and instead, there is a detector, which emits signals providing information on this parameter. It is desired to derive a feedback linear control using the information provided by this detector in order to stochastically stabilize the closed-loop system, satisfy the constraints whenever the initial conditions belong to an invariant set, and minimize an upper bound for the quadratic cost. We show that a linear matrix inequality (LMI) optimization problem can be formulated in order to obtain a solution for this problem. Two other related problems, one for minimizing the guaranteed quadratic cost considering fixed initial conditions and the other for maximizing an estimate of the domain of an invariant set, can also be formulated using our LMI approach. This paper is concluded with some numerical simulations. [ABSTRACT FROM AUTHOR]

We study in this paper, a class of constrained linear-quadratic (LQ) optimal control problem formulations for the scalar-state stochastic system with multiplicative noise, which has various applications, especially in the financial risk management. The linear constraint on both the control and state variables considered in our model destroys the elegant structure of the conventional LQ formulation and has blocked the derivation of an explicit control policy so far in the literature. We successfully derive in this paper, the analytical control policy for such a class of problems by utilizing the state separation property induced from its structure. We reveal that the optimal control policy is a piecewise affine function of the state and can be computed offline efficiently by solving two coupled Riccati equations. Under some mild conditions, we also obtain the stationary control policy for an infinite time horizon. We demonstrate the implementation of our method via some illustrative examples and show how to calibrate our model to solve dynamic constrained portfolio optimization problems. [ABSTRACT FROM AUTHOR]

In a discrete time nonhomogeneous Markov chain (TNHMC), the states spaces, transition probabilities, and reward functions at different times may be different. In this paper, with the confluencity previously introduced, we show that the states of a TNHMC can be classified into the branching states and a number of classes of confluent states (versus the transient and recurrent states in the time homogeneous case). The optimization of average reward in TNHMC's consisting of a single confluent class (uni-chain) have been addressed in a previous paper by the author. In this paper, we show that with confluencity and the state classification and under some bound conditions, we can obtain the necessary and sufficient conditions for optimal policies of the average reward of TNHMCs consisting of multiple confluent classes (multi-chains). Just like in the uni-chain TNHMC case, the sufficient condition does not need to hold in any “zero frequently visited” time sequence. This “under-selectivity” makes the problem not amenable to dynamic programming. A direct comparison based approach is used to prove the results. The results enhance our understanding of state classification and performance optimization with the notion of confluencity. [ABSTRACT FROM AUTHOR]

We study distributed optimization to minimize a sum of smooth and strongly-convex functions. Recent work on this problem uses gradient tracking to achieve linear convergence to the exact global minimizer. However, a connection among different approaches has been unclear. In this paper, we first show that many of the existing first-order algorithms are related with a simple state transformation, at the heart of which lies a recently introduced algorithm known as  $\mathcal {AB}$. We then present distributed heavy-ball, denoted as  $\mathcal {AB}m$ , that combines  $\mathcal {AB}$ with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both row- and column-stochastic weights,  $\mathcal {AB}m$ removes the conservatism in the related work due to doubly stochastic weights or eigenvector estimation.  $\mathcal {AB}m$ thus naturally leads to optimization and average consensus over both undirected and directed graphs. We show that  $\mathcal {AB}m$ has a global $R$ -linear rate when the largest step-size and momentum parameter are positive and sufficiently small. We numerically show that  $\mathcal {AB}m$ achieves acceleration, particularly when the objective functions are ill-conditioned. [ABSTRACT FROM AUTHOR]

This paper presents the stability and criticality analysis of integer linear programs with respect to perturbations in stochastic data given as Markov chains. These perturbations affect the initial distribution, the transition matrix, or the stationary distribution of Markov chains. Stability analysis is concerned with obtaining the set of all perturbations for which a solution remains optimal. This paper gives expressions for stability regions for perturbations in the initial distribution, the transition matrix, the stationary distribution, and the product of elements of the transition matrix and the stationary distribution. Furthermore, criticality measures that describe the sensitivity of the objective function with respect to an element of the problem data are derived. Stability regions that preserve the stochasticity of the problem data are given. Finally, stability regions for perturbations of elements of the transition matrix, given that the problem is not linear in the initial distribution or the transition matrix, are obtained using a small perturbation analysis. The results are applied to sensor placement problems and numerical examples are given. [ABSTRACT FROM PUBLISHER]

The paper considers normalized gradient descent (NGD), a natural modification of classical gradient descent (GD) in optimization problems. It is shown that, contrary to GD, NGD escapes saddle points “quickly.” A serious shortcoming of GD in nonconvex problems is that it can take arbitrarily long to escape from the neighborhood of a saddle point. In practice, this issue can significantly slow the convergence of GD, particularly in high-dimensional nonconvex problems. The paper focuses on continuous-time dynamics. It is shown that 1) NGD “almost never” converges to saddle points and 2) the time required for NGD to escape from a ball of radius $r$ about a saddle point $x^*$ is at most $5\sqrt{\kappa }r$ , where $\kappa$ is the condition number of the Hessian of $f$ at $x^*$. As a simple application of these results, a global convergence-time bound is established for NGD under mild assumptions. [ABSTRACT FROM AUTHOR]

Recently, Thompson sampling has been shown to achieve good theoretical performance guarantees for stochastic control problems with parameter uncertainty when the state, control, and parameter spaces are all finite. Much less is known however about the performance of Thompson sampling when applied to continuous or more general spaces, which constitutes an important class of problems in practice. In this paper, we study Thompson sampling when applied to a broad class of average cost stochastic control problems where the state, control, and parameter spaces are all general measurable spaces. The main contributions of our paper are establishing theoretical performance guarantees for Thompson sampling as measured by: first, expected posterior sampling error; and second, average per period regret. [ABSTRACT FROM AUTHOR]

In this paper, we address the so-called Liouville control problem for discrete-time SISO linear systems in the class of Gaussian distributions. In particular, we propose a systematic procedure for the characterization of a dynamic output feedback policy that will transfer the output of the system, which is a known Gaussian random variable, to a goal Gaussian distribution after a finite number of stages. In the proposed approach, the Liouville control problem is reduced to two decoupled (finite-dimensional) quadratic programs, one of which is subject to a single affine constraint, which is a convex program, whereas the other one is subject to a single quadratic equality constraint. Despite the fact that the second optimization problem is not convex, one can characterize its exact solution via a systematic procedure without resorting to convex relaxation techniques, which may yield suboptimal or even infeasible solutions to the original (nonconvex) optimization problem. Finally, we present numerical simulations that illustrate the key ideas of this paper. [ABSTRACT FROM AUTHOR]

This paper deals with the estimation of convergence rate and domain of attraction of control-Lyapunov functions in Lyapunov-based control. This pair of estimation problems has been considered only for input-affine systems with constraints on the input norm. In this paper, we propose a novel optimization framework to address the estimation of convergence rate and domain of attraction. Specifically, we formulate the estimation problems as min–max bilevel programs for the decay rate of the Lyapunov function, where the inner problem can be resolved using Karush–Kuhn–Tucker optimality conditions, and the resulting single-level programs can be transformed into and solved as mixed-integer nonlinear programs. The proposed approach is applicable to systems with input-nonaffinity or more general forms of input constraints under an input-convexity assumption. [ABSTRACT FROM AUTHOR]

Checking validity of a model is a crucial step in the process of system identification. This is especially true when dealing with switched affine systems since, in this case, the problem of system identification from noisy data is known to be generically NP-Hard and can only be solved in practice by using heuristics and relaxations. Therefore, before the identified models can be used for instance for controller design, they should be systematically validated against additional experimental data. In this paper we address the problem of model (in)validation for multi-input multi-output switched affine systems in output error form with unknown switches. As a first step, we prove that necessary and sufficient invalidation certificates can be obtained by solving a sequence of convex optimization problems. In principle, these problems involve increasingly large matrices. However, as we show in the paper by exploiting recent results from semialgebraic geometry, the proposed algorithm is guaranteed to stop after a finite number of steps that can be be explicitly computed from the a priori information. In addition, this algorithm exploits the sparse structure of the underlying optimization problem to substantially reduce the computational burden. The effectiveness of the proposed method is illustrated using both academic examples and a non-trivial problem arising in computer vision: activity monitoring. [ABSTRACT FROM AUTHOR]

In this paper, we present a unified framework for solving a general class of problems arising in the context of set-membership estimation/identification theory. More precisely, the paper aims at providing an original approach for the computation of optimal conditional and robust projection estimates in a nonlinear estimation setting, where the operator relating the data and the parameter to be estimated is assumed to be a generic multivariate polynomial function, and the uncertainties affecting the data are assumed to belong to semialgebraic sets. By noticing that the computation of both the conditional and the robust projection optimal estimators requires the solution to min-max optimization problems that share the same structure, we propose a unified two-stage approach based on semidefinite-relaxation techniques for solving such estimation problems. The key idea of the proposed procedure is to recognize that the optimal functional of the inner optimization problems can be approximated to any desired precision by a multivariate polynomial function by suitably exploiting recently proposed results in the field of parametric optimization. Two simulation examples are reported to show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

The aim of this paper is to approximate a Finite-State Markov (FSM) process by another process defined on a lower dimensional state space, called the approximating process, with respect to a total variation distance fidelity criterion. The approximation problem is formulated as an optimization problem using two different approaches. The first approach is based on approximating the transition probability matrix of the FSM process by a lower-dimensional transition probability matrix, resulting in an approximating process which is a Finite-State Hidden Markov (FSHM) process. The second approach is based on approximating the invariant probability vector of the original FSM process by another invariant probability vector defined on a lower-dimensional state space. Going a step further, a method is proposed based on optimizing a Kullback-Leibler divergence to approximate the FSHM processes by FSM processes. The solutions of these optimization problems are described by optimal partition functions which aggregate the states of the FSM process via a corresponding water-filling solution, resulting in lower-dimensional approximating processes which are FSHM or FSM processes. Throughout the paper, the theoretical results are justified by illustrative examples that demonstrate our proposed methodology. [ABSTRACT FROM AUTHOR]

This paper is concerned with the optimal distributed control (ODC) problem for linear discrete-time deterministic and stochastic systems. The objective is to design a static distributed controller with a prespecified structure that is globally optimal with respect to a quadratic cost functional. It is shown that this NP-hard problem has a quadratic formulation, which can be relaxed to a semidefinite program (SDP). If the SDP relaxation has a rank-1 solution, a globally optimal distributed controller can be recovered from this solution. By utilizing the notion of treewidth, it is proved that the nonlinearity of the ODC problem appears in such a sparse way that an SDP relaxation of this problem has a matrix solution with rank at most 3. Since the proposed SDP relaxation is computationally expensive for a large-scale system, a computationally cheap SDP relaxation is also developed with the property that its objective function indirectly penalizes the rank of the SDP solution. Various techniques are proposed to approximate a low-rank SDP solution with a rank-1 matrix, leading to near globally optimal controllers together with a bound on the optimality degree of each controller. The above results are developed for both finite-horizon and infinite-horizon ODC problems. The SDP relaxations developed in this work are exact for the design of a centralized controller, hence serving as an alternative for solving Riccati equations. The efficacy of the proposed SDP relaxations is elucidated through a case study on the distributed frequency control of power systems. [ABSTRACT FROM PUBLISHER]

The paper proposes an identification procedure for autoregressive Gaussian stationary stochastic processes under the assumption that the manifest (or observed) variables are nearly independent when conditioned on a limited number of latent (or hidden) variables. The method exploits the sparse plus low-rank decomposition of the inverse of the manifest spectral density and the efficient convex relaxations recently proposed for such decompositions. [ABSTRACT FROM PUBLISHER]

In this paper, we present a framework for risk-sensitive model predictive control (MPC) of linear systems affected by stochastic multiplicative uncertainty. Our key innovation is to consider a time-consistent, dynamic risk evaluation of the cumulative cost as the objective function to be minimized. This framework is axiomatically justified in terms of time-consistency of risk assessments, is amenable to dynamic optimization, and is unifying in the sense that it captures a full range of risk preferences from risk neutral (i.e., expectation) to worst case. Within this framework, we propose and analyze an online risk-sensitive MPC algorithm that is provably stabilizing. Furthermore, by exploiting the dual representation of time-consistent, dynamic risk measures, we cast the computation of the MPC control law as a convex optimization problem amenable to real-time implementation. Simulation results are presented and discussed. [ABSTRACT FROM AUTHOR]

This paper investigates the distributed computation of the well-known linear matrix equation in the form of ${{AXB}} = F$ , with the matrices $A$ , $B$ , $X$ , and $F$ of appropriate dimensions, over multiagent networks from an optimization perspective. In this paper, we consider the standard distributed matrix-information structures, where each agent of the considered multiagent network has access to one of the subblock matrices of $A$ , $B$ , and $F$. To be specific, we first propose different decomposition methods to reformulate the matrix equations in standard structures as distributed constrained optimization problems by introducing substitutional variables; we show that the solutions of the reformulated distributed optimization problems are equivalent to least squares solutions to original matrix equations; and we design distributed continuous-time algorithms for the constrained optimization problems, even by using augmented matrices and a derivative feedback technique. Moreover, we prove the exponential convergence of the algorithms to a least squares solution to the matrix equation for any initial condition. [ABSTRACT FROM AUTHOR]

This paper is concerned with the optimal static distributed control problem for linear discrete-time deterministic and stochastic systems. The objective is to design a stabilizing static distributed controller whose performance is close to that of the optimal centralized controller. To this end, we first consider deterministic systems, where the initial state is either given or belongs to a known bounded region. Given an arbitrary centralized controller, we derive a condition under which there exists a distributed controller that generates input and state trajectories close to their counterparts in the centralized closed-loop system. This condition for the design of a distributed controller is translated into an optimization problem, where the optimal objective value of this problem quantifies the closeness of the designed distributed and given centralized control systems. The results are then extended to stochastic systems that are subject to input disturbance and measurement noise. The proposed optimization problem has a closed-form solution (explicit formula) and can be efficiently solved for large-scale systems. The mathematical framework developed in this paper is utilized to design a near-globally optimal distributed controller based on the optimal centralized controller, and strong theoretical lower bounds on the global optimality guarantee of the obtained distributed controller are derived. We show that if the optimal objective value of the proposed convex program is sufficiently small, the designed controller is stabilizing and nearly globally optimal. To illustrate the results, case studies on aircraft formation and frequency control of power systems are offered. [ABSTRACT FROM AUTHOR]

This paper considers the problem of selecting the top-m designs using simulation with input uncertainty. The performance of each design is measured by its worst case performance. The objective of this paper is to maximize the probability of correctly selecting the top-m designs given a fixed simulation budget. Due to the complexity of probability of correct selection (PCS), we develop a lower bound for the PCS and derive an asymptotically optimal budget allocation rule. Useful insights on characterizing the efficient budget allocation rule with input uncertainty are provided. Meanwhile, a sequential simulation procedure is suggested to implement the allocation rule. A series of numerical experiments indicate that the proposed simulation budget allocation rule can outperform all existing selection rules. [ABSTRACT FROM AUTHOR]

This paper presents a human-inspired control approach to bipedal robotic walking: utilizing human data and output functions that appear to be intrinsic to human walking in order to formally design controllers that provably result in stable robotic walking. Beginning with human walking data, outputs—or functions of the kinematics—are determined that result in a low-dimensional representation of human locomotion. These same outputs can be considered on a robot, and human-inspired control is used to drive the outputs of the robot to the outputs of the human. The main results of this paper are that, in the case of both under and full actuation, the parameters of this controller can be determined through a human-inspired optimization problem that provides the best fit of the human data while simultaneously provably guaranteeing stable robotic walking for which the initial condition can be computed in closed form. These formal results are demonstrated in simulation by considering two bipedal robots—an underactuated 2-D bipedal robot, AMBER, and fully actuated 3-D bipedal robot, NAO—for which stable robotic walking is automatically obtained using only human data. Moreover, in both cases, these simulated walking gaits are realized experimentally to obtain human-inspired bipedal walking on the actual robots. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the l\infty gain characterizations of linear switched systems (LSS) and present various relevant results on their exact computation and optimization. Depending on the role of the switching sequence, we study two broad cases: first, when the switching sequence attempts to maximize, and second, when it attempts to minimize the l\infty gain. The first, named as worst-case throughout the paper, can be related to robustness of the system to uncontrolled switching; the second relates to situations when the switching can be part to the overall decision making. Although, in general, the exact computation of l\infty gains is difficult, we provide specific classes, the input-output switching systems, for which it is shown that linear programming can be used to obtain the worst-case l\infty gain. This is a sufficiently rich class of systems as any stable LSS can be approximated by one. Certain applications to robust control design are provided where we show that a switched compensation independently of the plant has no advantage over a linear time invariant (LTI) compensation, and further, if the plant is strictly causal, even a switched compensation which has a matched switching with the plant does not provide a better performance over an LTI compensation. Also, we present a new necessary and sufficient condition to check the stability of LSS in form of a model matching problem. On the other hand, if one is interested in minimizing the l\infty gain over the switching sequences, we show that, for finite impulse response (FIR) switching systems the minimizing switching sequence can be chosen to be periodic. For input-only or output-only switching an exact, readily computable, characterization of the minimal l\infty gain is provided, and it is shown that the minimizing switching sequence is constant, which, as also shown, is not true for input-output switching. [ABSTRACT FROM AUTHOR]

This paper proposes an equalization approach to mean-square (MS) feedback stabilization for multi-input/multi-output (MIMO) discrete-time systems over fading channels. An orthogonal encode/decode matrix pair is placed at the two ends of the fading channel, thereby equalizing the complementary sensitivity in the MS sense. By adopting the notion of the MS stability in an input-output setting, and using the signal-to-noise ratio (SNR) and encode/decode matrix as additional design parameters, we are able to convert the networked stabilization over fading channels into an equivalent constrained \mathcal H2 optimal control, and derive the MS stabilizability conditions over linear time-invariant controllers. Our results recover the existing MS stabilizability condition under the state feedback. For output feedback control, we provide a characterization of the minimum network resource for the SNR required to stabilize the networked control system over the fading channel, and develop the synthesis algorithms for design of the orthogonal coding matrix and output feedback controller in different scenarios. Our results show that the MS stabilization problem as formulated in this paper admits the closed-form solution for MIMO plants with unstable block zeros, and is mathematically tractable for more general MIMO plants. Two numerical examples are worked out to illustrate our results. [ABSTRACT FROM PUBLISHER]

Consider a connected network of agents endowed with local cost functions representing private objectives. Agents seek to find an agreement on some minimizer of the aggregate cost, by means of repeated communications between neighbors. Consensus on the average over the network, usually addressed by gossip algorithms, is a special instance of this problem, corresponding to quadratic private objectives. Consensus on the median, or more generally, consensus on a given quantile, is also a special instance of this problem. In this paper we show that optimizing the aggregate cost function regularized by a total variation (TV) term has appealing properties. First, it can be done very naturally in a distributed way, yielding algorithms that are efficient on numerical simulations. Secondly, the optimum for the regularized cost is shown to be also the optimum for the initial aggregate cost function under assumptions that are simple to state. Finally, these algorithms are robust to unreliable agents that keep injecting some false value in the network. This is remarkable enough, and is not the case, for instance, of gossip algorithms that are entirely ruled by unreliable agents as detailed in the paper. [ABSTRACT FROM PUBLISHER]

The first part of this note identifies and analyzes two weak points of the commented paper refid="ref1"/. i) Example 1 reports an incorrect result for which we provide a complete explanation and correction. ii) The practical use of Theorem 1 reveals major drawbacks such as a severe limitation in the applicability (due to the restrictive conditions requested by the hypothesis) and a relatively low accuracy of the results (i.e., rough values for the right outer bounds of the eigenvalue ranges of interval matrices). The second part of the note presents three methods that circumvent the use of Theorem 1 refid="ref1"/ and provide the following information about the eigenvalue range of an interval matrix: \bullet a right outer bound—relying on an inequality proved by J. Rohn (see References); \bullet the right end point—by solving a constrained global maximization problem; \bullet a right outer bound (for arbitrary interval matrices) and the right end point (for some classes of interval matrices)—by calculating the spectral abscissa of a constant matrix that majorizes the considered interval matrix. For illustration by numerical examples, throughout the note we use three interval matrices related to Example 1 from the commented paper. [ABSTRACT FROM AUTHOR]

In this paper, we consider the regularized version of the Jacobi algorithm, a block coordinate descent method for convex optimization with an objective function consisting of the sum of a differentiable function and a block-separable function. Under certain regularity assumptions on the objective function, this algorithm has been shown to satisfy the so-called sufficient decrease condition, and consequently, to converge in objective function value. In this paper, we revisit the convergence analysis of the regularized Jacobi algorithm and show that it also converges in iterates under very mild conditions on the objective function. Moreover, we establish conditions under which the algorithm achieves a linear convergence rate. [ABSTRACT FROM PUBLISHER]

In model predictive control (MPC), the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem at each sample in the control loop. The main computational effort when solving the CFTOC problem using an active-set (AS) method is often spent on computing the search directions, which in MPC corresponds to solving unconstrained finite-time optimal control (UFTOC) problems. This is commonly performed using Riccati recursions or generic sparsity exploiting algorithms. In this paper, the focus is efficient search direction computations for AS type methods. The system of equations to be solved at each AS iteration is changed only by a low-rank modification of the previous one, and exploiting this structured change is important for the performance of AS-type solvers. In this paper, theory for how to exploit these low-rank changes by modifying the Riccati factorization between AS iterations in a structured way is presented. A numerical evaluation of the proposed algorithm shows that the computation time can be significantly reduced by modifying, instead of re-computing, the Riccati factorization. This speedup can be important for AS-type solvers used for linear, nonlinear, and hybrid MPC. [ABSTRACT FROM PUBLISHER]

This paper explores optimal control problems with $l_1$ objectives involving linear discrete-time systems. These problems can be efficiently solved as linear programs. They also have previously been shown to yield sparse solutions, including idle or deadbeat solutions where the input or output is respectively zero along the entire control horizon. The main contribution of this paper is to derive conditions on the problem parameters that specify when idle or deadbeat solutions occur. These results, based on analyzing the dual problem, demonstrate how different types of sparse solutions result from the choice of the problem parameters and, as a consequence, may guide the design of controllers employing $l_1$ objectives. [ABSTRACT FROM PUBLISHER]

This paper is concerned with distributed learning and optimization in large-scale settings. The well-known fictitious play (FP) algorithm has been shown to achieve Nash equilibrium learning in certain classes of multiagent games. However, FP can be computationally difficult to implement when the number of players is large. Sampled FP (SFP) is a variant of FP that mitigates the computational difficulties arising in FP by using a Monte Carlo (i.e., sampling based) approach. Despite its computational advantages, a shortcoming of SFP is that the number of samples that must be drawn at each iteration grows without bound as the algorithm progresses. In this paper, we propose single sample FP (SSFP)—A variant of SFP in which only one sample needs to be drawn in each round of the algorithm. Convergence of SSFP to the set of Nash equilibria is proven. Simulation results show the performance of SSFP is comparable to that of SFP, despite drawing far fewer samples. [ABSTRACT FROM PUBLISHER]

A model-based event-triggered control scheme for nonlinear constrained continuous-time uncertain systems in networked configuration is presented in this paper. It is based on the combined use of model-predictive control (MPC) and integral sliding-mode (ISM) control, and it is oriented to reduce the packet transmission over the network both in the direct path and in the feedback path, in order to avoid network congestion. The key elements of the proposed control scheme are the ISM local control law, the MPC remote controller, a smart sensor, and a smart actuator, both containing a copy of the nominal model of the plant. The role of the ISM control law is to compensate matched uncertainties, without amplifying the unmatched ones. The MPC controller with tightened constraints generates the control component oriented to comply with state and control requirements and is asynchronous since the underlying constrained optimization problem is solved only when a triggering event occurs. In the paper, the robustness properties of the controlled system are theoretically analyzed, proving the regional input-to-state practical stability of the overall control scheme. [ABSTRACT FROM AUTHOR]

In this paper, we propose an event-based sampling policy to implement a constraint-tightening, robust MPC method. The proposed policy enjoys a computationally tractable design and is applicable to perturbed, linear time-invariant systems with polytopic constraints. In particular, the triggering mechanism is suitable for plants with no centralized sensory node as the triggering mechanism can be evaluated locally at each individual sensor. From a geometrical viewpoint, the mechanism is a sequence of hyperrectangles surrounding the optimal state trajectory such that robust recursive feasibility and robust stability are guaranteed. The design of the triggering mechanism is cast as a constrained parametric-in-set optimization problem with the volume of the set as the objective function. Reparameterized in terms of the set vertices, we show that the problem admits a finite tractable convex program reformulation and a linear program relaxation. Several numerical examples are presented to demonstrate the effectiveness and limitations of the theoretical results. [ABSTRACT FROM AUTHOR]

This is a companion paper of [Mixed equilibrium solution of time-inconsistent stochastic linear-quadratic problem, SIAM J. Control Optim., vol. 57, no. 1, 533–569, 2019], where general theory has been established to characterize the open-loop equilibrium control, feedback equilibrium strategy and mixed equilibrium solution for a time-inconsistent stochastic linear-quadratic problem. This note is, on the one hand, to test the developed theory of that paper and on the other hand to push the solvability of multiperiod mean-variance portfolio selection. A nondegenerate assumption, which is popular in the existing literature about multiperiod mean-variance portfolio selection, has been removed in this note; and neat conditions have been obtained to characterize the existence of equilibrium solutions. [ABSTRACT FROM AUTHOR]

This paper considers an unconstrained collaborative optimization of a sum of convex functions, where agents make decisions using local information in the presence of random interconnection topologies. We recast the problem as minimization of the sum of convex functions over a constraint set defined as the set of fixed-value points of a random operator derived from weighted matrices of random graphs. We show that the derived random operator has nonexpansivity property; therefore, this formulation does not need the distribution of random communication topologies. Hence, it includes random networks with/without asynchronous protocols. As an extension of the problem, we define a novel optimization problem, namely minimization of a convex function over the fixed-value point set of a nonexpansive random operator. We propose a discrete-time algorithm using diminishing step size for converging almost surely and in mean square to the global solution of the optimization problem under suitable assumptions. Consequently, as a special case, it reduces to a totally asynchronous algorithm for the distributed optimization problem. We show that fixed-value point is a bridge from deterministic analysis to random analysis of the algorithm. Finally, a numerical example illustrates the convergence of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes scalable, distributed algorithms for solving linear equations by integrating two mechanisms, termed consensus and conservation, in double-layered multiagent networks. The multiagent network considered in this paper is composed of clusters and each cluster consists of an aggregator and a subnetwork of agents. By achieving consensus and conservation through agent–agent communications in the same cluster and aggregator–aggregator communications among different clusters, respectively, distributed algorithms are devised for agents to cooperatively achieve a solution to the overall linear equation. These algorithms outperform existing algorithms, including but not limited to the following aspects—first, each agent does not have to know as much as a complete row or column of the overall equation; second, each agent only needs to control as few as two scalar states when the number of clusters and the number of agents are sufficiently large; third, the dimensions of agents’ states in the proposed algorithms do not have to be the same (while in contrast, algorithms based on the idea of standard consensus inherently require all agents’ states to be of the same dimension). Both analytical proof and simulation results are provided to validate exponential convergence of the proposed distributed algorithms in solving linear equations. [ABSTRACT FROM AUTHOR]

This paper is concerned with the robust event-triggered model predictive control (MPC) of discrete-time constrained linear systems subject to bounded additive disturbances. We make use of the interpolation technique to construct a feedback policy and tighten the original system constraint accordingly to fulfill robust constraint satisfaction. A dynamic event trigger that allows the controller to solve the optimization problem only at triggering time instants is developed, where the triggering threshold is related to the interpolating coefficient of the feedback policy and determined via optimization. We show that the proposed algorithm is recursively feasible and the closed-loop system is input-to-state stable in the attraction region. Finally, a numerical example is provided to verify the theoretical results. [ABSTRACT FROM AUTHOR]

The explicit reference governor (ERG) is a simple and systematic approach that provides constraint handling capabilities to prestabilized systems. The basic idea behind this approach is to translate state and input constraints into an upper-bound on the value of the Lyapunov function, which is then enforced by suitably manipulating the derivative of the applied reference. When designing the ERG, one of the main challenges is the determination of an upper-bound on the value of the Lyapunov function that ensures constraints satisfaction. This paper proposes a systematic approach for estimating online the optimal upper-bound for systems subject to the intersection of concave constraints. To do this, the Barrier function method is used. The effect of the estimation error caused by the time-varying nature of the auxiliary reference on the constraint satisfaction capability of the ERG is studied analytically. A procedure is proposed to modify the estimated upper-bound to avoid constraints violation in the presence of estimation errors. The effectiveness of the proposed scheme is demonstrated through a simulation study on an overhead gantry crane system. [ABSTRACT FROM AUTHOR]

Average consensus underpins key functionalities of distributed systems ranging from distributed information fusion, decision-making, distributed optimization, to load balancing and decentralized control. Existing distributed average consensus algorithms require each node to exchange and disclose state information to its neighbors, which is undesirable in cases where the state is private or contains sensitive information. In this paper, we propose a novel approach that avoids disclosing individual state information in average consensus by letting each node decompose its state into 2 substates. For each node, one of the two substates involves in computation and internode interactions as if it were the original state, while the other substate interacts only with the first substate of the same node, being completely invisible to other nodes. The initial values of the two substates are chosen randomly but with their mean fixed to the initial value of the original state, which is key to guarantee convergence to the desired consensus value. In direct contrast to differential-privacy based privacy-preserving average-consensus approaches, which enable privacy by compromising accuracy in the consensus value, the proposed approach can guarantee convergence to the exact desired value without any error. Not only is the proposed approach able to prevent the disclosure of a node's initial state to honest-but-curious neighbors, it can also provide protection against inference by external eavesdroppers able to wiretap communication links. Numerical simulations demonstrate the effectiveness of the approach and its advantages over state-of-the-art counterparts. [ABSTRACT FROM AUTHOR]

This paper aims to reduce the communication and computation costs of the Nash equilibrium seeking strategy for the $N$ -coalition noncooperative games. The objective is achieved by the following two manners: 1) an interference graph is introduced to describe the interactions among the agents in each coalition and 2) the Nash equilibrium seeking strategy is designed with the interference graphs considered. The convergence property of the proposed Nash equilibrium seeking strategy is analytically investigated. It is shown that the agents’ actions generated by the proposed method converge to a neighborhood of the Nash equilibrium of the graphical $N$ -coalition noncooperative games under certain conditions. Several special cases where there is only one coalition and/or there are coalitions with only one agent are considered. The results for the special cases demonstrate that the proposed seeking strategy achieves the solution seeking for noncooperative games, social cost minimization problems, and single-agent optimization problems in a unified framework. Numerical examples are presented to support the theoretical results. [ABSTRACT FROM AUTHOR]

We consider random walks in which the walk originates in one set of nodes and then continues until it reaches one or more nodes in a target set. The time required for the walk to reach the target set is of interest in understanding the convergence of Markov processes, as well as applications in control, machine learning, and social sciences. In this paper, we investigate the computational structure of the random walk times as a function of the set of target nodes, and find that the commute, hitting, and cover times all exhibit submodular structure, even in nonstationary random walks. We provide a unifying proof of this structure by considering each of these times as special cases of stopping times. We generalize our framework to Markov decision processes, in which the target sets and control policies are jointly chosen to minimize the travel times, leading to polynomial-time approximation algorithms for choosing target sets. Our results are validated through numerical study. [ABSTRACT FROM AUTHOR]

In this paper, we consider Newton–Kantorovich type methods for solving control-constrained optimal control problems that appear in model predictive control. Conditions for convergence are established for an inexact version of the Newton–Kantorovich method applied to variational inequalities. Based on these results, two groups of algorithms are proposed to solve the optimality system. The first group includes exact and inexact Newton and Newton–Kantorovich implementations of the sequential quadratic programming. In the second group, exact and inexact Newton and Newton–Kantorovich methods are developed for solving a nonsmooth normal map equation equivalent to the optimality system. Numerical simulations featuring examples from the aerospace and automotive domain are presented, which show that inexact Newton–Kantorovich type methods can achieve significant reduction of the computational time. [ABSTRACT FROM AUTHOR]

This paper is an attempt to study the first passage optimality criterion for continuous-time Markov decision processes with state-dependent discount factors and history-dependent policies. The state space is denumerable, the action space is a Borel space, and the transition and reward rates are unbounded. Under suitable conditions, we show the existence of a deterministic stationary optimal policy, establish the Bellman (optimality) equation, to which the value function is the unique solution, and give the value and policy iteration algorithms for solving (at least approximating) the value function and an optimal policy. Furthermore, we give examples about reliability and controlled birth processes with killing to illustrate the potential applications of the results obtained here, and also to show the difference between the main results in this paper and those in the previous literature. [ABSTRACT FROM PUBLISHER]

Decentralized optimization of distributed stochastic dynamical systems with two or more controls of the decision makers (DMs) has been an active area of research for over half a century. Although, such decentralized optimization problems are often formulated utilizing static team and person-by-person (PbP) optimality criteria, the corresponding static team theory results have not been extended to dynamical systems. In this first part of the two-part paper, we derive team and PbP optimality conditions for distributed stochastic differential systems, when the controls of the DMs generate actions based on different information structures. The necessary conditions are given by a Hamiltonian System described by coupled backward and forward stochastic differential equations (SDEs) and a conditional Hamiltonian, conditioned on the information structures available to the controls of the DMs. The sufficient conditions state that PbP optimality implies team optimality, if the Hamiltonian is convex in the state and/or actions spaces of the controls of the DMs. We show existence of relaxed team optimal strategies, when the information structures are not affected by the controls of the DMs. Throughout the paper we discuss similarities to analogous optimality conditions of centralized decision or control of stochastic systems, and we note a connections to mean field stochastic optimal control problems. [ABSTRACT FROM AUTHOR]

Schur-type methods in [6] and [11] solve the robust pole assignment problem by employing the departure from normality of the closed-loop system matrix as the measure of robustness. They work well generally when all poles to be assigned are simple. However, when some poles are close or even repeated, the eigenvalues of the computed closed-loop system matrix might be inaccurate. In this paper, we present a refined Schur method, which is able to deal with the case when some or all of the poles to be assigned are repeated. More importantly, the refined Schur method can still be applied when place [14] and robpole [28] fail to output a solution when the multiplicity of some repeated poles is greater than the input freedom. [ABSTRACT FROM AUTHOR]

A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behavior. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this paper, we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behavior over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori. [ABSTRACT FROM AUTHOR]

Model predictive control (MPC) is one of the most widely spread advanced control schemes in industry today. In MPC, a constrained finite-time optimal control (CFTOC) problem is solved at each iteration in the control loop. The CFTOC problem can be solved using, for example, second-order methods, such as interior-point or active-set methods, where the computationally most demanding part often consists of computing the sequence of second-order search directions. Each search direction can be computed by solving a set of linear equations that corresponds to solving an unconstrained finite-time optimal control (UFTOC) problem. In this paper, different direct (noniterative) parallel algorithms for solving UFTOC problems are presented. The parallel algorithms are all based on a recursive variable elimination and solution propagation technique. Numerical evaluations of one of the parallel algorithms indicate that a significant boost in performance can be obtained, which can facilitate high-performance second-order MPC solvers. [ABSTRACT FROM AUTHOR]

This paper considers solving convex quadratic programs in a real-time setting using a regularized and smoothed Fischer–Burmeister method (FBRS). The Fischer–Burmeister function is used to map the optimality conditions of a quadratic program to a nonlinear system of equations which is solved using Newton's method. Regularization and smoothing are applied to improve the practical performance of the algorithm and a merit function is used to globalize convergence. FBRS is simple to code, easy to warmstart, robust to early termination, and has attractive theoretical properties, making it appealing for real time and embedded applications. Numerical experiments using several predictive control examples show that the proposed method is competitive with other state-of-the-art solvers. [ABSTRACT FROM AUTHOR]

In this paper, we consider a distributed optimization scenario, motivated by peak-demand minimization, in which a set of processors aims at cooperatively solving a class of min–max optimization problems. The min–max structure and a twofold coupling make the problem challenging in a distributed setup. We propose a distributed algorithm based on the derivation of a series of dual problems and the application of properties from min–max optimization. The resulting distributed algorithm, despite its complex derivation, has a simple structure consisting of a primal optimization and a suitable dual update. We prove the convergence of the proposed algorithm in objective value, and, moreover, that every limit point of the primal sequence is an optimal (thus feasible) solution. This primal recovery property is of key importance in applications since it allows each agent to compute its portion of the global optimal strategy without resorting to any recovery mechanism. Finally, we provide numerical computations for peak-demand optimization in a network of thermostatically controlled loads and show that our algorithm outperforms a plain distributed subgradient performed on the dual. [ABSTRACT FROM AUTHOR]

We study the optimal control of battery energy storage under a general “pay-for-performance” setup such as providing frequency regulation and renewable integration. In these settings, batteries need to carefully balance the tradeoff between following the instruction signals and their degradation costs in real-time. Existing battery control strategies either do not consider the uncertainty of future signals, or cannot accurately account for battery cycle aging mechanism during operation. In this paper, we take a different approach to the optimal battery control problem. Instead of attacking the complexity of a battery degradation function or the lack of future information one at a time, we address these two challenges together in a joint fashion. In particular, we present an electrochemically accurate and trackable battery degradation model called the rainflow cycle-based model. We prove that the degradation cost is convex. Then, we propose an online control policy with a simple threshold structure and show that it achieves near-optimal performance with respect to an offline controller that has complete future information. We explicitly characterize the optimality gap and show that it is independent to the duration of operation. Simulation results with both synthetic and real regulation traces are conducted to illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

A regularized optimization problem over a large unstructured graph is studied, where the regularization term is tied to the graph geometry. Typical regularization examples include the total variation and the Laplacian regularizations over the graph. When the graph is a simple path without loops, efficient off-the-shelf algorithms can be used. However, when the graph is large and unstructured, such algorithms cannot be used directly. In this paper, an algorithm, referred to as “Snake,” is proposed to solve such regularized problems over general graphs. The algorithm consists in properly selecting random simple paths in the graph and performing the proximal gradient algorithm over these simple paths. This algorithm is an instance of a new general stochastic proximal gradient algorithm, whose convergence is proven. Applications to trend filtering and graph inpainting are provided among others. Numerical experiments are conducted over large graphs. [ABSTRACT FROM AUTHOR]

This paper introduces a continuous-time constrained control strategy, which mimics the behavior of a traditional model predictive control scheme using dynamic feedback. The approach is based on the idea that the solution of the optimal control problem can be embedded in the internal states of a dynamic control law running in parallel to the system. Using input-to-state stability arguments, it is shown that if the controller dynamics are sufficiently fast with respect to the plant dynamics, the interconnection between the two systems is asymptotically stable. Additionally, it is shown that, by augmenting the proposed scheme with an add-on unit known as an explicit reference governor, it is possible to guarantee recursive feasibility and limit the residual of the optimal control problem, regardless of any changes in the desired set point. Numerical examples featuring aerospace applications demonstrate the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

In this paper, we investigate an $L^0$ optimization problem with constraints in a form of Volterra integral equation and the $L^{\infty }$ norm. In particular, the equivalence theorem among the $L^p$ optimizations with $p\in [0, 1]$ is derived, which provides the following twofold extension of the existing results: First, these theoretical results enable us to solve sparse optimal control problems without imposing the finite dimensionality of the system to be controlled, which was the crucial assumption for the derivation of the existing results. Second, the relationship between the partial state constrained problem and output controllability is newly characterized. [ABSTRACT FROM AUTHOR]