Gradient of a function defined by a linear program

Question

Let

$$f(a) := \min_{x \in \mathbb{R}^n} \left\{ c^Tx : a^Tx \leq b \right\}$$

where $a, c, \in \mathbb{R}^n$ and $b \in \mathbb{R}$. How can I calculate $\nabla_a f(a)$?

Answer 1

Without loss of generality let $b = 0$ and $c^T c = 1$.

Say $x = \mu c - v$ with $c^T v = 0$. Then, $c^T x = \mu$. Thus, $c^T x$ is bounded from below, if $\mu$ is bounded from below.

1. Let $a = \lambda c + u$ with $c^T u = 0$, that is $\lambda = a^T c$.

2. If $\lambda \ge 0$, then we have $$ a^T (\mu c) = \lambda \mu \le 0 $$ for every $\mu < 0$. Thus, $\mu$ is unbound from below.

3. Assume $\lambda < 0$. Then, we have $$ a^T x = \mu a^T c - a^T v = \lambda \mu - u^T v \le 0$$ if and only if $$ \mu \ge \frac{u^T v}{\lambda}. $$ Thus, $\mu$ is bounded from below if and only if $u = 0$. In that case, we have $f(a) = 0$.

I leave you to compute the (directional) derivative.