THE UNIVERSITY OF NEW SOUTH WALES, SYDNEY
SCHOOL OF MATHEMATICS AND STATISTICS
MATH3161/MATH5165 — OPTIMIZATION – Term 1, 2021
Problem Sheet 1 – Model Formulation
1. Sydney Sounds Manufacturing produces speakers for hi-fi sets in two types, product
A and product B. Two types of processes are needed for their production. The first
process combines all machining operations, and the second consists of all assembly
operations. Each unit of product A requires 4 labor-hours of machining and 2 labor-
hours of assembly work, whereas each unit of product B requires 3 labor-hours of
machining and 0.5 labor-hours of assembly work. Manufacturing capacity available
during the coming production week is 2400 labor-hours, and the assembly work capacity
available for the same week is 750 labor-hours.
Previous sales experience indicates that product B sells at least as much as product A
and that there is already an order of 100 units for product A to be produced during the
next period. Furthermore, all products produced during the week can be sold during the
same week. Products A and B provide 7.00 and 5.00 profit per unit sold, respectively.
Management would like to know what quantities of A and B should be manufactured
during the next production week in order to maximize the total profit. The following
table summarizes the data.
Operation Product A Product B Capacity
Machining (labor-hours) 4 3 2400
Assembly (labor-hours) 2 0.5 750
Profit per unit ( ) 7 5
(a) Formulate this problem as a mathematical optimization problem.
(b) Sketch the feasible region, and find the vertices of the feasible region.
(c) *MATLAB: Use the MATLAB function linprog to find a solution.
Hint: In MATLAB type doc linprog.
2. The environmental Protection Agency (EPA) wants to restrict the amount of pollutants
added by a company to the river water. The concentrations of phenol and nitrogen in
the water are to be restricted to, respectively, P and N grams/ML (1ML = 1 mega-litre
= 106 litres) on a daily basis. The river has a flow of M ML/day. The company diverts
a portion of the river water, adds the pollutants, namely, phenol and nitrogen, to it,
and sends the water back to the river. The company has four possible ways to treat the
water it uses before returning it to the river. The characteristics of each treatment are
given in the following table.
Treatment 1 2 3 4
Phenol p1 p2 p3 p4
Nitrogen N1 N2 N3 N4
Cost/ML C1 C2 C3 C4
Table 1: Grams of pollutant/ML after treatment
Assuming that
the river is initially free of pollutants;
1
addition of pollutants does not a↵ect the amount of water flow;
the company has to process at least k ML/day of river water.
(a) Set up an optimization problem to solve for the amount of water to be processed
by each treatment so that total cost of treatment is minimized.
(b) How does the formulation change if EPA regulations apply not to total river con-
centration downstream from the plant, but rather to the concentration of e✏uent
from the plant?
3. An oil company has oil wells drilled at points A = (1, 1), B = (1, 1) and C = (0,3)
on a grid layout of a particular location. The scale of the grid is such that one grid unit
corresponds to one kilometre. The company must build pipelines from these wells to a
distribution depot. The cost of the pipelines from wells A and B is 1000/meter, but
only 500/meter from well C because of a lower flow rate from the well. For political
reasons the depot must lie on the same side of a state border as the town located at
the grid point (5,4). The state border is a straight line which passes through the
grid points (4,10) and (4, 6). There is also a circular lake 3 kilometres in diameter
centered at the grid point (2,1). Obviously the depot cannot be located in the lake.
Where should the depot be constructed so as to minimize the cost of building the
connecting pipelines?
Pose this as a mathematical optimization problem, and say as much as you can about
its structure.
4. * A Simplified Portfolio Selection Problem. A portfolio manager in charge of a
bank portfolio has 10 million to invest. The securities available for purchase, as well
as their respective quality ratings, maturities, and yields, are shown in the following
Table.
Bond Bond Quality scales Years to Yield to After-tax
name type maturity maturity yield
Moody’s Bank’s
A Municipal Aa 2 9 4.3% 4.3%
B Agency Aa 2 15 5.4% 2.7%
C Government Aaa 1 4 5.0% 2.5%
D Government Aaa 1 3 4.4% 2.2%
E Municipal Ba 5 2 4.5% 4.5%
The bank places the following policy limitations on the portfolio manager’s actions:
Government and agency bonds must total at least 4 million.
The average quality of the portfolio cannot exceed 1.4 on the bank’s quality scale.
(Note that a low number on this scale means a high-quality bond.)
The average years to maturity of the portfolio must not exceed 5 years.
Assuming that the objective of the portfolio manager is to maximize after-tax earnings
and that the tax rate is 50 percent, formulate the problem as a mathematical optimiza-
tion problem.
(You can also assume that all securities are purchased at par (face value) and held to
maturity and that the income on municipal bonds is tax-exempt.)
2
-
THE UNIVERSITY OF NEW SOUTH WALES, SYDNEY
SCHOOL OF MATHEMATICS AND STATISTICS
MATH3161/MATH5165 — OPTIMIZATION – Term 1, 2021
Problem Sheet 2 – Mathematical background
1. Calculate the gradient and Hessian for each of the following functions.
(a) f(x) = 3x1 4x2 + 2x3 7
(b) f(x) = x21 x22 + 3x1x2
(c) f(x) = 100(x2 x21)2 + (1 x1)2 (Rosenbrock’s function)
(d) f(x) = (x a)T (x a) r2 for constant a 2 Rn and r 2 R
2. Determine whether the following matrices are positive definite, positive semi-definite,
negative definite, negative semi-definite or indefinite.
(a)

8 12
12 18

(b)
4 1
1 2

(c)

6 2
9 3

(d)
24 2 0 50 3 0
5 0 14
35 (e)
242 2 02 3 0
0 0 2
35 (f)
242 3 03 3 0
0 0 1
35
3. (a) Prove that a square matrix G is positive definite if and only if G+GT is positive
definite.
(b) Prove that an n ⇥ n symmetric matrix G is positive definite if and only if G1 is
positive definite.
(c) Let G be a square matrix of order n and A be a matrix of order m⇥n. Prove that
the n+m by n+m square matrix
H =

G AT
A 0

is positive semi-definite if and only if G is positive semi-definite.
4. Let A be an n by n nonsingular matrix and let G = ATA.
(a) Prove that G is symmetric and positive definite.
(b) Prove that f(x) = (xTGx)
1
2 is a norm.
5*. Let G be an n⇥n symmetric matrix with a factorization G = LDLT , where L is a unit
lower triangular matrix and D is a diagonal matrix. Show that G is positive definite if
and only if Dii > 0, for i = 1, 2, . . . , n.
1
THE UNIVERSITY OF NEW SOUTH WALES, SYDNEY
SCHOOL OF MATHEMATICS AND STATISTICS
MATH3161/MATH5165 — OPTIMIZATION – Term 1, 2020
Problem Sheet 3 – Convex sets and functions
1. Establish rigorously whether the following sets are convex or not.
(a) ⌦ =

x 2 R2 | 2x1 x2 6

.
(b) ⌦ =

x 2 R2 | x21 x2 6

.
(c) ⌦ =

x 2 R2 | x21 x2 = 6

.
(d) ⌦ =

x 2 R2 | x21 x2  6

.
2. Prove the following sets are convex using the definition of a convex set.
(a) ⌦ =

x 2 Rn | aTx b = 0 , where b 2 R and a 2 Rn.
(b) ⌦ =

x 2 Rn | aTx b 0 , where b 2 R and a 2 Rn.
(c) ⌦ = {x 2 Rn | x = Ac, c 2 C }, where C ✓ Rn is a convex set and A is an n ⇥ n
matrix.
(d) ⌦ = { (x, r) 2 Rn ⇥ R | kAx bk  r }, where A is an m⇥ n matrix and b 2 Rm
and k · k is a norm on Rm.
3. (a) Determine whether the following functions are convex, concave or neither on the
given regions.
i. f(x) = (3x1 2)2 + 4(x2 + 4)2 on R2.
ii. f(x) = 8x21 + 2x
2
2 9x1x2 on R2.
iii. f(x) = (x22 2x2 + 1)ex21 on ⌦ =
n
x 2 R2 | 1p
2
 x1  1p2
o
.
(b) Find a convex set ⌦ in R2 on which the function f(x1, x2) = e(x21+x22) is convex.
4. (a) Let ⌦ ✓ Rn be a convex set. Show that a function f is convex on ⌦ if and only if
the set
epi(f) := { (x,↵) 2 Rn ⇥ R | x 2 ⌦, ↵ f(x) } ,
called the epigraph of the function f , is a convex subset of Rn ⇥ R.
(b) Let f1 and f2 be convex functions on a convex set ⌦.
i. Prove that if ↵1 0 and ↵2 0 then the function f = ↵1f1+↵2f2 is a convex
function on ⌦.
ii. Give an example of a convex set ⌦, convex functions f1, f2 and scalars ↵1 and
↵2 such that f = ↵1f1 + ↵2f2 is not convex.
iii. Prove that f(x) = max { f1(x), f2(x) } is convex on ⌦.
1
5*. (a) Let f be a convex function on Rn. Let x(1),x(2), . . . ,x(n) be points in Rn and
↵1,↵2, . . . ,↵n nonnegative numbers satisfying
nP
i=1
↵i = 1. Show that
f(↵1x
(1) + · · ·+ ↵nx(n))  ↵1f(x(1)) + · · ·+ ↵nf(x(n)).
(b) Use part (4a) to derive the famous arithmetic-geometric mean inequality
↵1a1 + ↵2a2 + · · ·+ ↵nan a↵11 a↵22 · · · a↵nn ,
where ai’s are given positive numbers and the ↵i are arbitrary nonnegative weights
satisfying
nP
i=1
↵i = 1.
6*. Let ⌦ ✓ Rn be a convex set, and let f(x) be a real valued convex function defined on
⌦. Let g() be a nondecreasing convex function defined on a real interval J where
the range of f(x) is contained in J. Prove that h(x) = g(f(x)) is convex. Use this to
show the following:
(a) If f(x) is a positive concave function defined on ⌦, then 1f(x) is convex.
(b) If f(x) is a convex function defined on ⌦ then ef(x) is convex.
2

































































































































































































































学霸联盟