The main of this paper is to study methods to solve optimization problem whose objective function does not possess partial derivatives available at hard  . This is due to the difficulty of finding derivatives. Derivative-free optimization (DFO) models attempt to express, in mathematical terms, the goal of this paper to solving problems in the “best” way, optimization, in lower dimensional subspaces. These new methods can be considered to develop this method. The new
method starts with an initial data points, where, n is the
dimension of the problem. An initial guess is provided first, then using random Householder’s and Given’s, matrices, the other points are generated   , with thought of as a centre. The other points are equidistant from, , with distance a pre-assigned radius. During the iterations there is need to regenerate the interpolation data points. This is done when no progress in function decrease has taken place. The interpolation points are selected to be D units distant from the kth iterate of . The Householder matrix , is used in the generation of the rest points   . Given a random vector z where its components are uniformly distributed in , i.e., , is obtained so that . Now if z is a column of then a point y is defined by,  . The resulting algorithm is shown to be numerically highly competitive.
2. Basic Material
Many interpolation-based trust-region methods construct local polynomial interpolation-based models of the objective function and compute steps by minimizing these models inside a region using the standard trust-region methodology    . The models are built so as to interpolate previously computed function values at a subset of past iterates or at specially constructed points. For the model to be well-defined, the interpolation points must be poised    . To provide the reader with some necessary information about used notations, we have to recall some basic material about the general trust-region framework, multivariate interpolation, Lagrange polynomials and the definition of poised-ness and well-poised-ness   .
3. Lagrange Polynomials
If the interpolation set Y is poised, the basis of Lagrange polynomials exists and is uniquely defined by  .
Given a set of interpolation points a basis of p polynomials in is called a basis of Lagrange polynomials if
The unique polynomial which interpolates on Y using this basis of Lagrange polynomials can be expressed as
Moreover, for every poised set , we have that
The accuracy of as an approximation of the objective function f in some region can be quantified using the following notion   . A poised set is said to be Λ-poised in B for some if and only if for the basis of Lagrange polynomials associated with Y,  .
The right hand side of (3) is related to the Lebesgue constant of the set which is defined as
see for instance    . Given the following relations
we conclude that
It is a measure of the accuracy of the polynomial interpolation at the set of points below. This suggests to look for a set of interpolation points with a small Lebesgue constant. Hence, conversely, the smaller Λ, the better the geometry of the set Y, importantly for our purposes, Lagrange polynomial values and Λ-posedness can be used to bound the model function and model gradient error. In particular, it is shown in Ciarlet and Raviart  ,  that for any x in the convex hull of Y.
Using the natural basis and a sample set , with , , , .
Choosing now the first four columns of , the system is determined but not well defined since the matrix is singular. We see now that the set Y is not
poised with respect to the sub-basis , but if we selected the
sub-basis , the set Y is well-poised and the corresponding matrix consisting of the first, the second, the third, and the sixth columns of is well-conditioned and a unique solution to this determined system exists. is given by   .
4. Unconstrained DFO Algorithm
We consider the bound-constrained optimization problem
where f is a nonlinear function from into , which is bounded below, and where l and u are vectors of (possibly infinite) lower and upper bounds on x. We denote the feasible domain of this problem by F  .
a model of the form
(where and are the function’s gradient and Hessian, respectively) is minimized inside a trust region , as derivatives are not given, and are approximated by determining its coefficients (here represented by the vector, ) from the interpolation conditions 
The points considered in the interpolation conditions (10) form the interpolation, set . The set contains in our case at least points and is chosen as a subset of , the set of all points where the value of the objective function f is known. How to choose this interpolation set is of course one of the main issues we have to address below, as not every set is suitable because of posedness issues   . We propose to handle the bound constraints by an “active-set” approach where a bound or is called active at x if or , respectively. The bound constraints and are inactive if at x.
4.1. The Ingredients Strategy
In a trust-region algorithm for choosing the trust-region radius at each iteration. We base this choice on the agreement between the model function and the objective function f at previous iterations. Given a step we define the ratio:
The numerator is actual reduction, and the denominator is the predicted reduction (that is, the reduction in f predicted by the model function). The method has been developed and especially model-based trust-region methods have been shown to perform well. It improves the efficiency of method while maintaining its good theoretical convergence properties, furthermore, the unconstrained method applying a model-based derivative-free method  . The interpolation points are chosen randomly, at each iteration, the generation of the random points is descanted in the functions. The function proved to be quite helpful to restore the method on the right track. This is because of randomness. The method proved to be efficient and reliable.
The accuracy of the method is acceptable and relies on the contours of the objective function. The step is obtained by minimizing the model over a region that includes , the predicted reduction will always be nonnegative. Hence, if is negative, the new objective value is greater than the current value , so the step must be rejected. On the other hand, if is close to 1, there is good agreement between the model and the function f over this step, so it is safe to expand the trust region for the next iteration. If is positive but significantly smaller than 1, do not alter the trust region, but if it is close to zero or negative, we shrink the trust region by reducing at the next iteration   .
Here (radius) is an overall bound on the step lengths. That the radius is increased only if actually reaches the boundary of the trust region. If the step stays strictly inside the region, we infer that the current value of is not interfering with the progress of the algorithm, so leave its value unchanged for the next iteration. The shape of the points looks like a moving cone. To turn Algorithm into a practical algorithm, we need to focus on solving the trust-region sub-problem
In discussing this matter, we sometimes drop the iteration subscript k and restate the problem as follows
A first step to exact solutions is given by the following:
Assume that at the current iterate we have a set of sample points
with again assume that is an element of this set and that no point in Y has a lower function value than . This point depends on Householder’s and Given’s matrices   . The choice of the points was guided by a desire to model-based method. Wish to construct a quadratic model of the form  
In general the matrix is given as the follows:
1) Input the ,
then set size of Y.
2) Solve the model (3) to find .
The matrix ;
4.2. Theorem (First Order Necessary Conditions)
If is a local minimize and f is continuously differentiable in an open neighborhood of , then   .
4.3. Theorem (Second Order Necessary Conditions)
If is a local minimize of f and exists and is continuous in an open neighborhood of , then and is positive semi definite    .
4.4. Theorem (Second Order Sufficient Conditions)
Suppose that is continuous in an open neighborhood of and that and is positive definite. Then is a strict local minimize of f  .
Let f be twice Lipschitz continuously differentiable in a neighborhood of a point at which second-order sufficient conditions Theorem 4.4 are satisfied. Suppose the sequence converges to and that for all k sufficiently large, the trust-region algorithm based on chooses steps that satisfy the Cauchy-point-based model reduction criterion and are asymptotically
similar to Newton steps whenever , that is  ,
Then the trust-region bound becomes inactive for all k sufficiently large and the sequence converges super-linearly to   .
5. The Selected Test Problems
The following functions are used in testing method have been selected from  and 
The Output (Tables 1-12)
Table 1. Summary of structural iterative solution overview of (DFO) of the function the initial point is .
Table 2. The value of the function at each iteration in Table 1.
Table 3. Summary of structural iterative Solution overview of (DFO) of the function using the last point in the iterative in Table 2 .
Table 4. The value of the function at each iteration in Table 3.
Table 5. Summary of structural iterative Solution overview of (DFO) of the function using the last point in the iterative in Table 4 .
Table 6. The value of the function at each iteration in Table 5.
Table 7. Summary of structural iterative Solution overview of (DFO) of the function using the initial point in Table 6 .
Table 8. The value of the function at each iteration in Table 7.
Table 9. Summary of structural iterative Solution overview of (DFO) of the function using the last point in the iterative in Table 8 .
Table 10. The value of the function at each iteration in Table 9.
Table 11. Summary of structural iterative Solution overview of (DFO) of the function using the last point in the iterative in Table 10 .
Table 12. The value of the function at each iteration in Table 11.
In this paper it has been shown that using a randomly selected data set point, within an interpolation based method for derivative free optimization was adequate and practical. In the generating of these randomly selected points Householders and Given’s matrices were used. The randomness comes from the random seed vectors, which were then transformed by Householders and Given’s matrices into the required.
I would like to thank my supervisor, Dr. Muhsin Hassan Abdallah who was a great help to me.
 Conn, A.R., Gould, N.I.M. and Toint, P.L. (2000) Trust-Region Methods. MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA. https://doi.org/10.1137/1.9780898719857
 Dennis, J.E. and Schnabel, A.B. (1989) A View of Unconstrained Optimization. In: Handbooks in Operations Research and Management, Elsevier Science Publishers, Amsterdam, The Netherlands, 1-72. https://doi.org/10.1016/S0927-0507(89)01002-9
 Conn, A.R., Scheinberg, K. and Vicente, L.N. (2008) Geometry of Interpolation Sets in Derivative Free Optimization. Mathematical Programming, 111, 141-172.
 Powell, M.J.D. (1970) A New Algorithm for Unconstrained Optimization. In: Rosen, J.B., Mangasarian, O.L. and Ritter, K., Eds., Nonlinear Programming, Academic Press, New York, 31-65. https://doi.org/10.1016/B978-0-12-597050-1.50006-3
 Ciarlet, P.G. and Raviart, P.A. (1972) General Lagrange and Hermite Interpolation in 〖IR〗^n with Applications to Finite Element Methods. Archive for Rational Mechanics and Analysis, 46, 177-199. https://doi.org/10.1007/BF00252458
 Byrd, R.H., Schnabel, R.B. and Schultz, A.A. (1988) Approximate Solution of the Trust Regions Problem by Minimization over Two-Dimensional Subspaces. Mathematical Programming, 40, 247-263. https://doi.org/10.1007/BF01580735
 Dennis, J.E. and Mei, H.H.W. (1979) Two New Unconstrained Optimization Algorithms Which Use Function and Gradient Values. Journal of Optimization Theory and Applications, 28, 453-482. https://doi.org/10.1007/BF00932218