20/3/2023 14:30MAST90045 Assignment 1
第1/8⻚file:///Users/bonnie/Downloads/asmt1_q.html
MAST90045 Assignment 1
Due on 29 March 2023
Question 1 (50 pts)
In this question, you are asked to implement a reverse accumulation method to compute
the gradient of one of the test functions found in the notes:
1-1 (3 pts)
To forwardly evaluate at based on the computational graph, from and
, you need to sequentially compute a value at each one of 10 vertices s as well as
vertex . DeNne the functions to compute values at the vertices, one function for each
vertex. The functions are named such that fv# for vertex and fy for vertex . The
arguments for each function should be one or two of x1 , x2 , v1 ,…, v10 .
( , ) = sin( − ) cos(2 − ).f2 x1 x2 x
2
1
2
x22
4 x1 e
x2
f x = ( , )x1 x2 x1
x2 v
y
v# y
20/3/2023 14:30MAST90045 Assignment 1
第2/8⻚file:///Users/bonnie/Downloads/asmt1_q.html
1-2 (3 pts)
Using all the component forward functions above, deNne f.ad that returns both y and
v , a length-10 vector for . Note that f.ad takes a length-2 vector x
for .
1-3 (5 pts)
To carry out the reverse accumulation, from , you need to sequentially compute each
one of 14 component partial derivatives. DeNne the functions to compute them, one
function for each edge. The functions are named such that d for and the numerator
followed by the denominator, e.g., dv1dx1 for . Following the mathematical
deNnition of partial derivatives, the arguments for each function must be the same as the
arguments for the corresponding forward function deNned above. For example, dv5dv4
must have the same arguments for fv5 .
1-4 (10 pts)
Finally, implement using all the component partial derivatives above as ad that
returns a gradient vector c(dydx1, dydx2) . As a reverse accumulation method, ad
takes not only x but also v .
1-5 (14 pts)
Many algorithms make use of gradients, and existing software packages for those
algorithms often implicitly compute gradients if we do not explicitly supply them. In most
cases, partial derivatives are computed using Nnite-difference approximation. That is, for
a small ,
v = ( ,… , )v1 v10
x = ( , )x1 x2
y
∂
∂v1
∂x1
∇f (x)
Δh
( , )∂f∂x1
x¯1 x¯2
( , )∂f∂x2
x¯1 x¯2
:= ≈lim
h→0
f ( + h, ) − f ( , )x¯1 x¯2 x¯1 x¯2
h
f ( + Δh, ) − f ( , )x¯1 x¯2 x¯1 x¯2
Δh
:= ≈lim
h→0
f ( , + h) − f ( , )x¯1 x¯2 x¯1 x¯2
h
f ( , + Δh) − f ( , )x¯1 x¯2 x¯1 x¯2
Δh
20/3/2023 14:30MAST90045 Assignment 1
第3/8⻚file:///Users/bonnie/Downloads/asmt1_q.html
Let’s do some experiments to see how well it performs. First, implement the following
procedure:
1. Write fd function that takes x and dh , and returns c(dydx1, dydx2) based on
Nnite difference,
2. Generate 10000 random points with the Nxed
randomness using set.seed(90045) ,
3. Compute the gradient using fd for each ,
4. Measure the error for each where is computed
using fgh2 included in the answer source Nle, and
5. Obtain and store the average error over 10000 errors.
Run experiments for your choice of , which is to be given to fd as dh . Report the
average error and the total execution time. You may use proc.time to time the
execution.
1-6 (15 pts)
Run the same experiments but using ad . Then, discuss the results from both sets of
experiments and implications for solving problems using gradient-based algorithms.
Question 2 (50 pts)
Suppose you are an industrial designer developing an object shaped like the following.
∈ [−0.5, 3] × [−0.5, 2]x¯
f ( )∇FD x¯ x¯
‖ f ( ) − ∇f ( )∇FD x¯ x¯ ‖∞ x¯ ∇f ( )x¯
Δh
20/3/2023 14:30MAST90045 Assignment 1
第4/8⻚file:///Users/bonnie/Downloads/asmt1_q.html
The left and right boundaries are rings of cm radius. The width is cm. Imagine the
object placed in 3-D Euclidean space with the centre at the origin. The shape
requirement is secondary and ]exible as long as it looks like the above. A priority is to
use expensive materials for superior colouring. So, to reduce costs, you want to
minimise an amount of materials used to produce each item by minimising its surface
area.
The manufacturing process is similar to wheel throwing for pottery. Consequently, the
minimisation problem is essentially to Nnd the best curve passing through
and , which is revolved about the x-axis to shape the object. For example,
the above object is shaped by revolving the following curve.
2-1 (5 pts)
2 2
y = f (x)
(−1, 2) (1, 2)
20/3/2023 14:30MAST90045 Assignment 1
第5/8⻚file:///Users/bonnie/Downloads/asmt1_q.html
You begin with heuristic search. Because of its ease of manufacturing, you Nrst consider
a set of piece-wise linear curves speciNed by two parameters and
. For example, the following Ngure shows the curve for and .
(In reality, two sharp kinks are slightly rounded, but assume this is reasonable
approximation.)
This results in the following object.
a ∈ (0, 1]
b ∈ [0, 2] a = 0.5 b = 0.6
20/3/2023 14:30MAST90045 Assignment 1
第6/8⻚file:///Users/bonnie/Downloads/asmt1_q.html
Find an expression for and compute the surface area as a function of
and .
2-2 (3 pts)
Next, you consider more general curves — a set of such that is non-negative
and differentiable over . First, note the following. When changes by an
inNnitesimal amount , the point on the curve at moves along the curve by
Explain why this is the case.
2-3 (4 pts)
To formally express revolution of about the x-axis, besides , it is
convenient to deNne another variable . When and change by inNnitesimal
amounts and respectively, it creates a surface area
Explain why this is the case.
2-4 (8 pts)
The whole surface area created by revolution of is obtained by the following
integral:
y = f (x; a, b) a
b
y = f (x) f
[−1, 1] x
dx (x, f (x))
dx.1 + [ (x)f ′ ]2‾ ‾‾‾‾‾‾‾‾‾‾√
y = f (x) x ∈ [−1, 1]
θ ∈ [0, 2π] x θ
dx dθ
dA = f (x) dxdθ.1 + [ (x)f ′ ]2‾ ‾‾‾‾‾‾‾‾‾‾√
y = f (x)
= dA
2π 1
20/3/2023 14:30MAST90045 Assignment 1
第7/8⻚file:///Users/bonnie/Downloads/asmt1_q.html
This allows us to formally express our optimisation problem as follows.
where is a set of non-negative differentiable functions over .
Notice that this optimisation problem is somewhat different from what we learn in the
class where we try to Nnd an optimal vector in Euclidean space. Here, we try to Nnd an
optimal function in . Nonetheless, the approach to Nnding a local optimum is based on
the same idea — the Nrst-order necessary condition (i.e., the vanishing derivative at a
local extremum).
It turns out that minimising the above integral is equivalent to minimising its integrand.
So, let denote the integrand
Our optimisation problem is now
In this context, the Nrst-order necessary condition (a.k.a., the Euler-Lagrange equation) is
expressed as the following differential equation,
where each partial derivative is taken as if were a function of only or .
Compute the derivatives and simplify the equation as nicely as possible. (You should get
a non-linear differential equation.)
A(f ) = dA∫
2π
0 ∫
1
−1
= f (x) dxdθ∫
2π
0 ∫
1
−1
1 + [ (x)f ′ ]2‾ ‾‾‾‾‾‾‾‾‾‾√
= 2π f (x) dx.∫
1
−1
1 + [ (x)f ′ ]2‾ ‾‾‾‾‾‾‾‾‾‾√
2π f (x) dx,min
f∈ℱ ∫
1
−1
1 + [ (x)f ′ ]2‾ ‾‾‾‾‾‾‾‾‾‾√
ℱ [−1, 1]
ℱ
L(x, f , )f ′
L(x, f , ) = f (x) .f ′ 1 + [ (x)f ′ ]2‾ ‾‾‾‾‾‾‾‾‾‾√
L(x, f , ).min
f∈ℱ
f ′
= ,∂L∂f
d
dx
∂L
∂f ′
L f f ′
20/3/2023 14:30MAST90045 Assignment 1
第8/8⻚file:///Users/bonnie/Downloads/asmt1_q.html
2-5 (10 pts)
The general solution to the differential equation above is
Find and that satisfy the boundary conditions. You need not but may use
newtonraphson provided in the answer source Nle.
2-6 (6 pts)
Using the values for and found above, analytically compute the integral
where
What is the minimised surface area?
2-7 (14 pts)
The client has just changed its mind and now wants a smaller object of cm radius,
instead of cm, at both boundaries. What is your answer to the modiNed optimisation
problem?
f (x) = α cosh( ).x − βα
α β
α β
A(f ) = 2π f (x) dx,∫
1
−1
1 + [ (x)f ′ ]2‾ ‾‾‾‾‾‾‾‾‾‾√
f (x) = α cosh( ).x − βα