Simple Optimization Example: Linear Optimization

Linear optimization is one of the most simple techniques in inequalities, but it can be unbelievably powerful in maximizing and minimizing expressions. First I'll discuss what linear optimization is, and then apply it to several problems which get quite difficult.

Observe the following graph (of $y=0.5x-1$): It's clearly a line.

The basic principle of linear optimization is, given a linear expression, it achieves its maximum/minimum at one of the "extreme" points on its domain!

For example, we can determine the minimal and maximal values of $3x+5$ on $x\in [0, 2]$. But the technique is more powerful than that: It works on any number of variables if the expression is linear in all of them!

For example, let's do the following:

Maximize the expression $a+b+c-3abc$ where $a,b,c$ are in the interval $[-1,1]$.

Temporarily fix $b,c$: Now $a+b+c-3abc = a(1-3bc)+ (b+c)$ is linear in $a$, so it achieves a maximum either when $a=-1,1$! The same goes for $b,c$. Basically this means that we only need to check when $a,b,c \in \{-1, 1\}$ to figure out the optimization.

(And of course, if we test these, we'll find the maximum is $4$ achieved at $a=b=1,c=-1$. )

Now we will do a difficult but very amazing problem:

Let $a_1,a_2,... a_{300}$ be real numbers with sum $1$. Let $S$ be the set of all ordered pairs $(i,j)$ with $i|j, 1\le i<j\le 300$. Compute the maximal value of $\displaystyle\sum_{(i,j)\in S} a_ia_j$.

The expression is linear in each $a_i$. But it's not that simple, because each value of $a_i$ is dependent on the others, since they all sum to one. So we can't just try optimizing by setting $a_i=0,1$...

However, there is something we can try doing to get rid of all this dependency- Fix all the $a_k$'s except for some $a_i$ and some $a_j$, and let those vary. Then $a_i+a_j$ will be constant, so this will be a linear expression!

If $i|j$, we can't perform this trick because an $a_ia_j$ term ruins the linearity of everything. So we need $i\not | j, j\not | i$.

Now suppose we choose such $a_i,a_j$ with constant sum $c$. Then by linear optimization, the expression we want to maximize is some linear function of $a_i,a_j$ so the maximum occurs when one of them equals zero (we don't know which one).

The miracle is we can keep repeating this! If any $i<j$ exist with $i\not |j$, there is no reason to set one of $a_i,a_j$ to not equal zero! This means a large number of zeroes...

We can take advantage of this easily. Let $T$ be the set of all $i$ with $a_i\neq 0$. Then for all $i,j\in T$, with $i<j$, we need $i|j$ by the reasons mentioned. This means $T$ is basically a big divisibility chain!

By Newton, since the expression is a second symmetric sum in the elements of $T$, it is at most $\dfrac{\binom{|T|}{2}}{|T|^2} \left( \displaystyle\sum_{i\in T} a_i \right)^2$.

This easily simplifies to $\dfrac{|T|-1}{2|T|}=0.5 - \dfrac{1}{2|T|}$ which we maximize by setting $|T|$ to be large. Since each element of $T$ divides the elements larger than it, we see $|T|$ is maximized at $\{1,2,4,8,...256\}$ in which $|T|=9$ and the maximum is $0.5-\frac{1}{18}=\dfrac{4}{9}$.

Equality comes from setting $a_1=a_2=a_4=...=a_{256}=\dfrac{1}{9}$

Now, I will briefly touch into a related topic. There is something called linear approximation with tangent lines, or the tangent line trick. The idea is as follows:

We approximate the blue graph, which is $e^x$, with a tangent (green) line, which is $1+x$. For small values of $x$, this is a very accurate approximation, and as a result it is also a very strong inequality! (This is where the famous $e^x \ge 1+x$ comes from!) Essentially we use calculus to find a tangent line and use it to bound things, and it works best on a very restricted interval.

This isn't exactly linear optimization, so I won't go into too much detail over it. But it's cool because we can use it to prove inequalities like the following:

Let $x,y$ be reals with sum one. Show that $e^x+e^y \ge 3$.

Or more difficult ones, like

Let $a,b,c$ be positive reals with sum three. Show that

$\dfrac{a^3+2a^2}{2a^2+a+b+c}+\dfrac{b^3+2b^2}{2b^2+a+b+c}+\dfrac{c^3+2c^2}{2c^2+a+b+c} \le 3$

To prove the line is in fact a tangent we usually just use calculus...

Note: There is something called linear programming where we try to maximize expressions in some region. If you're interested, see this