I've been working on an optimization problem that is almost a semi-definite program (SDP) barring a sum of squares constraint (expressed as under) which is making it a non-convex problem: \begin{equation} \sum_{i,j}x_{ij}^2 = 1 \end{equation}
As a preliminary approach to solving this, we can re-write the above constraint in the equivalent form: \begin{equation} \sum_{i,j}x_{ij}^2 \leq 1 \\ \sum_{i,j}x_{ij}^2 \geq 1 \end{equation} and then approximate the second constraint i.e. $\sum_{i,j}x_{ij}^2 \geq 1$ in some way that lower bounds the absolute values $|x_{ij}|$.
Again, as the right lower bounds on $|x_{ij}|$ are difficult to figure, is there any possible work around to solve the main problem with or without using the idea presented above (even an approximate solution is fine)?
A few points to be noted:
- Relaxing the constraint isn't giving anything useful in my particular case.
- The main constraint i.e. $\sum_{i,j}x_{ij}^2 = 1$ is an equivalent replacement for a relatively intractable constraint $\text{rank}(X) = 1$ as the sum-of-squares form looked a tad more tractable but an approach in either of these two directions should be fine.
- Trying to avoid black-box optimization techniques such as genetic algorithm, simulated annealing so a classical approach would be the suit best here.