1
$\begingroup$

Hi, this is a continuation of a previous question I asked about the convexity of an optimization problem I am working with.

Consider the function \begin{multline} B_i(a_0,\mathbf{p}) \equiv B(\vec{x}_i,a_0,\mathbf{p}) = \left(\begin{array}{cc} 1 & -p_{N}^*/a_0 \\\ p_{N}/a_0 & 1 \end{array}\right) \left(\begin{array}{cc} 1 & 0 \\\ 0 & z_{N}(\vec{x}_i) \end{array}\right) \cdots \\\ \left(\begin{array}{cc} 1 & -p_1^*/a_0 \\\ p_1/a_0 & 1 \end{array}\right) \left(\begin{array}{cc} 1 & 0 \\\ 0 & z_1(\vec{x}_i) \end{array}\right) \left(\begin{array}{cc} a_0 \\\ 0 \end{array} \right), \end{multline} where the variable $a_0$ is between 0 and 1, and the variables $\mathbf{p} = [\begin{array}{ccc} p_1 & \cdots & p_N \end{array}]$ satisfy $\vert p_j \vert \leq a_0$. The $z_j(\vec{x}_i)$'s are complex exponentials, e.g., $z_j(\vec{x}_i) = e^{\imath \vec{x}_i \cdot \vec{k}_j}$, where $\vec{x}_i$ is a spatial location and $\vec{k}_j$ is a spatial frequency location.

Here is the optimization problem: \begin{equation} \begin{array}{lll} \textrm{maximize} & a_0 & \\\ \textrm{subject to} & 0 \leq a_0 \leq 1 & \\\ & \vert p_j \vert \leq a_0, & j = 1,\dots,N \\\ & \vert B^d_i - B_i(a_0,\mathbf{p}) \vert \leq \delta_i, & i = 1,\dots,N_s \\\ & a_0^2 \prod_{j=1}^N(1+\vert p_j \vert^2/a_0^2) \leq 1, & \end{array} \end{equation} where $B^d_i$ is a target spatial pattern I want to achieve at spatial location $\vec{x}_i$, with maximum error $\delta_i$, and $N_s$ is the number of spatial locations I consider. $B^d_i$ has a maximum magnitude of 1. The variables are $a_0$ and $\mathbf{p}$.

Here is how I solve it, using bisection on $a_0$. I set initial lower and upper bounds on $a_0$ based on the result of a much faster, approximate optimization method. Then, for the initial lower-bound $a_0$ value, I solve the following feasibility problem, holding $a_0$ fixed:

\begin{equation} \begin{array}{lll} \textrm{minimize} & r & \\\ \textrm{subject to} & \delta_i^{-2} \vert B^d_i - B_i(\mathbf{p};a_0) \vert^2 \leq r, & i = 1,\dots,N_s \\\ & \vert p_j \vert \leq 1, & j = 1,\dots,N \\\ & a_0^2\prod_{j=1}^{N}\left(1 + \vert p_j \vert^2/a_0^2\right) \leq 1, \end{array}. \end{equation} I solve this subproblem using the barrier method, with Quasi-Newton search directions for $\mathbf{p}$.

If that problem is solved with $r \leq 1$, then these values of $a_0$ and $\mathbf{p}$ are feasible, and I can set the lower $a_0$ bound to this value of $a_0$, and repeat the problem at the midway point between this value of $a_0$ and the upper bound $a_0$. If $r > 1$, then these $a_0$ and $\mathbf{p}$ are infeasible, and I set the upper bound $a_0$ to this $a_0$, and solve the problem again for the midway point between the lower bound $a_0$ and the new upper bound $a_0$. I stop when $a_0$ stops changing by very much.

My question: Is this problem convex?

I have already proven that $a_0^2 \prod_{j=1}^N(1+\vert p_j \vert^2/a_0^2) \leq 1$ is convex in the domain of this problem, so it remains to be answered whether the $B_i$ error functions are convex. In a response to a previous question I asked it was shown that when $B^d_i = 0$, $\vec{x}_i = 0$ and $N=3$, then $\vert B^d_i - B_i(a_0,\mathbf{p})\vert $ is NOT convex. So, is it possible that when I use, for example, the barrier method to solve this problem, that the sum of the log-barriers for the $B_i$ error functions is a convex function?

$\endgroup$
4
  • 2
    $\begingroup$ The short answer is "No, there is no hope for any convexity here". Indeed, you may easily have two different ways to hit the target exactly already when $N=2$ but there is no hope that it'll be hit by every convex combination of those. The more interesting question is how on Earth to solve it then? Here I do not have a ready answer but I'll think of it. $\endgroup$
    – fedja
    May 27, 2011 at 22:55
  • $\begingroup$ Hi fedja, thanks for spending some time on it. As mentioned, I currently solve this problem (well, find some local minimum I suppose) using the barrier method. I remain hopeful that there is something provable about the optimality of my solutions, given that the solutions i get are simply very good and much better than competing methods. Furthermore, the algorithm always achieves the correct solutions for toy problems to which I know the answer a priori. $\endgroup$
    – Will
    May 28, 2011 at 8:05
  • $\begingroup$ Then just tell how exactly you do it and we may try to either prove the optimality or give you an example where your technique fails. That may take some time though. $\endgroup$
    – fedja
    May 28, 2011 at 12:43
  • $\begingroup$ Hi Fedja - just updated with a description of the algorithm. Thanks! $\endgroup$
    – Will
    May 30, 2011 at 6:51

0

Your Answer

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

Browse other questions tagged or ask your own question.