Séminaire Pluridisciplinaire d'Optimisation de Toulouse (SPOT) Pluridisciplinary Optimization Seminar in Toulouse (POST)

Comité local d'organisation 2012-2013

• Jérôme Bolte (UT1 et TSE)
• Serge Gratton (CERFACS et ENSEEIHT)
• Didier Henrion (LAAS – CNRS)
• Pierre Maréchal (ISAE)
• Frédéric Messine (IRIT et ENSEEIHT)
• Marcel Mongeau (ENAC)
• Aude Rondepierre (INSA et IMT)

Liste des séances 2012-2013

SPOT 10. Lundi 1 juillet 2013. Lieu: exceptionnellement, LAAS-CNRS, salle de conférences, conjointement avec la soutenance d'habilitation de Nicolas Mansard

My work is aiming at establishing the bases of a semiotics of motion, in order to facilitate the programing of complex robotics systems. The objective is to build a symbolic model of the action, based on the analysis of the numerical functions that drive the motion (control and planning). The methodology comes from the well-known robotics concepts: motion-planning algorithms, control of redundant systems and task-function approach. The originality of the work is to consider the ''task'' as the unifying concept both to describe the motion and to control its execution. The document is organized in two parts. In the first part, the task-function control framework is extended to cover all the possible modalities of the robot. The objective is to absorb from the lowest-possible functional level the maximum of uncertainty factors. It is then not any more necessary to model these factors at the higher functional levels. This sensorimotor layer is then used as a basic ``action vocabulary'' that enables the system to be controlled with a higher-level interface. In the second part, this action vocabulary is used to provide a dedicated robotics programing language, to build motion-planning methods and to describe an observed movement. The proposed methods are generic and can be applied to a various systems, from robotics (redundant robots) to computer animation (virtual avatars). Nonetheless, the work is more specifically dedicated to humanoid robotics. Without forgetting other possible outlets, humanoid robotics provides a tangible applicative and experimental framework. It also leads toward the natural human motion, as presented in the end of the document. See here for more information on the habilitation defense.

Robotic control has traditionally relied on pre-defined movements or hand-crafted model reductions. While optimal control formulations are appealing because they afford more flexibility, getting them to work in practice has been difficult due to high dimensionality, strong non-linearities and under-actuation. We have recently made advances on several fronts, that for the first time enable fully automated synthesis of complex behaviors with optimal control. These include new formulations of the physics of contact that are still realistic yet more amenable to numerical optimization, new representations of movement trajectories that allow more effective continuation methods, and a new physics simulator that takes advantage of parallel computing to speed up the numerical computation of derivatives. The talk will provide an overview of these developments and illustrate their effectiveness on a range of robotic control problem in simulation.

Feasibility problems, i.e., finding a solution satisfying certain constraints, are common in mathematics and the natural sciences. If the constraints have simple projectors (nearest point mappings), then one popular approach to these problems is to use the projectors in some algorithmic fashion to approximate a solution. In this talk, I will survey three methods (von Neumann's alternating projections, Dykstra's method, and the Douglas-Rachford method), comment on recent advances and remaining challenges, and describe a recent application in road design.

We give a tutorial-style introduction to polyhedral cones, their various generating functions, and Dedekind sums. The most basic generating function is a series that resembles a discrete Laplace transform, encoding the integer points in a convex polytope. We also introduce some Fourier methods that allow us to analyze integer points in polytopes, similar in spirit to the work of Brion, Vergne, and Barvinok. The most basic and yet interesting question along these lines would be: "What is the Fourier transform of a triangle?" As corollaries of these methods, Dedekind sums appear as building blocks of the ensuing Ehrhart polynomials and quasi-polynomials, and we discuss some of the computational complexity issues of Dedekind sums. We define all of these concepts from first principles.

SPOT 9. Lundi 3 juin 2013. Lieu: ENSEEIHT.

A geometric packing problem can be modeled as finding the independence number of a geometric infinite graph. For finite graphs one popular way to compute upper bounds for the independence number is to use Lasserre's semidefinite programming hierarchy. We generalize this hierarchy to infinite graphs and show that it converges after finitely many steps. Based on joint work with David de Laat.

In the first part of the talk we will review eigenvalue bounds for the independence number of a graph, their connection with Lovasz theta number, and their numerous applications in combinatorics. In a second part, we will discuss generalizations of these bounds that arise from certain hierarchies of semidefinite programs.

SPOT 8. Lundi 6 mai 2013. Lieu: UT1, Manufacture des Tabacs, Salle MF323, conjoint au séminaire MAD.

14h : Stéphane Gaubert (INRIA Saclay)
Tropical convexity applied to dynamic programming: a guided tour

Tropical convex sets have arisen in various guises. They can be obtained as limits of classical polyhedra, or as images by the valuation of polyhedra over the field of Puiseux series. We shall review some basic problems and results in tropical convexity, emphasizing the application to dynamic programming. These include external representation (separation and projection), discrepancies between classical and tropical vertices, and the equivalence between tropical linear programming and mean payoff games. Several of these results rely on techniques of non-linear Perron-Frobenius theory.

In ill-posed inverse problems one is often very happy when a given regularization scheme converges rapidly (in some sense) to the exact solution as some regularization parameter converges to zero. It is taken for granted that algorithms for solving the regularized problem converge rapidly to the regularized solution. We show that this assumption cannot be taken for granted and examine more closely the regularity requirements for local linear convergence of fundamental algorithms such as the method of alternating projections, steepest descents and the Douglas-Rachford algorithm. Linear convergence in particular is important for iteratively regularized schemes since this provides principled stopping criteria; until recently the focus has been only on convergence. Our goal is to determine the weakest conditions possible in order to achieve local linear convergence, and use this information to inform reguarization schemes. We demonstrate an application of the theory to the problem of phase retrieval in diffractive X-ray imaging.

SPOT 7. Lundi 8 avril 2013. Lieu: ENSEEIHT.

14h : Joachim Gwinner (Univ. Bundeswehr Munich)
On approximations of higher order for some nonsmooth variational problems

In this talk we are concerned with the finite element method in its hp- version to treat a scalar variational inequality of the mixed type that models unilateral contact and Coulomb friction or other nonsmooth material behaviour in continuum mechanics. Thus we extend recent work on the boundary element method to a larger class of nonlinear nonsmooth variational problems that are treatable by the finite element method. This leads to a nonconforming discretization scheme. In contrast to previous work we employ Gauss-Lobatto quadrature for the approximation of the unilateral constraint and also for the friction-type functional and take the resulting quadrature error into account of the error analysis. Atfirst without any regularity assumptions, we prove convergence of the FEM Galerkin solution in the energy norm. To this end we investigate Mosco- Stummel-Glowinski convergence for both convex sets and convex functionals. The key of our norm convergence result for the p-FEM is the used Gauss- Lobatto integration rule with its high exactness order and its positive weights together with duality arguments in the sense of convex analysis. Secondly by a novel Cea-Falk lemma we split the total discretization error into two different parts: the distance of the continuous solution to the convex set of approximations in the trial space and the consistency error caused by the nonconforming approximation. Here we use the well-known approximation theory of spectral methods, the cutting technique of Falk, and interpolation arguments. Moreover, we exploit the special structure of the friction-type functional. Thus we arrive under mild regularity assumptions at an a priori error estimate which is suboptimal because of the treatment of the full consistency error in the nonconforming approximation scheme and because of the well-known regularity threshold in unilateral problems.

When solving the Lagrangian dual problem, stabilization techniques are devised to accelarate convergence. Indeed, solution methods suffer typical drawbacks, such as dual oscillations, tailing-off effect, and primal degeneracy. In this presentation, we review stabilization procedures (such as smoothing, penalty functions, or interior point approaches) and we emphasize their link with cutting plane strategies. For instance, exploiting the duality between in-out separation and dual price smoothing helps to establish convergence proves and effective smoothing auto-regulating strategies that avoids the need for parameter tuning. The approach can further be combined with an ascent method, leading to improved performances. Joint work with A. Pessoa and E. Uchoa (Univ. Federal Fluminense, Brazil) and R. Sadykov (INRIA and Univ. Bordeaux).

SPOT 6. Lundi 18 mars 2013. Lieu: ENSEEIHT, exceptionnellement en Salle A202, Bâtiment A.

14h : Michel Théra (Univ. Limoges)
"Calmness modulus" en optimisation linéaire semi-infinie
Séminaire soutenu par la Structure Fédérative de Recherche en Mathématiques et Informatique de Toulouse (FREMIT).

Nous étudierons les propriétés de régularité métrique de la solution d'un problème d'optimisation linéaire (dite) semi-infinie lorsque la solution de ce problème est unique. Nous établirons une borne inférieure du module de "calmness" lorsque l'ensemble des contraintes estdéfini par une infinité d'inégalités ainsi qu'une formule exacte dans le cas de l'optimisation linéaire. Dans le cas où il n'y a plus unicité de la solution, nous proposerons une borne supérieure du module de "calmness" de la mutiapplication-solution. L'exposé sera agrémenté par de nombreux exemples.

Nous étudions une notion de régularité métrique d'ordre supérieur à un. Ensuite nous examinons la stabilité d'un problème d'optimisation min g(x(T)) où x(T) est le point terminal d'un système linéaire contrôlé, en étudiant la régularité métrique du système d'équations obtenues par le principe du maximum. Le principal intérêt de cette approche est d'obtenir des résultats de stabilité d'ordre supérieur à un.

************************************************************

SPOT 5. Lundi 4 février 2013. Lieu: ENSEEIHT.

14h : Claude Lemaréchal (INRIA Rhône-Alpes, Grenoble)
Polarity for unbounded convex sets

The traditional gauge/polarity theory establishes an involution in the class of compact convex neighborhoods of the origin. On the other hand, the cutting paradigm in combinatorial optimization (more specifically the so-called theory of S-free sets) calls for gauges of unbounded such neighborhoods. The talk will present some features of this challenge, its motivation, its difficulties. The main result is that polarity is no longer 1-to-1: a given set has a well-defined polar, but several "prepolars" may produce the same polar.

15h : François Malgouyres (Université Paul Sabatier, Toulouse)
Non-heuristic graph reduction for graph cuts and application to medical imaging

In few years, graph cuts have now become a fundamental combinatorial optimization tool in computer vision and graphics communities. Nevertheless, solving problems with a large number of variables remains computationally expensive and require a lot of memory storage since underlying graphs involve billion of nodes and even more edges. The strategies aiming at saving time and memory consumption of graph cuts include few exact methods and many heuristics. The latter generally fail to accurately preserve thin structures. In this paper, we propose a local test for reducing these graphs. As previous band-based strategies, the nodes are typically located in a narrow band surrounding the object edges. In addition, we prove that any node satisfying this test in the non-reduced graph can be safely removed without modifying the maximum flow value, keeping in this way the optimality on the solution. We present numerical experiments for segmenting large images which globally depict large memory gains.

In the second part of the talk, we describe an energy model (solved by graph cut) for the interactive segmentation of lung tumors in large 3D computerized tomography (CT) images. We illustrate the interest of the model and confront our results to the segmentation obtained by a physician.

************************************************************

SPOT 4. Lundi 7 janvier 2013. Lieu: ENSEEIHT.

14h : Eric Féron (Georgia Institute of Technology, Atlanta)
How can automatic control support the certification of safety-critical, embedded software ?

Certifying embedded software is a growing issue, as such software finds many safety-critical applications. Automotive and other ground transportation, Aerospace, many medical devices and soon robots will serve an increasingly sophisticated, but risk-adverse, human society. It therefore becomes necessary to certify such software, and the computer science community has provided a very strong response to this challenge, with the goal of reducing the enormous costs generated by this certification activity. Automatic control also contributes its share to this effort, because several embedded systems find their roots in feedback control systems, whose functional properties are often available immediately, though written in natural language that stands far away from software formalism. It is shown that computational bridges can be built to help the operator translate control specifications and their properties into a rigorous computer software environment, making the resulting software better prepared for its certification. This approach was initially tested on linear control laws, but it can be extended to other processes as well, including those derived from general dynamic programming or driven by on-line optimization as often seen in air transportation applications. This work is the result of a team effort that also includes LAAS, CERT-ONERA, ENSEEIHT, Rockwell-Collins, NASA, Carnegie-Mellon University, the National Institute of Aerospace, and the University of la Coruna.

15h : Sonia Cafieri (ENAC, Toulouse)
Deterministic conflict resolution for air traffic management

Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We present recent advances in modeling and deterministic solution of aircraft conflict avoidance problems. We propose in particular models and solution approaches based on mixed-integer nonlinear programming and optimal control. Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We present recent advances in modeling and deterministic solution of aircraft conflict avoidance problems. We propose in particular models and solution approaches based on mixed-integer nonlinear programming and optimal control.

SPOT 3. Lundi 10 décembre 2012 - Lieu: ENSEEIHT.

14h : Emilio Carrizosa (Universidad de Sevilla, Espagne)
Global optimization problems in data analysis

Many Statistical Data Analysis tasks lead in one way or another to Global Optimization problems, which may include continuous and integer variables and may have a very large number of variables, making exact Global Optimization impossible.
Different problems recently addressed by our research group will be analyzed, namely, Sparse Principal Component Analysis, Minimum-Sum-of-Squares Clustering in Social Networks, Parameter Selection in Support Vector Machines and Supervised Classification with robust criteria.
The problems will be described, formulated, and some ideas on how to solve them will be discussed. 

In network analysis, the problem of detecting subsets of elements important to the connectivity of a network (i.e., critical elements) has become a fundamental task over the last few years. Identifying the nodes, arcs, paths, clusters, cliques, etc., that are responsible for network cohesion can be crucial for studying many fundamental properties of a network. Depending on the context, finding these elements can help to analyze structural characteristics such as, attack tolerance, robustness, and vulnerability. Furthermore we can classify critical elements based on their centrality, prestige, reputation and can determine dominant clusters and partitions.
From the point of view of robustness and vulnerability analysis, evaluating how well a network will perform under certain disruptive events plays a vital role in the design and operation of such a network. To detect vulnerability issues, it is of particular importance to analyze how well connected a network will remain after a disruptive event takes place, destroying or impairing a set of its elements. The main goal is to identify the set of critical elements that must be protected or reinforced in order to mitigate the negative impact that the absence of such elements may produce in the network. Applications are typically found in homeland security, energy grid, evacuation planning, immunization strategies, financial networks, biological networks, and transportation.
From the member-classification perspective, identifying members with a high reputation and influential power within a social network could be of great importance when designing a marketing strategy. Positioning a product, spreading a rumor, or developing a campaign against drugs and alcohol abuse may have a great impact over society if the strategy is properly targeted among the most influential and recognized members of a community. The recent emergence of social networks such as Facebook, Twitter, LinkedIn, etc. provide countless applications for problems of critical-element detection.

SPOT 2. Lundi 12 novembre 2012 - Lieu: UT1, conjoint au séminaire MAD.

14h : Sylvain Sorin (Université Pierre et Marie Curie, Paris)
Programmation dynamique et jeux répétés: du temps discret au continu

Les principes de programmation dynamique ont été étendus en temps continu (conduisant aux équations HJB) et pour les jeux à 2 joueurs et à somme nulle (opérateur de Shapley). On peut utiliser la même approche pour étudier la limite des valeurs de jeux répétés via un passage en temps continu.

We introduce in this work a model of repeated zero-sum games with incomplete information on one side. At the beginning of the game, a state of nature is chosen randomly, and the first player receives a sequence of informative signals about this state variable all along the play while the second player does not receive any information. The payoff of each stage depends on actions taken by both players and also on the state variable. This model extends the classical model of Aumann and Maschler where the first player observes directly the state variable to a more general structure of signals. Our asymptotic approach is not related to the usual framework of undiscounted infinitely repeated games nor to the notion of uniform value. We consider that signals correspond asymptotically to observations of a continuous-time signalling process, for example the payoff function depend on the value of some Brownian motion at time T and the first player observes the value of this brownian motion at time t/n before stage t in the game of length n. This approach is well adapted in financial games with finite time horizon where time between two rounds goes to zero (or any model which approximate or can be approximated by a continuous-time model, e.g. differential games with incomplete information on one side). We prove a generalized version of the ``Cav(u)'' Theorem of Aumann and Maschler in this model using a probabilistic method based on martingales. We obtain a general characterization of the limits of optimal processes of revelation for the informed player and show that these optimal solutions induce n^{-1/2}-optimal strategies for the informed player in any game of length n. We also focus on the particular case with a finite number of informative signals and provide an abstract representation of the limit value function based on concavification operators.

SPOT 1. Lundi 1^er octobre 2012 - Lieu: ENSEEIHT.

14h : Yurii Nesterov (CORE, Université Catholique de Louvain-la-Neuve, Belgique)
Optimization in relative scale

The majority of modern optimization methods can deliver approximate solutions with absolute accuracy. Usually, the quality of such an approximations is affected by unknown parameters of the problems like Lipschitz constants and the size of the optimal solution. As a consequence, very often we ask for much higher absolute accuracy than needed.
In the last years we see more and more examples of optimization models, where the optimal solution is positive by its construction. For such problems it is usually possible to develop special schemes, which work with relative accuracy. Usually, such schemes need a preprocessing for computing an appropriate metric for measuring the problem data. Complexity estimates for such problems often depend only on the dimension of the problem and the desired relative accuracy. In our talk, we will discuss the most important examples of this approach.

In the same spirit as the one in a survey-paper co-authored with J. Malick on positive semidefine matrices ("A fresh variational-analysis look at the positive semidefinite matrices world", J. of Optimization Theory and Applications, 2012), we survey several useful properties of the rank function (of a matrix) and add some new ones. Since the so-called rank minimization problems are the subject of intense studies, we adopt the viewpoint of variational analysis, that is the one considering all the properties useful for optimizing, approximating or regularizing the rank function. Survey co-authored with Hai Yen Le, Ph D student.