Which optimization function and which algorithm do I use?

Dear all,

I've been working on an optimization of a conceptual aircraft. I've tried many things already, but so far no luck. Up until now the optimization ended prematurely, or stopped at an infeasible point, often with half of the input variables left untouched. I want to start all over again, by first selecting a suitable function.

I've tried to use the fmincon function before. However it gets stuck at infeasible local minimums every time. I tried dozens of starting points, but no luck. I have been able to find a feasible solution myself, so I know it is possible. Fmincon seemed to only improve the objective value and sort of just hopes it becomes feasible as well.

Walter Roberson pitched the idea of using fgoalattain. This is a multi-objective optimization function. I'm still not sure if this is the right one, since I have only one real objective. In case I want to use the fgoalattain function, all constraints become objectives. Would this be the right function to use for my problem? Or should a use a completely different function?

Here's what I want to do:

I have 31 variables, describing the planform and the tail size of the aircraft. There are 24 constraints, a few examples are: runway length required to take-off, stall speeds, cabin size, stability margins etc.

Those variables depend on the input vector through a whole series of subfunctions, which are quite complicated in some cases.

The start vector is a first guess and is likely to be infeasible. Usually about 1-5 of the constraints are violated. It is not likely that the first guess is completely off, since the input vector is constructed based on quick estimations.

The objective is to make the aircraft feasible in the first place and secondly maximize the range. A single run to make and analyze an aircraft takes approximately 30 seconds and I want to keep the total optimization time under 24 hours. My program does not calculate analytical derivatives for the input variables.

Whenever a constraint is violated, I have an amount by which it is violated. For the runway length this may for example be something like 120m violation of the required runway length. For stability margins this may be something like 0.02 violation. I really need to achieve feasibility, that is the most important requirement. Maximizing the range comes in second.

Beside these physical constraints, there are also some linear constraints on the input variable, which make sure that the aircraft can be handles by the evaluation function. The wing is seperated in a number of stations. The linear constraints make sure that the second station is further outboard than the first one, the third one is further outboard than the second one and that the chords keeps decreasing or at least equal when moving further outboard. These constraints were handles well by fmincon.

I hope that by posting this, I'm able to select the correct optimization function and algorithm, before I continue with the random trial and error thing, like it now feels. I also like some help by setting up the function. So if I do need to use fgoalattain for example, how do I use the constraints etc.

[Question edited]

[Jorrit]

Some additional info:

I do have specified upper and lower bounds. The constraints violated are for example runway length etc, depending on the geometry of the aircraft, via a whole number of calculations.

[Sarah Assani]

After 4 years, how did you solve it?

Answer 1

[Andrew Newell]

There are many possible reasons for the failure. I can only make some general comments:

1. The active-set algorithm doesn't satisfy the constraints at each step, so it isn't surprising that they aren't satisfied when no feasible solution is found.
2. The page on Choosing the algorithm suggests trying the interior-point algorithm first.
3. You should read When the Solver Fails.

[Jorrit]

Thanks. I've set it to interior point now. It is performing calculations and up until how, the aircraft evaluated seem more reasonable. It is currently at the 4th iteration, so I'll let it run for some time. (each function call takes approximately 30sec, since there is an aerodynamic evaluation in it, which takes long)

I'm going to read the 'when the solver fails'-page this evening. Thanks again.

Any additional suggestions are welcome.

[Jorrit]

Setting the algorithm to interior-point generates much more reasonable solutions. It, however, has not created a single feasible solution so far. I'm getting a bit desperate, seems like I have started an impossible graduation project. It is close to impossible to provide a feasible start solution. I have been trying to that, but it sort of removes the point of using fmincon. I selected the fmincon function mainly to seek for feasible solutions, besides optimal solution of course. Do you recommend a different algorithm, of moving away from fmincon completely? I cannot continue to try different starting vectors. I have been doing that for the past 3 days and it hasn't given me a single valid result, while I know that it should be possible. It really feels like I'm doing the optimization right now, and not fmincon.

[Andrew Newell]

I don't know how you distinguish between a reasonable solution and a feasible solution, but ... Assuming the problem is well-defined and there isn't an error in your code, maybe you need the Global Optimization Toolbox.

[Jorrit]

Just noticed I missed your comment, sorry for that.

A global optimization would probably solve the problem, but it also takes much longer. A single run through my code take approximately 30 seconds. I know someone who made a comparable program, but for a different aircraft type. His code was somewhat less detailed and only took 3 seconds, yet his optimization took 4 days with a genetic algorithm. He used only 8 variables if I remember correctly, I have 31.

I'm not sure if it would be feasible to use a global optimization, but I probably need to consider this seriously. I still believe however, that much more could be reached with a gradient based optimization. As you can read in the answer below, there is a gradient which does lead towards a feasible solution.

And yeah a reasonable solution is maybe a sloppy description. Based on what I know as an aerospace engineer, I can already judge if something has the potential to work or not. The unreasonable solutions are the really infeasible ones so to say, while the reasonable that are still infeasible are closer to an actual feasible solution.

I think the problem is well defined. I've set clear lower and upper bound. But some combinations may produce a somewhat odd-result. Usually the case is you take two opposite extremes. The program then still calculates everything, but the constraints are probably heavily violated or the objective value is way off. There are also some linear constraints on the input variables, which make sure that no physically impossible things are created.

[Andrew Newell]

Sorry we're not able to help more, but without seeing your code we can only offer generic suggestions. Have you tried all the suggestions in "When the solver fails"?

Answer 2

[Jorrit]

Okay I'm still trying; my computer has been running since I posted this question, but still no luck.

The interior-point does more sensible things, but still it cannot make the design feasible. I know there is a feasible solution, because after dozens of trials, I managed to find one myself. Trying myself however is not the solution, because I need to be able to make hundres of different aircraft with the program.

I have found a input vector, which violates only one constraint. It is an easy one, the stall speed. This depends on the maximum lift coefficient, which is to some extent dependent on the input vector, but definitely not much. The big dependence is the wing area. This can be easily adjusted by means of one entry of the input vector.

Yet fmincon does not even move slightly in the right direction to make the design feasible. About half of the input variables are left untouched, which is strange. By my engineering judgement I can tell which ones have to be changed.

Fmincon continues with the iterations, about 9 and then terminates at an infeasible solution, close to the start solution. There is a 21% increase in the objective value.

How is it possible that fmincon cannot find out how to make the design feasible?

In case of the stall speed, the analytical formula used in the constraint function is V = sqrt(2W/(rho*CLmax*S)). The landing weight, W and density, rho are fixed. CLmax is very insensitive, the big depence is S. I've let the function run manual for different input vectors and I can verify that with the change of one variable, I can make it feasible. There is always a gradient. So why can't fmincon?

Meeting this particular constraint comes at a small cost of the objective value, but this is necessary. Is this the reason fmincon cannot find a feasible solution? Is there an algorithm out there that can find a feasible solution?

I'm aware of local minimums in which the solution could get stuck. I've tried many different inputs, but the one described above is the most clear one. Other start points did not solve my problem either.

[Walter Roberson]

Sounds to me as if you should try fgoalattain(), as that allows you to set weights to favor optimization of particular variables.

[Jorrit]

Thank you sir. I'm going to look at this tomorrow. I will let you know if I can get it working.

[Jorrit]

Okay, I've just started a new optimization with the fgoalattain function.

I'm not really sure though if I used the right method. My goals are to find an aircraft that meets all constraints and has a maximized range.

What I did is, use the former constraint values and the range as the objective values and assigned a higher weight to the constraint values. I applied the subplus function over the constraint values, since they do not have to be zero, but just any negative, indicating the constraints are met. Is this a good approach? Somehow it feels like just a work around and I'm not sure if this is what you mean and if I explained the problem clear enough.

In case this is alright, would you still advise using a constraint function, with the same constraints values as used by the objective function?

[Jorrit]

In addition: The range was the previously used objective value, which has to be maximized.

[Walter Roberson]

Sorry, I haven't used fgoalattain(), and I am still rather shaky on the terminology and how the parts relate together.

[Jorrit]

Thanks for your help. I'll have a go at it myself and otherwise open a new question, specifically about fgoalattain.

Answer 3

[Alan Weiss]

It is possible that fmincon is not moving because your objective function is locally flat, or the constraints are. You might want to set DiffMinChange to a value larger than the default, such as 1e-3.

You didn't answer the question of whether you tried the suggestions in When the Solver Fails, and what were the results of your trying those suggestions. In particular, you might need to start at way more than a few dozen starting points. The Global Optimization Toolbox functions GlobalSearch and MultiStart do exactly that. Even though you don't seem to have Global Optimization Toolbox, you might look in the documentation to see if anything there might help you, such as Improving Results.

[Jorrit]

Thank you for the suggestions. It is a rather old question and I've tried a lot of things since. One of those is changing the dx. There is a numerical aerodynamic calculation, which is sometimes a bit insensitive to small changes, that's why I've the dx to a much larger value right now.

The optimization does work, but it still isn't ideal. It generally makes the aircraft feasible, but often does not produce an optimum results. How do I know? Sometimes the optimizer finds a lower objective value halfway through the optimization, which is feasible and ends with a higher objective. See the picture in the link: http://i51.tinypic.com/dnkr9t.jpg

I've switched algorithms a couple of times, now I'm using the active-set algorithm as suggested by a phd-student at our university, who is specialized in optimizations. Currently he is not at our faculty, so I cannot ask him for help.

[Steve Grikschat]

I can't be sure, but I know that the interior-point algorithm, while fairly robust, may sometimes struggle with certain problems where there appears to be non-smoothness in the objective/constraints whether or not it is real or numerical. For this reason, the active-set algorithm is preferred in engineering design problems where the objective is a simulation.

I would like to bring the "sqp" algorithm of fmincon to your attention in case you weren't aware. This is essentially the active-set algorithm but with some enhancements which may be of interest to you. Namely, it will respect bounds on the variables at each iteration.

Also, (this may be obvious) but have you considered parallel evaluations to save time?