0
$\begingroup$

It's known that for convex $f_i$ $\forall i$ if

$$ g(x) = \inf\{f_1(x_1)+f_2(x_2)|x_1+x_2=x\} $$

Then $g^{*}(y) = f^{*}(y)+f^{*}(y)$

I want to check this identity for $f_i(x)=\dfrac{1}{2}x^TP_ix$, $P_i > 0$.

First, I find $f^{*}$ for $f_i$:

$$ f_i^{*}(y) = \dfrac{1}{2}y^TP_i^{-1}y $$

Thus:

$$ g^{*}(y) = \dfrac{1}{2}y^T(P_1^{-1}+P_2^{-1})y $$

Then, I tried to found $g^{*}$ directly, but stuck:

$$ g^{*}(y) = \sup\limits_{x}\left(y^Tx-(\inf\limits_{x_1+x_2=x}\dfrac{1}{2}x_1^TP_1x_1 + \dfrac{1}{2}x_2^TP_1x_2)\right) $$

Here, first I found optimal $x_1, x_2$:

FOC from Lagrangian for "inf" problem:

$$ x_i^TP_i = \nu^T => x_1^TP_1 = x_2^TP_2 \\ x_1 + x_2 = x $$

Thus:

$$ x_1 = (I+P_2^{-1}P_1)^{-1}x\\ x_2 = (I - (I+P_2^{-1}P_1)^{-1})x $$

I don't know how to simplify quadratic form, when inserting this in equation for $g^{*}(y)$

$\endgroup$
  • $\begingroup$ Everything you did checks out. You still have to optimize over $x$ at the end, does that simplify your result? Are you looking to finish this derivation, or can you start with $f_1*(y)+f_2*(y)$ and take the conjugate? $\endgroup$ – LinAlg Jan 29 '17 at 0:05
  • $\begingroup$ I'm looking to finish derivation of $g^{*}$ from the definition and check that it's the same as I found from $f_1^{*}(y)+f_2^{*}(y)$. When I insert equations of $x_1, x_2$ I obtain some horrible quadratic form. Denote this matrix $Q$. Then $g^{*}(y) = \dfrac{1}{2}y^T Q^{-1}y$. But I can not simplify this $Q$ to $P_1^{-1}+P_2^{-2}$ $\endgroup$ – Evgeny Egorov Jan 29 '17 at 0:08
  • $\begingroup$ was my solution any helpful? $\endgroup$ – LinAlg Feb 7 '17 at 8:39
  • $\begingroup$ Your result looks like very far from right, so I didn't use it, sorry. I solve problem with block inversion, rather than find x_1 and x_2 separately $\endgroup$ – Evgeny Egorov Feb 7 '17 at 12:56
  • 1
    $\begingroup$ Has it ever crossed your mind that I put quite some time in finding and formulating my solution, which btw only had a minor mistake that could be resolved easily? Then you just disappeared. I'm abandoning this community as I'm just wasting my time. $\endgroup$ – LinAlg Feb 7 '17 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.