0

Show that if $ \ f \ $ is a convex function then so is $ \ \ g(x)=f(Ax-b) $ , where A is $ n \times n $ matrix and b is a $ n \times 1 $ vector . Next show that if $\hat{x} $ minimizes g(x) then $ \hat{x}+w $ also minimizes g(x) , for all $ w \in null(A) $. $$ $$ We know that a function f is said to convex if for any two points x,y , we have \begin{align} f(\lambda x+(1-\lambda y) \leq \lambda f(x)+(1-\lambda) f(y) \end{align} . But then how to proceed ? Any help is apreciated .

MAS
  • 10,638
  • 1
    Did you try the obvious thing first, show that $g(\hat x + w)\le g(x)$ for all $x$? If this doesn't go well, then the next thing to try usually is proof by contradiction. – Chee Han Apr 20 '17 at 06:08

2 Answers2

3

You can just use the definition $$\begin{align}g(\lambda x+(1-\lambda)y)&=f(A(\lambda x+(1-\lambda)y)+b)=f(\lambda (Ax+b)+(1-\lambda)(Ay+b))\\&\le\lambda f(Ax+b)+(1-\lambda)f(Ay+b)=\lambda g(x)+(1-\lambda)g(y).\end{align}$$

Eclipse Sun
  • 9,338
  • 21
  • 44
0

Since $b=\lambda b+(1-\lambda)b$ we have $g(\lambda x+(1-\lambda)y)=f(A(\lambda x+(1-\lambda)y)-b)=f(\lambda (Ax-b)+(1-\lambda)(Ay-b))\leq \lambda f(Ax-b)+(1-\lambda)f(Ay-b)=\lambda g(x)+(1-\lambda)g(y).$

Minz
  • 1,254
  • would you help me doing the next part of the question ? – MAS Apr 20 '17 at 06:04
  • what you mean? If any $x_0$ minimizes convex $f$ then no other point can minimize the same $f$. – Minz Apr 20 '17 at 06:12
  • yes the question says it can for $x_{0}+w $ , if $ w \in null(A) \ $ . But I can not prove this. Any Idea please – MAS Apr 20 '17 at 06:19
  • This is evident because $A(x_0+w)=Ax_0$ whenever $Aw=0.$ My previous comment was about strictly convex function. – Minz Apr 20 '17 at 06:46