Search

In this paper, a two-layer recurrent neural network is proposed to solve the nonsmooth convex optimization problem subject to convex inequality and linear equality constraints. Compared with existing neural network models, the proposed neural network has a low model complexity and avoids penalty parameters. It is proved that from any initial point, the state of the proposed neural network reaches the equality feasible region in finite time and stays there thereafter. Moreover, the state is unique if the initial point lies in the equality feasible region. The equilibrium point set of the proposed neural network is proved to be equivalent to the Karush–Kuhn–Tucker optimality set of the original optimization problem. It is further proved that the equilibrium point of the proposed neural network is stable in the sense of Lyapunov. Moreover, from any initial point, the state is proved to be convergent to an equilibrium point of the proposed neural network. Finally, as applications, the proposed neural network is used to solve nonlinear convex programming with linear constraints and L1 -norm minimization problems. [ABSTRACT FROM AUTHOR]

The scenario approach is a general methodology for data-driven optimization that has attracted a great deal of attention in the past few years. It prescribes that one collects a record of previous cases (scenarios) from the same setup in which optimization is being conducted and makes a decision that attains optimality for the seen cases. Scenario optimization is by now very well understood forconvexproblems, where a theory exists that rigorously certifies the generalization properties of the solution, that is, the ability of the solution to perform well in connection to new situations. This theory supports the scenario methodology and justifies its use. This paper considersnonconvexproblems. While other contributions in the nonconvex setup already exist, we here take a major departure from previous approaches. We suggest that the generalization level is evaluated only after the solution is found and its complexity in terms of the length of a support subsample (a notion precisely introduced in this paper) is assessed. As a consequence, the generalization level is stochastic and adjusted case by case to the available scenarios. This fact is key to obtain tight results. The approach adopted in this paper applies not only to optimization, but also to generic decision problems where the solution is obtained according to a rule that is not necessarily the optimization of a cost function. Accordingly, in our presentation we adopt a general stance of which optimization is just seen as a particular case. [ABSTRACT FROM AUTHOR]

This paper proposes a new optimization framework for the joint optimization of sparsity and filter order (JOSFO) for FIR filter design. Since the cost function for JOSFO involves \ell 0 and non-uniform overlapped group \ell 0 norms, which are not convex, a global optimal solution is difficult to obtain. To find an approximate solution of the non-convex problem, existing approaches repeat the following steps: 1) approximate the cost function; 2) find candidates of zero coefficients by minimizing the cost function; and 3) set them to zero. On the other hand, this paper directly solves the optimization problem, without any approximation to the cost function, by using the alternating direction method of multipliers with the pseudo-proximity operators of \ell 0 and non-uniform non-overlapped group \ell 0 norms. Experimental results show that resulting filters designed by the proposed method have sparser coefficients and lower orders, while satisfying filter specifications, such as an error from a desired frequency response. [ABSTRACT FROM PUBLISHER]

In this paper, we study the distributed fusion estimation problem for linear time-varying systems and nonlinear systems with bounded noises, where the addressed noises do not provide any statistical information, and are unknown but bounded. When considering linear time-varying fusion systems with bounded noises, a new local Kalman-like estimator is designed such that the square error of the estimator is bounded as time goes to $\infty$. A novel constructive method is proposed to find an upper bound of fusion estimation error, then a convex optimization problem on the design of an optimal weighting fusion criterion is established in terms of linear matrix inequalities, which can be solved by standard software packages. Furthermore, according to the design method of linear time-varying fusion systems, each local nonlinear estimator is derived for nonlinear systems with bounded noises by using Taylor series expansion, and a corresponding distributed fusion criterion is obtained by solving a convex optimization problem. Finally, target tracking system and localization of a mobile robot are given to show the advantages and effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods. [ABSTRACT FROM PUBLISHER]

This paper proposes an intra-iterative interference cancellation (IIC) detector based on convex optimization for large-scale MIMO systems. By utilizing Newton's method to solve the optimization problem, a hardware-friendly detector is implemented in a 65 nm CMOS technology. The proposed detector has a throughput of 3.6 Gb/s with a 600 MHz operating frequency. The simulation results indicate that the block-error rate (BLER) performance of the proposed method can approach that of the minimum mean square error (MMSE) detector. The design is found to be more efficient than other recently proposed MIMO detector implementations. [ABSTRACT FROM PUBLISHER]

This paper is concerned with the power system state estimation (PSSE) problem that aims to find the unknown operating point of a power network based on a given set of measurements. We first study the power flow (PF) problem as an important special case of PSSE. PF is known to be nonconvex and NP-hard in the worst case. To this end, we propose a set of semidefinite programs (SDPs) with the property that they all solve the PF problem as long as the voltage angles are relatively small. Associated with each SDP, we explicitly characterize the set of all the complex voltages that can be recovered via that convex problem. As a generalization, the design of an SDP problem that recovers multiple nominal points and a neighborhood around each point is also cast as a convex program. The results are, then, extended to the PSSE problem, where the measurements used in the PF problem are subject to noise. A two-term objective function is employed for each convex program developed for the PSSE problem: 1) the first term accounting for the nonconvexity of the PF equations and 2) other one for estimating the noise levels. An upper bound on the estimation error is derived with respect to the noise level, and the proposed techniques are demonstrated on multiple test systems, including a 9241-bus European network. Although the focus of this paper is on power networks, yet the developed results apply to every arbitrary state estimation problem with quadratic measurement equations. [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]

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 propose a new deadbeat dissipative filter with a finite impulse response (FIR) structure for linear discrete-time systems with external disturbance; this filter is called a deadbeat dissipative FIR filter (DDFF). The new filter ensures (Q,S,R)\text--\alpha-dissipativity and the deadbeat property based on three slack matrix variables. By tuning the weighting parameters provided by the (Q,S,R)\text--\alpha-dissipativity in the proposed DDFF, we present H\infty and passive FIR filters in a unified framework and investigate ways of improving the l2 stability, bounded-disturbance bounded-error stability, and robustness of FIR filters. The gain matrix of the proposed DDFF is obtained by solving a convex problem using the linear matrix inequality approach. Two numerical examples are provided to demonstrate the effectiveness and advantages of the obtained theoretical results. [ABSTRACT FROM PUBLISHER]

This paper studies the problem of minimizing a sum of (possible nonsmooth) convex functions that are corresponding to multiple interacting nodes, subject to a convex state constraint set. Time-varying directed network is considered here. Two types of computational constraints are investigated in this paper: one where the information of gradients is not available and the other where the projection steps can only be calculated approximately. We devise a distributed zeroth-order method, the implementation of which needs only functional evaluations and approximate projection. In particular, we show that the proposed method generates expected function value sequences that converge to the optimal value, provided that the projection errors decrease at appropriate rates. [ABSTRACT FROM AUTHOR]

Online learning has been successfully applied in various machine learning problems. Conventional analysis of online learning achieves a sharp generalization bound with a strongly convex assumption. In this paper, we study the generalization ability of the classic online gradient descent algorithm under the quadratic growth condition (QGC), a strictly weaker condition than strong convexity. Under some mild assumptions, we prove that the excess risk converges no worse than $O(\log T/T)$ when the data are independently and identically distributed (i.i.d.). When the data are generated from a $\phi $ -mixing process, we achieve the excess risk bound $O(\log T /T+\phi (\tau))$ , where $\phi (\tau)$ is the mixing coefficient capturing the non-i.i.d. attribute. Our key technique is based on the combination of the QGC and the martingale concentrations. Our results indicate that the strong convexity is not necessary to achieve the sharp $O(\log {T}/T)$ convergence rate in online learning. We verify our theories on both synthetic and real-world data. [ABSTRACT FROM AUTHOR]

In this paper, we design a no-overloading error feedback quantizer based on a \Delta \!\Sigma modulator, composed of an error feedback filter and a static quantizer. To guarantee no-overloading in the quantizer, we impose an l_{\infty } norm constraint on the feedback signal in the quantizer. Then, for a prescribed l_{\infty }$ norm constraint on the error at the system output induced by the quantizer, we design the error feedback filter that requires the minimum number of bits that achieves the constraint. Next, for a fixed number of bits for the quantizer, we investigate the achievable minimum l_{\infty } norm of the error at the system output with the no-overloading quantizer. Numerical examples are provided to validate our analysis and synthesis. [ABSTRACT FROM AUTHOR]

Finding the optimal solution to the constrained l0 -norm minimization problems in the recovery of compressive sensed signals is an NP-hard problem and it usually requires intractable combinatorial searching operations for getting the global optimal solution, unless using other objective functions (e.g., the l1 norm or lp norm) for approximate solutions or using greedy search methods for locally optimal solutions (e.g., the orthogonal matching pursuit type algorithms). In this paper, a neurodynamic optimization method is proposed to solve the l0 -norm minimization problems for obtaining the global optimum using a recurrent neural network (RNN) model. For the RNN model, a group of modified Gaussian functions are constructed and their sum is taken as the objective function for approximating the l0 norm and for optimization. The constructed objective function sets up a convexity condition under which the neurodynamic system is guaranteed to obtain the globally convergent optimal solution. An adaptive adjustment scheme is developed for improving the performance of the optimization algorithm further. Extensive experiments are conducted to test the proposed approach in this paper and the output results validate the effectiveness of the new method. [ABSTRACT FROM PUBLISHER]

This paper considers the distributed optimization problem over a network, where the objective is to optimize a global function formed by a sum of local functions, using only local computation and communication. We develop an accelerated distributed Nesterov gradient descent method. When the objective function is convex and $L$ -smooth, we show that it achieves a $O(\frac{1}{t^{1.4-\epsilon }})$ convergence rate for all $\epsilon \in (0,1.4)$. We also show the convergence rate can be improved to $O(\frac{1}{t^2})$ if the objective function is a composition of a linear map and a strongly convex and smooth function. When the objective function is $\mu$ -strongly convex and $L$ -smooth, we show that it achieves a linear convergence rate of $O([ 1 - C (\frac{\mu }{L})^{5/7} ]^t)$ , where $\frac{L}{\mu }$ is the condition number of the objective, and $C>0$ is some constant that does not depend on $\frac{L}{\mu }$. [ABSTRACT FROM AUTHOR]

In this paper, we study a dynamic version of the sharing problem, in which a dynamic system cost function composed of time-variant local costs of subsystems and a shared time-variant cost of the whole system is minimized. A dynamic alternating direction method of multipliers (ADMM) is proposed to track the varying optimal points of the dynamic optimization problem in an online manner. We analyze the convergence properties of the dynamic ADMM and show that, under several standard technical assumptions, the iterations of the dynamic ADMM converge linearly to some neighborhoods of the time-varying optimal points. The sizes of these neighborhoods depend on the drifts of the dynamic objective functions: the more drastically the dynamic objective function evolves across time, the larger the sizes of these neighborhoods. We also upper bound the limiting optimality gaps of the dynamic ADMM explicitly, and analyze its regret and constraint violation. Finally, two numerical examples are presented to corroborate the effectiveness of the proposed dynamic ADMM. [ABSTRACT FROM AUTHOR]

In this paper, a novel recurrent neural network (RNN) is presented to deal with a kind of nonsmooth nonconvex optimization problem in which the objective function may be nonsmooth and nonconvex, and the constraints include linear equations and convex inequations. Under certain suitable assumptions, from an arbitrary initial state, each solution to the proposed RNN exists globally and is bounded, and it enters the feasible region within a limited time. Moreover, the solution to the RNN with an arbitrary initial state can converge to the critical point set of the optimization problem. In particular, the RNN does not need the following: 1) abounded feasible region; 2) the computation of an exact penalty parameter; or 3) the initial state being chosen from a given bounded set. Numerical experiments are provided to show the effectiveness and advantages of the RNN. [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 a quaternion-valued one-layer recurrent neural network approach to resolve constrained convex function optimization problems with quaternion variables. Leveraging the novel generalized Hamilton-real (GHR) calculus, the quaternion gradient-based optimization techniques are proposed to derive the optimization algorithms in the quaternion field directly rather than the methods of decomposing the optimization problems into the complex domain or the real domain. Via chain rules and Lyapunov theorem, the rigorous analysis shows that the deliberately designed quaternion-valued one-layer recurrent neural network stabilizes the system dynamics while the states reach the feasible region in finite time and converges to the optimal solution of the considered constrained convex optimization problems finally. Numerical simulations verify the theoretical results. [ABSTRACT FROM AUTHOR]

The event-triggered scheduling of network transmissions has found many applications in engineering tasks operated in cyber-physical systems for its competitive advantage of system resource exploitation. This paper investigates the distributed gradient method for large-scale convex constrained problems with event-triggered consensus protocols. We show that the convergence can be ensured provided that the event-triggering threshold bound is square summable, and the stepsize satisfies specific conditions that are characterized by the Lipschitz constant of the gradient and the spectrum of the mixing matrix associated with the network topology. Stronger convergence results are derived for the strongly convex case, i.e., the local estimate of the minimizer linearly converges to the minimizer until reaching an error floor whose magnitude is shown to be proportional to the stepsize if the triggering threshold bound linearly converges. Comprehensive numerical experiments are conducted to verify the correctness of the theoretical results and advantages of the proposed algorithm over existing ones. [ABSTRACT FROM AUTHOR]

In this paper, we study the optimal control of service rates of a tandem queue with power constraints. The service rate of a server is determined by the power allocated to that server. The total power of the system is fixed. The system cost is comprised of two parts, the holding cost reflecting the congestion of queues and the operating cost reflecting the power consumed at servers. The optimization objective is to find the optimal power allocation policy among servers, which can minimize the system average cost. We formulate this problem as a Markov decision process with a constrained action space. Sensitivity-based optimization theory is applied to study this problem. The necessary and sufficient condition of optimal service rates, and the optimality of the vertexes of the feasible domain are derived when the operating cost has a linear or concave form. An iterative algorithm is further developed to find the optimal service rates. This algorithm may work well even when the cost function has a general form. The extension to general tandem queues with many servers is also studied. Finally, we conduct numerical experiments under different parameter settings to demonstrate the main idea of this paper. [ABSTRACT FROM AUTHOR]

Noise shaping filters for quantizers with error feedback are designed to mitigate the effects of quantization errors. In this paper, we prove that if the transfer function from the quantization error to the signal-of-interest has minimum phase and there is no constraint on the feedback signal, then the scaled inverse of the transfer function is the optimal noise shaping filter. Next, we design a noise shaping filter to minimize the variance or the l2 norm of the error in the signal-of-interest under a constraint on the variance or the l2 norm of the feedback signal, which can be expressed as bilinear matrix inequalities (BMIs). Although the BMIs are not convex, we prove that the minimization of the error variance under the constraint on the variance of the feedback signal can be cast into a convex optimization problem. This enables us to design optimal noise shaping filters using numerical methods. We formulate our design problem as a convex optimization problem using extended linear matrix inequalities to obtain noise shaping filters, except for the special case. Examples are provided to demonstrate the effectiveness of the designed noise shaping filters. [ABSTRACT FROM AUTHOR]

The existing distributed algorithms for network utility maximization (NUM) problems are mostly constructed using dual decomposition and first-order (gradient or subgradient) methods, which suffer from a slow rate of convergence. Part I of this paper proposed an alternative distributed Newton-type algorithm for solving NUM problems with self-concordant utility functions. For each primal iteration, this algorithm features distributed exact stepsize calculation with finite termination and decentralized computation of the dual variables using a finitely truncated iterative scheme obtained through novel matrix splitting techniques. This paper analyzes the convergence properties of a broader class of algorithms with potentially different stepsize computation schemes. In particular, we allow for errors in the stepsize computation. We show that if the error levels in the Newton direction (resulting from finite termination of dual iterations) and stepsize calculation are below a certain threshold, then the algorithm achieves local quadratic convergence rate in primal iterations to an error neighborhood of the optimal solution, where the size of the neighborhood can be explicitly characterized by the parameters of the algorithm and the error levels. [ABSTRACT FROM AUTHOR]

In this paper, we propose a neural network modeled by a differential inclusion to solve a class of nonsmooth convex optimization problems, where the constraints are defined by a class of nonsmooth convex inequality constraints and a class of affine equality constraints. For any initial point, the solution of the proposed network is global existent, unique and uniformly bounded, which is just the “slow solution” of network. By the regularization item, without any estimation on the exact penalty parameters, the solution of proposed network is convergent to the optimal solution set of optimization problem. Moreover, when the feasible region satisfies another condition, the solution of proposed network converges to the feasible region in finite time and to the particular element in the optimal solution set with the smallest norm, which indicates that our proposed neural network is globally attractive. Some numerical examples are presented to illustrate the effectiveness of the proposed neural network for solving nonsmooth convex optimization problems. [ABSTRACT FROM AUTHOR]

This paper presents a two-timescale duplex neurodynamic system for constrained biconvex optimization. The two-timescale duplex neurodynamic system consists of two recurrent neural networks (RNNs) operating collaboratively at two timescales. By operating on two timescales, RNNs are able to avoid instability. In addition, based on the convergent states of the two RNNs, particle swarm optimization is used to optimize initial states of the RNNs to avoid local minima. It is proven that the proposed system is globally convergent to the global optimum with probability one. The performance of the two-timescale duplex neurodynamic system is substantiated based on the benchmark problems. Furthermore, the proposed system is applied for $L_{1}$ -constrained nonnegative matrix factorization. [ABSTRACT FROM AUTHOR]

Conjugate gradient (CG) methods are a class of important methods for solving linear equations and nonlinear optimization problems. In this paper, we propose a new stochastic CG algorithm with variance reduction and we prove its linear convergence with the Fletcher and Reeves method for strongly convex and smooth functions. We experimentally demonstrate that the CG with variance reduction algorithm converges faster than its counterparts for four learning models, which may be convex, nonconvex or nonsmooth. In addition, its area under the curve performance on six large-scale data sets is comparable to that of the LIBLINEAR solver for the $L2$ -regularized $L2$ -loss but with a significant improvement in computational efficiency. 1 CGVR algorithm is available on github: https://github.com/xbjin/cgvr [ABSTRACT FROM AUTHOR]

This paper proposes distributed algorithms to solve robust convex optimization (RCO) when the constraints are affected by nonlinear uncertainty. We adopt a scenario approach by randomly sampling the uncertainty set. To facilitate the computational task, instead of using a single centralized processor to obtain a “global solution” of the scenario problem (SP), we resort to multiple interconnected processors that are distributed among different nodes of a network to simultaneously solve the SP. Then, we propose a primal-dual subgradient algorithm and a random projection algorithm to distributedly solve the SP over undirected and directed graphs, respectively. Both algorithms are given in an explicit recursive form with simple iterations, which are especially suited for processors with limited computational capability. We show that, if the underlying graph is strongly connected, each node asymptotically computes a common optimal solution to the SP with a convergence rate $O(1/(\sum _{t=1}^k\zeta ^t))$ , where $\lbrace \zeta ^t\rbrace$ is a sequence of appropriately decreasing stepsizes. That is, the RCO is effectively solved in a distributed way. The relations with the existing literature on robust convex programs are thoroughly discussed and an example of robust system identification is included to validate the effectiveness of our distributed algorithms. [ABSTRACT FROM AUTHOR]

This paper is concerned with a general class of distributed constrained optimization problems over a multiagent network, where the global objective function is represented by the sum of all local objective functions. Each agent in the network only knows its own local objective function, and is restricted to a global nonempty closed convex set. We discuss the scenario where the communication of the whole multiagent network is expressed as a sequence of time-varying general unbalanced directed graphs. The directed graphs are required to be uniformly jointly strongly connected and the weight matrices are only row-stochastic. To collaboratively deal with the optimization problems, existing distributed methods mostly require the communication graph to be fixed or balanced, which is impractical and hardly inevitable. In contrast, we propose a new distributed projection subgradient algorithm which is applicable to the time-varying general unbalanced directed graphs and does not need each agent to know its in-neighbors’ out-degree. When the objective functions are convex and Lipschitz continuous, it is proved that the proposed algorithm exactly converges to the optimal solution. Simulation results on a numerical experiment are shown to substantiate feasibility of the proposed algorithm and correctness of the theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of robust design problems with polynomial dependence on the uncertainty. One of the main motivations for considering these problems comes from robust controller design, where one often encounters systems that depend polynomially on the uncertain parameters. This paper can be seen as integrated in the emerging area of probabilistic robustness, where a probabilistic relaxation of the original robust problem is adopted, thus requiring the satisfaction of the constraints not for all possible values of the uncertainty, but for most of them. Different from the randomized approach for tackling probabilistic relaxations, which is only guaranteed to provide soft bounds on the probability of satisfaction, we present a deterministic approach based on the novel concept of kinship function introduced in this paper. This allows the development of an original framework, which leads to easily computable deterministic convex relaxations of the probabilistic problem. In particular, optimal polynomial kinship functions are introduced, which can be computed a priori and once for all and provide the “best convex bound” on the probability of constraint violation. More importantly, it is proven that the solution of the relaxed problem converges to that of the original robust optimization problem as the degree of the optimal polynomial kinship function increases. Furthermore, by relying on quadrature formulas for computation of integrals of polynomials, it is shown that the computational complexity of the proposed approach is polynomial in the number of uncertain parameters. Finally, unlike other deterministic approaches to robust polynomial optimization, the number of variables in the ensuing optimization problem is not increased by the proposed approximation. An important feature of this approach is that a significant amount of the computational burden is shifted to a one-time offline computation whose results can be stored and provided to the end-user. [ABSTRACT FROM PUBLISHER]

The problem of low-rank approximation with convex constraints, which appears in data analysis, system identification, model order reduction, low-order controller design, and low-complexity modeling is considered. Given a matrix, the objective is to find a low-rank approximation that meets rank and convex constraints while minimizing the distance to the matrix in the squared Frobenius norm. In many situations, this nonconvex problem is convexified by nuclear-norm regularization. However, we will see that the approximations obtained by this method may be far from optimal. In this paper, we propose an alternative convex relaxation that uses the convex envelope of the squared Frobenius norm and the rank constraint. With this approach, easily verifiable conditions are obtained under which the solutions to the convex relaxation and the original nonconvex problem coincide. A semidefinite programming representation of the convex envelope is derived, which allows us to apply this approach to several known problems. Our example on optimal low-rank Hankel approximation/model reduction illustrates that the proposed convex relaxation performs consistently better than nuclear-norm regularization and may outperform balanced truncation. [ABSTRACT FROM AUTHOR]

This paper introduces a nonsmooth (NS) neural network that is able to operate in a time-dependent (TD) context and is potentially useful for solving some classes of NS-TD problems. The proposed network is named nonsmooth time-dependent network (NTN) and is an extension to a TD setting of a previous NS neural network for programming problems. Suppose $C(t)$ , t \ge 0$ , is a nonempty TD convex feasibility set defined by TD inequality constraints. The constraints are in general NS (nondifferentiable) functions of the state variables and time. NTN is described by the subdifferential with respect to the state variables of an NS-TD barrier function and a vector field corresponding to the unconstrained dynamics. This paper shows that for suitable values of the penalty parameter, the NTN dynamics displays two main phases. In the first phase, any solution of NTN not starting in C(0)$ at t=0$ is able to reach the moving set C(\cdot ) , whereas in the second phase, the solution tracks the moving set, i.e., it stays within C(t)$ for all subsequent times t \ge t_{h} . NTN is thus able to find an exact feasible solution in finite time and also to provide an exact feasible solution for subsequent times. This new and peculiar dynamics displayed by NTN is potentially useful for addressing some significant TD signal processing tasks. As an illustration, this paper discusses a number of examples where NTN is applied to the solution of NS-TD convex feasibility problems. [ABSTRACT FROM AUTHOR]

Distributed decision on sensor network is affected by the bandwidth, network congestion, and computation capability of sensors, which cause the communication delays and feedback delays during the signal processing process. In this paper, the effects of state constraints, directed graph, communication delays and feedback delays on the online distributed parameter estimation problem for multi-sensor networks are considered comprehensively. To this end, we first propose an Online Decentralized Gradient Descent Algorithm (ODGDA) to overcome the effects of these factors and give the regret upper bounds for convex loss function and strongly convex loss function, respectively. Further, considering that the loss function may not be fully disclosed in the complex environment, we extend ODGDA to the scenario of bandit feedback and propose an Online Decentralized Bandit Feedback Algorithm (ODBFA), which is updated using historical state information stored by sensors. The analysis shows that, compared with the ODGDA which can directly use the gradient information for state update, the ODBFA utilizing two-point bandit feedback information does not lead to regret degradation in the order sense. Finally, the effectiveness of the proposed algorithm is verified by the multi-sensor network. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of decentralized optimization to minimize a finite sum of local convex cost functions over an undirected network. Compared with the existing works, we focus on improving the communication efficiency of the stochastic gradient tracking method and propose an effective event-triggering decentralized stochastic gradient tracking algorithm, namely, ET-DSGT. ET-DSGT utilizes the event-triggering mechanism in which each agent only broadcasts its estimators at the event time to effectively avoid real-time communication, thus improving communication efficiency. In addition, we present a theoretical analysis to show that ET-DSGT with a decaying step-size can converge to the exact global minimum. Moreover, we show that for each agent, the time interval between two successive triggering times is greater than the iteration interval under certain conditions. Finally, we provide several simulations to demonstrate the effectiveness of ET-DSGT. [ABSTRACT FROM AUTHOR]

The article discusses an article in the issue by Emmanuel Candès and Benjamin Recht on matrix completion. The author argues that the paper presents important technical innovations on topics including incoherence, convex optimization, and probabilistic analysis. The author examines how the paper looks at low-rank matrices and discusses the interactions between data and a priori information.

This paper presents an accurate, efficient, and scalable algorithm for minimizing a special family of convex functions, which have a lp loss function as an additive component. For this problem, well-known learning algorithms often have well-established results on accuracy and efficiency, but there exists rarely any report on explicit linear scalability with respect to the problem size. The proposed approach starts with developing a second-order learning procedure with iterative descent for general convex penalization functions, and then builds efficient algorithms for a restricted family of functions, which satisfy the Karmarkar's projective scaling condition. Under this condition, a light weight, scalable message passing algorithm (MPA) is further developed by constructing a series of simpler equivalent problems. The proposed MPA is intrinsically scalable because it only involves matrix-vector multiplication and avoids matrix inversion operations. The MPA is proven to be globally convergent for convex formulations; for nonconvex situations, it converges to a stationary point. The accuracy, efficiency, scalability, and applicability of the proposed method are verified through extensive experiments on sparse signal recovery, face image classification, and over-complete dictionary learning problems. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of estimating the position of a scene point from its image projections onto generalized cameras, i.e., cameras that can be modeled by a spherical projection followed by a perspective one. The sought estimate is defined through a geometric criterion, specifically the minimization of the angles between the projections on the sphere of the available image points and the corresponding projections of the estimate. A solution based on convex optimization with linear matrix inequalities (LMIs) is proposed for addressing this problem, which provides a candidate of the sought estimate. Moreover, a condition is provided for establishing exactness of the found candidate, i.e., establishing whether the found candidate is a minimizer of the considered geometric criterion. [ABSTRACT FROM AUTHOR]

This paper considers a distributed optimization problem over a multiagent network, in which the objective function is a sum of individual cost functions at the agents. We focus on the case when communication between the agents is described by a directed graph. Existing distributed optimization algorithms for directed graphs require at least the knowledge of the neighbors’ out-degree at each agent (due to the requirement of column-stochastic matrices). In contrast, our algorithm requires no such knowledge. Moreover, the proposed algorithm achieves the best known rate of convergence for this class of problems, $O(\mu ^k)$ for $0<\mu <1$ , where $k$ is the number of iterations, given that the objective functions are strongly convex and have Lipschitz-continuous gradients. Numerical experiments are also provided to illustrate the theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, we consider distributed optimization problems where the goal is to minimize a sum of objective functions over a multiagent network. We focus on the case when the interagent communication is described by a strongly connected, directed graph. The proposed algorithm, Accelerated Distributed Directed OPTimization (ADD-OPT), achieves the best known convergence rate for this class of problems,  $O(\mu ^{k}),0<\mu <1$ , given strongly convex, objective functions with globally Lipschitz-continuous gradients, where  $k$ is the number of iterations. Moreover, ADD-OPT supports a wider and more realistic range of step sizes in contrast to existing work. In particular, we show that ADD-OPT converges for arbitrarily small (positive) step sizes. Simulations further illustrate our results. [ABSTRACT FROM AUTHOR]

In this paper, based on \mathbb CR calculus and penalty method, a one-layer recurrent neural network is proposed for solving constrained complex-variable convex optimization. It is proved that for any initial point from a given domain, the state of the proposed neural network reaches the feasible region in finite time and converges to an optimal solution of the constrained complex-variable convex optimization finally. In contrast to existing neural networks for complex-variable convex optimization, the proposed neural network has a lower model complexity and better convergence. Some numerical examples and application are presented to substantiate the effectiveness of the proposed neural network. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of estimating a parameter matrix from observations which are affected by two types of noise components: (i) a sparse noise sequence which, whenever nonzero can have arbitrarily large amplitude (ii) and a dense and bounded noise sequence of “moderate” amount. This is termed a robust regression problem. To tackle it, a quite general optimization-based framework is proposed and analyzed. When only the sparse noise is present, a sufficient bound is derived on the number of nonzero elements in the sparse noise sequence that can be accommodated by the estimator while still returning the true parameter matrix. While almost all the restricted isometry-based bounds from the literature are not verifiable, our bound can be easily computed through solving a convex optimization problem. Moreover, empirical evidence tends to suggest that it is generally tight. If in addition to the sparse noise sequence, the training data are affected by a bounded dense noise, we derive an upper bound on the estimation error. [ABSTRACT FROM PUBLISHER]

In this paper we present a method for the addition of integral action to nonpassive outputs of a class of port-Hamiltonian (pH) systems. The proposed integral controller is a dynamic extension, constructed from the open-loop system, such that the closed loop preserves the pH form. It is shown that the controller is able to reject the effects of both matched and unmatched disturbances, preserving the regulation of the nonpassive outputs. Previous solutions to this problem have relied on a change of coordinates whereas the presented solution is developed using the original state vector and, therefore, retains its physical interpretation. In addition, the resulting closed-loop dynamics have a natural interpretation as a control by interconnection scheme. [ABSTRACT FROM AUTHOR]

This paper presents a neurodynamic optimization approach to bilevel quadratic programming (BQP). Based on the Karush–Kuhn–Tucker (KKT) theorem, the BQP problem is reduced to a one-level mathematical program subject to complementarity constraints (MPCC). It is proved that the global solution of the MPCC is the minimal one of the optimal solutions to multiple convex optimization subproblems. A recurrent neural network is developed for solving these convex optimization subproblems. From any initial state, the state of the proposed neural network is convergent to an equilibrium point of the neural network, which is just the optimal solution of the convex optimization subproblem. Compared with existing recurrent neural networks for BQP, the proposed neural network is guaranteed for delivering the exact optimal solutions to any convex BQP problems. Moreover, it is proved that the proposed neural network for bilevel linear programming is convergent to an equilibrium point in finite time. Finally, three numerical examples are elaborated to substantiate the efficacy of the proposed approach. [ABSTRACT FROM PUBLISHER]

In this paper, we consider a general problem setup for a wide class of convex and robust distributed optimization problems in peer-to-peer networks. In this setup, convex constraint sets are distributed to the network processors who have to compute the optimizer of a linear cost function subject to the constraints. We propose a novel fully distributed and asynchronous algorithm, named cutting-plane consensus, to solve the problem, based on a polyhedral outer approximation of the constraint sets. Processors running the algorithm compute and exchange linear approximations of their locally feasible sets. Independently of the number of processors in the network, each processor stores only a small number of linear constraints, making the algorithm scalable to large networks. The cutting-plane consensus algorithm is presented and analyzed for the general framework. Specifically, we prove the correctness of the algorithm, and show its robustness against communication or processor failures. Then, the cutting-plane consensus algorithm is specified to three different classes of distributed optimization problems, namely 1) inequality constrained problems, 2) robust optimization problems, and 3) almost separable optimization problems. For each one of these problem classes we solve a concrete problem and present computational results. That is, we show how to solve: position estimation in wireless sensor networks, a distributed robust linear program, and a distributed microgrid control problem. [ABSTRACT FROM AUTHOR]

In this paper, the problem of exponential stability for discrete-time switched genetic regulatory networks (GRNs) with persistent dwell-time (PDT) switching and time delays is concerned. The novelty of this paper is derived from introducing an extended property of quadratic convex function, and utilizing an improved summation inequality together with an extended reciprocally convex matrix inequality, which is less conservative than the Jensen inequality and the reciprocally convex combination employed in the discrete-time delay systems. In addition, the considered switching regularity is more general than dwell-time (DT) switching and average dwell-time (ADT) switching. Moreover, by introducing the delay partitioning method and the piecewise Lyapunov–Krasovskii functional, a set of sufficient conditions are established in the form of linear matrix inequalities to guarantee the discrete-time PDT switched GRNs with constant time delays and time-varying delays are exponentially stable, respectively. Finally, some numerical examples are exploited to demonstrate the validity and potential of the proposed method. [ABSTRACT FROM AUTHOR]

Most of time-varying systems in fusion estimation are generally modeled without bounded noises. In this paper, we study the distributed fusion estimation problem for networked time-varying systems with bounded noises, where the resource constraints (i.e., bandwidth or energy) and quantization effect are described by a unified model. A new local estimator with time-varying gain is designed by solving a class of convex optimization problems such that the square error of the estimator is bounded. When each local estimate is transmitted to the fusion center over communication networks, the selection probability criterion is derived such that the mean square error of the each compensating state estimate is bounded. Then, a convex optimization problem on the design of an optimal weighting fusion criterion is established in terms of linear matrix inequalities, which can be solved by standard software packages. Target tracking system with time-varying sampling period is given to show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This paper addresses the design of output controllers of chosen order in a given set for ensuring a number of desired properties, such as robust D-stability and robust performance. It is shown that a sufficient condition for determining such controllers can be obtained by solving convex optimization problems with linear matrix inequality constraints through the introduction of a Lyapunov function depending polynomially on both uncertainty and controller. The proposed condition is also necessary for sufficiently large degrees of the polynomials involved under some assumptions. [ABSTRACT FROM AUTHOR]

This paper considers time-average optimization, where a decision vector is chosen every time step within a (possibly nonconvex) set, and the goal is to minimize a convex function of the time averages subject to convex constraints on these averages. Such problems have applications in networking, multiagent systems, and operation research, where decisions are constrained to a discrete set and the decision average can represent average bit rates or average agent actions. This time-average optimization extends traditional convex formulations to allow a nonconvex decision set. This class of problems can be solved by Lyapunov optimization. A simple drift-based algorithm, related to a classical dual subgradient algorithm, converges to an $\epsilon$ -optimal solution within O(1/\epsilon ^2)$ time steps. Furthermore, the algorithm is shown to have a transient phase and a steady-state phase, which can be exploited to improve convergence rates to O(1/\epsilon)$ and when vectors of Lagrange multipliers satisfy locally polyhedral and locally smooth assumptions, respectively. Practically, this improved convergence suggests that decisions should be implemented after the transient period. [ABSTRACT FROM AUTHOR]

Model instability and poor prediction of long-term behavior are common problems when modeling dynamical systems using nonlinear “black-box” techniques. Direct optimization of the long-term predictions, often called simulation error minimization, leads to optimization problems that are generally nonconvex in the model parameters and suffer from multiple local minima. In this paper, we present methods which address these problems through convex optimization, based on Lagrangian relaxation, dissipation inequalities, contraction theory, and semidefinite programming. We demonstrate the proposed methods with a model order reduction task for electronic circuit design and the identification of a pneumatic actuator from experiment. [ABSTRACT FROM AUTHOR]

This paper studies the distributed optimization problem for continuous-time multiagent systems with general linear dynamics. The objective is to cooperatively optimize a team performance function formed by a sum of convex local objective functions. Each agent utilizes only local interaction and the gradient of its own local objective function. To achieve the cooperative goal, a couple of fully distributed optimal algorithms are designed. First, an edge-based adaptive algorithm is developed for linear multiagent systems with a class of convex local objective functions. Then, a node-based adaptive algorithm is constructed to solve the distributed optimization problem for a class of agents satisfying the bounded-input bounded-state stable property. Sufficient conditions are given to ensure that all agents reach a consensus while minimizing the team performance function. Finally, numerical examples are provided to illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

In this paper we consider distributed optimization problems in which the cost function is separable, i.e., a sum of possibly non-smooth functions all sharing a common variable, and can be split into a strongly convex term and a convex one. The second term is typically used to encode constraints or to regularize the solution. We propose a class of distributed optimization algorithms based on proximal gradient methods applied to the dual problem. We show that, by choosing suitable primal variable copies, the dual problem is itself separable when written in terms of conjugate functions, and the dual variables can be stacked into non-overlapping blocks associated to the computing nodes. We first show that a weighted proximal gradient on the dual function leads to a synchronous distributed algorithm with local dual proximal gradient updates at each node. Then, as main paper contribution, we develop asynchronous versions of the algorithm in which the node updates are triggered by local timers without any global iteration counter. The algorithms are shown to be proper randomized block-coordinate proximal gradient updates on the dual function. [ABSTRACT FROM PUBLISHER]