Polynomials
You should know what a polynomial is at this point, but just in case you’ve forgotten, a polynomial is any mathematical expression constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents. For example, a univariate polynomial may take the form:
f(x) = x^2 + -8x + 12
We would say that this polynomial has degree 2 and consists of 3 terms being summed (x^2 , -8x, and 12). The univariate example (1) is one-dimensional (that is, variable x is a scalar), but polynomials can have any number of variables, and those variables can be multiplied together in any combination. Figure 1 shows some examples of polynomials, and the bottom row is just two univariate polynomials (the same form as (1)) - one of x1 and one of x2 -added together. More generally we can express multivariate polynomials with any number of variables:
f(x1, x2, x3) = x1^2 + x2^2 + x1^3x2^2x3 + -4x1x2 + -8x1x2x3 + -x2 + 1
Of course it does not matter whether our variables are x1, x2, x3, … or x, y, z, ….
In this project, we will try to minimize multivariate polynomials like (2). As you can see from the examples in Figure 1, minimization will not be easy. Local minima may be present, and the problem may be unbounded (the polynomial goes to -∞). So, we will content ourselves with finding a local minimum. In the real world, we are often happy to accept a local minimum as a solution when the objective function is too difficult to globally optimize.
The steepest descent algorithm
The steepest descent algorithm is part of a class of algorithms called directional search methods. Basically, we start at some feasible point, pick a direction to move, pick an distance to move in the direction, and then move to a new point by a taking a step along the selected distance (see Figure 2). We repeat the process over and over until we have reached some stopping criteria.
As you can see, the two primary components of directional search methods are the step direction and the step length, and they are essentially the only things that vary from one directional search method to another.
Stopping criteria
Two common stopping criteria are
- Maximum number of iterations reached
- Sufficient closeness to a local minimum
How can we tell if we are sufficiently close to a local minimum? Just look at the gradient ∇f(x): If the gradient is close to zero, then we are probably pretty close to a local minimum. Since we have a vector of variables (x) and not just a scalar, the gradient will be a vector, and so we look at the size of gradient (defined by its norm) to see how close we are.
Step direction
In steepest descent, the goal is to move as quickly as possible to the closest local minimum. Recall that the first derivative of a one-dimensional function tells us the slope of the function. If we want to get to the closest local minimum, we should just follow the slope; more specifically, follow the negative of the slope. For example, Figure 1a shows f(x) = x^2 , which has derivative f0(x) = 2x and minimum at x = 0. If x = 4, then f0(4) = 8, so our direction should be −8, meaning that we should reduce x to get closer to the minimum.
The process for a multi-dimensional x is the same. Since a gradient is just a collection of first derivatives (slopes) for every variable, if we are at point x, the direction with the most decrease in every variable is just the negative gradient, −∇f(x).
Line search
Normally, we would try to optimize the step size α each iteration by performing what is called a line search (an optimization of f as a function of α), but we will be easy for now and just fix α to one value for whole algorithm. If we make α too big, we may continually step over the local minimum and never converge; however, if we make α too small, we may take such small steps that our algorithm moves too slowly to be practical. There’s no easy way to find a happy middle ground; we just have to try out different values and see what works for our particular problem.
Program description
In this project, you will implement the steepest descent algorithm to find local minima of polynomials of the form(2). You will display the performance of the algorithm for the following metrics:
- Final objective function value
- Closeness to local minimum
- Number of iterations needed for the algorithm to run
- Computation time needed for the algorithm to run
Important Notes: Most input-output statements, polynomial parsing, and a compilable skeleton of all classes in the project are provided for you. This project should require much less focus on output formatting than previous projects. You have to implement reading from a file, symbolic differentiation, and gradient descent optimization. In addition, you have to get used to working with ArrayLists, TreeSets - a sorted variant of a HashSet, and HashMaps. This will take some getting used to, but these are invaluable tools in modern Java programming. For all of the Java “Collections” classes as well as other classes you are encountering for the first time (e.g., StringBuilder), please refer to their Java documentation (just Google for “Java” and the class name) to understand what functionality these classes offer.
While I have provided a lot of code for you, I would expect that you can write all code on your own - so please read through and understand it - you may see a snippet on an exam.
Menu options
All menu functionality has been implemented for you in Pro3_utorid.java except for implementation of method calls in other classes and the first option R, where you have to implement file reading.
- R - Read polynomial function
The user enters a filename where the polynomial can be read. Polynomial parsing has been implemented for you in the Polynomial class constructor. - F - View polynomial function
The polynomial function is printed to the console. This functionality and the implementation of toString() for the Polynomial class has been done for you. - S - Set steepest descent parameters
The user enters values for each of the steepest descent parameters: tolerance, maximum number of iterations, step size α, and starting point (x(0) for all variables in the polynomial). Aside from method calls in other classes, this functionality has been done for you. - P - View steepest descent parameters
The steepest descent parameters are printed to the console. This functionality has been done for you. - M - Minimize polynomial by gradient descent
Run the steepest descent algorithm on the polynomial. You need to implement the functionality in the Minimizer class. - Q - Quit
Quit the program.
Error messages
All output and error messages have been provided for you in the code. Our test cases for this project will focus on correct functionality of the minimizer rather than error checking for pathological cases.