# Large-scale almost-linear optimization

I'm currently trying to minimize the following function: $$\min_{\mathbf x,\mathbf y,s} \|F\mathbf x-\mathbf a\|_2^2 + \|SF\mathbf y-\mathbf b\|_2^2 + \lambda \|\max(\mathbf x, \mathbf y)\|_1,$$ $$\mathbf x>\mathbf 0, \mathbf y>\mathbf 0.$$ Here $F$ and $S$ are both linear operators. $F$ is a discrete Fourier transform, $S$ is "shift by $s$ in Fourier domain" operator: $(Sf)_k = f_k \cdot e^{-2\pi i u_k s}$, and $\max(\mathbf x, \mathbf y)$ is elementwise.

So the problem is basically regularized least squares, and should hopefully lead to sparse solutions $\mathbf x, \mathbf y$ having nonzero elements in about the same locations (up to explicit shift $s$).

Note that it is almost linear but for the discontinuity in regularizer and nonlinear dependency on $s$. For fixed $s$ I get good results ($\mathbf x,\mathbf y$ close to true values) using LBFGS method. When optimizing separately for each $s$ from a range, I see a clear minimum around the true value. But when I include the $s$ variable into optimization, its value basically doesn't change from the initial one, no matter if it is close or far from the truth.

I guess the problem is that the function (of $s$) has many local minima all over the range. How to approach the problem correctly, or where to read about similar ones? I had no success with other common optimization algorithms from scipy I tried.

• Can you just do an inner/outer optimization? $\displaystyle \min_{x,s} ~f(x,s) = \min_s~ g(s)$ where $\displaystyle g(s) = \min_x~ f(x,s)$. The inner problem you can solve with quasi-newton. The outer problem is 1-dimensional so you can solve it with a secant method or something like that. – Nick Alger Feb 11 '18 at 23:46
• The regularizer is easily fixed by introducing slack variables $\mathbf z$ and replacing $\|\max(\mathbf x,\mathbf y)\|$ by $\|\mathbf z\|$, if you add constraints $\mathbf z\ge \mathbf x$ and $\mathbf z\ge \mathbf y$. If you further add another set of slack variables, you can convert the $l_1$ norm into a linear sum. – Wolfgang Bangerth Feb 13 '18 at 3:52

I think you could decompose this problem into a convex and non-convex one by alternation. One could maybe first optimize for $\mathbf x$ and $\mathbf y$: $$\min_{\mathbf x,\mathbf y} \|F\mathbf x-\mathbf a\|_2^2 + \lambda \|\max(\mathbf x, \mathbf y)\|_1,$$ keeping $\mathbf S$ constant.
In the next stage, we could solve for $\mathbf S$: $$\min_{s} \|SF\mathbf y-\mathbf b\|_2^2$$ this time keeping all the rest fixed. Maybe it is easier to solve this second equation via direct methods.
Starting from certain initialization, we could alternate both solutions until we arrive at the desired one. Other splits are also possible and might work better, such as first solving for $\mathbf x$, etc.