4
$\begingroup$

Let $$\begin{array}{rcl} z(t) & := & \min (c+t d)^T x \\ & \text{s.t.} & Ax \le b \end{array}$$

Show that $Z(t)$ is a concave, piecewise linear function of $t$.

I'm really not sure how to even start proving this, I would really appreciate some hints.

  • 2
    What is $T$? What connection does the objective have with $x$ in the constraint?2012-12-29
  • 1
    Honestly, this is an exam question and no further information is given in the exercise. I am just guessing that everything is arbitrary. This is exactly how the exercise was written but I am thinking now that "T" is actually transpose ( and not a some other variable)2012-12-29
  • 2
    If you let $C=\{x|Ax\leq b\}$ and $\phi_x(t) = \langle c+td, x \rangle$, then you can write $z$ as $z(t) = \inf_{x \in C} \phi_x(t)$, the pointwise infimum of a collection of linear (hence concave) functions, which is concave. However, $z$ may 'easily' take the value $-\infty$.2012-12-30
  • 1
    So actually set C doesn't matter and it could be any any set that respects some sort of condition for x?2012-12-30
  • 1
    Well, for concavity, the set $C$ doesn't matter. I am still struggling with piecewise linearity.2012-12-30

1 Answers 1

1

$\newcommand\R{\mathbb R} $Let us start by associating with each $t\in\R$ a linear form $\omega_t$ with $\omega_t(x) = (c+td)^T x$. Denote by $\Omega\colon \R\to (\R^n)^*$ the map sending $t$ to $\omega_t$.

Now $z(t)$ is obtained by minimizing the linear form $\omega_t$ along the polyhedron $Q=\{\,x\in\R^n\,|\, Ax\le b\,\}$. I'll assume that $Q$ is bounded and hence a polytope, otherwise the minima defining $z$ might not exist. Convex geometry tells us, that $\omega_t$ will attain its minimum on a face of $Q$. This face is determined by the cone of the normal fan $\mathcal N(Q)$ that contains $\omega_t$.

If you take the subdivision of $(\R^n)^*$ given by the normal fan of $Q$ and pull it back to $\mathbb R$ along $\Omega$, you get a partition of $\R$ into intervals $I_1,\dots,I_k$ such that for all $t$ in a fixed $I_j$, all linear forms $\omega_t$ attain their minimum at the same face of $Q$. (Think of this as $\Omega$ embedding the real line into $(\R^n)^*$, where you intersect this line with the cones of the normal fan.) Hence, letting $x_0$ be some point on this face, you have $z(t) = \min_Q \omega_t(x) = \omega_t(x_0)$ for all $t\in I_j$. You can see that $\omega_t(x_0)$ is an (affine) linear function in $t$ and hence $z$ is a piecewise-linear function on $\R$ with linearity regions $I_1,\dots,I_k$.