MATH30511 Optimisation
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH30511
Optimisation
I. Assessment Requirements
This coursework counts for 50% of your module mark. You can achieve a maximum of 60 marks. You should complete this work in CVX/CVXPY and write a report (either in LaTeX or Word) containing the main findings and brief comments/justification for every task. Your submission should be one document that includes both your report and CVX/CVXPY scripts. Submit the document to the module dropbox.
This coursework is an ‘element of assessment’ which means you need to pass it in order to pass the module. All work will be submitted to Turnitin as a means to check for plagiarism. Plagiarism will not be tolerated, students are reminded that this is an individual assignment.
II. Assessment Scenario/Problem
You have to carry out the following four equally-weighted tasks.
Task 1
Assume that you work in a computerised tomography (CT) laboratory and your task is to reconstruct images of human brain phantoms. However, the reconstructed images that you get from the scanner are corrupted with additive noise, and you are asked by your boss to come up with a strategy to de- corrupt them. You decide that you will address the problem using a smoothing regulariser.
(a) What is the price/unwelcome experience that will be undergone for achieving denoising?
(b) Suppose that the image that you want to reconstruct is the modified Shepp-Logan phantom of
the human brain with a spatial image resolution of 200x200. You can obtain this image, P, in the CVX/CVXPY environment by reading the “Modified_Shepp_Logan.mat” file that has been uploaded to NOW. Plot this image.
(c) Of course, you don’t know the exact image that you are trying to reconstruct but you have an approximate knowledge of how human brain phantoms looks like. Which regulariser would you choose for your denoising task? Justify your answer.
(d) Assume that the corrupted version of the image that you get from the scanner, Pn, is equivalent to the true image, P, after adding Gaussian noise with zero mean and standard deviation equal to 0.06. Create and illustrate this noisy version. This is the image that you will work with.
(e) If the reconstructed image pixel intensities Prec (i,j) (for i, j = 1, …, 200) need to be between 0 and
1 (0 ≤ Prec (i,j) ≤ 1), formulate the image reconstruction problem as a scalarised bi-criterion convex optimisation problem. Then, load it to CVX/CVXPY and solve it for three distinct levels of smoothing. Your chosen three levels should approximately correspond to “too much”, “about right”, and “not quite enough” smoothing. Provide the solutions to the three optimisation problems, that is, the illustrations of the reconstructed images. Hint: You may find it helpful to vectorise the image (using commands such as vec/reshape) before throwing it to the optimisation problem/routine so that you reconstruct a 1D signal instead. This approach is more convenient for calculations. Then, once you get the optimal 1D vector/output from the software, you can reshape back into 2D to get the reconstructed image.
(f) Plot the trade-off curve for this bi-criterion optimisation problem. In the plot show the Pareto
optimal point that you will eventually use.
(g) Provide all the CVX/CVXPY code used. (15 marks)
Task 2
One-Vs-All classification is a strategy that leverages binary algorithms for multi-class classification. It involves fitting one binary classifier per output class. For each classifier, the class is fitted against all the other classes. Finally, given a new input point, predictions are made by running all binary classifiers, and choosing the output class that corresponds to the prediction with the highest confidence.
Suppose you have been asked to build a model that best maps sepal and petal lengths to three types of roses, namely hybrid tea, grandiflora, and floribunda. That is to say, the explanatory variables comprise sepal length and petal length, whereas the output classes are the three types of roses. The dataset for this task can be found in the file “roses.mat”, and it contains 20 instances of each rose type, where the input features (sepal length and petal length, in that order) have been normalised.
Assume that you decided to deal with this task by using convex optimisation. In particular, you have chosen to employ the One-Vs-All strategy and the logistic model
p = prob(y = 1) = exp(aT u + b) / [1 + exp(aT u + b)]
where a e Rn and b e R are the model parameters, u e Rn contains the explanatory variables, and y equals 1 means that an individual rose from the population belongs to a certain type.
(a) Suppose the whole rose population in the dataset is to be used for fitting each binary classifier.
Provide the formulation of the convex optimisation problem that you will use for each binary classifier. Explain all notation used and why this problem is convex.
(b) Use CVX/CVXPY software to calculate the maximum likelihood estimates of the model
parameters a, b for each binary classifier, and present the results.
(c) Assume that you have been given a rose with normalised sepal and petal lengths (0,0)T . Use the model you built above to predict the class (rose type) to which it belongs.
(d) Provide all the CVX/CVXPY code used. (15 marks)
Task 3
(I) Let E1 and E2 be the following two ellipsoids:
(a) Provide the formulation of the convex optimisation problem for finding the minimum volume ellipsoid covering the union of E1 and E2 . State the optimisation variables of the problem and their respective sizes. Give all appropriate ellipsoid parameterisations that you will be using.
(b) Use CVX/CVXPY software to find the solution to the above problem. Give the solution (i.e., the minimum volume ellipsoid covering the union of E1 and E2 ) in parameterised form.
(c) Provide all the CVX/CVXPY code used.
(II) Assume that you have been asked to calculate the analytic centre of a set of 50 linear inequalities in R5, with one of the 50 linear inequalities being:
3x1 + 4x2 + 11x3 + 2x4 + x5 ≤ 50.
Suppose you have successfully addressed this assignment by minimising the logarithmic barrier function, and that you have found a unique solution. You are now asked to perform the same calculation on a set of 51 linear inequalities. These comprise the same 50 linear inequalities as in the previous problem, plus the following linear inequality:
3x1 + 4x2 + 11x3 + 2x4 + x5 ≤ 100.
Will the feasible set and the analytic centre remain the same or differ from the values for the first problem? Briefly justify your answer. (15 marks)
Task 4
Consider the unconstrained optimisation problem
minimise f (x) = − 1Tx + exp(1Tx),
where x = (x1,x2 ) e R2 is the optimisation variable.
(a) Use CVX or CVXPY software to solve the optimisation problem given above. Give the optimal
value p* .
(b) Assume that you now want to implement the gradient descent algorithm yourself for solving
the optimisation problem given above. Derive the gradient ∇f (x). Then, write code that implements the gradient descent algorithm with x(0) = (10,1). Use α = 0.01 and β = 0.5 as backtracking line search parameters, and the stopping criterion: ||∇f (x(k)) ||2 ≤ 10-3 .
The maximum number of iterations should be 500. After how many iterations did the algorithm converge?
(c) Is the sublevel set
S = {x | f (x) ≤ f (x(0) )}
closed? Justify your answer.
(d) Use your code to plot the suboptimality f (x(k))−p* (where p* is the optimal value obtained in part (a)) and the step size t(k), both of them as a function of the iteration number k.
(e) Provide all the CVX/CVXPY code used.
(f) Show that the direction p = (1,1)T is a descent direction at point x = (ln(1/2),0)T . (15 marks)
2023-04-22