Category Archives: Optimization

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

 

Advertisements

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.

Constructing matrix in TI Nspire for Markov chain with Poisson distribution

In calculation for Markov chain, matrix setup can be complicated evn with the user-friendly interface on the TI Nspire. The built-in function like identity(), constructMat() etc are useful on specific cases.

For Markov chain calculation, the model setup in terms of matrix sometimes get quite complicated and demanded a few exceptions from the built-in function mentioned above that are geared towards common linear algebra.

The example below attempts to simply the construction of the Markov model by use of piece-wise functions in building matrix. The problem to solve in Markov process is on a stock resupply problem, where an imaginary shop keeps stock of 1 to 3, and replenish on each day only when all stock is exhausted. Poisson distribution is assumed on the demand side.

Firstly a function called markov_prob is created, which takes the demand as variable and return the corresponding Poisson distribution. Note that how the function handle probability for demand greater than 3. A short-hand function mkp() is created afterwards to ease reading in the matrix.
markovstock1

When the function is defined, the Markov model can be formulated in a new 3 x 3 matrix created using the template. It is sometimes not easy to define state transition function as in this example problem. Therefore, the shorthand function just created will help in filling in the states as matrix elements. For example, P11 means the stock next day (Sx+1) equals stock today (Sx) which is 1, and that means the demand is zero, and thus mkp(0). There are some curve ball like P12, where Sx+1 > Sx which is not possible, since that means the shop has more stock the next day for any day with non-zero stock (i.e. negative demand), and thus the probability is zero.markovstock2

After setting up the Markov model, the equilibrium distribution can be deduced. The below is one of the methods using Nelder-Mead algorithm.
markovstock3

Based on this model, more figures can be deduced for decision making on fine tuning stock keeping strategy.