Convex hull models

Convex hull as an optimization problem

In the previous posts, the construction of a convex hull played a significant role: it was an easy way to reduce the size of the data sets, often by a large amount. Somehow, it escaped me that we can try to formulate this as what turns out to be a conceptually rather simple optimization problem. This has probably little or no practical value. But it remains an interesting exercise.

Minimum enclosing circle/ellipse 2

In [1] where I discussed how to find the minimum enclosing circle and minimum enclosing ellipse around a set of points. This is a follow-up post where I extend this to sets of circles and ellipses. 

1. MINIMUM ENCLOSING CIRCLE

Here our data is a set of \(n\) circles (or disks) of different size. We want to find the smallest circle that contains all these circles. 

An example data set with random circles can look like:

----     30 PARAMETER circles  coordinates of center and radius

                   x           y           r

circle1        4.294      21.082       1.663
circle2       13.759       7.528       4.014
circle3        7.305       5.601       1.961
circle4        8.746      21.407       6.235
circle5        1.678      12.505       2.591
circle6       24.953      14.468       2.715
circle7       24.778      19.056       4.564
circle8        3.267      15.993       5.336
circle9        3.988       6.252       4.769
circle10      16.723      10.884       3.783
circle11       8.993       8.786       3.480
circle12       3.287       3.753       1.706
circle13      14.728      20.772       2.885
circle14       5.770      16.643       1.279
circle15      19.396       7.591       3.031

Minimum enclosing ellipse

Minimum encompassing circle and ellipse

This is again about finding the smallest geometric shape containing all our data points. Here I focus on easy, convex cases: a circle and an ellipse. After the last post, where I was struggling mightily with a non-convex version of this model, this should be a breeze. 

I'll discuss SDP (semidefinite programming), SOCP (second order cone programming), rotated SOCP and traditional NLP approaches using gradient based solvers. So there is a lot of ground to cover.

First let's do circles.

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].