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.

Improve this question
$\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$
    – Nathaniel Johnston
    Commented 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$
    – Michael Grant
    Commented Dec 19, 2014 at 3:38

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .