Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATHEMATICS AND STATISTICS
MATH5165
ASSIGNMENT
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.