# [SciPy-dev] Fwd: from GSoC student Dmitrey Kroshko

Dmitrey Kroshko openopt@ukr....
Mon Aug 13 13:06:09 CDT 2007

```          Hi Matthieu,
I just implemented very simple algorithm for line-search subproblem, described in the book B. Pshenichniy "Linearisation method", page 46, and lincher is almost the same as the NLP solver from same page 46. You can check that one in lincher.py, line 296 (as you see, it didn't use gradient info vs yours). But since the book is dated 1983, I guess there are better algorithms for now. I will be happy if you'll provide any one (that can be used with non-smooth funcs).

So I have updated svn, and if you are interested here's results of mine and yours funcs:

#my Armijo implementation
itn 66 : Fk= 85.4300044557 maxResidual= 8.77891444873e-07
istop:  4 (|| F[k] - F[k-1] || < funtol)
Solver:   Time elapsed = 7.41     CPU Time Elapsed = 7.28
objFunValue: 85.4300044557 (feasible)

#Matthieu:
mylinesearch = line_search.StrongWolfePowellRule(sigma=5)
destination = mylinesearch(function = lsF, origin = x0, step = direction, state = state)

itn 78 : Fk= 85.4300278074 maxResidual= 6.97178904829e-07
istop:  4 (|| F[k] - F[k-1] || < funtol)
Solver:   Time elapsed = 8.58     CPU Time Elapsed = 8.46
objFunValue: 85.4300278074 (feasible)

if I use
line_search.StrongWolfePowellRule() (i.e. with default param sigma)
it yields (the example from lincher.py head)
itn 0: Fk= 1428.11851019 maxResidual= 2242631.78131
itn 10 : Fk= 86.6072664467 maxResidual= 0.466521056114
N= 5336.61507377
and then CPU hang up (at least, I didn't observe anything till ~2 min and then stopped; my iprint = 10).

Matthieu Brucher wrote:            Hi,

Some precisions :)

this week I wrote line-search optimizer based on Armijo rule.

It seems not to be committed yet. I've coded it myself thursday or friday :       http://projects.scipy.org/scipy/scikits/browser/trunk/openopt/scikits/openopt/solvers/optimizers/line_search/backtracking_search.py
Too sad dmitrey did not code it with my framework.

It's
very simple, but now lincher didn't require other line-search
optimizers from other software - I mean Matthieu's one (unfortunately
it very often makes CPU hang up)

Precision here so that there are no misunderstanding : the one dmitrey is talking anout is one of many, it's the one with Strong Wolfe-Powell rule, and dmitrey's cost function is not smooth thus the line search has trouble dealing with it.

For those who are intersted :       http://projects.scipy.org/scipy/scikits/wiki/Optimization

Matthieu

_______________________________________________
Scipy-dev mailing list
Scipy-dev@scipy.org
http://projects.scipy.org/mailman/listinfo/scipy-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://projects.scipy.org/pipermail/scipy-dev/attachments/20070813/0838cd40/attachment.html
```