Linear programming - the auxiliary LP

 Yesterday, I wrote a series of posts explaining how to solve a linear programming problem of the form

• Minimize the objective function $f(x)=c\cdot x$
• subject to the constraints
• $Ax=b$ where $A$ is an $m\times n$ matrix
• $x\geq 0$

The simplex algorithm works great, but you need an initial basic feasible solution to get started. Luckily, one can construct a Phase I program to decide if any feasible solutions exist, and provide such a solution if so. The last remaining piece is to turn this into a basic feasible solution, which we can do with the help of an auxiliary LP.

Recall that the phase I LP is the following

Phase 1 LP (standard)

Introduce new variables $y=(y_1,\ldots,y_n)$.

• Minimize $\sum_{i=1}^n y_i=e\cdot y $ where $e=(1,\ldots,1)$
• subject to
• $Ax+Iy=b$
• $x,y\geq 0$

If we have an optimal solution $(x^*,y^*)$ with $y^*=0$, then $x^*$ is a solution to the original problem. If all of the $y^*$ variables are non-basic, then we can easily construct a bfs for the original LP. However it is quite possible that this is not the case. To remedy this, we introduce the auxiliary LP.

Auxiliary LP

Start with the phase 1 LP and add one new variable $z$.

• Minimize $c\cdot x$
• subject to
• $Ax+Iy=b$
• $e\cdot y+z = 0$ 
• $x,y,z\geq 0$

The auxiliary LP is useful for the following reasons:

• Fact 1: If $(x,y,z)$ is optimal for the auxiliary LP, then $x$ is optimal for the original LP.
• Fact 2: If the auxiliary LP is unbounded, then the original LP is unbounded.
• Fact 3: If $(x^*,0)$ is an optimal solution to the phase 1 LP, then $(x^*,0,0)$ is a bfs for the auxiliary LP. The basic variables are the same as those for $(x^*,0)$ with $z$ added.

Facts 1 and 2 basically come from the fact that any solution to the auxiliary LP must have $y=0$ and $z=0$, because the sum of nonnegative terms $e\cdot y+z$  is equal to $0$. 

The main thing about Fact 3 is to check that the new matrix, after appending the column $\left(\begin{matrix} 0\\ 1\end{matrix}\right)$, is invertible, which I leave as an exercise.

So now we have a complete algorithm to solve LPs of the form indicated at the start of the post. I've implemented this algorithm in C# and it works quite well. The one issue that I kept grappling with is the issue of thresholds, and I essentially just kept tinkering with them until the program stopped giving me error messages. The linear systems I have been dealing with are often highly degenerate, and one thing I am picking up from these posts is that I may want to row reduce the coefficient matrix and throw away extraneous rows before implementing the algorithm. 

So now the question is, what's next? I would like to understand how to do quadratic programming, but I would also like to run through at least one real life (but smallish) example of the LP algorithm we just described both for illustrative purposes, but also so I can see how I might be able to improve it.

Linear Programming - Phase 1 algorithms

 In my previous few posts I discussed solving the LP

• Minimize $c\cdot x$
• Subject to
• $Ax=b$ and 
• $x\geq 0.$

Here $A$ is an $m\times n$ matrix, while $c$ and $x$ are $n$-vectors.

We went through the basic simplex algorithm, but it required an initial basic feasible solution to get started. In this post I want to discuss two algorithms for finding a feasible solution.

We begin with what appears to be the standard Phase 1 LP, taken from Solow's textbook.

Phase 1 LP (standard)

Introduce new variables $y=(y_1,\ldots,y_n)$.

• Minimize $\sum_{i=1}^n y_i=(1,\ldots,1)\cdot y $
• subject to
• $Ax+Iy=b$
• $x,y\geq 0$
• Initial bfs: $B=I$ is formed from the last $m$ columns of  the coefficient matrix $[A \, I]$.

Theorem: Let $(x^*,y^*)$ be an optimal solution to the phase 1 LP. Then the original LP is feasible iff $y^*=0$. In that case, $x^*$ is a solution.

Proof:

Clearly if $y^*=0$, then $b=Ax^*+Iy^*=Ax^*$, so $x^*$ is feasible for the original LP. Moreover, $x^*\geq 0$ since $(x^*,y^*)$ is feasible for the phase 1 LP.

Now suppose that the original LP is feasible with solution $x^*$. Then $(x^*,0)$ is feasible for the phase 1 LP. Moreover the objective function $f(x,y)=\sum y_i$ is zero on this solution. Moreover $f(x,y)>0$ if $y\neq 0$, so that means any optimal solution must have $y^*=0$. $\Box$

This gives us a very pretty solution to the question of when the feasible region is nonempty, but if we are to use it to continue with the simplex algorithm, we still need to have a bfs for the original LP, not just a solution. We will return to this question later when we talk about auxilliary LPs. For now, let us look at another Phase 1 LP from Best's book on Quadratic Programming.

The set up for this algorithm is slightly more general. We are looking at a region expressed by the constraints

• $a_i^Tx\leq b_i$ for $i=1,\ldots, m$
• $a_i^Tx = b_i\geq 0$ for $i=m+1,\ldots,m+r$

The question is whether the region carved out by these constraints is nonempty.

Phase 1 LP (Best's Algorithm)

Let $d=-\sum_{i=m+1}^{m+r}a_i$, and introduce a single additional variable $\alpha$. 

• Minimize $d\cdot x+\alpha$.
• Subject to:
• $a_i^Tx-\alpha \leq b_i$ for $i=1,\ldots m$
• $a_i^Tx \leq b_i$ for $i=m+1,\ldots,m+r$
• $-\alpha\leq 0$

Best says that taking $x=0$ and $\alpha$ sufficiently large is a  feasible solution to the phase I LP, which is true, but he does not say that it is a basic feasible solution. Indeed, this is an inequality constrained LP, so the discussion from our previous posts does not apply. In his book, Best develops an algorithm for optimizing a quadratic objective function subject to both equality and inequality constraints, which he specializes to the case of an linear objective function. I will have to dig into that algorithm more to see what initial data is required. Perhaps simply a feasible solution is enough.

 

Leaving these concerns aside, let us check to see if Best's algorithm really does determine if the original LP is feasible.

Proposition: Best's Phase 1 LP is bounded from below. Hence an optimal solution exists. 

Proof:

The objective function 

$$d\cdot x+\alpha=\alpha-\sum_{i=m+1}^{m+r}a_i\geq \alpha -\sum_{i=m+1}^{m+r}b_i\geq-\sum_{i=m+1}^{m+r}b_i.$$

$\Box$

Theorem: Let $(x^*,\alpha^*)$ be an optimal solution to Best's Phase 1 LP. Then the initial LP is feasible iff $\alpha^*=0$.

Proof: We start with the lower bound on the objective function 

$$d\cdot x^*+\alpha^*\geq -\sum_{i=m+1}^{m+r}b_i.$$

If the initial LP were feasible with solution $x^*$, then $(x^*,0)$ would make the above inequality an equality. Hence if $d\cdot x^*+\alpha^*> -\sum_{i=m+1}^{m+r}b_i$, the initial LP is not feasible. If on the other hand $d\cdot x^*+\alpha^*= -\sum_{i=m+1}^{m+r}b_i$, then $\alpha=0$ and the inequalities $A_ix\leq b$ for $i=m+1,\ldots,m+r$ must actually be equalities, implying $x^*$ is a feasible solution to the original LP. $\Box$

So it looks like Best's Phase 1 algorithm checks out, and is actually quite clever.

Linear Programming: pivoting

 Let us summarize our progress so far. 

• $x=(x_B,x_N)=(B^{-1}b,0)$ is a basic feasible solution to $Ax=b, x\geq 0$, 
• $j^*$ is an index such that $d:=(c_N-c_BB^{-1}N)_{j^*}<0$ and
• $t^*=\min\{-x_i/d_i\,|\, 1\leq i\leq n\text{ and } d_i<0\}$. Let $k^*$ be a choice of index where this minimum is realized.

Then we have concluded that $x+t^*d$ is a feasible solution. In this post we want to show that it is a bfs, and how to calculate the new index sets.

One thing to note: if $t^*=0$ then we aren't actually moving to a different point, but we are moving to a different bfs representation of that same point. In this case the objective function doesn't strictly decrease, which means that if we repeat the basic steps in our algorithm, we might cycle back to the same point. Apparently cycling is quite rare in practice, though one can also preclude its happening through the right choice of pivoting rule - i.e. which $j^*$ and $k^*$ to pick! (One such choice is Bland's Rule.) 

Theorem: With the hypotheses above, $x+t^*d$ is a bfs $(x_{B'},x_N')$ where $B'$ is formed by replacing column $k^*$ of $B$ with column $j^*$ of $N$. 

Proof: By construction, we zeroed out the $x_{k^*}$ variable, so $x_{N'}=0$. If we can show $B'$ is invertible, then automatically $x_{B'}=(B')^{-1}b$ and we are done. To see that $B'$ is invertible, we claim that $B'=BE$ where $E$ is formed by replacing column $k^*$ of the $m\times m$ identity matrix with $-d_B$. 

If $k\neq k*$, $(BE)_{\cdot k}=BE_{\cdot k}=BI_{\cdot k}= B_{\cdot k}$.

On the other hand $(BE)_{\cdot k^*}=BE_{\cdot k^*}=B(-d_B)=B(B^{-1}N_{\cdot j^*})=N_{\cdot j^*}.$ By definition the column vector $N_{\cdot j^*}$ is equal to $B'_{\cdot k^*}$.

Finally we need to show that $E$ is nonsingular. This follows because $(d_B)_{k^*}\neq 0$. So one can use row operations to clear out the rest of the $k^*$ column to get a diagonal matrix with $1$'s on the diagonal, except for an occurrence of $(d_B)_{k^*}$. $\Box$

This operation of updating $B$ to $B'$ is called pivoting.

Now we have all the ingredients for the basic simplex algorithm to minimize an objective function $c\cdot x$ subject to the constraints $Ax=b$ and $x\geq 0$.

1. Start with an initial bfs $x=(x_B,x_N)=(B^{-1}b,0)\geq 0$.
2. Compute $c_N-c_BB^{-1}N$.
3. If  $c_N-c_BB^{-1}N\geq 0$, $x$ is optimal. Terminate program.
4. Otherwise, select $1\leq j^*\leq n-m$ such that $(c_N-c_BB^{-1}N)_j<0.$
5. Compute $d_B=-B^{-1}N_{\cdot j^*}.$
6. If $d_B\geq 0$, the LP is unbounded. Terminate program.
7. Otherwise, select $1\leq k^*\leq m$ so that $-x_{k^*}/d_{k^*} = \min\{-x_i/d_i\,|\, 1\leq i\leq n\text{ and } d_i<0\}$.
8. Create a new bfs by replacing the $k^*$ column of $B$ with the $j^*$ column of $N$. 
9. Go to step 2.

This is all very well, but how do we find that initial bfs? How do we even determine if there is a feasible solution at all? That was actually my primary motivation for looking into this. How can we find a solution to $Ax=b$ such that $x\geq 0$? Let's not even worry about the objective function!

In the next post, I want to introduce what is called the phase I program. This is a linear program formed from the original, which has the property that it has an obvious bfs, and such that the solution can tell us if the initial problem was feasible. In fact, I plan to explore two different constructions. One is given in the book Linear Programming by Daniel Solow. The other is from the book Quadratic Programming with Computer Programs by Michael J. Best. Solow's phase I algorithm looks pretty standard from the various sources I have looked at. Best's algorithm appears to me much more efficient, requiring only one additional variable, and if it works, it seems to be a major improvement. I am a bit skeptical, but hopefully we can sort it out in subsequent posts.

Linear programming: improving a basic feasible solution

 Recall our basic set up. We have a linear program

• Minimize $c\cdot x$ where $x$ and $c$ are $n$-vectors.
• subject to the constraints
• $Ax=b$ ($A$ is an $m\times n$ matrix.
• $x\geq 0$

and we have decided to look for basic feasible solutions, which correspond to partitioning the index set of columns of $A$ into the $B$ and $N$ indices. Somewhat abusing notation, $B$ and $N$ are also the submatrices of $A$ formed by these columns. $x$ is said to be a basic feasible solution if $x_N=0$, and $x_B=B^{-1}b\geq 0$.

In the last post we saw that if $x$ passes the test for optimality $c_N-c_BB^{-1}N\geq 0$, then it is optimal. In this post we consider what happens if our bfs fails the test. Our first step will be to find a direction $d$ along which the objective function decreases. For calculus aficionados, denoting the objective function by $f(x)=c\cdot x$, the directional derivative in the direction of $d$, is just given by $c\cdot d$. Hence we want to find a direction $d$ such that $c\cdot d<0$. (We also need the direction to point into the polytope.)

Theorem: If $x$ is a bfs which fails the test for optimality, let $j$ be an $N$-index  such that $1\leq j\leq n-m$ and $(c_N-c_BB^{-1}N)_j<0$. Let $d=(d_B,d_N)=(-B^{-1}N_{\cdot j},I_{\cdot j})$, where $I$ is the $(n-m)\times(n-m)$ identity matrix. Then $c\cdot d<0$.

Proof:

$$c\cdot d = c_Bd_B+c_Nd_N=-c_BB^{-1}N_{\cdot j}+c_NI_{\cdot j}$$

$$\hspace 4em = (c_N-c_BB^{-1}N)_j<0$$

$\Box$

So we have a direction $d$, possibly several. Let $j^*$ be some choice of index such that $(c_N-c_BB^{-1}N)_j<0$ which gives us this direction. Next we must determine how far to go in the direction $d.$ That is, if we have a bfs $x$, and a direction $d$, how big can we make $t$ so that $x+td$ remains in our feasible polytope. One nice thing is that the equality constraints $Ax=b$ remain true along the entire line if $d$ is of the special form $(-B^{-1}N_{\cdot j},I_{\cdot j})$.

Lemma: Suppose $x=(x_B,x_N)=(B^{-1}b,0)$ is a bfs for $Ax=b$ and $d=(d_B,d_N)=(-B^{-1}N_{\cdot j},I_{\cdot j})$ for some $j$, then for all $t$ $A(x+td)=b$.

Proof:

It suffices to show that $Ad=0$. 

$$Ad=Bd_B+Nd_N=B(-B^{-1}N_{\cdot j})+NI_{\cdot j}=N_{\cdot j}-N_{\cdot j}=0.$$

$\Box$

So we need to find the maximal $t$ so that the nonnegativity constraints $x\geq 0$ are satisfied.

Lemma: Suppose $x\geq 0$ is a solution for $Ax=b$ and $d$ is a direction having at least one negative component, then

$$t^* = \min\{-x_i/d_i\,|\, 1\leq i\leq n\text{ and } d_i<0\}$$ has the property that $x+t^*d\geq 0$. In particular, if $x,d$ are as in the previous lemma, then $x+t^*d$ is feasible.

If $d\geq 0$, the LP is unbounded: the entire ray $x+td, t\geq 0$ lies in the feasible region and $f$ is decreasing along it.

Proof of lemma: 

By the previous lemma, we just need to satisfy the inequality constraints $x\geq 0$. Let us check for each coordinate $x_i$. If $d_i\geq 0$, then $(x+td)_i = x_i+td_i\geq 0$ for all $t>0$. Otherwise suppose $d_i<0$. Then $(x+t^*d)_i = x_i+t^*d_i$, and we know $t^*\leq -x_i/d_i$ by definition, so $t^*d_i\geq -x_i$ and $x_i+t^*d_i\geq x_i-x_i=0$.

$\Box$

In summary, we have chosen a direction along which the objective function decreases that lies in the affine subspace $Ax=b$. Then we have calculated the maximum distance one can travel along this ray and stay in the positive orthant. 

In the next post we will reinterpret this operation combinatorially and show that $x+t^*d$ is also a bfs.

Linear programming and the test for optimality.

[Note: I am using Linear Programming by Daniel Solow as a reference for this and future posts. This is an economical Dover Book which I highly recommend!]

Our goal in this post is to describe an algorithm for solving a particular type of linear program, one which is an optimization problem of the following form:

• Minimize $f(x)=c\cdot x$ 
• Subject to
• $Ax=b$
• $x\geq 0$

Let's just take a step back and think about this problem for a second. $Ax=b$ is some affine subspace of $\mathbb R^n$, and we are considering its intersection with the positive orthant. This gives us some higher dimensional polytope, and we are trying to identify the point that minimizes $f$. Since $f$ is a linear function, such a point, if it exists, will have to be one of the vertices of this polytope. Unfortunately, a polytope can have exponentially many vertices in the number of constraints, so any method that seeks to enumerate all vertices first is going to be very slow.

I am going to outline a method, due to Dantzig, called the simplex method. There are two ingredients of this method that make it work:

• There is a simple test to check if a point is optimal. So if you happen to land on an optimal point, you can easily check if you are done.
• If you are not on an optimal point, you can find a direction where $f$ decreases, and walk along an edge of the polytope to find a new point. 

You do need an initial vertex to get the algorithm started (more on that later), but once you have it, you can keep walking along edges, decreasing $f$ each time, until you find the minimum.

Next lets think about what a vertex of this polytope is combinatorially. To begin, we will assume that the solution set to $Ax=b$ is generic in the sense that the rows of $A$ are linearly independent. That means it carves out a codimension $m$ affine subspace of $\mathbb R^n$. Generically, this will intersect an $m$ dimensional subspace in a point, so the corners of our polytope will come from setting $n-m$ coordinates equal to $0$. And indeed, if we set $n-m$ variable equal to $0$, we are left with the same number of unknowns as equations, and we expect there to be a unique solution generically. This motivates the definition of what is known as a "basic feasible solution" or bfs for short.

Definition: A basic feasible solution (bfs) to the linear system $Ax=b, x\geq 0$, is a vector $x$ such that

• there is a nonsingular $m\times m$ submatrix of $A$ formed by choosing $m$ columns, denoted by $B$, and the remaining columns are denoted by $N$ such that
• $x_B=B^{-1}b$
• $x_B\geq 0$, and
• $x_N=0$

Here $x_B$ and $x_N$ are the projections of $x$ onto the subspace spanned by the $B$ and $N$ columns of $A$ respectively. 

Again, a bfs is generically nothing more than a vertex of the solution polytope in the first orthant. If $Ax=b$ is not generic, one could first row reduce the system and throw out the $0$ rows. There are other options available as well to create a system with an initial bfs.

Let us return now to the two ingredients I mentioned above, a test for optimality, and a method to determine a direction to walk if the current point is not optimal.

Test for optimality: Consider the linear program to minimize $f(x)=c\cdot x$ subject to $Ax=b, x\geq 0$. Let $x^*$ be a bfs with $(x_B,x_N)=(B^{-1}b,0)\geq 0$. If $$c_N-c_BB^{-1}N\geq0$$ then $x^*$ is optimal for this LP.

Proof:

Let $x=(x_B,x_N)$ be some other feasible solution. We want to show $c\cdot x\geq c\cdot x^*$.

$$ c\cdot(x-x^*) = c_B(x_B-x_B^*)+c_N(x_N-x_N^*) $$

$$\hspace{2em}=c_B[B^{-1}(b-Nx_N)-B^{-1}b]+c_N(x_N-0)$$

Here we use that $x$ is feasible, so $Ax=Bx_B+Nx_N=b$, and solving for $x_B$, we get $x_B=B^{-1}(b-Nx_N)$.

Continuing,

$$c_B[B^{-1}(b-Nx_N)-B^{-1}b]+c_N(x_N-0)=c_B[B^{-1}b-B^{-1}Nx_N-B^{-1}b]+c_Nx_N$$

$$\hspace{4em}=-c_BB^{-1}Nx_N+c_Nx_N$$

$$\hspace{4em}=(c_N-c_BB^{-1}N)x_N.$$

So to reiterate, for any feasible solution $x$, and any bfs $x^*$, we have the equation

$$c\cdot(x-x^*)=(c_N-c_BB^{-1}N)x_N.$$

By hypothesis, $(c_N-c_BB^{-1}N)\geq 0$, and by feasibility $x_N\geq 0$. So if $x^*$ passes the optimality test, then $c\cdot x\geq c\cdot x^*$ for any feasible solution. Hence it really is optimal. $\Box$

Now, what about the converse? Can we show that if a feasible solution is optimal, then it is a basic feasible solution satisfying the optimality test? This is a good question which we will return to later. To get some intuition, let's do an example.

Example: Minimize $x+2y+3z,$ subject to $x+y+z=1$ and $x,y,z\geq0$. 

There are $3$ basic feasible solutions. $(1,0,0)$, $(0,1,0)$ and $(0,0,1)$. In each case $B$ is the $1\times 1$ matrix with a $1$ in it. So $B=B^{-1}=(1)$, while $N=(1,1)$. For the first basic feasible solution we have $c_N=(2,3)$ and $c_B=(1)$. So we get

$$c_N-c_BB^{-1}N=(2,3)-(1)*1*(1,1)=(1,2)\geq 0.$$

So indeed $y=z=0$ gives an optimal solution. It is interesting to note that this works even in the degenerate case when we consider $x=y=z=0$. 

This seems like a good place to stop for this post. In the next post, we'll look at how to find an improved bfs if your existing bfs fails the test for optimality.

Solving linear systems, the pseudoinverse, and linear programming.

Suppose we want to solve a system of linear equations $Ax=b$. There are many ways to go about this. If $A$ happens to be a square invertible matrix, you can just write $x=A^{-1}b$. If $A$ is not square, or is not invertible, then we have to look for other methods. One trick that often works is to multiply both sides of the equation $Ax=b$ by the transpose of $A$, to get

$$A^TAx=A^Tb$$

The matrix $A^TA$ is a square matrix, and in good cases, it is actually invertible, so we have

$$x=(A^TA)^{-1}A^Tb.$$

This is actually a special case of the Moore-Penrose pseudoinverse of a matrix $A^+$. When $A^TA$ is invertible, we have that $A^+=(A^TA)^{-1}A^T$, but $A^+$ is defined for any matrix.

It is not my intention to get deep into the theory of pseudoinverses, but I do want to point out some important properties. (See wikipedia for more detail.)

• The system $Ax=b$ has at least one solution if and only if $AA^+b=b$.
• If a solution exists, $x=A^+b$ is the solution with smallest Euclidean norm. (i.e. it is closest to the origin.)
• If a solution exists, one can obtain all solutions by $x=A^+b+(I-A^+A)w$ for an arbitrary vector $w$.  

Calculation of pseudoinverses is widely supported in software libraries. For example, in C#, I use the MathNet numerics package, and it is a convenient way to solve linear systems.

Instead of finding the solution closest to the origin, what if you want to find the solution closest to some other point $x_0$?

Exercise: Let $A$ be an $m\times n$ matrix. What is a method for finding the solution to a system of equations $Ax=b$ which is closest to a given $x_0\in\mathbb R^n$.

Solution: Subtract $Ax_0$ from both sides of the equation to get: $$A(x-x_0)=b-Ax_0.$$

Then $x-x_0=A^+(b-Ax_0)$ is the solution such that $x-x_0$ is closest to $0$. Thus $$x=A^+(b-Ax_0)+x_0$$ is closest to $x_0$. $\Box$

We have just solved a simple quadratic optimization problem, that of minimizing the distance to a point of a solution to a linear system. 

Let us consider a slightly more complex question. 

Problem: Minimize the distance to a point $x_0$ of a solution to $Ax=b$, assuming each coordinate of $x$ is nonnegative.

This is a more difficult question, and even the simpler feasibility question is not so obvious:

Feasibility Problem: Does there exist a solution to $Ax=b$ where each coordinate of $x$ is nonnegative?

The feasibility problem can be solved using the technique of linear programming, which for our purposes means that we want to minimize some linear objective function $f\colon \mathbb R^n\to\mathbb R$ subject to the constraints $Ax=b$ and $x\geq 0$. (Although it looks like a typo, the convention is that $x\geq0$ means each coordinate of $x$ is nonnegative.) At first glance, this seems like a harder problem than determining feasibility, but bear with me. Once we have set up the algorithm for solving linear programs of the above form, we will be able to easily apply it to the feasibility issue.

In order to make these posts as readable as possible, I'll stop here and continue in the next post to talk about linear programs.

Toward the 4D Poincare Conjecture

The Disc Embedding Theorem is a recent book carefully explicating the work of Mike Freedman in proving the topological 4D Poincare Conjecture. I am very excited about this book. I have always wanted to understand the proof of the theorem, but prior to this book, there has not been a feasible accessible approach to it. A dream of mine is to be able to actually see one of the crazy topological disks that the proof creates, for example bounding a topologically slice knot.

The book is based on a series of lectures that Freedman gave, though saying that tends to obscure the amount of work the contributors of the book put into it! One nice feature of the book is its reflection of the structure of Freedman's original presentation, introducing important techniques through historical examples.

One such example is the "shrinking" proof of the Schönflies Theorem. Not only is this a cool and foundational result in topology, the argument introduces the concept of shrinking, which figures into the 4D proof.

I'd actually like to go through this proof of Schönflies. It is super elegant and really showcases the power of point set topology as found in Munkres's standard text that so many of us learned from as undergraduates!

Definition: A subset $X$ of an $n$-manifold $M$ is said to be cellular if it is a nested intersection of countably many closed $n$-cells. More precisely, $X=\cap_{n\geq 1} C_n,$ where $C_n$ is homeomorphic to the closed $n$ dimensional ball $D^n$, and $C_{n+1}\subset \operatorname{int}C_n.$

I invite the reader to come up with examples of cellular sets. The one given in the book is a literal letter $X$, which you can imagine a nested series of disks approaching. You can also imagine more exotic examples like a truncated topologist's sine curve, or simply connected sets with fractal like filaments.

Of course $X$ has to be compact. It seems obvious that $X$ has to be connected and simply connected, though I don't even see a proof of these "easy" facts. In fact, I would bet that $X$ is contractible, though I would have to consider further why that is the case. 

Update: After thinking about it, aside from connectivity, these "obvious" facts are wrong. First, the topologist's sine curve in the plane, defined by $Y=\{(x,\sin(1/x)\,|\,0<x\leq 1\}\cup \{0\}\times[-1,1],$ is a cellular set. I learned this by watching a video of Arunima Ray. You can see it is a cellular set by having each successive closed cell trace out more of the oscillations of the sine curve. Hence, cellular sets do not have to be path connected. Indeed, one can modify this example by considering the topologist's sine curve of revolution in $\mathbb R^3$, formed by rotating $Y$ around the $y$-axis. This space is not simply connected.

As for connectivity, suppose $X$ is separated by sets $U$ and $V$ which are open in the ambient manifold. Then $C_i\subset U\cup V$ for sufficiently large $i$, but then $U\cup V$ would separate $C_i$ which is a contradiction.

Cellular sets seem like they can get pretty pathological, but in fact we have the following theorem.

Theorem: If $X$ is a cellular set in a compact manifold $M$, then the quotient map $\pi\colon M\to M/X$  is a homeomorphism.

The proof of this fact is a beautiful function space argument. One constructs homeomorphisms $h_\epsilon\colon M\to M$ which collapse $X$ to small radius and then argue that the sequence $h_\epsilon$ converges to a limit homeomorphism in the uniform topology on the appropriate function space. 

In a follow-up post, I'll sketch the proof of the topological Schönflies theorem.