4
$\begingroup$

I am looking for an appropriate method or hint to solve the following constrained nonlinear least square problem:

$\operatorname{argmin}_X \sum_{i\in I} \|\mathbf{X}_i - \mathbf{X}_{i+1}\|_2^2 + \sum_{i\in I} \|\mathbf{X}_i - \mathbf{Z}_i \|_2^2$ $\text{s.t.}\quad \forall i,j \quad (\mathbf{X}_{i,0} - \mathbf{X}_{i,1})^2 = (\mathbf{X}_{j,0} - \mathbf{X}_{j,1})^2, (\mathbf{X}_{i,3} - \mathbf{X}_{i,4})^2 = (\mathbf{X}_{j,3} - \mathbf{X}_{j,4})^2$

where $\mathbf{X}_i, \mathbf{Z}_i \in\mathbb{R}^d$, and $I$ is a set of samples. The number of variables in $\mathbf{X}$ is about 1 million ($d\approx 100$). $\mathbf{Z}$ is a constant, full-rank matrix.

Thanks for suggestions!

$\endgroup$

1 Answer 1

2
$\begingroup$

The constraints can be rewritten by replacing the squares with absolute values, then you have a program like

$\operatorname{argmin}_{\mathbf{X}} \|\mathbf{D}\mathbf{X}\|_F^2 + \|\mathbf{X} - \mathbf{Z}\|_F^2$

$\text{s.t.}\quad \forall i,j \quad |\mathbf{d}_{01} \mathbf{X}_i| = |\mathbf{d}_{01} \mathbf{X}_j|, \text{ and } |\mathbf{d}_{34} \mathbf{X}_i| = |\mathbf{d}_{34} \mathbf{X}_j| $

where the $\mathbf{X}_i$ constitute the columns of $\mathbf{X},$ the matrix $\mathbf{D}$ takes the differences of the consecutive columns of $\mathbf{X},$ and $\mathbf{d}_{01}, \mathbf{d}_{34}$ are appropriately defined row vectors.

Then you can use the standard trick of replacing $|x|$ with $x_{+} + x_{-}$ subject to $x = x_{+} - x_{-}$ and $x_{+}, x_{-} \geq 0$ to get the equivalent program

$\operatorname{argmin}_{\mathbf{X}, \mathbf{e}^{+}, \mathbf{e}^{-},\mathbf{f}^{+}, \mathbf{f}^{-}} \|\mathbf{D}\mathbf{X}\|_F^2 + \|\mathbf{X} - \mathbf{Z}\|_F^2$

$\text{s.t.}\quad \forall i: \quad \mathbf{d}_{01} \mathbf{X}_i = e^{+}_i - e^{-}_i, \text{ and } \mathbf{d}_{34} \mathbf{X}_i = f^{+}_i - f^{-}_i,$

$\quad \quad \forall i \neq j: e^{+}_i + e^{-}_i = e^{+}_j + e^{-}_j, \text{ and } f^{+}_i + f^{-}_i = f^{+}_j + f^{-}_j,$

$\quad \quad \mathbf{e}^{+}, \mathbf{e}^{-}, \mathbf{f}^{+}, \mathbf{f}^{-} \succeq 0$

By considering the Lagrangian, you can see that for each i, at least one of the $e^{\pm}_i$ will be zero, and likewise for the $f^{\pm}_i,$ so this is indeed equivalent to the original program. Concisely: at a presumed optimal point you can always increase over the value $L(\mathbf{X}^\star, \mathbf{e}^{+,\star}, \mathbf{e}^{-,\star}, \mathbf{f}^{+,\star}, \mathbf{f}^{-,\star}, \boldsymbol{\lambda}, \boldsymbol{\nu})$ by moving all the mass onto exactly one of $\mathbf{e}^{\pm}$ and $\mathbf{f}^{\pm}.$

By vectorizing $\mathbf{X}$, you can write the objective as a convex quadratic in a vector $\mathbf{x}$, and a little massaging of the constraints gives you a convex quadratic program in standard form.

In terms of actually solving the final QP, I'm not sure what the state of art is, especially since performance usually depends on the properties of your problem (sparsity or structure in the Hessian of your quadratic, whether you have only equality or inequality constraints, etc.). You'd need a subject matter expert to get a definitive answer on that one. I'd personally try TFOCS if you have access to Matlab, since it's a first order solver and looks relatively easy to use (I have not used it myself).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.