The Multiplicative Weights Update Algorithm for Mixed Integer NonLinear Programming : Theory, Applications, and Limitations - Archive ouverte HAL Access content directly
Theses Year : 2017

The Multiplicative Weights Update Algorithm for Mixed Integer NonLinear Programming : Theory, Applications, and Limitations

L'Algorithme Multiplicative Weights Update pour la Programmation non linéaire en nombres entiers : Théorie, Applications et Limites

(1)
1

Abstract

This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5.
L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5.
Fichier principal
Vignette du fichier
58420_MENCARELLI_2017_archivage.pdf (2.7 Mo) Télécharger le fichier
Origin : Version validated by the jury (STAR)
Loading...

Dates and versions

tel-01784066 , version 1 (03-05-2018)

Identifiers

  • HAL Id : tel-01784066 , version 1

Cite

Luca Mencarelli. The Multiplicative Weights Update Algorithm for Mixed Integer NonLinear Programming : Theory, Applications, and Limitations. Optimization and Control [math.OC]. Université Paris-Saclay, 2017. English. ⟨NNT : 2017SACLX099⟩. ⟨tel-01784066⟩
176 View
652 Download

Share

Gmail Facebook Twitter LinkedIn More