Notes on LP, GP and multivariable search

(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.