Today we compare the techniques between Simplex algorithm and Nested Sampling for general Bayesian.

The Simplex algorithm solves a linear program -  set of linear equations. It takes a set of linear inequalities and a linear objective function and finds optimal feasible point by the following strategy. 

1. Find a vertex v in the feasible region 

2. While there’s a neighbor v’ of v with better objective value: set v = v’  

A linear equation involving the n dimensions defines a hyperplane when plotted in an n-dimensional space and the corresponding linear inequality defines a half-space, all  points that are precisely hyperplane or lie on one particular side of it. The feasible region of a linear program specified by a set of inequalities is the intersection of the corresponding half-spaces, a convex polyhedron.  

But what do the concepts of vertex and neighbor mean in this general context. Each vertex is the unique point at which some set of hyperplanes meet. 

Each vertex is specified by a set of n inequalities. 

Two vertices are neighbours if they have n-1 defining inequalities in common. 

On each iteration of the algorithm, the simplex has two tasks 

1. Check whether the current vertex is optimal 

2. Determine where to move next 

As we will see, both tasks are easy if the vertex happens to be at the origin. And if the vertex is elsewhere, we will transform the co-ordinate system to move it to the origin.  

When the origin is feasible, it is certainly a vertex, since it is the unique point at which the n inequalities are tight.  

The origin is optimal if and only if all ci <= 0 where ci is the contraint we try to maximize in each dimension 

If all ci <= 0, then considering  the constraints x >= 0, we can’t hope for a better objective value. Conversely if the origin is not optimal, we can improve one of the constraints. 

Thus for task 2 we can move by increasing some xi for which ci > 0. We can keep on increasing it until we hit another constraint. At that point we again have n tight inequalities and hence we arrive at a new vertex. 

When we compare the Simplex algorithm with the Nested Bayesian, we see both rely on picking a next estimate and either accepting or rejecting the new candidate.

#codingexercise
Print a two dimensional matrix in spiral form
        static void PrintSpiralRecursive(int[,] A, int left, int right, int top, int bottom)
        {
            int r = bottom - top + 1;
            int c = right - left + 1;
            if (r < 0 || c < 0) return;
            if (r == 2 && c == 2)
            {
                Console.Write("{0} {1} {2} {3}", A[top, left], A[top, right], A[bottom, right], A[bottom, left]);
                return;
            }
            if (r == 1 && c == 1)
            {
                Console.Write("{0} ", A[top, left]);
                return;
            }
            if (r == 1)
            {
                for (int j = left; j <= right; j++)
                    Console.Write("{0} ", A[top, j]);
                return;
            }
            if (c == 1)
            {
                for (int i = top; i <= bottom; i++)
                    Console.Write("{0} ", A[i, right]);
                return;
            }

            for (int j = left; j < right; j++)
                Console.Write("{0} ", A[top, j]);
            for (int i = top; i < bottom; i++)
                Console.Write("{0} ", A[i, right]);
            for (int j = right; j > left; j--)
                Console.Write("{0} ", A[bottom, j]);
            for (int i = bottom; i > top; i--)
                Console.Write("{0} ", A[i, left]);
            if (left + 1 < right && top + 1 < bottom)
                PrintSpiralRecursive(A, left + 1, right - 1, top + 1, bottom - 1);
        }
 1  2   3  4
 5  6   7  8
 9 10 11 12
13 14 15 16

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

1 2 3
4 5 6
7 8 9

1 2 3 6 9 8 7 4 5