Matrix-free optimization

[Ives Macêdo]

Hi there,

I'm trying to use ALGENCAN (through it's Matlab interface) to solve optimization problems treating the involved matrices as linear operators (without storing densely nor sparsely the matrix entries).

I understand that I can do part of that by implementing evalhlp for the action of the Hessian of the Augmented Lagrangian at given point on a given vector.

However, I'm not sure how to deal with that when it comes to the Jacobian of the constraints...

Can anyone provide me some light on this matter?

As a reference, you can think that I'm solving QPs in the form:

minimize 1/2*x^T*H*x + c^T*x

subject to Ax=a, Bx<=b and l<=x<=u

Cheers,

Ives

[Ernesto G. Birgin]

Dear Ives,

Many thanks for your interest in Algencan.

Can you provide the Jacobian of the constraints, performing products of the Jacobian matrix with canonical vectors, within evalgjac suboroutine? Or are you suggesting that A and B are so large that they non-null elements can not be stored? How large are they?

If this the case, you will need to code the gradient of the Lagrangian by yourself (in way similar to the one evalhlp is coded). However, there is not Matlab interface for such subrotuine and you should provide the interfacing subroutine Fortran-to-C-to-Matlab too. It would be easier to use the stand-alone Fortran version of Algencan in this case, in order to avoid coding those interfacing subroutines.

Regards,
Ernesto.

[Ives Macêdo]

Hi Ernesto, thank you very much for the prompt response.

I thought that would be the case, but wouldn't hurt to ask...

So, one example of such a Jacobian might be a (possibly reduced) discrete cosine transform, for which there are fast algorithms to compute its action on a given vector without storing its actual entries. If I evaluated this action on a set of canonical vectors the advantage of using a fast transform instead of the actual matrix would be moot.

Is there any real requirement on the already implemented subproblem solvers that the Jacobian be given or it would be enough to compute the gradient of the Augmented Lagrangian? If this is possible (and I understand that such functionality is not implemented in the current version), where would I be required to modify the code to do this? Any help in this regard would be very much appreciated.

Best,

Ives

[Ernesto G. Birgin]

Hi! The subroutine to be modified is evalnl, that computes the gradient of the Lagrangian. To perform this task, it calls the user supplied subroutines evalg and evaljac, or, evalgjac. Then, it computes the sum of those (sparse) gradients using some given coeffcients. You can find evalnl subroutine within file sources/algencan/evalal. But what I just said means that gradients of the constraints are needed in some way or another. Ernesto.

On Tuesday, May 8, 2012 7:01:11 PM UTC-3, Ives Macêdo wrote:

[Ives Macêdo]

If that's all I need to do, that's awesome!

If I manage to get this working, I'll post it here just in case that might interest anyone...

Just FYI, I had to change one line (1084) in matlabwrapper64.f to be able to compile the Matlab interface it in my Macbook Pro running Snow Leopard and Matlab R2011a with Apple's standard compiler (from Xcode) and R's gfortran (version 2.4.3). The change was:

from:

      call mxCopyReal8ToPtr(lambda,mxGetPr(prhs(4)),integerToMwSize(m))

to:

      call mxCopyReal8ToPtr(lambda,mxGetPr(prhs(4)),

     +integerToMwSize(m))

I have no idea why (I'm not really a FORTRAN programmer), but that did the trick.

I also had to use my own mexopts.sh file adding the full path to gfortran and the flag -xf77-cpp-input to FFLAGS and call mex by hand from the Matlab Command Window. I'm only saying all this in case someone else is trying to figure out how to make this work without installing older versions of the compilers...

Thanks a lot!

Cheers,

Ives

[Ernesto G. Birgin]

Many thanks for your feedback. Full instructions about how to compile Algencan plus the Matlab interface in your platform would be great! Regards, Ernesto.

On Tuesday, May 8, 2012 7:01:11 PM UTC-3, Ives Macêdo wrote:

[Ives Macêdo]

What I had to do was:

1) change line 1084 in algencan-2.3.7/sources/interfaces/matlab/matlabwrapper64.f from:

      call mxCopyReal8ToPtr(lambda,mxGetPr(prhs(4)),integerToMwSize(m))

to:

      call mxCopyReal8ToPtr(lambda,mxGetPr(prhs(4)),

     +integerToMwSize(m))

2) open Matlab and run:

>> mex -setup

then choosing option 1 for the gcc compiler options.

3) copy ~/.matlab/R2011a/mexopts.sh to algencan-2.3.7/sources/interfaces/matlab/

4) in the maci64 block of algencan-2.3.7/sources/interfaces/matlab/mexopts.sh change FC='gfortran' to FC=/usr/local/bin/gfortran and add the flag -xf77-cpp-input to FFLAGS (which now reads FFLAGS='-fexceptions -m64 -fbackslash -xf77-cpp-input')

5) from Matlab change the directory to algencan-2.3.7/sources/interfaces/matlab/ and run the command:

>> mex -largeArrayDims -I../../algencan ../../algencan/algencan.f ../../algencan/auglag.f ../../algencan/backtrack.f ../../algencan/betra.f ../../algencan/calc.f ../../algencan/cgm.f ../../algencan/dogleg.f ../../algencan/drand.f ../../algencan/evalal.f ../../algencan/extrap.f ../../algencan/gencan.f ../../algencan/happrox.f ../../algencan/lss.f ../../algencan/moresor.f ../../algencan/newtd.f ../../algencan/newtonkkt.f ../../algencan/scl.f ../../algencan/setpoint.f ../../algencan/sevalus.f ../../algencan/spgls.f ../../algencan/tevalus.f ../../algencan/tnls.f ../../algencan/uevalus.f ../../algencan/vevalus.f ./checkderm64.f ./fparamm64.f ./matlabwrapper64.f

My system is a MacBook Pro with an Intel Core 2 Duo CPU running Snow Leopard (version 10.6.8) and Matlab R2011a with the Xcode (version 3.2.6) gcc and the gfortran build (version 4.2.3) provided by the R-project in http://cran.r-project.org/bin/macosx/tools/

To make people's life easier, I've attached the files I've changed (mexopts.sh and matlabwrapper64.f which should overwrite those in algencan-2.3.7/sources/interfaces/matlab/) and the line above in a .m file which should be ran inside Matlab from the directory algencan-2.3.7/sources/interfaces/matlab/

That's how it worked for me. One note, I was able to successfully run the script algencanma.m even though the compilation flags the 3 warnings below:

./fparamm64.f:470: warning: no newline at end of file

ld: warning: in /Developer/SDKs/MacOSX10.6.sdk/usr/local/lib/gcc/i686-apple-darwin8/4.2.3/libgfortranbegin.a, file was built for unsupported file format which is not the architecture being linked (x86_64)

ld: warning: in /Developer/SDKs/MacOSX10.6.sdk/usr/local/lib/gcc/i686-apple-darwin8/4.2.3/libgcc.a, file was built for unsupported file format which is not the architecture being linked (x86_64)

The first one is really nothing, but the other two seem to indicate some sort of mismatch with the gfortran build from the R-project and the code generated by gfortran itself. But again, algencanma.m called the FORTRAN code and didn't crash...

Hope that helps other people...

Best,

Ives

P.S.: Thanks a lot for making ALGENCAN available! :)