Examine the dual problem

Introduction

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.

Install

bash


pip install dual

give it a try

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

Easy with Jupyter

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.