2
$\begingroup$

Consider the following optimization problem
$$ \min \| \textbf{Ax-B}\| $$
$$ s.t.|x_i|=1,i=1,...,n $$
where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th element of $\textbf{x}$, $\textbf{A}\in \mathbb{C}^{m \times n}$ and $\textbf{B}\in \mathbb{C}^{m}$ are constant.

I want to find a algorithm to solve a stationary point of the problem. When I replace $x_i$ with theta, some search algorithms seem to be extremely difficult to solve. Maybe there are other methods to transform the problem to familiar one.

$\endgroup$
2
  • 1
    $\begingroup$ If you replace the constraint $|x_i| = 1$ with $|x_i| \leq 1$ then it becomes a true convex optimization problem (a semidefinite program, even) and becomes easy to solve. It won't agree with the minimum that you're after in general, but at least will give you a nontrivial lower bound on it. $\endgroup$ Dec 18, 2014 at 16:11
  • $\begingroup$ Indeed, I would not tag this as convex-optimization or linear-programming. It is most certainly neither. This is quite a difficult problem and I am unaware of any good heuristics (not that I would know them all!) $\endgroup$ Dec 19, 2014 at 3:38

1 Answer 1

2
$\begingroup$

A usual trigonometric substitution $x_j:=\cos\phi_k +i\sin\phi_k$, $\phi:=(\phi_1,\dots,\phi_n)$ might tell something. After some straightforward manipulations your minimisation problem becomes $$\min_{0\leq \phi\leq 2\pi} \sum_k\sum_j (w_{kj}-z_{kj}\cos(\phi_k+\omega_{kj})),$$ where $w_{kj}:=|A_{kj}|^2+|B_k|^2$, $z_{kj}:=2|A_{kj}||B_k|$, and $\omega_{kj}:=\arg A_{kj}-\arg B_k$.

It appears to be in general a highly non-linear problem, with lots of local minima.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.