0
$\begingroup$

Let the objective be to maximize the sum of $f_i(x_i)$ where all $f_i$ are strictly increasing convex functions. Maximizing a convex function is hard as a local maximum might not be a global one. However for the special case described above, since $f_i$ are strictly increasing, from what I understand, the local maximum should be the global one.

If so, are there any special techniques that can optimize the objective (or maybe a piecewise approximation of it) subject to linear inequality constraints quickly?

Thanks

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ If all $f_i$ are strictly convex then a local maximum must be the global maximum. If all $f_i$ are strictly increasing then the maximum is unbounded. To maximize you would have to set $x_i=\infty$ for all $x_i$. $\endgroup$
    – James King
    Commented Sep 19, 2011 at 10:00
  • 1
    $\begingroup$ @James - The OP asked for maximizing w/ respect to linear inequality constraints. $\endgroup$
    – Opt
    Commented Sep 19, 2011 at 21:07
  • $\begingroup$ Note: for a CONVEX function f_i, the local minimum would be the same as the global minimum. This is not true because you want to MAXIMIZE the sum of f_i(x_i). BTW, exactly the reverse would be true if f_i were concave, i.e., maximization would be easy, but minimization would be hard. $\endgroup$
    – user8040
    Commented Jan 20, 2012 at 17:17
  • $\begingroup$ Use the Lagrange multiplier, you'll solve a similar problem with the same results. $\endgroup$
    – luke14free
    Commented Jan 23, 2012 at 8:18
  • $\begingroup$ Local maxima are not necessarily the global maximum in your situation. For example, consider maximizing 2x^2+y^2 subject to x+y≤1, x≥0, y≥0. Point (1,0) is a local maximum but not the global maximum. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 25, 2012 at 1:25

1 Answer 1

Reset to default
1
$\begingroup$

I'm sorry I don't fully understand the question, but if the point is to find the maximum, considering the local maximum is the global, then any gradient based method is going to take you directly to it. For instance artificial neural networks (gradient backpropagation).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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