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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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)$$
-
$\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$– JiroJul 28, 2016 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$– JiroAug 9, 2016 at 15:23