0

How can I prove the convexity and show $x$ is a subgradient of $f$ at $y$??

Let $S$ be a nonempty, bounded convex set in $\mathbb{R}^n$, and let $f: \mathbb{R}^n \to \mathbb{R}$ be defined as: $ f(y)=sup_{x \in S}{ \ y^t*x}.$

Prove that $f$ is convex and show that if $f(y) = y^t*x$, where $x \in S$, $x$ is a subgradient of $f$ at $y$.

Chickenmancer
  • 4,347
iemuzo
  • 1
  • 4

1 Answers1

1

If $f_\alpha$ is convex for all $\alpha$ then $f=\sup_\alpha f_\alpha$ is convex. This can be proved directly or by noting that the epigraph of $f$ is the intersection of the epigraphs of $f_\alpha$.

Since each $y \mapsto y^T x$ is convex (in fact linear) it follows that $y \mapsto \sup_{x\in S} y^T x$ is convex. (This has nothing to do with the convexity of $S$.)

Suppose $f(y) = y^T x$ with $x \in S$. Note that $f(y+h) \ge (y+h)^T x$ for all $h$.

Then we have $f(y+h) -f(y) \ge (y+h)^T x-y^T x = h^T x$ for all $h$, hence $x \in \partial f(y)$.

copper.hat
  • 172,524
  • Why each $y \mapsto y^T x$ is convex? – user441848 Jan 01 '18 at 19:42
  • @Anneliset.: Any linear (or affine) function is convex. It is also straightforward to check from the definition of convexity or note that the second derivative is $0$ which is positive semi definite. – copper.hat Jan 01 '18 at 19:44
  • I see and why $f(y+h) \ge (y+h)^T x,$ for all $h$? why did you change $=$ by $\ge?$ – user441848 Jan 01 '18 at 19:56
  • @Anneliset.: There is a nice duality with the nearest point to a compact convex set and the support function: $\min_{|y| \le 1} \max_{x \in S} y^T x =\max_{x \in S} \min_{|y| \le 1} y^T x = - \min_{x \in S} |x|$. – copper.hat Jan 01 '18 at 20:22
  • I don't get it, we need to show that $x$ is a subgradient , so we need to find the $\ge$, I think you shouldn't write $f(y+h) \ge (y+h)^T x$ but $f(y+h) = (y+h)^T x$. And for your information I already took a break for the new year – user441848 Jan 01 '18 at 20:31
  • @Anneliset.: Sorry, I deleted a comment that was incorrect. What is meant by the question is that if $f(y) = y^T x$ for $x \in S$ (that is, $x$ is a maximiser) then $x$ is a subgradient. So we have $f(y+h) \ge (y+h)^T x$ (by definition of the support function and $f(y) = y^T x$ by assumption. Subtracting gives the required relationship that $f$ and a subgradient must satisfy. – copper.hat Jan 01 '18 at 20:34
  • @Anneliset. The function $f$ is not linear. – copper.hat Jan 01 '18 at 20:36
  • But why are you using the definition of support function? For the second question, i.e. to prove $x$ is a subgradient of $f$, $f$ is defined only as $f(y)=y^tx?$ – user441848 Jan 01 '18 at 20:44
  • @Anneliset.: No, the question is to show that for some $y$ if there is some $x$ such that $f(y) = y^Tx$ then $x \in \partial f(y)$. The question is poorly worded (it confused me earlier which is why I added an incorrect comment). – copper.hat Jan 01 '18 at 20:46
  • okay, I think I understand now, thanks. – user441848 Jan 01 '18 at 20:58
  • Sorry, then why is there a hypothesis $S$ is convex? It does not look like it is necessary. Thanks. – 10understanding Sep 19 '20 at 17:02
  • @10understanding You would have to ask the OP that, I have no idea why. – copper.hat Sep 19 '20 at 17:16
  • @copper.hat The problem is also in the Bazaraa book, stated the same way. I was actually not just asking you, but the author/problem itself and all of us involved haha xD – 10understanding Sep 19 '20 at 17:31