An exact dynamic programming algorithm, lower and upper bounds, applied to the large block sale problem - Laboratoire Interdisciplinaire des Sciences du Numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

An exact dynamic programming algorithm, lower and upper bounds, applied to the large block sale problem

Résumé

In this article, we address a class of non convex, integer, non linear mathematical programs using dynamic programming. The mathematical program considered, whose properties are studied in this article, may be used to model the optimal liquidation problem of a single asset portfolio, held in a very large quantity, in a low volatility and perfect memory market, with few market participants. In this context, the Portfolio Manager's selling actions convey information to market participants, which in turn lower bid prices and further penalize the liquidation proceeds we attempt to maximize. We show the problem can be solved exactly using Dynamic Programming (DP) in polynomial time. However, exact resolution is only efficient for small instances. For medium size and large instances, we introduce dedicated heuristics which provide thin admissible solutions, hence tight lower bounds for the initial problem. We also benchmark them against a commercial solver, such as LocalSolver [7]. We are also interested in the continuously relaxed problem, which is non convex. Firstly, we use continuous solutions, obtained by free solver NLopt [26] and transform them into thin admissible solutions of the discrete problem. Secondly, we provide, under some convexity assumptions, an upper bound for the continuous relaxation, and hence for the initial (integer) problem. Numerical experiments confirm the quality of proposed heuristics (lower bounds), which often reach the optimal, or prove very tight, for small and medium size instances, with a very fast CPU time. Our upper bound, however, is not tight.
Fichier principal
Vignette du fichier
articleDPMain_V3.pdf (268.89 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03501803 , version 1 (23-12-2021)

Licence

Paternité

Identifiants

Citer

David Nizard, Nicolas Dupin, Dominique Quadri. An exact dynamic programming algorithm, lower and upper bounds, applied to the large block sale problem. 2021. ⟨hal-03501803⟩
53 Consultations
234 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More