CS1500 Algorithms and Data Structures for Engineering, FALL 2012

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):
, 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.