Is $f(b) = \max\{c^T x \mid Ax\leq \sqrt{b} \}$ convex, concave, or is it not possible to say?

Solution 1:

Partial answer:

Suppose $f$ is well defined (that is, finite and a maximiser exists) on $[b_1,b_2]$, the convex hull of $b_1,b_2$. Then $f$ is concave on $[b_1,b_2]$. There are $x_1,x_2$ such that $f(b_k) = c^T x_k, Ax_k \le \sqrt{b_k}$.

Suppose $t \in [0,1]$. Then $A(tx_1+(1-t)x_2) \le t\sqrt{b_1}+(1-t)\sqrt{b_2} \le \sqrt{tb_1+(1-t)b_2}$ (componentwise) and so $f(tb_1+(1-t)b_2) \ge c^T(tx_1+(1-t)x_2)=tf(b_1)+(1-t)f(b_2)$.

Solution 2:

Claim: The function $f: \mathbb{R}_+ \rightarrow \mathbb{R}$ defined by $ f(b) = \max \{ c^T x \mid A x \leq b \} $ is concave.

Let's set up some notation. Let $\lambda \in [0,1]$ be given and consider $b_0, b_1 \in \mathbb{R}_+$. Let the convex combination be denoted by $b_\lambda = \lambda b_0 + (1-\lambda) b_1$. Let two (arbitrary) optimal solutions be denoted as $x_i \in \text{argmax} \{ c^T x \mid A x \leq b_i \}$ for $i =1,2$. Note that by construction, $f(b_0) = c^T x_0$ and $f(b_1) = c^T x_1$.

Lemma: The point $x_\lambda = \lambda x_0 + (1-\lambda) x_1$ satisfies the system of equations $A x_\lambda \leq \sqrt{b_\lambda}$.

Proof: Observe that \begin{align} A x_\lambda &= A(\lambda x_0 + (1-\lambda) x_1) &(\text{definition of $x_\lambda$}) \\ &= \lambda A x_0 + (1-\lambda) A x_1 &(\text{linearity}) \\ &\leq \lambda \sqrt{b_0} + (1-\lambda) \sqrt{b_1} &(\text{because $x_0$ and $x_1$ are feasible.}) \\ &\leq \sqrt{\lambda b_0 + (1-\lambda) b_1} &(\dagger)\\ &= \sqrt{b_\lambda} \enspace, \end{align} where the inequality $(\dagger)$ follows from the hint that you were given. $\blacksquare$

Now, we can proceed to prove the main claim.

Proof (of main claim): Observe that

\begin{align} f(b_\lambda) &= \max \{ c^T x \mid A x \leq b_\lambda \} \\ &\geq c^T x_\lambda &(\text{lemma above})\\ &= c^T (\lambda x_0 + (1-\lambda) x_1) &(\text{definition of $x_\lambda$})\\ &= \lambda c^T x_0 + (1-\lambda) c^T x_1 &(\text{linearity of the objective})\\ &= \lambda \cdot f(b_0) + (1-\lambda) \cdot f(b_1). &(\text{choice of $x_0$ and $x_1$})\\ \end{align}

Note that the proof extends to the setting where the objective is concave (as opposed to just linear).

EDIT

Here is how to deal with the issue of unboundedness of the linear program. Suppose that if $b$ yields an unbounded program (i.e. $\sup \{ c^T x \mid A x \leq \sqrt{b} \} = \infty$), we set $f(b) = - \infty$. This is perhaps counter-intuitive, but let me argue that this is the "right" thing to do. Suppose that $b_0, b_1 \in \mathbb{R}_+$ and $\lambda \in [0,1]$ are given, with $b_\lambda \triangleq \lambda b_0 + (1-\lambda) b_1$. We seek to show $f(b_\lambda) \geq \lambda f(b_0) + (1-\lambda) f(b_1)$. Suppose that $b_1$ yields an unbounded program so that $f(b_1) = -\infty$. Then, concavity follows as $$ \lambda f(b_0) + (1-\lambda) f(b_1) = - \infty \leq f(b_\lambda) $$ which holds regardless of the value of $f(b_\lambda)$.