Let $f(x,y)$ be a function defined on $[0,1]^2$ and define \begin{align} g(a,b) = f\left(\frac{a+b}{2}, \frac{a-b}{2}\right) \end{align} where $a$ and $b$ are such that $\frac{a+b}{2} \in[0,1]$ and $\frac{a-b} {2}\in[0,1]$. Suppose $g(a,b)$ is convex in $a$ for fixed $b$ and concave in $b$ for fixed $a$.

I am trying to solve the optimization problem \begin{align} \begin{array}{ll} \text{maximize} & \sum_{i} \alpha_i f(x_i,y_i)\\ \text{s.t.} & \sum_{i} \alpha_i x_i = \epsilon\\ & \sum_{i} \alpha_i y_i = \epsilon\\ & \sum_{i} \alpha_i = 1 \end{array} \end{align} for $\epsilon\in[0,1]$, where the maximization is over $\alpha_i\in[0,1]$, $x_i\in[0,1]$, and $y_i\in[0,1]$ for $i\in\{1,2,3\}$.

Intuitively, it seems that the solution must be $\epsilon f(1,1) + (1-\epsilon)f(0,0)$, i.e., it involves only the extreme points $(0,0)$ and $(1,1)$. But I have not been able to come up with an argument supporting the intuition.

One example where this is satisfied: if $f(x,y)=x y$, then $g(a,b)$ is convex in $a$ and concave in $b$. The solution to the above optimization problem is then \begin{align} \sum_i \alpha_i f(x_i,y_i) = \sum_i \alpha_i x_i y_i \leq \sum_i \alpha_i x_i\leq \epsilon = \epsilon f(1,1) + (1-\epsilon)f(0,0). \end{align}


Your Answer

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

Browse other questions tagged or ask your own question.