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?


  • 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 Sep 19 '11 at 10:00
  • 1
    $\begingroup$ @James - The OP asked for maximizing w/ respect to linear inequality constraints. $\endgroup$ – Opt Sep 19 '11 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 Jan 20 '12 at 17:17
  • $\begingroup$ Use the Lagrange multiplier, you'll solve a similar problem with the same results. $\endgroup$ – luke14free Jan 23 '12 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 Jan 25 '12 at 1:25

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).

| cite | improve this answer | |

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.