0
$\begingroup$

I'm working with the following optimization problem below. $$\min_{\Pi} \left[ \frac{1}{4 \lambda }\left((\Pi\vec{1}-s)^T K(\Pi\vec{1}-s) + \left(\Pi^T \vec{1}-t\right)^T K \left(\Pi^T \vec{1}-t\right)\right)-\text{Tr}[\Pi K] \right]$$

Here, $\lambda$ is a scalar, $\Pi$ and $K$ are $n\times n$ matrices, and $s,t$ are $n\times 1$ probability vectors (i.e. the components sum up to $1$). Also $K$ is PSD and $\Pi$ has elements summing up to $1$.

I was able to empirically show that the diagonal elements of $\Pi^{*}$, the optimal $\Pi$, correspond to $\frac{s+t}{2}$ regardless of the choice of $\lambda$, but I am having difficulty showing this to be the case theoretically. Does anyone have any advice? I tried for the case when $n=2$ using Lagrange multipliers and even then it gets very messy.

I set up a Lagrange multipier where the matrix constraint $1^T \Pi 1=1$, and I end up getting as my first order conditions

$$2K [(\Pi+\Pi^T) \vec{1}-(s+t)] \vec{1}^T - K - \lambda \vec{1}\vec{1}^T = 0$$ and $$1-\vec{1}^T \Pi \vec{1}=0.$$

I just don't see where to go from here. I'd like to use these to show $\vec{diag(\Pi^*)} = \frac{1}{2}(\vec{s+t})$. Also, how do I come up with KKT duals when every element of $\Pi$ must be nonnegative?

Anyone have any ideas?

$\endgroup$
13
  • $\begingroup$ For $n \ge 2$, the problem is generally unbounded, unless there is an additional constraint, such as all elements of $P \ge 0$.. Presuming this additional constraint is added, I did not find agreement with your assertion on any of several instances I generated with random s and t probability vectors and random PSD K, and numerically solved as QP. However, your assertion appears to be true, if also K is a (positive) multiple of the Identity matrix, but not true if K is a general PSD diagonal matrix. $\endgroup$ May 15, 2020 at 0:48
  • $\begingroup$ Oh so yeah also all the elements of $\Pi$ are nonnegative, yes. $\endgroup$
    – Kashif
    May 15, 2020 at 2:35
  • $\begingroup$ Can you tell me which instances gave a counterexample? $\endgroup$
    – Kashif
    May 15, 2020 at 2:36
  • $\begingroup$ Every instance I tried, except for the exceptions I mentioned. Maybe all your inputs are more structured specials cases. What instances did you solve and how do they map against the special cases I mentioned? $\endgroup$ May 15, 2020 at 2:38
  • 1
    $\begingroup$ KKT conditions en.wikipedia.org/wiki/…. QP, so satisfies Linearity constraint qualification. I am doubting you will find a closed form solution. $\endgroup$ May 15, 2020 at 2:51

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.