Optimization Techniques

Method: optimisation by differential calculus. Write the objective (surface area), eliminate one variable using the constraint (volume), set the first derivative to zero and check the second derivative.

Formulation

Let $r$ = radius and $h$ = height.

• Objective: $A = 2\pi r^2 + 2\pi r h$ (minimise)
• Constraint: $V = \pi r^2 h = 2\ \text{m}^3 \Rightarrow h = \dfrac{V}{\pi r^2}$

Substitute $h$:

$$A(r) = 2\pi r^2 + \frac{2V}{r}$$

Stationary point

$$\frac{dA}{dr} = 4\pi r - \frac{2V}{r^2} = 0 \;\Rightarrow\; r^3 = \frac{V}{2\pi}$$ $$r = \left(\frac{2}{2\pi}\right)^{1/3} = 0.6828\ \text{m}$$

Then $D = 2r = 1.3656$ m and

$$h = \frac{V}{\pi r^2} = \frac{2}{\pi (0.6828)^2} = 1.3656\ \text{m} = 2r$$

so the best tank has height equal to diameter.

Check for minimum

$$\frac{d^2A}{dr^2} = 4\pi + \frac{4V}{r^3} = 12.566 + \frac{8}{0.3183} = 37.7 > 0$$

The second derivative is positive, so this is a minimum.

Minimum area

$$A_{min} = 2\pi (0.6828)^2 + 2\pi (0.6828)(1.3656) = 2.929 + 5.859 = 8.79\ \text{m}^2$$

Answer: $D = h = 1.366$ m, $A_{min} = 8.79\ \text{m}^2$ (second derivative $= 37.7 > 0$).

(a) Golden section search

It is an interval-reduction method for a unimodal function (one minimum in the interval). Two interior points are placed at

$$x_1 = b - 0.618(b-a), \qquad x_2 = a + 0.618(b-a)$$

• If $f(x_1) < f(x_2)$, the minimum lies in $[a, x_2]$, so set $b = x_2$.
• Otherwise it lies in $[x_1, b]$, so set $a = x_1$.

The old interior point is reused as one new interior point, so each iteration needs only one new function evaluation and shrinks the interval by 0.618. Exhaustive search needs many evaluations for the same accuracy, so golden section is much cheaper. It needs no derivative.

(b) Numerical

Initial $[a,b] = [1,5]$, length 4.

After four iterations the interval is $[2.889, 3.472]$ (length 0.583, which is $4\times0.618^4$).

Estimated minimum at the mid-point: $x^* \approx 3.18$, $f \approx 27.09$.

Check by calculus: $f' = 2x - 54/x^2 = 0 \Rightarrow x^3 = 27 \Rightarrow x = 3$, $f_{min} = 27$. The search interval contains this point.

Answer: final interval $[2.89,\ 3.47]$; $x^* \approx 3.2$ (true minimum $x=3$, $f=27$).

(a) Linear programming and geometric programming

Linear programming (LP) optimises a linear objective subject to linear constraints.

$$\text{Maximise } Z = c_1x_1 + c_2x_2 + \dots \quad \text{subject to } \sum a_{ij}x_j \le b_i,\ x_j \ge 0$$

• Graphical method for two variables: plot constraints, find the feasible region, and check the corner points. The optimum is always at a vertex.
• For many variables the simplex method is used.
• Design use: product mix, material cutting, allocation of machine hours.

Geometric programming (GP) handles objective and constraints written as posynomials (sums of positive terms with product of powers):

$$f(x) = \sum_k c_k\, x_1^{a_{k1}} x_2^{a_{k2}} \cdots x_n^{a_{kn}},\ c_k>0$$

Using the arithmetic-geometric mean inequality it gives the optimum cost from the dual problem, often before the design variables are known. The weights satisfy normality $\sum w_k = 1$ and orthogonality conditions. The number of degrees of difficulty is (number of terms) $-$ (variables) $-$ 1; zero means the solution is found by solving linear equations. Use: design of tanks, beams, gear trains where cost has power-law terms.

(b) Multivariable search methods

Methods for several variables without derivatives (or with them):

• Lattice (grid) search: evaluates a grid; simple but expensive.
• Univariate search: change one variable at a time to its best value, then the next, and repeat.
• Steepest descent (gradient): move along $-\nabla f$ with a step length found by line search.
• Pattern search (Hooke-Jeeves), Simplex (Nelder-Mead), Newton and conjugate gradient for faster convergence.

   x2
    |      . . .  contour of f
    |    .  *  .   * = optimum
    |  .  /  .     steps follow
    |   /___.      descent path
    +----------- x1

Multifactor objective functions

Real designs have several goals (weight, cost, life, safety). Methods to combine them:

• Weighted sum: $F = w_1 f_1 + w_2 f_2 + \dots$ with $\sum w_i = 1$ (after normalising the $f_i$).
• Constraint method: optimise the most important goal and convert the others to constraints.
• Pareto set: collection of designs where one objective cannot improve without worsening another; the designer chooses from it.