Computer Aided Engineering Design

OPTIMIZATION 359

The sufficiency condition may be written as

ΔXT[H]ΔX > 0 (12.28b)

orH is positive definite at the optimum, where H is the Hessian of the Lagrangian. Note that the
Hessian would comprise only equality and active constraints since the Lagrange multipliers for
inactive (and feasible) constraints will be zero.
For solving Eqs. (12.28) when the number of design variables and/or constraints at hand is large,
working solutions by hand is quite cumbersome and the numerical implementations are quite involved.
Of the many available methods for which the reader is suggested to refer to dedicated texts on
optimization, this chapter discusses three generic and often used methods, namely Linear Programming,
Sequential Linear Programming (SLP) and Sequential Quadratic Programming (SQP).

12.4 Linear Programming

Linear programming is employed when the function and constraints have linear dependence on the
design variables. The constraint equations can either be in the equality or inequality form. In standard
form, a linear programming problem can be stated as

Minimize: f(x 1 ,x 2 ,... , xn) = c 1 x 1 + c 2 x 2 +... + cnxn = cTX

Subject to:

a 11 x 1 + a 12 x 2 +... + a 1 nxn = b 1

a 21 x 1 + a 22 x 2 +... + a 2 nxn = b 2 ≡ aX=b

...

am 1 x 1 + am 2 x 2 +... + amnxn = bm

with x 1 ,x 2 ,... , xn all ≥ 0 or X≥ 0 (12.29)

Note that for a linear programming problem, the objective should be of the minimization type, the
constraints should be of the equality type and all decision (design) variables should be non-negative.
The maximization of a function is equivalent to the minimization of its negative and this change
should be incorporated accordingly. Constraints of the type

ap 1 x 1 + ap2x 2 +... + apnxn≤bp

can be modified to

ap 1 x 1 + ap 2 x 2 +... + apnxn + xn+1 = bp

while those of the type aq 1 x 1 + aq 2 x 2 +... + aqnxn≥bq

can be modified to ax a xqq 1212 + +... + ax xqnn – n+1 = bq

by introducing a non-negative slack(for≤ constraints) or surplus (for ≥ constraints) variable xn+1. For
m equality constraints in n variables, we would be interested in an underdetermined set (m < n) of
linear equations for if m = n, the solution, if existing, will be unique and there will not be any scope
for optimization. For m>n, the solution may not exist at all. Note that for the system aX = b with
the number of constraints less than the variables, there may exist many solutions. However, they may
or may not satisfy X≥ 0. All solutions satisfying aX=b and X≥ 0 are called feasible solutions and