Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is converting a maximization algorithm into a minimization one a matter of changing max to min?

Tags:

algorithm

This might come across as a silly question but I am curious to know if given a maximization algorithm and asked to get the dual (minimization version), it is just a matter of converting all max's into min's and doing other basic adjustments?

If yes, are there any problems where this would not be the case? If not, is there a good intuitive reason why this does not work?

like image 262
Legend Avatar asked Mar 04 '11 21:03

Legend


2 Answers

Yes, maximization and minimization problems are basically the same. The solution for max(f(x)) is the same as -min(-f(x)).

When searching game trees this relation is used for example to convert a minimax search into a negamax search. This has the advantage that instead of writing two functions, one for maximizing your score and another for minimizing the opponent's score, you write a single maximizing function but flip the sign of the result of the evaluation function when it's the other person's move.

like image 125
Mark Byers Avatar answered Oct 10 '22 20:10

Mark Byers


It depends on how your maximization algorithm works. Numerical algorithms that need gradients will probably do more than max and min, and other complexities can come up.

However, there is indeed a very easy fix. Maximizing a function f(a,b,c) is equivalent to minimizing -f(a,b,c). So just negate result of the function.

like image 20
luqui Avatar answered Oct 10 '22 20:10

luqui