Dual problem of piecewise linear function

920 Views Asked by At

I would like to see the geometric interpretation of the relationship between the primal problem and the dual problem on the $x,y$-plane. So I am looking at an example of minimizing the maximum of some linear functions. Say,

$$\min\max\{-2x-6,\,-0.2x+0.5,\,x+3\}.$$

So how to go about constructing the corresponding dual problem?

1

There are 1 best solutions below

2
On BEST ANSWER

I am not sure that my answer answers your question. So, pls. be forgiving.

I've made up a game:

You choose a number between, say, $-4$ and $0$ and then I choose a function among those you listed. Then we plug your number into my function and the result will be my gain (your loss).

The figure below depicts the three functions:

enter image description here

The thick line shows the maximum of the three functions at any $x$.

What number would you choose? You would certainly choose the number belonging to the crossing point of the yellow line and the purple line. In that case my gain (your loss) is minimal. Any other number (between $-4$ and $0$) would lead to a higher gain for me. So, your strategy has to be selecting the number that minimizes the maximum of your functions.

There is another game we can play with the same functions:

You choose a function now. And then I choose a number. Which function would you choose?

You would certainly chose the purple function and I would choose the value $-4$. That would provide me the highest gain assuming that you choose the purple function. Any other choice would be worse for you.

So, in the case of this "dual" game you have to compute the maximums of the the functions over our interval and then you will choose the minimum of these maximums:

Your choice is

$$\min_f \{\max_{[-4,0]}(-2x-6),\max_{[-4,0]}(x+3),\max_{[-4,0]}(-0.2x+0.5)\}.$$

Perhaps this is the dual of

$$\min_{[-4,0]}\max_f\{-2x-6,\,-0.2x+0.5,\,x+3\}.$$