Adding support for Manifolds to Nelder-Mead

[danspielman]

I did this in the obvious way: retract! is applied to every vector created by Nelder-Mead. I have found this very useful for doing optimization over complicated manifolds. I used to handle optimizations of this sort by using an objective function of the form x -> obj( retract (x)). But, this causes Nelder-Mead to operate in the wrong space. Using the manifold approach has sped up some of my code a lot, and has allowed it to converge in situations that failed before.

[codecov[bot]]

Codecov Report

Merging #872 into master will increase coverage by 0.07%. The diff coverage is 93.33%.

@@            Coverage Diff             @@
##           master     #872      +/-   ##
==========================================
+ Coverage   82.07%   82.15%   +0.07%     
==========================================
  Files          43       43              
  Lines        2778     2790      +12     
==========================================
+ Hits         2280     2292      +12     
  Misses        498      498              

Impacted Files	Coverage Δ
...c/multivariate/solvers/zeroth_order/nelder_mead.jl	85.52% <93.33%> (+1.24%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 19c74be...1e00f2e. Read the comment docs.

[pkofod]

Hi, thanks! And sorry for the very late response. I've been finishing up my thesis in the fall and have had little time for these projects. We could move the retraction inside of the centroid call and just have the centroid call accept the method, but this solution also looks fine. HAve you run into any issues since October? If not, I'll merge this. Again, apologies for the late response.

[danspielman]

Dear Patrick,

There is no need to apologize! I assure you that I am slower to handle pull requests on my (less used) packages. Really, I only handle them over breaks.

I am still using manifolds with Nelder-Mead, and still find it very useful.

BTW, if you like I would be happy to add support for the manifold of PSD matrices if someone else hasn’t done it yet. I use them often.

Best wishes, Dan

On Wed, Dec 16, 2020 at 3:44 PM Patrick Kofod Mogensen < [email protected]> wrote:

Hi, thanks! And sorry for the very late response. I've been finishing up my thesis in the fall and have had little time for these projects. We could move the retraction inside of the centroid call and just have the centroid call accept the method, but this solution also looks fine. HAve you run into any issues since October? If not, I'll merge this. Again, apologies for the late response.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/JuliaNLSolvers/Optim.jl/pull/872#issuecomment-746985385, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJKRL2FNRX2EJNVF7ENRDSVEL2JANCNFSM4SB26SUA .

-- Sent from mobile phone

[pkofod]

BTW, if you like I would be happy to add support for the manifold of PSD matrices if someone else hasn’t done it yet. I use them often.

Are you in the #manifolds channel on the julia slack? I asked a question about this earlier today. It was my impression that PSD matrices do not live on a manifold, only PD matrices.

Edit: Oh, looking at your comment time stamp you mentioned this before I asked on slack. Interesting coincidence.

[danspielman]

I haven't looked at that channel. I'll check it out.

I'll admit that I don't use slack much. But, I'll try to start.

Best, Dan

On Tue, Dec 22, 2020 at 1:42 PM Patrick Kofod Mogensen < [email protected]> wrote:

BTW, if you like I would be happy to add support for the manifold of PSD matrices if someone else hasn’t done it yet. I use them often.

Are you in the #manifolds channel on the julia slack? I literally asked a question about this earlier today.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/JuliaNLSolvers/Optim.jl/pull/872#issuecomment-749712620, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJKRLNIJPS7PRA3P6KG3DSWDSBRANCNFSM4SB26SUA .

[kellertuer]

Cool!. Alternatively you could check out the symmetric positive definite manifold from Manifolds https://juliamanifolds.github.io/Manifolds.jl/latest/manifolds/symmetricpositivedefinite.html and use nelder mead with that manifold in Manopt.jl, see https://manoptjl.org/stable/solvers/NelderMead.html

Or check the symmetric positive semidefinite manifold of fixed rank matrices https://juliamanifolds.github.io/Manifolds.jl/latest/manifolds/symmetricpsdfixedrank.html – I haven't checked plain semidefinite symmetric matrices yet.

[pkofod]

Or check the symmetric positive semidefinite manifold of fixed rank matrices https://juliamanifolds.github.io/Manifolds.jl/latest/manifolds/symmetricpsdfixedrank.html – I haven't checked plain semidefinite symmetric matrices yet.

Are you stealing my users on a PR in my own package? :scream:

:rofl:

[kellertuer]

Maybe ;)

One could also take the manifold mentioned as a starting point to add it here.