C# LP/Lagrange with Bounded Variables

Summary: How would I go about solving this problem?

Hi there,

I'm working on a mixture-style maximization problem where my variables are going to be bounded by minima and maxima. A representative example of my problem might be:

maximize: (2x-3y+4z)/(x^2+y^2+z^2+3x+4y+5z+10)
subj. to: x+y+z=1
          1 < x < 2
         -2 < y < 3
          5 < z < 8
where numerical coefficients and the minima/maxima are given.

My final project is involving a more complicated problem similar to the one above. The structure of the problems won't change- only the coefficients and inputs will change. So with the example above, I would be looking for a set of func开发者_JAVA技巧tions that might allow a C# program to quickly determine x, then y, then z like:

x = f(given inputs)
y = f(given inputs,x)
z = f(given inputs,x,y)

Would love to hear your thoughts on this one!

Thanks!

The standard optimization approach for your type of problem, non-linear minimization, is the Levenberg-Marquardt algorithm:

• Levenberg–Marquardt algorithm

but unfortunately it does not directly support the linear constraints you have added. Many different approaches have been tried to add linear constraints to Levenberg-Marquardt with varying success.

Another algorithm I can recommend in this situation is the Simplex algorithm:

• Nelder–Mead method

Like the Levenberg-Marquardt, it also works with non-linear equations but handles linear constraints which act like discontinuities. This could work well for your case above.

In either case, this is not so much a programming problem as an algorithm selection problem. The literature is rife with algorithms and you can find C# implementations of either of the above with a little searching.

You can also combine algorithms. For example, you can do a preliminary search with Simplex with the constraints and the refine it with Levenberg-Marquardt without the constraints.

If your problem is that you want to solve linear programming problems efficiently, you can use Cassowary.net or NSolver.

If your problem is implementing a linear programming algorithm efficiently, you may want to read Combinatorial Optimization: Algorithms and Complexity which covers the Simplex algorithm in most of the detail provided in the short text An Illustrated Guide to Linear Programming but also includes information on the Ellipsoid algorithm, which can be more efficient for more complex constraint systems.

There's nothing inherently C#-specific about your question, but tagging it with that implies you're looking for a solution in C#; accordingly, reviewing the source code to the two toolkits above may serve you well.