Subsections

• One-dimensional Unconstrained Optimization
  • Golden-Section Search
  • Quadratic Interpolation
  • Newton's Method
  
  
• Multidimensional Unconstrained Optimization
  • Direct Methods
  • Gradient Methods
  
  
• Contrained Optimization
  • Linear Programming
  • Optimization with Packages
  
  
• Engineering Applications: Optimization

Optimization

Figure 4.1: The illustation of the difference between roots and optima.

An optimization or mathematical programming problem

Find $\mathbf{x}$, which minimizes or maximizes $f(\mathbf{x})$

subject to

$$d_i(\mathbf{x}) \le a_i \quad i=1,2,\ldots,m$$ (4.1)

$$e_i(\mathbf{x}) = b_i \quad i=1,2,\ldots,p$$ (4.2)

where $\mathbf{x}$ is an n-dimensional design vector, $f(\mathbf{x})$ is the objective function, $d_i(\mathbf{x})$ are inequality constraints, $e_i(\mathbf{x})$ are equality constraints.

Classification of optimization problem

• The form of $f(\mathbf{x})$:
  • If $f(\mathbf{x})$ and the constraints are linear, linear programming.
  • If $f(\mathbf{x})$ is quadratic and the constraints are linear, quadratic programming.
  • If $f(\mathbf{x})$ is not linear or quadratic and/or the constraints are nonlinear, nonlinear programming.
• For constrained problem
  • Unconstained optimization
  • Constrained optimization
• Dimensionality
  • One-dimensional problem
  • Multi-dimensional problem

One-dimensional Unconstrained Optimization

Golden-Section Search

Figure 4.2: The illustation of the Golden-section search method.

Golden-section search method is similar to the bisection method in solving for the root of a single nonlinear equation. Golden-section search method can be achived by specifying that the following two conditions hold:

$$\ell_0 = \ell_1 + \ell_2$$ (4.3)

$$\frac{\ell_1}{\ell_0} = \frac{\ell_2}{\ell_1}$$ (4.4)

Defining $R=\ell_2 / \ell_1$

$$R=0.61803....$$ (4.5)

This value is called the golden ratio.

Disadvantages

• Many evaluation
• Time-consuming evaluation

Quadratic Interpolation

Quadratic interpolation takes advantages of the fact that a second-order polynomial often provides a good approximation to the shape of $f(x)$ near an optimum.

An estimate of the optimal $x$

$$x_3=\frac{f(x_0)(x^2_1 -x^2_2)+f(x_1)(x^2_2 -x^2_0)+f(x_2)(x^2_0 -x^2_1)}{2f(x_0)(x_1 -x_2)+2f(x_1)(x_2 -x_0)+2f(x_2)(x_0 -x_1)}$$ (4.6)

Newton's Method

At an optimum, the optimal value $x^*$ satisfy

$$f'(x^*)=0$$ (4.7)

With a second-order Taylor series of $f(x)$, we can find the following equations for an estimate of the optimal

$$x_{i+1} = x_i - \frac{f'(x_i)}{f''(x_i)}$$ (4.8)

Multidimensional Unconstrained Optimization

Classification of unconstrained optimization problems

• Nongradient or direct methods
• Gradient or descent methods

Direct Methods

Figure 4.3: Conjugate directions.

These methods vary from simple brute force approaches to more elegant techniques that attempt to exploit the nature of the function.

• random search : repeatedly evaluates the function at randomly selected values of the independent variables.
• univariate search : change one variable at a time to improve the approximation while the other variables are held constant. Since only one variable is changed, the problem reduces to a sequence of one-dimensional searches.

Gradient Methods

Gradient methods use derivative information to generate efficient algorithms to locate optima.

The gradient is defined as

$$\nabla f = \frac{\partial f}{\partial x}\mathbf{i} + \frac{\partial f}{\partial y}\mathbf{j}$$ (4.9)

Derivative information

• First derivative:
  • a steepest trajectory of the function
  • whether it is a optima
• Second derivative: called as Hessian, $H$
  • If $\vert H\vert > 0$, it is a local minimum
  • If $\vert H\vert < 0$, it is a local maximum
  • If $\vert H\vert = 0$, it is a saddle point

The quantity $\vert H\vert$ is equal to the determinant of a matrix made up of the second derivatives and, for example, the Hessian of a two-dimensional system is

$$H= \begin{bmatrix} \displaystyle \frac{\partial^2 f}{\partial x^2... ...l y \partial x} & \displaystyle \frac{\partial^2 f}{\partial y^2} \end{bmatrix}$$

The steepest-descent algorithm is summaried as

• Determine the best direction
• Determine the best value along the search direction.

1. Calculate the partial derivatives

   $$\frac{\partial f(\mathbf{x})}{\partial \mathbf{x}_i}$$ (4.10)

   
   

2. Calculate the search vector

   $$\mathbf{s} = - \nabla f(\mathbf{x}^k)$$ (4.11)

   
   

3. Use the relation

   $$\mathbf{x}^{k+1} = \mathbf{x}^k + \lambda^k \mathbf{s}^k$$ (4.12)

   
   
   to obtain the value of $\mathbf{x}^{k+1}$. To get $\lambda^k$ use the following equations

   $$f(\mathbf{x}^{k+1}) = f(\mathbf{x}^k + \lambda \mathbf{x}^k) = f(... ...{1}{2} (\lambda \mathbf{s}^k)^T \mathbf{H}(\mathbf{x}^k) (\lambda \mathbf{s}^k)$$ (4.13)

   
   
   To get the minimum, differentiate with respect to $\lambda$ and equate the derivative to zero

   $$\frac{df(\mathbf{x}^k + \lambda \mathbf{x}^k)}{d\lambda}= \nabla^... ...\mathbf{s}^k + (\mathbf{s}^k)^T \mathbf{H}(\mathbf{x}^k) (\lambda \mathbf{s}^k)$$ (4.14)

   
   
   with the result

   $$\lambda^\mathrm{opt} = \frac{\nabla^T f(\mathbf{x}^k) \mathbf{s}^k}{(\mathbf{s}^k)^T \mathbf{H}(\mathbf{x}^k)\mathbf{s}^k}$$ (4.15)

   
   

Contrained Optimization

Linear Programming

Four general outcome from linear programming

• Unique solution
• Alternate solutions
• No feasible solution
• Unbounded problems

Optimization with Packages

• Matlab:
  • fmin : Minimize function of one variable
  • fmins : Minimiza function of several varaibles
  • fsolve : Solve nonlinear equations by a least squares method
• IMSL : various routines are exist to solve optimization problems

Engineering Applications: Optimization

See the textbook