Multiplier Stabilization Applied to Two-Stage Stochastic Programs

Clara Lage (1, 2, 3) , Claudia Sagastizábal (4) , Mikhail Solodov (5)

1 ENGIE E&P International [La Défense]
2 CES - Centre d'économie de la Sorbonne
3 UP1 - Université Paris 1 Panthéon-Sorbonne
4 IMECC - Instituto de Matemática, Estatística e Computação Científica [Brésil]
5 IMPA - Instituto Nacional de Matemática Pura e Aplicada

In many mathematical optimization applications dual variables are an important output of the solving process, due to their role as price signals. When dual solutions are not unique, different solvers or different computers, even different runs in the same computer if the problem is stochastic, often end up with different optimal multipliers. From the perspective of a decision maker, this variability makes the prices signals less reliable and, hence, less useful. We address this issue for a particular family of linear and quadratic programs by proposing a solution procedure that, among all possible optimal multipliers, systematically yields the one with the smallest norm. The approach, based on penalization techniques of nonlinear programming, amounts to a regularization in the dual of the original problem. As the penalty parameter tends to zero, convergence of the primal sequence and, more critically, of the dual is shown under natural assumptions. The methodology is illustrated on a battery of two-stage stochastic linear programs.

Dans de nombreuses applications d'optimisation mathématique, les variables doubles sont une sortie importante du processus de résolution, en raison de leur rôle en tant que signaux de prix. Lorsque les solutions doubles ne sont pas uniques, différents solveurs ou différents ordinateurs, même des exécutions différentes sur le même ordinateur si le problème est stochastique, se retrouvent souvent avec des multiplicateurs optimaux différents. Du point de vue d'un décideur, cette variabilité rend les signaux de prix moins fiables et donc moins utiles. Nous abordons ce problème pour une famille particulière de programmes linéaires et quadratiques en proposant une procédure de solution qui, parmi tous les multiplicateurs optimaux possibles, donne systématiquement celui avec la norme la plus petite. L'approche, basée sur des techniques de pénalisation de la programmation non linéaire, revient à une régularisation dans le dual du problème d'origine. Comme le paramètre de pénalité tend vers zéro, la convergence de la séquence primitive et, plus critique, du dual est montrée sous des hypothèses naturelles. La méthodologie est illustrée sur une batterie de programmes linéaires stochastiques en deux étapes.

Mots clés: Multiplier stability; Dual regularization; Penalty method; Stochastic programming; Two-stage stochastic programming; Empirical approximations

Mots clés: Stabilité multiplicateur; Régularisation double; Méthode de pénalité; Programmation stochastique; Programmation stochastique en deux étapes; Approximations empiriques

Domaines: Economies et finances; Optimisation et contrôle [math.OC]

Clara Lage, Claudia Sagastizábal, Mikhail Solodov. Multiplier Stabilization Applied to Two-Stage Stochastic Programs. 2020. ⟨halshs-02900862⟩