0
$\begingroup$

$\mathbf{Question}$: Suppose we have $T\in \mathcal{R}^{p\times n},W\in \mathcal{R}^{p\times m}$ and $h\in \mathcal{R}^p$.

For $Q:\mathcal{R}^n \times \mathcal{R}^m \rightarrow \mathcal{R}\cup \{\pm\infty\}$ we have $Q(\xi,\eta)=\min\limits_y \{\eta^T y|Wy=h-T\xi,y\geq 0\}$.

Now, determine whether the function is convex, concave, or neither of the two in the following cases (and justify why):

1). For a fixed $\xi=\hat{\xi}$.

2). For a fixed $\eta=\hat{\eta}$ such that the polyhedral set $P=\{x|W^Tx\leq\hat{\eta}\}$ is nonempty.

3).$Q(\xi,\eta)$.

$\mathbf{Answer}$: For part (2), my claim is that $Q$ is convex, from the theorem:

$\textbf{Theorem}$: Given $A\in \mathcal{R}^{m\times n}$ and $c\in \mathcal{R}^n$, suppose that the polyhedral set $P:=\{u:A^Tu\leq c\}$ is non-empty. Then the function $\hat{\theta}=\min\limits_x \{c^Tx:Ax=\hat{b},x\geq 0\}$ is convex.

For (2) can such a reasoning be drawn directly from the theorem? Also for part (1), my gut feeling is telling me that its concave, and I tried proving my claim along the definition of an epigraph but am unable to make any progress..

$\textbf{Update on (1):}$ with @LinAlg's and @prubin's advice, since $\eta$ is not fixed, for $\lambda\in[0,1]$, $y\geq0$,

$$\min\limits_y\{f(y),f(y')\}\leq \lambda f(y)+(1-\lambda)f(y')\leq f(\lambda y+(1-\lambda)y')$$

$\forall y,y'$ in the domain of $f$. So it follows that $f$ is concave and quasi-concave. Thus, $Q(\hat{\xi},\eta)$ is concave.

$\textbf{End of update to (1)}$

Is this the right way about doing this? (clarification needed)

For (3), I have no clue as to how I can approach this, but a couple of my pals advised me that it may be neither concave nor convex.

Hence, some clarifications and hints with regards to the above questions will be deeply appreciated.

If there is a more intuitive way of approaching problems such as the above, I'll love to hear it too!

Thanks.

$\endgroup$
  • 1
    $\begingroup$ In your statement of the theorem, is $\hat{\theta}$ a function of $\hat{b}$? $\endgroup$ – prubin Apr 10 '18 at 15:22
  • 1
    $\begingroup$ For 1: the minimum of a set of linear functions is concave. $\endgroup$ – LinAlg Apr 10 '18 at 15:35
  • $\begingroup$ @prubin Yes. In fact, $\hat{\theta}$ is a function of $c$ and $\hat{b}$. $\endgroup$ – Stoner Apr 10 '18 at 16:07
  • $\begingroup$ @LinAlg Is there a way to show this with the definition of concavity? And to be precise, what does it mean when $\xi=\hat{\xi}$? Sorry but I am not too certain about this yet.. $\endgroup$ – Stoner Apr 10 '18 at 16:09
  • 1
    $\begingroup$ @Stoner absolutely, see math.stackexchange.com/questions/373229/… $\endgroup$ – LinAlg Apr 10 '18 at 16:15
1
$\begingroup$

In the theorem, $c$ is fixed, so $\hat{\theta}$ is a function of just $\hat{b}$. After mapping the notation of the theorem to the notation of your problem, you can get part 2 directly from the theorem by exploiting the fact that the composition of a convex function with a linear function is convex. (If you haven't seen that derived, the proof is straightforward from the definitions of linearity and convexity.)

$\endgroup$
  • $\begingroup$ Thank you for the clarification. And yes, I have the proof of the above. With regards to part (1), what does it mean to hold $\hat{b}$ constant? I am interpreting it as having the feasible set bounded, but am still unable to draw any conclusions from it.. $\endgroup$ – Stoner Apr 11 '18 at 1:01
  • 1
    $\begingroup$ For part 1, you are in geometric terms working with a fixed polyhedron and looking at the optimal value as a function of the the objective coefficients. If it helps, picture tilting the objective line in a 2-D problem (or the objective plane in a 3-D problem). $\endgroup$ – prubin Apr 11 '18 at 18:29
  • $\begingroup$ For part 3, I can suggest an approach that worked (more often than not) for me as a student. When I wasn't sure if a mathematical statement was true or false, and couldn't see an obvious proof, I would try to construct a counterexample. If I got one, the statement was false. If I failed after several attempt, I tried to identify a common cause for my failures. That common cause (if I could find it) might point to a key step in a proof of the statement's truth. $\endgroup$ – prubin Apr 11 '18 at 18:31
  • $\begingroup$ Awesome thanks for your feedback! I have also updated my post with my working for part (1). Do let me know if I am on the right track as I can't think of any other way to tackle this problem as of now.. $\endgroup$ – Stoner Apr 12 '18 at 7:00
  • $\begingroup$ Your function $f(y)$ is linear (so both convex and concave), but in any case it's a function of $y$, not $\eta$, so I'm not sure what it has to do with convexity of $Q(\xi, \cdot)$. $\endgroup$ – prubin Apr 12 '18 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.