[SciPy-dev] Derivative-based nonlinear optimization with linear ineqality constraints

[dmitrey]

Bill Baxter wrote:
> On 5/22/07, dmitrey <openopt@ukr.net> wrote:
>   
>> Bill Baxter wrote:
>>     
>>> There don't seem to be any optimizers in SciPy that have all of these
>>> attributes:
>>> 1) nonlinear objective function
>>> 2) uses analytical derivatives
>>> 3) allows (non-)linear (in)equality constraints
>>>
>>>       
>> So your message differs very much from topic "Derivative-based nonlinear
>> optimization with linear    ineqality constraints"
>>     
>
> Not sure what you mean.  I have gradient information and I am
> interested in using it to optimizing a non-linear objective function
> subject to linear inequality constraints.  But at the same time I
> don't see any gradient-based solvers in scipy that can handle *any*
> constraints other than simple bounds, hence the (non-) and (in) in
> parentheses.
>
>   
>>> Did I just miss it?  The only things I see are methods that can only
>>> handle simple bounds, or don't make use of derivative info.
>>>
>>>       
>> It seems to me I had seen in scipy.optimize solver(s) that allow(es) to
>> handle nonlinear inequality constraints (with derives), but not
>> equality.
>>     
>
> Here's what there is:
> fmin - simplex method, no derivs no constraints
> fmin_powell - powell's method, no derivs no constraints
> fmin_cg - uses derivs, no constraints
> fmin_ncg - uses derivs (and hessian), no constraints
> fmin_bfgs - uses derivs, no constraints
> fmin_l_bfgs_b - uses derivs, bounds only
> fmin_tnc - uses derivs, bounds only
> fmin_cobyla - no derivs, but non-linear constraints
>
> So again the question... did I miss anything?  It seems like there's a
> hole in the category of "uses derivs, supports constraints".
>
>   
Sorry, maybe I saw the ones in Octave-forge repository
>> There are very small % of NLP solvers that are able to handle
>> equality constraints. Also note please that many SQP/rSQP solvers can
>> handle equality, but not inequality constraints, so amount of NLP
>> solvers capable of handling both eq & ineq is very small. Usually it is
>> based in method of linearization. Afaik there is free IPopt (but it has
>> GPL license) from COIN-OR project, written in C++, and some commercial,
>> for example KNitro. There was a Ukrainean academician Pshenichniy, who
>> had spend dozens of years to research in linearization-based
>> optimization methods, but some months ago he died.
>> BTW in his book "Linearization method" (1983) he says very important
>> observation:
>> "multiyears practice of solving optimization problems made specialists
>> think, that there can't be universal NLP algorithm, that successfully
>> enough solves ALL problems" (and that he is agree with the statement, as
>> well as I do). I would explain the statement with my own args, but it
>> requires much English-written text, so let me omit the one here.
>> And some lines below Pshenichniy continue:
>> "Practical experience shows, that there are a sets of problems, where an
>> algorithm, that seems to be the most ineffective from the theoretical
>> point of view, turns out to yield good results, due to specific of
>> problem. Hence, a number of different algorithms is required."
>> An alternative approach (to constructing a single universal solver, like
>> some do) can be like TOMLAB (or like in my OpenOpt): assignment of
>> problem to single object + trying different solvers. And, of course,
>> observing convergence pictures, because just single output <f_opt,
>> x_opt, time_elapsed> can be very uninformative in many cases.
>>     
>
> All very interesting, but I'm not sure what point you're trying to make.
> I'd be happy to try different solvers on my problem, and in fact I
> have tried a couple.  The BFGS seem to work pretty well if I start
> from a feasible point, but it makes me a little nervious using them
> since the values of my function are bogus outside the feasible region.
>   

>  I'm just setting f(x) to HUGE_NUM outside the feasible region.
> fmin_tnc did *not* work. It seems to take a step out of bounds and get
> lost.
>   
Since fmin_tnc uses  derives, of course it will fail to solve the 
problem with HUGE_NUM outside the feasible region.
You should either search for BSD (or other appropriate license) solver 
outside the scipy optim solvers bunch, or use penalty coefficients.
BTW ralg is capable of successfully handling very huge penalties, and 
this is one more reason why our dept use the solver very often in our 
software.
So, if your problem is smooth, you can use something like
F = lamda x: f(x) + N*sum(c[i](x)**2) + N*sum(h[i](x)**2)
(for constraints c[i](x) <= 0, h[i](x) = 0)
so you should rise the N until your solution will become feasible, in a 
cycle or somehow else.
If you use nonsmooth optimizer (like ralg), it's better to handle 
penalties as
F = lamda x: f(x) + N*sum(abs(c[i](x))) + N*sum(abs(h[i](x)))

Automitic turning of penalty coefficients (in Naum Z.Shor r-alg) is 
implemented for example in my OpenOpt for MATLAB/Octave or in SolvOpt by 
Alexey Kuntsevich  for C/Fortran/MATLAB (2001) (also our department 
worker). But for Python it's not done yet, as well as smooth NLP 
optimizer that I promised in my GSoC project.

WBR, D.