CHAPTER 1
INTRODUCTION

Background Of the Study

In mathematics, optimization problem is a problem where it consists of maximizing or minimizing a real function by systematically choose an input values within an allowed set and compute the value of the function. An additional, it also means solve the problem so that we can the goal as quickly as possible without wasting a lot of resources.

Optimization also can be deviating from a target by the smallest possible margin. Generally, a large area of applied mathematics is comprised by the optimization theory and techniques to other formulations. In the simple case, optimization is like finding a good value or a best available value of some problems given a defined domain, including a many of different types of objectives functions and different types of domains.

In vector calculus, the gradient of a scalar field is a vector field that points in the direction of the scalar field, and whose the magnitude is that rate of increase. The variation in space of any quantity can be represented by a slope in simple terms. The gradient is like represents the steepness and the direction of the slope. The gradient or gradient of a scalar function f〖:R〗^n→R^1 is denoted by ∇f or ∇ ⃗f where ∇ denotes the vector of the differential operator.

Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and this matrix is later named after him. Hessian matrix is the matrix of second derivatives of a multivariate function. In mathematics it means the gradient of the gradient of a function. Hessian matrix is relevant in many places such as in economy too.

Let a real-valued function f〖:R〗^n→R^1 be given and if all the second partial derivatives of f exist and are continuous over the domain of the function, then the Hessian matrix of f is

H(f)_ij (x)=D_i D_j f(x)=(δ^2 f(x))/(δx(δx))

where x=(x_1,x_2,…,x_n ) and D_i is the differentiation operator with the respect to the ith argument. Hence

H(f)(x)=∇^2 f(x)=[■((∂^2 f)/(〖∂x〗_1^2 )&(∂^2 f)/(∂x_1 ∂x_2 )&…@(∂^2 f)/(∂x_2 ∂x_1 )&(∂^2 f)/(〖∂x〗_2^2 )&…@■(⋮@(∂^2 f)/(∂x_n ∂x_1 ))&■(⋮@(∂^2 f)/(∂x_n ∂x_2 ))&■(⋱@…)) ■((∂^2 f)/(∂x_1 ∂x_n )@(∂^2 f)/(∂x_2 ∂x_n )@■(⋮@(∂^2 f)/(〖∂x〗_n^2 )))] Second derivative test is a test to determine if a given critical point of a real function of one variable is a local maximum or minimum. The real function is twice differentiable at a critical point, x:

Theorem: Sufficient Conditions for an Extremum.

Let f be twice differentiable, then

If f"(x) < 0, then f has a local maximum at x. If f"(x) > 0, then f has a local minimum at x. If f"(x) = 0, the test is inconclusive.

For n-dimensional cases, we have the following criteria:

If ∇^2 f(x) is positive definite, then f has a local minimum at x. If ∇^2 f(x) is negative definite, then f has a local maximum at x. If ∇^2 f(x) is non-definite, then the test is inconclusive.

Objective Of the Study

In this study, we wish to investigate the effect of scaling within the symmetric rank one for unconstrained optimization.
The specific objectives are as follow: To derive some scaling for the symmetric rank one update in preserving the positive definiteness of the updating matrix. To compare the performance of symmetric rank one method with various choices on the scaling.

Outline Of the Report

This report is divided into 5 chapters. Chapter 1 consist the background of the study which includes the introduction of the optimization, gradient and the Hessian matrix. We also state the objectives of this study and the overview of the report.

Chapter 2 gives a brief review of literature on Newton method, quasi-Newton method and symmetric rank one method.

We will describe about the methodology or ways to conducts this paper in Chapter 3. We will discuss about the method that are considered in solving the test problems.
In additional, the algorithms of the scaling of the symmetric rank one method will be provided.

Next, in Chapter 4, we will attempt to show the calculations and results of the few test problems. We will make a comparison between the various scaling that we choose and at the end will discuss whether which scaling is more effective to use in solving the unconstrained optimization.

Finally we conclude the results and findings of this study in Chapter 5. In addition, we will recommend some areas for further research that might play an important role in future study.

CHAPTER 2
LITERATURE REVIEW

Newton method also can be called as the Newton-Raphson method or Newton Iteration. It is a root finding algorithm. But somehow Newton method has its own drawbacks. There is the Newton method is an expensive method which mean it will cost a lot if using this method to solve some problem.

In Newton method, it assumes that the function can be locally approximated as a quadratic in a region around the optimum and the method uses the first and the second derivatives to find out the stationary point. Newton method uses the gradient and the Hessian matrix of the second derivatives of the function to be minimized in the higher dimension.

The main purpose of quasi-Newton method is to find the local maxima and minima of the functions or problems. Quasi-Newton method is based on the Newton method to find the stationary point of the function where the gradient will be zero. Stationary point is an input to a function where the derivative is zero in mathematics.

Today, quasi-Newton method is recognized as one of the most efficient ways to solve the nonlinear unconstrained or bound constrained optimization problems. This quasi-Newton method is mostly used when the second derivative matrix of the objective function is either unavailable or too costly to compute. Actually, they are very similar to Newton method but it avoiding the need of computing the Hessian matrices by recurring, from the iteration to the iteration, a symmetric matrix which can be considered as an approximation of the Hessian.

But the Hessian matrix does not need to be computed in quasi-Newton method because the Hessian is updated. It was updated by analyzing successive gradients vectors instead. Furthermore, the quasi-Newton method is a generalization of the secant method to find the root of the first derivative for the multidimensional problems.

In the multi-dimension problem, the secant equation is cannot be determined. Not only have that, the quasi-Newton method also different in how they constrain the solution by just typically adding a simple low rank updated to the current estimate of the Hessian.

W.C. Davidon (1959) is a physicist who works in the Argonne National Laboratory and he developed the first quasi-Newton method in 1959 which is the updating Davidon-Fletcher-Powell formula (Davidon, 1970) but it is rarely to be used nowadays. The most common one now is symmetric rank one method (SR1).

The SR1 method is actually a quasi-Newton method which to update the second derivative of Hessian matrix based on the derivatives calculated at two points. Next, SR1 is a generalization to the secant method for a multidimensional problem. Secant method is a way of root finding algorithm that uses the succession of roots of secant lines to better approximate the root of a function. If compared to the secant method, the SR1 method is much simpler and may require less computation per iteration when unfactored forms of methods are used.

Symmetric rank one method update the Hessian approximation and it update rule is known to have a good numerical performance. So, the update of the symmetric rank one maintains the symmetric of the matrix but however it does not guarantee the update will be positive definite. In generally, an n x n complex matrix M is said to be positive definite if z*Mz is real and positive for all non-zero complex vectors z.

Symmetric rank one method generated the sequence of Hessian approximations under mild conditions. In another meaning is symmetric rank one generated the approximate Hessians to show faster progress towards the true Hessian if comparing with doing those popular alternatives method like David-Fletcher-Powell formula (DFP) (Davidon, 1970) or Broyden-Fletcher-Goldfarb-Shanno formula (BFGS) (Shanno, 1970) in preliminary numerical experiments.

Quasi-Newton algorithm for the unconstrained nonlinear minimization generates a sequence of matrices that can be considered as approximation of the objective function second derivatives. Conn et al. (1991) proposed and give the conditions under which these approximations can be proved to converge globally to the true Hessian matrix. In the case where the symmetric rank one update formula is used. They examined and proved the rate of convergence and can improving with the rate of convergence of the underlying iterate. Numerical experiments confirmed the theory and the experiments also show the convergence of the Hessian approximation to be substantially slower for the other known quasi-Newton formula.

Multi-step quasi-Newton methods for unconstrained optimization used by the Ford and Moghrabi (1997). They showed how an interpolating curve in the variable spaces could be used to derive an appropriate generalization of the Secant Equation normally employed in the construction of quasi-Newton methods. One of the most successful of these multi-step methods employed the current approximation to the Hessian to determine the parameterization of the interpolating curve and, hence the derivatives which are required in the generalized updating formula.

The certain of approximations were found to be necessary in the process in order to reduce the level of computation required which must be repeated in each iteration to acceptable level. However, they showed how a variant of the algorithm which avoids the need for such approximation, may be obtained.

Hassan et al. (2002) proposed a scaling symmetric rank one update method for the unconstrained optimization because the disadvantages of this method is that the symmetric rank one update may not preserve the positive definiteness when starting a point with a positive definite approximation. So they started a simple remedy to this problem by just restart the update with the initial approximation mostly the identity matrix whenever this difficulty arises. Instead of using the identity matrix, they used a positive multiple of the identity matrix however the numerical experience shows that restart with the identity matrix is not a good choice. They used the positive scaling factor because the positive scaling factor is the optimal solution of the measure defined by the problem.

Ting and Sun (2008) proposed a new quasi-Newton pattern search method based on symmetric rank one update for unconstrained optimization. They developed a new robust and quickly convergent pattern search method based on an implementation of Optimal Conditioning Based Self-Scaling symmetric rank one algorithm for unconstrained optimization. The factorization of approximating Hessian matrices had utilized by this method to provide a series of convergent positive bases needed in pattern search process. They performed numerical experiments on some famous optimization test problems to show that the new method performs well and is competitive in comparison with some other derivative-free methods.

A generalized symmetric rank one method is generalized by Modarres et al. (2009). They employed the interpolatory polynomials. In numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. So, they employed it in order to possess more accurate information from more than one previous step.

In their study, the basic idea is that they incorporate the symmetric rank one update within the framework of multi-step methods. Additionally, iterates could be interpolated by a curve in such a way that the consecutive points define the curves. However they preserve the positive definiteness of the symmetric rank one updates a restart procedure is applied, in which they restart the symmetric rank one update by a scale of the identity. They also compared the results with the Broyden-Fletcher-Goldfarb-Shanno formula (BFGS).

Symmetric rank one is one of the competitive formulas among the quasi-Newton methods. Some modified symmetric rank one updates based on the modified secant equations is proposed by Modarres et al. (2009) which use both gradient and function information. They applied a restart procedure to this update in order to prevent the loss of positive definiteness and zero denominators of the new symmetric rank one updates.

To improve the Hessian approximation, three new algorithms are given to improve it with modified secant equations for the symmetric rank one method. In the results they showed clearly that the proposed algorithms are very encouraging and the advantages of the proposed algorithms over the standard symmetric rank one.

For the large-scale optimization, Leong and Hassan (2011) developed a scaled memoryless symmetric rank one method for it. They concerned the memoryless quasi-Newton method which precisely the quasi-Newton method for which the approximation to the inverse of Hessian, at each step, is updated from the identity matrix. Not only that, the search direction can be computed without the storage of the matrices.

The basic idea is to incorporate the symmetric rank one update within the framework of the memoryless quasi-Newton method. Somehow the symmetric rank one update may not preserve positive definiteness even when the updated from a positive definite matrix. Therefore they proposed the memoryless symmetric rank one method which is updated from a positive scaled of the identity, where the scaling factor is derived in such a way that the positive definiteness of the updating matrices are preserved and at the same time improves the conditions of the scaled memoryless symmetric rank one update. Their study showed that the optimally scaled memoryless symmetric rank one method is very encouraging.

Khiyabani and Leong (2012) performed a new symmetric rank one method with restart for solving unconstrained optimization problems. This new method attempts to improve the quality of the symmetric rank one Hessian by employing the scaling of the identity in a certain sense.

Somehow they proposed an updates criterion based on the eigenvalues of the symmetric rank one update to measure the quality due to some iterations these updates might be singular, indefinite or undefined. They stated that the new method is employed only to improve the approximation of the symmetric rank one Hessian. Hence it showed that the numerical results support the theoretical considerations for the usefulness of the criterion and show that the proposed method improves the performance of the Symmetric rank one update substantially.

CHAPTER 3
METHODOLOGY

3.1 Introduction

The chapter describes the detailed procedures of scaling of symmetric rank one method in solving the unconstrained optimization problems.

In this study, we are concerned with the numerical methods for solving the unconstrained nonlinear optimization problem

min⁡〖f(x),〗 (3.1.1)

where the objective function f:.^n→. is a twice continuously differentiable defined in n-dimensional space.

Among the numerous iterative methods in solving this kind of function (3.1.1), quasi-Newton method can be used. The quasi-method requires only the gradient of the objective function to be supplied at each iterate.

The simplest possibility is to have

H_(k+1)=H_k+E_k=H_k+auu^T, (3.1.2)

in which a is a scalar and a symmetric rank one matrix E_k=auu^T y_k=s_k is added into H_k where s_k=x_(k+1)-x_k , y_k=g_(k+1)-g_k and g_k=∇f(x_k ).

If the quasi-Newton equation

H_(k+1) y_k=s_k, (3.1.3)

is to be satisfied, it follows (3.1.2) and (3.1.3) that

H_(k+1) y_k=H_k y_k+auu^T y_k=s_k, (3.1.4)

or

auu^T y_k=s_k-H_k y_k . (3.1.5)

Hence, ▁u is proportional to s_k-H_k y_k. We may also take

▁u=s_k-H_k y_k. (3.1.6)

Then, 〖au〗^T y_k=1, (3.1.7)

or

a=1/(u^T y_k )=1/((s_k-H_k y_k )^T y_k.) (3.1.8)

Thus, the symmetric rank one formula is given by

〖 H〗_(k+1)=H_k+((s_k-H_k y_k ) 〖(s_k-H_k y_k)〗^T)/(〖(s_k-H_k y_k)〗^T y_k ), (3.1.9)

where s_k=x_(k+1)-x_k , y_k=g_(k+1)-g_k and g_k=∇f(x_k ) denotes the gradient vector of f at current iteration point x_k.

In order to ensure the positive definiteness of the symmetric rank one method, various choices of scaling is used where H_k is updated using the following formula

H_k=θH_(k-1)+((s_(k-1)-〖θH〗_(k-1) y_(k-1) ) (s_(k-1)-〖θH〗_(k-1) y_(k-1) )^T)/((s_(k-1)-θH_(k-1) y_(k-1) )^T y_k ), (3.1.10) where θ is chosen as in order to keep the positive definiteness. Note that if (s_(k-1)-θH_(k-1) y_(k-1) )^T y_k>0, then H_k is positive definite if θ>0 and H_(k-1) is positive definite. So, an appropriate choice of θ should be such that

〖(s_k-H_k y_k)〗^T y_k>0, (3.1.11)

s_k^T y_k-θy_k^T H_k y_k>0, (3.1.12)

θ0. (3.2.3)

Then we have

s_k^T y_k-θy_k^T H_k y_k>0, (3.2.4)

θ