UNIVERSITY OF MELBOURNE
SCHOOL OF MATHEMATICS AND STATISTICS
MAST30013 Techniques in Operations Research Semester 1, 2020
Assignment 2 Due: 4 pm, Thursday, 7 May
- Solution must be typeset in LaTex.
- Please submit your solution online by the due date.
- Show all necessary working.
1. Consider the function f : R4 ! R:
f(x) = x41 + x
4
2 + x
4
3 � x31x3 � 12x1x23 + x1x2x3 � 3x32 � 4x1x2 + x24 + 9x2 � 3x4 + 4.
You are required to do a computational study comparing the below three methods for finding
the local and global minima of f .
i Steepest descent method;
ii Newton’s method;
iii BFGS Quasi-Newton method.
(a) Compute the gradient and hessian of f .
(b) Create a set of instances which consists of 1000 randomly generated initial points for
the algorithms. Test the algorithms on the instance set and compare their average
performance in terms of solutions found and computational time. Use the following
parameters:
• tolerance ✏1 = 10�2 for the three methods,
• tolerance ✏2 = 10�5 for the Golden section search,
• step size T = 10,
• initial points with coordinate values range xi 2 (�10, 10), i = 1, 2, 3, 4.
i. You should report the average performance of your algorithms in tables.
f value Minimiser No. of times Ave iterations
per search
Ave time per
search (sec)
�2 (x1, x2, x3, x4) 6 7.8 0.2157
...
ii. Discuss, in words, the conclusion you have arrived at from your computational study.
You need to modify the given code (f.m, GRADF.m, HESS.m and script.m) from the
LMS in order to take function f as input. Only include a screenshot of the Matlab
script.m in your LaTex submission. Do NOT include the other Matlab code.
(c) Using the same set of instances and code as in part (b), test di↵erent parameter choices:
1 of 2
䨺
• T 2 {0.1, 100} and xi 2 (�10, 10), i = 1, 2, 3, 4;
• T = 10 and xi 2 (�1, 1), i = 1, 2, 3, 4.
Discuss, in words, the impacts of di↵erent choices.
2. Solve the equality-constrained nonlinear program:
min f(x) = 3x1x2 + 4x
2
2
s.t. h(x) = x21 + x
2
2 + x
2
3 � 1 = 0.
(a) Check the constraint qualifications at each stationary point.
(b) Use the second-order su�cient condition to determine the minimality of any stationary
point.
2 of 2