THE UNIVERSITY OF NEW SOUTH WALES
SCHOOL OF MATHEMATICS AND STATISTICS
MATH5165 OPTIMIZATION Term 1, 2022
ASSIGNMENT
Your answers to this assignment must be submitted via Moodle before 5:00pm, April 22,
2022. Late assignments will not be accepted except on documented medical or compassionate grounds.
Assignments must include a signed cover sheet available from the School of Mathematics and Statistics
web site at:
http://www.maths.unsw.edu.au/sites/default/files/assignment.pdf
School date stamp is not needed on the cover sheet.
Marking of this Assignment
Each question on this assignment is worth 25 marks. A full mark of 100 on this assignment
is worth 5% of the total marks for MATH5165. Present your work (especially for questions
3 and 4) as a self contained, well-written report including the problem statement, solu-
tion summary, clear interpretation of solutions, model formulation, definition of problem
variables and your computer output. State clearly the assumptions that you make. Any
Matlab files that you modify/write should be included as an appendix.
1. Consider the optimization problem
(P1) min
x∈Rn
x1
s.t. ‖x− x0‖22 ≤
1
n(n− 1) ,
eTx = 1,
where n ≥ 2, x = (x1, x2, . . . , xn)T ∈ Rn, x0 = ( 1n , . . . , 1n)T ∈ Rn and e = (1, 1, . . . , 1)T ∈ Rn.
(i) Show that the problem (P1) is a convex optimization problem.
(ii) Using the Karush-Kuhn-Tucker optimality conditions, find the global minimizer of (P1).
2. Consider the following non-convex quadratic minimization problem
(P2) min
x∈Rn
xTAx + 2bTx + c
s.t. ‖x‖22 − r ≤ 0,
where A is a symmetric (n×n) constant matrix, b is a constant n× 1 vector, c is a scalar, ‖x‖2 =
√
xTx
and r > 0 is a scalar. You are given that x∗ ∈ Rn, λ∗ ∈ R and the following conditions hold:
(A+ λ∗I)x∗ + b = 0, ‖x∗‖22 − r ≤ 0, λ∗(‖x∗‖22 − r) = 0, (A+ λ∗I) 0, λ∗ ≥ 0,
where I is the (n× n) identity matrix and (A+ λ∗I) 0 means that the matrix (A+ λ∗I) is a positive
semi-definite matrix. Note that the matrix A is not assumed to be positive semi-definite. Prove that x∗
is a global minimizer of (P2).
Hint: Show first that the Lagrangian function L(x, λ∗) of (P2) is a convex function on Rn.
1
3. Minimum Cost Pizza Problem. Using only the items given in the tables below, formulate an
optimization problem in standard form to create a minimum cost pizza which satisfies both the nutritional
requirements of Table 1 and bounds on item quantities given in Table 2. Use the nutritional data of Table
3 and the cost data of Table 4 in your model.
Use the MATLAB linear optimization routines linprog to solve the problem. Interpret your results.
Table 1
Nutrient Requirement Units
Calcium 750.0 mg
Iron 12.0 mg
Protein 48.5 gram
Vitamin A 4500.0 IU
Thiamine 1.3 mg
Niacin 16.0 mg
Riboflavin 1.6 mg
Vitamin C 30.0 mg
Table 2
UPPER AND LOWER BOUNDS ON PIZZA ITEMS
Item Upper Bounds* Lower Bound*
Sauce 1.986 1.140
dough 5.249 4.266
cheese 2.270 1.703
pepperoni 0.983 N/A
ham 1.135 N/A
bacon 0.993 N/A
g.pepper 1.561 N/A
onion 0.993 N/A
celery 1.561 N/A
mushroom 1.135 N/A
tomato 1.703 N/A
pineapple 1.703 N/A
meat N/A 0.993
veg. N/A 0.993
fungi N/A 0.922
* Amount in hundreds of grams.
2
Table 3
NUTRITIONAL DECOMPOSITION OF PIZZA ITEMS*
Item Calc Iron Prot Vit A Thia Niac Ribo Vit C
cheese 517.700 .222 20.000 3000.000 .022 6.000 .244 -
Sauce 14.000 1.800 2.000 800.000 0.100 1.400 .060 6.000
dough 18.233 3.826 14.224 - .586 8.852 .628 -
pepperoni 10.000 2.500 15.000 - - 2.000 - -
ham 9.031 2.291 14.692 - .740 4.009 0.178 -
bacon 13.000 1.189 8.392 - .361 1.828 .114 -
g.pepper 9.459 .675 1.351 209.460 .081 .540 .081 127.030
onion 27.273 .545 1.818 18.182 .363 .545 .036 10.000
celery 40.000 .250 - 125.000 .025 .500 .025 10.000
mushroom 6.000 .800 3.000 - .100 4.300 .460 3.000
tomato 13.333 .533 1.333 450.000 .066 .800 .04 22.667
pineapple 12.016 .310 .387 25.194 .081 .193 .019 6.977
* Units as in Table 1
Table 4
COSTS OF PIZZA ITEMS
Item Cost in cents/100 grams
cheese 139.80
sauce 105.72
dough 28.89
pepperoni 132.33
ham 132.15
bacon 132.81
green pepper 75.30
onion 15.99
celery 42.42
mushrooms 93.60
tomatoes 66.09
pineapple 77.94
3
4. Portfolio Selection Problem. An individual with $100,000 to invest has identified three mutual
funds as attractive opportunities. Over the last five years, dividend payments (in cents per dollar invested)
have been as shown in Table 5, and the individual assumes that these payments are indicative of what can
be expected in the future. This particular individual has two requirements: (1) the combined expected
yearly return from his/her investments must be no less than $8,000 (the amount $100,000 would earn
at 8 percent interest) and (2) the variance in future, yearly, dividend payments should be as small as
possible. How much should this individual fully invest his/her $100,000 in each fund to achieve these
requirements?
Table 5
Years
1 2 3 4 5
Investment 1 10 4 12 13 6
Investment 2 6 9 6 5 9
Investment 3 17 1 11 19 2
[Hint: Let xi(i = 1, 2, 3) designate the amount of funds to be allocated to investment i, and let xik denote
the return per dollar invested from investment i during the kth time period in the past (k = 1, 2, . . . , 5).
If the past history of payments is indicative of future performance, the expected return per dollar from
investment i is
Ei =
1
5
5∑
k=1
xik.
The variance in future payments can be expressed as
f(x1, x2, x3) =
3∑
i=1
3∑
j=1
σ2ijxixj = x
TCx,
where the covariances σ2ij are given by
σ2ij =
1
5
5∑
k=1
xikxjk − 1
52
(
5∑
k=1
xik
)(
5∑
k=1
xjk
)
. ]
(a) Using the following table, calculate the covariance matrix C = [σ2ij ].
Table 6
k x1k x2k x3k x
2
1k x
2
2k x
2
3k x1kx2 x1kx3 x2kx3
k k k
1 10 6 17 100 36 289 60 170 102
2 4 9 1 16 81 1 36 4 9
3 12 6 11 144 36 121 72 132 66
4 13 5 19 169 25 361 65 247 95
5 6 9 2 36 81 4 54 12 18
total 45 35 50 465 259 776 287 565 290
(b) Set up a standard form optimization problem (i.e. quadratic optimization problem) that will deter-
mine the best investment mix.
(c) Solve the problem using the MATLAB quadratic programming routine quadprog. Interpret your
results.
4
NOTES: Essential information for accessing files from the MATH3161/MATH5165 Course Web page
and for using Matlab.
ˆ Matlab can be accessed from your own laptop using the myAccess service. (see the link on the
Course Web-page, UNSW Moodle, Computing facilities (labs, virtual apps, software).
ˆ Matlab M-files can be obtained from Matlab Worksheets in Class Resources at the Course Web-
page, UNSW Moodle. The Matlab files for Q1, Problem Sheet-1 (ss22.m) and for Q5, Problem
Sheet-6 (qp22.m) are available at this page in the assignment folder.
ˆ Matlab is run by typing
matlab
at the UNIX prompt. Inside Matlab use ‘help command’ to get help,
e.g.
help optim
help linprog
help quadprog
ˆ To run a Matlab .m file from within Matlab simply type the name of the file:
ss22
This assumes the file ss22.m is in the current directory (use the UNIX command ‘ls’ to see what
files you have; if it is not there get a copy of the file from Matlab worksheets page at the Course
Web page and save it as ss22.m).
ˆ An entire Matlab session, or a part of one, can be recorded in a user-editable file, by means of the
diary command. The recording is terminated by the command diary off. A copy of the output
produced by Matlab can be stored in the file ‘ss22.out’ by typing diary ss22.out For example
diary ss22.txt
ss22
diary off
will save a copy of all output in the file ss22.txt
ˆ The file ss22.out may be viewed using ‘more’ or any text editor (xedit, vi) or printed using the ‘lpr’
command.
5