# line fitting with numerical optimization

I'm programming a small MATLAB project to fit a 3D line to a line cloud point having N points using optimization technique, currently steepest descent and BFGS (working).

The problem is described by the figure:

• Premise:

a point that estimating line goes through $P(x_0,y_0,z_0)$ which is 1 point in the cloud;

estimating line is defined by 3 angles $\alpha, \beta, \gamma$ between line directional vector $\vec{u}$ with $\vec{i},\vec{j},\vec{k}$ of Ox, Oy, Oz.

(from another post of mine in math SE, I've learnt that this is 1 DOF redundant. 3D line has only 4 DOFs)

• Objective function analysis:

$f=\sum \|d_i\|$ with i=1..N, $d_i$ distance of point i to the estimating line

1) the function is smooth. This can be seen from its value and corresponding gradient

the blue lines are the functions $f(:,\beta_0,\gamma_0), f(\alpha_0,:,\gamma_0), f(\alpha_0,\beta_0,:)$ and red lines are corresponding $\nabla f$ functions

I barely know now to check its smoothness without having the explicit representation of the function. So, slicing down to simpler function is my choice

I also want to check its convexity - to ensure global convergence - but not sure how to.

The smooth function gives a chance to reach global minimizer?

2) therefore, this is a unconstrained optimization problem.

3) I'm wondering if this is a nonlinear least square problem?

• Result:

I've applied Wofle condition (backtracking for step length) and using Steepest Descent. So step $p_k$ is always descent

the first figure in the problem description is also the result of the optimization which doesn't look like a good estimation. And also from this $f$ plot over ~330 iterations.

I'm wondering if this is a convergence?? and 1070 is a the value of local minimizer?? How can I bring this to a better estimation, namely, to global minimizer??

-
is my question off topic? or it does not make sense or difficult? this is my class project and I really need some hints :) –  Shawn Le Jan 7 '13 at 4:52