6CCE3EAL Coursework 2 Deadline: 16:00, Thursday 15th December 2022
Coursework 2: Optimization
6CCE3EAL Engineering Algorithms
This coursework will count for 30% of your total grade in the course.
Remember that all work you submit should be your own work. Although you can e.g. discuss
your approach to the problem at hand with others, this coursework is not meant to be a team
exercise. The College treats plagiarism very seriously.
You should submit your report by 16:00, Thursday 15th December 2022 using the submis-
sion link on the KEATS site for 6CCE3EAL.
If you have more general or administrative problems please use the online forum or consult during
drop-in-sessions or support sessions. If an email is required, please include the course number
(6CCE3EAL) in the subject line.
Overview
The success of optimization techniques depends on the complexity and nature of the objective function
and feasible region. This coursework focuses on a classic therapy problem and on two notoriously
difficult objective functions, and investigates the most “appropriate” way of identifying their optima.
! This coursework has a number of components that you must complete. You should ensure thatyou allow enough time to complete them before the deadline!
Question 1
1. Complete the Optimization Onramp tutorial.
2. Upload your certificate.
3. Upload the MATLAB code of the therapy project.
Question 2
1. Write a MATLAB function that implements a line search algorithm using the secant method.
The arguments to this function are the name of the m-file for the gradient, the current point,
and the search direction. For example, the function may be called linesearch_secant and be used
by the function call alpha=linesearch_secant(‘grad’ ,x,d), where grad.m is the m-file containing
the gradient, x is the starting line search point, d is the search direction, and alpha is the value
returned by the function [which we use in the following parts of the question as the step size for
iterative algorithms].
Use the stopping criterion |dT?f(x+αd)| < |dT?f(x)|, where α > 0 is a pre-specified number,
f is the gradient, x is the starting line search point, and d is the search direction. Use a value
of = 10?4 and initial conditions of 0 and 0.001.
2. Write a simple MATLAB program for implementing the method of steepest descent.
Test your code to find the minimizer of
f(x1, x2, x3) = (x1 ? 4)4 + (x2 ? 3)2 + 4(x3 + 5)4.
1
6CCE3EAL Coursework 2 Deadline: 16:00, Thursday 15th December 2022
Use the initial point x = [4, 2,?1]T .
3. Write a simple MATLAB program for implementing the steepest descent algorithm using the
secant method for the line search of Question 1. For the stopping criterion, use the condition
‖?f(xk)‖ < , where = 10?6.
Test your program using an initial condition of [?4, 5, 1]T , determine the number of iterations
required to satisfy the stopping criterion, and evaluate the objective function at the final point
to see how close it is to 0.
Compare the output with the output from question 2.
4. Apply your program for the steepest descent algorithm to Rosenbrock’s function:
f(x) = 100(x2 ? x21)2 + (1? x1)2,
where x = (x1, x2)T . Use an initial condition of x0 = [ˉ2, 2]T . Terminate the algorithm when the
norm of the gradient of f is less than 10?4.
Question 3
1. Write MATLAB programs to implement naive random search and simulated annealing. Use the
neighborhood
N(x(k)) = {x : x(k)i ? α ≤ xi ≤ x(k)i + α},
where α > 0 is pre-specified, and pick z(k) to be uniformly distributed on N(x(k)).
2. Test both algorithms on maximizing the MATLAB "peaks" function,
defined over the set {?3 ≤ x ≤ 3,?3 ≤ y ≤ 3}.
3. Comment on the effect of varying α.
4. Plot f(x, y) over its feasible set.
5. Using the MATLAB function fminunc to find the minimum of f(x, y).
Tasks
Complete the Optimization Onramp tutorial and upload your certificate.
Download the MATLAB archive which contains a template for the functions that you should
complete.
! Do not adjust the function signature, i.e. the function inputs and outputs. These aredesigned to be precisely what you need for your coursework!
Submit a short report that outlines your routines, results, and lessons learnt. This should ideally
be in the form of a MATLAB .mtx live script, as we have been using in the labs.
Ensure your report is no more than 4 pages in length including all references and citations with
appropriate font size and margins.
2
6CCE3EAL Coursework 2 Deadline: 16:00, Thursday 15th December 2022
Debugging tips
This coursework involves many different bits of code.
Deliberately I have split this into many functions. That is because this is easier to test!
Ensure you use MATLAB to help debug your programs: you can set breakpoints by clicking on
the line numbers, which will allow you to stop the program and observe values of variables.
Also ensure you make use of MATLAB’s routines.
Marking scheme
Your submission will be assessed on the following criteria:
Uploading the Onramp optimization certificate and solving the therapy project. [10%]
Fully working implementation of code of Question 2. [25%]
Fully working implementation of code of Question 3. [25%]
Report that highlights main findings. [25%]
Discretionary marks for good programming technique (in terms of efficiency, presentation of code,
and structure) and appropriate use of commenting. [15%]
You should attempt all of the above routines; incomplete solutions will be given partial credit. Note
that these routines will all be marked independently, and you can still receive full credit for complete
solutions even if the preceding parts are not fully implemented.
! ‘Fully working’ in the above is left deliberately vague. You should try to consider the differentinputs that your functions may receive and act accordingly.
Submission
You should submit your report via the online submission point on KEATS by the assignment deadline:
16:00, Thursday 15th December 2022.