Bei der Optimierung für das ursprüngliche Problem (Hauptproblem) [Duales Problem](https://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AF%BE%E5%95%8F Sie können an% E9% A1% 8C denken.
Das doppelte Problem hat die folgenden wichtigen Eigenschaften:
Hier sind einige Beispiele für Haupt- und Doppelprobleme.
| Hauptproblem | Doppelproblem | |
| $ \min{~ c^T x} $ | $ \max{~ b^T y} $ | |
| $ A x \ge b $ | $ A^T y \le c $ | |
| $ x \ge 0 $ | $ y \ge 0 $ |
Ich habe ein Python3-Paket (dual) erstellt, mit dem Sie die dualen Probleme verschiedener Hauptprobleme leicht verstehen können.
bash
pip install dual
Schauen wir uns ein Beispiel an.
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
Es ist richtig.
Bei einem doppelten Problem wird es zum Hauptproblem.
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
Wenn Sie die Ungleichung der Einschränkungsbedingung in eine Gleichheit ändern, wird y zu einer freien Variablen.
bash
python -m dual << EOF
min c^T x
A x = b
x >= 0
EOF
>>>
max b^T y
A^T y <= c
Wenn x eine freie Variable ist, sind die Einschränkungen des dualen Problems gleich.
bash
python -m dual << EOF
min c^T x
A x >= b
EOF
>>>
max b^T y
A^T y = c
y >= 0
Machen wir es etwas kompliziert.
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
Wenn Sie ein doppeltes Problem auf die gleiche Weise angeben, kehrt es zum Hauptproblem zurück.
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
Sie können es leicht mit Jupyter [^ 1] tun. Als Vorbereitung importieren.
jupyter_notebook
import dual
Ich werde es versuchen.
jupyter_notebook
%%dual
min c^T x
A x >= b
x >= 0
>>>
max b^T y
A^T y <= c
y >= 0
das ist alles
[^ 1]: Ich verwende die Technik von Jupyters Trick 2.
Recommended Posts