Category 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

Advertisements

Building blocks of genetic algorithm in TI Nspire

Genetic algorithm is one of the more popular evolutionary algorithm with wide range of usage including optimization. While there are a lot of implementation of this technique, including the one as an option in the Excel solver, building one is a very good choice to understand the underlying process.

The TI Nspire provided a rich set of matrix operations that can be utilized to model the data structure required genetic algorithm. For example, creating an initial population with arbitrary size of binary, integer, or real numbers.

ga1

The cross over operation can be modeled as extracting part of a matrix using the augment function.

ga2

Fitness function can be dynamically defined using the expr function available in the Nspire environment.ga3

 

GARCH model in R

A much more practical approach than calculating GARCH parameters on a calculator is to do it in R. Not only is there is available packages, retrieving financial data for experimenting is also a piece of cake as the facilities built-in offered convenient access to historical data.

To use GARCH in R the library must be installed first.

fgarch1

To test the library, data are imported using the tSeries package.

fgarch2

 

A plot of the log return.

fgarch3a

fgarch3

 

Before running the GARCH model, a QQ plot is reviewed.

fgarch4a
fgarch4

 

Finally, the GARCH model is created using the command below.

fgarch6

 

Density plot.

fgarch5a

fgarch5

 

With trace=off a clean model can be printed after running the model.

fgarch7

Training neural network using Nelder-Mead algorithm on TI Nspire

In this installment the Nelder-Mead method is used to train a simple neural network for the XOR problem. The network consisted of 2-input, 1-output, and 2 hidden layers, and is fully connected. In mainstream practical neural network, back propagation and other evolutionary algorithms are much more popular for training neural network for real world problem. Nelder-Mead is used here just out of curiosity to see how this general optimization routine performed under neural network settings on TI Nspire.
neural-network-xor1

The sigmoid function is declared in an TI Nspire function.
neural-network-xor2

For the XOR problem, the inputs are defined as two lists, and the expected output in another.
neural-network-xor3

The activation functions for each neuron are declared.
neural-network-xor4

To train the network, the sum of squared error function is used to feed into the Nelder-Mead algorithm for minimization. Random numbers are used for initial parameters.
neural-network-xor6
neural-network-xor7

Finally the resulting weights and bias are obtained from running the Nelder-Mead program.
neural-network-xor8

The comparison graph of the performance of the Nelder-Mead trained XOR neural network against expected values.
neural-network-xor9

 

Optimizing optimization code in TI-84 program

As shown in a previous installment on running the Nelder-Mead optimization of the Rosenbrock function in TI-84, its hardware is not up to the challenge for problems of this kind. It is however an interesting case to learn from this program that took a considerable amount of time (in minutes), when most TI-84 programs complete in seconds, to grasp the technique in writing optimized code.

The problem used in the setting is the Rosenbrock function:
nelder-mead-84-code-optimization3

Two techniques were used to try to optimize the code. The first one is to in-line the function (in this case the Rosenbrock function). In the original version this function is stored in a string value to be evaluated whenever necessary by using the TI-84 expr() function. The idea from common in-lining is borrowed to see if it works in TI-84. As shown in line 44 below, the Rosenbrock function replaced the original expr() function call.

nelder-mead-84-code-optimization2b

Another technique is to remove unnecessary comments. For most modern languages this is never considered a problem but for simple calculators it is speculated valuable processing time may be spent on processing comments that contribute nothing to the algorithm.
nelder-mead-84-code-optimization1

Both programs returned the same results. To compare the gain in speed, the same set of initial parameters and tolerance were used in both the original and code-optimized program. Surprisingly, the inline method does not yield any gain while removing all those “:” that were used for indentation does improve the speed. The average of the original program is 183 seconds while the program with cleaned code is only 174 seconds, which is around 95% of the run time of the original program.
nelder-mead-84-code-optimization4

 

 

 

Solving a primary school math problem with Excel Solver

Since the last installment with a controversial primary school mathematical question, another interesting but no less challenging question is being popularized recently on local social media. The question involved finding the value of 9 single digit variables, namely A to H and P, that will fulfill the following simple calculation, where A to H are all of different values, and

primarydifficultexcel6

As reported in local newspaper, this question originated from a primary school for provoking student’s mathematical thinking and is not in standard syllabus. Yet it is challenging even for university graduates.

It is not the intention here to discuss the pedagogy of this problem, but only to explore solving this interesting problem using Excel without any programming.

The Excel Solver is able to solve this question by modelling it into constraints. Usually for Solver problems the variables are modeled in single cell values, but since this question mandated some intrinsic properties that are not easy to be defined in the Solver dialog, a special matrix is used instead of single cell value like in the below so that constraint of each variable carries different value can be defined.primarydifficultexcel1

The various constraints are modeled in the Solver dialog. Each sum of row must be one implies only one digit is selected for each run for A to H. Likewise each sum of column must be equal or less than one implies no duplicate digits for each run. Integer constraint is also applied. The target cell containing the equation of PPP – (AB – CD + GH) is set to zero. Simplex-LP method is selected for this problem, while it was believed that evolutionary methods better suit the model as the matrix has high resemblance of genes.
primarydifficultexcel2

Running the Excel Solver to obtain the result. On an Intel Core i5 it took almost 2 seconds!
primarydifficultexcel3

A more descriptive diagram showing the relationship between cells that the model is comprised of. The column next to the Sum of row one are sumproduct cells that will naturally return the values represented by each variable according to the selected single digit value.
primarydifficultexcel9

primarydifficultexcel8

Excel file download

The Excel Solver is not just versatile but also is fun in itself to work with tricky problem like this “primary school” question.