Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  fedja May 27 '11 at 22:55
    
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. –  Will May 28 '11 at 8:05
    
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. –  fedja May 28 '11 at 12:43
    
Hi Fedja - just updated with a description of the algorithm. Thanks! –  Will May 30 '11 at 6:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.