TMA947 / MMG621 – Nonlinear optimization Lecture 1

TMA947 / MMG621 — Nonlinear optimization

Lecture 1 — Introduction to optimization

Emil Gustavsson, Zuzana Nedělková

October 20, 2017

What is optimization?

Optimization is a mathematical discipline which is concerned with finding the minima or

maxima of functions, possibly subject to constraints.

Basic notation
• Vectors are written with bold face, i.e., x ∈ Rn .

• Elements in a vector are written as xj , j = 1, . . . , n.

• All vectors are column vectors.

Pn
• The inner product of a and b is written as aT b = bT a = a j bj .
j=1
√ qP
n
• The norm || · || denotes the Euclidean norm, i.e., ||x|| = xT x = 2
j=1 xj .

• We utilize vector inequalities, a ≤ b, meaning that aj ≤ bj , j = 1, . . . , n.

Optimization problem formulation

In order to introduce a general optimization problem, we need to define the following:

x ∈ Rn : vector of decision variables xj , j = 1, . . . , n,

f : Rn → R ∪ ±∞ : objective function,
X ⊆ Rn : ground set,
gi : Rn → R : constraint function defining restriction on x,
gi ≥ 0, i ∈ I : inequality constraints,
gi = 0, i ∈ E : equality constraints.

1
TMA947 / MMG621 – Nonlinear optimization Lecture 1

A general optimization problem is to

minimize f (x), (1a)

x
subject to gi (x) ≤ 0, i ∈ I, (1b)
gi (x) = 0, i ∈ E, (1c)
x ∈ X. (1d)

(If we consider a maximization problem, we change the sign of f to get a minimization problem.)

Classification of optimization problems

Linear Programming (LP):

f (x) = cT x = n
P
- Linear objective function j=1 cj xj ,
- Affine constraint functions gi (x) = ai T x − bi , i ∈ I ∪ E
- Ground set X defined by affine equalities/inequalities.

Nonlinear programming (NLP):

- Some functions f, gi , i ∈ I ∪ E are nonlinear.

Unconstrained optimization:
- I ∪ E = ∅,
- X = Rn .

Constrained optimization:
- I ∪ E 6= ∅, and/or
- X ⊂ Rn .

Integer programming (IP):

- X ⊆ Zn or X ⊆ {0, 1}n .

Convex programming (CP):

- f, gi , i ∈ I are convex functions,
- gi , i ∈ E are affine,
- X is closed and convex.

2
TMA947 / MMG621 – Nonlinear optimization Lecture 1

Conventions

Let S = {x ∈ Rn | gi (x) ≤ 0, i ∈ I, gi (x) = 0, i ∈ E, x ∈ X} denote a feasible set.

What do we mean by solving the problem to minimize f (x) ?

x∈S

Let
f ∗ := infimum f (x)
x∈S

denote the infimum value of f over the set S. If the value f ∗ is attained at some point x∗ in S, we can write

f ∗ := minimum f (x),
x∈S

and have f (x∗ ) = f ∗ . Another well-defined operator defines the set of minimal solutions to the problem

S ∗ := arg minimum f (x),

x∈S

where S ⊆ S is nonempty if and only if the infimum value f ∗ is attained at some point x∗ in S.
∗

Now we can define what we mean by the problem to minimize f (x).

x∈S

"to minimize f (x)" means "find f ∗ and an x∗ ∈ S ∗ "

x∈S

If we have an optimization problem

P : minimize f (x)
x∈S

• A point x is feasible in problem P if x ∈ S. The point is infeasible in problem P if x ∈

/ S.
• The problem P is feasible if there exist a x ∈ S and the problem P is infeasible if S = ∅.
• A point x∗ is an optimal solution to P if x∗ ∈ arg minimum f (x).
x∈S

• f ∗ is an optimal value to P if f ∗ = minimum f (x).

x∈S

Examples

I. Consider the problem to

minimize (x + 1)2 ,
subject to x ∈ R,

Easy problem, (x + 1)2 is convex, no constraints. Just solve f ′ (x) = 0, and get the optimal solution x∗ = −1
and the optimal value f ∗ = 0.

(Convex, quadratic, unconstrained optimization problem)

3
TMA947 / MMG621 – Nonlinear optimization Lecture 1

II. A more complicated problem is to

minimize (x + 1)2 ,
subject to x ≥ 0.

Now the "f ′ (x) = 0" trick does not work and we need to consider the boundary. We get the optimal solution
x∗ = 0 and the optimal value f ∗ = 1.

(Convex, quadratic, constrained optimization problem)

III. Consider the problem to

minimize − x1 ,
subject to x1 + x2 ≤ 1,
x1 , x2 ≥ 0.

We solve this graphically. So optimal solution is x∗ = (1, 0)T and the optimal value if f ∗ = −1.

x2
1 −∇f = (1, 0)T

x1 + x2 = 1

x∗ = (1, 0)T
x1
0 1

The diet problem

As a first example of an real optimization problem, we consider the diet problem (first formulated by George
Stigler).

For a moderately active person, how much of each of a number of foods should be eaten on a daily basis
so that the person’s intake of nutrients will be at least equal to the recommended dietary allowances
(RDAs), with the cost of the diet being minimal?

Good example to show

• how to model a real optimization problem,

• why a realistic model sometimes can be difficult to achieve.

We consider the case when the only allowed foods can be found at McDonalds.

For a moderately active person, how much of each of a number of McDonald foods (see Table 1) should
be eaten on a daily basis so that the person’s intake of nutrients will be at least equal to the recom-
mended dietary allowances (RDAs), with the cost of the diet being minimal?

4
TMA947 / MMG621 – Nonlinear optimization Lecture 1

Food Calories Carb Protein Vit A Vit C Calc Iron Cost

Big Mac 550 kcal 46g 25g 6% 2% 25% 25% 30kr
Cheeseburger 300 kcal 33g 15g 6% 2% 20% 15% 10kr
McChicken 360 kcal 40g 14g 0% 2% 10% 15% 35kr
McNuggets 280 kcal 18g 13g 0% 2% 2% 4% 40kr
Caesar Sallad 350 kcal 24g 23g 160% 35% 20% 10% 50kr
French Fries 380 kcal 48g 4g 0% 15% 2% 6% 20kr
Apple Pie 250 kcal 32g 2g 4% 25% 2% 6% 10kr
Coca-Cola 210 kcal 58g 0g 0% 0% 0% 0% 15kr
Milk 100 kcal 12g 8g 10% 4% 30% 8% 15kr
Orange Juice 150 kcal 30g 2g 0% 140% 2% 0% 15kr
RDA 2000 kcal 350g 55g 100% 100% 100% 100%

Table 1: Given data for the diet problem

We define the sets

Foods := {Big Mac, Cheeseburger, McChicken, McNuggets, Caesar Sallad

French Fried, Apple Pie, Coca-Cola, Milk, Orange Juice},
Nutrients := {Calories, Carb, Protein, Vit A, Vit C, Calc, Iron.}

Then we define the parameters

aij = Amount of nutrient i in food j, i ∈ Nutrients, j ∈ Foods,

bi = Recommended daily amount (RDA) of nutrient i, i ∈ Nutrients,
cj = Cost for food j, j ∈ Foods,

and the decision variables

xj = Amount of food j we should eat each day, j ∈ Foods.

The model of the diet optimization problem is then to

X
minimize c j xj , (2a)
j∈Foods
X
subject to aij xj ≥ bi , i ∈ Nutrients, (2b)
j∈Foods

xj ≥ 0, j ∈ Foods. (2c)

(2a) We minimize the total cost, such that

(2b) we get enough of each nutrient, and such that
(2c) we don’t sell anything to McDonalds.

5
TMA947 / MMG621 – Nonlinear optimization Lecture 1

The optimal solution is then

   
xBig Mac 0
xCheeseburger  7.48
   
 xMcChicken   0 
   
 xMcNuggets   0 
   
 xCaesar Sallad  0.27
x=

=
  .
 xFrench Fries   0 

 xApple Pie  3.03
   
 xCoca Cola   0 
   
 xMilk   0 
xOrange Juice 0
Total cost = 118.47 kr.
Total intake of calories = 3093.51 kcal.

If we add the constraint that xj should be integer, the solution is

   
xBig Mac 0
xCheeseburger  7
   
 xMcChicken  0
   
 xMcNuggets  0
   
 xCaesar Sallad  1
x=   =  .
 xFrench Fries  0
  
 xApple Pie  3
   
 xCoca Cola  0
   
 xMilk  0
xOrange Juice 0

Total cost = 150 kr.

Total intake of calories = 3200 kcal.

Now consider going on a diet, meaning that we would like to eat as few calories as possible. We reformulate
our model to

X
minimize aCalories,j xj , (3a)
j∈Foods
X
subject to aij xj ≥ bi , i ∈ Nutrients \ {Calories}, (3b)
j∈Foods

xj ≥ 0, j ∈ Foods. (3c)

The optimal solution is then

   
xBig Mac 0
xCheeseburger   0 
   
 xMcChicken   0 
   
 xMcNuggets   0 
   
 xCaesar Sallad   0 
x= =
 xFrench Fries   0  .

   
 xApple Pie   0 
   
 xCoca Cola   3.96 
   
 xMilk  12.41
xOrange Juice 0.36

6
TMA947 / MMG621 – Nonlinear optimization Lecture 1

Total cost = 251.01 kr.

Total intake of calories = 2127.47 kcal.

If we add the constraint that xj should be integer, the solution is

   
xBig Mac 0
xCheeseburger   0 
   
 xMcChicken   0 
   
 xMcNuggets   0 
   
 xCaesar Sallad   0 
x=  xFrench Fries  =  0  .
  
   
 xApple Pie   0 
   
 xCoca Cola   1 
   
 xMilk  11
xOrange Juice 6

Total cost = 270 kr.

Total intake of calories = 2210 kcal.

The real diet problem

When first studied by the Stigler, the problem concerned the US military and had 77 different foods in the
model. He didn’t managed to solve the problem to optimality, but almost. The near optimal diet was

• Wheat flour
• Evaporated milk
• Cabbage
• Spinach
• Dried navy beans

at a cost of $0.1 a day in 1939 US dollars.

7
TMA947 / MMG621 – Nonlinear optimization Lecture 1

Course material

Lecture 1 Define and model optimization problems, classification

Lecture 2 Convexity of sets, functions, optimization problems
Lecture 3 Optimality conditions, introduction
Lecture 4 Unconstrained optimization, methods, classification.
Lecture 5 Optimality conditions, continued
Lecture 6 The Karush-Kuhn-Tucker conditions
Lecture 7 Lagrangian duality
Lecture 8 Linear programming, introduction
Lecture 9 Linear programming, continued
Lecture 10 Duality in linear programming
Lecture 11 Convex optimization
Lecture 12 Integer programming
Lecture 13 Nonlinear optimization methods, convex feasible sets
Lecture 14 Nonlinear optimization methods, general sets
Lecture 15 Overview of the course