# Non-linear programming

I would like to minimize a non-linear function with Sage.

More precisely I would like to find the numerical minimum of a function $\sum_{i=1}^{n} a_i \log \frac{1}{x_i}$ where the variables $x_i$ are subjected linear constraints, while $a_i$ are known coefficients.

Thus the constraints are essentially similar to the ones of a continuous linear program. And now I would like to set up the objective function and solve.

Since this is not a linear program I wonder how to do it in Sage. Is there a way? I thought that since the function is concave, a routine for convex optimization should work.

edit retag close merge delete

Are you trying to minimize the function numerically or analytically? And what is the the variable with respect to which you wish to minimize? I don't know whether this helps but try looking at the command "minimize_constrained". You can find more about the command on http://www.sagemath.org/doc/reference/sage/numerical/optimize.html

for minimizing, you need convexity, not concavity.... Anyhow, writing the function as $-\sum_i a_i\log x_i$ looks more meaningful.

Sort by » oldest newest most voted

This question has been sitting here for a while with no answer. I had to do something like this myself recently, so I thought I'd post an answer.

Here is some sample code that you could adapt to your situation. I've used 2 variables for illustration, but most of the code only depends on the value of n set at the top. The code at the bottom displays a 3d plot of your function, the minimum, and a contour line indicating the constraint I choose.

n = 2
x = var(",".join(["x%d" % i for i in range(n)]))
a = [-2, 3] # length n
f = sum([a[i]*log(1/x[i]) for i in range(n)])

# constraints: either test functions (should be positive in region) or intervals
c2 = lambda u: -1*(u+2.0*u-1) # x1 <= (-1/2)*x0 + 1/2
c3 = lambda u: 5.0-u # x0 and x1 less than 5
c4 = lambda u: 5.0-u
c5 = lambda u: u-0.1 # x0 and x1 bigger than 0.1
c6 = lambda u: u-0.1
# I1 = (0.1, 5)  # uncomment if you just want intervals
# I2 = (0.1, 5)

# initial point
p0 = (0.1,0.1)

# find a minimum and evaluate f there
# p = minimize_constrained(f, [I1, I2], p0) # uncomment if you just want intervals
p = minimize_constrained(f, [c2, c3, c4, c5, c6], p0)
eval_dict = dict([ ("x%d" % i, p[i]) for i in range(n) ])
fmin = f(**eval_dict) # evaluate f at arbitrarily many inputs
print "min occurs at p = ", p, "fmin = ", fmin

# show the minimum and constraints
P = plot3d(f, (x, 0.1, 5), (x, 0.1,5))
P += point3d((p,p,fmin), size=20, color='red')
P += parametric_plot3d([lambda s:s, lambda s: -(1/2)*s+1/2, lambda s: f(x0=s, x1=-(1/2)*s+1/2)], (0.1, 0.9),color='red')
show(P)

more