Engineering Analysis/Optimization

Optimization

Optimization is an important concept in engineering. Finding any solution to a problem is not nearly as good as finding the one "optimal solution" to the problem. Optimization problems are typically reformatted so they become minimization problems, which are well-studied problems in the field of mathematics.

Typically, when optimizing a system, the costs and benefits of that system are arranged into a cost function. It is the engineers job then to minimize this cost function (and thereby minimize the cost of the system). It is worth noting at this point that the word "cost" can have multiple meanings, depending on the particular problem. For instance, cost can refer to the actual monetary cost of a system (number of computer units to host a website, amount of cable needed to connect Philadelphia and New York), the delay of the system (loading time for a website, transmission delay for a communication network), the reliability of the system (number of dropped calls in a cellphone network, average lifetime of a car transmission), or any other types of factors that reduce the effectiveness and efficiency of the system.

Because optimization typically becomes a mathematical minimization problem, we are going to discuss minimization here.

Minimization

Minimization is the act of finding the numerically lowest point in a given function, or in a particular range of a given function. Students of mathematics and calculus may remember using the derivative of a function to find the maxima and minima of a function. If we have a function f(x), we can find the maxima, minima, or saddle-points (points where the function has zero slope, but is not a maxima or minima) by solving for x in the following equation:

$\frac{df(x)}{dx}=0$

In other words, we are looking for the roots of the derivative of the function f. Once we have the roots of the function (if any), we can test those points to see if they are relatively high (maxima), or relatively low (minima). Some other words to remember are:

Global Minima

A global minima of a function is the lowest value of that function anywhere.

Local Minima

A local minima of a function is the lowest value of that function within a given range A < x < B. If the function derivative has no roots in that range, then the minima occurs at either A, or B.

We will discuss some other techniques for finding minima below.

Unconstrained Minimization

Unconstrained Minimization refers to the minimization of the given function without having to worry about any other rules or caveats. Constrained Minimization, on the other hand, refers to minimization problems where there are other factors or constraints that must be satisfied.

Besides the method above (where we take the derivative of the function and set that equal to zero), there are several numerical methods that we can use to find the minima of a function. These methods are useful when using computational tools such as Matlab.

Hessian Matrix

The function has a local minima at a point x if the Hessian matrix H(x) is positive definite:

$H(x)=\frac{{\partial }^{2}f(x)}{\partial x^2}$

Where x is a vector of all the independant variables of the function. If x is a scalar variable, the hessian matrix reduces to the second derivative of the function f.

Newton-Raphson Method

The Newton-Raphson Method of computing the minima of a function, f uses an iterative computation. We can define the scheme:

$x^{n+1}=x^n-\frac{f^{\prime }(x)}{f^{″}(x)}$

Where

$f^{\prime }(x)=\frac{df(x)}{dx}$

$f^{″}(x)=\frac{d^{2}f(x)}{d{x}^2}$

As we repeat the above equation, plugging in consecutive values for n, our solution will converge on the true solution. However, this process will take infinitely many iterations to converge, so oftentimes an approximation of the true solution will suffice.

Steepest Descent Method

The Newton-Raphson method can be tricky because it relies on the second derivative of the function f, and this can oftentimes be difficult (if not impossible) to accurately calculate. The Steepest Descent Method, however, does not require the second derivative, but it does require the selection of an appropriate scalar quantity ε, which cannot be chosen arbitrarily (but which can also not be calculated using a set formula). The Steepest Descent method is defined by the following iterative computation:

$x^{n+1}=x^n-ϵ\frac{df(x)}{dx}$

Where epsilon needs to be sufficiently small. If epsilon is too large, the iteration may diverge. If this happens, a new epsilon value needs to be chosen, and the process needs to be repeated.

Constrained Minimization

Constrained Minimization' is the process of finding the minimum value of a function under a certain number of additional rules or constraints. For instance, we could say "Find the minium value of f(x), but g(x) must equal 10". These kinds of problems are difficult, but fortunately we can utilize the Khun-Tucker theorem, and also the Karush=Khun-Tucker theorem to solve for them.

There are two different types of constraints: equality constraints and inequality constraints. We will consider them individually, and then we will consider them together.

Equality Constraints

The Khun-Tucker Theorem is a method for minimizing a function f(x) under the equality constraint g(x). We can define the theorem as follows:

If we have a function f, and an equality constraint g in the following form:

$g(x)=0$,

Then we can convert this problem into an unconstrained minimization problem by constructing the Lagrangian function of f and g:

$L(x)=f(x)+⟨\mathrm{\Lambda },g(x)⟩$

Where Λ is the lagrangian vector, and < , > denotes the scalar product operation of the Rⁿ vector space (where n is the number of equality constraints). Λ is the Lagrangian Multipler vector, with one entry in Λ for each equality constraint on the equation. We will discuss scalar products more later. If we differentiate this equation with respect to x, we can find the minimum of this whole function L(x), and that will be the minimum of our function f.

$\frac{dL(x)}{dx}+\left[\frac{dg(x)}{dx}\right]\mathrm{\Lambda }=0$

This is a set of n equations with 2n unknown variables (Λ and x vectors). We can create additional equations by differentiating with respect to each element of Λ and x.

Inequality Constraints

Similar to the method above, let's say that we have a cost function f, and an inequality constraint in the following form:

$g(x)\le 0$

Then we can take the Lagrangian of this again:

$L(x)=f(x)+⟨\mathrm{\Lambda },g(x)⟩$

But we now must also use the following two equations in determining our solution:

$⟨\mathrm{\Lambda },g(x)⟩=0$

$\mathrm{\Lambda }\ge 0$

These last two equations can be interpreted in the following way:

if $g(x)<0$, then $\mathrm{\Lambda }=0$

if $g(x)\le 0$, then $\mathrm{\Lambda }\ge 0$

Using these two additional equations, we can solve for our minimization answer in a similar manner as above.

Equality and Inequality Constraints

If we have a set of inequality and equality constraints:

$g(x)=0$

$h(x)\le 0$

We can combine them into a single Lagrangian with two additional conditions:

$L(x)=f(x)+⟨\mathrm{\Lambda },g(x)⟩+⟨\mu ,h(x)⟩$

$⟨\mu ,h(x)⟩=0$

$\mu \ge 0$

The last two conditions can be interpreted in the same manner as above to find the solution.

Infinite Dimension Minimization

The above methods work well if the variables involved in the analysis are finite-dimensional vectors, especially those in the R^N space. However, what if we are trying to minimize something that is more complex then a vector, such as a function? If we consider the L^{2 space, we have an infinite-dimensional space where the members of that space are all functions. We will define the term functional as follows:}

Functional

A functional is a function that takes one or more functions as arguments, and which returns a scalar value.

Let's say that we have a function x of time t. We can define the functional f as:

$f(x(t))$

With that function, we can associate a cost function J:

$J(x)=\underset{a}{\overset{b}{\int }}f(x,t)dt$

Where we are explicitly taking account of t in the definition of f. To minimize this function, like all minimization problems, we need to take the derivative of the function, and set the derivative to zero. However, we are not able to take a standard derivative of J with respect to x, because x is a function that varies with time. However, we can define a new type of derivative, the Gateaux Derivative that can handle this special case.

Gateaux Derivative

We can define the Gateaux Derivative in terms of the following limit:

$\delta F(x,h)=\underset{ϵ\to 0}{\lim }\frac{1}{ϵ}[F(x+ϵh)-f(x)]$

Which is similar to the classical definition of the derivative, except with the inclusion of the term ε. In english, above we took the derivative of F with respect to x, in the direction of h. h is an arbitrary function of time, in the same space as x (here we are talking about the L₂ space). We can use the Gateaux derivative to find the minimization of our function above.

Euler-Lagrange Equation

The Euler-Lagrange Equation uses the Gateaux derivative, discussed above, to find the minimization of the following types of function:

$J(x(t))=\underset{a}{\overset{b}{\int }}F(x(t),x^{\prime }(t),t)dt$

We want to find the solutions to this problem:

$\delta J(x)=0$

And the solution is:

$\frac{\partial F}{\partial x}-\frac{d}{dt}\frac{\partial F}{\partial x^{\prime }}=0$

The partial derivatives can be done in an ordinary way ignoring the fact that x is a function of t. Solutions to this equation are either the maxima or minima of the cost function J.

Example: Shortest Distance

We've heard colloquially that the shortest distance between two points is a straight line. We can use the Euler-Lagrange equation to prove this rule.

If we have two points in R² space, a, and b, we would like to find the minimum function that joins these two points. We can define the differential ds as the differential along the function that joins points a and b:

$ds=\sqrt{d{x}^2+d{y}^2}$

Our function that we are trying to minimize then is defined as:

$J(x)=\underset{a}{\overset{b}{\int }}ds$

or:

$J(x)=\underset{a}{\overset{b}{\int }}\sqrt{1+{\left(\frac{dy}{dx}\right)}^2}dx$

We can take the Gateaux derivative of the function J and set it equal to zero to find the minimum function between these two points.