CS1500
Algorithms and Data Structures for Engineering, FALL 2012
HW2 Gradient Descent
Implement the Gradient Descent algorithm for finding the minimum of a
polynomial function of one variable f(x).Your program has to :
- Allow the user to define the function: read the degree and
polynomial coefficients from a file (in any readable format, we suggest this
format). Ask the user for the filename.
In order to avoid using arrays, you can define the 5 coefficients
(assume maximum degree 4) as global variables, that is outside any
function. Alternatively, you can use an array of coefficients, but we have a lecture on arrays until next week.
- Implement a C++ function double
userfunction(double) that computes f(x) for any real numbers x.
- Implement a C++ function double
userfunction_diff(double) that computes the first differential f'(x) on real arguments x.
- Implement the
Gradient descent loop for finding the minimum value of f using repeated
calls to the two functions above, starting with an initial guessed
argument x. Make sure the
termination condition causes the loop to finish eventually.
- Try
several learning rates λ, see what works best.
- EXTRA CREDIT: You can also
try to vary λ across loop iterations: start with a larger value, and
decrease it when x approaches the optimum.
- EXTRA CREDIT: Try to identify the cases where from starting x, following gradient descent leads to minus infinity.
Try your program with the following functions (other functions could be
used by TA for testing):
f(x)= (x-2)2+1, start with x=3
f(x) = 5x^3 - 16.25x^2 - 205x +6.57, start with x=0 , use λ=0.002
A description of the complete algorithm can be found here; however
lecture notes
are sufficient for this assignment. As usual for homeworks,
you have to write the pseudocode and submit it together with your code.
EXTRA CREDIT: Implement Gradient Descent for polynomials up to degree 4
with two variables f(x1,x2).
EXTRA CREDIT: Implement Gradient Descent for other functions (not polynomials) of two
variables, like Radial-Basis
Functions.