to describe the optimization function with optimization variable and the objective function .

Linear optimization programming

where and .

The following problems can be formulated as LPs.

Minimize .

This is equivalent to the LP:

This follows from that That is, .

Minimize .

This is equivalent to the LP:

This follows from that . The LP is optimal when . Then, it implies that is optimal.

Minimize subject to .

This is equivalent to the LP:

Minimize subject to .

This is equivalent to the LP:

Minimize .

This is equivalent to the LP:

Gradient Descent

for k inrange(0,N):
Approximate f by f_k according to x(k)
Do something using f_k(e.g., setting x(k+1)= argmmin f_k(x))

There are multiple forms of approximations

First-order approximation:

Usually, the algorithm here looks like

for k inrange(0,N):ifgradient(x(k))<= eps:returnx(k)x(k+1)=x(k)- step_size *gradient(x(k))

Theorem: Let . For any , the following are equivalent:

for all

for all

for all

Theorem: Let be a function with -Lipschitz gradient and be any minimizer of . The gradient descent with step size outputs a point such that in iterations.

Second-order approximation: Stochastic Approximation: for a random Matrix Approximation: Approximate by a simpler with Set Approximation: Approximate a convex set by an ellipsoid or a polytopeBarrier Approximation: Approximate a convex set by a smooth function that blows up on the boundaryPolynomial Approximation: Approximate a function by a polynomialPartial Approximation: Split the problem into two parts and approximate only one partTaylor Approximation: Mixed - Approximation: Stochastic Matrix Approximation: Approximate by a simpler random with and Homotopy Method: Approximate a function by a family of functions