<< Graphics`

Preliminary setup (READ THIS FIRST)

First, we need to make a few definitions to make our work a bit easier.

Let's define a generalized gradient function (the one built into Mathematica is strictly for functions of 3 variables):

grad[scalarFunction_, variableList_?VectorQ] := 
      Table[(∂_(variableList[[i]])) scalarFunction, {i, 
          Length[variableList]}]

(This makes a vector by differentiating by each element of the variableList successively.  The ?VariableQ part forces you to enter the list of variables.)

The way you use this function is as follows:

grad[(x^2) - 2  x y, {x, y}]

Or, for a function of 3 variables:

grad[Sin[x y] Cos[z], {x, y, z}]

Or, for that matter, you can use it on a function of 6 variables:

grad[(a^2) (b^3) Sin[c d] - e Log[f], {a, b, c, d, e, 
        f}]

We also can do the following to make life easier:

SetAttributes[Equal, Listable]

This makes it easier to set vector equations equal to each other and solve them:

f[x_, y_] := (x^2) - 2  x + 3  (y^2)

∇f = grad[f[x, y], {x, y}]

system = ∇f == {0, 0}

Solve[∇f == {0, 0}, {x, y}]

(Hint:  we just found the critical points of this function.)

Optimization - No constraints

Finding critical points using Solve

To find the critical points of a function, you need to find all points where the gradient is equal to the zero vector or undefined.  So, we can use the definition I made for grad earlier:

f[x_, y_] := (x^3) - 2  x + 3  (y^2) - 5  y

∇f = grad[f[x, y], {x, y}]

This is never undefined, so we just need to set each component equal to 0 and solve the system of equations:

critPts = Solve[∇f == {0, 0}, {x, y}]

There are two critical points for this function.  (Notice the compact way we do this.  You could type in the equations individually, but this is much nicer.)  Also, we give the set of critical points a name (critPts) so we can refer back to them later and use them to calculate with.  You can get Mathematica to pick out a single one of these points using the following notation:

critPts[[1]]

critPts[[2]]

(Yes, you have to use the double square brackets like this.)

Of course, now you have to decide whether each of these is a local minimum, maximum, saddle point, or none of these.  One way to do this would be to graph the function around the critical points and see what it looks like:

Plot3D[f[x, y], {x, -2, 2}, {y, -2, 2}]

Perhaps you can tell what we have here.  If you were to "zoom in" on each critical point more closely (i.e., change your domain displayed), you could probably tell better.  However, it is often easier to look at the contour plot instead:

ContourPlot[f[x, y], {x, -2, 2}, {y, -2, 2}, 
      Contours -> 50, PlotPoints -> 30]

Notice that this makes it much clearer what is going on.  (It is often useful to use the Contours->50 or some large number so all minima/maxima get completely encircled.)  So, the critical point with the positive x value is a minimum, while the one with the negative x value is a saddle point.  (Be certain that you understand how to tell this from the graph before continuing.)

Let's use the 2 variable second derivative test to check this for sure.  In doing this, I will demonstrate a few tricks you can do with Mathematica to streamline this process (cutting and pasting gets to be a big pain after awhile).

We could do this a couple of different ways.  First, lets define D from the second derivative test:

secondDerivTest = (∂_(x, x))f[x, y] (∂_(y, y))f[
              x, y] - ((((∂_(x, y))f[x, y]))^2)

Now, to plug the critical points in, we could cut and paste them (bad idea), or we could use the replacement operator /.

secondDerivTest  /. {y -> (5/6), x -> (Sqrt[(2/3)])}

This replaces x with (Sqrt[(2/3)]) and y with (5/6).  These are called replacement rules. However, if you notice, our list of critical points is already composed of a list of these replacement rules:

critPts

So, we could do the following:

secondDerivTest  /. critPts

The first value corresponds to the value at the first critical point and the second one to the second point.  You can do the same thing to check (Subscript[f, x,x ]):

(∂_(x, x))f[x, y] /. critPts

We can handle all of our critical points simultaneously by doing things this way.  Thus, the first critical point has a negative value for D, so it is a saddle point.  The second critical point has a positive D and (Subscript[f, x, x]) is positive, so it is a minimum.

Finding critical points using FindRoot/FindMinimum

Unfortunately, Solve doesn't always work to find the critical points (if your function is exponential or trigonometric, for example).  In this case, there are two options.

Use FindRoot

The problem here is that, since it is based on Newton's method, you need an initial guess.  This means two things:  First, you need to look at a graph of the function (contour lines are good here) to make a reasonable guess.  Second, you can only realistically find critical points in a particular region (not true if Solve works; you can find all critical points then).  After finding each critical point, you still have to classify it (min/max/saddle point/neither).

Use FindMinimum

This command is kind of like the FindRoot command (i.e., you must give it an initial guess), but it then automatically finds a nearby minimum of the function.  This has the advantage that you know your answer will be a minimum.  Of course, it won't help you find saddle points.  You can find a maximum by using FindMinimum on -f(x, y), so the minimum of -f(x, y) will be the maximum of f(x, y).

Example

Consider the function:

f[x_, 
        y_] := (2  y - x + (E^(1 - (x^2) - (y^2))))/(1 + 
            (x^2) + (y^2))

∇f = grad[f[x, y], {x, y}]

Solve[∇f == {0, 0}, {x, y}]

In other words, forget it.  So, let's get a quick look at this near the origin:

ContourPlot[f[x, y], {x, -2, 2}, {y, -2, 2}, 
      Contours -> 20, PlotPoints -> 40]

It appears there is a minimum around (0.8,-1.5) and a maximum around (0,0.2) or so.  Let's find them:

FindRoot[∇f, {x, 0.8}, {y, -1.5}]

FindRoot[∇f, {x, 0}, {y, 0.2}]

You can use the graph (or the second derivative test) to see what each of these is.  If there were a saddle point, you could find it this way as well.

Or, using the FindMinimum command:

FindMinimum[f[x, y], {x, 0}, {y, 0}]

Notice that you use this command on f(x, y), not on ∇f  (and it gives you the value of the function at the point as an added bonus).  Also, since there is only one minimum nearby, you don't have to be very accurate with your initial guess.

In order to find the maximum:

FindMinimum[-f[x, y], {x, 0}, {y, 0}]

You would not be able to find saddle points reliably this way, however.  (Sometimes it will find them, but not always.)

Problems:

For each of the following, find the critical points, show them graphically on a contour plot (and 3-D if you wish), and classify them using the second derivative test as minima/maxima/saddle points/none of these.  If possible, use Solve to find all critical points.  If Solve doesn't work (or you don't get an answer back from it in a few minutes of waiting), then use FindRoot or FindMinimum to find all critical points on the region -2 ≤ x ≤ 
        2 and  - 2 ≤ y ≤ 2.

1.

f[x_, 
        y_] := ((y^2) - x + x y + 
            Log[(x^2) + (y^4) + 
                1]) (E^(-((x^2) + (y^2))))

2.

f[x_, y_] := 3  x - (x^3) - 2  x (y^2) + 2  y

Curve fitting using the method of Least Squares

One of the important applications of optimizing a multi-variable function is in finding a function that fits a set of experimental data.  This is useful in many fields, from applied science to economics.  Most spreadsheet, like Excel, have a built-in function to fit data to certain functions (usually called "regression" or something similar).  You can use Mathematica to fit your data to any function you wish, however.  

So, first we need some data to work with (it is possible to read this in from an external file, if you save it as a text file):

dataSet = {{0, -8.644412242139174`}, {1.`, 
            6.36983059812407`}, {2.`, 3.1166920538346634`}, {3.`, 
            16.534923962027378`}, {4.`, 17.28546439401197`}, {5.`, 
            14.042067682369016`}, {6.`, 29.67441157387531`}, {7.`, 
            31.892651694887128`}, {8.`, 25.187987568268625`}, {9.`, 
            33.50299780522195`}, {10.`, 37.5350851739895`}, {11.`, 
            41.804132220144915`}, {12.`, 46.673536373409014`}, {13.`, 
            51.31729013748644`}, {14.`, 51.428028230851666`}, {15.`, 
            64.48691715222478`}, {16.`, 55.879218441093954`}, {17.`, 
            76.16003134379929`}, {18.`, 73.19300996826124`}, {19.`, 
            74.48592658271696`}, {20.`, 90.48679882846014`}, {21.`, 
            89.55814982445182`}, {22.`, 87.06754392046815`}, {23.`, 
            87.27997238153488`}, {24.`, 105.91709124294056`}, {25.`, 
            93.9617805682085`}, {26.`, 98.71189437805373`}, {27.`, 
            109.49367210046722`}, {28.`, 111.3678316994278`}, {29.`, 
            106.64349890587818`}, {30.`, 119.7488499937566`}, {31.`, 
            132.29996876469778`}, {32.`, 124.86637365981635`}, {33.`, 
            135.81461179885287`}, {34.`, 128.87545668750323`}, {35.`, 
            141.14510958182848`}, {36.`, 152.82969149322244`}, {37.`, 
            143.12175703772104`}, {38.`, 160.0594450025457`}, {39.`, 
            163.2577901450373`}, {40.`, 167.53765193710154`}, {41.`, 
            161.5364857484343`}, {42.`, 165.42877625833646`}, {43.`, 
            171.32178595591188`}, {44.`, 183.58835667177243`}, {45.`, 
            182.50342065665296`}, {46.`, 192.87389824007832`}, {47.`, 
            182.5420606461265`}, {48.`, 200.15909367012085`}, {49.`, 
            195.01704949927293`}, {50.`, 204.62499444239253`}};

We can use the ListPlot command to take a look at all this data:

dataGraph = ListPlot[dataSet]

This looks basically linear, so let's see if we can find the "best" linear fit for this data.  (The deviations from a linear graph could be due to experimental error, chance, or other complicating factors.)  There are different definitions of what line/curve would best fit this data, but the one we will use is called the "least square fit".  The idea is to define a function with appropriate unknown parameters:

linearFit[x_] := a x + b

where a and b are the parameters you are trying to find.  

Now, at each point we want to examine the "residual", which is the difference between f(x) and the actual y value of the data.  This tells you how far the actual data point is from the line.  So, for example, at x=1, the residual would be a(1) + b - 6.36983059812407, which is a function of the parameters a and b.  You could then add together the residuals for all the points.  This would give you the total amount all the data points differ from a given line.  For the "best" line, you would like this total of the residuals to be as small as possible (so it is the "closest" line to as many points as possible).  

Unfortunately, since some points are above the line and some are below it, some of their residuals will cancel out (some are positive and some negative).  We can fix this by squaring each residual to make it positive.  If we then minimize the sum of these squares of the residuals, we will find the line that is the "closest" to the most points.  This is called the "method of least squares".

So, to actually set this up, we could do the following:

howManyPts = Length[dataSet]

sumOfSquares = (∑_(j = 1)^howManyPts)(((linearFit[dataSet[[j, 1]]] - dataSet[[j, 2]]))^2)

In this function, dataSet[[j,1]] refers to the x coordinate of the (j^th) point and dataSet[[j,2]] refers to the y coordinate.  (howManyPts tells you exactly what it says...)  

Now, sumOfSquares is a function of two variables a and b, which we want to minimize.  So we can simply find the critical points and decide whether they are minima or not.

∇sumOfSquares = grad[sumOfSquares, {a, b}]

bestCoef = Solve[∇sumOfSquares == 0, {a, b}]

Since there is only one critical point, you should be able to convince yourself that this is indeed a minimum by any of the methods mentioned above (or by simple logic; it can't be a maximum since you can always make the line as far from the data as you want).  The best fit line is therefore:

f[x_] := linearFit[x] /. bestCoef

f[x]

Let's plot both the data and the line we just found together on the same graph:

curve = Plot[f[x], {x, 0, 50}]

Show[dataGraph, curve]

If your data doesn't look like it is linear, then you need to decide what kind of function it does look like.  Then, use the formula for that type of function with appropriate parameters and use the same process on it (using a different function besides linearFit).  

Here are some typical functions you might use:

parabolicFit[x_] := a (x^2) + b x + c

cubicFit[x_] := a (x^3) + b (x^2) + c x + d

exponentialFit[x_] := a (E^(-b x)) + c

exponentialXFit[x_] := 
      a (x^2) (E^(-b (x^2))) + c

logisticFit[
        x_] := ((a b)/(a + (b - a) (E^(-c x))))  (you may assume that a > b and a, b, c > 0)

When finding the critical points, if Solve doesn't work, then you are forced to use FindMinimum (or FindRoot, though FindMinimum would probably be better here).  For the functions with 3 (or more) parameters, it can be tricky to pick a starting guess.  Sometimes it is useful to just pick anything reasonable for a starting guess (thinking about x or y-intercepts and any asymptotes, for example).  If Mathematica gives you an error message saying something like "Machine precision is insufficient to achieve the requested accuracy or precision.", then take the answers it gives you for this and use those numbers for your initial guess instead.

For each of the possible functions above, graph them with some different values for the coefficients, so you can get an idea of what they look like.  Give a brief explanation of the roles of the parameters in the last 3 (i.e., what effect do they have on the y-intercept, horizontal asymptote, shift up or down, etc.).

Problems - Choose any TWO of the following:

1.

dataSet = {{0, 4.795450582322369`}, {0.2`, 
            18.219913155940013`}, {0.4`, 
            28.06685239427116`}, {0.6000000000000001`, 
            37.68621643430582`}, {0.8`, 45.14603521623819`}, {1.`, 
            51.5539140822255`}, {1.2000000000000002`, 
            52.27586054015945`}, {1.4000000000000001`, 
            58.923370278912564`}, {1.6`, 53.44715783224788`}, {1.8`, 
            54.265811131401385`}, {2.`, 53.021164287401504`}, {2.2`, 
            48.119374733293974`}, {2.4000000000000004`, 
            45.58562906050006`}, {2.6`, 
            39.43134306008845`}, {2.8000000000000003`, 
            40.83417951595212`}, {3.`, 32.735340856967156`}, {3.2`, 
            25.874112888316564`}, {3.4000000000000004`, 
            18.93549825485953`}, {3.6`, 
            12.80328384569315`}, {3.8000000000000003`, 
            10.880885120119924`}, {4.`, 7.501991673058515`}, {4.2`, 
            2.0861271305059987`}, {4.4`, -3.042021683801549`}, {4.6000000000000005`, 1.7798967117207856`}, {4.800000000000001`, 
            0.4409410907361451`}, {5.`, 1.9762139745659846`}, {5.2`, 
            5.43112592192729`}, {5.4`, 
            7.3004802774149695`}, {5.6000000000000005`, 
            13.587705874497974`}, {5.800000000000001`, 
            22.402699892340507`}, {6.`, 37.60726538176784`}};

2.

dataSet = {{0, 0.6819138084404404`}, {0.5`, 
            1.9765217260256138`}, {1.`, 2.9056014498950953`}, {1.5`, 
            3.4025178717953803`}, {2.`, 4.043051675911651`}, {2.5`, 
            4.4365305714437975`}, {3.`, 4.372672878445865`}, {3.5`, 
            5.053734783958435`}, {4.`, 5.717491444205223`}, {4.5`, 
            5.761821599270346`}, {5.`, 5.853953479526335`}, {5.5`, 
            6.6225113100445405`}, {6.`, 6.14615751843068`}, {6.5`, 
            6.3413947109160835`}, {7.`, 6.94302264781887`}, {7.5`, 
            6.966373035875038`}, {8.`, 6.690027999168499`}, {8.5`, 
            7.109007856841218`}, {9.`, 7.509615892837005`}, {9.5`, 
            6.99888802627019`}, {10.`, 7.303255162499371`}, {10.5`, 
            7.097973555251163`}, {11.`, 7.75843268857269`}, {11.5`, 
            7.49042118262303`}, {12.`, 7.447426865851176`}, {12.5`, 
            7.543493275009288`}, {13.`, 7.97730133080266`}, {13.5`, 
            7.832264507635624`}, {14.`, 7.695788366569908`}, {14.5`, 
            7.881147557941922`}, {15.`, 8.004857816999683`}, {15.5`, 
            7.554742048993395`}, {16.`, 7.886313045899679`}, {16.5`, 
            7.520157906400456`}, {17.`, 7.8101453430810865`}, {17.5`, 
            7.619516937734489`}, {18.`, 7.828690902883435`}, {18.5`, 
            8.244900345921423`}, {19.`, 8.089992862050252`}, {19.5`, 
            8.01433047010997`}, {20.`, 7.821913267832745`}};

3.

dataSet = {{0, 3.080090467237231`}, {0.1`, 
            3.2868639940828084`}, {0.2`, 
            3.6064421750038607`}, {0.30000000000000004`, 
            4.520233182152512`}, {0.4`, 5.783170963763869`}, {0.5`, 
            7.077757418111564`}, {0.6000000000000001`, 
            7.937670335507099`}, {0.7000000000000001`, 
            9.0765645728725`}, {0.8`, 9.880371522576352`}, {0.9`, 
            10.361489013110985`}, {1.`, 10.49757375891783`}, {1.1`, 
            10.11592970293036`}, {1.2000000000000002`, 
            9.907008360258567`}, {1.3`, 
            9.393461141893576`}, {1.4000000000000001`, 
            8.60379521160976`}, {1.5`, 7.626582500399559`}, {1.6`, 
            6.943243812501887`}, {1.7000000000000002`, 
            6.04317392967861`}, {1.8`, 
            5.695934576608815`}, {1.9000000000000001`, 
            4.932195501844078`}, {2.`, 4.596105314066718`}, {2.1`, 
            4.236123204301426`}, {2.2`, 
            3.808689406216186`}, {2.3000000000000003`, 
            3.6555959759592573`}, {2.4000000000000004`, 
            3.2137717918715523`}, {2.5`, 3.1164892152984165`}, {2.6`, 
            3.16220373465184`}, {2.7`, 
            3.1465041219115313`}, {2.8000000000000003`, 
            3.056180202233477`}, {2.9000000000000004`, 
            2.9288752874491704`}, {3.`, 2.9132889272798677`}, {3.1`, 
            3.187082719185429`}, {3.2`, 
            3.0707383934400387`}, {3.3000000000000003`, 
            2.9407012122958793`}, {3.4000000000000004`, 
            2.9532959127115372`}, {3.5`, 3.075811594988412`}, {3.6`, 
            3.180545279111814`}, {3.7`, 
            2.980249788776125`}, {3.8000000000000003`, 
            3.0690997779950298`}, {3.9000000000000004`, 
            2.9910972754225456`}, {4.`, 2.994730401070941`}};

Optimization - With constraints

Lagrange multipliers

Fortunately, the method of Lagrange multipliers can be relatively easy to implement using Mathematica.  For example, if you need to optimize f (x, y) = 3  (x^2) (y^2) subject to the contraint that (x^2) + (y^2) = 4, you could set it up as follows:

f[x_, y_] := 3  (x^2) (y^2)

∇f = grad[f[x, y], {x, y}]

g[x_, y_] := (x^2) + (y^2)

∇g = grad[g[x, y], {x, y}]

system = {∇f == λ ∇g, g[x, y] == 4} // 
        Flatten

The //Flatten command at the end is necessary here for the Solve command to work properly with this.  It strips out the extra {}'s you would get otherwise.  Now you can use the Solve command to solve the system (even though you don't care what λ equals, you should still solve for it):

solutionPts = Solve[system, {x, y, λ}]

Notice that, again, we can give a name to the entire set of solutions to this sytem.  This way, we can work with all of them at one time, or pick a single one out to work with. 

Now, we need to find which of these is the minimum and which is the maximum:

f[x, y] /. solutionPts

(This plugs all of the solution points into f and displays the results.)  So, the minimum value is 0 (which occurs at the first 4 solution points) and the maximum value is 12 (which occurs at the last 4 solution points).

What to do when Solve doesn't work

So, what do you do when the Solve command doesn't work here?  Not surprisingly, you use the FindRoot command.  This is both easier and harder than it is in the case of finding critical points.  To do this, you must display a contour plot and a graph of the contraint equation on the same axes.  So, let's consider optimizing f (x, 
            y) = ((x^2) + x y + (y^2) - 
              x) cos(π (Sqrt[ (x^2) + (y^2) + 1])) subject to 2  (x^2) + 3  (y^2) = 1.

f[x_, y_] := ((x^2) + x y + (y^2) - x) 
        Cos[π (Sqrt[ (x^2) + (y^2) + 1])]

∇f = grad[f[x, y], {x, y}]

g[x_, y_] := 2  (x^2) + 3  (y^2)

∇g = grad[g[x, y], {x, y}]

system = {∇f == λ ∇g, g[x, y] == 1} // 
        Flatten

solutionPts = Solve[system, {x, y, λ}]

Well, I left this running for over 2 hours and it still hadn't come up with a solution, so it's time to look at the FindRoot function.  However, to use it, we need an initial guess.  This is trickier than it was with finding critical points.  Remember, what you are looking for is where the gradients of f and g are parallel.  An easier thing to look for, however, is where the contour curves are "parallel" (which is equivalent, if you think about it).  

So, first, let's graph the contour plot for f on the same graph with g (not contour curves):

fContourGraph = 
      ContourPlot[f[x, y], {x, -0.75, 0.75}, {y, -0.75, 0.75}, 
        Contours -> 50, PlotPoints -> 50, 
        ContourShading -> False]

gGraph = 
      ImplicitPlot[
        g[x, y] == 1, {x, -0.75, 0.75}, {y, -0.75, 
          0.75}]

Show[fContourGraph, gGraph]

Notice that we don't have to see all of f; we only need to see the region around the constraint curve g.  According to this graph, it looks like there are probably two points where the contour curves run parallel to g:  near (0.6,-0.4) and near (-0.6,-0.2).  Let's use those as our initial guesses for FindRoot.  Since we have no idea what λ equals for those points (and we don't really care), we will just guess that λ = 0.

solution1 = 
      FindRoot[system, {x, 0.6}, {y, -0.4}, {λ, 0}]

f[x, y] /. solution1

Now let's check the other one:

solution2 = 
      FindRoot[system, {x, -0.6}, {y, -0.4}, {λ, 
          0}]

f[x, y] /. solution2

Therefore, solution1 is the minimum and solution2 is the maximum.  (There are fancier ways to check both of these at the same time, but I am trying to keep things simple here.)

The problem with this method is that it isn't always easy to find all the places where the curves are parallel.

Problems:

For each of the following, find the minimum and maximum values of the function f subject to the given restriction.  If f is a function of two variables, plot its contours and the constraint on the same graph.  If Solve doesn't work (or you don't get an answer back from it in a few minutes of waiting), then use FindRoot instead, using your graph to pick your initial guesses.  Hint:  If you have a function of more than two variables, you treat it exactly the same as a function of two variables (our grad function can handle this, as long as you remember to give it a list of all the variables), except you have to adjust all the variable lists appropriately. (Also, really hope that Solve works on these.  It would be very hard to find them one at a time with FindRoot.)

1.

f[x_, y_, z_, w_] := 4  (x^2) - 3  (y^2) + 2  (z^2) - (w^2)

subject to (x^2) + (y^2) + 3  (z^2) + 4  (w^2) = 10

2.

f[x_, 
        y_] := ((x y)/2) + (E^(-(x^2) - (y^2))) 
          Cos[π ((x^2) - y)]

subject to (x^2) + (y^2) = 1