Search

We introduce a fast solver for the phase field crystal (PFC) and functionalized Cahn-Hilliard (FCH) equations with periodic boundary conditions on a rectangular domain that features the preconditioned Nesterov accelerated gradient descent (PAGD) method. We discretize these problems with a Fourier collocation method in space, and employ various second-order schemes in time. We observe a significant speedup with this solver when compared to the preconditioned gradient descent (PGD) method. With the PAGD solver, fully implicit, second-order-in-time schemes are not only feasible to solve the PFC and FCH equations, but also do so more efficiently than some semi-implicit schemes in some cases where accuracy issues are taken into account. Benchmark computations of five different schemes for the PFC and FCH equations are conducted and the results indicate that, for the FCH experiments, the fully implicit schemes (midpoint rule and BDF2 equipped with the PAGD as a nonlinear time marching solver) perform better than their IMEX versions in terms of computational cost needed to achieve a certain precision. For the PFC, the results are not as conclusive as in the FCH experiments, which, we believe, is due to the fact that the nonlinearity in the PFC is milder nature compared to the FCH equation. We also discuss some practical matters in applying the PAGD. We introduce an averaged Newton preconditioner and a sweeping-friction strategy as heuristic ways to choose good preconditioner parameters. The sweeping-friction strategy exhibits almost as good a performance as the case of the best manually tuned parameters.

We describe a Lanczos-based algorithm for approximating the product of a rational matrix function with a vector. This algorithm, which we call the Lanczos method for optimal rational matrix function approximation (Lanczos-OR), returns the optimal approximation from a given Krylov subspace in a norm depending on the rational function's denominator, and can be computed using the information from a slightly larger Krylov subspace. We also provide a low-memory implementation which only requires storing a number of vectors proportional to the denominator degree of the rational function. Finally, we show that Lanczos-OR can be used to derive algorithms for computing other matrix functions, including the matrix sign function and quadrature based rational function approximations. In many cases, it improves on the approximation quality of prior approaches, including the standard Lanczos method, with little additional computational overhead.

Maintaining the stability of renewable-dominant power systems requires the procurement of virtual inertia services from non-synchronous resources (e.g., batteries, wind turbines) in addition to inertia traditionally provided by synchronous resources (e.g., thermal generators). However, the pricing of inertia provision has not been studied in a stochastic electricity market, where the uncertainty characteristics of renewable energy sources (RES) are considered. To fill in this research gap, this paper formulates a chance-constrained stochastic unit commitment model with inertia requirements and computes equilibrium energy, reserve and inertia prices using convex duality. Numerical experiments on an illustrative system and a modified IEEE 118-bus system show the performance of the proposed pricing mechanism. By allowing new virtual inertia providers to contribute to system inertia requirements, the total operating cost reduces. Moreover, the proposed stochastic electricity market internalizes RES uncertainty, which yields additional cost reductions by co-optimizing energy, reserve and inertia procurement.

In this paper, we propose a variance-reduced primal-dual algorithm with Bregman distance for solving convex-concave saddle-point problems with finite-sum structure and nonbilinear coupling function. This type of problems typically arises in machine learning and game theory. Based on some standard assumptions, the algorithm is proved to converge with oracle complexity of $O\left(\frac{\sqrt n}{\epsilon}\right)$ and $O\left(\frac{n}{\sqrt \epsilon}+\frac{1}{\epsilon^{1.5}}\right)$ using constant and non-constant parameters, respectively where $n$ is the number of function components. Compared with existing methods, our framework yields a significant improvement over the number of required primal-dual gradient samples to achieve $\epsilon$-accuracy of the primal-dual gap. We tested our method for solving a distributionally robust optimization problem to show the effectiveness of the algorithm.

In this work, we present a modification of explicit Runge-Kutta temporal integration schemes that guarantees the preservation of any locally-defined quasiconvex set of bounds for the solution. These schemes operate on the basis of a bijective mapping between an admissible set of solutions and the real domain to strictly enforce bounds. Within this framework, we show that it is possible to recover a wide range of methods independently of the spatial discretization, including positivity preserving, discrete maximum principle satisfying, entropy dissipative, and invariant domain preserving schemes. Furthermore, these schemes are proven to recover the order of accuracy of the underlying Runge-Kutta method upon which they are built. The additional computational cost is the evaluation of two nonlinear mappings which generally have closed-form solutions. We show the utility of this approach in numerical experiments using a pseudospectral spatial discretization without any explicit shock capturing schemes for nonlinear hyperbolic problems with discontinuities., Comment: 21 pages, 10 figures

We consider unconstrained stochastic optimization problems with no available gradient information. Such problems arise in settings from derivative-free simulation optimization to reinforcement learning. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a stochastic function using finite differences within a common random number framework. We develop modified versions of a norm test and an inner product quasi-Newton test to control the sample sizes used in the stochastic approximations and provide global convergence results to the neighborhood of the optimal solution. We present numerical experiments on simulation optimization problems to illustrate the performance of the proposed algorithm. When compared with classical zeroth-order stochastic gradient methods, we observe that our strategies of adapting the sample sizes significantly improve performance in terms of the number of stochastic function evaluations required.

International audience; An interpolation problem is defined by a set of linear forms on the (multivariate) polynomial ring and values to be achieved by an interpolant. For Lagrange interpolation the linear forms consist of evaluations at some nodes,while Hermite interpolation also considers the values of successive derivatives. Both are examples of ideal interpolation in that the kernels of the linear forms intersect into an ideal. For an ideal interpolation problem with symmetry, we address the simultaneous computation of a symmetry adapted basis of the least interpolation space and the symmetry adapted H-basis of the ideal. Beside its manifest presence in the output, symmetry is exploited computationally at all stages of the algorithm. For an ideal invariant, under a group action, defined by a Groebner basis, the algorithm allows to obtain a symmetry adapted basis of the quotient and of the generators. We shall also note how it applies surprisingly but straightforwardly to compute fundamental invariants and equivariants of a reflection group.

The second-order cone (SOC) is a class of simple convex cones and optimizing over them can be done more efficiently than with semidefinite programming. It is interesting both in theory and in practice to investigate which convex cones admit a representation using SOCs, given that they have a strong expressive ability. In this paper, we prove constructively that the cone of sums of nonnegative circuits (SONC) admits a SOC representation. Based on this, we give a new algorithm for unconstrained polynomial optimization via SOC programming. We also provide a hybrid numeric-symbolic scheme which combines the numerical procedure with a rounding-projection algorithm to obtain exact nonnegativity certificates. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with fairly large degree and number of variables., 29 pages, 7 tables, 6 figures, extended version of the article published in the proceedings of ISSAC 2020. arXiv admin note: text overlap with arXiv:1906.06179

A rank-adaptive integrator for the approximate solution of high-order tensor differential equations by tree tensor networks is proposed and analyzed. In a recursion from the leaves to the root, the integrator updates bases and then evolves connection tensors by a Galerkin method in the augmented subspace spanned by the new and old bases. This is followed by rank truncation within a specified error tolerance. The memory requirements are linear in the order of the tensor and linear in the maximal mode dimension. The integrator is robust to small singular values of matricizations of the connection tensors. Up to the rank truncation error, which is controlled by the given error tolerance, the integrator preserves norm and energy for Schro"\dinger equations, and it dissipates the energy in gradient systems. Numerical experiments with a basic quantum spin system illustrate the behavior of the proposed algorithm.

Semidefinite and sum-of-squares (SOS) optimization are fundamental computational tools in many areas, including linear and nonlinear systems theory. However, the scale of problems that can be addressed reliably and efficiently is still limited. In this paper, we introduce a new notion of block factor-width-two matrices and build a new hierarchy of inner and outer approximations of the cone of positive semidefinite (PSD) matrices. This notion is a block extension of the standard factor-width-two matrices, and allows for an improved inner-approximation of the PSD cone. In the context of SOS optimization, this leads to a block extension of the scaled diagonally dominant sum-of-squares (SDSOS) polynomials. By varying a matrix partition, the notion of block factor-width-two matrices can balance a trade-off between the computation scalability and solution quality for solving semidefinite and SOS optimization problems. Numerical experiments on a range of large-scale instances confirm our theoretical findings., Accepted for publication as a regular paper at IEEE TAC. Code is available through https://github.com/zhengy09/SDPfw

We consider composition problems of the form , which are important for machine learning. Although gradient descent and stochastic gradient descent are straightforward solutions, the essential computation of in each single iteration is expensive, let alone for large m. In this article, we devise a stochastically controlled compositional gradient algorithm. Specifically, we introduce two variants of stochastically controlled technique to estimate the inner function G(x) and the gradient of the objective function, respectively. The computational cost is largely reduced. However, the natural needs of two stochastic subsets D1 and D2 form direct barriers to guarantee the convergence of the algorithm, especially the theoretical proof of the convergence. To this end, we present a general convergence analysis by proving and , through which the proposed method significantly improve composition algorithms under low target accuracy (i.e., 1/e≪ m or n) in both strongly convex and nonconvex settings. Comprehensive experiments demonstrate the superiority of the proposed method over existing methods.

The logarithmic representation of infinitesimal generators is generalized to the cases when the evolution operator is unbounded. The generalized result is applicable to the representation of infinitesimal generators of unbounded evolution operators, where unboundedness of evolution operator is an essential ingredient of nonlinear analysis. In conclusion a general framework for the identification between the infinitesimal generators with evolution operators is established. A mathematical framework for such an identification is indispensable to the rigorous treatment of nonlinear transforms: e.g., transforms appearing in the theory of integrable systems., To appear in Math. Meth. Appl. Sci

This paper presents a family of algorithms for decentralized convex composite problems. We consider the setting of a network of agents that cooperatively minimize a global objective function composed of a sum of local functions plus a regularizer. Through the use of intermediate consensus variables, we remove the need for inner communication loops between agents when computing curvature-guided updates. A general scheme is presented which unifies the analysis for a plethora of computing choices, including gradient descent, Newton updates, and BFGS updates. Our analysis establishes sublinear convergence rates under convex objective functions with Lipschitz continuous gradients, as well as linear convergence rates when the local functions are further assumed to be strongly convex. Moreover, we explicitly characterize the acceleration due to curvature information. Last but not the least, we present an asynchronous implementation for the proposed algorithms, which removes the need for a central clock, with linear convergence rates established in expectation under strongly convex objectives. We ascertain the effectiveness of the proposed methods with numerical experiments on benchmark datasets.

We consider a partial differential equation - ordinary differential equation system to describe the dynamics of traffic flow with autonomous vehicles. In the model, the bulk flow of human drivers is represented by a scalar conservation law, while each autonomous vehicle is described by an ordinary differential equation. The coupled PDE-ODE model is introduced, and existence of solutions for this model is shown, along with a proposed algorithm to construct approximate solutions. Next, we propose a control strategy for the speeds of the autonomous vehicles to minimize the average fuel consumption of the entire traffic flow. Existence of solutions for the optimal control problem is proved, and we numerically show that a reduction in average fuel consumption is possible with an AV acting as a moving bottleneck.

We prove that every semidefinite moment relaxation of a polynomial optimization problem (POP) with a ball constraint can be reformulated as a semidefinite program involving a matrix with constant trace property (CTP). As a result such moment relaxations can be solved efficiently by first-order methods that exploit CTP, e.g., the conditional gradient-based augmented Lagrangian method. We also extend this CTP-exploiting framework to large-scale POPs with different sparsity structures. The efficiency and scalability of our framework are illustrated on second-order moment relaxations for various randomly generated quadratically constrained quadratic programs., 43 pages, 6 algorithms, 23 tables

In this paper, we extend a recently established subgradient method for the computation of Riemannian metrics that optimizes certain singular value functions associated with dynamical systems. This extension is threefold. First, we introduce a projected subgradient method which results in Riemannian metrics whose parameters are confined to a compact convex set and we can thus prove that a minimizer exists; second, we allow inexact subgradients and study the effect of the errors on the computed metrics; and third, we analyze the subgradient algorithm for three different choices of step sizes: constant, exogenous and Polyak. The new methods are illustrated by application to dimension and entropy estimation of the H\'enon map., Comment: 30 pages, 5 figures

A mixed-integer programming (MIP) problem contains both constraints and integer restrictions. Integer restrictions divide the feasible region defined by constraints into multiple discontinuous feasible parts. In particular, the number of discontinuous feasible parts will drastically increase with the increase of the number of integer decision variables and/or the size of the candidate set of each integer decision variable. Due to the fact that the optimal solution is located in one of the discontinuous feasible parts, it is a challenging task to solve a MIP problem. This article presents a cutting and repulsion-based evolutionary framework (called CaR) to solve MIP problems. CaR includes two main strategies: 1) the cutting strategy and 2) the repulsion strategy. In the cutting strategy, an additional constraint is constructed based on the objective function value of the best individual found so far, the aim of which is to continuously cut unpromising discontinuous feasible parts. As a result, the probability of the population entering a wrong discontinuous feasible part can be decreased. In addition, in the repulsion strategy, once it has been detected that the population has converged to a discontinuous feasible part, the population will be reinitialized. Moreover, a repulsion function is designed to repulse the previously explored discontinuous feasible parts. Overall, the cutting strategy can significantly reduce the number of discontinuous feasible parts and the repulsion strategy can probe the remaining discontinuous feasible parts. Sixteen test problems developed in this article and two real-world cases are used to verify the effectiveness of CaR. The results demonstrate that CaR performs well in solving MIP problems.

We propose a novel preconditioned inexact primal-dual interior point method for constrained convex quadratic programming problems. The algorithm we describe invokes the preconditioned conjugate gradient method on a new reduced Schur complement KKT system, in implicit form. In contrast to standard approaches, the Schur complement formulation we consider enables reuse of the factorization of the KKT matrix with rows and columns corresponding to inequality constraints excluded, across all interior point iterations. Further, two new preconditioners are presented for the resulting reduced system, that alleviate the ill-conditioning associated with slack variables in primal-dual interior point methods. Each of the preconditioners we propose also provably reduces the number of unique eigenvalues for the coefficient matrix, and thus the CG iteration count. One preconditioner is efficient when the number of equality constraints is small, while the other is efficient when the number of remaining degrees of freedom is small. Numerical experiments with synthetic problems and problems from the Maros-M\'esz\'aros QP collection show that our preconditioned inexact interior point solvers are effective at improving conditioning and reducing cost. Across all test problems for which the direct method is not fastest, our preconditioned methods achieve a reduction in cost by a geometric mean of $1.432$ relative to the best alternative preconditioned method for each problem., Comment: 33 pages, 6 figures

Nonnegative least squares problems with multiple right-hand sides (MNNLS) arise in models that rely on additive linear combinations. In particular, they are at the core of most nonnegative matrix factorization algorithms and have many applications. The nonnegativity constraint is known to naturally favor sparsity, that is, solutions with few non-zero entries. However, it is often useful to further enhance this sparsity, as it improves the interpretability of the results and helps reducing noise, which leads to the sparse MNNLS problem. In this paper, as opposed to most previous works that enforce sparsity column- or row-wise, we first introduce a novel formulation for sparse MNNLS, with a matrix-wise sparsity constraint. Then, we present a two-step algorithm to tackle this problem. The first step divides sparse MNNLS in subproblems, one per column of the original problem. It then uses different algorithms to produce, either exactly or approximately, a Pareto front for each subproblem, that is, to produce a set of solutions representing different tradeoffs between reconstruction error and sparsity. The second step selects solutions among these Pareto fronts in order to build a sparsity-constrained matrix that minimizes the reconstruction error. We perform experiments on facial and hyperspectral images, and we show that our proposed two-step approach provides more accurate results than state-of-the-art sparse coding heuristics applied both column-wise and globally., Comment: 25 pages + 18 pages supplementary material. This is the new version of a work originally called "A Homotopy-based Algorithm for Sparse Multiple Right-hand Sides Nonnegative Least Squares". Although the central concept is the same, the paper has been almost completely rewritten

Nonlinear and nonconvex optimization problems are vital and fundamental problems in science and engineering fields. In this article, a novel finite-time circadian rhythms learning network (called FT-CRLN) is proposed for solving nonlinear and nonconvex optimization problems with periodic noises. Different from the traditional recurrent neural networks, the proposed FT-CRLN can suppress the periodic noise notably and achieve excellent convergence performance in solving nonlinear and nonconvex problems. The theoretical analysis and rigorous mathematical proof verify the superior convergence, high accuracy, and strong robustness of the proposed FT-CRLN. The simulation results demonstrate the effectiveness and robustness of the proposed FT-CRLN in solving nonlinear and nonconvex problems compared with other state-of-art neural networks.

In this paper, we consider the classical wave equation with time-dependent, spatially multiscale coefficients. We propose a fully discrete computational multiscale method in the spirit of the localized orthogonal decomposition in space with a backward Euler scheme in time. We show optimal convergence rates in space and time beyond the assumptions of spatial periodicity or scale separation of the coefficients. Further, we propose an adaptive update strategy for the time-dependent multiscale basis. Numerical experiments illustrate the theoretical results and showcase the practicability of the adaptive update strategy.

In this paper we consider the spatial semi-discretization of conservative PDEs. Such finite dimensional approximations of infinite dimensional dynamical systems can be described as flows in suitable matrix spaces, which in turn leads to the need to solve polynomial matrix equations, a classical and important topic both in theoretical and in applied mathematics. Solving numerically these equations is challenging due to the presence of several conservation laws which our finite models incorporate and which must be retained while integrating the equations of motion. In the last thirty years, the theory of geometric integration has provided a variety of techniques to tackle this problem. These numerical methods require solving both direct and inverse problems in matrix spaces. We present three algorithms to solve a cubic matrix equation arising in the geometric integration of isospectral flows. This type of ODEs includes finite models of ideal hydrodynamics, plasma dynamics, and spin particles, which we use as test problems for our algorithms., 14 pages, 1 figure

The notion of abstract convex structure generalizes the standard notion of convexity in linear spaces. We consider abstract convex structures that are combinatorial objects studied in various areas of mathematics and convex algebras as introduced in [8] and we study a general definition of convex preferences. Relations defined by aggregation of orderings are considered.

This article presents the dynamical analysis of the stochastic leprosy epidemic model. Positivity and boundedness are the criteria used in the deterministic model. A primary technique is known as the Euler Maruyama used in the solution of the said model. The standard computational methods will evaluate the design stability and efficiency based on the chosen criteria. The traditional computational methods like the stochastic Euler and the stochastic Runge Kutta fail to restore the essential features of biological problems. However, our proposed approach, the stochastic non-standard finite difference (NSFD), is used and found to be efficient, cost-effective, and accommodates all the desired feasible properties. Our method achieves all-time convergence against the backdrop of other classical techniques that perform conditionally or fail over a long period. In the end, a comparison between this scheme and the existing ones reviews the novelty of our approach.

Based on the fact that the traditional probability distribution entropy describing a local feature of the system cannot effectively capture the global topology variations of the network, some indicators constructed by the network adjacency matrix and Laplacian matrix come into being. Specifically, these measures are based on the eigenvalues of the scaled Laplace matrix, the eigenvalues of the network communicability matrix, and the spectral entropy based on information diffusion that has been proposed recently, respectively. In this article, we systematically study the dependence of these measures on the topological structure of the network. We prove from various aspects that spectral entropy has a better ability to identify the global topology than the traditional distribution entropy. Furthermore, the indicator based on the eigenvalues of the network communicability matrix achieves good results in some aspects while, overall, the spectral entropy is able to identify network topology variations from a global perspective.

Some response surface functions in complex engineering systems are usually highly nonlinear, unformed, and expensive-to-evaluate. To tackle this challenge, Bayesian optimization, which conducts sequential design via a posterior distribution over the objective function, is a critical method used to find the global optimum of black-box functions. Kernel functions play an important role in shaping the posterior distribution of the estimated function. The widely used kernel function, e.g., radial basis function (RBF), is very vulnerable and susceptible to outliers; the existence of outliers is causing its Gaussian process surrogate model to be sporadic. In this paper, we propose a robust kernel function, Asymmetric Elastic Net Radial Basis Function (AEN-RBF). Its validity as a kernel function and computational complexity are evaluated. When compared to the baseline RBF kernel, we prove theoretically that AEN-RBF can realize smaller mean squared prediction error under mild conditions. The proposed AEN-RBF kernel function can also realize faster convergence to the global optimum. We also show that the AEN-RBF kernel function is less sensitive to outliers, and hence improves the robustness of the corresponding Bayesian optimization with Gaussian processes. Through extensive evaluations carried out on synthetic and real-world optimization problems, we show that AEN-RBF outperforms existing benchmark kernel functions.

We study nested variational inequalities, which are variational inequalities whose feasible set is the solution set of another variational inequality. We present a projected averaging Tikhonov algorithm requiring the weakest conditions in the literature to guarantee the convergence to solutions of the nested variational inequality. Specifically, we only need monotonicity of the upper- and the lower-level variational inequalities. Also, we provide the first complexity analysis for nested variational inequalities considering optimality of both the upper- and lower-level.

We introduce a software package called HIFIR for preconditioning sparse, unsymmetric, ill-conditioned, and potentially singular systems. HIFIR computes a hybrid incomplete factorization, which combines multilevel incomplete LU factorization with a truncated, rank-revealing QR factorization on the final Schur complement. This novel hybridization is based on the new theory of approximate generalized inverse and $\epsilon$-accuracy. It enables near-optimal preconditioners for consistent systems and enables flexible GMRES to solve inconsistent systems when coupled with iterative refinement. In this paper, we focus on some practical algorithmic and software issues of HIFIR. In particular, we introduce a new inverse-based rook pivoting into ILU, which improves the robustness and the overall efficiency for some ill-conditioned systems by significantly reducing the size of the final Schur complement for some systems. We also describe the software design of HIFIR in terms of its efficient data structures for supporting rook pivoting in a multilevel setting, its template-based generic programming interfaces for mixed-precision real and complex values in C++, and its user-friendly high-level interfaces in MATLAB and Python. We demonstrate the effectiveness of HIFIR for ill-conditioned or singular systems arising from several applications, including the Helmholtz equation, linear elasticity, stationary incompressible Navier--Stokes equations, and time-dependent advection-diffusion equation., Comment: Submitted to ACM Transactions on Mathematical Software (TOMS)

Stochastic optimization methods have become a class of popular optimization tools in machine learning. Especially, stochastic gradient descent (SGD) has been widely used for machine learning problems such as training neural networks due to low per-iteration computational complexity. In fact, the Newton or quasi-newton methods leveraging second-order information are able to achieve a better solution than the first-order methods. Thus, stochastic quasi-Newton (SQN) methods have been developed to achieve the better solution efficiently than the stochastic first-order methods by utilizing approximate second-order information. However, the existing SQN methods still do not reach the best known stochastic first-order oracle (SFO) complexity. To fill this gap, we propose a novel faster stochastic quasi-Newton method (SpiderSQN) based on the variance reduced technique of SIPDER. We prove that our SpiderSQN method reaches the best known SFO complexity of $\mathcal{O}(n+n^{1/2}\epsilon^{-2})$ in the finite-sum setting to obtain an $\epsilon$-first-order stationary point. To further improve its practical performance, we incorporate SpiderSQN with different momentum schemes. Moreover, the proposed algorithms are generalized to the online setting, and the corresponding SFO complexity of $\mathcal{O}(\epsilon^{-3})$ is developed, which also matches the existing best result. Extensive experiments on benchmark datasets demonstrate that our new algorithms outperform state-of-the-art approaches for nonconvex optimization., Comment: 11 pages, accepted for publication by TNNLS. arXiv admin note: text overlap with arXiv:1902.02715 by other authors

Eigendecomposition of symmetric matrices is at the heart of many computer vision algorithms. However, the derivatives of the eigenvectors tend to be numerically unstable, whether using the SVD to compute them analytically or using the Power Iteration (PI) method to approximate them. This instability arises in the presence of eigenvalues that are close to each other. This makes integrating eigendecomposition into deep networks difficult and often results in poor convergence, particularly when dealing with large matrices. While this can be mitigated by partitioning the data into small arbitrary groups, doing so has no theoretical basis and makes it impossible to exploit the full power of eigendecomposition. In previous work, we mitigated this using SVD during the forward pass and PI to compute the gradients during the backward pass. However, the iterative deflation procedure required to compute multiple eigenvectors using PI tends to accumulate errors and yield inaccurate gradients. Here, we show that the Taylor expansion of the SVD gradient is theoretically equivalent to the gradient obtained using PI without relying in practice on an iterative process and thus yields more accurate gradients. We demonstrate the benefits of this increased accuracy for image classification and style transfer., Comment: IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) PREPRINT 2021

Particle swarm optimizer (PSO) and mobile robot swarm are two typical swarm techniques. Many applications emerge separately along both of them while the similarity between them is rarely considered. When a solution space is a certain region in reality, a robot swarm can replace a particle swarm to explore the optimal solution by performing PSO. In this way, a mobile robot swarm should be able to efficiently explore an area just like the particle swarm and uninterruptedly work even under the shortage of robots or in the case of unexpected failure of robots. Furthermore, the moving distances of robots are highly constrained because energy and time can be costly. Inspired by such requirements, this article proposes a moving-distance-minimized PSO (MPSO) for a mobile robot swarm to minimize the total moving distance of its robots while performing optimization. The distances between the current robot positions and the particle ones in the next generation are utilized to derive paths for robots such that the total distance that robots move is minimized, hence minimizing the energy and time for a robot swarm to locate the optima. Experiments on 28 CEC2013 benchmark functions show the advantage of the proposed method over the standard PSO. By adopting the given algorithm, the moving distance can be reduced by more than 66% and the makespan can be reduced by nearly 70% while offering the same optimization effects.

Multigrid methods are one of the most efficient techniques for solving linear systems arising from Partial Differential Equations (PDEs) and graph Laplacians from machine learning applications. One of the key components of multigrid is smoothing, which aims at reducing high-frequency errors on each grid level. However, finding optimal smoothing algorithms is problem-dependent and can impose challenges for many problems. In this paper, we propose an efficient adaptive framework for learning optimized smoothers from operator stencils in the form of convolutional neural networks (CNNs). The CNNs are trained on small-scale problems from a given type of PDEs based on a supervised loss function derived from multigrid convergence theories, and can be applied to large-scale problems of the same class of PDEs. Numerical results on anisotropic rotated Laplacian problems demonstrate improved convergence rates and solution time compared with classical hand-crafted relaxation methods.

In this paper, we consider a broad class of nonsmooth and nonconvex fractional programs, where the numerator can be written as the sum of a continuously differentiable convex function whose gradient is Lipschitz continuous and a proper lower semicontinuous (possibly nonconvex) function, and the denominator is weakly convex over the constraint set. This model problem includes the composite optimization problems studied extensively lately, and encompasses many important modern fractional optimization problems arising from diverse areas such as the recently proposed scale invariant sparse signal reconstruction problem in signal processing. We propose a proximal subgradient algorithm with extrapolations for solving this optimization model and show that the iterated sequence generated by the algorithm is bounded and any of its limit points is a stationary point of the model problem. The choice of our extrapolation parameter is flexible and includes the popular extrapolation parameter adopted in the restarted Fast Iterative Shrinking-Threshold Algorithm (FISTA). By providing a unified analysis framework of descent methods, we establish the convergence of the full sequence under the assumption that a suitable merit function satisfies the Kurdyka--{\L}ojasiewicz (KL) property. In particular, our algorithm exhibits linear convergence for the scale invariant sparse signal reconstruction problem and the Rayleigh quotient problem over spherical constraint. In the case where the denominator is the maximum of finitely many continuously differentiable weakly convex functions, we also propose an enhanced extrapolated proximal subgradient algorithm with guaranteed convergence to a stronger notion of stationary points of the model problem. Finally, we illustrate the proposed methods by both analytical and simulated numerical examples., Comment: Revised version: Oct. 16, 2020

This paper presents a rigorous but tractable study of sparsity. We postulate a definition of sparsity that is as broad as possible, so that it generates all the various measures that are useful in practice, but narrow enough that the fundamental properties of generalized sparsity still hold. As we work through the various ways of demonstrating the advantageous properties of sparsity, we illustrate its meaning from geometrical and operational perspectives. Thereafter, we construct specific measures of sparsity which are successfully qualified in complexity analysis and sparse optimization scenarios. Overall, our main objective is to construct measures of sparsity that will facilitate and enhance the design of the next innovative sensing technologies.

In this article, an adaptive swarm control within saturated input based on the nonlinear coupling degree is proposed. Swarm control is a forward study in kinematics and dynamics of the swarm system. However, the coupling degree in the previous work can only manifest whether the agents in the swarm being connected or not, ignoring the connection strength. As a result, the nonlinear coupling degree is proposed, which is more suitable for practical engineering than the previous coupling degree. Based on the nonlinear coupling degree, we put forward novel swarm kinematics and dynamics. Besides, the effects of input saturation and nonlinear dynamics should be considered for this novel swarm control based on the nonlinear coupling degree. Therefore, we introduce the backstepping method to design an adaptive swarm controller. With this controller, the input saturation auxiliary system is designed to reduce the effects of input saturation, and a radial basis function neural network (RBF-NN) is introduced to approximate the nonlinear dynamics. To overcome the differential explosion in the backstepping method, a command filter is put forward to reduce the amount of calculation and reduces the difficulty of the controller design. It is proved that the proposed controller ensures stability based on the Lyapunov stability theory. Finally, the simulation results of a multiagent system composed of six omnidirectional mobile robots illustrate the validity of the proposed controller.

Investigation of spectral (collocation or Galerkin) methods for the solution approximation of different classes of optimal control problems have had been increased in recent years. In this research work, we proposed and analyzed an applicable Legendre spectral collocation approach, based on an efficient space of fractional basis functions, to compute numerically the solution of fractional optimal control problems. We first introduce a fractional Lagrange interpolation and then approximate the unknown control and state by this new set of fractional interpolation functions. The problem is discretized in terms of shifted Legendre–Gauss collocation points and two approaches are suggested to calculate the exact fractional differentiation matrix. Also, we prove that the approximate solutions of the obtained discretized problem converge to the optimal solution of the main problem by assuming some mild conditions. The method is implemented for three numerical test problems to show the claimed efficiency and capability.

In this paper, we study second-order optimality conditions for nonconvex set-constrained optimization problems. For a convex set-constrained optimization problem, it is well known that second-order optimality conditions involve the support function of the second-order tangent set. In this paper, we propose two approaches for establishing second-order optimality conditions for the nonconvex case. In the first approach, we extend the concept of the support function so that it is applicable to general nonconvex set-constrained problems, whereas in the second approach, we introduce the notion of the directional regular tangent cone and apply classical results of convex duality theory. Besides the second-order optimality conditions, the novelty of our approach lies in the systematic introduction and use, respectively, of directional versions of well-known concepts from variational analysis.

This article studies the problem of multiobjective control design for a class of human–machine systems (HMSs) with safety performance constraints containing state constraints and input constraints. The HMSs under consideration not only monitor the human but also need to take proper actions to both the human and machine. A model of controlled hidden Markov jump system (CHMJS) is applied to represent the HMSs. Based on the CHMJS model, a sufficient condition for the practical mean square stability of the unconstrained HMSs is first derived using a stochastic Lyapunov functional. A sufficient condition for ensuring the safety performance constraints of the HMSs is also deduced by employing reachability analysis and set invariance theory. Subsequently, a bilinear matrix inequality-based control design is presented to guarantee both the practical mean square stability and safety performance constraints of the HMSs. A multiobjective optimization problem (MOP) is then formulated to determine a feedback controller for the human and a human-assistance controller for the machine such that both the practical mean square stability and safety performance constraints as well as the less human intervention can be satisfied. An algorithm that mixes the multiobjective particle swarm optimization and linear matrix inequality technique is developed to solve this MOP. Finally, a lane departure example is given to illustrate its effectiveness.

In this work, we propose integral global optimality conditions for multiobjective problems not necessarily differentiable. The integral characterization, already known for single objective problems, are extended to multiobjective problems by weighted sum and Chebyshev weighted scalarizations. Using this last scalarization, we propose an algorithm for obtaining an approximation of the weak Pareto front whose effectiveness is illustrated by solving a collection of multiobjective test problems.

For compact self-adjoint operators in Hilbert spaces, two algorithms are proposed to provide fully computable a posteriori error estimate for eigenfunction approximation. Both algorithms apply well to the case of tight clusters and multiple eigenvalues, under the settings of target eigenvalue problems. Algorithm I is based on the Rayleigh quotient and the min-max principle that characterizes the eigenvalue problems. The formula for the error estimate provided by Algorithm I is easy to compute and applies to problems with limited information of Rayleigh quotients. Algorithm II, as an extension of the Davis--Kahan method, takes advantage of the dual formulation of differential operators along with the Prager--Synge technique and provides greatly improved accuracy of the estimate, especially for the finite element approximations of eigenfunctions. Numerical examples of eigenvalue problems of matrices and the Laplace operators over convex and non-convex domains illustrate the efficiency of the proposed algorithms., 39 pages, 12 tables, 9 figures

A principal singular vector based on multiple Toeplitz matrices is proposed to solve the accuracy problem of direction-of-arrival (DOA) estimation for coherent signals. First, the data matrix received by uniform linear array (ULA) is transformed into a Toeplitz matrix. An equivalent covariance matrix is obtained by square weighted summation method using the Toeplitz matrix. Then, a polynomial containing DOA information is constructed because the signal space and the steering matrix have the same column space; the Toeplitz matrix is built using polynomial coefficients. The problem is transformed into solving linear equations by establishing the relationship between the Toeplitz matrix and the signal subspace. Furthermore, the weighted least square method is used to obtain multiple candidates for linear equations. Finally, the maximum likelihood (ML) rule is used to select source signal candidates from multiple candidates. In comparison with currently known algorithm, the proposed algorithm has the characteristics of high estimation accuracy, low-complexity, and strong anti-interference ability and resolution. Even when the signal-to-noise ratio (SNR) is low, the snapshot number is small, and multiple signals exist; this method can still provide good estimation performance and resolution, which is more than 90% in most cases. Simulation experiments verify the superiority of the algorithm.

Aim. Development of the method of multi objective synthesis of nonlinear robust control by multimass electromechanical systems to satisfy various requirements for the operation of multi-mass systems in various modes. Methodology. The problem of multi objective synthesis of nonlinear robust control of multimass electromechanical systems is formulated and the possibility of satisfying various requirements for the operation of such systems in various modes based on the concept of functionally multiple membership of the state vector and the solution of the Hamilton-Jacobi-Isaacs equation is shown. A method for choosing weight matrices with the help the vector of purpose of nonlinear robust control is formed by solving a zero-sum vector antagonistic game has been substantiated and developed. Results. The results multi objective synthesis of nonlinear robust two-mass electromechanical servo systems in which differences requirements for the operation of such systems in various modes were satisfied are given. Based on the results of modeling and experimental studies it is established, that with the help of synthesized robust nonlinear controllers, it is possible to improve of quality indicators of two-mass electromechanical servo system in comparison with the system with standard regulators. Originality. For the first time the method of multi objective synthesis of nonlinear robust control by multimass electromechanical systems to satisfy various requirements for the operation of multimass systems in various modes is developed. Practical value. From the point of view of the practical implementation the possibility of solving the problem of multi objective synthesis of nonlinear robust control systems to satisfy various requirements for the operation of multimass electromechanical systems in various modes is shown., Мета. Розробка методу багатокритеріального синтезу нелінійного робастного керування багатомасовими електромеханічними системами для задоволення різноманітних вимог до роботи багатомасових систем у різних режимах. Методологія. Сформульовано задачу багатокритеріального синтезу нелінійного робастного керування багатомасовими електромеханічними системами та показана можливість задоволення різноманітних вимог до роботи таких систем у різних режимах на основі концепції функціонально множинної належності вектора стану та рішення рівняння Гамільтона-Якобі-Айзекса. Обґрунтовано та розроблено метод вибору вагових матриць, за допомогою яких формується вектор мети нелінійного робастного керування, шляхом розв’язання векторної антагоністичної гри з нульовою сумою. Результати. Наведено результати багатокритеріального синтезу нелінійних робастних двомасових електромеханічних сервосистем керування, в яких були задоволені різноманітні вимоги до роботи таких систем у різних режимах. На основі результатів моделювання та експериментальних досліджень встановлено, що за допомогою синтезованих нелінійних робастних регуляторів можна підвищити якісні показники двомасової електромеханічної сервосистеми в порівнянні з системою зі стандартними регуляторами. Оригінальність. Вперше розроблено метод багатокритеріального синтезу нелінійного робастного керування багатомасовими електромеханічними системами для задоволення різноманітних вимог до роботи багатомасових систем у різних режимах. Практичне значення. З точки зору практичної реалізації показана можливість вирішення задачі багатокритеріального синтезу нелінійних робастних електромеханічних систем керування для задоволення різноманітних вимог до роботи таких систем у різних режимах.

This paper studies the energy-to-peak filter design problem for the continuous-time nonlinear singular systems. A Takagi-Sugeno (T-S) fuzzy model is constructed to represent the nonlinear plant. The paper focuses on the fuzzy filter design for singular systems such that the formulated filtering error system is admissible (regular, impulse-free and stable) and ensures the corresponding filtering performance in the singular systems. By introducing a novel Lyapunov function, design conditions of the fuzzy filter for the continuous-time singular systems are proposed in the light of linear matrix inequalities (LMIs) representations. Finally, a practical example and the relevant simulation results are provided to demonstrate the effectiveness and feasibility of the proposed energy-to-peak filter design approach.

This article considers the decentralized stabilization problem of continuous-time nonlinear systems subject to unmatched interconnections and asymmetric input constraints. Initially, with the nonquadratic value functions being introduced to constrained auxiliary subsystems, the decentralized stabilization problem is converted into an array of nonlinear optimal control problems. It is proved that all solutions of these nonlinear optimal control problems together assure asymptotic stability of the entire system. Then, in the framework of adaptive critics, the critic-only architecture is built to solve the Hamilton-Jacobi-Bellman equations associated with these solutions. The critic-only architecture is implemented via critic neural networks (NNs) with their weight vectors being tuned through an improved gradient descent method. A remarkable feature of the present gradient descent approach is that it simultaneously utilizes previously stored and instantaneous state data, which makes the persistence of excitation conditions relaxed. After that, with Lyapunov’s techniques being employed, asymptotic stability of the closed-loop auxiliary subsystems and uniform ultimate boundedness of the critic NNs’ weight estimation errors are demonstrated. Finally, simulations of an unmatched interconnected nonlinear plant are provided to validate the present decentralized control method.

In this paper, an integrated guidance and control approach is presented to improve the performance of the missile interception. The approach includes damping augmented system with attitude rate feedback to decrease the oscillation during the homing phase for missiles with low damping. In addition, physical constraints, which can affect the performance of the missile interception, such as acceleration limit, seeker’s look angle, and look angle rate constraints are considered. The integrated guidance and control problem is formulated as a convex quadratic optimization problem with equality and inequality constraints, and the solution is obtained by a primal–dual interior point method. The performance of the proposed method is verified through several numerical examples.

This paper presents a new sampled-data-based event-triggered pointwise security controller by pointwise measurements for partial differential equation (PDE) systems under stochastic cyber-attacks. First, according to the Takagi--Sugeno fuzzy model, the considered nonlinear system is reconstructed and an event-triggered pointwise fuzzy controller is proposed with pointwise measurements. Moreover, networked control systems (NCSs) are introduced to improve the transmission convenience; however, two deception cyber-attacks with different characteristics are brought into PDE systems for the first time. In addition, based on novel Lyapunov-Krasovskii functionals (LKFs), some relaxed conditions to assure system's exponential stability are established. Finally, the effectiveness and practicability of the designed controller are demonstrated by numerical and application examples.

Multipopulation methods are highly effective in solving dynamic optimization problems. Three factors affect this significantly: 1) the exclusion mechanisms to avoid the convergence to the same peak by multiple subpopulations; 2) the resource allocation mechanism that assigns the computational resources to the subpopulations; and 3) the control mechanisms to adaptively adjust the number of subpopulations by considering the number of optima and available computational resources. In the existing exclusion mechanisms, when the distance (i.e., the distance between their best found positions) between two subpopulations becomes less than a predefined threshold, the inferior one will be removed/reinitialized. However, this leads to incapability of algorithms in covering peaks/optima that are closer than the threshold. Moreover, despite the importance of resource allocation due to the limited available computational resources between environmental changes, it has not been well studied in the literature. Finally, the number of subpopulations should be adapted to the number of optima. However, in most existing adaptive multipopulation methods, there is no predefined upper bound for generating subpopulations. Consequently, in problems with large numbers of peaks, they can generate too many subpopulations sharing limited computational resources. In this article, a multipopulation framework is proposed to address the aforementioned issues by using three adaptive approaches: 1) subpopulation generation; 2) double-layer exclusion; and 3) computational resource allocation. The experimental results demonstrate the superiority of the proposed framework over several peer approaches in solving various benchmark problems.

The first part of this work established the foundations of a radial duality between nonnegative optimization problems, inspired by the work of (Renegar, 2016). Here we utilize our radial duality theory to design and analyze projection-free optimization algorithms that operate by solving a radially dual problem. In particular, we consider radial subgradient, smoothing, and accelerated methods that are capable of solving a range of constrained convex and nonconvex optimization problems and that can scale-up more efficiently than their classic counterparts. These algorithms enjoy the same benefits as their predecessors, avoiding Lipschitz continuity assumptions and costly orthogonal projections, in our newfound, broader context. Our radial duality further allows us to understand the effects and benefits of smoothness and growth conditions on the radial dual and consequently on our radial algorithms., A two-part work. See the first part for the foundations, establishing the uniqueness and calculus of this nonnegative optimization duality

We find an algorithmic procedure that enables the computation and description of the structure of the isotropy subgroups of the group of complex orthogonal matrices with respect to the action of similarity on complex symmetric matrices. A key step in our proof is to solve a certain rectangular block upper triangular Toeplitz matrix equation.

Discrete optimal transport problems give rise to very large linear programs (LPs) with a particular structure of the constraint matrix. In this paper, we present a hybrid algorithm that mixes an interior point method (IPM) and column generation, specialized for the LP originating from the Kantorovich optimal transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we propose a column generation–like technique to force all intermediate iterates to be as sparse as possible. The algorithm is implemented nearly matrix-free. Indeed, most of the computations avoid forming the huge matrices involved and solve the Newton system using only a much smaller Schur complement of the normal equations. We prove theoretical results about the sparsity pattern of the optimal solution, exploiting the graph structure of the underlying problem. We use these results to mix iterative and direct linear solvers efficiently in a way that avoids producing preconditioners or factorizations with excessive fill-in and at the same time guaranteeing a low number of conjugate gradient iterations. We compare the proposed method with two state-of-the-art solvers and show that it can compete with the best network optimization tools in terms of computational time and memory use. We perform experiments with problems reaching more than four billion variables and demonstrate the robustness of the proposed method. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: F. Zanetti received funding from the University of Edinburgh, in the form of a PhD scholarship. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0184 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0184 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .