1
$\begingroup$

I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set of 3D GPS vectors easily modeled with constraints like this

$min$ $\sum_{\forall i} u_{i} + v_{i}$

$w_{i} x_{i,end} - w_{i} x_{i,start} + u_{i} - v_{i} = w_{i} b_{i}$

I've had success running Barrodale and Robert's $L_{1}$ minimising simplex method on it, but for intractable problems with more than 10,000 constraints I want to try Dikin's affine interior point method.

I've written an implementation of the affine IP method using C++ and Armadillo in which it initialises using the Big M method successfully, and after 5 or 6 iterations the big M variable drops to below $10^{-7}$ which is small enough for me to remove and add the excess to the residuals.

Unfortunately, it then goes on to not converge. Even on small problems of 100 constraints. I've tried larger big M values (currently it is set to be the sum of the $b$ vector) and also just not dropping the big M term, but neither work. If I leave the algorithm long enough, the quadratic form used in the projection becomes a matrix that has no inverse and the programs stops. Can I assume this is the culmination of numerical error?

I'm obviously doing this incorrectly so any advice would be much appreciated.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.