• View
• Edit
• History
• Print

2008-2009

Many robust optimization problems cannot be solved due to computational intractability.

In this talk, a new probabilistic solution framework is introduced for robust convex optimization problems. This includes for instance robust linear and quadratic programs, and the wide class of optimization problems representable by means of parameter-dependent linear matrix inequalities (LMIs).

By appropriate sampling of the constraints, one obtains a convex optimization problem (the scenario problem) that can be solved by means of standard optimization solvers. The solution of the scenario problem bears probabilistic robustness properties that are chosen by the user.

A rich family of optimization problems which are in general hard to solve in a deterministically robust sense is therefore amenable to polynomial-time solution if robustness is intended in the proposed probabilistic sense. This opens-up new avenues for addressing problems in finance, control, systems theory and many more fields.

Methods of dimensionality reduction provide a way to understand and visualize the structure of complex data sets. Traditional methods like principal component analysis and classical metric multidimensional scaling suffer from being based on linear models. Since the late nineties, many newmethods have been developed and nonlinear dimensionality reduction, also called manifold learning, has become a hot topic. New advances that account for this rapid growth are, e.g. the use of graphs to represent the manifold topology, and the use of new metrics like the geodesic distance. This seminar will review (some of the) existing techniques for nonlinear dimensionality reduction, based either on the nonlinear optimization of well-designed objective criteria, or on the algebraic solution to simplified ones.

Subset selection methods try identify those columns of a matrix that are "most" linearly independent. Many subset selection methods are based on a QR decomposition with column pivoting. We discuss deterministic and probabilistic methods for subset selection, as well as the application of subset selection to nonlinear least squares problems in parameter estimation.

Networks that can be observed in the Business-to-Business analytics are related to companies and Business decision makers. Like other large networks, the size of the B2B related networks increases rapidly with the time and the information enrichment from additional sources. Vadis has developed a number of processes to build, partition and visualize such networks in the context of data mining applications. This discovery talk aims to give an overview of the approach and the results around this network development as well as the remaining challenges.

L'attachement préférentiel est un élément essentiel dans la théorie des réseaux complexes. Nous étudions un petit modèle de croissance de réseau avec attachement préférentiel et suppression de nœuds. Nous montrons analytiquement, et confirmons par des simulations, que selon les paramètres du modèle la distribution des degrées est asymptotiquement une loi de puissance ou bien observe une décroissance exponentielle. Il y a donc une transition de phase topologique entre ces deux régimes asymptotiques. A recent trend about estimating scientific achievement of a single researcher through quantitative bibliometric indicators (such as number of publications, number of citations, Hirsch index...) has been largely criticized. However, large scale correlations for several thousand scientists may bring a few insights. In such a study, we compare the predictions of several bibliometric indicators on the promotions of about 600 CNRS researchers. Contrary to previous publications, our study encompasses most disciplines, and shows that no single indicator is the best predictor for all disciplines. Overall, the Hirsch index h provides the least bad correlations, followed by the number of papers published. It is important to realize however that even h is able to recover only half of the actual promotions. We then turn to dissemination activities of several thousands CNRS researchers: most scientific institutions acknowledge the importance of opening the so-called 'ivory tower' of academic research through popularization (through media or general audience events), industrial collaboration or teaching. However, little is known about the actual openness of scientific institutions and how their proclaimed priorities translate into concrete measures. This study gives an idea of some actual practices. We find that, contrary to what is often suggested, scientists active in wider dissemination are also more active academically. However, their dissemination activities have almost no impact (positive or negative) on their careers.

hape modelling is important in many disciplines, in particular image processing and computer vision, where it is used for the segmentation of objects from images. As a result, it has been the subject of a great deal of research, for example in statistics. For the most part, this research has focused on modelling families of shapes consisting of deviations around a given reference shape with a simple topology. There are applications, however, where the family of shapes involved does not show such constrained behaviour. Cases where the number of objects is unknown a priori, or where the topology of the shape may be otherwise complex (for example, network shapes), require new techniques. 'Higher-order active contours' (HOACs) represent one approach to modelling such families of shapes. By introducing explicit long-range interactions between points on the shape boundary, HOACs can model families of shapes sharing geometric properties without overly constraining topology. Representing shapes by their boundaries is often inconvenient, however, both analytically and numerically, especially for complex topologies. An alternative is the approach known as 'phase field' modelling. The phase field representation and modelling framework offers a number of advantages over other approaches, both for the simplest shape models and for HOACs. By way of illustration, the use of HOAC and HOAC phase field models to estimate the regions corresponding to road networks and tree crowns in satellite and aerial images will be described.

In this communication we present some recent results concerning the mathematical modeling of the behavior of social groups, notably to unravel the mechanisms that make opinion to diffuse (in the group) and how this diffusion shapes the group of acquaintances. We propose a model of (scalar) opinion dynamics model where agents adjust their current opinion as a result of random encounters, allowing to study the mechanism of group formation under the pressure of two antagonist forces: friendship and social temperature. As a result of the interactions, clusters of individuals sharing the same opinion and displaying high affinity-friendship values are formed. The distribution of the clusters is monitored and a second order phase transition detected, marking the distinction between a full connected group and a fragmented population. Using this model we are able to propose a dynamical interpretation of the sociological distinction between large and small groups of interacting individuals: In the former case individual behaviors are largely dominated by the group effect, while in the latter mutual relationships do matter. We also show that "small world property" could naturally emerge in the social group. Numerical and analytical tools are combined to substantiate our claims.

For a complete description of the talk, please check the pdf version of the abstract?.

We show that the graph isomorphism problem is polynomially reducible to the problem of recognition of equal (isometrically equivalent) simplices in n-dimensional space. This elementary observation can lead to new methods in the graph isomorphism problem based on geometrical properties of simplices. In particular, relations between several previously known classes of spectral and combinatorial invariants of graphs and geometrical invariants of simplices are established.

Repetitions, i.e., consecutive occurrences of words within a word and especially repetition-freeness have been fundamental research subjects in combinatorics on words since the seminal papers of Thue in the beginning of the 20th century. In this talk we consider repetition-freeness of partial words. Partial words are sequences of letters containing special "do not know"-symbols "#" called holes. For example, the word " abba#b" is a partial square since the hole can be replaced by "b" and the word becomes a square " abbabb" . We concentrate on square-freeness and overlap-freeness. We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite number of holes. We also show that there exist infinitely many infinite overlap-free binary partial words containing at least one hole. These words cannot contain more than one hole and the only hole must occur either in the first or in the second position. A construction of 2-overlap-free binary partial words containing an infinite number of holes will be mentioned.

I will give a short introduction to Particle Swarm Optimization.This technique was first proposed in 1995 by J.Kennedy and C.R.Eberhart.Since then, many articles have been published on this topic. Based on my reading of the book "Fundamentals of computational swarm intelligence - Andries P.Engelbrecht (Wiley)", I will present : the basic PSO algorithm and its characteristics, a brief study of the particles trajectories, the ideas for proving the algorithm convergence, some techniques to extend PSO abilities to multi-modal optimization.

Hash functions are a invaluable tool for Cryptography, used for message authentication codes and digital signatures but also in almost any cryptographic protocol. Hash functions map large messages into small bitstrings. Their primary purpose is to satisfy collision and preimage resistance, but due to their wide range of applications they are often built and considered as 'random functions'. Due to increasingly efficient attacks against its current standard SHA, NIST has recently prompted a competition for a new secure hash algorithm.We describe how to build cryptographic hash functions from large expander graphs and how the cryptographic properties of the functions may be interpreted as graph properties, and as group properties when using Cayley graphs. We describe the advantages and drawbacks of the design, we review existing proposals and we identify which graphs make good candidates for hash functions. Finally, we propose a simple solution to the main drawbacks of the design and we conclude with an interesting open problem in non-Abelian groups.

Firstly, I will discuss social influence and popularity of cultural items (e.g. books or movies). Some items become popular, while others remain largely obscure. This distribution of popularity is investigated. While popularity breeds its own popularity, quality might also play a role. A theoretical model is formulated which balances the influence of popularity and quality, and empirical distributions from YouTube and Hollywood are compared. Secondly, I will present a new method for community detection in networks with both negative and positive links. A popular way for community detection is through optimizing a quality function known as modularity. However, for networks with both negative and positive links this function is ill-defined. By redefining modularity, community detection in these types of networks becomes possible. An example application of this method to networks of international alliances and conflicts is presented.

We consider the problem of partial order production: arrange the elements of an unknown totally ordered T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases of this problem include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing ITLB + o(ITLB) + O(n) comparisons in the worst case. Here, n denotes the size of the ground sets, and ITLB denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target poset. The overall complexity of our algorithm is polynomial. This answers a question of Yao (SICOMP, 1989). Our strategy is to extend the poset S to a weak order W whose corresponding information-theoretic lower bound is provably not much larger than that for S. Taking W instead of S as a target poset, we then solve the problem by applying a multiple selection algorithm that performs not much more than ITLB comparisons. We base our analysis on the entropy of the target poset S, a quantity that can be efficiently computed and provides a good estimate of ITLB since the latter is, up to a linear error term, n times the entropy of S.

Sequential decision making under the presence of uncertainties is often modelled by Markov decision processes (MDPs). In practical applications, however, the parameters of MDPs are often not exactly known, they are usually estimated, and therefore, there may be parameter uncertainties, as well. In the presentation, first, I consider the case when the transition-probability function is fixed, but uncertain, viz., we do not know what it is, we only know that it belongs to a given uncertainty set. I propose an efficient robust convex optimization based approach to handle this problem. Then, I analyze the case, when the transition-probability and the immediate-cost functions are uncertain in a way that they may vary from time to time, provided that the accumulated changes remain asymptotically bounded. I investigate the possibility of applying stochastic iterative algorithms (SIAs) in this kind of changing environments. I present a generalized convergence theorem for SIAs with time-dependent update operators. Afterwards, I apply this theorem to deduce a convergence theorem for value function based reinforcement learning (RL) methods working in changing MDPs. Finally, I illustrate these results through variants of classical RL algorithms as well as numerical experiments.

Given a linear numeration system U and a set X (include in N) such that repU(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X is ultimately periodic, i.e., whether or not X is a finite union of arithmetic progressions ? J. Honkala showed that this problem turns out to be decidable for the usual b-ary numeration system (b greater than 2) defined by Un = bUn-1 for n greater than 1 and U0 = 1. In this work, we give a decision procedure for this problem for a large class of linear numeration systems. More information can be found [[Attach:"abstract E.Charlier Louvain 12-12-08.pdf|here

Fibrous active network structures whose properties are regulated by motor proteins, or simply motors, are fundamental to life. A fully elastic, three-dimensional model for such a network is presented. We include the effects of surface anchoring and demonstrate that, for unidirectional motors, two basic contractile phases emerge in these systems. The transition is governed by the ratio of the breaking strain $ tau_b$ and the motility limiting strain $ tau_c$ of the motors.

For $ tau_b/tau_c lesssim 2$ and clamped boundaries, a network rupture occurs, forming local asters with a high density of motors at the centre and the fibers radially spanning out. This phase displays contraction strain during the formation of asters, but the network stress is relaxed once the asters are formed, demonstrating that the formation aster-like structures provides a mechanism for stress relaxation.

For $ 2 lesssim tau_b/tau_c$ the network is not ruptured, but reaches a force equilibrium with a high contraction strain in the case of clamped boundaries. In the case of free boundaries, the network collapses into one single aster. We also show that the distribution of energy on the motors is a power law with the exponent $ -frac{1}{2}$ .

In this talk, we will discuss two problems that arise in the control of a formation of autonomous agents. The first problem is how to maintain a triangular formation in the plane consisting of three mobile autonomous agents. It is shown that the distributed control law we proposed can cause any initially non-collinear formation to converge exponentially fast to the desired formation. It is also shown that initially collinear formations remain collinear and may drift off to infinity as time t approaches infinity. The second problem is the three landmark station keeping problem in the plane in which range measurements are the only sensed signals upon which station keeping is to be based. A tractable and provably correct solution is given using concepts from switched adaptive control theory plus a special parameterization of the class of 2-by-2 nonsingular matrices. The performance of the overall system degrades gracefully in the face of increasing measurement and miss-alignment errors, provided the measurement errors are not too large.

The talk focuses on the development of algorithmic methods for calculating the extinction probability of a particular class of multitype branching processes called "Markovian binary trees." We analyze these processes in the general context, where the particles behave independently of each other, and in the presence of catastrophes or within a Markovian random environment, where independence does not happen anymore, which complicates the analysis. Most algorithms are obtained on the basis of their probabilistic interpretation in terms of growing families of trees. Transient measures associated with Markovian binary trees are also described, such as the distribution of their size at a given time, the distribution of the time until extinction, and the distribution of the total progeny. We apply our results to the demographic comparison of ten world populations, by adapting real data to the parameters of our model.

Note: the seminar has been moved to friday

Slides of the seminar are available here?.

During this talk, I will show that the quality of the partition of a graph can be expressed in terms of the auto-correlation of a dynamical process taking place on it. This approach allows to recover a well-known quality function, i.e. modularity, but also defines a whole family of quality functions which incorporate in a natural way a resolution parameter associated to the time scale of the process. The cases of a random walk and of the linearised Kuramoto model are discussed in order to illustrate the approach. The possibility to optimize the family of functions for large (unknown) graphs is also discussed.

The WWW is slowly moving from a web of pages to a web of objects. Natural Language processing tools are being used today to anotate large quantities of text with entities and types: people, business, adresses, etc. Data models such as RDF are used to directly encode this information in web pages. A number of graphs can be constructed with this novel information, and these graphs can be analysed to find properties of the objects. For example, one may want to find the most relevant dates, locations and people for a given ad-hoc query. I will show some examples of these graphs and some initial search prototypes developed at Yahoo! Research Barcelona.

Communication networks between cities : analysis of large datasets
Gautier Krings

On a quantity characterizing cones
Raphaël Jungers

Accelerated optimization methods
Pierre-Antoine Absil

http://www.uclouvain.be/238384.html

I will present a model of social networks motivated by a recent large-scale empirical study. By starting from a set of plausible microscopic rules governing the formation of social ties at the individual level, the model is able to produce macroscopic social structures that are compatible with real world social networks. In particular, the model enables exploring the role of interaction strengths in the emergence of communities in social systems. It turns out that by tuning a model parameter that governs the sensitivity of the microscopic rules to tie strengths, the resulting networks undergo a gradual structural transition from a module-free topology to one with communities.

Slides?.

This talk will present a method for accurately computing the solution of a wave equation by decomposing it onto a largely incomplete set of eigenfunctions of the Helmholtz operator, chosen at random. The recovery method is the ell-1 minimization of compressed sensing. The guarantees of success are based on three new estimates for the wave equation, namely 1) an L1 estimate, 2) a result of extension of the eigenfunctions, and 3) an eigenvalue gap estimate. These estimates hold in the one-dimensional case when the variable speed of sound has small total variation. In practice, the compressive strategy is a natural way of parallelizing wave simulations for memory-intensive applications. Joint work with Laurent Demanet.

Abstract: I present a method for composing, inverting, exponentiating, and taking the square root of the singular integral operators that arise from linear PDE, by compression of their pseudodifferential symbol. This approach leads to novel fast-summation-style algorithms for the wave and Helmholtz equations in variable media. The computational complexity is (provably) proportional to the bandwidth of the coefficients of the PDE, not the solution of the PDE, which is an important point in view of applications to inverse scattering problems in reflection seismology. Joint work with Lexing Ying from UT Austin.

Je reprendrai la structure de ma thèse, en parlant tout d'abord des modèles existants de piles de sable et des améliorations proposées, puis je parlerai de leur unification à l'aide des automates de sable (définitions, résultats et axes de recherche), qui rendent possible une étude plus globale.