How do I optimize over this individually convex but not-jointly convex problem? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T21:13:59Z http://mathoverflow.net/feeds/question/76917 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76917/how-do-i-optimize-over-this-individually-convex-but-not-jointly-convex-problem How do I optimize over this individually convex but not-jointly convex problem? Jackson 2011-10-01T11:52:50Z 2011-10-02T04:48:33Z <p>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? <br></p> <p>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$).</p> <p>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.</p> <p>For dimensions, </p> <p>$P_i$ are $k$ by $k$, <br> $X,Y$ are $k$ by $J$ where $J >> k$, <br> $\mathbf{\alpha}_i$ are $J$ by $1$ <br> $\mathbf{e}_i$ are unit vectors $J$ by $1$ <br></p> <p>$$\min_{X,Y} ~ \sum_{i=1}^n || P_i - X \mathbf{diag}( \boldsymbol{\alpha}_i ) Y^T ||_F$$</p> <p>$$\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}$$ </p> <p>Or equivalently, </p> <p>$$\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$$</p> <p>$$\text{s.t.} ~~ ||\mathbf{vec} (\mathbf{x}_j \mathbf{y}_j^T )||_2^2 \leq 1 ~~~ \forall j = {1, ..., J}$$</p> <p><br> <br></p> <p>When I write the Lagrangian and take derivative w.r.t. $X$, I get the following but I'm stuck</p> <p>$$\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?</p>