1 Unconstrained Minimisation 50 marks
Consider the unconstrained minimisation problem
Xm
expaTi xbi 1 with variables x 2 Rn, where aT1 , . . . , aTm are the rows of A. The question
consists of the following.
a Derive the gradient rfx and Hessian Hfx of fx. 10 marks
b One inexact line search method that is very simple and quite eective is called backtracking line search. It depends on two parameters , , with 0 1, 0 0.5. The line search is called backtracking because it starts with relatively large step size 0 0 we will use 0 1 and then reduces it by the factor i.e. l l1 until the stopping condition
fxk ldk fxk lrfxkT dk
is satisfied, where xk is the current iterate and dk is the search direction. Implement backtracking line search in filesunconstrained.py. 10 marks
c Implement gradient descent in filesunconstrained.py to solve the problem 1, using a stopping criterion of the form krfxk2 where tolerance 0, and backtracking line search. Experiment on the small instance and plot objective value fxk versus iteration k. Report your results in answers.pdf. 10 marks
d Experiment with the backtracking parameters and to examine their influence on the convergence rate. For example, you can fix and vary or vice versa to see its eect on the number of iterations required to converge. Analyse your results in answers.pdf. 5 marks
e The Newton decrement
x rf xT Hf xrf x12 2
is a measure of the proximity of x to x, which plays an important role in the analysis of Newtons method. Implement Newtons method in
2
min fx x
i1
2
filesunconstrained.py to solve the problem 1, using a stopping criterion of the form 2×2 where tolerance 0, and back tracking line search. Experiment on the small instance and plot objec tive value fxk versus iteration k. Report your results inanswers.pdf. Note: numpy is useful to calculate the inverse of Hessian matrix. 10 marks
f The cost of Newtons method is dominated by the cost of evaluating the Hessian. Approximating Hessian might be useful to solve large prob lems. One common approximation method is to evaluate the Hessian only every N iterations; for the other steps, reuse the last Hessian eval uated. Experiment this method on the large instance and compare the number of iteration and required execution time. Analyse your results in answers.pdf. 5 marks
Waypoint Pathing 50 marks
The company you work for is designing an automated flight system for a surveillance drone. There are two parts of this system, an upperlevel prob lem that selects the set of waypoints to visit points of interest to survey, and a second lowerlevel problem that takes these waypoints as input and optimises the flight path. Youve been tasked with delivering this second part.
The flight path optimiser will take as input a set of weighted waypoints see figure 1 that the drone should visit at particular times, and optimises the flight path taking into account the drones dynamics acceleration and velocity as well as its limited fuel supply.
The flight path optimiser will be designed in a 2D environment, assuming that the drone operates at a fixed altitude. Time is discretised into T 2 N timesteps. After performing this discretisation, the dynamics are as follows for the position, velocity and acceleration of the drone pt, vt, at 2 R2:
pt pt1 vt vt vt1 at
3
200
150
100
50
0
Figure 1: Position of waypoints in our 2D setting. The velocity and acceleration are limited as so:
kvtk2 vmax katk2 amax
The drone fuel ft 2 0,1 decreases over time, depending on the drones velocity and acceleration:
ft ft1 fvkvtk2 fakatk2 where fv and fa are parameters for the fuel consumption.
The fileswaypoints.json file gives all the required data for the test in stance. Including the above parameters, this file also includes the initial position, velocity and fuel level of the drone p,v,f init.
The drone may not be able to exactly visit every waypoint in the allotted time and given the limited fuel supply, so you should treat visiting waypoints as soft constraints, by penalising deviation away from the waypoint position. To model this, each waypoint w 2 W has parameters for its position pw
4
0 50 100 150 200 x
y
pos, strength sw str and the set of times where the waypoint is active Gw times. The objective function then becomes:
X X s w k p t p w k 2 2 w2W t2Gw
a Take a convex relaxation of the fuel consumption constraint. Explain whether or not you expect this relaxation to be exact and why. 10 marks
b Formulate and solve the above problem as a convex optimisation prob lem in filesflightpath.py. Hint: you might want to rewrite con straints of the form kxk2 k as kxk2 k2 assuming k is positive. See madoptcheatsheet.py and the lecture examples for help with using the madopt library. 30 marks
c Check if the fuel limitations are binding at the optimal solution by reporting the appropriate dual variable value note that the dual vari able sign convention is dierent in madopt ipopt from pulp CBC. Increase the starting fuel until the fuel limits are no longer binding. Explain qualitatively how this changes the optimal solution change it back to the original value of 4000 prior to submission. 10 marks
5