0

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?

Sapphire
  • 661
  • This problem has no constraints, so the dual has no variables. It's just "maximize $p^$", where $p^$ is the fixed optimal value of the primal problem. – Michael Grant Aug 25 '15 at 16:16
  • @MichaelGrant Is there any example in which I can explicitly plot out the primal and dual on the $x,y$-plane? I'm expecting something where the minimum of the (convex) primal problem intersects the maximum of the (concave) dual problem (assuming strong duality here). – Sapphire Aug 25 '15 at 16:36
  • 1
    That would not be as insightful as you think, because the primal and dual variables live in entirely different spaces. It doesn't really make sense for them to appear on the same plot. – Michael Grant Aug 25 '15 at 16:39
  • I think Bertsekas offers some visual representations of duality in his textbook on convex optimization. – Michael Grant Aug 25 '15 at 16:39

1 Answers1

0

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\}.$$

Community
  • 1
zoli
  • 20,452
  • Thanks for the explanation. Actually, I was looking for a way to represent both the primal and dual problem in the same plot for visualization purposes. But as Michael Grant mentioned, that doesn't make sense. – Sapphire Aug 25 '15 at 17:04
  • @Sappire: Thank you for accepting my nonsensical solution. Important is that we are having fun! – zoli Aug 25 '15 at 17:09