[Scilab-Dev] Fwd: Optimization

[michael.baudin at contrib.scilab.org]

Hi,

One particular point that you may not be aware of is that
the unconstrained and the constrained algorithms are different.
This is not one single, constrainted, algorithm which is used either
with bounds or with infinite bounds: these are two different
routines.
This is why setting infinite bounds such as [-inf,inf] may not have any 
numerical
interest: the unconstrained version should be used in this case.

In your message, you state that "all components are stricly in [0,1]",
but I can see that 1.04>1, so that if the upper bound is set to 1, this
bound will be active.
On the other hand, if the bounds were not active (but they are), the 
difference
between the unconstrained and the constrained algorithms should be
insignificant.

So, my guess is that the reason why the LBFGSB0inf algorithm has a 
nonzero
gradient is because some constraint is active, which prevents the
algorithm to converge to an unconstrained minimum :
it has to respect some bound.

My own experience with the "gc" algorithm is that there are very
few cases in which this algorithm outperforms the default "qn" 
algorithm.
More precisely, the "gc" algo. is designed to manage large problems,
but I was not able to create a problem where "qn" fails because of a 
lack of
memory, and were "gc" succeeds.
I guess that this is because the implementation in Scilab uses the 
maximum
available memory to compute the number of vectors in the L-BFGS algo.
In practice, if "qn" fails because it has not enough memory,
"gc" also fails, either because it requires more memory than Scilab can
give, or because it does not converge at all.

Best regards,

Michaël

PS
A document which might be of some interest to you is "Optimization in 
Scilab",
where the chapter 2 is on nonlinear optimization :

http://forge.scilab.org/index.php/p/docoptimscilab/downloads/



Le 2012-11-16 00:34, Jean-Pierre Dussault a écrit :
> Reposted with pdf figure instead of too big scg
>
>  JPD
>
>  -------- Message original --------
>
>  		SUJET:
>  		Optimization
>
>  		DATE :
>  		Thu, 15 Nov 2012 18:27:47 -0500
>
>  		DE :
>  		Jean-Pierre Dussault <Jean-Pierre.Dussault at Usherbrooke.CA>
>
>  		POUR :
>  		dev at lists.scilab.org
>
>  Hi all,
>
>  I am preparing examples for an optimization course for students in
> image science. I use an example from
> 
> http://www.ceremade.dauphine.fr/~peyre/numerical-tour/tours/optim_1_gradient_descent/
> [1] to promote the use of better algorithms than the simple gradient
> descent.
>
>  I attach the convergence plot of the norm of the gradient for 5
> variants of the optim command: gc unconstrained, gc with bounds
> [-%inf,%inf], gc with bounds [0,1], gc with bounds [0,%inf] and nd. I
> also include the gradient descent.
>
>  Except for the [0,%inf] variant, the solution has all components
> strictly in [0,1] as displayed here:
>
>> 
>> -->[max(xoptS),max(xoptGC),max(xoptGCB),max(xoptGCBinf),max(xoptGCB0inf),max(xoptND)]
>> ans =
>>
>> 0.9249840 0.9211455 0.9216067 0.9213056 1.0402906 0.9212348
>>
>> 
>> -->[min(xoptS),min(xoptGC),min(xoptGCB),min(xoptGCBinf),min(xoptGCB0inf),min(xoptND)]
>> ans =
>>
>> 0.0671743 0.0718204 0.0678885 0.0714951 0.0772300 0.0714255
>  On the convergence plot, we clearly see that the gradient norm of
> the gc with [0,1] bounds stalls away from zero while with no bounds 
> or
> infinite bounds, it converges to zero. This is even more severe for
> the variant with bounds [0.%inf], which no more approaches the
> solution, making virtually no progress at all after some 30 function
> evaluations.
>
>  Is it a Scilab bug or a bad example for the gcbd underlying routine?
> The cost function is strongly convex of dimension 65536. Has someone
> experienced a similar behavior?
>
>  This is unfortunate since I wish to convince my students to use
> suitably constrained models instead of enforcing constraints
> afterward.
>
>  Thanks for any suggestion to work around this troublesome situation.
>
>  JPD
>
>
>
> Links:
> ------
> [1]
> 
> http://www.ceremade.dauphine.fr/%7Epeyre/numerical-tour/tours/optim_1_gradient_descent/
>
> _______________________________________________
> dev mailing list
> dev at lists.scilab.org
> http://lists.scilab.org/mailman/listinfo/dev