Revisiting a crazy global NLP problem

Minimum encompassing triangle

This looks like a simple problem. Given \(n\) 2d points, find the smallest encompassing triangle. I follow the formulation from [1]. This post is self-contained, so you don't have to go back to [1]. The main contribution here is how one could work around the performance issues of the original formulation. 

Summary

The problem can be formulated as a nonconvex quadratic problem. However, this leads to models that are very difficult for global NLP solvers: global optimality can not be proven in reasonable time, even for very small data sets. One possible way to attack the problem is to use a different measure for size of the triangle: circumference instead of the more obvious area of a triangle. Although there are explicit algorithms for this problem [3,4], here we are trying to use an optimization model.

Experience with NLP solvers on a simple economic growth model

Growth Models

In this post, we formulate and solve a relatively simple economic growth model where we want to find an optimal savings rate. Consumers can either use their income for direct consumption or they can save. Savings lead to investment and to more income down the road. The resulting NLP (nonlinear programming) model is not too complicated, and it is interesting to see how we can implement this model using different tools.

I often get the question: why not use Python or R for my (economic) models? This note tries to give an answer using a rather smallish model. Although the model is small and simple, it actually illustrates some of the problems we can face when using say Python or R code. Some of the code I present here is not very obvious, or self-explanatory. One reason is that some algorithm developers look at NLP problems as something like: \[\begin{align}\min\>&f(x) \\ &g(x)=0 \\& h(x)\ge 0\end{align}\] Unfortunately, such a representation is close to the solver, but far away from practical models. It is just the wrong abstraction level. The model implementation impedance becomes even larger if we need to provide analytic gradients. Time we could have spent on developing better models is instead wasted on error-prone low-level detailed programming. This problem is even more costly, when we think about maintenance such as bug-fixing and adding new features to the model. We'll see how this looks like for this model.  

The underlying economic model is often called a Ramsey growth model, after Frank Plumpton Ramsey [1].