2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ I have tried this option and it works, but isn't there any possibility to use a derivative based and more robust method? $\endgroup$ – Sebastian Schlecht Jul 28 '16 at 11:23
  • $\begingroup$ I believe that there is a typo: $\frac{A_{i,l}A_{i,k}}{(\sum_j A_{i,j}x_j)^2}$ in the Hessian should be instead $\frac{A_{i,l}A_{i,k}}{(\sum_j A_{i,j}x_j)^4}$. Can you confirm this? $\endgroup$ – Sebastian Schlecht Aug 9 '16 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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