How many methods could be used to solve this optimization problem with equality constraints?

Question

I wonder whether there is a simplest method for this problem.

The function to maximize is $F(x)$. $F(x)=\|Kx\|_2^2=x^TK^TKx$, where $K\in \mathbb{R}^{n\times d}$ and $x\in \mathbb{R}^d$.

and $\nabla F=2K^TKx.$

The equality constraints are $$g(x_i)=1-|x_i|=0,i=1,\cdots,d$$where $x_i$ is the $i^{th}$ component of $x$.

I try to use Lagrange multiplier, but it ends a uncomputable problem.

I figure out a method but I am not sure this will work well.

I can use gradient increase to solve the follow equation.

$$x^TK^TKx-(x_1-1)^2-\cdots-(x_d-1)^2$$

I am looking forward to your advice.

Answer 1

I am curious to know where you apply this. I am familiar with this problem from the context of wireless sensor networks. This problem belongs to the class of non-convex combinatorial quadratic programming and is NP-Hard. A well-known numerical approximation technique is semi-definite relaxation. Please read this well-known paper to know more about it.