MASSACHUSETTS INSTITUTE OF TECHNOLOGY
Department of Civil and Environmental Engineering
1.731 Water Resource Systems
Lecture 3, General Optimization Concepts 1, Sept. 14, 2006
Problem Formulation:
Maximize F ( x1 , x 2 ,..., x n )
x1 ,x 2 ,...,x n
such that :
g i ( x1 , x 2 ,..., x n ) = 0 i = 1,..., r Strict equality constraints
g i ( x1 , x 2 ,..., x n ) ≤ 0 i = r + 1,..., m Inequality constraints
Basic components:
• n decision variables x → xi = [ x1 , x 2 ,..., x n ] , collectively define a decision strategy.
• Scalar objective function F ( x ) → F ( x1 , x 2 ,..., x n ) measures performance of decision
strategy
• r equality constraints gi(x), i=1,…, r
• n-r inequality constraints gi(x), i= r + 1,…,m
Note:
• Minimization of F(x) is maximization of –F(x)
• g(x) > 0 is same as –g(x) < 0
Feasible region F : Set of x that satisfies constraints (depends only on gi(x)).
Discrete optimization: F consists of a finite number of feasible solutions
x2
A F F
F consists of 7 discrete x1 and x2 values,
B F F F indicated by circles
C F F
A B C x1
g1(x) = -1 for (x1, x2) = {AA, AB, AC, BA, BB, CB, CC}
g1(x) = +1 otherwise
1
Continuous (non-discrete) optimization: F consists of an infinite number of feasible solutions
x2
g2(x) = 0
F is bounded by curves corresponding
g1(x) = 0
F to gi(x) = 0.
Interior of F is set of points that satisfy
g2(x) ≤ 0
g1(x) ≤ 0 gi(x) < 0.
g3(x) ≤ 0
g3(x) = 0
x1
Solving Optimization Problems
Objective in optimization is to find the best decision strategy among all feasible possibilities:
→ We seek a global optimum
Most common way to find optimum for large problems is to use an iterative search:
Pick Yes Evaluate
Evaluate Yes
Pickinitial
initial Feasible
Feasibl Stop
solution objective
objective Sto
solutio ?
?
Start functio
function Exit
No No
Try Move
Move to ato a
again ?
again better feasible
better feasible
Yes solutio
solution
No
An iterative search algorithm needs:
• A method for selecting an initial feasible solution - Can be formulated as a secondary
optimization problem
• A stopping criterion that detects following:
1. No feasible solution – no way to satisfy all constraints
2. Optimal solution found – satisfies optimality conditions
3. Objective function unbounded over feasible region - Objective can be infinite
within feasible region.
2
• A solution improvement mechanism – challenging for nonlinear problems, often based
on optimality conditions, sometimes ad hoc.
Types of search procedures:
• Exhaustive Searches - For discrete problems:
Move methodically through all (or sometimes a subset) of the feasible solutions to
determine which has best objective value.
• Selective Searches – For continuous problems:
Use information from current and past candidate solutions (e.g. objective value or
objective gradient) to determine next feasible solution.
For now, focus on continuous problems and selective searches.
Global vs. Local Maxima for Continuous Problems
In practice, it is much easier to find local optima:
x* is a local maximum if F(x*) ≥ F(x) for all feasible x near x*
x* is a local minimum if F(x*) ≤ F(x) for all feasible x near x*
Two key questions:
1. When is a local optimum also global optimum?
2. How do we know when a particular candidate solution x* is a local optimum?
What can we say about global optimality based on local properties (near x*) ?
F(x)
Global max
dF(x)/dx=0
Local max
dF(x)/dx ≠ 0
Inflection pt
Global optima cannot be
identified from local properties !
Except in certain special cases
Nonunique local min
Global min
x
Feasible Region