Search

Your search keyword '"Descent (mathematics)"' showing total 30 results
Start Over Descriptor "Descent (mathematics)" Search Limiters Full Text Publisher hal ccsd
30 results on '"Descent (mathematics)"'

1. Motivic integration and Milnor fiber

Author

Yimu Yin, Goulwen Fichou, Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, and Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)

Subjects
Pure mathematics, Matching (graph theory), Fiber (mathematics), Applied Mathematics, General Mathematics, Resolution of singularities, Mathematical proof, Motivic zeta function, symbols.namesake, Mathematics - Algebraic Geometry, Mathematics::Logic, Mathematics::Algebraic Geometry, 14E18, 12J25, 14B05, Euler's formula, symbols, FOS: Mathematics, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Motivic integration, Algebraic Geometry (math.AG), ComputingMilieux_MISCELLANEOUS, Mathematics, Descent (mathematics)
Abstract

We put forward in this paper a uniform narrative that weaves together several variants of Hrushovski-Kazhdan style integral, and describe how it can facilitate the understanding of the Denef-Loeser motivic Milnor fiber and closely related objects. Our study focuses on the so-called "nonarchimedean Milnor fiber" that was introduced by Hrushovski and Loeser, and our thesis is that it is a richer embodiment of the underlying philosophy of the Milnor construction. The said narrative is first developed in the more natural complex environment, and is then extended to the real one via descent. In the process of doing so, we are able to provide more illuminating new proofs, free of resolution of singularities, of a few pivotal results in the literature, both complex and real. To begin with, the real motivic zeta function is shown to be rational, which yields the real motivic Milnor fiber; this is an analogue of the Hrushovski-Loeser construction. We also establish, in a much more intuitive manner, a new Thom-Sebastiani formula, which can be specialized to the one given by Guibert, Loeser, and Merle. Finally, applying $T$-convex integration after descent, matching the Euler Characteristics of the topological Milnor fiber and the motivic Milnor fiber becomes a matter of simple computation, which is not only free of resolution of singularities as in the Hrushovski-Loeser proof, but is also free of other sophisticated algebro-geometric machineries.

Published
2022

2. K-theory of valuation rings

Author

Matthew Morrow, Shane Kelly, Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)), and Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Noetherian, Pure mathematics, Algebra and Number Theory, Mathematics::Commutative Algebra, 010102 general mathematics, K-Theory and Homology (math.KT), Mathematical proof, K-theory, 01 natural sciences, Valuation (logic), Mathematics::K-Theory and Homology, Mathematics - K-Theory and Homology, 0103 physical sciences, FOS: Mathematics, [MATH.MATH-KT]Mathematics [math]/K-Theory and Homology [math.KT], 010307 mathematical physics, 0101 mathematics, Algebraic number, Descent (mathematics), Mathematics
Abstract

We prove several results showing that the algebraic$K$-theory of valuation rings behaves as though such rings were regular Noetherian, in particular an analogue of the Geisser–Levine theorem. We also give some new proofs of known results concerning cdh descent of algebraic$K$-theory.

Published
2021

3. Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization

Author

Jeremy E. Cohen, Le Thi Khanh Hien, Andersen Man Shun Ang, Nicolas Gillis, Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio (PANAMA), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), FNRS, Fonds Wetenschappelijk Onderzoek - Vlaanderen, O005318F-RG47, ANR-20-CE23-0010,LoRAiA,Approximations de rang faible pour l'intelligence artificielle(2020), European Project: 679515,H2020,ERC-2015-STG,COLORAMAP(2016), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Inria Rennes – Bretagne Atlantique, and Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Heuristic (computer science), Extrapolation, MathematicsofComputing_NUMERICALANALYSIS, Machine Learning (stat.ML), 010103 numerical & computational mathematics, 01 natural sciences, Machine Learning (cs.LG), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Convergence (routing), FOS: Mathematics, Mathematics - Numerical Analysis, Nonnegative tensor factorization, 0101 mathematics, Coordinate descent, Mathematics - Optimization and Control, Computational budget, Block (data storage), Mathematics, Descent (mathematics), Algebra and Number Theory, Applied Mathematics, Numerical Analysis (math.NA), 010101 applied mathematics, Optimization and Control (math.OC), Algorithm
Abstract

This paper is concerned with improving the empirical convergence speed of block-coordinate descent algorithms for approximate nonnegative tensor factorization (NTF). We propose an extrapolation strategy in-between block updates, referred to as heuristic extrapolation with restarts (HER). HER significantly accelerates the empirical convergence speed of most existing block-coordinate algorithms for dense NTF, in particular for challenging computational scenarios, while requiring a negligible additional computational budget., 32 pages, 24 figures

Published
2021

4. A bilevel model for public transport demand estimation

Author

Neila Bhouri, Jean-Patrick Lebacque, Pablo A. Lotito, Victoria M. Orlando, Génie des Réseaux de Transport Terrestres et Informatique Avancée (COSYS-GRETTIA ), Université Gustave Eiffel, PLADEMA (PLADEMA), Comisión Nacional de Energía Atómica [ARGENTINA] (CNEA)-Universidad Nacional del Centro de la Provincia de Buenos Aires [Buenos Aires] (UNICEN)-Comisión de Investigaciones Científicas [Buenos Aires] (CIC), Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires] (CONICET), and Comisión de Investigaciones Científicas [Buenos Aires] (CIC)-Universidad Nacional del Centro de la Provincia de Buenos Aires [Buenos Aires] (UNICEN)-Comisión Nacional de Energía Atómica [ARGENTINA] (CNEA)

Subjects
[SPI.OTHER]Engineering Sciences [physics]/Other, Mathematical optimization, PUBLIC TRANSPORT DEMAND, TRANSPORT EN COMMUN, Optimization problem, Computer science, 0211 other engineering and technologies, 02 engineering and technology, Bilevel optimization, Matrix (mathematics), ORIGINE DESTINATION, 0502 economics and business, AFFECTATION (TRAFIC), Descent (mathematics), 050210 logistics & transportation, CONFERENCE, 021103 operations research, business.industry, DEMANDE, 05 social sciences, Resolution (logic), AFFECTATION DU TRAFIC, Flow (mathematics), CHYPRE, Public transport, Focus (optics), business
Abstract

For the case of public transport, we consider the problem of demand estimation. Given an origin-destination matrix representing the public transport demand, the distribution of flow among different lines can be obtained assuming that it corresponds to a certain equilibrium characterized by an optimization problem. In particular we will focus on the assignment model proposed by Cepeda et al. (2006). However the knowledge of origin-destination matrix is expensive and sometimes unaffordable in practice. Traditionally, it is estimated using statistical or econometrical considerations. In this work, we explore the estimation through the numerical solution of a bilevel optimization problem. One disadvantage of this formulation is the difficulty of obtaining descent directions, hence, for the resolution of the optimization problem we use a derivative-free method. This method was applied for small networks getting good results.

Published
2020

5. NGO-GM: Natural Gradient Optimization for Graphical Models

Author

Rida Laraki, David Saltiel, Jamal Atif, Eric Benhamou, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Université du Littoral Côte d'Opale (ULCO)

Subjects
FOS: Computer and information sciences, Meta parameters, Mathematical optimization, Computer Science - Machine Learning, Optimization problem, Computer science, Trend detection, Machine Learning (stat.ML), Overfitting, 01 natural sciences, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], 010309 optics, 03 medical and health sciences, 0302 clinical medicine, Distribution (mathematics), Statistics - Machine Learning, 0103 physical sciences, Graphical model, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Natural gradient, 030217 neurology & neurosurgery, Descent (mathematics)
Abstract

This paper deals with estimating model parameters in graphical models. We reformulate it as an information geometric optimization problem and introduce a natural gradient descent strategy that incorporates additional meta parameters. We show that our approach is a strong alternative to the celebrated EM approach for learning in graphical models. Actually, our natural gradient based strategy leads to learning optimal parameters for the final objective function without artificially trying to fit a distribution that may not correspond to the real one. We support our theoretical findings with the question of trend detection in financial markets and show that the learned model performs better than traditional practitioner methods and is less prone to overfitting., 18 pages, 9 figures

Published
2020

6. First-order and second-order variants of the gradient descent in a unified framework

Author

Nicolas Perrin-Gilbert, Olivier Sigaud, Thomas Pierrot, Institut des Systèmes Intelligents et de Robotique (ISIR), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Systèmes robotiques Conception et Commande (SYROCO), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Perrin-Gilbert, Nicolas, Sorbonne Université (SU), InstaDeep, Centre National de la Recherche Scientifique (CNRS), and ANR-18-CE33-0005,HUSKI,Apprentissage de capacités de mouvements avec des humanoïdes virtuels(2018)

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], FOS: Computer and information sciences, Computer Science - Machine Learning, 0209 industrial biotechnology, Covariance matrix, [INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO], Machine Learning (stat.ML), [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], 02 engineering and technology, First order, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], 020901 industrial engineering & automation, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, 0202 electrical engineering, electronic engineering, information engineering, Order (group theory), Applied mathematics, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], 020201 artificial intelligence & image processing, Natural gradient, Gradient descent, ComputingMilieux_MISCELLANEOUS, Descent (mathematics), Mathematics
Abstract

In this paper, we provide an overview of first-order and second-order variants of the gradient descent method that are commonly used in machine learning. We propose a general framework in which 6 of these variants can be interpreted as different instances of the same approach. They are the vanilla gradient descent, the classical and generalized Gauss-Newton methods, the natural gradient descent method, the gradient covariance matrix approach, and Newton's method. Besides interpreting these methods within a single framework, we explain their specificities and show under which conditions some of them coincide., Comment: 13 pages

Published
2019

7. ON THE CANONICAL, FPQC, AND FINITE TOPOLOGIES ON AFFINE SCHEMES. THE STATE OF THE ART

Author

Yves André, Luisa Fiorot, and ANDRE, YVES

Subjects
Pure mathematics, Canonical topology, effective descent, pure ring map, fpqc topology, finite covering, regularity, Frobenius algebra, rational singularity, splinter, cluster algebra, regularity, Canonical topology, Commutative Algebra (math.AC), Network topology, Theoretical Computer Science, splinter, [MATH.MATH-AC] Mathematics [math]/Commutative Algebra [math.AC], Mathematics - Algebraic Geometry, Mathematics (miscellaneous), Morphism, fpqc topology, FOS: Mathematics, Category Theory (math.CT), effective descent, Commutative algebra, Algebraic Geometry (math.AG), finite covering, Topology (chemistry), Descent (mathematics), Mathematics, Ring (mathematics), [MATH.MATH-AG] Mathematics [math]/Algebraic Geometry [math.AG], Mathematics - Category Theory, Mathematics - Commutative Algebra, pure ring map, Injective function, Frobenius algebra, rational singularity, Affine transformation, cluster algebra, [MATH.MATH-NT] Mathematics [math]/Number Theory [math.NT]
Abstract

This is a systematic study of the behaviour of finite coverings of (affine) schemes with regard to two Grothendieck topologies: the canonical topology and the fpqc topology. The history of the problem takes roots in the foundations of Grothendieck topologies, passes through main strides in Commutative Algebra and leads to new Mathematics up to perfectoids and prisms. We first review the canonical topology of affine schemes and show, keeping with Olivier's lost work, that it coincides with the effective descent topology; covering maps are given by universally injective ring maps, which we discuss in detail. We then give a "catalogue raisonn\'e" of examples of finite coverings which separate the canonical, fpqc and fppf topologies. The key result is that finite coverings of regular schemes are coverings for the canonical topology, and even for the fpqc topology (but not necessarily for the fppf topology). We discuss a "weakly functorial" aspect of this result. "Splinters" are those affine Noetherian schemes for which every finite covering is a covering for the canonical topology. We also investigate their mysterious fpqc analogs, and prove that in prime characteristic, they are all regular. This leads us to the problem of descent of regularity by (non-necessarily flat) morphisms $f$ which are coverings for the fpqc topology, which is settled thanks to a recent theorem of Bhatt-Iyengar-Ma., Comment: Final version, accepted in Ann. Sc. Norm. Super. Pisa Cl. Sci

Published
2019

8. Catalan words avoiding pairs of length three patterns

Author

Vincent Vajnovszki, Carine Khalil, Jean-Luc Baril, and Baril, Jean-Luc

Subjects
FOS: Computer and information sciences, Mathematics::Combinatorics, Discrete Mathematics (cs.DM), General Computer Science, Integer sequence, Bivariate analysis, Constructive, language.human_language, Theoretical Computer Science, Combinatorics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Enumeration, language, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Catalan, Combinatorics (math.CO), Recursive decomposition, Bijection, injection and surjection, Mathematics, Descent (mathematics), Computer Science - Discrete Mathematics
Abstract

Catalan words are particular growth-restricted words counted by the eponymous integer sequence. In this article we consider Catalan words avoiding a pair of patterns of length 3, pursuing the recent initiating work of the first and last authors and of S. Kirgizov where (among other things) the enumeration of Catalan words avoiding a patterns of length 3 is completed. More precisely, we explore systematically the structural properties of the sets of words under consideration and give enumerating results by means of recursive decomposition, constructive bijections or bivariate generating functions with respect to the length and descent number. Some of the obtained enumerating sequences are known, and thus the corresponding results establish new combinatorial interpretations for them.

Published
2019

9. Backtracking strategies for accelerated descent methods with smooth composite objectives

Author

Luca Calatroni, Antonin Chambolle, Calatroni, Luca, Blanc International II - Algorithmes efficaces pour l'optimisation non-lisse en traitement d'images. - - EANOI2012 - ANR-12-IS01-0003 - Blanc International II - VALID, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and ANR-12-IS01-0003,EANOI,Algorithmes efficaces pour l'optimisation non-lisse en traitement d'images.(2012)

Subjects
Elastic net regularization, Composite number, 0211 other engineering and technologies, ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization/G.1.6.1: Convex programming, Acceleration (differential geometry), 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Thresholding algorithm, FOS: Mathematics, 0101 mathematics, Image denoising, Mathematics - Optimization and Control, Descent (mathematics), Mathematics, Shrinkage, 021103 operations research, Backtracking, ACM: I.: Computing Methodologies/I.4: IMAGE PROCESSING AND COMPUTER VISION, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], Optimization and Control (math.OC), ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 90C25, 65F22, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Algorithm, Software
Abstract

We present and analyse a backtracking strategy for a general Fast Iterative Shrinkage/Thresholding Algorithm which has been recently proposed in (Chambolle, Pock, 2016) for strongly convex objective functions. Differently from classical Armijo-type line searching, our backtracking rule allows for local increasing and decreasing of the descent step size (i.e. proximal parameter) along the iterations. For such strategy accelerated convergence rates are proved and numerical results are shown for some exemplar imaging problems.

Published
2019

10. A line search algorithm for wind field adjustment with incomplete data and RBF approximation

Author

Christian Gout, Pedro González Casanova, Miguel Angel Moreles, Daniel A. Cervantes, Instituto de Matematicas (UNAM), Universidad Nacional Autónoma de México (UNAM), Laboratoire de Mathématiques de l'INSA de Rouen Normandie (LMI), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU), Centro de Investigación en Matemáticas (CIMAT), and Consejo Nacional de Ciencia y Tecnología [Mexico] (CONACYT)

Subjects
Work (thermodynamics), Field (physics), Wind adjustment, Applied Mathematics, Wind field, RBF methods, Numerical Analysis (math.NA), 010103 numerical & computational mathematics, 01 natural sciences, 010101 applied mathematics, Computational Mathematics, Line search, Adjoint equation, FOS: Mathematics, Applied mathematics, Radial basis function, Mathematics - Numerical Analysis, 0101 mathematics, Descent direction, [MATH]Mathematics [math], Divergence (statistics), Mathematics, Descent (mathematics)
Abstract

International audience; The problem of concern in this work is the construction of free divergence fields given scattered horizontal components. As customary, the problem is formulated as a PDE constrained least squares problem. The novelty of our approach is to construct the so-called adjusted field, as the unique solution along an appropriately chosen descent direction. The latter is obtained by the adjoint equation technique. It is shown that the classical adjusted field of Sasaki’s is a particular case. On choosing descent directions, the underlying mass consistent model leads to the solution of an elliptic problem which is solved by means of a radial basis functions method. Finally, some numerical results for wind field adjustment are presented.

Published
2018

11. Galois descent of semi-affinoid spaces

Author

Daniele Turchetti, Lorenzo Fantini, Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)), Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques Nicolas Oresme (LMNO), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), and Normandie Université (NU)-Normandie Université (NU)

Subjects
Pure mathematics, General Mathematics, 010102 general mathematics, Formal scheme, Automorphism, Space (mathematics), 01 natural sciences, Discrete valuation ring, Mathematics - Algebraic Geometry, 0103 physical sciences, FOS: Mathematics, 010307 mathematical physics, Affine transformation, 0101 mathematics, [MATH]Mathematics [math], Algebraic Geometry (math.AG), Descent (mathematics), Analytic function, Mathematics, Analytic proof
Abstract

We study the Galois descent of semi-affinoid non-archimedean analytic spaces. These are the non-archimedean analytic spaces which admit an affine special formal scheme as model over a complete discrete valuation ring, such as for example open or closed polydiscs or polyannuli. Using Weil restrictions and Galois fixed loci for semi-affinoid spaces and their formal models, we describe a formal model of a $K$-analytic space $X$, provided that $X\otimes_KL$ is semi-affinoid for some finite tamely ramified extension $L$ of $K$. As an application, we study the forms of analytic annuli that are trivialized by a wide class of Galois extensions that includes totally tamely ramified extensions. In order to do so, we first establish a Weierstrass preparation result for analytic functions on annuli, and use it to linearize finite order automorphisms of annuli. Finally, we explain how from these results one can deduce a non-archimedean analytic proof of the existence of resolutions of singularities of surfaces in characteristic zero., Comment: Exposition improved and minor modifications. 37 pages. To appear in Math. Z

Published
2018

12. Accelerated Alternating Descent Methods for Dykstra-like problems

Author

Samuel Vaiter, Pauline Tan, Antonin Chambolle, Centre de Mathématiques Appliquées - Ecole Polytechnique ( CMAP ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Mathématiques de Bourgogne [Dijon] ( IMB ), Université de Bourgogne ( UB ) -Centre National de la Recherche Scientifique ( CNRS ), Gaspard Monge Program for Optimization and operations research (PGMO), through the 'MAORI' group, GDR MIA (CNRS), ANR-12-IS01-0003,EANOI,Algorithmes efficaces pour l'optimisation non-lisse en traitement d'images. ( 2012 ), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Bourgogne [Dijon] (IMB), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), and ANR-12-IS01-0003,EANOI,Algorithmes efficaces pour l'optimisation non-lisse en traitement d'images.(2012)

Subjects
Statistics and Probability, Mathematical optimization, Accelerated methods, 0211 other engineering and technologies, 02 engineering and technology, MSC: 65K10, 65D18, 68U10, Quadratic equation, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Descent (mathematics), Variable (mathematics), 021103 operations research, Alternating minimizations, Applied Mathematics, Random coordinate descent, [ MATH.MATH-NA ] Mathematics [math]/Numerical Analysis [math.NA], Condensed Matter Physics, Stochastic gradient descent, Block descent algorithms, Modeling and Simulation, 020201 artificial intelligence & image processing, Total variation minimization, Geometry and Topology, Computer Vision and Pattern Recognition, Descent direction, Gradient descent, Convex function, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; This paper extends recent results by the first author and T. Pock (ICG, TU Graz, Austria) on the acceleration of alternating minimization techniques for quadratic plus nonsmooth objectives depending on two variables. We discuss here the strongly convex situation, and how ‘fast’ methods can be derived by adapting the overrelaxation strategy of Nesterov for projected gradient descent. We also investigate slightly more general alternating descent methods, where several descent steps in each variable are alternatively performed.

Published
2017

13. Preserving the Number of Cycles of Length k in a Growing Uniform Permutation

Author

Romaric Duvignau, Philippe Duchon, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB), Aix Marseille Université (AMU), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Duchon, Philippe

Subjects
Random graph, Discrete mathematics, Golomb–Dickman constant, Applied Mathematics, Sampling (statistics), 0102 computer and information sciences, Random permutation, 01 natural sciences, Random binary tree, Theoretical Computer Science, Combinatorics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Tree (descriptive set theory), Permutation, Computational Theory and Mathematics, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Geometry and Topology, ComputingMilieux_MISCELLANEOUS, Mathematics, Descent (mathematics)
Abstract

The goal of this work is to describe a uniform generation tree for permutations which preserves the number of $k$-cycles between any permutation (except for a small unavoidable subset of optimal size) of the tree and its direct children. Moreover, the tree we describe has the property that if the number of $k$-cycles does not change during any $k$ consecutive levels, then any further random descent will always yield permutations with that same number of $k$-cycles. This specific additional property yields interesting applications for exact sampling. We describe a new random generation algorithm for permutations with a fixed number of $k$-cycles in $n+\mathcal{O}(1)$ expected calls to a random integer sampler. Another application is a combinatorial algorithm for exact sampling from the Poisson distribution with parameter $1/k$.

Published
2016

14. Iterated variable neighborhood search for the capacitated clustering problem

Author

Xiangjing Lai, Jin-Kao Hao, Laboratoire d'Etudes et de Recherche en Informatique d'Angers (LERIA), Université d'Angers (UA), and Institut Universitaire de France

Subjects
Mathematical optimization, 021103 operations research, Matching (graph theory), Computer science, 0211 other engineering and technologies, 02 engineering and technology, Grouping problem, Variable (computer science), Artificial Intelligence, Control and Systems Engineering, Iterated function, 0202 electrical engineering, electronic engineering, information engineering, Capacitated clustering, Heuristics, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Electrical and Electronic Engineering, Cluster analysis, Variable neighborhood search, Descent (mathematics)
Abstract

International audience; The NP-hard capacitated clustering problem (CCP) is a general model with a number of relevant applications. This paper proposes a highly effective iterated variable neighborhood search (IVNS) algorithm for solving the problem. IVNS combines an extended variable neighborhood descent method and a randomized shake procedure to explore effectively the search space. The computational results obtained on three sets of 133 benchmarks reveal that the proposed algorithm competes favorably with the state-of-the-art algorithms in the literature both in terms of solution quality and computational efficiency. In particular, IVNS discovers an improved best known result (new lower bounds) for 28 out of 83 most popular instances, while matching the current best known results for the remaining 55 instances. Several essential components of the proposed algorithm are investigated to understand their impacts on the performance of algorithm.

Published
2016

15. A variable neighborhood search for solving the multi-vehicle covering tour problem

Author

Mustapha Ratli, Bassem Jarboui, Houda Derbel, Manel Kammoun, FSEGS, Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201 (LAMIH), and Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Centre National de la Recherche Scientifique (CNRS)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)

Subjects
Mathematical optimization, 021103 operations research, Heuristic (computer science), Applied Mathematics, 0211 other engineering and technologies, 02 engineering and technology, Transportation theory, " "Variable neighborhood search", "Covering Tour Problem", Set (abstract data type), Variable (computer science), 11. Sustainability, 0202 electrical engineering, electronic engineering, information engineering, "Heuristic algorithms", Discrete Mathematics and Combinatorics, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Variable neighborhood search, Mathematics, Descent (mathematics)
Abstract

International audience; In this article, we consider a transportation problem with different kinds of locations: V , T, and W. The set T ⊂ V consists of vertices that must be visited through the use of potential locations in V and W consists of locations that must be covered. The problem consists in minimizing vehicle routes on a subset of V including T. We develop a variable neighborhood search heuristic based on a variable neighborhood descent in which a set of locations must be visited, whereas another subset must be close enough to the planned routes. We tested and compared our algorithm on datasets based on TSP Library instances.

Published
2015

16. Equivalence classes of permutations modulo descents and left-to-right maxima

Author

Jean-Luc Baril, Armen Petrossian, Laboratoire Electronique, Informatique et Image [UMR6306] (Le2i), Université de Bourgogne (UB)-École Nationale Supérieure d'Arts et Métiers (ENSAM), Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Centre National de la Recherche Scientifique (CNRS), Baril, Jean-Luc, Laboratoire Electronique, Informatique et Image ( Le2i ), and Université de Bourgogne ( UB ) -AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Centre National de la Recherche Scientifique ( CNRS )

Subjects
Discrete mathematics, Mathematics::Combinatorics, Modulo, [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Combinatorics, Catalan number, Permutation, Motzkin number, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Maxima, Equivalence class, ComputingMilieux_MISCELLANEOUS, Descent (mathematics), Bell number, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

In a recent paper [2], the authors provide enumerating results for equivalence classes of permutations modulo excedances. In this paper we investigate two other equivalence relations based on descents and left-to-right maxima. Enumerating results are presented for permutations, involutions, derangements, cycles and permutations avoiding one pattern of length three.

Published
2014

17. Detection of asymmetric control valve stiction from oscillatory data using an extended Hammerstein system identification method

Author

Qinghua Zhang, Jiandong Wang, College of Engineering [Beijing], Peking University [Beijing], Statistical Inference for Structural Health Monitoring (I4S), Département Composants et Systèmes (IFSTTAR/COSYS), PRES Université Lille Nord de France-PRES Université Nantes Angers Le Mans (UNAM)-Université de Lyon-Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-PRES Université Lille Nord de France-PRES Université Nantes Angers Le Mans (UNAM)-Université de Lyon-Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-Université de Lyon-PRES Université Nantes Angers Le Mans (UNAM)-PRES Université Lille Nord de France-Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-Université de Lyon-PRES Université Nantes Angers Le Mans (UNAM)-PRES Université Lille Nord de France-Inria Rennes – Bretagne Atlantique

Subjects
Control valves, 0209 industrial biotechnology, Engineering, Hammerstein system identification, 02 engineering and technology, Industrial and Manufacturing Engineering, 020901 industrial engineering & automation, 020401 chemical engineering, Control theory, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0204 chemical engineering, Cyclo-stationarity, Descent (mathematics), business.industry, Oscillation, Control valve stiction, Process (computing), System identification, Computer Science Applications, Identification (information), Nonlinear system, Control and Systems Engineering, Modeling and Simulation, Stiction, business
Abstract

International audience; The study in this paper is motivated by the detection of control valves with asymmetric stiction resulting in oscillations in feedback control loops. The joint characterization of the control valve and the controlled process is formulated as the identification of a class of extended Hammerstein systems. The input nonlinearity is described by a point-slope-based hysteretic model with two possibly asymmetric ascent and descent paths. An iterative identification method is proposed, based on the idea of separating the ascent and descent paths subject to the oscillatory input and output. The structure of the formulated extended Hammerstein system is shown to be identifiable, and the oscillatory signals in feedback control loops are proved to be informative by exploiting the cyclo-stationarity of these oscillatory signals. Numerical, experimental and industrial examples are provided to illustrate the effectiveness of the proposed identification method.

Published
2014

18. Lie theory for quasi-shuffle bialgebras

Author

Loïc Foissy, Frédéric Patras, Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville (LMPA), Université du Littoral Côte d'Opale (ULCO), Laboratoire Jean Alexandre Dieudonné (JAD), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), and ANR-12-BS01-0017,CARMA,Combinatoire Algébrique, Résurgence, Moules et Applications(2012)

Subjects
Pure mathematics, Structure (category theory), Context (language use), 0102 computer and information sciences, 01 natural sciences, Shuffle algebra, Bialgebra, Lie algebra, Lie theory, planar binary tree, 0101 mathematics, 05E05, 05E15, 16T30, 16T05, quasi-shuffle algebra, Mathematics, Descent (mathematics), tridendriform algebra, 010102 general mathematics, [MATH.MATH-RA]Mathematics [math]/Rings and Algebras [math.RA], Mathematics - Rings and Algebras, combinatorial Hopf algebra, dendriform algebra, 010201 computation theory & mathematics, Complete theory, Schröder tree, WQSym, FQSym, Hopf operad, shuffle algebra
Abstract

International audience; Many features of classical Lie theory generalize to the broader context of algebras over Hopf operads. However, this idea remains largely to be developed systematically. Quasi-shuffle algebras provide for example an interesting illustration of these phenomena, but have not been investigated from this point of view.The notion of quasi-shuffle algebras can be traced back to the beginings of the theory of Rota–Baxter algebras, but was developed systematically only recently, starting essentially with Hoffman’s work, that was motivated by multizeta values (MZVs) and featured their bialgebra structure. Many partial results on the fine structure of quasi-shuffle bialgebras have been obtained since then but, besides the fact that each of these articles features a particular point of view, they fail to develop systematically a complete theory.This article builds on these various results and develops the analog theory, for quasi-shuffle algebras, of the theory of descent algebras and their relations to free Lie algebras for classical enveloping algebras.

Published
2014

19. Tensor Decompositions with Banded Matrix Factors

Author

Mikael Sorensen, Pierre Comon, Department of Electrical Engineering [Leuven] (ESAT), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe SIGNAL, Signal, Images et Systèmes (Laboratoire I3S - SIS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)

Subjects
banded, Computation, 02 engineering and technology, Toeplitz, Matrix (mathematics), [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, 0202 electrical engineering, electronic engineering, information engineering, Decomposition (computer science), Discrete Mathematics and Combinatorics, canonical, Tensor, Descent (mathematics), Mathematics, Signal processing, Numerical Analysis, Band matrix, Algebra and Number Theory, decomposition, 020206 networking & telecommunications, Toeplitz matrix, tensor, Algebra, polyadic, Hankel, 020201 artificial intelligence & image processing, parafac, Geometry and Topology, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract

published online on Jan. 5, 2012; International audience; The computation of the model parameters of a Canonical Polyadic Decomposition (CPD), also known as the parallel factor (PARAFAC) or canonical decomposition (CANDECOMP) or CP decomposition, is typically done by resorting to iterative algorithms, e.g. either iterative alternating least squares type or descent methods. In many practical problems involving tensor decompositions such as signal processing, some of the matrix factors are banded. First, we develop methods for the computation of CPDs with one banded matrix factor. It results in best rank-1 tensor approximation problems. Second, we propose methods to compute CPDs with more than one banded matrix factor. Third, we extend the developed methods to also handle banded and structured matrix factors such as Hankel or Toeplitz. Computer results are also reported.

Published
2013

20. Natural endomorphisms of shuffle algebras

Author

Loïc Foissy, Frédéric Patras, Laboratoire de Mathématiques de Reims (LMR), Université de Reims Champagne-Ardenne (URCA)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Jean Alexandre Dieudonné (JAD), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), ANR-12-BS01-0017,CARMA,Combinatoire Algébrique, Résurgence, Moules et Applications(2012), Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville (LMPA), Université du Littoral Côte d'Opale (ULCO), and COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Pure mathematics, Endomorphism, General Mathematics, 010102 general mathematics, Subalgebra, Mathematics::Rings and Algebras, [MATH.MATH-RA]Mathematics [math]/Rings and Algebras [math.RA], Structure (category theory), 0102 computer and information sciences, Tensor algebra, Mathematics - Rings and Algebras, Hopf algebra, Descent algebras, 01 natural sciences, Shuffle algebra, Convolution, Shuffle algebras, 16T30, 05A05, 17A30, 010201 computation theory & mathematics, Dendriform algebras, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Descent (mathematics), Mathematics
Abstract

We focus in this text on the adaptation to the study of shuffles of the main combinatorial tool in the theory of free Lie algebras, namely the existence of a universal algebra of endomorphisms for tensor and other cocommutative Hopf algebras: the family of Solomon's descent algebras of type A. We show that there exists similarly a natural endomorphism algebra for commutative shuffle algebras, which is a natural extension of the Malvenuto-Reutenauer Hopf algebra of permutations, or algebra of free quasi-symmetric functions. We study this new algebra for its own, establish freeness properties, study its generators, bases, and also feature its relations to the internal structure of shuffle algebras., Comment: 19 pages

Published
2013

21. Evolutionary analyses of non-genealogical bonds produced by introgressive descent

Author

Fernando Baquero, Philippe Lopez, James O. McInerney, Richard M. Burian, Frédéric Bouchard, Eric Bapteste, Adaptation, Intégration, Réticulation et Evolution (AIRE), Evolution Paris Seine, Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), Social Sciences and Humanities Research Council of Canada, European Union [PAR-241476, EvoTAR-282004], Carlos III Institute Research Fund [FIS-PI10-02588], Science Foundation Ireland Research Frontiers Programme [09/RFP/EOB2510], Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
Lineage (evolution), Gene regulatory network, biodiversity structure, [SDV.BID]Life Sciences [q-bio]/Biodiversity, Biology, Evolution, Molecular, 03 medical and health sciences, Phylogenetics, Databases, Genetic, Kinship, Gene Regulatory Networks, Inbreeding, Base sequence, Phylogeny, 030304 developmental biology, Descent (mathematics), 0303 health sciences, Multidisciplinary, Base Sequence, 030306 microbiology, evolutionary transitions, network of life, Evolutionary transitions, lateral gene transfer, symbiosis, Evolutionary biology, Perspective, Genealogy and Heraldry
Abstract

International audience; All evolutionary biologists are familiar with evolutionary units that evolve by vertical descent in a tree-like fashion in single lineages. However, many other kinds of processes contribute to evolutionary diversity. In vertical descent, the genetic material of a particular evolutionary unit is propagated by replication inside its own lineage. In what we call introgressive descent, the genetic material of a particular evolutionary unit propagates into different host structures and is replicated within these host structures. Thus, introgressive descent generates a variety of evolutionary units and leaves recognizable patterns in resemblance networks. We characterize six kinds of evolutionary units, of which five involve mosaic lineages generated by introgressive descent. To facilitate detection of these units in resemblance networks, we introduce terminology based on two notions, P3s (subgraphs of three nodes: A, B, and C) and mosaic P3s, and suggest an apparatus for systematic detection of introgressive descent. Mosaic P3s correspond to a distinct type of evolutionary bond that is orthogonal to the bonds of kinship and genealogy usually examined by evolutionary biologists. We argue that recognition of these evolutionary bonds stimulates radical rethinking of key questions in evolutionary biology (e.g., the relations among evolutionary players in very early phases of evolutionary history, the origin and emergence of novelties, and the production of new lineages). This line of research will expand the study of biological complexity beyond the usual genealogical bonds, revealing additional sources of biodiversity. It provides an important step to a more realistic pluralist treatment of evolutionary complexity.

Published
2012

22. The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

Author

Heesung Shin, Jiang Zeng, Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), and MIRA-2008

Subjects
0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Combinatorics, symbols.namesake, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, 0101 mathematics, Descent (mathematics), Mathematics, Discrete mathematics, Mathematics::Combinatorics, Conjecture, 010102 general mathematics, Tangent, Eulerian path, Divisibility rule, Unimodality, Derangement, Computational Theory and Mathematics, 010201 computation theory & mathematics, symbols, Geometry and Topology, Combinatorics (math.CO), Combinatorial theory
Abstract

This paper was motivated by a conjecture of Br\"{a}nd\'{e}n (European J. Combin. \textbf{29} (2008), no.~2, 514--531) about the divisibility of the coefficients in an expansion of generalized Eulerian polynomials, which implies the symmetric and unimodal property of the Eulerian numbers. We show that such a formula with the conjectured property can be derived from the combinatorial theory of continued fractions. We also discuss an analogous expansion for the corresponding formula for derangements and prove a $(p,q)$-analogue of the fact that the (-1)-evaluation of the enumerator polynomials of permutations (resp. derangements) by the number of excedances gives rise to tangent numbers (resp. secant numbers). The $(p,q)$-analogue unifies and generalizes our recent results (European J. Combin. \textbf{31} (2010), no.~7, 1689--1705.) and that of Josuat-Verg\`es (European J. Combin. \textbf{31} (2010), no.~7, 1892--1906)., Comment: 19 pages, 2 figures

Published
2012

23. Global descent obstructions for varieties

Author

Emmanuel Hallouin, Jean-Marc Couveignes, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Lithe and fast algorithmic number theory (LFANT), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB), Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

Subjects
Pure mathematics, Field (mathematics), descent, 01 natural sciences, Moduli, Mathematics - Algebraic Geometry, 11R34, Mathematics::Category Theory, 0103 physical sciences, FOS: Mathematics, 11G35, 12G05, Number Theory (math.NT), 0101 mathematics, Global field, Algebraic Geometry (math.AG), Descent (mathematics), Mathematics, field of definition, 14D22, algebraic curve, Algebra and Number Theory, Mathematics - Number Theory, 010102 general mathematics, stack, global field, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT], Field of definition, field of moduli, 010307 mathematical physics, Algebraic curve, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], 12Y05, 12F10, 11R37, Stack (mathematics)
Abstract

International audience; We show how to transport descent obstructions from the category of covers to the category of varieties. We deduce examples of curves having $\QQ$ as field of moduli, that admit models over every completion of $\QQ$, but have no model over $\QQ$.

Published
2011

24. The case for strategic oscillation

Author

Jin-Kao Hao, Fred Glover, Laboratoire d'Etudes et de Recherche en Informatique d'Angers (LERIA), and Université d'Angers (UA)

Subjects
Zero-one optimization, Mathematical optimization, Optimization problem, Global minima, Computer science, 0211 other engineering and technologies, General Decision Sciences, Hard problems, Theory of Computation, 02 engineering and technology, Management Science and Operations Research, Space (commercial competition), Local optimum, 0202 electrical engineering, electronic engineering, information engineering, tabu search, [INFO]Computer Science [cs], Metaheuristic, Descent (mathematics), 021103 operations research, Tabu search, Global optimum, Strategic oscillation, Combinatorics, Theory of computation, Operations Research/Decision Theory, 020201 artificial intelligence & image processing, Algorithm
Abstract

International audience; We study a “hard” optimization problem for metaheuristic search, where a natural neighborhood (that consists of moves for flipping the values of zero-one variables) confronts two local optima, separated by a maximum possible number of moves in the feasible space. Once a descent method reaches the first local optimum, all sequences of feasible moves to reach the second, which is the global optimum, must ultimately pass through solutions that are progressively worse until reaching the worst solution of all, which is adjacent to the global optimum. We show how certain alternative neighborhoods can locate the global more readily, but disclose that each of these approaches encounters serious difficulties by slightly changing the problem formulation. We also identify other possible approaches that seem at first to be promising but turn out to have deficiencies. Finally, we observe that a strategic oscillation approach for transitioning between feasible and infeasible space overcomes these difficulties, reinforcing recent published observations about the utility of solution trajectories that alternate between feasibility and infeasibility. We also sketch features of such an approach that have implications for future research.

Published
2011

25. The Iso-regularization Descent Algorithm for the LASSO

Author

Philippe Preux, Manuel Loth, Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), Sequential Learning (SEQUEL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), and Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)

Subjects
Elastic net regularization, Mathematical optimization, algorithm, MathematicsofComputing_NUMERICALANALYSIS, Polytope, Feature selection, 010103 numerical & computational mathematics, descent, 01 natural sciences, Regularization (mathematics), Statistics::Computation, Constraint (information theory), regularization, 010104 statistics & probability, Statistics::Machine Learning, Lasso (statistics), [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Path (graph theory), Statistics::Methodology, 0101 mathematics, Lasso, [STAT.CO]Statistics [stat]/Computation [stat.CO], Mathematics, Descent (mathematics)
Abstract

International audience; Following the introduction by Tibshirani of the LASSO technique for feature selection in regression, two algorithms were proposed by Osborne et al. for solving the associated problem. One is an homotopy method that gained popularity as the LASSO modification of the LARS algorithm. The other is a finite-step descent method that follows a path on the constraint polytope, and seems to have been largely ignored. One of the reason may be that it solves the constrained formulation of the LASSO, as opposed to the more practical regularized formulation. We give here an adaptation of this algorithm that solves the regularized problem, has a simpler formulation, and outperforms state-of-the-art algorithms in terms of speed.

Published
2010

26. Elementary 3-descent with a 3-isogeny

Author

Fabien Pazuki, Henri Cohen, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Lithe and fast algorithmic number theory (LFANT), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Sciences et Technologies - Bordeaux 1, Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, and Université Sciences et Technologies - Bordeaux 1 (UB)

Subjects
Isogeny, Algebra and Number Theory, Mathematics - Number Theory, Computation, 010102 general mathematics, Mathematics::History and Overview, Rank of an elliptic curve, 010103 numerical & computational mathematics, 01 natural sciences, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT], Interpretation (model theory), Algebra, 11G05, 14G05, 14H52, FOS: Mathematics, Number Theory (math.NT), 0101 mathematics, Mathematics, Descent (mathematics)
Abstract

International audience; In this expository paper, we show how to use in practice 3-descent with a 3-isogeny to find an estimate for the rank of an elliptic curve having a rational 3-torsion subgroup, and we also give a geometric interpretation of these computations.

Published
2009

27. The six operations for sheaves on Artin stacks I: Finite Coefficients

Author

Yves Laszlo, Martin Olsson, and Laszlo, Yves

Subjects
Six operations, General Mathematics, Duality (mathematics), 18E30, 18G30, Base change, Mathematics - Algebraic Geometry, Mathematics::Algebraic Geometry, 14A20, 18G40, 55U30, Mathematics::K-Theory and Homology, Mathematics::Category Theory, derived categories, FOS: Mathematics, Algebraic Geometry (math.AG), Descent (mathematics), Mathematics, Discrete mathematics, [MATH.MATH-AG] Mathematics [math]/Algebraic Geometry [math.AG], algebraic stack, Number theory, Scheme (mathematics), duality, Krull dimension, dualizing complex, 6 operations, Stack (mathematics)
Abstract

In this paper we develop a theory of Grothendieck's six operations of lisse-\'etale constructible sheaves on Artin stacks which are locally of finite type over suitable regular basis of dimension at most 1., Comment: We improve the previous version generalizing the constructions to all stacks locally of finite type over suitable basis. Some typos have been corrected

Published
2008

28. Non-smooth structured control design with application to PID loop-shaping of a process

Author

Vincent Bompart, Pierre Apkarian, Dominikus Noll, ONERA - The French Aerospace Lab [Toulouse], ONERA, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), and Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)

Subjects
0209 industrial biotechnology, Engineering, 2354646 (2008k:93055), Process (engineering), General Chemical Engineering, Control (management), Biomedical Engineering, Aerospace Engineering, PID controller, Context (language use), 02 engineering and technology, Industrial and Manufacturing Engineering, 020901 industrial engineering & automation, Control theory, 0202 electrical engineering, electronic engineering, information engineering, Electrical and Electronic Engineering, [MATH]Mathematics [math], Implementation, ComputingMilieux_MISCELLANEOUS, Descent (mathematics), Structure (mathematical logic), business.industry, Mechanical Engineering, Control engineering, Control and Systems Engineering, 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], business
Abstract

SUMMARY Feedback controllers with specific structure arise frequently in applications because they are easily apprehended by design engineers and facilitate on-board implementations and re-tuning. This work is dedicated to H1 synthesis with structured controllers. In this context, straightforward application of traditional synthesis techniques fails, which explains why only a few ad hoc methods have been developed over the years. In response, we propose a more systematic way to design H1 optimal controllers with fixed structure using local optimization techniques. Our approach addresses in principle all those controller structures which can be built into mathematical programming constraints. We apply non-smooth optimization techniques to compute locally optimal solutions, and provide practical tests for descent and optimality. In the experimental part we apply our technique to H1 loop-shaping proportional integral derivative (PID) controllers for MIMO systems and demonstrate its use for PID control of a chemical process. Copyright # 2007 John Wiley & Sons, Ltd.

Published
2007

29. Gauged BRST symmetry and covariant gravitational anomalies

Author

François Gieres, Jean Pierre Ader, Yves Noirot, Institut de Physique Nucléaire de Lyon (IPNL), Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3), Centre de physique moléculaire optique et hertzienne (CPMOH), and Centre National de la Recherche Scientifique (CNRS)-Université Sciences et Technologies - Bordeaux 1

Subjects
Physics, [PHYS]Physics [physics], Nuclear and High Energy Physics, 010308 nuclear & particles physics, Covariance, 01 natural sciences, Symmetry (physics), BRST quantization, Gravitation, High Energy Physics::Theory, 0103 physical sciences, Statistics::Methodology, Covariant transformation, Gauge theory, Anomaly (physics), 010306 general physics, General Theoretical Physics, ComputingMilieux_MISCELLANEOUS, Descent (mathematics), Mathematical physics
Abstract

We derive generalized descent equations which contain both the consistent and covariant gravitational anomalies. The derivation makes use of the natural field reparametrizations which occur in the process of gauging the (anti)BRST symmetry and it leads to an expression for the covariant anomaly which satisfies strong covariance conditions.

Published
1991

30. The Conjugate Residual Method for Constrained Minimization Problems

Author

David G. Luenberger, Department of Electrical Engineering [Stanford], and Stanford University

Subjects
Numerical Analysis, Applied Mathematics, Constrained optimization, 010103 numerical & computational mathematics, Positive-definite matrix, System of linear equations, 01 natural sciences, 010101 applied mathematics, Computational Mathematics, Conjugate gradient method, Applied mathematics, Conjugate residual method, Minification, 0101 mathematics, [MATH]Mathematics [math], Mathematics, Conjugate, Descent (mathematics)
Abstract

The method of conjugate gradients, a particular version of the general class of conjugate direction methods, was originally developed for solving a linear system of equations $$ Ax = b,$$ where $A$ is an $n \times n$ symmetric, positive definite matrix, $x$ is an unknown $n$-vector and $b$ is a fixed $n$-vector. The conjugate gradient method can be viewed as a descent procedure for the problem : Minimize $$(x , Ax) - 2(x, b);$$ and through this viewpoint the method can be generalized so as to apply to the solution of general unconstrained minimization problems. For these general problems conjugate gradient methods are among the most effective first order descent procedures.

Published
1970

Catalog

Books, media, physical & digital resources
See catalog results