Tag Archives: optimization

Exploring optimization problems in Excel

Excel is able to solve optimization problems. Two commonly available tools are the build-in Solver tool and the Excel plugin for Microsoft Solver Foundation (MSF). The former is not installed by default but can be easily enabled through the Excel Options menu. The latter is a separate download available from Microsoft.

For a simple comparison of the performance of the two, the non-linear data fitting example from the MSF is used as benchmark.
msf-1

MSF provided additional menu pane within Excel for complex optimization operations.
msf-2

Optimization results and log of this benchmark run of a non-linear data fitting sample from the MSF, based on an NIST sample.
msf-10
msf-3

Goals setting screen.
msf-5

Model Display.
msf-6

On the other hand, the built-in Solver offered a simpler interface but still provide detailed reports, including answer, sensitivity, and limits reports in separate spreadsheets.
msf-7

msf-8

The built-in Excel Solver offered easy to use interface, while the Microsoft Solver Foundation is more capable for complex problems and modelling.

The NelderMead solver is selected in this benchmark by the MSF. Check out this previous installment for details of running Nelder-Mead on TI Nspire. The same data set is performed on the Nspire using Nelder-Mead to obtain the following results.
msf-9
msf-11

Observations on effect of initial parameter of Nelder-Mead to solve linear problem

Out of curiosity a test program is created to iterate the initial parameters for the Nelder-Mead program in TI Nspire to see if there is any effects or patterns to the outcome of the algorithm. The Nelder-Mead program is to solve the following inequalities:

nmsimplexparmest1

The test case will iterate test variables x and y from 1 to 10, resulting in 100 tests. Absolute error value of the Nelder-Mead program result to the known optimal value (33) is plotted in the below chart.

nmsimplexparmest2

nmsimplexparmest3

Solving linear programming problem with Nelder-Mead method

For solving linear programming problem, the simplex method is often applied to search for solution. On the other hand, the Nelder-Mead method is mostly applied as a non-linear searching technique. It would be interesting to see how well it is applied to a linear programming problem previously solved using the Simple Method in TI-84.

The Nelder-Mead method is ran under the TI Nspire CX CAS with NM program written in the TI Basic program. The program accepts arguments including the name of the function to maximize as a string and a list of initial parameters to execute the Nelder-Mead algorithm. The function itself is declared using piece-wise function to bound the return value to the function to maximize while giving penalty to values that violate any constraints (as in the inequalities of the standard simplex method).

Previous program in the TI-84 using the simplex method obtained {200,400} as the solution. The Nelder-Mead returned a solution very close to it.

nmsimplex

Simplex Algorithm on the Casio 9860GII

With matrix capable calculator, simplex algorithm for common maximization problem can be solved easily like in the TI-84.

The Casio 9860GII is also equipped with equivalent matrix operations to solve the same problem.

casiosimplex1

casiosimplex2

casiosimplex4

casiosimplex3

Nelder-Mead algorithm on the TI-84 Plus SE

This mean nothing more than to prove that implementing the Nelder-Mead algorithm on the TI-84 is possible. In reality, the time it will take for a TI-84 Plus SE to arrive a solution for any practical non-linear problem renders this somewhat a last resort option. That is, in the absence of any modern computer or even a decent mobile phone 🙂

The program is implemented in the native TI-Basic, which is ported from the program for the same problem previously done on TI Nspire and Casio fx-9860GII. It took some efforts to port the program as the resources on the TI-84 is comparatively limited. For example,variable names are also restricted to single character, but thanks to list, things are easier.

With the availability of the new generation TI-Connect software, the Program Editor has returned and this tool greatly helped programming the Nelder-Mead on TI-84. Although unlike the more advanced Nspire Software which is able to run the program on PC instead of having to download the program to the TI-84 every time, editing TI-Basic in PC with a full keyboard and full screen is way more comfortable than to doing so on the calculator. The new TI-Connect CE PC software looks really nice.

ti84+nelder-mead1

Screens of the actual program running on a TI-84 Plus Pocket SE. The equation to solve is the Rosenbrock function of f(x,y) = (a-x)^2 + b(y-x^2)^2, using a=1 and b=100.

ti84+nelder-mead2

ti84+nelder-mead3

The TI-84 Plus Pocket SE took 12 minutes to complete, while its big brother TI Nspire took only 22 seconds.

TI-84 Plus Pocket SE and the Simplex Algorithm

The TI-84+ Pocket SE is the little brother of the TI-84 Plus. They are almost identical in terms of screen resolution, processor architecture and speed, and also the OS. The Pocket version measured only 160 x 80 x 21mm in dimension and weighted at 142g, considerably more compact than the classic version.

TI84+PSE1

This little critter is full of features from the 2.55 MP OS. It will easily blow away the mainstream Casio series of the same size like the fx991 and even fx5800P with TI’s built-in advanced functions like ANOVA. Nevertheless, the TI-84 Plus series is still considered a stripped down version of the TI Nspire and TI-89 Titanium, and as such personally I do not expect or intent to run on it sophisticated calculations or programs like the Nelder-Mead algorithm that fits comfortably on the Nspire or Titanium.

Having said that, many complex calculation can easily be accomplished with the rich set of advanced features available out-of-the box in the TI-84, even without programming. One such example is the linear programming method implemented in the simplex algorithm for optimization. Consider the following example: In order to maximize profit, number of products to be produced given a set of constraints can be determined by linear programming. This set of constraints can be expressed in linear programming as system of equations as

8x + 7y ≤ 4400   :Raw Material P
2x + 7y ≤ 3200   :Raw Material Q
3x + y ≤ 1400    :Raw Material R
x,y ≥ 0

In the above, two products are considered by variable x and y, representing the constraints for product A and B respectively. Each of the first three equations denote the raw material requirements to manufacture each product, for material P, Q, and R. Specifically, product A requires 8 units of raw material P, 2 units of raw material Q, and 3 units of raw material R. The total available units for these three raw materials in a production run are 4400, 3200, and 1400 units respectively. When using the Simple Algorithm to maximize the function

P = 16x + 20y

which represents the profits for product A and B are $16 and $20 each, the tableau below is set up initially with slack variables set as

  8   7 1 0 0 0 4400
  2   7 0 1 0 0 3300
  3   1 0 0 1 0 1400
-16 -20 0 0 0 1    0

TI84+PSE3

Using the *row() and *row+() matrix function, the Simplex Algorithm can be implemented without even one line of code. The final answer is obtained as 11200 which is the maximum profit by producing 200 Product A and 400 Product B.

TI84+PSE4

Nspire fight back in the overclock race

In a previous installment, fx-9860GII beats Nspire CX CAS in an overclocking match, computing the parameters for a logistic regression function by the Nelder-Mead algorithm programmed in their respective on-calculator environment. It is quite astonishing not only to see Nspire losing in the speed race, but also by how much it loses.

To give the CX a second chance, while still maintaining the overall fairness, the program on the Nspire is enhanced by localizing variables (33 of them) and nothing else. The declaration of scope for variables is believed to be a common technique for performance boost. The logic of the program remain unchanged, so is the tolerance parameter.

And the results – Nspire is catching up by doubled performance from 63 seconds to 33 seconds!

nspire_vs_casio_nelder_mead2

Estimating GARCH parameters from S&P500 index data in Nspire

Yes this could be done easily even in Excel today with a modern PC, so why abuse a calculator that is probably running on 3.3V? But dare I ask why not. Calculators today, especially the top of the line products like the Nspire, are almost on par in terms of computing power with the PC back in the days when I am in college. It is almost a fun in itself to program these little machines for calculations so complex that owners of early generation calculators back then can never dream of.

garch2

One of the usage of GARCH in finance is the pricing of options. The gist of this model is that returns follow normal distribution with volatility dependent on time. Like most models, good parameters are crucial to the success in the model’s capability, and GARCH is no exception. To try out how well Nspire will do the parameter estimation that required computation technique including processing arrays of numerical data, logarithmic, and also optimization, a list of continuous daily S&P500 index figures are loaded into the Spreadsheet application in the Nspire, and the continuous compounded returns are then calculated in the next column, by the formula

Rt = LN(St/St-1)

where st denotes the price of the underlying asset at time t.

There are 1000 data points in this test set but Nspire seems to handle it decently in the Spreadsheet application, with the help from the “Fill” function that works exactly like in Excel, so that the row index will be worked out automatically (t and t-1 correspond to the row index). My only complaint is that unlike in Excel, there is no provision in the Nspire similar to the “Shift+End+Arrow” key feature that instantly jump to the last data row with selection.

The simplest form of GARCH, GARCH(1,1), is targeted in this test for parameter estimation. Three parameters in the model, namely alpha, beta, and omega, are to be estimated using the maximum likelihood method which is a popular technique. In this particular case, i.e. when p=1 and q=1, the GARCH model can be represented by

σt+12 = ω + α • rt2 + β • σt2

The coefficients alpha and beta exhibits the measurement of persistence of volatility. The more close to 1 for their sum, the more persistent the volatility is; while the reverse (towards zero) means a quicker reversal to the long term variance. A function in Nspire is written to do this calculation which takes the list from the log returns of the 1000 S&P data stored in the Spreadsheet application as variable log_return, and the actual maximization (for likelihood) of this function in Nspire is done via the Nelder-Mead algorithm, using the following kernel distribution function with the constants (2π) removed for calculation speed yet preserving the property of proportional to the maximum likelihood.

Σ (- ln(σt2 - rt2 / σt2), t=1..n)

garch3

It took the real Nspire more than two hours to finish the computation. I think I am going back to Excel 😉 Nevertheless, doing all these again from scratch on the Nspire is really a good refresher on how these algorithms, models and formulae work.

Implementing the Nelder-Mead method on the TI Nspire

Implementing the Nelder-Mead method on the Nspire is pretty straight forward. This is after nothing turns up in the search for such library on the Internet. A sample below using the Rosenbrog function as a test target: f(x,y) = (a-x)^2 + b(y-x^2)^2, using a=1 and b=100.

nedler-mead-nspire

p is the initial parameter set with {10,10}.

nm(“nmfunc”, “p”, p) invoke the Nelder-Mead program, and specify “nmfunc” as the name of the objective function (which defined earlier); “p” as the name of the parameter set; and p the actual parameter.

Results are stored in the resultsmatrix set. 1st element is the function value, 2nd and 3rd are the x,y results respectively.

Took 22 seconds on real Nspire for this test set.

This program also helped determine the parameters for a logistic regression problem on another occasion, where it was not possible using the built-in Nspire logistic regression function since it supports only x-list and y-list but the problem involved 3 variables.