The over-all goal is to explore several advanced methods for finding global minimum of complex (non-convex) functions, with multiple local minima. We will also investigate related problems such as robustness of the minimum and sampling of multi-dimensional space. Three parts: A, B, C. Parts A and B are the same for everyone. Part C has two options, see below. PART A. Compare at least two advanced methods for finding global minima available in Mathematica. Choose ones that belong to very different classes. Test them on at least three fairly complex functions in N dimension, conclude which method is better. Speed of the method is not primary concern: the first question is whether each method can identify the global minimum at all, within some reasonable amount of time, say several hours on your laptop. Test functions. Prepare one of the functions yourself -- this one should mimic the famous protein folding funnel. Analytical, differentiable function E = z(x, y, z....) that produces "realistic looking" folding funnels (e.g. http://wavefunction.fieldofscience.com/2011/06/protein-folding-funnel-and-its.html ) with great many local minima. Of course, you must construct the function in such a way that its only global minimum is known apriori. For the second and third test functions, choose two of the common functions used in this field (see a subset of those at the bottom of this document). A number of those are available in VTDirect sample code. Make sure your functions are easily generalizable to any N. Start with N=1, then move on to N=2. Make sure to provide contour or 2D plots + some type of convergence analysis. Once you have explored N=1,2, push the limits: consider N=3 and beyond. When do the methods start to break down? That is another criterion of "goodness" of the method. Make a table, with functions, methods and the metrics you use to test how good they are. PART B. Take the function that you think is the "hardest" from the ones you have tested (N=2) and see how VT direct handles it. First, explore how the method scales with the number of available nodes. Y you start with running it on all o the cores within a single node, then test k=2, 3, 4. nodes. Make plots of "time to find global minimum vs. # of nodes". Push the limits: consider N=3 and beyond. When do the methods start to break down? Again, you do not want to run the calculations for longer than one day. PART C. A new metric of optimum robustness. [This is intructor guided part of the project. You can choose it, or propose your own alternative project, see below] This is the most creative part of the project. You need to come up with a reasonable metric (and and algorithm to compute it) that compares the global minima and slightly sub-optimal local ones to choose the most robust practical solution. Here is the problem: mathematically, the global minimum of the objective function (OF) is, obviously, always the best. However, this may not be the case in practice. Suppose you construct a complex machine (structure, method, etc) that depends on multiple parameters, e.g. geometrical dimensions of the parts of the machine. You want to find the values of these parameters that minimize the deviation of the objective function (OF) from some standard. Suppose the "well" corresponding to the global minimum is extremely narrow, and the OF grows steeply as the argument deviates only slightly from the value corresponding to the global minimum. In this case it may be impossible to manufacture the parts with the exact specs of the global minimum: there will always be some deviation along each dimension in the parameter space. Thus, in reality, the manufactured part will "fall" on the steep wall outside of the global minimum, where the OF is high. This solution may be very bad, e.g. your airplane may drop out of the sky with these non-optimal parameters. However, suppose that the second deepest --local-- minimum is not much higher than the global minimum, but is relatively much more shallow and wide. Then, the inevitable deviation of the parameters from the exact value that yield this local minimum will not lead to a disastrous rise in the OF -- the resulting practical solution may be very reasonable in practice. Another example illustrating the same point is the famous protein folding challenge discussed in class. As you remember, the problem amounts to finding a global minimum of the energy of the protein, on a very rugged and complex energy landscape E(x) with multiple local minima. In reality, the protein is always kicked around by thermal jolts from the surrounding water, other proteins, etc. These jolts add a ``noise" to E(x) of an order of kT. That is if you have two minima whose values are different by much less than kT, the protein can easily hop between the two, kicked around by the thermal jolts. Now imagine that one of these minima is the true global one, but narrow, while the other is much wider. There are much greater chances for the protein to actually be found in the second one (bigger bucket vs. smaller one). Mathematically speaking, you need to propose a way to somehow compare apples and oranges -- depth and width of the minima -- on the same footing. The solution needs to be well justified. Further hints will be provided. Hint (1) In general, in each specific problem you will have a parameter, let's call it "δ ", which tells when two values of the OF are indistinguishable in practice: if |E(x) - E(y)| << δ, E(x) is essentially the same as E(y). There is some analo gy between δ and machine ε. You will explore how your metric works on your test fictions. PART C (Alternative) As discussed in class, you can propose your own project that is a good candidate for this class. Must be instructor approved. DELIVERABLES: 1. 50 points. Mid-term progress report. Oral, in class. Each group presents. DUE DATE TBA. Should include complete and final results of "A" + some amount of preliminary results on B and C. You can pick and choose, e.g. do quite a bit of B and a little of C, or 50/50 on both or something. But not 100/0 or 0/100. At least some brainstorming on "C" is expected at this point. In particular,if you choose your ``own" project, you must at this stage distill the actual priblem to a mathematical abstraction. Specify the objective function, how many parameters to optimize (that is the dimensionality of the space). 2. 100 points. Final typed report. A+B+C final. Due within 3 days of the reading day, by 5 pm. 6 to 8 pages max, 11 pt font. PDF + LaTex or Word source. Format: follow the format of a typical research paper, with all of the usual sections (abstract, Intro, Methods, Results, Conclusions). Good pictures are a must. Make sure to give your names on the front page, along with a description of who did what. POSSIBLE TEST FUNCTIONS: Think which ones are good to test --global-- optimization algorithms, ones that are supposed to find the unique global optima among a slew of local ones. There are a great many other suitable functions in the literature. Some examples are below, not all of them are good for us. PICKING A USEFUL FUNCTION, AND JUSTIFYING THE CHOICE IS PART OF THE ASSIGNEMNT THAT WILL CONTRIBUTE TO YOUR SCORE. Ackley function: https://en.wikipedia.org/wiki/Ackley_function Griewank function. See e.g. https://en.wikipedia.org/wiki/Griewank_function ! The function formula is ! f(c) = 1+sum(c(i)^2/d)-product(cos(c(i)/sqrt(i))), ! where d = 500.0 (a bigger d value gives more local minima) and ! i is the summation index ranging from 1 to N (the number of ! dimensions). The global minimum is f(c)=0 at c(:)=(0,...,0), when c ! is in [-20, 30]^N. Quartic function. ! The function formula is f(c) = sum(2.2*(c(i)+e_i)^2-(c(i)-e_i)^4), ! where e_i is a uniformly distributed random number in [0.2,0.4] ! and i is the summation index ranging from 1 to N (the ! number of dimensions). Here, take all e_i = 0.3 for a ! deterministic result. The global minimum is f(c)=-29.186*N at ! c(:)=(3,...,3) when c is in [-2,3]^N. Rosenbrock's valley function. ! The function is f(c)=sum(100*(c(i+1)-c(i)^2)^2+(1-c(i))^2), ! where i is the summation index ranging from 1 to N-1 (the ! number of dimensions minus one). The global minimum is f(c)=0 at ! c(:)=(1,...,1), when c is in [-2.048, 2.048]^N. Schwefel's function. ! The function formula is f(c)=sum(-c(i)*sin(sqrt(abs(c(i))))), ! where i is the summation index ranging from 1 to N (the number of ! dimensions). The global minimum is f(c)=-N*418.9829 at ! c(:)=(420.9687,...,420.9687), when c is in [-500,500]^N. Michalewicz's function. ! The function formula is ! f(c)=-sum(sin(c(i))*(sin(i*c(i)^2/pi))^(2*m)), where i is the ! summation index ranging form 1 to N (the number of dimensions), ! and m=10 (a bigger m value presents a narrower valley). ! The global minimum is f(c)=-4.687 (N=5) at ! c=(2.203, 1.571, 1.285, 1.923, 1.720), ! when c is in [0, pi]^N.