Optimization Problem Formulation

4DM20 Engineering Optimization

Mauro Salazar and Dinesh Krishnamoorthy

Department of Mechanical Engineering

Eindhoven University of Technology

Academic year 2023–2024

1 / 53
Sources

Presentation based on material from:

• Papalambros & Wilde (2017): Principles of optimal design
• Nocedal & Wright (2006): Numerical optimization
• Haftka & Gürdal (1993): Elements of structural optimization

2 / 53
Optimization problem formulation

The mathematical problem formulation is the key to the

success of engineering optimization

3 / 53
Overview of Today’s Lecture
Learning Objectives: After this lecture you are expected to
1 understand how to frame optimization problems

2 formulate optimization problems in terms of objective,

constraints and variables
3 characterize optimization problems (feasibility, modality, ...)

4 characterize constraints (activity, redundancy, ...)

5 understand and recognize problem convexity and class

Readings: Chapter 1 from Principles of Optimal Design

Schedule:
• Design Optimization Example: Air Tank Design
• Mathematical Problem Formulation and Characteristics
• Introduction to Convex Optimization
• Conclusion
4 / 53
i

Example: airtank design

How to optimize an air tank design?

5 / 53
 i
“airtank˙temp” — 2006/6/15 — 10:54 — page 1 — #1

Example: airtank design

head h s = shell thickness

s r = inside radius
h = head thickness
shell l l = shell length
r

(Papalambros & Wilde, 2017)

6 / 53
Example: airtank design i

i
“airtank˙temp” — 2006/6/15 — 10:54 — page 1 — #1

Find : dimensions
Minimize : metal volume
Subject to : constraints on:
Total volume ( )
head h Head thickness ( )
Shell thickness ( )
s
Shell length ( & )
shell l
Outer radius ()
r

7 / 53
Example: airtank design i

i
“airtank˙temp” — 2006/6/15 — 10:54 — page 1 — #1

Find : x = [h, l, r , s]
Minimize : 2⇡(r + s)2 h + ⇡[(r + s)2 r 2 ]l
Subject to : ⇡r 2 l 2.12 · 107 cm3
h
r 0.13
s
head h r 0.01
10 cm  l  750 cm
s
r + s  150 cm
shell l
r
Physical relevance: x 2 X h, l, r , s > 0

8 / 53
Example: airtank design i

i
“airtank˙temp” — 2006/6/15 — 10:54 — page 1 — #1

Find : x = [h, l, r , s]
Minimize : f = 2⇡(r + s)2 h + ⇡[(r + s)2 r 2 ]l
⇡r 2 l
Subject to : g1 = 2.12·10 7 + 1  0
h
g2 = 0.13r +10
s
head h g3 = 0.01r +10
l
s g4 = 10 + 1  0
l
shell l g5 = 750 10
r +s
r g6 = 150 1  0
Physical relevance: x 2 X h, l, r , s > 0

9 / 53
Design optimization

Design optimization is the selection of the best design with

the available means

(Papalambros & Wilde, 2017)

10 / 53
Optimization

1 select optimization variables

2 select objective criterion in terms of optimization variables
(to minimize or maximize)
3 determine constraints in terms of optimization variables
which must be satisfied
4 determine optimization variable values which minimize
(maximize) the objective while satisfying all constraints

11 / 53
Mathematical problem formulation

Minimize f (x) x = vector of optimization variables

x
subject to hj (x) = 0 j = 1, . . . , mh
gk (x)  0 k = 1, . . . , mg
x 2 X ✓ Rn

12 / 53
Negative null form

Minimize f (x) x = (column) vector of design variables

x
subject to h(x) = 0 h = [h1 , h2 , . . . , hmh ]T
g(x)  0 g = [g1 , g2 , . . . , gmg ]T
x 2 X ✓ Rn

Other formulations:
• positive null form (g(x) 0)
• negative unity form (g(x)  1)
• positive unity form (g(x) 1)

13 / 53
Formulation examples
Optimization variables x:
• sizing (dimensions)
• shape (geometry of boundary)
• decisions (routes, propulsive power)

Objective function f (x):

• profit (income, efficiency, ...)
• cost (lap time, weight, ...)

Constraint functions hj (x) and gk (x):

• geometrical (width, length, height, ...)
• structural (stresses, displacements, ...)
• dynamical (accelerations, eigenfrequency, ...)
• physical (temperatures, pressures, ...)

14 / 53
 Example: airtank design 1-D
i i

i
“airtank˙temp” — 2006/6/15 — 10:54 — page 1 — #1

Find : x = [H, L, R, s]
Minimize : f = 2⇡(R + s)2 H + ⇡[(R + s)2 R 2 ]L
⇡R 2 L
Subject to : g1 = 2.12·10 7 + 1  0
H
head h g2 = 0.13R + 1  0
s
s
g3 = 0.01R +10
L
shell l g4 = 10 + 1  0
L
r g5 = 750 10
R+s
g6 = 150 10
Physical relevance: x 2 X H, L, R, s > 0

15 / 53
Example: airtank design 1-D

x ,s (shell thickness as design variable)

R, H, L constant parameters

min 2⇡(R + x)2 H + ⇡[(R + x)2 R 2 ]L

x
x
s.t. g3 = 0.01R +10
R+x
g6 = 150 10
X :x >0

16 / 53
 i
Example: airtank design 1-D
i
“plot1Da˙temp”
“plot1Da˙temp” —
— 2006/6/15
2006/6/26 —
— 16:36
16:21 —
— page
page 11 —
—

f(x)

17 / 53
Example: airtank design 1-D
f(x)

g6(x)
g
0

g3(x)

x
18 / 53
Example: airtank design 1-D
f(x)

g6(x)
g
0

g3(x)

infeasible feasible x

19 / 53
Example: airtank design 1-D
f(x)

f g6 = 0

g3 = 0

g6(x)
g
0

g3(x)

x
20 / 53
Example: airtank design 1-D
f(x)

f g6 = 0

g3 = 0

g6(x)
g
0

g3(x)

x
21 / 53
 i
Example: airtank design 1-D
i
“plot1Df˙temp” — 2006/6/26 — 16:21 — page 1 —

f(x)

f g6 = 0

g3 = 0

22 / 53
 i

Constrained versus unconstrained optimum

f f(x) f g1 = 0 g2 = 0
f(x)

g=0

x x
• constrained optimum • unconstrained optimum
• bounded optimum • interior optimum

23 / 53
 “multi˙temp” — 2006/6/15 — 17:12 — page 1 — #1
Multiple local minima: multi-modality

f(x)
f(x)
f f
local global global

local

x x

24 / 53
Example: airtank design 2-D

x 1 , r , x2 , l (2 design variables)
S, H constant parameters

min 2⇡(x1 + S)2 H + ⇡[(x1 + S)2 x12 ]x2

x
⇡x12 x2
s.t. g1 = 2.12·107 + 1  0
H
g2 = 0.13x 1
+10
S
g3 = 0.01x1 + 1  0
x2
g4 = 10 +10
x2
g5 = 750 1  0
g6 = x150
1 +S
10
X : x1 , x2 > 0

25 / 53
 “plot2Da˙temp” — 2006/6/15 — 21:15 — page 1 — #1
Example: airtank design 2-D

9 10
8
6 7 g1 = 0

f g1 < 0
x2 x2
feasible

x1 x1
objective function constraint g1

26 / 53
Example: airtank design 2-D

x2

g1

x1

27 / 53
Example: airtank design 2-D

g2 g3 g6

x2
g5

g4
g1

x1

28 / 53
Example: airtank design 2-D

g2 g3 g6

x2
g5
F feasible
domain
g4
g1

x1

29 / 53
Example: airtank design 2-D

optimum
g2 g3 g6

x2
g5
F

g4
g1

x1

30 / 53
Terminology

optimum
g2 g3 g6 Terminology
• feasibility
x2 • redundancy
g5
• domination
F
• well-boundedness
• uniqueness
g4
• active constraints
g1
• convexity
x1

31 / 53
Constraint activity theorem

A constraint gj (x)  0 being active at the optimum implies that

1 if gj (x)  0 is left out, the location of the optimum changes

2 the constraint is satisfied with strict equality: gj (x) = 0

32 / 53
Constrained optimum - 2D examples

f
f F
x2 F x2

g
P2 P2
P1 x1 P1 x1

well-constrained over P1 ⇥ P2 well-constrained over P1 ⇥ P2

33 / 53
Constrained optimum - 2D examples

f f

x2 F x2 F

P2 P2
P1 x1 P1 x1

well-constrained over P1 ⇥ P2 Is it well-constrained?

not well-constrained (w.r.t. x2 )

34 / 53
 i
“unc˙overv2D1˙temp” — 2007/4/4 —“unc˙overv2D2˙temp”
17:56 — page 1 —
Overview well-bounded problems

2-D examples

f f

x2 x2

x1 x1

unconstrained cases (interior optima)

35 / 53
 i
“con˙overv2D1˙temp” — 2007/4/4 — 17:56“con˙overv2D2˙temp”
— page 1 — #1 — 20
Overview well-constrained problems

2-D examples

f
x2 x2

x1 x1
The number of active The number of active
constraints is less than the constraints equals the
number of variables. number of variables.

constrained cases (boundary optima)

36 / 53
Normalization
Why is it important?
1 Speeds up convergence considerably
2 Sometimes even enables the solution of the problem
Consider example of min f (x) = x > Qx with Q = Q > ⌫ 0.
Gradient descent: xk+1 = xk s · rf (xk ).
2
Optimal s = max + min leads to convergence rate
⇣ ⌘k
kxk x ? k  max min
max + min
· kx0 x ? k.
Suppose problem not normalized, then could have max min
1
(matrix ill-conditioned) and difficult convergence. For instance,
with RTOL= 10 6 and ratio equal to 1010 , you would converge in
7 · 1014 steps!
Instead, for ratio equal to 4, converge in 27 steps.

How to do it?
1 Normalize variables xn = x/x̄, so their magnitude is around 1
2 Normalize constraints and objective to have factors around 1
37 / 53More in the exercises.
Problem properties: smoothness

Function f (x) : Rn ! R is

@f
— differentiable if all @xi exist
@f
— continuously differentiable if all @xi continuous
@2f
— twice differentiable if all @xi @xj exist
@2f
— twice continuously differentiable if all @xi @xj continuous

Smoothness assumption ⌘ twice continuously differentiable

Needed for convergence proofs for Newton-based algorithms

38 / 53
 i
Non-smoothness Reformulation - Max
i
“max˙temp” — 2006/6/25

• Discontinuities? ! Try to reformulate

• Example: max-operator in objective

f(x)
Non-smooth problem:
f

min max(0, x)
x2R
x

Reformulated: x-z<0

min z z
(x,z)2R2
s.t. x z 0
z 0 z>0 x

39 / 53
 i
Non-smoothness reformulation - abs
i
“abs˙temp” — 2006/6/25 —

• Discontinuities? ! Try to reformulate

• Example: absolute value operator in objective

f(x)
Non-smooth problem:
f

min |x|
x2R
x

Reformulated: -x-z<0 x-z<0

z
min z
(x,z)2R2
s.t. x z 0
x z 0 x

40 / 53
 i
Non-smoothness reformulation - min
i
“max˙con˙temp” — 2006/6/2

• Discontinuities? ! Try to reformulate

• Example: min operator in constraint

-min(x1,x2)+1
Non-smooth problem: f
x2
min x 1 + x2
(x1 ,x2 )2R2
s.t. min(x1 , x2 ) + 1  0 x1
-x1+1
Reformulated: f
x2
min x1 + x2
(x1 ,x2 )2R2 -x2+1
s.t. x1 + 1  0
x2 + 1  0 x1

41 / 53
Problem Properties: Convexity
convex function convex feasible domain

f x2
F

x x1

If
1 The objective function is a convex function over F
2 The feasible domain is convex (= h affine and g convex
then
1 The problem only has global minima
2 which can be computed in polynomial time
42 / 53
Convexity

The two-times differentiable function f (x) is (strictly) convex on

the domain X , if its Hessian matrix H is positive semi-definite
(definite) for all x 2 X .

2 @2f @2f @2f

3
@x12 @x1 @x2
··· @x1 @xn
6 @2f @2f @2f 7
6 @x22
··· 7
H ,6
6
@x2 @x1
.. ...
@x2 @xn
..
7
7
4 . . 5
@2f @2f @2f
@xn @x1 @xn @x2
··· @xn2

43 / 53
Convexity

A symmetric matrix being positive semi-definite (definite) is

equivalent to:

1 all its eigenvalues are non-negative (positive)

2 all determinants of its leading principal minors are

non-negative (positive)

44 / 53
Quiz

Which one of the following statements is TRUE:

A) A unimodal objective function is convex.
B) A non-convex objective function is multi-modal.
C) An optimization problem consisting of a multi-modal objective
function is not convex.
D) Convex optimization problems have a unique global minimizer.

More on convexity next week...

45 / 53
Formulation Concepts

Optimization variables:
• single-variable or multi-variable

Objective function:
• minimization or maximization
• single-objective or multi-objective

Constraints:
• unconstrained or constrained
• equality or inequality

46 / 53
Formulation Concepts

Optimization variables:
• Domain: {0, 1}, N, N⇤ , Z, R, R+

Objective and constraint functions:

• Linearity: linear or nonlinear
• Continuity: none/once/twice-differentiable
• Convexity: convex/non-convex

These properties are important because they define the problem

type, for which there may be tailored solution algorithms.
E.g., linprog for Linear Programs (LPs)!

47 / 53
 i

Formulation classes:
i
linear program “LP˙temp” — 2006

Linear program (LP):

• Affine objective function
• Affine constraint functions
g3
• Continuous design variables f

Example: x2 g2

min f (x) = 2x1 x2

x2R2
s.t. g1 (x) = x1 + 2x2 8  0
F g1
g2 (x) = 2x1 2x2 3  0
g3 (x) = 2x1 + 1  0 g4
g4 (x) = 2x2 + 1  0
x1
(Some) optimization variables discrete:
• (Mixed-)integer linear program: (M)ILP

48 / 53
Formulation classes:
i
quadratic program “QP˙temp” — 2006

Quadratic program (QP):

• Quadratic objective function
• Affine constraint functions
• Continuous design variables g3
f
Example: x2
min f (x) = 3x12 2x1 + 5x22 + 30x2
x2R2
s.t. g1 (x) = 2x1 3x2 + 8  0 F
g2 (x) = 3x1 + 2x2 15  0 g2
g3 (x) = x2 5  0 g1
x1
(Some) optimization variables discrete:
• (Mixed-)integer quadratic program: (M)IQP

49 / 53
Formulation classes: non-linear least squares
i
Non-linear least squares (NLSQ) problem:
i
“NLLS˙temp” — 200
• Non-linear objective function with special structure
• No constraint functions
• Continuous design variables

1 P
m
f (x) = 2 rj2 (x)
j=1
y
Example:

(x, t) = x1 + tx2 + e x3 t
P
m
f (x) = 12 [yj (x, tj )]2
j=1
t1 t2 t3 t4 t5 t

50 / 53
 i

Formulation classes: nonlinear program

i
“NLP˙temp” — 200

Nonlinear program (NLP):

• Non-linear objective function
• Non-linear constraint functions
g2
• Continuous design variables
f
x2 F
Example:
p g1
min2 f (x) = 3x1 + 3x2
x2R p
s.t. g1 (x) = 18 6 3
x1 + x2 30
g3
g2 (x) = 5.73 x1  0
g3 (x) = 7.17 x2  0
x1
(Some) optimization variables discrete:
• (Mixed-)integer nonlinear program (M)INLP

51 / 53
 i
“airtank˙temp” — 2006/6/15 — 10:54 — page 1 — #1

Example: airtank design

• Four optimization variables

• Six constraints
• NLP problem
head h
s • How to solve it?
shell l • Where is the minimizer located?
r • Which constraints are active?

What did you learn?

52 / 53
Conclusion
Take-home Messages:
• Optimization problems consist of variables, objective and
constraints
• The mathematical formulation is crucial (more next week)
• Normalizing variables and functions can improve/enable
numerical convergence
• Convex problem () Convex objective and constraint set
=) It has only global minima, which can be efficiently found
• There are different classes of problems; each class has
dedicated efficient solution algorithms
For next week:
• Do Computer Assignments 0 and 1
• Read 2.1-2, 3.1-2 and 4.1-4 from Convex Optimization by
Boyd & Vandenberghe
53 / 53