0
$\begingroup$

If a minimization task is a convex optimization problem, is the maximization of the same objective function also always a convex optimization problem?

My guess is yes since minimization of the negative of the objective function is maximization, but wondering if there are cases that outdo, and disprove, this sign 'trick'

$\endgroup$
2
  • 1
    $\begingroup$ Note that the "negative" of a convex function will not usually be convex (because changing signs reverses the direction of the inequality). $\endgroup$ – hardmath Sep 11 '20 at 0:01
  • 1
    $\begingroup$ No. In fact very often the minimization task is convex ("easy" to solve) while maximization is computationally extremely hard. $\endgroup$ – Michal Adamaszek Sep 11 '20 at 6:41
2
$\begingroup$

$$\min x^2,$$$$ -1 \le x \le 1$$ is convex.

If you consider $$\max x^2 ,$$$$ -1 \le x\le 1,$$

It is clearly not convex, in particular, it attains the maximum at the boundary but if we interpolate it, we do not get an optimal solution in between.

$\endgroup$
8
  • $\begingroup$ can you provide an example that doesn't impose constraints on the decision variable $x$ $\endgroup$ – develarist Oct 14 '20 at 17:08
  • $\begingroup$ just remove the constraint then, that would give you an example. $\endgroup$ – Siong Thye Goh Oct 14 '20 at 17:21
  • $\begingroup$ but min $x^2$ and max $x^2$ would both be convex functions, which changes the validity of your answer $\endgroup$ – develarist Oct 14 '20 at 17:28
  • $\begingroup$ $\max x^2 = - \min (-x^2)$, check that $-x^2$ is not convex. $\endgroup$ – Siong Thye Goh Oct 14 '20 at 17:29
  • $\begingroup$ does $-$min$(-x^2)$ = min $x^2$? $\endgroup$ – develarist Oct 14 '20 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.