Monday, January 12, 2015

Mathematical Optimization Under Uncertainty

As part of self education on mathematical optimization, I have been working my way through the book Optimization Modeling with Spreadsheets, Second Edition by Kenneth R. Baker (Amazon). I really like the book because it focuses on building models for optimization. Also, it does not bog the reader down with programming languages or fancy solvers. Instead, it uses spreadsheets and their built in solver, both of which are readily available and familiar to everyone. The implementation of the models in a spreadsheet ensures that the concepts are understood. It is too easy to fall into, I read it and therefore OF COURSE I understood it.

As I am working my way through the book, I came across "just an appendix" titled "Stochastic Programming". Stochastic Programming is techno bable for mathematical optimization under uncertaintiy. It was like wow, you can actually quantifiably perform optimization taking into account the probability of various events happening. After all, in the real world, there are scenarios and associated probabilities. There is no, x is going to definitely happen. Yah, I know, insert joke about death and taxes.

Let's actually walk through the examples in the appendix. The manufacturer has to build two types of refrigerators: standard and deluxe. The goal is optmize profit given the manufacturing constraints. In scenario 1 there is a known demand of 80 units for the standard model and at least 25 units for the deluxe model. After the optimization is performed, 80 standard models along with 70 deluxe models are produced to yield a profit of $6,100. In scenario 2 there is a known demand of 104 units for the standard model and at least 25 units for the deluxe model. After the optimization is performed, 104 standard models along with 44 deluxe models are produced to yield a profit of $6,520. There is a similar situation for the third scenario.

Now, lets take a step back and assume that scenario 1 has a probability of 0.2 and scenario 2 has a probability of 0.5. By default, scenario 3 has to have a probability of 0.3. When the optimization is performed taking into account these probabilities, a profit of $6,360 is generated. Notice that this profit is not that much different than if you had guessed at what the original scenario was going to be.

You can even get more fancy and add extra resources once you actually know the scenario. In this case, the optimization tells you to first produce 98 units of the standard model and 52 units of the deluxe model. When you determine the actual scenario, add extra resources and
  1. If scenario 1 happens, produce an additional 0 standard models and 15 deluxe models.
    1. If scenario 2 happens, produce an additional 6 standard models and 12 deluxe models.
      1. If scenario 3 happens, produce an additional 16 standard models and 0 deluxe models.
        The above optimization produces a profit of $6,994. This is slightly greater than the other profits because extra resources were added.

        A lot of details have been elided. If you are interested in digging in
        1. For a table summary of the above click here.
          1. If you want the spreadsheet that was used to generate the above numbers, click here.
            1. If you want the appendix from which the material came, click here.
              In summary, you can perform mathematically quantifiable optimization under uncertainity. All you need to say is that scenario 1 has probability x, scenario 2 has probability y, and scenario 3 has probability z. Create the model in a spreadsheet and than use its built in solver. If you want to get fancy you can have a model that says
              1. Start by doing a.
                1. When you determine which scenario is actually happening, the model will say do b if scenario 1 happens or do c if scenario 2 happens.
                  For a more mathematically rigorous approach, articles like "Brief Intro to Stochastic Programming (and Financial Modeling Applications) by Hercules Vladimirou" can be found.

                  If there is enough interest, perhaps we should start a Google group on Stochastic Optimization? It is realized that certain things will want to be kept confidential by individuals but I am sure that we can share lists of interesting artices or books. So, if you are interested in creating a Google user group, please say so by creating a comment on this blog post.

                  Also, to save people some search time, below are links to some groups and books that are related to stochastic optimization.

                  To get a list of stochastic optimization groups, click here.

                  To get a list of stochastic optimization books, click here.

                  Depending on the browser, you might have to "download" the file after you click "here" in order to actually see a web page.

                  Sunday, December 14, 2014

                  Python - Financial Industry

                  Recently, I have bumped into a decent amount of info about Python and the financial industry. Hopefully, the links below will save others some leg work
                  1. Books
                    1. Annotated Algorithms in Python: with Applications in Physics, Biology, and Finance by Massimo Di Pierro
                      1. Amazon
                    2. Derivatives Analytics with Python by Yves Hilpisch
                      1. Book's Web Home Page
                      2. Wiley
                    3. Financial Modeling in Python by Shayne Fletcher, C Gardner
                      1. Amazon
                    4. Python for Finance by Yuxing Yan
                      1. Amazon
                      2. Y Combinator Book Review
                    5. Python for Finance by Yves Hilpisch
                      1. Amazon
                      2. O'Reilly
                  2. Conferences
                    1. EuroPython 2011
                      1. Derivatives Analytics w/ Python & Numpy by Yves Hilpisch
                        1. PyVideo.Org
                        2. YouTube
                    2. PyData London 2014
                      1. DX Analytics - Python Based Library for Derivatives Analytics by Yves Hilpisch
                        1. YouTube
                  3. IPython
                    1. Interactive Financial Analytics based on VSTOXX Volatility Index by Yves Hilpisch
                  4. People
                    1. Hilpishc, Yves J
                  5. Videos
                    1. Learning iPython Notebook by James Powell
                      1. O'Reilly
                  6. Web Pages
                    1. For Python Quants Conference
                    2. New York Python Meetup Group
                    3. PyGotham
                    4. Python Quants Group
                    5. Quant Platform
                      1. PDF
                  7. Webinars
                    1. Derivatives Analytics w/ Python by Yves Hilpisch

                  Monday, September 29, 2014

                  Simulated Annealing (SA) for Mathematical Optimization

                  Lately, I have been having conversations with various people regarding simulated annealing (SA). I thought that it would be helpful to put all the references in 1 spot.

                  I am not an expert in the subject. I am just trying to become part of the conversation.

                  Below are some references for SA which you hopefully will find helpful.
                  1. Generally Applicable References
                    1. Books
                      1. Annealing Algorithm by R.H.J.M Otten and L.P.P.P van Ginneken
                      2. Introduction to Optimum Design, Third Edition by Jasbir Arora
                      3. Numerical Recipes 3rd Edition: The Art of Scientific Computing by William H. Press, Saul A. Teukolsky
                      4. Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and and Neural Computing by Emile Aarts, Jan Korst
                        1. Interesting how book suggests using Boltzman Machines to execute SA in parallel. Also, please remember that Boltzman Machines are part of the mathematical stack for deep learning.
                          1. Amazon
                          2. Simulated Annealing: Strategies, Potential Uses and Advantages by Marcos Tsuzuki, Thiago De Castro Martins
                          3. Simulated Annealing: Theory and Applications by P.J. van Laarhoven, E.H. Aarts
                        2. Articles
                        3. Internet Information
                        4. Python
                      5. Parallelizing SA References

                      Friday, August 22, 2014

                      Generate All Permutations - Heap Algorithm

                      A common problem that shows up often is to generate all the possible permutations for a set of things. Here permutation is being used in the strict mathematical sense. For example, all the permutations of [ 1, 2, 3 ] are

                      1. [ 1, 2, 3 ]
                      2. [ 1, 3, 2 ]
                      3. [ 2, 1, 3 ]
                      4. [ 2, 3, 1 ]
                      5. [ 3, 1, 2 ]
                      6. [ 3, 2, 1 ]

                      Notice that the above results in 6 possibilities. This corresponds to 3 x 2 x 1 = 3! = 6. The "!" is mathematical notation for factorial. If you are interested in a general discussion about combinations and permutations and factorials, check out Combinations and Permutations by MathIsFun.Com. For those who want a strict definition of the problem we are going to work on permutations without repetition where we choose all the entries.

                      If you were in a hurry and the number of entities that had to consider were small and you weren't familiar w/ various algorithms, nested loops could be used to generate all the permutations. However, the nested loop approach does not scale because you don't want to change the code by adding / removing loops each time change the number of entities that have to consider.

                      Luckly, we can avoid nested loops by using the Heap algorithm. The original paper Permutations by Interchanges by B. R. Heap (\[Oxford Journals - The Computer Journal (1963) 6 (3): 293-298. doi: 10.1093/comjnl/6.3.293)\] can be freely obtained by clicking here. Later on, another article on the topic was Permutation Generation Methods by Robert Sedgewick - 1977 - ACM. Unfortunately, to obtain this article, you are going to have to pay for it. Luckly, Robert Sedgewick posted material on Heap's algorithm at Princeton. To obtain that material, click here.

                      The above "official" material can be supplemented by the following material found on the web

                      1. Stack Overflow: Algorithm to generate all possible permutations of a list?
                      2. Wikipedia: Heap's Algorithm

                      Python Books on Algorithms

                      I haven't been able to find a list of Python books on algorithms and so here I am creating my own. Hopefully, it will help others

                      1. Algorithms by Robert Sedgewick, Kevin Wayne
                      2. Annotated Algorithms in Python by Dr Massimo Di Pierro
                      3. Annotated Algorithms in Python: with Applications in Physics, Biology, and Finance by Dr Massimo Di Pierro
                      4. Data Structures and Algorithms in Python by Michael T. Goodrich, Roberto Tamassia and Michael H. Goldwasser
                      5. Data Structures and Algorithms Using Python by Rance D. Necaise
                      6. Data Structures and Algorithms: Using Python and C++ by David M. Reed and John Zelle
                      7. Image Analysis, Classification and Change Detection in Remote Sensing: With Algorithms for ENVI/IDL and Python, Third Edition by Morton J. Canty
                      8. Problem Solving with Algorithms and Data Structures Using Python by Bradley N. Miller and David L. Ranum
                      9. Problem Solving with Algorithms and Data Structures Using Python by Bradley N. Miller and David L. Ranum
                      10. Problem Solving with Algorithms and Data Structures Using Python SECOND EDITION by Bradley N. Miller, David L. Ranum
                      11. Programming Computer Vision with Python: Tools and algorithms for analyzing images by Jan Erik Solem
                      12. Python Algorithms: Mastering Basic Algorithms in the Python Language by Magnus Lie Hetland

                      Monday, August 11, 2014

                      Deep Learning Mathematical Stack (Updated)

                      Deep learning seems to be a hot topic these days but I haven't been able to find a reference which states the mathematical stack needed to understand it. Below is my attempt at creating one

                      1. Markov Network Models
                      2. Ising Models
                      3. Variational Methods
                      4. Hopfield Networks
                      5. Boltzmann Machines
                      6. Restricted Boltzmann Machines
                      7. Deep Learning

                      Markov Network Models fall under the category of Probabilistic Graphical Models (PGM).

                      Below are reference

                      1. Books
                        1. Information Theory, Inference and Learning Algorithms by David J. C. MacKay
                        2. Introduction to the Math of Neural Networks Kindle Edition by Jeff Heaton
                      2. Videos
                        1. Information Theory of Deep Learning. Naftali Tishby - Aug 3, 2017
                        2. Mathematics for Deep Learning - Marc Deisenroth - Sep 13, 2017
                        3. Tutorial : Mathematics of Deep Learning - Part 1 - ComputerVisionFoundation Videos - Aug 23, 2017



                      Probabilistic Graphical Models (PGM) - Topic List

                      On my last blog post, I forgot to include links to the PGM topic list files. I have now included them below.

                      To go to the linear alphabetic list of PGM topics, click here.

                      To go to the hierarchical list of PGM topics, click here.