#math effortpost

I think there are two different "big ideas" you could get out of that post. One is I think the one you're getting at. You can find new points by intersecting lines and curves.

I associate this mostly with algebraic geometry. One of the foundational results in algebraic geometry is Bezout's theorem, which says that (up to some very important technicalities) the intersection of a degree $n$ curve and a degree $m$ curve contains exactly $nm$ points. We can see that in the example I gave; we intersect a line (degree 1) and a circle (degree 2) and get two points.

But $x^4+y^4 =1$ is degree 4, so we expect our lines to intersect it four times. Instead there's only the one intersection. What's wrong?

The answer is that one of the requirements for Bezout's theorem to hold is that we're working over an "algebraically closed" field--i.e. every polynomial equation has a root. The complex numbers are algebraically closed; the reals and the rationals are not. So there are four complex points of intersection between $x^4 + y^4 = 1$ and $y = 2(x+1)$, but there's only one rational intersection.

So this idea is very important to algebraic geometry, which tends to just work over algebraically closed fields. But it's not very helpful in number theory, which wants to ask questions about the rational numbers.

The other idea is the one I want to think of, which is the idea of parametrization. (This is important in both algebraic geometry and in algebraic number theory, and eventually leads to moduli spaces which are really cool and I don't understand very well).

We didn't just prove that there are infinitely many pythagorean triples. We gave a way of finding all of them. Contrast with the case of prime numbers: we can fit a proof that there are infinitely many into a haiku, but we don't have any way of finding more that's much better than brute force.

But we actually have something even better than that. Not only can we generate all the reduced triples, we have them aligned with some other structure--the reduced triples are in a natural correspondence with the rational numbers. And the naturalness of this correspondence means that information goes both ways--e.g. a larger rational number corresponds to a more obtuse measured angle in the corresponding right triangle, which you can see from the picture.

A lot of the work of number theory involves showing that all your points are in correspondence to "something else" or have some "extra structure" on them. For instance, one of the reasons we like elliptic curves so much is that the points form a group, meaning we can add together two points (in a non-obvious geometric way) and get a new one. So we can ask, not only how many points an elliptic curve has, but what their structure is.

From a mathematical perspective, optimization is the question of maximizing some "objective function" subject to "constraints." The objective function is just a function that describes how much of something we get--it can measure profit or utility or fuzzy bunnies, whatever our goal is. (It's an "objective" function in the sense of "mission objective," not in contrast to a subjective function). The constraints are restrictions that tell us what we're allowed to do. They can describe prices of inputs, or the breeding rate of rabbits, or the rule that we aren't allowed to restrict speech, or any other limitations we want or need to put on things.

An optimization algorithm is a technique for finding this maximum. It's not too hard to state a problem where you can tell that a maximum has to exist, but it's not at all obvious what you need to do to get that best result. (If your boss comes to you and asks what decision will maximize your firm's profit, the answer "some decision, definitely" is not terribly helpful). So we're talking about ways of not just showing that some optimization problem has a solution, but of actually finding the solution.

In this post we're specifically discussing linear optimization, which means that the objective function is a linear function and the constraints are all given by linear inequalities (that is, they look like $f(\mathbf{x}) \leq 0$ where $f$ is a linear function). (We actually can relax this a bit and ask about convex functions and reasons; I'll come back to this thought at the end).

These techniques were originally developed by Leonid Kanotorovich, a Soviet mathematician who was trying to solve the central planning problem. (You can read more about the history in slatestarscratchpad's mainblog post on Red Plenty, and even more if you go read the actual book).

Kantorovich's constraints were the inputs it takes to make each good (at each factory etc); and his objective function was...Uh, well, one of the fundamental problems of central planning is that it's not clear what you should be optimizing for. Kantorovich sidestepped this by actually starting with a fixed output and trying to minimize the amount of inputs necessary. This turns out to be equivalent, and we'll come back to this equivalence later.

(You might worry about whether the actual constraints in the real world are linear. The answer is probably "no, not really." Fortunately, we can generally get pretty good results by approximating non-linear functions by linear functions--this is in fact the main point of derivatives, see my post on linear functions for more. It is true that this only works as long as we stay away from extreme edge cases, but under the quite reasonable assumption that we don't want to devote our entire economy to making men's shoes, size nine, gray, this probably isn't too big a problem).

These techniques are currently used by almost every big logistical organization: FedEx, for instance, has a massive army of people using these and related techniques to optimize their shipping organization. So while the original goal of "saving the Soviet Union's economic planning" didn't really work out, the techniques do have tremendous practical applications. After all, a corporation is just a planned economy with a potentially well-defined objective function.

So how does linear optimization work? Let's start by drawing some simple pictures. Suppose we have an economy that can produce either guns or butter--

Actually, no, wait, that's boring. Suppose you run a company that makes two products: board game versions of Tetris and Rubik's cubes that deliver electric shocks to their users. (No, I don't know why you would make and sell either of those things. Or who's buying them from you. It's your company, you tell me). And suppose you make \$5 of profit for each pointless board game and \$3 of profit for every dangerous math toy.

Your objective, presumably, is to maximize profit. We can write $T$ for the number of tetris games you make, and $R$ for the number of Rubik's Cubes you make. So your objective function is $f(T,R) = 5T + 3R$, and we can check that this is a linear function. (Note: the function stops being linear if you assume the amount you make has an effect on the price, so these techniques are most useful when no one manufacturer is a monopolist or anything).

But with just this information, you obviously maximize your profit by making "as many toys as possible." In order for the question to be interesting, we need some constraints. First of all, you (sadly for everyone else) can't make negative toys, so we have $T \geq 0$ and $R \geq 0$. Then let's say that you can make at most a hundred stupid tchotchkes a month. We can render this with the constraint equation $T + R \leq 100$. At this point the problem is still easy--the Tetris game is more profitable than the Rubik's cube, so we should make 100 of the Tetris games for a total profit of $500.

So let's add another constraint. Maybe both toys require a certain amount of plastic, and it's hard to find sufficiently low-quality plastic so you can only get 300 ounces a month. The Tetris game takes 4 ounces of plastic to make, and the Rubik's cube only takes two ounces. We have a second constraint, now, that $4 T + 2 R \leq 300$. At this point you can probably still solve the problem in your head. We want to make as many Tetris games as possible, so what's the most we can make? A little experimentation or calculus will show that you can make fifty Tetris board games and fifty electrified Rubik's cubes, and we get a total profit of $f(50,50) = 5\cdot 50 + 3 \cdot 50 = 400$ dollars.

Let's add one more contstraint. You probably don't want to work more than, say, 55 hours a month, and it takes forty minutes to make a Tetris game and only thirty to make a Rubik's cube. This gives us a third constraint, which is that $40T + 30 R \leq 3300$. And now this is hard to think about in our heads. (I don't know what the answer is yet). So we need some tools.

The first tool, when you can use it, is to draw a picture. (This is why we're still working in two variables). First let's draw a picture of what solutions the constraints allow, ignoring the feasible region for now. We can draw a line for each constraint, and shade in the set of solutions it allows:

This allows us to sketch a picture of the precise feasible region. This is a picture of all the outputs you could choose to make. So under our constraints you could make zero of either thing, or you could make ten Tetris games and twenty Rubik's cubes. But you can't make seventy of each.

Everything we've done so far works with any functions, not just linear functions. But now we can introduce two facts that make our job much easier. First, that the maximum is always on the boundary. This should be intuitive from the example: if you can make more Rubik's Cubes without making fewer Tetris games, that will obviously give you more money. This is a general theorem about linear functions on regions defined by linear inequalities.

Second, and even better, the maximum is always on a vertex. And furthermore, if two vertices yield the same output, the entire line between them will also yield that same output. So at a first pass we can just check all the vertices. Looking at the picture above, there are five vertices; checking them all we get the following table: $$ \begin{array}{cc} (T,R) & f(T,R) \\\\ (0,0) & 0 \\\\ (0,100) & 300 \\\\ (75,0) & 375 \\\\ (30,70) & 360\\\\ (60,30) & 390 \end{array} $$ So we maximize profit by making sixty terrible Tetris games and thirty wretched Rubik's cubes, for a profit of $390. The new constraint cost us ten dollars.

In that problem we could just check all the vertices; in interesting problems there can be millions of vertices, so that's not terribly efficient. But we can think about the problem in a couple of other ways. The picture I like to have in my head is a picture of moving level sets. For any output of the objective function, we can draw a line that represents "all the solutions that give that output." So for instance this is the line of all solution that have an output of 300:

Just from looking at the picture we can see that we can do better. Here's the line for 400:

And we see that we can't quite do that well. But we almost can! Conceptually we can think about slowly moving the line further and further out until it just barely hits one vertex:

This is the line for 390, and thus it is our solution.

This isn't really a general purpose algorithm, although it's quite useful for seeing and really grasping what's going on. So keep those pictures in mind.

But also think back to how we intuitively solved the easy version of the problem. We could make at most 100 toys. So at any given point we could trade out a Tetris game for a Rubik's cube or vice versa. And it's clear that trading one Rubik's cube for one Tetris game will gain two dollars, so you should keep making that trade until you can't any more.

This is the basic idea behind the simplex algorithm which was invented by George Dantzig in 1947, when he was working for the US Air Force. (If you've ever heard the story about the math PhD student who solved a major open problem because he accidentally thought it was course homework--that was this guy and related to this problem).

The algorithm: start at a vertex of the feasible region, doesn't really matter which one. Compute the gradient (derivative) of the objective function there (this is really easy since it's linear). Figure out which adjacent vertex (that is, a vertex directly connected by a line segment) is in the direction of most rapid increase, and go to that vertex. (This is called a "pivot"). Repeat.

Sometimes there are no adjacent vertices that give better results. In that case you move to one of the vertices that is "just as good". This is called "stalling" and it's fairly normal for it to happen. But there's an obvious risk of winding up in a "cycle" where you get back to a vertex that you already hit earlier--in which case the program will never terminate. But fortunately there are rules that can ensure this never happens and the program always terminates.

Importantly, the entire problem can be encoded in a giant matrix, and then this entire algorithm can be encoded as simple matrix operations. This is great, because matrix operations are fast and efficient and easy to execute.

Consequently, the simplex algorithm is "usually" very efficient. In practice it works on most problems. Under any reasonable method of generating random problems, the simplex method works very well on average. However, there are problems where the simplex method is very slow; with a carefully designed problem (such as the Klee-Minty cube) you can force it to check every vertex.

There is a whole family of so-called "vertex" or "basis-exchange" algorithms that stay on the boundaries of the feasible region. Many of them are efficient on average but all of them are vulnerable to these sorts of pathological problems where they take exponential time.

More recently (starting around 1980) Khachiyan, Karmarkar, and others developed "interior-point" methods that use information from the interior of the feasible region, and have worst-case polynomial time performance. Both types of algorithms are in common use in industry today, in almost any industry that uses large-scale logistics operations.

Another perspective we can use to look at this is the perspective of the dual problem. Duality shows up in a lot of areas of math--the ability to, essentially, take a problem and look at it from the other direction. Or a slightly different problem that gives information about the original problem.

In this case we stated our original, or "primal" problem, as trying to maximize our profit subject to some constraints, which you can think of as resource costs. The number we can set is the "number of units produced." The dual version of the problem is to try to minimize the total cost of the resources used, subject to having certain minimum prices for finished goods. The number we can set in the dual problem is the price of resources.

So in our problem, we would minimize the function $f^\dagger (x,y,z) = 100x + 300 y + 3300 z$ (the total cost of resources) subject to the constraints $x + 4y +40 z \geq 5$ and $x + 2y +30z \geq 3$ (which say that you have to get at least \$5 for every Tetris game and at least \$3 for every Rubik's cube). That is, our dual objective function is the "cost of all the resources used," and the dual constraints reflect the observation that if resource prices are "too low" relative to their value then you'll have resource shortages.

Here's a picture of the feasible region for the dual problem.  (You can see why we prefer drawing pictures of two-variable problems. )

The dual problem isn't the same as the primal, but rather a mirror. A feasible solution to the dual problem provides an upper bound for the primal problem--every solution satisfying the constraints will guarantee at least the maximum profit available to the primal problem. Conversely, every feasible solution to the primal gives a lower bound for the dual--it uses as many or more resources than the minimum possible.

This technique actually generalizes to all sorts of optimization problems. But in general, there is a "duality gap": the solution that minimizes the dual problem might not get the solution as low as the maximum to the primal problem. (Recall they are mirrors but not identical). But in the special case we're in, the linear case, that can't happen.

If there is an optimal solution to the primal problem, then there is an identical optimal solution to the dual problem. (If the dual problem is completely infeasible--there's no way to satisfy the constraints--then the primal problem is unbounded, which means you can get infinite profit. And vice versa).

This is highly related to the idea of duality and equilibria in game theory. Supposedly, Dantzig mentioned his work to von Neumann and von Neumann immediately conjectured that duality would hold because linear programming worked just like the game theory he was developing.

In fact, there's a sense in which you can think of a linear optimization problem as a two-player game played between a producer and a planning board--the producer wants to maximize profit, the planning board wants to minimize profit, and the optimum reflects the Nash equilibrium strategy. You can actually prove Nash's theorem using these linear programming techniques; the proof isn't difficult but is long and boring, and essentially reduces to "turn every game into a linear optimization problem, and then show that it has a solution."

I want to finish up by talking about two different ways we can make the problem harder.

One thing we can do is relax the linearity condition. The general problem of "optimize a function subject to constraints" is really hard; it's not that difficult to write down optimization problems that are harder than NP-complete (and thus definitely require exponential time), although most interesting ones are in NP in some form or another.

To keep things manageable, people often only search for approximate solutions--it's much easier to find a solution that's "probably close to optimal" than it is to prove that you definitely have the optimal solution. There's usually a tradeoff that you can get a more exact answer in exchange for a longer computational time.

But we can restrict the functions a bit and still get a manageable problem; this is the domain of convex optimization. A region is "convex" if you can pick any two points in the region, and the line segment connecting them is entirely contained in the region. So for example, a triangle or a circle is convex, but a star or a chevron is not.

It's not too hard to see that the regions defined by linear inequalities that we've been discussing are convex.

We say that a function is convex if the region above its graph is convex. Again, it's not difficult to see that linear functions are convex.

The simplex method does not work on convex regions--it needs to move among vertices, and convex regions (like circles) may not have any vertices, and if they do the vertices aren't necessarily special. But we still know that the optimum has to be somewhere on the boundary, and a simple modification of the interior point methods will still work. In particular, convex optimization problems still have the property that the dual problem will always overlap the primal, so the two problems have a feasible solution in common, which is optimal.

Cosma Shalizi has an excellent post on Red Plenty where he discusses some of the limits of convex optimization. Sadly the entire economy probably is not convex (which would essentially imply, among other things, that there was never increasing returns to scale). But we're fortunate enough that a number of important problems are convex and are tractable to these types of algorithms.

The other way of making this problem harder is more interesting to me personally, and actually why I originally brought this topic up. (Don't worry, you're near the end of this post!) When we solve the problem earlier, it asked for 60 Tetris games. If it had asked for 58, we still would have been happy. But what if it had asked for 58.5? We can't make half a Tetris game. What if it had told us we needed $19 \pi$ Tetris games?

The tools that allow us to find solutions will find the best real-number solution, but we might need to find a solution that's entirely made up of integers. For a lot of problems this isn't a big deal--if the algorithm calls for 1023.7 tons of concrete, you can round that off to 1024 tons without having huge problems.

So what is a linear function? Well let's start with the one-variable case. As we probably all remember via flashbacks to high school algebra, a line has equation $y = mx +b$. (We say $m$ is the slope and $b$ is the y-intercept). I prefer a variant equation $y = m(x-x_0) + y_0$, which conveys more information directly: the line has slope $m$, and goes through the point $(x_0, y_0)$.

Why is this nice? Well, primarily, it's easy to compute with. We don't have to do anything weird. We can solve it without taking any square roots or doing anything nasty. Assuming the slope isn't zero, it will hit every possible value exactly once, and we can easily tell where that happens.

(We also like lines because they're fundamental to most conceptions of geometry, but that's not going to be super relevant. It will be a little, though).

How do lines come up in calculus? Well, if you've taken calculus you might remember that people define the derivative as the "slope of the tangent line" to a function. There are a number of ways one could define the "tangent line," but relevant to our purposes, the tangent line is the linear function that best approximates your original function.

Basically, we like linear functions because they're easy to work with. When we look for the tangent line to a function $f$ at a point $a$, we're saying "okay, let's pretend $f$ is a line. What's the closest we can get to it being the same as the real $f$?"

And the answer is different depending on where you are on the graph. Below we have a graph with two tangent lines at two different points. We can see that each one looks a lot like the graph in a certain neighborhood, but they're very different from each other.

This means that we need a different derivative for every point on the graph. And the function $f'(x)$ is a function that tells you "If I look at the point $x$, then what is the line that looks the most like the graph of $f$ near that point?" And near a starting point $a$, we get the approximation $$f(x)\approx f'(a) (x-a) + f(a).$$

So with one variable, the derivative $f'(x)$ is a function that takes in a point, and outputs a line. What happens if we have more than one variable?

Well, first we can ask what the analog of a line is. If you ask most people what the two-dimensional version of a line is, after some hemming and hawing they'll probably come up with "a plane." And that's basically right.

And in fact we can see that the equation that gives a plane as its graph is something like $f(x,y) = ax + by +c$, which looks like our line equation except with an extra variable. And we can generalize this. A linear function on three variables is $f(x,y,z) = ax + by + cz + d$, and in general if we have a linear function on $n$ variables it looks like $$f(x_1, \dots, x_n) = a_1 x_1 + a_2 x_2 + \dots + a_n x_n +c= \sum_{i=1}^n a_i x_i +c.$$

Note: we can make things more compact with good notation. I'll use the convention that $\mathbf{x} = (x_1, \dots, x_n)$. You also may or may not remember that we can take the "dot product" of two vectors by $$\mathbf{x} \cdot \mathbf{y} = x_1 y_1 + x_2 y_2 + \dots + x_n y_n = \sum_{i=1}^n x_i y_i.$$ Thus a linear function is one where we have some vector $\mathbf{a} = (a_1, \dots, a_n)$ such that $f(\mathbf{x}) = \mathbf{a} \cdot \mathbf{x} + c.$

This basically just means that a linear function is one where you multiply each variable by some fixed number and then add them all together. You never multiply two variables together and you never do anything weird to them. So things are still really easy to calculate with.

So how does this relate to calculus and the idea of approximation? If you've taken a multivariable calculus course, you've probably spent some time dealing with "partial derivatives" and "directional derivatives" and such. These are all useful computational tools but are a bit beside the point for understanding what's actually going on.

Let's return to the two-variable case, because we can actually draw pictures of graphs and see what's going on. We have a function and we want the equation for a plane that looks the most like our function--the "tangent plane," which you can see below.

If you remember the details of your hypothetical multivariable calculus class, this might point you to the gradient. The gradient of a function at a given point is the normal vector to the tangent plane, and thus tells you the equation. In less technical language, the gradient at a point is a list of all the $a_i$ in the equation I gave above. And thus if the gradient of a function $f$ is $\nabla f$, then our linear approximation is given by $\nabla f(\mathbf{a}) \cdot \textbf{x} + c$.

So the "real" derivative here is the vector $\nabla f(\mathbf{x})$, which for any vector $\mathbf{x}$ gives us all the coefficients for the linear function that approximates our original function near $\mathbf{x}$. In particular, we get the approximation $$f(\mathbf{x}) \approx \nabla f(\mathbf{a}) \cdot (\mathbf{x} - \mathbf{a}) + f(\mathbf{a}).$$ Notice how similar this is to our earlier approximation! And we can use this to turn a hard-to-work-with function into an easy-to-work-with linear approximation.

But we can actually go one step further. Until now I've assumed that while my function might have many inputs, it only has one output. But for full generality we want to let our function have multiple outputs.

If a function has $n$ inputs and $m$ outputs we say it is a function from $\mathbb{R}^n$ to $\mathbb{R}^m$ or write $F: \mathbb{R}^n \to \mathbb{R}^m$. We usually break this up output by output; so we have $F(\mathbf{x}) = (f_1(\mathbf{x}), \dots, f_m(\mathbf{x}))$. Each component has many inputs but just one output, so we can compute the linear approximation just like we did before.

Since $F$ is a list of many-to-one functions, our linear approximation will be a list of vectors. And if you're clever, you might realize that a list of vectors is a matrix. The total derivative of a function $F$ at a point $a$ is a matrix $dF_\mathbb{a}$, and the approximation is $$F(\mathbf{x}) \approx dF_\mathbf{a} \cdot\mathbf{x} + F(\mathbf{a}).$$ So the best linear approximation of any function with many inputs and outputs is going to be given by some matrix the total derivative, or the Jacobian. This is basically the fundamental object of multivariable differential calculus--though it usually isn't taught that way.

Because I'm a mathematician, I can't resist abstracting one more step. (Going up one more meta-level? I dunno, I guess that's endemic around here).

When a mathematician says a function is linear, he generally means that it has the following two properties: $$f(\mathbf{x} + \mathbf{y}) = f(\mathbf{x}) + f(\mathbf{y})$$ $$f(c \mathbf{x}) = c f(\mathbf{x}).$$ In any finite-dimensional setup these functions correspond to matrices, and in the many-to-one variable setup these functions are dot products. (and in the typical single-variable case, every linear function is just scalar multiplication--or multiplication by a $1 \times 1$ matrix).

You might have noticed that in the preceeding exposition, I basically ignored the constant at the end of every equation. And that's because on technical points that makes the equation not linear in this sense. The actual linear function is the number/vector/matrix that we multiply by.

And this means we can give a very general definition of a (Frechet) derivative, for any function between two normed vector spaces. If $f: A \to B$ is a map of normed vector spaces, then $L$ is the derivative at $a$ if it is a (bounded) linear function from $A$ to $B$, and $$\lim_{x \to a} \frac{f(x) - f(a) - L(x-a)}{x-a} = 0.$$ If you're familiar with the usual single-variable derivative definition, you can write it out and see that this is the same thing.