[SOLVED] 1 Unconstrained Minimisation 50 marks

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 01, 00.5. The line search is called backtracking because it starts with relatively large step size 00 we will use 01 and then reduces it by the factori.e. ll1 until the stopping condition
fxkldkfxklrfxkT 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 parametersandto examine their influence on the convergence rate. For example, you can fixand varyor 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
xrf 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 22 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:
ptpt1vt vtvt1at
3

200
150
100
50
0
Figure 1: Position of waypoints in our 2D setting. The velocity and acceleration are limited as so:
kvtk2vmax katk2amax
The drone fuel ft 2 0,1 decreases over time, depending on the drones velocity and acceleration:
ftft1fvkvtk2fakatk2 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 tp 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 kxk2k as kxk2k2 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 madoptipopt from pulpCBC. 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