Nonlinear solver in breeze

[jie liu]

Hi, 

I am using the nonlinear solver in breeze recently. https://github.com/scalanlp/breeze/blob/master/math/src/main/scala/breeze/optimize/proximal/NonlinearMinimizer.scala

It seems to be a general nonlinear solver. Is there any formal document about this solver? 

Is breeze tested against large scale problems for this solver? 

Thanks,

Jie

[David Hall]

The doc comments are the only documentation I know about for this class. 

Debasish, I don't know if you can weigh in with more specifics? Thanks!

--
You received this message because you are subscribed to the Google Groups "Scala Breeze" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-breeze...@googlegroups.com.
To post to this group, send email to scala-...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/scala-breeze/22149ffd-ff70-4230-ba39-113d8e76467b%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Debasish Das]

Hi Jie,

For formal documentation you can refer to ADMM papers by Professor Boyd.

Idea here is to solve f(x) + g(z) using admm where f(x) is smooth and g(z) has a proximal operator defined....I have benchmarked it with OWLQN and they were at par for L1 constraint...Of course due to generic nature of g(z) you can solve lot many constraint problems than L1....It integrates to Spark in the same way that OWLQN / LBFGS is integrated with Spark right now. I have not got time to show examples of spark integration through a spark package...As soon as I get time I will add it...in general if you get into issues or need any pointers on how to use it, I should be able to help you out...Are you looking for an example spark integration to understand how it can be used to solve large scale problems ? I can add it if needed...if you are looking for more interesting constraints let me know the usecase.

Thanks.
Deb

[jie liu]

Hi Deb,

Thank you very much! I am not familiar the method you mentioned. Seems that as long as the problem is convex, it should work. I am a little confused about the representation f + g, where g is the constraint. Do you mean something like a penalty on the constraint?   f + \lambda g? I will read the paper first. 

My problem has some nonlinear constraints. So I just use your method as a building block to solve a box constrained subproblem. I also met some issues where the box constraints is violated. But I guess there might be other reasons. Right now I cannot reproduce it. Hopefully I can get back to you with more details and receive more help from you. 

Thank you, 

Jie 

You received this message because you are subscribed to a topic in the Google Groups "Scala Breeze" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/scala-breeze/nbOiU9cdi2k/unsubscribe.
To unsubscribe from this group and all its topics, send an email to scala-breeze...@googlegroups.com.

To post to this group, send email to scala-...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/scala-breeze/CA%2BB-%2BfwDizDktYogq28%3DQ_x6HDT4EjArw-8qgRk1%2BD0gXkZ3mQ%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Jie Liu

[Debasish Das]

g is the proximal representation of constraint...

I will give you few examples:

f(x) = x^2

s.t x >= 0

Here you can write x >= 0 as a proximal function (a list of proximal are already implemented in Proximal.scala, take a look into them)

ADMM solver f(x) + g(z) s.t x = z 

g(z) = prox(z : z >= 0)

parameter tuning is through ADMM algorithm.

Another example:

Cost(x) = x^2 + L1(x)

f(x) = x^2 

g(z) = proximal(L1(z))

Again there are proximal formulation for L1(z)

ADMM will solve f(x) + g(z) s.t x = z 

The equality constraint in ADMM is interesting since you can model more things than FISTA using this formulation. 

For practical use-cases just the simple variant is fine but ADMM as formulation can solve the following as well and can act as a fast alternative to interior point method if the problem is well conditioned and you are fine with an approximate answer...

f(x) + g(z) s.t Ax + Bz = C

I have ECOS solver on Spark/Scala as well if you want to experiment with interior point solvers but that did not scale beyond 20K variables when I last experimented with it.

https://github.com/embotech/ecos-java-scala

Let me know your problem file and I can look into it why it failed. 

I have references for paper in the code as well.