Suppose I have this optimization problem:
$ min f(X) - g(X), s.t. f(X)-g(X)\le 0, |X|\ge 0$
where $X$ is a square, symmetric, SPD matrix $\in \mathbb{R}^{N\times N}$, $f(X)=\sum_{a\in S} a^TXa$, and $g(X) =\sum_{b\in D} b^TXb$. $S$ and $D$ are two disjoint set in $\mathbb{R}^N$.
We know $f(x)$ and $g(x)$ are both convex and twice differentiable ( I believe..). So this is a DCP (difference convex programming) which can be solved by Convex-Concave Procedure (CCCP). Based on the CCCP, one can iteratively solve $X_{t+1}$ by:
$min f(X) - g(X_t) - \nabla g(X_t)^T(X-X_t)$ subject to the same constraints.
Let me substitute $f(x)$ and $g(x)$ into the cost function:
$ J =\sum_{a\in S}a^TXa - \sum_{b\in D}b^TX_tb - tr(\sum_{b\in D}bb^T(M-M_t))$
So using the sub-gradient method:
$ G = \partial J/\partial X = \sum_{a\in S}aa^T-\sum_{b\in D}bb^T$
We can update $M=M-\alpha G$. However, this problem seems not converge.
I found the linearised cost function is equal to the initial difference of convex problem, is this means CCCP cannot be used in this case?
$ J =\sum_{a\in S}a^TXa - \sum_{b\in D}b^TX_tb - tr(\sum_{b\in D}bb^T(M-M_t))\\ \ \ = \sum_{a\in S}a^TXa - \sum_{b\in D}b^TX_tb - tr(\sum_{b\in D}bb^TM)+tr(\sum_{b\in D}bb^TM_t)\\ \ \ = \sum_{a\in S}a^TXa - \sum_{b\in D}b^TX_tb -\sum_{b\in D}b^TXb + \sum_{b\in D}b^TX_tb\\ \ \ = f(X)-g(X)$
Extended question:
What will happen if I change my cost function to:
$J=\sum_{a\in S}exp(-a^TXa)-\sum_{b\in D}exp(-b^TXb)$
and subject to only $|X|\ge 0$. This one can be linearised to :
$J=\sum_{a \in S}exp(-a^TXa)-\sum_{b \in D}exp(-b^TX_tb)-tr([\sum_{b\in D}exp(-b^TX_tb)bb^T]^T(M-M_t)) $
The important thing is, the set $S$ and $D$ are changing (hopefully reducing size) during the optimization. So I'm using sub-gradient method to compute the gradient.