Find conjugate function

Question

$A\in R^{m\times n},\ rankA = m,\ f(y) -\text{ Convex function,} \ f:R^m\rightarrow R.$ Let $g(x) = f(Ax)$ Find $g^*(y)$.

Because$x\rightarrow Ax$ - Affine transformation $\implies g(x)$ - is convex as well.

Because $rank{A}=m \implies g:R^m \rightarrow R$.

Because $g(x)$ is convex upwards $-g(x)$ is convex downwards and has $sup$ (only one).

Let's notice that $<x,y> - g(x)$ is also convex downwards. $$k(x,y)=<x,y>-g(x)$$ $$k_x'(x,y)=\bar{y}-\nabla g(x)=\bar{y}- A^T\nabla f(Ax)=0$$ $$\nabla f(Ax) = (A^T)^{-1}y$$ $$g^*(y) = \sup_{R^m}{k(x,y)}=<x,y>-...$$

How can I precede starting from this moment?

Answer 1

Assuming that $n = m$, so that the inverse of $A^T$ exists, you can continue your derivation as $$ g^*(y) = \sup_{x} \left\{ \langle x, y \rangle - f(Ax) \right\} = \sup_{x} \left\{ \langle Ax, (A^T)^{-1} y \rangle - f(Ax) \right\} \\ = \sup_{z} \left\{ \langle z, (A^T)^{-1} y\rangle - f(z) \right\} = f^*((A^T)^{-1} y). $$

The key steps above are:

• Noting that $\langle x, y \rangle = \mathsf{tr}(x^T y) = \mathsf{tr}(x^T A^T (A^T)^{-1} y) = \langle Ax, (A^{T})^{-1} y\rangle$ (second equality).
• Since $A$ is full-rank, every $z \in \mathbb{R}^m$ can be written as $Ax$ for an appropriate $x$ (third equality).