$u(a,b)=\min(xa,yb)-a-b-f\max(a+b-k,0)$, $x,y,f,k$ are parameters. What condition for these parameters will result in a convex $u(a,b)$?
The answer is $\frac{xy}{x+y}-1\in(0,f)$
My attempt at arriving at the above:
$\min(xa,yb),\max(a+b-k),-a-b$ are all planes. In fact, even $\min(xa,yb)$ can be broken down into two separate planes $xa$ and $yb$. Same with the $\max$ term.
So the resulting convex polyhedron equation will be:
$\begin{bmatrix}1 & 1\\ -1 & -1\\ x & 0\\ 0 & y \end{bmatrix}\begin{bmatrix}a\\ b \end{bmatrix}\leq\begin{bmatrix}k\\ 0\\ 0\\ 0 \end{bmatrix}$
but this has no $f$ term which means I'm doing something wrong.
EDIT 1: The earlier polyhedron form was wrong:
Note that the $\max$ and $\min$ functions create a branching of sorts. They encapsulate 4 different planes into one form, i.e. every possibility of $\min,\max$ results in a plane. Those planes will be:
$xa-a-b-0=a(x-1)+b(-1)$
$yb-a-b-0=a(-1)+b(y-1)$
$xa-a-b-fa-fb+fk=a(x-1-f)+b(-1-f)+fk$
$yb-a-b-fa-fb+fk=a(-1-f)+b(y-1-f)+fk$
This can be written in polyhedron form as:
$\begin{bmatrix}x-1 & -1\\ -1 & y-1\\ x-1-f & -1-f\\ -1-f & y-1-f \end{bmatrix}\begin{bmatrix}a\\ b \end{bmatrix}\leq\begin{bmatrix}0\\ 0\\ -fk\\ -fk \end{bmatrix} $
But every polyhedron of form $Ax \leq B$ is by definition convex. So I'm not sure why there is even a condition as mentioned in this paper.
EDIT with code:
I wrote a matplotlib plotter with sliders to change $x,y,f,k$. I see that the function is always concave i.e the epigraph of the negative of the function is definitely convex. So, it seems the paper was wrong? Or am I misinterpreting it?
See snippet from paper below:
Attached code here:
from mpl_toolkits import mplot3d
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.widgets import Slider
import matplotlib
import time
import sys
import pdb
print(sys.version)
print(matplotlib.__version__)
# curve definition
def foo(a, b, x, y, f, k):
# print range for convexity
print(0, x * y/(x + y) - 1, f)
time.sleep(1)
return np.minimum(a*x,b*y) - a - b - f * np.maximum(a + b - k, 0)
# calculate x,y,z
x = np.linspace(-6, 6, 30)
y = np.linspace(-6, 6, 30)
X, Y = np.meshgrid(x, y)
Z = foo(X, Y, 0.1, 0.1, 2.0, 2.0)
# figure plot
fig = plt.figure()
ax = plt.axes(projection='3d')
l = ax.contour3D(X, Y, Z, 50, cmap='binary')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('z')
# figure slider for interactive update
def update(val):
global f
f = valf.val
k = valk.val
x = valx.val
y = valy.val
ax.cla()
ax.contour3D(X,Y,foo(X,Y, x,y,f,k), 50, cmap='binary')
plt.draw()
axcolor = 'lightgoldenrodyellow'
ax_slider_f = plt.axes([0.25, 0.1, 0.65, 0.03], facecolor=axcolor)
ax_slider_k = plt.axes([0.25, 0.15, 0.65, 0.03], facecolor=axcolor)
ax_slider_x = plt.axes([0.25, 0.20, 0.65, 0.03], facecolor=axcolor)
ax_slider_y = plt.axes([0.25, 0.25, 0.65, 0.03], facecolor=axcolor)
valk = Slider(ax_slider_k, 'k', 0, 30.0, valinit=0.1, valstep=0.001)
valf = Slider(ax_slider_f, 'f', 0, 30.0, valinit=0.1, valstep=0.001)
valx = Slider(ax_slider_x, 'x', 0, 30.0, valinit=0.1, valstep=0.001)
valy = Slider(ax_slider_y, 'y', 0, 30.0, valinit=0.1, valstep=0.001)
valk.on_changed(update)
valf.on_changed(update)
valx.on_changed(update)
valy.on_changed(update)
# invoke plot
plt.show()
EDIT (Using Strong duality to prove that original problem is convex):
First we need a primal form. Instead of maximizing u, we can maximize one of the halfplanes (since the apex must lie on all halfplanes) subject to the condition of the other halfspaces. This can be rewritten as an optimization of one of these planes subject to the other as constraints:
$\max-a-b=\begin{bmatrix}-1 & -1\end{bmatrix}\begin{bmatrix}a\\ b \end{bmatrix}$
$\text{s.t }\begin{bmatrix}x-1 & -1\\ -1 & y-1\\ x-1-f & -1-f\\ -1-f & y-1-f \end{bmatrix}\begin{bmatrix}a\\ b \end{bmatrix}\leq\begin{bmatrix}0\\ 0\\ -fk\\ -fk \end{bmatrix}$
The dual form of the above is:
$\min\begin{bmatrix}0 & 0 & -fk & -fk\end{bmatrix}\begin{bmatrix}e_{1}\\ e_{2}\\ e_{3}\\ e_{4} \end{bmatrix}$
$\text{s.t.}$
$\begin{bmatrix}x-1 & -1 & x-1-f & -1-f\\ -1 & y-1 & -1-f & y-1-f \end{bmatrix}\begin{bmatrix}e_{1}\\ e_{2}\\ e_{3}\\ e_{4} \end{bmatrix}=\begin{bmatrix}-1\\ -1 \end{bmatrix}$
$\begin{bmatrix}e_{1}\\ e_{2}\\ e_{3}\\ e_{4} \end{bmatrix}\geq[0]$
If strong duality can be proven i.e. if duality gap between dual and primal is zero, then the original primal problem must be convex.
The new dual problem has an affine objective function. So we can consider Slater's weak condition for strong duality, which allows us to set $e_{1}=e_{2}=0$ (also it doesn't affect the payoff function. so it's okay?):
$\begin{bmatrix}x-1-f & -1-f\\ -1-f & y-1-f \end{bmatrix}\begin{bmatrix}e_{3}\\ e_{4} \end{bmatrix}=\begin{bmatrix}-1\\ -1 \end{bmatrix}$
$e_{3}>0$
$e_{4}>0$
Solving this gives:
$\frac{xy}{x+y}<1+f$
I still don't understand if this chain of arguments are valid. I also tried other combinations of setting $e_i,e_j$ to zero but none to them lead to the lower bound i.e. $\frac{xy}{x+y} - 1 > 0$.
Taking the facts
$$ \min(a,b) = -\max(a,b)\\ \min(a,b)+c = \min(a+c,b+c) $$
we can transform
$$ u(a,b)=\min(xa,yb)-a-b-f\max(a+b-k,0) $$
into
$$ u(a,b) = \min((x-1)a-b- f k,(y-1)b-a- f k))+f\min(a+b,f k) $$
NOTE
The three involved planes have an intersection at
$$ \{a x = b y\} \cap \{a+b-k = 0\} $$
with coordinates
$$ a^* = \frac{k y}{x+y},\ \ b^* = \frac{k x}{x + y} $$
and
$$ u(a^*,b^*) = k\left(\frac{xy}{x+y}-1\right) $$
could this be the convex summit value? For this be true, the system
$$ \left\{ \begin{array}{rcl} (x-1)a^*-b^* - f k& \le & k\left(\frac{xy}{x+y}-1\right)\\ -a^*+(y-1)b^*- f k &\le & k\left(\frac{xy}{x+y}-1\right)\\ f a^* + f b^* &\le & k\left(\frac{xy}{x+y}-1\right)\\ f k \le k\left(\frac{xy}{x+y}-1\right) \end{array} \right. $$
should be feasible and clearly it is true under the conditions
$$ \left\{ \begin{array}{rcl} f k & \ge & 0\\ k(f + 1)& \le & k\frac{x y}{x+y} \end{array} \right. $$
Attached a plot showing the surface for the set of parameters:
$$ \{x = 2,\ y = 3, \ f = 1.6, \ k = 1\} $$
the summit is indicated by the red point.