Below mentioned methods can be used to solve and optimization
problem with constraints.
Graphical optimization method
It is the simplest and rather
convenient method to solve an optimization problem involving one or two design
variables. If the optimization problem is a function of single design variable,
then optimum solution can be acquired by plotting the objective function and
finding maxima or minima. As for optimization problems involving two design
variables, firstly feasible region is identified by plotting constraint functions.
Then contours (contour represents the curve comprised of points with same value
for objective function) of objective function are drawn and optimum value is
found by visual assessment.
Optimality criteria method
Optimality criteria are the
condition an objective function must satisfy at its minimum point. Only minimum
for an objective function can be found by using optimality criteria i.e. it
cannot be used to find maximum of objective function. To find maximum of
function, first minimize it and then multiply it by -1 for maximization.
For unconstrained problems
The first order optimality
condition for local minimum of an unconstrained optimality problem f(x) with
single design variable around optimum point is given as
?f () = 0
Where ?f () is the gradient of function f(x).
Points that satisfy this condition are called stationary points.
This condition is necessary but not
sufficient to find minimum as it tells that function value in proximity of is not increasing.
Sufficient condition for minimum
of f(x) is given as
Where represents hessian matrix.
If hessian matrix is positive definite,
stationary point is local maximum.
If hessian matrix is negative definite,
stationary point is local minimum.
If hessian matrix is indefinite, stationary
point is inflexion point.
If hessian matrix is semi-definite, sufficient
conditions are inconclusive.
For constrained problems
function combines the constraints (equality/inequality) and objective function.
The function is formulated such that the necessary conditions for its minimum
are same as that for constrained problem.
the function definition, all the inequality constraints if any are converted to
equality constraints such that
+ = 0
Where represent the inequality constraint and is known as slack variable. It is squared to
avoid addition of negative number to inequality constraint.
Therefore the Lagrangian function is written
L (x, u, v,
s) = f(x) + (x) + +(x)
x is vector of design variables
u ? 0 is
vector of Lagrangian multipliers for inequality constraints
vector of Lagrangian multipliers for equality constraints
vector of slack variables
As above mentioned function is unconstrained, necessary
conditions for its minimum are
conditions are first order necessary conditions for the minimization of
objective function having constraints on design variables.
Gradient conditions for
optimality of constrained minimization problem is given as
f + + = 0
Here and , i=1,…,p are the
Lagrange multipliers associated with constraints 0 (inequality
constraints) and = 0 (equality
set of conditions i.e. are called complementary slackness. It shows
that either or. If
the slack variable that is is zero then the subsequent constraint is
active with a positive Lagrange multiplier . If
the Lagrange multiplier is zero, then the corresponding constraint is
inactive. This shows that first set of condition involve only active inequality
For a point to be minimum of a function subjected to equality constraints and inequality
constraints, below mentioned conditions are necessary.
should be a regular point
Gradient condition f() + + = 0 must be satisfied
Constraints should be satisfied at optimum.
Switching conditions must be met.
variables must satisfy feasibility conditions i.e.
multipliers should always have positive sign
An optimization problem which has
linear cost/objective function and linear constraint equations is called linear
programming problem. The constraint equations can either be of equality,
inequality or both. But most of the real life optimization problems are of
non-linear type. These problems can be transformed in the linear type problems
by converting them in succession of linear programs. Non-linear problems can
also be converted to linear programming problems by linearizing the objective
function about a known point.
Standard for of linear
programming (L.P) problem can be stated as
Where is mxn matrix consisting of constraints
Is a vector of design variables.
Is a vector comprising of objective function
Vector consisting of
R.H.S of constraint equations.
It can be seen that the
standard for of LP problems is of minimization, i.e. goal is to minimize
objective / cost function. Also all the constraints are linear having R.H.S
positive. Furthermore all the design variables are limited to non-negative.
Conversion to standard LP form
To transform a given optimization
problem to the stand LP form, following steps should be taken
If objective function/cost function is of
maximization, convert it into minimization type by multiplying it by -1.
Standard LP form entails that there must be
positive constant on right hand side of constraints. It there is a negative
constant, multiply it by negative sign.
For less than type constraints, slack variable
is added to convert the constraint to equality. Polarity of slack variable
should be kept positive.
To convert greater than type constraints to
equality, positive surplus variable is added.
In case of unrestricted variables, they are
written in term of the difference between two new variables. If the difference
if positive, the original variable is positive and vice versa.
If a constant is present in objective function
either it can simply be ignored during solving problem as objective function is
not affected by a constant. After obtaining solution, optimum value is altered
to account for constant. Or a duplicate design variable is multiplied by
constant and corresponding constraint to design variable is set with value 1.
Linear programming problems are
convex problems. When LP problems are in their standard form, they stand for n no. of constraint equations and m no.
of optimization variables.
Following cases may arise
If m=n, solution can be obtained without
consideration of objective function with only solving constraint equations.
If m>n, this represents the case that some
constraints are linearly dependent on other constraints.