Maximization of a nonconvex bi-variate function

Question

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}

Answer 1

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