4
$\begingroup$

Suppose we have a bi-variate function like $f(x,y)$ which is concave in $x$, $\frac{d^2f(x,y)}{dx^2} = -g(x,y)<0$ (that is $f(x,y)$ can be a function with high order in $x$ ) but convex in $y$, that is $\frac{d^2f(x,y)}{dy^2}>0$ which is a second-order polynomial function in $y$. Here, if we assume that $0\le y \le 1$, I am wondering how to determine the optimal solution of the objective function? Because the function is convex in $y$, is it possible to say that the optimal value of $y$ is either 0 or 1, and we can determine the optimal value of $x$ condition on $y=0,1$? Also, the objective function is always nonnegative for all values of decision variables.

If this approach is not correct, please recommend a method to solve the problem.

\begin{equation} \begin{split} \max_{x \in R, 0\le y\le 1} f(x,y) \end{split} \end{equation}

$\endgroup$
2
  • $\begingroup$ @SecretAgentMan, i find your most recent edit here unhelpful as it makes part of my answer superfluous. $\endgroup$ Sep 15 at 22:46
  • 1
    $\begingroup$ @worldsmithhelper Corrected! Thanks for calling me out. $\endgroup$ Sep 16 at 12:51
3
$\begingroup$

Concavity or convexity alone are not sufficient conditions to locate an extremum over an interval, as the function could be constant in some regions with regard to those variables. Strict concavity or strict convexity would be necessary to draw any conclusions. The mathematical condition you gave implies strict convexity and differntiability.

You are correct in that if you minimize a strictly concave function the minima are on the extrema of the interval and equivalent if you maximize a strictly convex function the maxima are at extrema of the interval.

For any fixed $x$ the maximizers of $h_x(y) = f(x,y)$ are either $\{0\}, \{1\}$ or $\{0,1\}$. Further $h_x(1), h_x(0)$ are both convex so $\max \{\max_x h_x(1),\max_x h_x(0)\}$ is the maxima.

For general non-convex optimization i would suggest looking into these methods.

  • Local optimization with restarts
  • Interval Newton method
  • Branch and Bound over a convex relaxation (such as McCormick envelopes) of your problem
$\endgroup$
5
  • $\begingroup$ Thanks for your response. So, since the objective function is strictly convex/concave in either of the variables, we can conclude the optimal value of $y$ is either 0 or 1. You mentioned "You are correct in that if you minimize a strictly concave function the minima are on the extrema of the interval and equivalent if you maximize a strictly convex function the maxima are at extrema of the interval". I am wondering if this is true for all functions either a function with a signle variable or multiple variables? Could you give some references or proof for this? $\endgroup$
    – Katatonia
    Sep 14 at 4:20
  • 1
    $\begingroup$ $\max\{ \max_{x}h_x(1), h_x(0) \}$ is the maximum or minimum? $\endgroup$
    – Katatonia
    Sep 14 at 4:20
  • 1
    $\begingroup$ Proof idea: Point is optimal if stationary points are the right kind of optima or if you are at a boundary (KKT) given the function smoothly differentiable everywhere. For the cases i mentioned above it is always the wrong kind. So optima must be at border. $\endgroup$ Sep 14 at 9:14
  • $\begingroup$ Is there any modification i need to make for you to be able to accept the answer? $\endgroup$ Sep 15 at 8:57
  • 1
    $\begingroup$ Ooo. I forgot to accept it as the answer. Done. Thank you so much $\endgroup$
    – Katatonia
    Sep 15 at 16:59

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.