University of Duisburg-Essen, NTNU, University of Hong Kong
Abstract
The research topic is Combinatorial Stochastic Optimization, which is at the crossroads between probability theory, discrete mathematics, graph theory, optimization and computer science. The project aims at developing new and fast methods for finding exact or approximate solutions to hard combinatorial stochastic optimization problems.
Stochastic programming problems are commonly solved using stochastic gradient methods which combine gradient approach and Monte Carlo simulation methods. Stochastic gradient methods convergence is generally slow and provides only approximated solutions. We propose to study new approaches for solving stochastic programming problems by using main ideas from interior point methods. This new topic needs advanced theoretical studies in order to propose new polynomial algorithms for stochastic optimization problems.
Context
Stochastic programming problems with continuous distributions have been solved by the well known stochastic gradient algorithm. In LRI/GraphComb team, we applied this algorithm to solve combinatorial stochastic problems, namely stochastic knapsack problems. As the majority of the gradient algorithms, the stochastic gradient one might have convergence difficulties. As far as we know, interior point algorithms have not been used so far. We propose in this thesis to study new variants for stochastic programming problems both from theoritical and empirical point of view.
Objectives
Our objectives in this projet are threefold:
1.Study new algorithms based on interior point methods for solving stochastic combinatorial optimization problems.
2. Application of such algorithms for solving semidefinite programming problems.
3. Derive tight bounds for combinatorial optimization problems.
Work program
The candidate will work on the approaches developed within GraphComb team, namely stochastic gradient methods with continuous distributions as well as the state of the art in stochastic programming. He will also work on interior point methods both for linear programming and their extension for semidefinite programming. This will make a bridge between stochastic programming and combinatorial optimization. The following stage will concern studies and proposal of new approaches for solving stochastic programming using interior point methods.
Extra information
Prerequisite
The candidate should have a strong background in optimization and computer science in general and more specifically in probability theory, statistics and optimization. Skills in object programming langages are appreciated.
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
Mr. Jianqiang Cheng, University of Shanghai, China.
Utilisateur
abdel.lisser
Créé
Lundi 22 mars 2010 15:03:27 CET
dernière modif.
Jeudi 10 mai 2012 09:59:38 CEST
Fichiers joints
filename
créé
hits
filesize
Aucun fichier joint à cette fiche
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit Assistante
Stéphanie Druetta Conseiller aux thèses
Dominique Gouyou-Beauchamps
ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr