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?


2 Answers 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.


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)


You must log in to answer this question.

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