Examiner le double problème

Introduction

Dans l'optimisation, pour le problème d'origine (problème principal), [Double problème](https://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AF%BE%E5%95%8F Vous pouvez penser à% E9% A1% 8C).

Le double problème a les propriétés importantes suivantes:

--Si l'un ou l'autre a la solution optimale, les deux ont la solution optimale et les valeurs optimales correspondent. «Le double problème du double problème est le problème principal.

  • Le théorème de dualité tient. (Référence: wikipedia)

Voici quelques exemples de problèmes principaux et doubles.

Problème principal Double problème
$ \min{~ c^T x} $$ \max{~ b^T y} $
$ A x \ge b $$ A^T y \le c $
$ x \ge 0 $$ y \ge 0 $

J'ai créé un package Python3 (dual) qui vous permet de comprendre le double problème de divers problèmes principaux, je vais donc les présenter.

Installation

bash


pip install dual

essayez-le

Regardons un exemple.

bash


python -m dual << EOF
min c^T x
A x >= b
x >= 0
EOF
>>>
max b^T y
A^T y <= c
y >= 0

C'est juste.

Face à un double problème, cela devient le problème principal.

bash


python -m dual << EOF
max b^T y
A^T y <= c
y >= 0
EOF
>>>
min c^T x
A x >= b
x >= 0

Si vous modifiez l'inégalité de la condition de contrainte en une égalité, y devient une variable libre.

bash


python -m dual << EOF
min c^T x
A x = b
x >= 0
EOF
>>>
max b^T y
A^T y <= c

Si x est une variable libre, les contraintes du problème dual sont égales.

bash


python -m dual << EOF
min c^T x
A x >= b
EOF
>>>
max b^T y
A^T y = c
y >= 0

Rendons les choses un peu compliquées.

bash


python -m dual << EOF
min c^T x + d^T z
A x - P z >= b
Q z <= f
x >= 0
EOF
>>>
max b^T y - f^T w
A^T y <= c
- P^T y - Q^T w = d
y >= 0
w >= 0

Si vous donnez un double problème de la même manière, il reviendra au problème principal.

bash


python -m dual << EOF
max b^T y - f^T w
A^T y <= c
- P^T y - Q^T w = d
y >= 0
w >= 0
EOF
>>>
min c^T x + d^T z
-Q z >= -f
A x - P z >= b
x >= 0

Facile avec Jupyter

Vous pouvez facilement le faire avec Jupyter [^ 1]. Importez comme préparation.

jupyter_notebook


import dual

Je vais essayer.

jupyter_notebook


%%dual
min c^T x
A x >= b
x >= 0
>>>
max b^T y
A^T y <= c
y >= 0

c'est tout

[^ 1]: J'utilise la technique de l'astuce de Jupyter 2.

Recommended Posts