Consider the function $$f(x,y) = \big(b-x^T A y\big)^2$$ where $x \in \mathbb{R}^{p\times 1}$, $y \in \mathbb{R}^{n\times 1}$, $A \in \mathbb{R}^{p \times n}$ and $b \in \mathbb{R}$.

What is the Fenchel conjugate of $f$, that is $$ f^*(u,v) := \sup_{x,y} \big[ u^T x + v^T y - f(x,y)\big] = \;? $$


1 Answer 1


This is just a partial answer, but maybe it's still of some use to you. First, I would simplify the system a bit by reducing it to just one variable $\tilde x\in \mathbb R^{n+p}$ and $\tilde u\in \mathbb R^{n+p}$ by defining $\tilde x=\begin{bmatrix}x\\y\end{bmatrix}$, $\tilde u=\begin{bmatrix}u\\v\end{bmatrix}$ and $\tilde A=\frac12 \begin{bmatrix}0 & A \\ A^T & 0\end{bmatrix}$. Note that $\tilde A$ is symmetric. Then $$\tilde f(\tilde x)=(b-\tilde x^T\tilde A \tilde x)^2$$ and the Fenchel transform becomes $$\tilde f^*(\tilde u)=\sup_{\tilde x} [\tilde u^T \tilde x - \tilde f(\tilde x)]$$ Since $\tilde f$ is differentiable, we get as necessary condition $$\partial_{\tilde x} (\tilde u^T \tilde x - \tilde f(\tilde x)) =\tilde u - 4(b-\tilde x^T \tilde A\tilde x)\tilde A x=0$$ If $\tilde g$, defined by $\tilde g(\tilde x)=4(b-\tilde x^T\tilde A\tilde x)\tilde A\tilde x$, is invertible, you get $$\tilde f^*(\tilde u)=\tilde u\tilde g^{-1}(\tilde u)-\tilde f(\tilde g^{-1}(\tilde u))$$ However, I cannot see how one could come up with an analytical expression for $\tilde g^{-1}$, nor how one could get rid of the $\tilde x$ terms in the expression for $\tilde f^*$ otherwise. (I tried a bit around with premultiplying the equation for $\tilde u$ by $\tilde x^T$ and then trying some substitutions in $\tilde f^*$, but that didn't work out.).

NB: If you need to do the transform numerically, then of course you can use stuff like e.g. Newton's method or Brent's method to find $\tilde g^{-1}$.

  • $\begingroup$ Thanks for the effort. I think it is easier to separately maximize first over, say, $x$ and then $y$. It seems to me that the $\sup$ is going to be $\infty$ for most $(u,v)$ pairs. $\endgroup$
    – passerby51
    Feb 22, 2013 at 2:04
  • $\begingroup$ I tried that too with $x$ and $y$ separately, but than you get a couple system which doesn't make things easier IMO. $\endgroup$ Feb 23, 2013 at 8:50
  • $\begingroup$ I think you're right with the second part: just take some $\tilde x\in \ker(\tilde A)$ and $\tilde u^T \tilde x - \tilde f(\tilde x)=\tilde u^T \tilde x - b^2$. Since for any scalar factor $\alpha$ you also have $\alpha \tilde x\in\ker(\tilde A)$, this cannot be bounded. Except, of course, if $n=p$ and $A$ is non-singular. $\endgroup$ Feb 23, 2013 at 8:58
  • $\begingroup$ ... and not $\tilde u\in\ker(\tilde A)^\bot$. $\endgroup$ Feb 23, 2013 at 9:06

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.