Data Science PT 11: Linear Programming/Convex Optimization

The canonical form of linear programming is as follows: 

and we can use matrix manipulations/tricks to create variations.

In mathematics and computer science, a canonical, normal, or standard form of a mathematical object is a standard way of presenting that object as a mathematical expression. Basically forming into one simple well known mathematical expression. 

For example, let's try to get the canonical form of this expression: 

in the general form of 

To convert minimum to maximum, we notice that the minimum of the positive number is the maximum of negative numbers which results in the expression:

.

~A is assigned to A, ~b to b, and ~c to -c. 

Now let's say Ax = b. How do we convert this? 

There's actually a ingenious way to do it. We want to add the second constraint Ax >= b, equivalent to   -Ax <= b. So ~A = [A -A], ~b = [b -b] and ~c = c. 

We’ve minimized ||x||1 here (instead of cTx), trying to optimize a system of equations. This is the formatting for linear programming. We can post costs as a linear model and bot minimize cost and maximize profit. Many work problems are linear or can be linearized at a certain point. Early formulations date back to early 20th century with the invention of the simplex method.

The simplex method has a few constraints, including linear constraints with Ax >= b and x >= 0. We want the linear function CTx to be optimized. The simplex is the outer "shell" of the polytope shown above. We want to start at some convex point, then example the neighboring vertices. Either cTx already optimal, or it’s better at neighbor. Then, we move to best neighboring vertex; iterate until done. The specific steps correspond to linear algebra.

Here, the left is a convex function and the right is a concave function. Convex functions are described by the equation 

f(λx+(1- λ)y))≤ λf(x)+(1- λ)f(y),∀x,y∈𝒳, λ∈(0,1), indicating that the line segment between any two points on the graph of the function lies above the graph between the two points.

whereas concave function are described by the resultant function above in the line, or f(λx+(1- λ)y))≤ λf(x)+(1- λ)f(y),∀x,y∈𝒳, λ∈(0,1).

In a basic convex problem, we have the following equations: 

The least squares, entropy maximization, and linear programming can all be described as convex functions.

Let's talk about Newton's method. Newton’s method finds roots of equations, f(x)=0

Instead, derivative f`=0 or gradient 𝛻f = 0. Here's the pseudocode + equations: 

We can use second order approximations which are more complicated, but also faster. 

Let's do a constructive example here. We want to compute the x1 and x2 for Newton's method. x^2 - 4x + 3. 

An application for convex optimization is gradient descent. In each iteration, select direction to pursue. We want to not overshoot or undershoot but select a direction that minimizes the cost function the fastest. 

A key sub-method is to move along direction just enough to minimize the function along that line. Example of this is the line search which an example is the golden search method.

Golden section works as follows:

Recall that taking minimum of f(x) is taking maximum of -f(x) for canonical form. We define a, a lower bound, and b and upper bound. We calculate the golden ratio [(sqrt(5) - 1)/2], and calculate a value d which is the golden ratio which is b - a. We both calculate x1, which is d + a, then do b - d for x2. Then we compare f(x1) to f(x2). If f(x1) < f(x2), we eliminate everything to the left of x2. X2 becomes the new a, with no change in b. If f(x1) > f(x2) we eliminate everything to the right of x1, then x1 is the new b with no change in a. 

Here's the pseudocode: 

def golden_section(myfunc, a, b, epsilon):

 iterations = 0

 goldenRatio = 0.618

 while abs(b - a) > epsilon: 

 iterations += 1

 d = goldenRatio * (b - a)

 x1 = a + d

 x2 = b - d

 fx1 = myfunc(x1)

 fx2 = myfunc(x2)

 if fx1 < fx2: 

 a = x2

 else: 

 b = x1

 return a, b, iterations

An example of linear programming has to do with selling T-Shirts. Say it costs $8 and $14 to produce shirts A and B and shirt A profits $2 while shirt B profits $3. We can have $20,000 of merchandise with 2,000 shirts a month. So we have the following system of equations: 

Profit = 2x + 3y

Merchandise limit: $20,000 >= 8x + 14y

$2000 >= x + y 

and the canonical form is 

max 2x+3y (x, y such that 20,000 >= 8x + 14y | 2000 >= x + y | x, y >= 0.)

Another related method to golden search is simulated annealing. It models the physical process of heating a material and then slowly lowering the temperature to decrease defects. Picture it as the water bubble rings game. At the beginning, we want to get any ring in, but as we move along, we want to get more and more precise as to not have a ring come off so we make a smaller and smaller change. It's one of the solutions that proves relatively effective to the local minimum issue. It sits as the "Goldilocks" between hill climbing/gradient descent and random walk. Here's the algorithm: