Ask Your Question
1

Non-linear programming

asked 2011-03-11 03:43:18 -0500

MassimoLauria gravatar image

updated 2011-03-12 01:01:23 -0500

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 flag offensive close merge delete

Comments

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

Shashank gravatar imageShashank ( 2011-03-11 07:38:25 -0500 )edit

I'll try to make the question more clear.

MassimoLauria gravatar imageMassimoLauria ( 2011-03-12 00:53:04 -0500 )edit

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

Dima gravatar imageDima ( 2011-04-23 07:42:22 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
2

answered 2011-04-19 08:47:19 -0500

benjaminfjones gravatar image

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[0]+2.0*u[1]-1) # x1 <= (-1/2)*x0 + 1/2
c3 = lambda u: 5.0-u[0] # x0 and x1 less than 5 
c4 = lambda u: 5.0-u[1]
c5 = lambda u: u[0]-0.1 # x0 and x1 bigger than 0.1
c6 = lambda u: u[1]-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], 0.1, 5), (x[1], 0.1,5))
P += point3d((p[0],p[1],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)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2011-03-11 03:43:18 -0500

Seen: 810 times

Last updated: Apr 19 '11