Consider a convex set $S ⊆ ℝ^n$ and an affine function $f(x)=Ax+b$. Then if the image of $S$ under $f$,$f(S)$={$f(x)|x \in S$} , is convex. Then the inverse image of the convex set C,$f^{-1}(C)=\{x|f(x) \in C$}, is convex set.
Hint:Let $y_1$ and $y_2 \in C.$Then there exist $x_1$ and $x_2 \in f^{-1}(C) $.Show that $f^{-1}(C)$ is convex.

How to prove the inverse of affine convex function is still a function?Because for me,i intuitively think the inverse image of the convex is still a convex.

My proof is as below,i am not sure whether it is right or not

For two elements of the preimage $x_1,x_2\in f^{-1}(C)$ and $t\in[0,1]$, you have to show that $tx_1+(1-t)x_2\in f^{-1}(C)$, i.e. that there exists an element $y\in C$, such that $tx_1+(1-t)x_2=f(y)$.

Since $x_1,x_2\in f^{-1}(C)$ there exist $y_1,y_2\in C$, such that $f(y_1)=x_1,f(y_2)=x_2$. Now use the definition of $f$ to find $y$ and you are done.

So \begin{align} f(tx_1+(1-t)x_2) &=A(tx_1+(1-t)x_2)+b\\ & = t(Ax_1+b)+(1-t)(Ax_2+b)\\ & = tf(x_1)+(1-t)f(x_2)\\ & = f(y) \end{align} And the question said $f(x)$ is a convex,that is,$f(tx_1+(1-t)x_2)$ is convex,so $f(y)$ is convex,that is $f^{-1}(C) $ is convex

Is this proof right?

  • $\begingroup$ If you wish to show curly braces $\{ \ldots \}$ when using MathJax, you can use \{ and \}. $\endgroup$ – Theo Bendit Oct 25 '18 at 7:26
  • $\begingroup$ You don't need $f$ to have an inverse. The inverse image $f^{-1}(S)$ is defined, regardless of whether $f$ is invertible, to be the set of points $x$ such that $f(x) \in S$. For example, if $f : \mathbb{R} \to \mathbb{R}$ is constantly $y$, then $f^{-1}(S)$ will either be $\emptyset$ if $y \notin S$ or $\mathbb{R}$ if $y \in S$. Note that $f^{-1}$ is not a function, as $f$ is very far from being one-to-one! $\endgroup$ – Theo Bendit Oct 25 '18 at 7:29
  • $\begingroup$ @TheoBendit so the proof if this doesn't have relation with $f(x)=Ax+b$?i just said that there exist s $x_1$ and $x_2 \in C$,and C is convex set,so the $f^{-1}(C)$ must be convex too? $\endgroup$ – electronic component Oct 25 '18 at 7:57
  • $\begingroup$ It does relate to $f$, but it doesn't require there to be a function $f^{-1}$. I may have misunderstood your issue with this question, but you seemed to be interested in showing $f^{-1}$ is still a function (which, in general, it won't be). $\endgroup$ – Theo Bendit Oct 25 '18 at 8:00
  • $\begingroup$ not quite. My hint was a bit misleading and there was some mixup with $y$ and $x$, i finished it up in my answer. $\endgroup$ – weee Oct 26 '18 at 20:42

For two elements of the preimage $x_1,x_2\in f^{-1}(C)$ and $t\in[0,1]$, you have to show that $tx_1+(1-t)x_2\in f^{-1}(C)$, i.e. that $f(tx_1+(1-t)x_2)\in C$. ($S$ is convex so $tx_1+(1-t)x_2\in S$ and we can apply $f$)

Since $x_1,x_2\in f^{-1}(C)$ we have $f(x_1)\in C,f(x_2)\in C$.

Edit: to finish up, we calculate \begin{align} f(tx_1+(1-t)x_2)&=A(tx_1+(1-t)x_2)+b\\ &=t(Ax_1+b)+(1-t)(Ax_2+b)\\ &=tf(x_1)+(1-t)f(x_2). \end{align} Since $C$ is convex, and $f(x_1)\in C,f(x_2)\in C$ we have also $tf(x_1)+(1-t)f(x_2)\in C$ and are done.

  • $\begingroup$ the definition of $f$ is $Ax+b$,but how can we find $y$ by using this function?how do you know the $f(y_1)=x_1 $ and $f(y_2)=x_2$ from the $tx_1+(1-t)x_2=f(y)$? $\endgroup$ – electronic component Oct 26 '18 at 2:02

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.