Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

Let z(t) = min $(c+t d)^T x$ s.t $Ax <= b$ 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.

share|improve this question
1  
What is $T$? What connection does the objective have with $x$ in the constraint? – copper.hat Dec 29 '12 at 21:54
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) – bubbly Dec 29 '12 at 22:12
1  
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$. – copper.hat Dec 30 '12 at 8:06
So actually set C doesn't matter and it could be any any set that respects some sort of condition for x? – bubbly Dec 30 '12 at 9:30
Well, for concavity, the set $C$ doesn't matter. I am still struggling with piecewise linearity. – copper.hat Dec 30 '12 at 9:33

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.