The Experts below are selected from a list of 7992 Experts worldwide ranked by ideXlab platform
Sergio Grammatico - One of the best experts on this subject based on the ideXlab platform.
-
on the convergence of discrete time linear systems a linear time varying mann Iteration Converges iff its operator is strictly pseudocontractive
IEEE Control Systems Letters, 2018Co-Authors: Giuseppe Belgioioso, Filippo Fabiani, Franco Blanchini, Sergio GrammaticoAbstract:We adopt an operator-theoretic perspective to study convergence of linear fixed-point Iterations and discrete-time linear systems. We mainly focus on the so-called Krasnoselskij–Mann Iteration, ${x}$ ( $k + 1$ ) = ( $1-\alpha _{k}$ ) ${x}$ ( ${k}$ ) + $\alpha _{k} A~{x}$ ( ${k}$ ), which is relevant for distributed computation in optimization and game theory, when $A$ is not available in a centralized way. We show that strict pseudocontractiveness of the linear operator $x \mapsto Ax$ is not only sufficient (as known) but also necessary for the convergence to a vector in the kernel of $I-A$ . We also characterize some relevant operator-theoretic properties of linear operators via eigenvalue location and linear matrix inequalities. We apply the convergence conditions to multi-agent linear systems with vanishing step sizes, in particular, to linear consensus dynamics and equilibrium seeking in monotone linear-quadratic games.
Mortari Daniele - One of the best experts on this subject based on the ideXlab platform.
-
Fuel-Efficient Powered Descent Guidance on Large Planetary Bodies via Theory of Functional Connections
'Springer Science and Business Media LLC', 2020Co-Authors: Johnston Hunter, Schiassi Enrico, Furfaro Roberto, Mortari DanieleAbstract:In this paper we present a new approach to solve the fuel-efficient powered descent guidance problem on large planetary bodies with no atmosphere (e.g. the Moon or Mars) using the recently developed Theory of Functional Connections. The problem is formulated using the indirect method which casts the optimal guidance problem as a system of nonlinear two-point boundary value problems. Using the Theory of Functional Connections, the problem constraints are analytically embedded into a "constrained expression," which maintains a free-function that is expanded using orthogonal polynomials with unknown coefficients. The constraints are satisfied regardless of the values of the unknown coefficients which convert the two-point boundary value problem into an unconstrained optimization problem. This process casts the solution into the admissible subspace of the problem and therefore simple numerical techniques can be used (i.e. in this paper a nonlinear least-squares method is used). In addition to the derivation of this technique, the method is validated in two scenarios and the results are compared to those obtained by the general purpose optimal control software, GPOPS-II. In general, the proposed technique produces solutions of $\mathcal{O}(10^{-10})$. Additionally, for the proposed test cases, it is reported that each individual TFC-based inner-loop Iteration Converges within 6 Iterations, each Iteration exhibiting a computational time between 72 and 81 milliseconds within the MATLAB legacy implementation. Consequently, the proposed methodology is potentially suitable for on-board generation of optimal trajectories in real-time.Comment: 17 pages, 10 figures, 6 table
-
Fuel-Efficient Powered Descent Guidance on Large Planetary Bodies via Theory of Functional Connections
'Springer Science and Business Media LLC', 2020Co-Authors: Johnston Hunter, Schiassi Enrico, Furfaro Roberto, Mortari DanieleAbstract:In this paper we present a new approach to solve the fuel-efficient powered descent guidance problem on large planetary bodies with no atmosphere (e.g., Moon or Mars) using the recently developed Theory of Functional Connections. The problem is formulated using the indirect method which casts the optimal guidance problem as a system of nonlinear two-point boundary value problems. Using the Theory of Functional Connections, the problem's linear constraints are analytically embedded into a functional, which maintains a free-function that is expanded using orthogonal polynomials with unknown coefficients. The constraints are always analytically satisfied regardless of the values of the unknown coefficients (e.g., the coefficients of the free-function) which converts the two-point boundary value problem into an unconstrained optimization problem. This process reduces the whole solution space into the admissible solution subspace satisfying the constraints and, therefore, simpler, more accurate, and faster numerical techniques can be used to solve it. In this paper a nonlinear least-squares method is used. In addition to the derivation of this technique, the method is validated in two scenarios and the results are compared to those obtained by the general purpose optimal control software, GPOPS-II. In general, the proposed technique produces solutions of O(10(-10)) accuracy. Additionally, for the proposed test cases, it is reported that each individual TFC-based inner-loop Iteration Converges within 6 Iterations, each Iteration exhibiting a computational time between 72 and 81 milliseconds, with a total execution time of 2.1 to 2.6 seconds using MATLAB. Consequently, the proposed methodology is potentially suitable for real-time computation of optimal trajectories.Johnson Space Center12 month embargo; published 25 September 2020This item from the UA Faculty Publications collection is made available by the University of Arizona with support from the University of Arizona Libraries. If you have questions, please contact us at repository@u.library.arizona.edu
Sharify Meisam - One of the best experts on this subject based on the ideXlab platform.
-
Algorithmes de mise à l'échelle et méthodes tropicales en analyse numérique matricielle
2011Co-Authors: Sharify Meisam, Gaubert StéphaneAbstract:L'Algèbre tropicale peut être considérée comme un domaine relativement nouveau en mathématiques. Elle apparait dans plusieurs domaines telles que l'optimisation, la synchronisation de la production et du transport, les systèmes à événements discrets, le contrôle optimal, la recherche opérationnelle, etc. La première partie de ce manuscrit est consacrée a l'étude des applications de l'algèbre tropicale à l'analyse numérique matricielle. Nous considérons tout d'abord le problème classique de l'estimation des racines d'un polynôme univarié. Nous prouvons plusieurs nouvelles bornes pour la valeur absolue des racines d'un polynôme en exploitant les méthodes tropicales. Ces résultats sont particulièrement utiles lorsque l'on considère des polynômes dont les coefficients ont des ordres de grandeur différents. Nous examinons ensuite le problème du calcul des valeurs propres d'une matrice polynomiale. Ici, nous introduisons une technique de mise à l'échelle générale, basée sur l'algèbre tropicale, qui s'applique en particulier à la forme compagnon. Cette mise à l'échelle est basée sur la construction d'une fonction polynomiale tropicale auxiliaire, ne dépendant que de la norme des matrices. Les raciness (les points de non-différentiabilité) de ce polynôme tropical fournissent une pré-estimation de la valeur absolue des valeurs propres. Ceci se justifie en particulier par un nouveau résultat montrant que sous certaines hypothèses faites sur le conditionnement, il existe un groupe de valeurs propres bornées en norme. L'ordre de grandeur de ces bornes est fourni par la plus grande racine du polynôme tropical auxiliaire. Un résultat similaire est valable pour un groupe de petites valeurs propres. Nous montrons expérimentalement que cette mise à l'échelle améliore la stabilité numérique, en particulier dans des situations où les données ont des ordres de grandeur différents. Nous étudions également le problème du calcul des valeurs propres tropicales (les points de non-différentiabilité du polynôme caractéristique) d'une matrice polynômiale tropicale. Du point de vue combinatoire, ce problème est équivalent à trouver une fonction de couplage: la valeur d'un couplage de poids maximum dans un graphe biparti dont les arcs sont valués par des fonctions convexes et linéaires par morceaux. Nous avons développé un algorithme qui calcule ces valeurs propres tropicales en temps polynomial. Dans la deuxième partie de cette thèse, nous nous intéressons à la résolution de problèmes d'affectation optimale de très grande taille, pour lesquels les algorithms séquentiels classiques ne sont pas efficaces. Nous proposons une nouvelle approche qui exploite le lien entre le problème d'affectation optimale et le problème de maximisation d'entropie. Cette approche conduit à un algorithme de prétraitement pour le problème d'affectation optimale qui est basé sur une méthode itérative qui élimine les entrées n'appartenant pas à une affectation optimale. Nous considérons deux variantes itératives de l'algorithme de prétraitement, l'une utilise la méthode Sinkhorn et l'autre utilise la méthode de Newton. Cet algorithme de prétraitement ramène le problème initial à un problème beaucoup plus petit en termes de besoins en mémoire. Nous introduisons également une nouvelle méthode itérative basée sur une modification de l'algorithme Sinkhorn, dans lequel un paramètre de déformation est lentement augmenté. Nous prouvons que cette méthode itérative(itération de Sinkhorn déformée) converge vers une matrice dont les entrées non nulles sont exactement celles qui appartiennent aux permutations optimales. Une estimation du taux de convergence est également présentéeTropical algebra, which can be considered as a relatively new field in Mathematics, emerged in several branches of science such as optimization, synchronization of production and transportation, discrete event systems, optimal control, operations research, etc. The first part of this manuscript is devoted to the study of the numerical applications of tropical algebra. We start by considering the classical problem of estimating the roots of a univariate complex polynomial. We prove several new bounds for the modulus of the roots of a polynomial exploiting tropical methods. These results are specially useful when considering polynomials whose coefficients have different orders of magnitude. We next consider the problem of computing the eigenvalues of a matrix polynomial. Here, we introduce a general scaling technique, based on tropical algebra, which applies in particular to the companion form. This scaling is based on the construction of an auxiliary tropical polynomial function, depending only on the norms of the matrices. The roots (non-differentiability points) of this tropical polynomial provide a priori estimates of the modulus of the eigenvalues. This is justified in particular by a new location result, showing that under assumption involving condition numbers, there is one group of large eigenvalues, which have a maximal order of magnitude, given by the largest root of the auxiliary tropical polynomial. A similar result holds for a group of small eigenvalues. We show experimentally that this scaling improves the backward stability of the computations, particularly in situations when the data have various orders of magnitude. We also study the problem of computing the tropical eigenvalues (non-differentiability points of the characteristic polynomial) of a tropical matrix polynomial. From the combinatorial perspective, this problem can be interpreted as finding the maximum weighted matching function in a bipartite graph whose arcs are valued by convex piecewise linear functions. We developed an algorithm which computes the tropical eigenvalues in polynomial time. In the second part of this thesis, we consider the problem of solving very large instances of the optimal assignment problems (so that standard sequential algorithms cannot be used). We propose a new approach exploiting the connection between the optimal assignment problem and the entropy maximization problem. This approach leads to a preprocessing algorithm for the optimal assignment problem which is based on an iterative method that eliminates the entries not belonging to an optimal assignment. We consider two variants of the preprocessing algorithm, one by using the Sinkhorn Iteration and the other by using Newton Iteration. This preprocessing algorithm can reduce the initial problem to a much smaller problem in terms of memory requirements. We also introduce a new iterative method based on a modification of the Sinkhorn scaling algorithm, in which a deformation parameter is slowly increased We prove that this iterative method, referred to as the deformed-Sinkhorn Iteration, Converges to a matrix whose nonzero entries are exactly those belonging to the optimal permutations. An estimation of the rate of convergence is also presentedPALAISEAU-Polytechnique (914772301) / SudocSudocFranceF
-
Algorithmes de mise à l'échelle et méthodes tropicales en analyse numérique matricielle
HAL CCSD, 2011Co-Authors: Sharify MeisamAbstract:Tropical algebra, which can be considered as a relatively new field in Mathematics, emerged in several branches of science such as optimization, synchronization of production and transportation, discrete event systems, optimal control, operations research, etc. The first part of this manuscript is devoted to the study of the numerical applications of tropical algebra. We start by considering the classical problem of estimating the roots of a univariate complex polynomial. We prove several new bounds for the modulus of the roots of a polynomial exploiting tropical methods. These results are specially useful when considering polynomials whose coefficients have different orders of magnitude. We next consider the problem of computing the eigenvalues of a matrix polynomial. Here, we introduce a general scaling technique, based on tropical algebra, which applies in particular to the companion form. This scaling is based on the construction of an auxiliary tropical polynomial function, depending only on the norms of the matrices. The roots (non-differentiability points) of this tropical polynomial provide a priori estimates of the modulus of the eigenvalues. This is justified in particular by a new location result, showing that under assumption involving condition numbers, there is one group of large eigenvalues, which have a maximal order of magnitude, given by the largest root of the auxiliary tropical polynomial. A similar result holds for a group of small eigenvalues. We show experimentally that this scaling improves the backward stability of the computations, particularly in situations when the data have various orders of magnitude. We also study the problem of computing the tropical eigenvalues (non-differentiability points of the characteristic polynomial) of a tropical matrix polynomial. From the combinatorial perspective, this problem can be interpreted as finding the maximum weighted matching function in a bipartite graph whose arcs are valued by convex piecewise linear functions. We developed an algorithm which computes the tropical eigenvalues in polynomial time. In the second part of this thesis, we consider the problem of solving very large instances of the optimal assignment problems (so that standard sequential algorithms cannot be used). We propose a new approach exploiting the connection between the optimal assignment problem and the entropy maximization problem. This approach leads to a preprocessing algorithm for the optimal assignment problem which is based on an iterative method that eliminates the entries not belonging to an optimal assignment. We consider two variants of the preprocessing algorithm, one by using the Sinkhorn Iteration and the other by using Newton Iteration. This preprocessing algorithm can reduce the initial problem to a much smaller problem in terms of memory requirements. We also introduce a new iterative method based on a modification of the Sinkhorn scaling algorithm, in which a deformation parameter is slowly increased We prove that this iterative method, referred to as the deformed-Sinkhorn Iteration, Converges to a matrix whose nonzero entries are exactly those belonging to the optimal permutations. An estimation of the rate of convergence is also presented.L'Algèbre tropicale peut être considérée comme un domaine relativement nouveau en mathématiques. Elle apparait dans plusieurs domaines telles que l'optimisation, la synchronisation de la production et du transport, les systèmes à événements discrets, le contrôle optimal, la recherche opérationnelle, etc. La première partie de ce manuscrit est consacrée a l'étude des applications de l'algèbre tropicale à l'analyse numérique matricielle. Nous considérons tout d'abord le problème classique de l'estimation des racines d'un polynôme univarié. Nous prouvons plusieurs nouvelles bornes pour la valeur absolue des racines d'un polynôme en exploitant les méthodes tropicales. Ces résultats sont particulièrement utiles lorsque l'on considère des polynômes dont les coefficients ont des ordres de grandeur différents. Nous examinons ensuite le problème du calcul des valeurs propres d'une matrice polynomiale. Ici, nous introduisons une technique de mise à l'échelle générale, basée sur l'algèbre tropicale, qui s'applique en particulier à la forme compagnon. Cette mise à l'échelle est basée sur la construction d'une fonction polynomiale tropicale auxiliaire, ne dépendant que de la norme des matrices. Les raciness (les points de non-différentiabilité) de ce polynôme tropical fournissent une pré-estimation de la valeur absolue des valeurs propres. Ceci se justifie en particulier par un nouveau résultat montrant que sous certaines hypothèses faites sur le conditionnement, il existe un groupe de valeurs propres bornées en norme. L'ordre de grandeur de ces bornes est fourni par la plus grande racine du polynôme tropical auxiliaire. Un résultat similaire est valable pour un groupe de petites valeurs propres. Nous montrons expérimentalement que cette mise à l'échelle améliore la stabilité numérique, en particulier dans des situations où les données ont des ordres de grandeur différents. Nous étudions également le problème du calcul des valeurs propres tropicales (les points de non-différentiabilité du polynôme caractéristique) d'une matrice polynômiale tropicale. Du point de vue combinatoire, ce problème est équivalent à trouver une fonction de couplage: la valeur d'un couplage de poids maximum dans un graphe biparti dont les arcs sont valués par des fonctions convexes et linéaires par morceaux. Nous avons développé un algorithme qui calcule ces valeurs propres tropicales en temps polynomial. Dans la deuxième partie de cette thèse, nous nous intéressons à la résolution de problèmes d'affectation optimale de très grande taille, pour lesquels les algorithms séquentiels classiques ne sont pas efficaces. Nous proposons une nouvelle approche qui exploite le lien entre le problème d'affectation optimale et le problème de maximisation d'entropie. Cette approche conduit à un algorithme de prétraitement pour le problème d'affectation optimale qui est basé sur une méthode itérative qui élimine les entrées n'appartenant pas à une affectation optimale. Nous considérons deux variantes itératives de l'algorithme de prétraitement, l'une utilise la méthode Sinkhorn et l'autre utilise la méthode de Newton. Cet algorithme de prétraitement ramène le problème initial à un problème beaucoup plus petit en termes de besoins en mémoire. Nous introduisons également une nouvelle méthode itérative basée sur une modification de l'algorithme Sinkhorn, dans lequel un paramètre de déformation est lentement augmenté. Nous prouvons que cette méthode itérative(itération de Sinkhorn déformée) converge vers une matrice dont les entrées non nulles sont exactement celles qui appartiennent aux permutations optimales. Une estimation du taux de convergence est également présentée
Giuseppe Belgioioso - One of the best experts on this subject based on the ideXlab platform.
-
on the convergence of discrete time linear systems a linear time varying mann Iteration Converges iff its operator is strictly pseudocontractive
IEEE Control Systems Letters, 2018Co-Authors: Giuseppe Belgioioso, Filippo Fabiani, Franco Blanchini, Sergio GrammaticoAbstract:We adopt an operator-theoretic perspective to study convergence of linear fixed-point Iterations and discrete-time linear systems. We mainly focus on the so-called Krasnoselskij–Mann Iteration, ${x}$ ( $k + 1$ ) = ( $1-\alpha _{k}$ ) ${x}$ ( ${k}$ ) + $\alpha _{k} A~{x}$ ( ${k}$ ), which is relevant for distributed computation in optimization and game theory, when $A$ is not available in a centralized way. We show that strict pseudocontractiveness of the linear operator $x \mapsto Ax$ is not only sufficient (as known) but also necessary for the convergence to a vector in the kernel of $I-A$ . We also characterize some relevant operator-theoretic properties of linear operators via eigenvalue location and linear matrix inequalities. We apply the convergence conditions to multi-agent linear systems with vanishing step sizes, in particular, to linear consensus dynamics and equilibrium seeking in monotone linear-quadratic games.
Marc Quincampoix - One of the best experts on this subject based on the ideXlab platform.
-
on the reachability problem for uncertain hybrid systems
IEEE Transactions on Automatic Control, 2007Co-Authors: Yan Gao, John Lygeros, Marc QuincampoixAbstract:In this paper, we revisit the problem of designing controllers to meet safety specifications for hybrid systems, whose evolution is affected by both control and disturbance inputs. The problem is formulated as a dynamic game and an appropriate notion of hybrid strategy for the control inputs is developed. The design of hybrid strategies to meet safety specifications is based on an Iteration of alternating discrete and continuous safety calculations. We show that, under certain assumptions, the Iteration Converges to a fixed point, which turns out to be the maximal set of states for which the safety specifications can be met. The continuous part of the calculation relies on the computation of the set of winning states for one player in a two player, two target, pursuit evasion differential game. We develop a characterization of these winning states (as well as the winning states for the other player for completeness) using methods from nonsmooth analysis and viability theory.
