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