2

Usually I use Mathematica, but now trying to shift to python, so this question might be a trivial one, so I am sorry about that.

Anyways, is there any built-in function in python which is similar to the function named Interval[{min,max}] in Mathematica ? link is : http://reference.wolfram.com/language/ref/Interval.html

What I am trying to do is, I have a function and I am trying to minimize it, but it is a constrained minimization, by that I mean, the parameters of the function are only allowed within some particular interval.

For a very simple example, lets say f(x) is a function with parameter x and I am looking for the value of x which minimizes the function but x is constrained within an interval (min,max) . [ Obviously the actual problem is just not one-dimensional rather multi-dimensional optimization, so different paramters may have different intervals. ]

Since it is an optimization problem, so ofcourse I do not want to pick the paramter randomly from an interval.

Any help will be highly appreciated , thanks!

hnk
  • 2,216
  • 1
  • 13
  • 18
string
  • 102
  • 1
  • 11
  • If your problem is convex and continuous in the domain, you could simply build a generalized gradient descent solver with constraints viz. your interval. – hnk Jul 12 '14 at 03:54
  • I am not quite sure what did you mean. Actually the problem in hand is highly non-linear multi-dimensional problem, and I would go for Simplex method of minimization which does not need the gradients. I just need to restrict the parameter interval. – string Jul 12 '14 at 04:01
  • how will you use simplex for a highly non-linear problem? – hnk Jul 12 '14 at 04:02
  • Check out http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html#scipy.optimize.minimize – Happy001 Jul 12 '14 at 04:04
  • @ Happy001, I have already searched in scipy page, for some reason their documentations are always vague to me :-| – string Jul 12 '14 at 04:21
  • [This link](http://scipy-lectures.github.io/advanced/mathematical_optimization/#box-bounds) might be useful (look at section box constraints). There is so much stuff implemented out there in a decent way that I wouldn't go about writing my own algorithm withouta good reason. – Ioannis Jul 13 '14 at 06:55
  • @ Ioannis, the link you provided is certainly helpful, thank you for your help :-) – string Jul 14 '14 at 15:12

1 Answers1

0

If it's a highly non-linear problem, you'll need to use an algorithm such as the Generalized Reduced Gradient (GRG) Method.

The idea of the generalized reduced gradient algorithm (GRG) is to solve a sequence of subproblems, each of which uses a linear approximation of the constraints. (Ref)

You'll need to ensure that certain conditions known as the KKT conditions are met, etc. but for most continuous problems with reasonable constraints, you'll be able to apply this algorithm.

This is a good reference for such problems with a few examples provided. Ref. pg. 104.

Regarding implementation:

While I am not familiar with Python, I have built solver libraries in C++ using templates as well as using function pointers so you can pass on functions (for the objective as well as constraints) as arguments to the solver and you'll get your result - hopefully in polynomial time for convex problems or in cases where the initial values are reasonable.

If an ability to do that exists in Python, it shouldn't be difficult to build a generalized GRG solver.

The Python Solution:

Edit: Here is the python solution to your problem: Python constrained non-linear optimization

Community
  • 1
  • 1
hnk
  • 2,216
  • 1
  • 13
  • 18
  • I had no idea about this GRG method. Previously I used Simplex method in Mathematica, which is actually the Nelder-Mead Algorithm. Anyways, I thought the my question should have a straight forward answer by defining an interval for the parameter (forgetting about the minimization issue). Now seems like everything is so involved. Btw, thanks for the links, I have no idea about those methods, so I will look them up in details and figure out whether it helps. – string Jul 12 '14 at 04:18
  • Well, I'm surprised that you could use regular simplex for a highly non-linear problem (unless the problem was approximately linear within the interval and hence simplex gave a close enough answer). But if you'd like to use the Nelder Mead method, here is a reference example in Excel which you could study and implement: http://www.personal.soton.ac.uk/rchc/NATCOR/Examples/NelderMeadDemo.xls – hnk Jul 12 '14 at 04:22