Optimization of Product of Different Objective functions (Ex.: Maximize The Product of projections of a complex vector)

Question

Suppose We have this optimization problem which is convex

$\mathbf{x}={\arg}\: \underset{\mathbf{x}}\max f_{i}\left (\mathbf{x} \right )$

But the product of different objective function is non-convex

$\mathbf{x}={\arg}\: \underset{\mathbf{x}}\max\left(\prod_{i=1}^{L}f_{i}\left (\mathbf{x} \right )\right)$

• Is there a method to approximate the non-convex problem to a convex one ?
• What is the best method to solve the non-convex problem ?

The Problem I faced is:

we have $L$ complex vectors $\mathbf{a}_{l}$ with dimension $N\times 1$

$\mathbf{x}=\arg \mathrm{max}_{\mathbf{x}}\prod_{l=1}^{L}\left | \mathbf{a}_{l}^{H} \mathbf{x} \right |^{2} $ subject to $\left \|{\mathbf{x}} \right \|^{2}=1$

where $\mathbf{x}$ is $N\times 1$ complex vector with unit norm

, $(.)^{H}$ is the complex conjugate transpose operator

, and $\prod_{l=1}^{L}(.)$ is the product operator to the elements from 1 to $L$

Can anyone help?

Answer 1

Hint: Probably your objective function is either log-convex or log-quasi convex.

My suggestion is to take $\log$ and then solve it. Note, that even by doing so your problem is non-convex because of $\|x\|=1$ (especially if $\|x\|=\|x\|_2$, then you can either relax the problem by converting the constraint $\|x\|=1$ to $\|x\|\leq 1$.

If the relaxation is not possible for your problem, then you will be able to solve the non-convex problem directly, by a forming the Lagrangian, and looking for some local optima, (iteratively optimizing for the primal and dual variables until convergence)

Answer 2

Your problem is not convex even if $L=1$, for two reasons: for one, you would be maximizing a convex function; and two, your constraint set is non-convex.

We can fix the second problem by relaxing the constraint to $\|x\|\leq 1$. Alt suggested this, but what he did not make clear is that you can guarantee equivalence in this case. To see why, suppose we relaxed the constraint to $\|x\|\leq 1$ and solved it perfectly, obtaining an optimal value $v\geq 0$ and an optimal vector $x^*$. If $\|x^*\|<1$, then consider the new vector $\bar{x}=\alpha x^*$, where $\alpha=1/\|x^*\|>1$. The objective function obtains the value $$\prod_{i=1}^L |a^H_l \bar{x}|^2 = \prod_{i=1}^L |\alpha a^H_l x^*|^2 = \alpha^2 \prod_{i=1}^L |a^H_l x^*| = \alpha^2 v \geq v$$ So $\bar{x}$ satisfies $\|\bar{x}\|=1$, and it obtains an objective value at least as good as $x^*$---in fact, if $v>0$, it is strictly larger. Therefore, you can safely relax your constraint in this case to $\|x\|\leq 1$.

This is good, of course, but it doesn't change the fact that your objective is non-convex. If you're going to construct a local solver for this, consider taking the logarithm of the objective. That won't change the optimal point: $$\begin{array}{ll}\text{maximize}&2\sum_{i=1}^L \log|a^H_l x|\\\text{subject to}&\|x\|\leq 1\end{array}$$ I think what I would do is alternate between gradient steps and normalization steps. That is, take a step in the direction of the gradient, and then re-normalize $x$ so that $\|x\|=1$, and repeat.