代写一个Java程序，可以自动计算给定数据的梯度最小值。
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.
