Tag Archives: optimization

Constraint Optimization in R

In R, the function constrOptim provides a set of optimization routines to solve linear inequality constraint problems conveniently. Different algorithms are available, for example, to use the Nelder-Mead algorithm, just set the input parameter gradient function to null.
rconstr

Advertisements

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