Proof of convex conjugate identity

[Zerox5f3759df]

Homework Statement

Prove that the conjugate of $g(x) = f(Ax + b)$ is $g^*(y) = f^*(A^{-T}y) - b^TA^{-T}y$ where A is nonsingular nXm matrix in R, and b is in $R^n$.

Homework Equations

This is from chapter 3 of Boyd's Convex Optimization.

1. The conjugate function is defined as $f^*(y) = \sup_{x\in dom f} (y^Tx - f(x))$

2. The differentiable conjugate is given as $f^*(y) = x^{*T} \nabla f(x^*) - f(x^*)$

3. We also have that for arbitrary $z \in R^n$ and $y = \nabla f(z)$ we have $f^*(y) = z^T \nabla f(z) - f(z)$

The Attempt at a Solution

This question/relation is stated right after explaining the differential conjugate relationships above, so I suspect I need to use these identities versus the definition using the supremum. However, I'm having trouble applying the known identities to the function $g(x) = f(Ax + b)$. If the function was $f(x) = Ax+b$, I'd calculate $\nabla f(x)$ as A, and plug that into (2) above.

I tried using (3) by letting $z = Ax + b$. From this I have that $y = \nabla f(z) = A$ and then $f^*(y) = z^T \nabla f(z) - f(z)$. But expanding this out doesn't get me anything that looks promising.

Am I misunderstanding an identity here, or computing something wrong? Any pointers would be greatly appreciated.

 

[Ray Vickson]

Homework Statement

Prove that the conjugate of $g(x) = f(Ax + b)$ is $g^*(y) = f^*(A^{-T}y) - b^TA^{-T}y$ where A is nonsingular nXm matrix in R, and b is in $R^n$.

Homework Equations

This is from chapter 3 of Boyd's Convex Optimization.

1. The conjugate function is defined as $f^*(y) = \sup_{x\in dom f} (y^Tx - f(x))$

2. The differentiable conjugate is given as $f^*(y) = x^{*T} \nabla f(x^*) - f(x^*)$

3. We also have that for arbitrary $z \in R^n$ and $y = \nabla f(z)$ we have $f^*(y) = z^T \nabla f(z) - f(z)$

The Attempt at a Solution

This question/relation is stated right after explaining the differential conjugate relationships above, so I suspect I need to use these identities versus the definition using the supremum. However, I'm having trouble applying the known identities to the function $g(x) = f(Ax + b)$. If the function was $f(x) = Ax+b$, I'd calculate $\nabla f(x)$ as A, and plug that into (2) above.

I tried using (3) by letting $z = Ax + b$. From this I have that $y = \nabla f(z) = A$ and then $f^*(y) = z^T \nabla f(z) - f(z)$. But expanding this out doesn't get me anything that looks promising.

Am I misunderstanding an identity here, or computing something wrong? Any pointers would be greatly appreciated.

How can an $m \times n$ matrix be nonsingular if $m \neq n$? And if you happen to have $m=n$ and a nonsingular $A$, what does the notation $A^{-T}$ mean?

 

[Zerox5f3759df]

Hello, and thanks for taking a look. The n x m is a typo, my apologies, it should be n x n. I do also have a proof, which actually does just use the supremum definition. Here it is

$g^*(y) = \sup_{x \in dom(g)} (y^Tx - g(x))$
$= \sup_{x \in dom(g)} (y^Tx - f(Ax + b))$
$= \sup_{x \in dom(g)} (y^Tx + y^TA^{-1}b - y^TA^{-1}b - f(Ax + b))$
$= \sup_{x \in dom(g)} (y^TA^{-1}(Ax + b) - f(Ax + b) - y^TA^{-1}b)$
$= \sup_{x \in dom(g)} (y^TA^{-1}x - f(x) - y^TA^{-1}b)$
$= f^*(A^{-T}y) - b^TA^{-T}y$

As far as the notation $A^{-T}$ that is the inverse of the transpose of A. I apologize on the notation and typo confusion. We are given questions pulled from all over, and I suspect there are oddities in the material due to that. Thanks so much for taking the time to review my question!

 

[I like Serena]

Hi Zerox5f3759df! Welcome to PF! :)

Do you still have a question?

 

[Zerox5f3759df]

Nope, I think I am good on this one. Thanks for checking!