3

I'm solving the constrained least squares problem $\underset{u \in [0,1]^N} \min \lVert Au-f \rVert_2^2$ with $u \in \mathbb{R}^N$, $A \in \mathbb{R}^{N \times N}$ and $f \in \mathbb{R}^N$ by using the following modified Jacobi-Method:

$u^{k+1}=\max \{ \min \{ D^{-1} (f - R u^k), 1 \},0 \}$ where $A=D+R$, $D$ is the diagonal of $A$. The $\max$ and $\min$ are applied element-wise, so what I'm doing is basically the standard Jacobi-Method but with projection to the constraint after each iteration.

I need to find out under which conditions on $A$ and $f$ this actually converges to the correct solution of the above problem. Any hints on related literature would be appreciated!

TestTestGuest
  • 31
  • Is $A$ diagonally dominant, or are their some conditions that would make the spectral radius of $D^{-1}R$ be less than one? – copper.hat Feb 25 '13 at 20:15
  • yes, A is strictly diagonally dominant. it satisfies all conditions for the normal jacobi method to converge – TestTestGuest Feb 25 '13 at 21:29

1 Answers1

3

Here is a (tedious) example that shows that the proposed method will not stop at a solution.

Let $A= \frac{1}{10}\begin{bmatrix} 20 & 10 \\ 10 & 21 \end{bmatrix}$, $f = \frac{1}{160}\begin{bmatrix} 505 \\ 278 \end{bmatrix}$ and $\hat{u} = \frac{1}{2} \begin{bmatrix} 2 \\ 1 \end{bmatrix}$.

Let $\phi(u) = \frac{1}{2} \|Au -f\|_2^2$, and note that $\phi$ is convex and $\nabla \phi(u) = A^T(Au -f)$, and $\nabla( \hat{u}) = \begin{bmatrix} -1 \\ 0 \end{bmatrix}$. Furthermore, note that $\langle \nabla \phi(u), u - \hat{u} \rangle \geq 0 $ or all $u \in [0,1]^2$, hence $\hat{u}$ is the solution to the constrained least squares problem.

We have $D= \frac{1}{10}\begin{bmatrix} 20 & 0 \\ 0 & 21 \end{bmatrix}$, $R = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$. The Jacobi update would give $u_+ = D^{-1}(f-R \hat{u})) = \frac{1}{1344}\begin{bmatrix} 1785 \\ 472 \end{bmatrix}$, which when projected onto $[0,1]^2$ would give $\frac{1}{1344}\begin{bmatrix} 1344 \\ 472 \end{bmatrix} \neq \hat{u}$.

The problem is that the update directions do not align at the solution of the original problem.

copper.hat
  • 172,524
  • thanks for the tedious example.

    but i was looking for some result which states that for some specific conditions on $A$ and $f$ this method converges.

     – TestTestGuest Feb 27 '13 at 18:30
  • Well, if you have an example that doesn't work and understand why, this may lead to you finding $A,f$ that might work. You are asking for a detailed analysis/result to solve a well-understood problem using a hacked-up method. – copper.hat Feb 27 '13 at 22:43