IE2110 Tutorial 10
Tutorial 10
2
Problem 10.1(a)
Problem Set 11.2A Q1, pg 628.
Q s H Company advertises on soap operas and football games. Each soap opera ad costs $50,000, and each
football game ad costs $100,000. Giving all figures in millions of viewers, if S soap opera ads are bought, they will
be seen by 𝟓 𝑺 men and 20 𝑺 women. If F football ads are bought, they will be seen by 17 𝑭 men and 7 𝑭
women. Q s H wants at least 40 million men and at least 60 million women to see its ads.
a) Formulate an NLP that will minimize Ǫ & H’s cost of reaching sufficient viewers.
b) Does the NLP violate the Proportionality and Additivity Assumptions?
c) Suppose that the number of women reached by F football ads and S soap opera ads is 𝟕 𝑭 + 𝟐𝟎 𝑺 −
𝟎. 𝟐 𝑭𝑺. Why might this be a more realistic representation of the number of women viewers seeing Ǫ & H’s
ads?
Let S: # soap opera ads bought; F: # football ads bought
min 𝒛 = 𝟓𝟎𝑺 + 𝟏𝟎𝟎𝑭
s.t. 5 𝑆 + 17 𝐹 ≥ 40 [Reach constraint: men]
20 𝑆 + 7 𝐹 ≥ 60 [Reach constraint: women]
𝑆, 𝐹 ≥ 0 [Variables non-negativity constraint]
3
Problem 10.1(b)
Problem Set 11.2A Q1, pg 628.
Q s H Company advertises on soap operas and football games. Each soap opera ad costs $50,000, and each
football game ad costs $100,000. Giving all figures in millions of viewers, if S soap opera ads are bought, they will
be seen by 𝟓 𝑺 men and 20 𝑺 women. If F football ads are bought, they will be seen by 17 𝑭 men and 7 𝑭
women. Q s H wants at least 40 million men and at least 60 million women to see its ads.
a) Formulate an NLP that will minimize Ǫ & H’s cost of reaching sufficient viewers.
b) Does the NLP violate the Proportionality and Additivity Assumptions?
c) Suppose that the number of women reached by F football ads and S soap opera ads is 𝟕 𝑭 + 𝟐𝟎 𝑺 −
𝟎. 𝟐 𝑭𝑺. Why might this be a more realistic representation of the number of women viewers seeing Ǫ & H’s
ads?
Since doubling S (or F) does not double the contribution of S (or F) to each constraint, we are
violating the proportionality assumption. Additivity is not violated.
Example: Suppose S is increased from 2 to 4 → 2 2 > 4 = 2
4
Problem 10.1(c)
Problem Set 11.2A Q1, pg 628.
Q s H Company advertises on soap operas and football games. Each soap opera ad costs $50,000, and each
football game ad costs $100,000. Giving all figures in millions of viewers, if S soap opera ads are bought, they will
be seen by 𝟓 𝑺 men and 20 𝑺 women. If F football ads are bought, they will be seen by 17 𝑭 men and 7 𝑭
women. Q s H wants at least 40 million men and at least 60 million women to see its ads.
a) Formulate an NLP that will minimize Ǫ & H’s cost of reaching sufficient viewers.
b) Does the NLP violate the Proportionality and Additivity Assumptions?
c) Suppose that the number of women reached by F football ads and S soap opera ads is 𝟕 𝑭 + 𝟐𝟎 𝑺 −
𝟎. 𝟐 𝑭𝑺. Why might this be a more realistic representation of the number of women viewers seeing Ǫ & H’s
ads?
This accounts for the fact that an extra soap opera ad yields a benefit which is a decreasing
function of the number of football ads. This accounts for the fact that we may not want to double
count people who see both types of ads.
5
Key Concept: Convexity Test
Using Second Derivative
• 𝑓′′(𝑥) ≥ 0 [convex] global C local minimum
• 𝑓 ′′ 𝑥 > 0 [strictly convex] local minimum
• 𝑓′′(𝑥) ≤ 0 [concave] global C local maximum
• 𝑓 ′′ 𝑥 < 0 [strictly concave] local maximum
Using Hessian Matrix 𝐻 𝑥 = ∇2𝑓(𝑥)
• H(x) +ve semidefinite [convex]
All principal minors are non-negative (≥ 0)
• H(x) +ve definite [strictly convex]
All leading principal minors are +ve (>0)
• H(x) –ve semidefinite [concave]
kth principal minor value =0 or sign of (-1)k
• H(x) –ve definite [strictly concave]
kth leading principal minor sign of (-1)k
Indefinite: some eigenvalues +ve, some –ve [saddle point] 14
Problem 10.2
Problem Set 11.3A QG, pg 636.
On the given set S, determine whether the function is convex, concave, or neither:
𝑓 𝑥1, 𝑥2, 𝑥3 = −𝑥2 − 𝑥 2 − 2𝑥2 + 0.5𝑥1𝑥2; 𝑆 = 𝑅3
1 2 3
Find all local maxima, local minima and saddle points for the function f.
Convexity Test: Using Hessian Matrix
𝛛2𝑓 𝛛2𝑓 𝛛2𝑓
𝛛 2 𝑥 21 𝛛𝑥 1 𝛛𝑥 2 𝛛𝑥 1 𝛛𝑥 3
𝛛2𝑓 𝛛2𝑓 𝛛2𝑓 1st principal minors of H are: -2, -2, -4; all of the sign (-1)1 = -1 <0
𝐻 𝑥1 , 𝑥2 , 𝑥3 = ∇2 𝑓 = 𝛛𝑥 2 𝛛𝑥 1 𝛛 2 𝑥22 𝛛𝑥 2 𝛛𝑥 3
𝛛2𝑓 𝛛2𝑓 𝛛2𝑓 2nd principal minors of H are: 3.75, 8, 8; all of the sign (-1)2 = 1 >0
𝛛𝑥 3 𝛛𝑥 1 𝛛𝑥 3 𝛛𝑥 2 𝛛 2 𝑥 23 −2 0.5 −2 0
det = 3.75 det =8
0.5 −2 0 −4
−2 0.5 0
= 0.5 −2 0 3rd principal minor of H = (-4)(-2)(-2) – (0.5)(0.5)(-4) = -15 < 0
0 0 −4 Therefore, H is negative semidefinite, and function f is
concave on 𝑅3. (sufficient to derive same conclusion looking at
the leading principal minors)
7
Problem 10.2
Problem Set 11.3A QG, pg 636.
On the given set S, determine whether the function is convex, concave, or neither:
𝑓 𝑥1, 𝑥2, 𝑥3 = −𝑥2 − 𝑥 2 − 2𝑥2 + 0.5𝑥1𝑥2; 𝑆 = 𝑅3
1 2 3
Find all local maxima, local minima and saddle points for the function f.
Convexity Test: Using Hessian Matrix
Setting the gradient of f to zero vector yields the following linear
system of equations:
𝛛2𝑓 𝛛2𝑓 𝛛2𝑓
𝛛 2 𝑥 21 𝛛𝑥 1 𝛛𝑥 2 𝛛𝑥 1 𝛛𝑥 3 −2𝑥1 + 0.5𝑥2 = 0
𝛛2𝑓 𝛛2𝑓 𝛛2𝑓 −2𝑥2 + 0.5𝑥1 = 0
𝐻 𝑥1 , 𝑥2 , 𝑥3 = ∇2 𝑓 = 𝛛 2 𝑥 22
𝛛𝑥 2 𝛛𝑥 1 𝛛𝑥 2 𝛛𝑥 3 −4𝑥 3 = 0
𝛛2𝑓 𝛛2𝑓 𝛛2𝑓
Solving the above simultaneous equations,
𝛛𝑥 3 𝛛𝑥 1 𝛛𝑥 3 𝛛𝑥 2 𝛛 2 𝑥 23
𝑥1 = 𝑥2 = 𝑥3 = 0
−2 0.5 0
= 0.5 Since f is a concave function (as shown previously), this point
−2 0
0 0 −4 𝑥1, 𝑥2, 𝑥3 = (0, 0, 0) is a local and global maximum.
8
Problem 10.3
Problem Set 11.6A Q1, pg 65G.
A company has n factories. Factory 𝒊 is located at point (𝒙𝒊, 𝒚𝒊), in the x–y plane. The company wants to locate a
warehouse at a point (𝒙, 𝒚) that minimizes:
𝑛
(distance from factory 𝒊 to warehouse)𝟐
𝑖=1
Where should the warehouse be located? f(x,y) is the sum of convex functions and is therefore
convex. To show that (x*, y*) is a local minimum we
We wish to minimize:
2𝑛 0
compute the Hessian 𝐻 = .
0 2𝑛
𝑦 ,𝑥 𝑓 =
σ𝑛𝑖 = 1 { (𝑥𝑖 − 𝑥)2 + (𝑦𝑖 − 𝑦)2} Thus, the two leading principal minors are:
Taking derivatives w.r.t. x and y: H1 = 2n > 0 and H2 = 4n2 > 0,
𝛛𝑓 Therefore, (x*, y*) is a local minimum.
𝑖=1 (𝑥 𝑖 − 𝑥) = 0 for 𝑥 = (𝑥 1 + 𝑥2 + ⋯ + 𝑥𝑛 )/𝑛
= −2 σ 𝑖=𝑛 ∗
𝛛𝑥
𝛛𝑓
The fact that f(x,y) is convex now shows that (x*, y*)
𝑖=1(𝑦 𝑖 − 𝑦) = 0 for 𝑦 = (𝑦 1 + 𝑦2 + ⋯ + 𝑦𝑛 )/𝑛
= −2 σ 𝑖=𝑛 ∗
𝛛𝑦 minimizes f(x,y) over all possible choices of (x, y), i.e., it
Warehouse ideally located at a minimum point (x*, y*) is a global minimum.
9