In the optimization, for the original problem (main problem), [Duality problem](https://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AF%BE%E5%95%8F You can think of something like% E9% A1% 8C).
The dual problem has the following important properties:
--If either has the optimal solution, both have the optimal solution and the optimal values match. --The dual problem of the dual problem is the main problem. --The dual theorem holds. (Reference: wikipedia)
Here are some examples of the main problem and the dual problem.
| Main problem | Dual problem | |
| $ \min{~ c^T x} $ | $ \max{~ b^T y} $ | |
| $ A x \ge b $ | $ A^T y \le c $ | |
| $ x \ge 0 $ | $ y \ge 0 $ |
I have created a Python3 package (dual) that allows you to understand the dual problems of various main problems, so I will introduce them.
bash
pip install dual
Let's look at an example.
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
It's right.
Giving a dual problem makes it the main problem.
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
If you change the constraint inequality sign to an equal sign, y becomes a free variable.
bash
python -m dual << EOF
min c^T x
A x = b
x >= 0
EOF
>>>
max b^T y
A^T y <= c
If x is a free variable, the constraints of the dual problem are equal signs.
bash
python -m dual << EOF
min c^T x
A x >= b
EOF
>>>
max b^T y
A^T y = c
y >= 0
Let's make it a little complicated.
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
If you give a dual problem in the same way, it will return to the main problem.
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
You can easily do it with Jupyter [^ 1]. Import as a preparation.
jupyter_notebook
import dual
I will try it.
jupyter_notebook
%%dual
min c^T x
A x >= b
x >= 0
>>>
max b^T y
A^T y <= c
y >= 0
that's all
[^ 1]: I am using the technique of Jupyter's trick 2.
Recommended Posts