CINXE.COM

<!DOCTYPE html>    <html lang="en-US">  <head> <meta charset="UTF-8" /> <meta name="viewport" content="width=device-width" /> <link rel="profile" href="http://gmpg.org/xfn/11" /> <link rel="pingback" href="https://cermics-lab.enpc.fr/xmlrpc.php" />  <title>Decision, Algorithms and Geometry – CERMICS</title> <link rel='dns-prefetch' href='//fonts.googleapis.com' /> <link rel='dns-prefetch' href='//s.w.org' /> <link rel="alternate" type="application/rss+xml" title="CERMICS » Feed" href="https://cermics-lab.enpc.fr/feed/" /> <link rel="alternate" type="application/rss+xml" title="CERMICS » Comments Feed" href="https://cermics-lab.enpc.fr/comments/feed/" /> <script type="text/javascript"> window._wpemojiSettings = {"baseUrl":"https:\/\/s.w.org\/images\/core\/emoji\/2\/72x72\/","ext":".png","svgUrl":"https:\/\/s.w.org\/images\/core\/emoji\/2\/svg\/","svgExt":".svg","source":{"concatemoji":"https:\/\/cermics-lab.enpc.fr\/wp-includes\/js\/wp-emoji-release.min.js?ver=4.6.29"}}; !function(e,o,t){var a,n,r;function i(e){var t=o.createElement("script");t.src=e,t.type="text/javascript",o.getElementsByTagName("head")[0].appendChild(t)}for(r=Array("simple","flag","unicode8","diversity","unicode9"),t.supports={everything:!0,everythingExceptFlag:!0},n=0;n<r.length;n++)t.supports[r[n]]=function(e){var t,a,n=o.createElement("canvas"),r=n.getContext&&n.getContext("2d"),i=String.fromCharCode;if(!r||!r.fillText)return!1;switch(r.textBaseline="top",r.font="600 32px Arial",e){case"flag":return(r.fillText(i(55356,56806,55356,56826),0,0),n.toDataURL().length<3e3)?!1:(r.clearRect(0,0,n.width,n.height),r.fillText(i(55356,57331,65039,8205,55356,57096),0,0),a=n.toDataURL(),r.clearRect(0,0,n.width,n.height),r.fillText(i(55356,57331,55356,57096),0,0),a!==n.toDataURL());case"diversity":return r.fillText(i(55356,57221),0,0),a=(t=r.getImageData(16,16,1,1).data)[0]+","+t[1]+","+t[2]+","+t[3],r.fillText(i(55356,57221,55356,57343),0,0),a!=(t=r.getImageData(16,16,1,1).data)[0]+","+t[1]+","+t[2]+","+t[3];case"simple":return r.fillText(i(55357,56835),0,0),0!==r.getImageData(16,16,1,1).data[0];case"unicode8":return r.fillText(i(55356,57135),0,0),0!==r.getImageData(16,16,1,1).data[0];case"unicode9":return r.fillText(i(55358,56631),0,0),0!==r.getImageData(16,16,1,1).data[0]}return!1}(r[n]),t.supports.everything=t.supports.everything&&t.supports[r[n]],"flag"!==r[n]&&(t.supports.everythingExceptFlag=t.supports.everythingExceptFlag&&t.supports[r[n]]);t.supports.everythingExceptFlag=t.supports.everythingExceptFlag&&!t.supports.flag,t.DOMReady=!1,t.readyCallback=function(){t.DOMReady=!0},t.supports.everything||(a=function(){t.readyCallback()},o.addEventListener?(o.addEventListener("DOMContentLoaded",a,!1),e.addEventListener("load",a,!1)):(e.attachEvent("onload",a),o.attachEvent("onreadystatechange",function(){"complete"===o.readyState&&t.readyCallback()})),(a=t.source||{}).concatemoji?i(a.concatemoji):a.wpemoji&&a.twemoji&&(i(a.twemoji),i(a.wpemoji)))}(window,document,window._wpemojiSettings); </script> <style type="text/css"> img.wp-smiley, img.emoji { display: inline !important; border: none !important; box-shadow: none !important; height: 1em !important; width: 1em !important; margin: 0 .07em !important; vertical-align: -0.1em !important; background: none !important; padding: 0 !important; } </style> <link rel='stylesheet' id='avatar-manager-css' href='https://cermics-lab.enpc.fr/wp-content/plugins/avatar-manager/assets/css/avatar-manager.min.css?ver=1.2.1' type='text/css' media='all' /> <link rel='stylesheet' id='wp-hal-style1-css' href='https://cermics-lab.enpc.fr/wp-content/plugins/hal/css/style.css?ver=4.6.29' type='text/css' media='all' /> <link rel='stylesheet' id='zerogravity-fonts-css' href='https://fonts.googleapis.com/css?family=Arimo:400italic,700italic,400,700&subset=latin,latin-ext' type='text/css' media='all' /> <link rel='stylesheet' id='zerogravity-style-css' href='https://cermics-lab.enpc.fr/wp-content/themes/zerogravity/style.css?ver=1.9.3' type='text/css' media='all' /> <link rel='stylesheet' id='zerogravity-custom-style-css' href='https://cermics-lab.enpc.fr/wp-content/themes/zerogravity/custom-style.css?ver=4.6.29' type='text/css' media='all' />  <link rel='stylesheet' id='dashicons-css' href='https://cermics-lab.enpc.fr/wp-includes/css/dashicons.min.css?ver=4.6.29' type='text/css' media='all' /> <link rel='stylesheet' id='font-awesome-css' href='https://cermics-lab.enpc.fr/wp-content/themes/zerogravity/css/font-awesome-4.4.0/css/font-awesome.min.css?ver=4.6.29' type='text/css' media='all' /> <script type='text/javascript' src='https://cermics-lab.enpc.fr/wp-includes/js/jquery/jquery.js?ver=1.12.4'></script> <script type='text/javascript' src='https://cermics-lab.enpc.fr/wp-includes/js/jquery/jquery-migrate.min.js?ver=1.4.1'></script> <script type='text/javascript' src='https://cermics-lab.enpc.fr/wp-content/plugins/avatar-manager/assets/js/avatar-manager.min.js?ver=1.2.1'></script> <link rel='https://api.w.org/' href='https://cermics-lab.enpc.fr/wp-json/' /> <link rel="EditURI" type="application/rsd+xml" title="RSD" href="https://cermics-lab.enpc.fr/xmlrpc.php?rsd" /> <link rel="wlwmanifest" type="application/wlwmanifest+xml" href="https://cermics-lab.enpc.fr/wp-includes/wlwmanifest.xml" /> <meta name="generator" content="WordPress 4.6.29" /> <link rel="canonical" href="https://cermics-lab.enpc.fr/seminaires/decision-algorithms-and-geometry/" /> <link rel='shortlink' href='https://cermics-lab.enpc.fr/?p=3083' /> <link rel="alternate" type="application/json+oembed" href="https://cermics-lab.enpc.fr/wp-json/oembed/1.0/embed?url=https%3A%2F%2Fcermics-lab.enpc.fr%2Fseminaires%2Fdecision-algorithms-and-geometry%2F" /> <link rel="alternate" type="text/xml+oembed" href="https://cermics-lab.enpc.fr/wp-json/oembed/1.0/embed?url=https%3A%2F%2Fcermics-lab.enpc.fr%2Fseminaires%2Fdecision-algorithms-and-geometry%2F&format=xml" /> <style type='text/css'> a {color: #0098D3;} a:hover {color: #0098D3;} .blog-info-sin-imagen {background-color: #0098D3;} .social-icon-wrapper a:hover {color: #0098D3;} .toggle-search {color: #0098D3;} .prefix-widget-title {color: #0098D3;} .term-icon {color: #0098D3;} .sub-title a:hover {color:#0098D3;} .entry-content a:visited,.comment-content a:visited {color:#0098D3;} input[type="submit"] {background-color:#0098D3 !important;} .bypostauthor cite span {background-color:#0098D3;} .site-header h1 a:hover, .site-header h2 a:hover { color: #0098D3; } .entry-header .entry-title a:hover {color:#0098D3 ;} .archive-header {border-left-color:#0098D3;} .main-navigation a:hover, .main-navigation a:focus { color: #0098D3; } .widget-area .widget a:hover { color: #0098D3 !important; } footer[role="contentinfo"] a:hover { color: #0098D3; } .entry-meta a:hover { color: #0098D3; } .format-status .entry-header header a:hover { color: #0098D3; } .comments-area article header a:hover { color: #0098D3; } a.comment-reply-link:hover, a.comment-edit-link:hover { color: #0098D3; } .main-navigation .current-menu-item a, .main-navigation .current-menu-ancestor > a, .main-navigation .current_page_item > a, .main-navigation .current_page_ancestor > a {color: #0098D3;} .currenttext, .paginacion a:hover {background-color:#0098D3;} .main-navigation li a:hover {color: #0098D3;} .aside{border-left-color:#0098D3 !important;} blockquote{border-left-color:#0098D3;} .logo-header-wrapper, .image-header-wrapper {background-color:#0098D3;} h2.comments-title {border-left-color:#0098D3;} .logo-header-wrapper, .image-header-wrapper {background-color:#ffffff;} .blog-info-sin-imagen { background-color:#ffffff; color:#444444 !important; } .blog-info-sin-imagen a { color:#444444 !important; } .blog-info-sin-imagen h2 {color:#444444 !important;} body.custom-font-enabled {font-family: "Arimo", Arial, Verdana;} @media screen and (max-width: 599px) { .menu-toggle, .menu-toggle:hover { background:#0098D3 !important; color:#ffffff !important; width:100%; } } </style> <style type="text/css" id="custom-background-css"> body.custom-background { background-color: #9b9b9b; } </style> <link rel="icon" href="https://cermics-lab.enpc.fr/wp-content/uploads/2016/12/cropped-7-ecole_ponts_rvb_transparent-32x32.png" sizes="32x32" /> <link rel="icon" href="https://cermics-lab.enpc.fr/wp-content/uploads/2016/12/cropped-7-ecole_ponts_rvb_transparent-192x192.png" sizes="192x192" /> <link rel="apple-touch-icon-precomposed" href="https://cermics-lab.enpc.fr/wp-content/uploads/2016/12/cropped-7-ecole_ponts_rvb_transparent-180x180.png" /> <meta name="msapplication-TileImage" content="https://cermics-lab.enpc.fr/wp-content/uploads/2016/12/cropped-7-ecole_ponts_rvb_transparent-270x270.png" />  <script async src="https://www.googletagmanager.com/gtag/js?id=UA-109939919-1"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){dataLayer.push(arguments);} gtag('js', new Date()); gtag('config', 'UA-109939919-1'); </script> </head> <body class="page page-id-3083 page-child parent-pageid-18 page-template page-template-page-templates page-template-full-width page-template-page-templatesfull-width-php custom-background full-width custom-font-enabled"> <div id="page" class="hfeed site"> <header id="masthead" class="site-header" role="banner"> <div class="top-bar"> <div class="boton-menu-movil"><i class="fa fa-align-justify"></i></div> <div class="blog-title-wrapper"> CERMICS </div> <div class="toggle-search"><i class="fa fa-search"></i></div> <div class="social-icon-wrapper"> <a class="rss" href="http://cermics-lab.enpc.fr/intranet" title="intranet" target="_blank"><small>Intranet</small></a> </div> </div> <div class="wrapper-search-top-bar"> <div class="search-top-bar"> <div> <form method="get" id="searchform-toggle" action="https://cermics-lab.enpc.fr/"> <label for="s" class="assistive-text">Search</label> <input type="search" class="txt-search" name="s" id="s" /> <input type="submit" name="submit" id="btn-search" value="Search" /> </form> </div> </div> </div> <div style="position:relative"> <div id="menu-movil"> <div class="search-form-movil"> <form method="get" id="searchform-movil" action="https://cermics-lab.enpc.fr/"> <label for="s" class="assistive-text">Search</label> <input type="search" class="txt-search-movil" placeholder="Search..." name="s" id="s" /> <input type="submit" name="submit" id="btn-search-movil" value="Search" /> </form> </div> <div class="menu-movil-enlaces"> <div class="menu-menu-principal-container"><ul id="menu-menu-principal" class="nav-menu"><li id="menu-item-22" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22"><a href="https://cermics-lab.enpc.fr/">Home</a></li> <li id="menu-item-26" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-has-children menu-item-26"><a href="https://cermics-lab.enpc.fr/organisation/">Organization</a> <ul class="sub-menu"> <li id="menu-item-2992" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-2992"><a href="https://cermics-lab.enpc.fr/organisation/overall-organization/">Overall organization</a></li> <li id="menu-item-42" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-42"><a href="https://cermics-lab.enpc.fr/organisation/probabilites-appliquees/">Applied probability</a></li> <li id="menu-item-34" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-34"><a href="https://cermics-lab.enpc.fr/organisation/modelisation-analyse-et-simulation/">Modeling, Analysis and Simulation</a></li> <li id="menu-item-892" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-892"><a href="https://cermics-lab.enpc.fr/organisation/optimization/">Optimization</a></li> </ul> </li> <li id="menu-item-23" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-has-children menu-item-23"><a href="https://cermics-lab.enpc.fr/activite-scientifique/">Activity</a> <ul class="sub-menu"> <li id="menu-item-64" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-64"><a href="https://cermics-lab.enpc.fr/activite-scientifique/theses-et-hdrs/">PhD and habilitation theses</a></li> <li id="menu-item-4336" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-4336"><a href="https://cermics-lab.enpc.fr/activite-scientifique/presentations-by-phd-students-and-postdocs/">Presentations by PhD students and postdocs</a></li> <li id="menu-item-522" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-522"><a href="https://cermics-lab.enpc.fr/activite-scientifique/grants-and-contracts/">Grants and contracts</a></li> <li id="menu-item-82" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-82"><a href="https://cermics-lab.enpc.fr/enseignement/">Teaching</a></li> <li id="menu-item-66" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-66"><a href="https://cermics-lab.enpc.fr/activite-scientifique/rapports-dactivite/">Activity reports</a></li> <li id="menu-item-78" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-78"><a href="https://cermics-lab.enpc.fr/activite-scientifique/rapports-devaluation/">Evaluation reports</a></li> </ul> </li> <li id="menu-item-27" class="menu-item menu-item-type-post_type menu-item-object-page current-page-ancestor current-menu-ancestor current-menu-parent current-page-parent current_page_parent current_page_ancestor menu-item-has-children menu-item-27"><a href="https://cermics-lab.enpc.fr/seminaires/">Seminars</a> <ul class="sub-menu"> <li id="menu-item-71" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-71"><a href="https://cermics-lab.enpc.fr/seminaires/colloquium-du-cermics/">Colloquium</a></li> <li id="menu-item-625" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-625"><a href="https://cermics-lab.enpc.fr/seminaires/seminaire-du-laboratoire/">Applied Mathematics</a></li> <li id="menu-item-624" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-624"><a href="https://cermics-lab.enpc.fr/seminaires/young-researchers-seminar/">Young Researchers</a></li> <li id="menu-item-429" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-429"><a href="http://cermics.enpc.fr/~alfonsi/GTMSF.html">Stochastic methods and finance</a></li> <li id="menu-item-3086" class="menu-item menu-item-type-post_type menu-item-object-page current-menu-item page_item page-item-3083 current_page_item menu-item-3086"><a href="https://cermics-lab.enpc.fr/seminaires/decision-algorithms-and-geometry/">Decision, algorithms and geometry</a></li> <li id="menu-item-4869" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-4869"><a href="https://cermics-lab.enpc.fr/seminaires/data-transitions/">Data Transitions</a></li> </ul> </li> <li id="menu-item-4770" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-4770"><a href="https://cermics-lab.enpc.fr/cauchy-fellowship/">Cauchy fellowship</a></li> <li id="menu-item-24" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-24"><a href="https://cermics-lab.enpc.fr/annuaire/">People</a></li> <li id="menu-item-113" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-113"><a href="https://cermics-lab.enpc.fr/acces/">How to find us</a></li> </ul></div> </div> <div class="social-icon-wrapper-movil"> <a class="rss" href="http://cermics-lab.enpc.fr/intranet" title="RSS" target="_blank"><i class="fa fa-rss"></i></a> </div> </div> </div> <div class="image-header-wrapper"> <a href="https://cermics-lab.enpc.fr/"><img src="https://cermics-lab.enpc.fr/wp-content/uploads/2016/12/cropped-coriolis_credit.jpg" class="header-image" width="1382" height="336" alt="CERMICS" /></a> </div> <nav id="site-navigation" class="main-navigation" role="navigation"> <a class="assistive-text" href="#content" title="Skip to content">Skip to content</a> <div class="menu-menu-principal-container"><ul id="menu-menu-principal-1" class="nav-menu"><li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22"><a href="https://cermics-lab.enpc.fr/">Home</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-has-children menu-item-26"><a href="https://cermics-lab.enpc.fr/organisation/">Organization</a> <ul class="sub-menu"> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-2992"><a href="https://cermics-lab.enpc.fr/organisation/overall-organization/">Overall organization</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-42"><a href="https://cermics-lab.enpc.fr/organisation/probabilites-appliquees/">Applied probability</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-34"><a href="https://cermics-lab.enpc.fr/organisation/modelisation-analyse-et-simulation/">Modeling, Analysis and Simulation</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-892"><a href="https://cermics-lab.enpc.fr/organisation/optimization/">Optimization</a></li> </ul> </li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-has-children menu-item-23"><a href="https://cermics-lab.enpc.fr/activite-scientifique/">Activity</a> <ul class="sub-menu"> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-64"><a href="https://cermics-lab.enpc.fr/activite-scientifique/theses-et-hdrs/">PhD and habilitation theses</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-4336"><a href="https://cermics-lab.enpc.fr/activite-scientifique/presentations-by-phd-students-and-postdocs/">Presentations by PhD students and postdocs</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-522"><a href="https://cermics-lab.enpc.fr/activite-scientifique/grants-and-contracts/">Grants and contracts</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-82"><a href="https://cermics-lab.enpc.fr/enseignement/">Teaching</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-66"><a href="https://cermics-lab.enpc.fr/activite-scientifique/rapports-dactivite/">Activity reports</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-78"><a href="https://cermics-lab.enpc.fr/activite-scientifique/rapports-devaluation/">Evaluation reports</a></li> </ul> </li> <li class="menu-item menu-item-type-post_type menu-item-object-page current-page-ancestor current-menu-ancestor current-menu-parent current-page-parent current_page_parent current_page_ancestor menu-item-has-children menu-item-27"><a href="https://cermics-lab.enpc.fr/seminaires/">Seminars</a> <ul class="sub-menu"> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-71"><a href="https://cermics-lab.enpc.fr/seminaires/colloquium-du-cermics/">Colloquium</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-625"><a href="https://cermics-lab.enpc.fr/seminaires/seminaire-du-laboratoire/">Applied Mathematics</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-624"><a href="https://cermics-lab.enpc.fr/seminaires/young-researchers-seminar/">Young Researchers</a></li> <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-429"><a href="http://cermics.enpc.fr/~alfonsi/GTMSF.html">Stochastic methods and finance</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page current-menu-item page_item page-item-3083 current_page_item menu-item-3086"><a href="https://cermics-lab.enpc.fr/seminaires/decision-algorithms-and-geometry/">Decision, algorithms and geometry</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-4869"><a href="https://cermics-lab.enpc.fr/seminaires/data-transitions/">Data Transitions</a></li> </ul> </li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-4770"><a href="https://cermics-lab.enpc.fr/cauchy-fellowship/">Cauchy fellowship</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-24"><a href="https://cermics-lab.enpc.fr/annuaire/">People</a></li> <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-113"><a href="https://cermics-lab.enpc.fr/acces/">How to find us</a></li> </ul></div> </nav> </header> <div id="main" class="wrapper"> <div id="primary" class="site-content border-none"> <div id="content" role="main"> <article id="post-3083" class="post-3083 page type-page status-publish hentry"> <header class="entry-header"> <h1 class="entry-title">Decision, Algorithms and Geometry</h1> </header> <div class="entry-content"> <p>Joint seminar of聽the Optimization team of CERMICS (Ecole des Ponts<br /> Paristech) and the Tropical team (INRIA Saclay & CMAP, Ecole<br /> Polytechnique)</p> <hr /> <h2><span style="text-decoration: underline">Forthcoming sessions</span></h2> <h2></h2> <p> </p> <p> </p> <p> </p> <h3>April 21st, Ecole Polytechnique</h3> <h2><a href="https://lipn.univ-paris13.fr/~pournin/">Lionel Pournin</a> (LIPN, Paris XIII)</h2> <p><strong>Algorithmic, combinatorial, and geometric aspects of linear<br /> optimization </strong></p> <p>The simplex and interior point methods are currently the most<br /> computationally successful algorithms for linear optimization. While<br /> simplex methods follow an edge path, interior point methods follow the<br /> central path. The complexity of these methods is closely related to the<br /> combinatorial and geometric structures of the feasible region. Focusing<br /> on the analysis of worst-case constructions leading to computationally<br /> challenging instances, recently obtained lower bounds on the largest<br /> possible diameter of lattice polytopes will be presented. These bounds,<br /> via lattice zonotopes, are established using tools from combinatorics<br /> and number theory. This talk is based on joint work with Antoine Deza.</p> <h2><span style="text-decoration: underline">Past sessions</span></h2> <h3>March 24th, 10:00, Ecole des Ponts, F102</h3> <h2><a href="http://www.im.ufrj.br/bernardofpc">Bernardo da Costa</a> (UFRJ)</h2> <p><strong>Risk Budgeting Portfolios from Simulations </strong></p> <p>Les fonds de pension doivent poursuivre une strat茅gie<br /> d’investissement qui soit 脿 la fois prudente et 茅conomiquement<br /> rentable. Une strat茅gie de construction de tels portefeuilles est<br /> donn茅e par les portefeuilles 脿 “budget de risque” (Risk Budgeting<br /> Portfolios – RBP). Leur caract茅ristique principale est de diversifier<br /> selon la contribution de chaque actif au risque total du portefeuille.<br /> Ils sont donc id茅aux pour des fonds de pension qui sont soumis 脿 des<br /> contraintes d’investissement assez rigides.</p> <p>La plupart des techniques de construction pour de tels portefeuilles<br /> part de l’hypoth猫se (assez forte) que la rentabilit茅 des actifs est<br /> donn茅e par une variable al茅atoire Gaussienne multivari茅e. Apr猫s avoir<br /> introduit les concepts de mesure de risque utilis茅s, on pr茅sentera un<br /> probl猫me d’optimisation dont la solution permet de d茅duire le<br /> portefeuille d茅sir茅. Ensuite, on montrera quelques techniques<br /> d’optimisation stochastique qui permettent de construire des<br /> portefeuilles 脿 budget de risque d’apr猫s une distribution arbitraire<br /> des retours. Pour des mesures de risque coh茅rentes, comme l’AVAR, le<br /> mod猫le r茅sultant est convexe, ce qui permet une impl茅mentation tr猫s<br /> efficace, m锚me pour un nombre assez large de sc茅narios.</p> <h2><a href="https://aoustry.github.io/">Antoine Oustry</a> (LIX – CNRS)</h2> <p><strong>ACOPF: Nonsmooth optimization to improve the computation of SDP bounds</strong></p> <div>Antoine Oustry, joint work with Claudia D’Ambrosio (LIX-CNRS), Leo Liberti (LIX-CNRS) and Manuel Ruiz (RTE).</div> <div></div> <div>The Alternating-Current Optimal Power Flow (ACOPF) problem models the optimization of power dispatch in an AC electrical network.聽 In the quest for global optimality certificates, the semidefinite programming (SDP) relaxation of the ACOPF problem is a major asset since it is known to produce tight lower bounds. To improve the scalability of the SDP relaxation, state-of-the-art approaches exploit the sparse structure of the power grid by using a clique decomposition technique. Despite this advance, the clique-based SDP relaxation remains difficult to solve for large-scale instances: numerical instabilities may arise when solving this convex optimization problem. These difficulties cause two issues (i) inaccuracy and (ii) lack of <i>certification</i>.</div> <div></div> <div>We tackle both issues with an original approach. We reformulate the Lagrangian dual of the ACOPF, whose value equals the value of the SDP relaxation, as a concave maximization problem with the following properties: (i) it is unconstrained (ii) the objective function is partially separable. Based on this new formulation, we present how to obtain a certified lower bound from any dual vector, whether feasible or not in the classical dual SDP problem. Our new formulation is solved with a tailored polyhedral bundle method exploiting the structure of the problem. We use this algorithm as a post-processing step, after solving the SDP relaxation with the state-of-the-art commercial interior point solver MOSEK. For many instances from the PGLib-OPF library, this post-processing significantly reduces the computed optimality gap.</div> <h2><a href="https://sites.google.com/site/phamxuanhuyen/">Huyen Pham</a> (Paris-Diderot)</h2> <h3>December 16th, 10:30, Ecole Polytechnique (salle Jean Lascoux, rez de chauss茅e)</h3> <p><strong>Optimal bidding strategies for digital advertising</strong></p> <div>With the emergence of new online channels and information technology, digital advertising聽 tends to substitute more and more to traditional advertising by offering the opportunity to companies to</div> <div>target聽 the consumers/users that聽 are really interested by their products or services. We introduce a novel framework for the study of optimal bidding strategies associated to different types of advertising, namely, commercial advertising for triggering purchases or subscriptions, and social marketing for alerting population聽 about unhealthy behaviours (anti-drug, vaccination, road-safety campaigns). Our聽 continuous-time models are based on a common framework encoding users online behaviours via their web-browsing at random times, and the targeted advertising auction mechanism widely used on Internet,聽 the objective being聽 to efficiently diffuse advertising information by means of digital channels. Our main results are to provide semi-explicit formulas for the optimal value and bidding policy for each of these problems.</div> <div>We show聽 some sensitivity properties of the solution with respect to model parameters, and analyse how the different sources聽 of digital information聽 accessible to users including聽 the social interactions affect the optimal bid聽 for advertising auctions. We also study how to efficiently combine targeted adver\-tising and non-targeted advertising mechanisms. Finally, some聽 classes of examples with fully explicit formulas are derived.</div> <div></div> <div>Joint work with M茅d茅ric Motte (Universit茅 de Paris)</div> <h2><span style="text-decoration: underline">聽</span></h2> <h2><a href="https://www.oliveira.mat.br/">Welington de Oliveira</a> (ENSMP, Sophia-Antipolis) <a href="https://cermics-lab.enpc.fr/wp-content/uploads/2021/04/DC-WdeOliveira.pdf">Slides</a></h2> <h3>November 18th, 11:00, Ecole des Ponts (CERMICS Seminar room)</h3> <p><strong>Sequential Difference-of-Convex Programming</strong></p> <p>A function is called DC if it is expressible as the difference of two convex functions. In the first part of this talk, we present a short tutorial on DC programming and highlight important facts about DC functions and optimality conditions.</p> <p>Optimization methods for DC programs iteratively solve convex sub-problems to define iterates. Although convex, depending on the problem鈥檚 structure, these subproblems are very often challenging and require specialized solvers. In the second part of this talk, we will focus on a recent class of algorithms that defines iterates as approximate critical points of significantly easier DC subproblems approximating the original one. Several algorithms can be designed from the presented approach since there is considerable freedom to choose such more accessible subproblems. In some cases, the resulting algorithm boils down to a straightforward process with iterates given in an analytic form.</p> <p>This talk is based on the following two papers:</p> <p>W. de Oliveira<a href="https://www.google.com/url?q=https%3A%2F%2Frdcu.be%2Fb9oIq&sa=D&sntz=1&usg=AFQjCNGWQ5GEt0a13yyNWkzLoKHcXdtsJw" target="_blank" rel="noopener">聽The ABC of DC Programming.</a>聽Set-Valued and Variational Analysis, v. 28, pp. 679-706, 2020.</p> <p>W. de Oliveira.<a href="https://www.google.com/url?q=https%3A%2F%2Frdcu.be%2Fb55lQ&sa=D&sntz=1&usg=AFQjCNEXowl5jdvZqxqQK6uTz3itZsf-zQ" target="_blank" rel="noopener">聽Sequential Difference-of-Convex Programming</a>. Journal of Optimization Theory and Applications, v.186 (3), pp. 936-959, 2020.</p> <p> </p> <h3>Adrien Lefranc, CERMICS, Efficacity</h3> <h3>November 18th, 14:00, Ecole des Ponts (CERMICS Seminar room)</h3> <p><strong>Numerical methods in generalized convexity</strong></p> <div>We present potential applications of聽 the so-called one-sided linear couplings –<br /> a class that encompasses the Fenchel coupling of (standard) convex analysis.<br /> We start by extending the mirror descent algorithm. Then, turning to the Capra (constant along primal rays) coupling as a particular case, we provide explicit formulations for the Capra subdifferential of the l0 pseudonorm.<br /> Lastly, we discuss the difficulties that arise when trying to use Capra convexity to solve sparse optimization problems, and introduce some numerical perspectives.</div> <div>All-in-all, we contribute to an original viewpoint on sparse optimization, whose applications in statistics and signal processing have a huge impact on all engineering fields.</div> <h2><a href="https://www.ljll.math.upmc.fr/achdou/">Yves Achdou</a> (LJLL & INRIA, Paris)</h2> <h3>October 14st, 10:30, Ecole des Ponts (CERMICS Seminar room)</h3> <h3>Jeux 脿 champ moyen: un survol</h3> <ol> <li>La th茅orie des jeux 脿 champ moyen a 茅t茅 introduite en 2006 par JM. Lasry et PL. Lions pour d茅crire des jeux diff茅rentiels (茅quilibres de Nash) dans la limite o霉 le nombre de joueurs tend vers l’infini. Cette th茅orie a depuis connu un essor consid茅rable. Elle constitue un point de rencontre de plusieurs domaines des math茅matiques appliqu茅es: th茅orie des jeux, contr么le optimal d茅terministe ou stochastique, calcul des variations, transport optimal,聽 analyse des EDPs, m茅thodes num茅riques. Les applications sont nombreuses: 茅conomie, 茅tude des comportements collectifs avec anticipations rationnelles, etc…On tentera de聽 donner un aper莽u聽 de la th茅orie des jeux 脿 champ moyen, en insistant sur plusieurs aspects: La master equation est une 茅quation aux d茅riv茅es partielles non lin茅aire dont l’inconnue est une fonction agissant en particulier sur une mesure de probabilit茅. C’est donc une EDP pos茅e en dimension infinie. Elle聽 permet d’une part d’analyser le passage 脿 la limite quand le nombre d’agents tend vers l’infini, et est d’autre part incontournable quand les agents sont soumis 脿 un bruit commun. Quand l’espace des 茅tats est fini, la master equation est une 茅quation pos茅e en dimension finie mais possiblement grande, pour laquelle des simulations num茅riques sont parfois possibles.</li> <li>Dans les cas les plus simples, les trajectoires caract茅ristiques de la master equation sont obtenues en r茅solvant des syst猫mes d’EDPs forward-backward pos茅es dans l’espace des 茅tats. Il couplent une 茅quation de Hamilton-Jacobi donnant la strat茅gie des joueurs 脿 une 茅quation de Fokker-Planck permettant de caract茅riser l’茅volution de la distribution des 茅tats. L’analyse des ces syst猫mes d’EDPs a fait l’objet d’un important travail de recherche depuis quinze ans.</li> <li>Les solutions explicites ou semi-explicites des syst猫mes forward-backward 茅tant tr猫s rares, il est crucial, s’il on veut utiliser les jeux 脿 champ moyen 脿 des fins pr茅dictives, de disposer de m茅thodes num茅riques robustes. On pr茅sentera rapidement les sch茅mas aux diff茅rences finies utilis茅s, de sr茅sultats de convergence,聽 ainsi que des exemples de simulations dans des mod猫les de trafic ou de mouvement de pi茅tons.Si le temps le permet, on abordera des travaux en cours utilisant des r茅seaux de neurones profonds pour simuler num茅riquement des master equations en dimension grande.</li> </ol> <h2><a href="https://gdalle.github.io/">Guillaume Dalle</a> (CERMICS)</h2> <h3>October 14st, 14:30, Ecole des Ponts (CERMICS Seminar room)</h3> <h3>Understanding railway delay propagation through latent variable models <a href="https://cermics-lab.enpc.fr/wp-content/uploads/2021/04/dag.pdf">(slides)</a></h3> <p>Railway networks are very unstable systems: a single delay caused by an external incident can set off a chain reaction that ends up paralyzing an entire line. Unfortunately, we rarely have complete information about resource conflicts between trains, which makes delay propagation hard to predict. To overcome this issue, we introduce a new model based on a latent congestion variable, which lives on the network graph and evolves according to a Vector AutoRegressive process $X_t = \theta X_{t-1} + \varepsilon_t$.<br /> Since we only get partial and noisy observations of $X$, the estimation of $\theta$ can be challenging: depending on the density of traffic and the locality of propagation phenomena, how much information can we recover? We provide two complementary answers to this question: an information-theoretic minimax lower bound, and the non-asymptotic analysis of a specific sparse estimator. Combining both of them yields an optimal convergence rate for this statistical problem, which is validated on simulated data and put to the test on real railway logs.</p> <h2><a href="http://www.gpeyre.com/">Gabriel Peyr茅</a> (CNRS & Ecole Normale Sup茅rieure, Paris)</h2> <h3>July聽2nd, 10:30, Ecole Polytechnique (CMAP Seminar room)<br /> The seminar will also be聽accessible <a href="https://ecolepolytechnique.zoom.us/j/86971510687?pwd=c05UYVV5NkRuN1FaaGFIWXBUcHFqUT09">online</a></h3> <h2>Scaling Optimal Transport for High dimensional Learning</h2> <p>Abstract:<br /> Optimal transport (OT) has recently gained lot of interest in machine learning. It is a natural tool to compare in a geometrically faithful way probability distributions. It finds applications in both supervised learning (using geometric loss functions) and unsupervised learning (to perform generative model fitting). OT is however plagued by the curse of dimensionality, since it might require a number of samples which grows exponentially with the dimension. In this talk, I will explain how to leverage entropic regularization methods to define computationally efficient loss functions, approximating OT with a better sample complexity. More information and references can be found on the website of our book “<a href="https://optimaltransport.github.io/">Computational Optimal Transport</a>”</p> <h2>Eloise Berthier聽(INRIA & Ecole Normale Sup茅rieure, Paris)</h2> <h3>July聽2nd, 14:00, Ecole Polytechnique (Seminar room of CMAP)</h3> <h2>Max-Plus Linear Approximations for Deterministic Continuous-State Markov</h2> <p>Abstract :<br /> We consider deterministic continuous-state Markov decision processes<br /> (MDPs). We apply a max-plus linear method to approximate the value function<br /> with a specific dictionary of functions that leads to an adequate<br /> state-discretization of the MDP. This is more efficient than a direct<br /> discretization of the state space, typically intractable in high dimension. We<br /> propose a simple strategy to adapt the discretization to a problem instance,<br /> thus mitigating the curse of dimensionality. We provide numerical examples<br /> showing that the method works well on simple MDPs.</p> <h2>Ma毛l Forcier聽(CERMICS,聽聽Ecole des Ponts)</h2> <h3>July聽2nd, 14:45, Ecole Polytechnique (CMAP Seminar room)</h3> <h2>Multistage Stochastic Linear Programming and Polyhedral Geometry</h2> <p>Abstract:<br /> We show that the multistage linear problem (MSLP) with an arbitrary cost distribution is equivalent to a MSLP on a finite scenario tree.<br /> Indeed, be studying the polyhedral structure of MSLP, we show that the cost distribution can be replaced by a discrete cost distribution, taking the expected value of the cost at each cone of a normal fan.<br /> In particular, we show that the expected cost-to-go functions are polyhedral and affine on the cells of a chamber complex, which is independent<br /> of the cost distribution. This leads to new complexity results, showing that MSLP is fixed-parameter tractable.<br /> A dual approach in terms of fiber polyhedron is eventually presented to derive algorithms for two-time scale MSLP.</p> <p> </p> <h2><a href="https://www.comp.tmu.ac.jp/kzmurota/index.en.html">Kazuo Murota</a>聽(The Institute of Statistical Mathematics, Tokyo)</h2> <h3>May 20th, 10:00,聽<a href="https://ecolepolytechnique.zoom.us/j/89686045711?pwd=bGJTTWM2QU4wZHd5WG5VWTd3blJrdz09">Online</a></h3> <h2>Multiple exchange property of gross substitutes valuations<br /> with a proof by discrete convex analysis (<a href="https://cermics-lab.enpc.fr/wp-content/uploads/2021/04/2105ParisEXCweb.pdf">Slides</a>)</h2> <p>Abstract:<br /> Discrete convex analysis (DCA) offers a general framework of discrete optimization,<br /> combining the ideas from matroid theory and convex analysis.聽 It has found applications<br /> in many different areas including operations research, mathematical economics, and game<br /> theory. The interaction between DCA and mathematical economics was initiated by<br /> Danilov, Koshevoy, and Murota (2001), and accelerated by the crucial observation of Fujishige<br /> and Yang (2003) that M-natural-concavity is equivalent to the gross substitutes (GS) property<br /> of Kelso and Crawford (1982).</p> <p>In this talk we show how an old question in economics was settled with<br /> the DCA machinery. More concretely, we explain how the equivalence of the gross substitutes<br /> condition to the strong no complementarities (SNC) condition of Gul and Stacchetti<br /> (1999) can be proved with the use of the Fenchel-type duality theorem and the conjugacy<br /> theorem in DCA.<br /> The SNC condition means the multiple exchange property of a set function<br /> f, saying that, for two subsets X and Y and a subset I of X-Y, there exists a subset J<br /> of Y-X such that聽 f((X-I)+J) +f((Y-J)+I) is not smaller than f(X) + f(Y).</p> <p>This talk is intended to offer a glimpse at a technical interaction<br /> between DCA and economics.<br /> No preliminary knowledge of DCA is required.</p> <h2><a href="https://www.ceremade.dauphine.fr/~vigeral/indexenglish.html">Guillaume Vigeral</a>聽(Ceremade, Paris Dauphine)</h2> <h3>April 8th, 10:30,聽<a href="https://ecolepolytechnique.zoom.us/j/89686045711?pwd=bGJTTWM2QU4wZHd5WG5VWTd3blJrdz09">Online</a></h3> <h2>Structure of the sets of Nash equilibria of finite games; applications<br /> to the complexity of some decision problems in game theory (<a href="https://cermics-lab.enpc.fr/wp-content/uploads/2021/04/PresDecision2021.pdf">Slides</a>)</h2> <p>Abstract:<br /> The set of Nash equilibrium payoffs of a finite game is always non<br /> empty, compact and semialgebraic. We show that, for 3 players or more,<br /> the reverse also holds: given E a subset of R^N that is non empty,<br /> compact and semialgebraic, one constructs a finite N player game such<br /> that E is its set of equilibrium payoffs. Related results also holds<br /> when one consider only games with integral payoffs, or when the focus is<br /> on equilibria instead of equilibrium payoffs.<br /> We apply this result to understand the complexity class of some natural<br /> decision problems on finite games.</p> </div> <footer class="entry-meta"> </footer> </article> <div id="comments" class="comments-area"> <div class="wrapper-form-comments"> </div> </div> </div> </div> </div> <footer id="colophon" role="contentinfo"> <div class="site-info"> <center><a href="https://cermics-lab.enpc.fr/legal-notice/">Legal notice</a></center> </div> </footer> </div> <script type='text/javascript' src='https://cermics-lab.enpc.fr/wp-content/plugins/hal/js/cv-hal.js?ver=4.6.29'></script> <script type='text/javascript' src='https://cermics-lab.enpc.fr/wp-content/themes/zerogravity/js/navigation.js?ver=20140711'></script> <script type='text/javascript' src='https://cermics-lab.enpc.fr/wp-content/themes/zerogravity/js/zg-toggle-search.js?ver=1.9.3'></script> <script type='text/javascript' src='https://cermics-lab.enpc.fr/wp-includes/js/wp-embed.min.js?ver=4.6.29'></script> </body> </html>