How do I optimize over this individually convex but not-jointly convex problem?

2011-10-01T11:52:50Z

I have the following optimization problem where I know how to optimize w.r.t $\alpha_i$ but want to derive an update rule or an equation to optimize over $X$ and $Y$. Does anyone have an idea on how to approach this?

I've tried deriving a Lagrangian dual but couldn't proceed after taking derivative wrt $X$ and the same for $Y$ because equation for optimal $X$ has $Y$ in it and vice versa. Hence, it's not easy to get a Lagrangian dual (only in terms of the dual variable corresponding to the constraint and knowns $P_i$, $\mathbf{\alpha}_i$).

The update equation doesn't have to use Lagrangian dual. It could be possible to massage this problem into a known problem using linear algebra tricks.

For dimensions,

$P_i$ are $k$ by $k$,
$X,Y$ are $k$ by $J$ where $J >> k$,
$\mathbf{\alpha}_i$ are $J$ by $1$
$\mathbf{e}_i$ are unit vectors $J$ by $1$

$$ \min_{X,Y} ~ \sum_{i=1}^n || P_i - X \mathbf{diag}( \boldsymbol{\alpha}_i ) Y^T ||_F $$

$$\text{s.t.} ~~ ||X \Lambda_j Y^T||_F^2 ~ \leq 1 ~~~~ \text{where } \Lambda_j=\mathbf{diag}(\mathbf{e}_j) ~~~~ \forall j = {1, ..., J} $$

Or equivalently,

$$ \min_{X,Y} ~ \sum_{i=1}^{n} || \mathbf{vec}(P_i) - [ \mathbf{vec}(\mathbf{x}_1 \mathbf{y}_1^T) , ... , \mathbf{vec}(\mathbf{x}_J \mathbf{y}_J^T) ] \boldsymbol{\alpha}_i ||_2^2 $$

$$ \text{s.t.} ~~ ||\mathbf{vec} (\mathbf{x}_j \mathbf{y}_j^T )||_2^2 \leq 1 ~~~ \forall j = {1, ..., J} $$

When I write the Lagrangian and take derivative w.r.t. $X$, I get the following but I'm stuck

$$\sum_{i=1}^n P_i \tilde Y_i^T = X \left( \sum_{i=1}^n \tilde Y_i \tilde Y_i^T + \sum_{j=1}^J \lambda_j \hat Y_j \hat Y_j^T \right)$$ $\text{where} ~ \tilde Y_i = \mathbf{diag}(\mathbf{\alpha}_i) Y^T$ and $\hat Y_j = \Lambda_j Y^T$ Lagrangian might not be the way to go about this. Does anyone have a suggestion?

How do I optimize over this individually convex but not-jointly convex problem? - MathOverflow

How do I optimize over this individually convex but not-jointly convex problem?