MATLAB Answers

Which optimization function and which algorithm do I use?

21 views (last 30 days)
Jorrit
Jorrit on 17 Jun 2011
Commented: Sarah Assani on 14 Jul 2015
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]

  2 Comments

Jorrit
Jorrit on 17 Jun 2011
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.

Sign in to comment.

Answers (3)

Andrew Newell
Andrew Newell on 17 Jun 2011
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.

  5 Comments

Show 2 older comments
Andrew Newell
Andrew Newell on 20 Jun 2011
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
Jorrit on 21 Jun 2011
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
Andrew Newell on 23 Jun 2011
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"?

Sign in to comment.


Jorrit
Jorrit on 21 Jun 2011
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.

  6 Comments

Show 3 older comments
Jorrit
Jorrit on 22 Jun 2011
In addition: The range was the previously used objective value, which has to be maximized.
Walter Roberson
Walter Roberson on 22 Jun 2011
Sorry, I haven't used fgoalattain(), and I am still rather shaky on the terminology and how the parts relate together.
Jorrit
Jorrit on 23 Jun 2011
Thanks for your help. I'll have a go at it myself and otherwise open a new question, specifically about fgoalattain.

Sign in to comment.


Alan Weiss
Alan Weiss on 18 Aug 2011
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.

  2 Comments

Jorrit
Jorrit on 19 Aug 2011
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
Steve Grikschat on 6 Sep 2011
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?

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by