How to specify equality constraints in constrained nonlinear optimization

[Vills]

Dear Members,

I am trying to solve a constrained nonlinear optimization problem, which involves 6 variables (and possibly more). Attached is the problem formulation. I started writing a program using the example VI "Find Global Min on Surface.vi". I assumed that though this VI is written for 2 variables, it will also work for larger number of variables. The sub VI "Find Global Min On Surface_Func.vi" shows a template of how to define the objective function and equality/inequality constraints. However, it does not really provide much documentation on how to specify those constraints.

There is another example "Linear Programming Simplex Method.vi", in which it is relatively clearer how to specify the equality constraints using matrix M and vector B. However, "Find Global Min on Surface_Func.vi" does not have similar matrix/vector type of inputs to specify constrains. I am also not sure if there is a way to somehow use "Linear Programming Simplex Method.vi" to implement the constraints in "Find Global Min on Surface_Func.vi".

I also looked at another example, “Linear Programming for nD Variables.vi”, which gives a very good facility to describe the constraints in string format, which are then parsed into appropriate equations. However, I cannot easily use this VI, because the function in the instant case, is quite complex involving about 30 constants and higher powers (up to 7) of independent variables. It will really be a long string, which I will have to change programmatically every time.

Any help would be greatly appreciated.

[Bob_Schor]

Wait a minute -- are you putting "constraints" on the "data" variables (x's and y's)?  Normally I think of "constraints" as being placed on the fitting parameters (the a's and b's), e.g. "How many red balls and how many blue balls best fill this container, with the constraint that there cannot be a negative number of balls".  If I understand your formulation, you seem to say "Find the best fit using a set of data points (which are a "given") that are all in the positive octant (x, y, z are all >= 0).

Bob Schor

[Vills]

Hi Bob,

Thank you so much for the response! Yes, the constraint is on the Xs and Ys to be in the positive octant, so we need to actually vary the values of x and y, so that the functions F will result in approximately equal values. The aij, bij and cij are constants, where i=0 to 7 and j=0 to 6. You guidance is very much needed.

Thank you,

Vilas

[Bob_Schor]

I regret to say that I don't understand at all what you are trying to do.  I have no idea which values represent "known" quantities, which represent "parameters", what the model function is that you are trying to optimize (or, alternatively, what equation(s) bind the variables and parameters).  Though I've done parameter estimations and curve/plane fitting, almost nothing you said makes sense to me (but that could well be a language or paradigm-misunderstanding problem on my part).  Sorry.

Bob Schor

[Vills]

Hi Bob,

To avoid confusion, without getting into too much details, please think of this as any other general minimization problem. In such a case, can you please help me in understanding how would you write the constraints in "Find Global Min on Surface.vi"? The numeric control for Equality Constraints, in this VI, is a 1D array. Now, if I have multiple constraints, how can I express all those equations in the form of a single 1D array? All the subVis of this top level VI are written only for a 1D constraint. Please help.

Thank you,

Vilas

[Bob_Schor]

Ah, now I think I'm beginning to understand what you are thinking.  I'm going to have to do a little homework, myself, but I'll try to help you...

Bob Schor

[Bob_Schor]

Well, that was quick -- I found the "Find Global Min on Surface" VI in the examples, and boy, is that messy code!  And such wonderful, largely-non-existent Documentation, too!

But never mind.  I started thinking about how, not knowing anything about this series of VIs whose function I don't understand and whose behavior I haven't tested (and thus am not sure I believe), I would solve the following problem:

Given a function f(x, y, z), find the minimum value of this function for (x, y, z) subject to the constraints x>0, y>0, z>0 and (x, y, z) lies on the surface of a unit sphere.

"When Life Gives You a Lemon, Make Lemonade!", or "Think like a Mathematician".

I'm going to transform this problem from Cartesian to Spherical Polar Coordinates, r, theta, phi, where r = 1, theta is [0, pi/2], and phi is [0, pi/2].  Now I've both lowered the dimensionality (only theta and phi are varying) and I've transformed this to an inequality constraint, something I know how to handle.

I've recently been thinking about the Simplex Method, which has a neat way of handling inequality constraints, so I'll use that.  Because I don't want to write "theta" and "phi", let me call my two variables "u" and "v".  Recall both u and v lie between 0 and pi/2.  So pick a starting point (u, v), and create a Simplex of three sets of (u, v) points.  You need to evaluate the function f(x, y, z) at the Spherical-Polar coordinates (1, u, v).  OK, messy math, but certainly doable.  Do this for all three Simplex points, then follow the usual Simplex algorithm (expansion, contraction, reflection, etc.), applying the usual "constraint factors" (typically jacking up the Objective Function if u or v gets out of the (0, pi/2) range).

Hmm.  That's pretty dense, isn't it?  Sorry about that, but it just "came to me in a flash" and I wanted to write it down before it's time to go home ...

The basic idea for "equality constraints" is to use them to reduce the dimensionality of the problem.  The question seems like "minimize f(x, y, z)", i.e. 3 unknowns, but the equality constraint allows you to say "minimize g(theta, phi)", two unknowns, no more "equality" constraints, but more usual constraints on theta and phi.  Actually, if you have a good guess for a solution and choose theta and phi near that, you might not even need to worry about the inequality constraints, depending on your algorithm.  

Bob Schor

P.S. -- I was about to say something about Levenburg-Marquardt, but didn't want to think about taking partial derivatives in SPC-space -- I've done it, but not for a few years ...

[Vills]

Hi Bob,

Thank you so much for such a detailed response. In the instant case, however, the number of variables is seldom 3, it is usually 9 and possibly more, with 3 to 4 constraint equations. Therefore, I am not sure whether the dimensionality reduction will help much. The best way is to figure out, how these constraints can be fit into the format that the LabVIEW optimization algorithm expects.

You can also take a look at another similar example VI titled "Linear Programming Simplex Method.vi", which implements equality/inequality constraints. Hopefully, that might give you some idea.

Thank you,

Vilas

[DSPGuy · Accepted solution]

The Find Global Min on Surface.vi example uses Global Optimization.vi

When creating your objective function, keep in mind:

1. The equality constraints are specified to have a value of 0.  So you should express the constraint as x1+x2+x3-c1=0

2. The inequality constraints are specified to be less than 0. In your example, you should express this as -x1<0, -x2<0, etc.

3. You will need to define a more proper objective function. If you want F1=F2=F3, then consider the pairwise distances.

For example, F_obj=(F1-F2)^2 + (F1-F3)^2 + (F2-F3)^2

I have attached a quick implementation of your equations as a global optimization objective function. Not optimal, but I think it is close to what you are looking for. Please notice the passing of the constants using the 'data' control. 

-Jim

[Vills]

Hi DSPGuy,

Thank you so much for your reply. The definition of objective function you gave sounds a good idea. Let me try it. However, I am unable to open the VI you attached, since it is written in LabVIEW 2016. I am using LV2015. Can you please save that VI in LV2015 and send it again? Thanks a lot again!