implement WORHP as a solver

[timueh]

Currently, we support casadi with ipopt and fmincon as solvers on the abstractify branch. Once #105 has been taken care of, @Alexdaijlu takes care of adding worhp.

[xinliang-dai]

WORHP-extension has been created in Morenet project and is called in createLocalSolvers.m

Notice that it is a prototype and only avaliable for small-scale least-squares problem currently. More detailed information would be described in issue 26 in Morenet project

[xinliang-dai]

@alexe15 The Hessian (vector) issue by using worhp has been solved.
Currently, it works for unconstrained problem.

[xinliang-dai]

Now, worhp work fine for both feasibility (eqaulity constrained) and least-sqaures (unconstrained) problem in morenet project. It shows a comparable shorter running time than CasADi, especially when problem size is large.

To solve inequality constrained problem, more modification is needed in worhp-matlab interface.

[alexe15]

Hey Xinliang, that sounds great, nice work! How did you do it in the end? With sparsity detection as we discussed?

[xinliang-dai]

Yes, first use sparsity detection and then I have 2 small modifications.

Order of Hessian Elements

I read worhp manual in detail and found something I missed last time:

WORHP requires a special sorting of the sparse entries. All entries on the diagonal must be given, even structural zeros. Furthermore, the non-diagonal entries must be given first.

So the correct order of elements should be:

1. nonzero elements in lower triangular matrix;
2. all diagonal elements, including zero element.

Matlab Function-handle

The second modification is to simply the calling function
In previous version, the Hess-info is supported by:

wCallback.hm          = @(x)build_Hess_vector(Hess.Func, x, ...);

where Hess.Func is a function-handle.

Now, the build_Hess_vector is called by:

wCallback.hm          = @(x)build_Hess_vector(Hess.Func(x)...);

Instead of a function-handle, the input is a numerical matrix.

After both modifications, worhp works for both problem formulations in Morenet. In the following is the simulation results of least-squares problem:

I'm updating the report. I can send it to you if you wanna have a look. @alexe15

[timueh]

That's very nice to see! Great job!

Do you have any feeling @Alexdaijlu for why fmincon is still so much faster?

[xinliang-dai]

Do you have any feeling @Alexdaijlu for why fmincon is still so much faster?

@timueh
It could be discussed in 3 aspects:

1. Inexact Hessian approximated by Jacobian

As we discussed in issue 26, hessian of least-squares problem could be approximated by Jacobian and becomes more accurate when x approach minimun. Compared with 3 inexact hessian approximation algs in fmincon, i.e. BFGS, LBFGS and Finite-difference, the hessian approximated by Jacobian is much faster:

2. fmincon vs extended solvers
   Compared with extended solvers, i.e. CasADi and worhp, it is faster to setup a problem by fmincon. I think one of the reason is function handle rooted in matlab.

3. fmincon vs fminunc
fmincon is faster than fminunc, when the problem size goes large. During computation of large-scale problem, it is observed that fminunc runs slower with more F-count (the number of points where function evaluations took place) and more iterations, and sometime it results in several warnings, including singular matrix. It shows that fmincon has some better strategies to find minimun. Regularization could be one of them.

PS: worhp also has great potential in solving large-scale problem.