DT059A/MT034A Tillämpad Optimering

DT059A/MT034A Applied optimization

1. Introduction to optimization
Roger Olsson - IST
Introduction to DT059A/MT034A

• Seminars := lecture + discussion

• Labs := Individual work with online discussion and supervision

Mittuniversitetet 2
Course info – Optimization

• Seminars := lecture + • Provide knowledge about optimization and how it is used

discussion in practical applications in areas such as
• information technology (machine learning, robotics,
• Labs := Individual work with algorithms and complexity),
online discussion and • communication networks,
supervision • economics,
• signal processing, and
• information theory

• Applied
• Illustrated with practical examples and SW tools
along the way

Mittuniversitetet 3
Course info – Optimization

• After the course the student should be able

to
• formulate an optimization problem with constraints. • describe regularization methods for solving ill-
posed problems, and when they are applicable.

• apply the Karush-Kuhn-Tucker conditions for • apply and program optimization algorithms for
optimization with constraints. problem solving.

• explain different optimization algorithms for linear • evaluate the suitability of different optimization
and non-linear problems without and with algorithms for an optimization problem.
constraints, and when they are applicable.

• describe how non-convex optimization problems

can be reformulated into convex problems, and in
cases when non-convex optimization problems can
be reformulated to these.

Mittuniversitetet 4
Chapter 1

Design process for engineering systems

• A complex multidimensional process

• Relies on various assumptions and considerations

• Iteration is key

Mittuniversitetet 5
Chapter 1

Design process

Mittuniversitetet 6
Chapter 1

Conventional Design vs. Optimal Design

Mittuniversitetet 7
Chapter 1

Optimal Design vs. Optimal Control

Mittuniversitetet 8
Chapter 1

Terminology and notation

Summation and matrix multiplication

Vectors and points

Sets and constraints

𝒙
𝜃
𝒚
Derivatives
Norm/length of a vector Functions

Mittuniversitetet 9
Chapter 2

Formulate the optimization problem

Describe the problem

Collect data and information

Define design variables

Define optimization criteron

Formulate constraints

Mittuniversitetet 10
Chapter 2

Example – Can

Problem Data and information

Design a can according to the above figure, to hold at least 400 mL of liquid (1 mL = 1 cm3), as well as Provided in the problem description.
to meet other design requirements.
The can will be produced in the billions, so it is desirable to minimize the manufacturing costs. Since cost
can be directly related to the surface area of the sheet metal used, it is reasonable to minimize the
amount of sheet metal required.
Fabrication, handling, aesthetics, and shipping considerations impose the following restrictions on the
size of the can:
- the diameter should be no more than 8 cm and no less than 3.5 cm, whereas
- the height should be no more than 18 cm and no less than 8 cm.

Design variables Optimization Criterion Constraints

D = diameter of can [cm] The design objective is to minimize the total surface First constraint is the volume requirement:
H = height of can [cm] area S of the sheet metal for the three parts of the
cylindrical can: the surface area of the cylinder
(circumference × height) and the surface area of the
two ends. Therefore, the optimization criterion, or cost Second constraint is the size limitations:
function (the total area of sheet metal), is given as

Mittuniversitetet 11
Chapter 2

Example – Sawmill

Problem Data and information

A company owns two sawmills and two forests. The capacity of each mill, and the distance between the forests and
the mills, are summarized in the following:
Each forest can yield up to 200 logs/day for the duration of the project, and
the cost to transport the logs is estimated at $10/km/log.
At least 300 logs are needed daily.
The goal is to minimize the total daily cost of transporting the logs and meet
the constraints on the demand and the capacity of the mills.

Design variables Optimization Criterion Constraints

How many logs to ship The daily cost of transporting depends on the Mill capacity: Meaningful solution:
from Forrest i to Mill j: transportation cost and the transportation distance:
𝑥𝑖 ; 𝑖 = 1 𝑡𝑜 4

Forest yield:

Daily demand:

Mittuniversitetet 12
Chapter 2

Example – Carpentry #1

Problem Data and information

A cabinet is assembled from components C1, C2, and C3. All data for the problem are given in the project statement.
Each cabinet requires 8 C1, 5 C2, and 15 C3 components. The assembly of
C1 requires either 5 bolts or 5 rivets, whereas C2 requires 6 bolts or 6 rivets, The problem can be formulated in several different ways, depending
and C3 requires 3 bolts or 3 rivets. The cost of installing a bolt, including the on assumptions made and definitions of design [Link]
cost of the bolt itself, is $0.70 for C1, $1.00 for C2, and $0.60 for C3. Similarly, different fomulations will be presented.
riveting costs are $0.60 for C1, $0.80 for C2, and $1.00 for C3. Bolting and
riveting capacities per day are 6000 and 8000, respectively. To minimize the
cost for the 100 cabinets that must be assembled each day, we wish to
determine the number of components to be bolted and riveted.

Design variables Optimization Criterion Constraints

Minimize the total cost of cabinet fabrication: Fabrication:
C1
C2 C3
$b # $r #

𝐶𝑜𝑠𝑡 = 0.70 5 𝑥1 + 0.6 5 𝑥2 + 1.0 6 𝑥3 + 0.8 6 𝑥4 + 0.60 3 𝑥5 + 1.0 3 𝑥6

= 3.5𝑥1 + 3.0𝑥2 + 6𝑥3 + 4.8𝑥4 + 1.8𝑥5 + 3.0𝑥6

Capacity:

Meaningful solution:

Mittuniversitetet 13
Chapter 2

Example – Carpentry #2

Problem Data and information

A cabinet is assembled from components C1, C2, and C3. All data for the problem are given in the project statement.
Each cabinet requires 8 C1, 5 C2, and 15 C3 components. The assembly of
C1 requires either 5 bolts or 5 rivets, whereas C2 requires 6 bolts or 6 rivets, The problem can be formulated in several different ways, depending
and C3 requires 3 bolts or 3 rivets. The cost of installing a bolt, including the on assumptions made and definitions of design [Link]
cost of the bolt itself, is $0.70 for C1, $1.00 for C2, and $0.60 for C3. Similarly, different fomulations will be presented.
riveting costs are $0.60 for C1, $0.80 for C2, and $1.00 for C3. Bolting and
riveting capacities per day are 6000 and 8000, respectively. To minimize the
cost for the 100 cabinets that must be assembled each day, we wish to
determine the number of components to be bolted and riveted.

Design variables Optimization Criterion Constraints

Minimize the total cost of cabinet fabrication: Fabrication:
C1 C2 C3 C1 C2 C3

$b # $r #

𝐶𝑜𝑠𝑡 = 0.70𝑥1 + 1.0𝑥2 + 0.6𝑥3 + 0.6𝑥4 + 0.8𝑥5 + 1.0𝑥6

Capacity:

Meaningful solution:

Mittuniversitetet 14
Chapter 2

A generalized mathematical model

• ”One ring to rule them all…”

• All design problems can be transcribed into a standard form

Design variables

Optimization Criterion

Constraints

Constraints

• Also known as Nonlinear Programming Problem (NLP)

Mittuniversitetet 15
Chapter 2

Fitting the standard model

• What about maximization?

𝑓 𝒙 = −𝐹(𝒙)

Mittuniversitetet 16
Chapter 2

Fitting the standard model

• What about more-than-equal constraints?

𝑔𝑖 𝒙 = −𝐺𝑖 (𝒙)

Mittuniversitetet 17
Chapter 2

The Standard Model

• Function dependence • Unconstrained problems

• f(x), hj(x), and gi(x) must depend, explicitly or • Not all design problems have constraints
implicitly, on some of the design variables

• Number of equality constraints

• The number of independent equality constraints must
be less than, or at the most equal to, the number of
design variables (ie, p ≤ n).
• When p > n, we have an overdetermined system of
• Linear programming problems
equations. • If all of the functions f(x), hj(x), and gi(x) are linear in
design variables x, then the problem is called a linear
• When p = n, no optimization of the system is
programming problem
necessary because the roots of the equality
constraints are the only candidate points for
optimum design.

• Number of inequality constraints • Scaling of problem functions

• there is no restriction on the number of inequality • If the cost function is scaled by multiplying it with a
constraints. However, the total number of active positive constant, the optimum design does not
constraints (satisfied at equality) must, at the change
optimum, be less than or at the most equal to the
number of design variables.

Mittuniversitetet 18
Chapter 2

Feasible set

• A feasible set for the design problem is a collection of all feasible designs

• Geogebra example
• The feasible region usually shrinks when more constraints are added to the design model

Mittuniversitetet 19
Chapter 2

Active/inactive/violated constraints

• An inequality constraint gj(x) ≤ 0 is said to be active at a

design point x* if it is satisfied at equality (ie, gj(x*) = 0).
• All equality constraints are active for all feasible designs

x*
• An inequality constraint gj(x) ≤ 0 is said to be inactive at active x*
violated
a design point x* if it is strictly satisfied
(ie, gj(x*) < 0). x*
inactive

• An inequality constraint is said to be violated at a design

point x* if its value is positive
(ie, gj(x*) > 0).

Mittuniversitetet 20
Chapter 2

Discrete and integer design variables

• Problems where variables must have integer values

• Integer programming problems

• This impose additional constraints on the design problem

• Solving for a continous representation gives a lower

bound on the cost function

Mittuniversitetet 21