Fundamentals on Unconstrained Optimization. Stepsize Computation

Unconstrained optimization consists of minimizing a function which depends on a number of real variables without any restrictions on their values. When the number of variables is large, this problem becomes quite challenging. The methods for the unconstrained optimization are iterative. They start with an initial guess of the variables and generate a sequence of improved estimates of the minimum point until they terminate with a set of values for variables. At every iteration xk an optimization algorithm computes the search direction dk in the current point, which must be a descent one, and a stepsize αk taken along the search direction to obtain a new estimation of the minimum point, xk+1 = xk + αkdk. The purpose of this chapter is to present the most important modern methods as well as their convergence properties for computing the stepsize αk, which is a crucial component of any unconstrained optimization algorithm. For checking if this set of values of variables is indeed the solution of the problem, the optimality conditions should be used. If the optimality conditions are not satisfied, they may be used to improve the current estimate of the solution. The algorithms described in this book utilize the values of the minimizing function, of the first and possibly of the second derivatives of this function. Other methods based only on function’s values (Golden-section search, Fibonacci, compass search, dichotomous search, quadratic interpolation) are not considered in this book. We emphasize and recommend that the reader study the mathematical concepts and results included in Appendix A.