Least Squares Algorithm with Inverse Norm

Question

Given an overdetermined linear system $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^{m \times 1}$ with $A < 0$ and $b < 0$. What is a good way to numerically determine $$ \min_x \left\lVert \frac{1}{A x} - \frac{1}{b}\right\rVert_2^2,$$ where the fractions $\frac{1}{A x}$ and $\frac{1}{b}$ are element wise. Especially, what is the best way to approach this in Matlab?

Answer 1

Matlab's fminsearch would appear to be well-suited for this problem.

xMin=fminsearch(@(x) norm(1./(A*x)-1./b)^2 , ones(m,1));

It might be necessary to put in some constraints to avoid hitting $x=0$.

Alternatively, there is fminunc which is gradient-based and can make use of the objective function, its gradient and its hessian, but you have to manually calculate those (matlab, alas, does not do automatic differentiation). $$\left\|\frac{1}{A x}-\frac{1}{b}\right\|_2^2=\sum_i\left(\frac{1}{(A x)_i}-\frac{1}{b_i}\right)^2$$ $$\frac{\partial}{\partial x_k}\left\|\frac{1}{A x}-\frac{1}{b}\right\|_2^2=2\sum_i \left(\frac{1}{(A x)_i}-\frac{1}{b_i}\right) \frac{\partial}{\partial x_k} \left(\frac{1}{(A x)_i}-\frac{1}{b_i}\right)$$ $$\frac{\partial}{\partial x_k}\left\|\frac{1}{A x}-\frac{1}{b}\right\|_2^2=2\sum_i \left(\frac{1}{(A x)_i}-\frac{1}{b_i}\right) \frac{\partial}{\partial x_k} \left(\frac{1}{\sum_j A_{i,j}x_j}\right)$$ $$\frac{\partial}{\partial x_k}\left\|\frac{1}{A x}-\frac{1}{b}\right\|_2^2=2\sum_i \left(\frac{1}{(A x)_i}-\frac{1}{b_i}\right) \left(\frac{-A_{i,k}}{(\sum_j A_{i,j}x_j)^2}\right)$$ this is the gradient.

For the Hessian we must derive again $$\frac{\partial^2}{\partial x_k\partial x_l}\left\|\frac{1}{A x}-\frac{1}{b}\right\|_2^2=\frac{\partial}{\partial x_l}2\sum_i \left(\frac{1}{(A x)_i}-\frac{1}{b_i}\right) \left(\frac{-A_{i,k}}{(\sum_j A_{i,j}x_j)^2}\right)$$ $$\frac{\partial^2}{\partial x_k\partial x_l}\left\|\frac{1}{A x}-\frac{1}{b}\right\|_2^2=2\sum_i \left(\left(\frac{A_{i,l}A_{i,k}}{(\sum_j A_{i,j}x_j)^2}\right) + \left(\frac{1}{(A x)_i}-\frac{1}{b_i}\right) \frac{\partial}{\partial x_l}\left(\frac{-A_{i,k}}{(\sum_j A_{i,j}x_j)^2}\right)\right)$$ $$\frac{\partial^2}{\partial x_k\partial x_l}\left\|\frac{1}{A x}-\frac{1}{b}\right\|_2^2=2\sum_i \left(\left(\frac{A_{i,l}A_{i,k}}{(\sum_j A_{i,j}x_j)^2}\right) + \left(\frac{1}{(A x)_i}-\frac{1}{b_i}\right) \left(\frac{2 A_{i,k}A_{i,l}}{(\sum_j A_{i,j}x_j)^3}\right)\right)$$