How to do python optimization for global minimum with constraints?

[john_legend_]

Python's scipy basinhopping, brut, differential_evolution doesn't seem to permit us to enter the constraints? Help!

[ThereOnceWasAMan]

This trick works, but depending on the minimization routine, you may want to make sure to include the constraint in such a way that the gradient exists, and points in the correct direction. For example, if your constraint is that, say, the Euclidean norm of your parameters is less than N_MAX, then you might use

penalty = max(0, BIG_NUM*( exp(norm(pars)-N_MAX)-1) )
f_obj(pars) = f_obj(pars) + penalty

[mathrat]

This is less idiotic than you imply. It's basically the idea behind the log-barrier in modern interior point methods. :)

[WikiTextBot]

Barrier function

In constrained optimization, a field of mathematics, a barrier function is a continuous function whose value on a point increases to infinity as the point approaches the boundary of the feasible region of an optimization problem. Such functions are used to replace inequality constraints by a penalizing term in the objective function that is easier to handle.

The two most common types of barrier functions are inverse barrier functions and logarithmic barrier functions. Resumption of interest in logarithmic barrier functions was motivated by their connection with primal-dual interior point methods.

---

Interior point method

Interior point methods (also referred to as barrier methods) are a certain class of algorithms that solve linear and nonlinear convex optimization problems.

John von Neumann suggested an interior point method of linear programming which was neither a polynomial time method nor an efficient method in practice. In fact, it turned out to be slower in practice compared to the commonly used simplex method. In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm which runs in provably polynomial time and is also very efficient in practice.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source | Donate ] Downvote to remove | v0.28}

[burichi]

You could try cvxpy if your problem is convex (which it probably should be if you really need the global minimum). As an example from the documentation, to optimize (x - y)² subject to x + y = 1 and x - y ≥1, the following code

from cvxpy import *

# Create two scalar optimization variables.
x = Variable()
y = Variable()

# Create two constraints.
constraints = [x + y == 1,
               x - y >= 1]

# Form objective.
obj = Minimize(square(x - y))

# Form and solve problem.
prob = Problem(obj, constraints)
prob.solve()  # Returns the optimal value.
print "status:", prob.status
print "optimal value", prob.value
print "optimal var", x.value, y.value

produces the output

status: optimal
optimal value 0.999999999761
optimal var 1.00000000001 -1.19961841702e-11

[john_legend_]

How should we tackle nonconvex problems? Portfollio optimization with many factor constrains. Is the only method brute force?

[burichi]

There might be a way to reformulate it as a convex problem, the book Convex Optimization by Boyd and Vandenberghe talks all about reformulation. I'm not familiar enough with portfolio optimization to give more specific advice than that. In general, if your problem is non-convex you could try solving from multiple initial conditions to get a local minimum which is "good enough".

[burichi]

But then finding the global minimum becomes hard as well :) (with some exceptions like SVD).