Search

In this paper, we introduce an efficient conjugate gradient method for solving nonsmooth optimization problems by using the Moreau-Yosida regularization approach. The search directions generated by our proposed procedure satisfy the sufficient descent property, and more importantly, belong to a suitable trust region. Our proposed method is globally convergent under mild assumptions. Our numerical comparative results on a collection of test problems show the efficiency and superiority of our proposed method. We have also examined the ability and the effectiveness of our approach for solving some real-world engineering problems from image processing field. The results confirm better performance of our method. [ABSTRACT FROM AUTHOR]

Copyright of Al-Mustansiriyah Journal of Science is the property of Republic of Iraq Ministry of Higher Education & Scientific Research (MOHESR) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The paper discusses several versions of the method of shortest residuals, a specific variant of the conjugate gradient algorithm, first introduced by Lemaréchal and Wolfe and discussed by Hestenes in a quadratic case. In the paper we analyze the global convergence of the versions considered. Numerical comparison of these versions of the method of shortest residuals and an implementation of a standard Polak–Ribière conjugate gradient algorithm is also provided. It supports the claim that the method of shortest residuals is a viable technique, competitive to other conjugate gradient algorithms. [ABSTRACT FROM AUTHOR]

The conjugate gradient (CG) method is one of the most popular methods for solving large-scale unconstrained optimization problems. In this paper, a new modified version of the CG formula that was introduced by Polak, Ribière, and Polyak is proposed for problems that are bounded below and have a Lipschitz-continuous gradient. The new parameter provides global convergence properties when the strong Wolfe-Powell (SWP) line search or the weak Wolfe-Powell (WWP) line search is employed. A proof of a sufficient descent condition is provided for the SWP line search. Numerical comparisons between the proposed parameter and other recent CG modifications are made on a set of standard unconstrained optimization problems. The numerical results demonstrate the efficiency of the proposed CG parameter compared with the other CG parameters. [ABSTRACT FROM PUBLISHER]

The conjugate gradient method is widely used in unconstrained optimization, especially for large-scale problems. Recently, Zhang et al. proposed a three-term PRP method (TTPRP) and a three-term HS method (TTHS), both of which can produce sufficient descent conditions. In this paper, the global convergence of the TTPRP and TTHS methods is studied, in which the line search procedure is replaced by a fixed formula of stepsize. This character is of significance when the line search is expensive in some particular applications. In addition, relevant computational results are also presented. [ABSTRACT FROM AUTHOR]

The development of optimization theory originated with economic requirements and problems, where optimal strategy was to be determined mathematically. At about the same time, approximation theory, which was already well developed, experienced a reinvigoration brought about by the advent of electronic computers. In this paper, what follows, we recall the functional analysis that constitutes the framework of our development of an extended conjugate gradient algorithm that does not involve any approximation in any of its steps. This is a computational enhancement over the conventional conjugate gradient method which is dependent on some approximation theory. We use this improved algorithm for the construction of some functional inequalities. [ABSTRACT FROM AUTHOR]

In this paper, we present a new conjugate gradient (CG) based algorithm in the class of planar conjugate gradient methods. These methods aim at solving systems of linear equations whose coefficient matrix is indefinite and nonsingular. This is the case where the application of the standard CG algorithm by Hestenes and Stiefel (Ref. 1) may fail, due to a possible division by zero. We give a complete proof of global convergence for a new planar method endowed with a general structure; furthermore, we describe some important features of our planar algorithm, which will be used within the optimization numerical results are reported. [ABSTRACT FROM AUTHOR]

The BFGS method is one of the most, famous quasi-Newton algorithms for unconstrained optimization. In 1984, Powell presented an example of a function of two variables that shows that the Polak Ribi[egrave;]re Polyak (PRP) conjugate gradient method and the BFGS quasi-Newt, on method may cycle around eight nonstationary points if each line search picks a local minimum that provides a reduction in the objective function. In this paper, a new technique of choosing parameters is introduced, and an example with only six cyclic points is provided. It is also noted through the examples that the BFGS method with Wolfe line searches need not converge for nonconvex objective functions. [ABSTRACT FROM AUTHOR]

Conjugate gradient methods play an important role in many fields of application due to their simplicity, low memory requirements, and global convergence properties. In this paper, we propose an efficient three-term conjugate gradient method by utilizing the DFP update for the inverse Hessian approximation which satisfies both the sufficient descent and the conjugacy conditions. The basic philosophy is that the DFP update is restarted with a multiple of the identity matrix in every iteration. An acceleration scheme is incorporated in the proposed method to enhance the reduction in function value. Numerical results from an implementation of the proposed method on some standard unconstrained optimization problem show that the proposed method is promising and exhibits a superior numerical performance in comparison with other well-known conjugate gradient methods. [ABSTRACT FROM AUTHOR]

In this paper, a generalized projection quasi-Newton method with inexact line search is proposed for the nonlinear optimization problem with linear constraints. The projection and quasi-Newton technique are used to determine the search direction at each iteration. It is proved that the method has properties of global convergence and superlinear convergence rate under some suitable assumptions. [ABSTRACT FROM AUTHOR]

The original Liu-Storey (LS) method is one of the most effective nonlinear conjugate gradient methods for solving unconstrained optimization problems. Its global convergence is only obtained by using some descent backtracking line searches, which can force the original LS method to generate the sufficient descent direction at each iteration. In this paper, we prove the global convergence of the original LS method with a non-declining backtracking line search. [ABSTRACT FROM AUTHOR]

It is generally acknowledged that the conjugate gradient (CG) method achieves global convergence—with at most a linear convergence rate—because CG formulas are generated by linear approximations of the objective functions. The quadratically convergent results are very limited. We introduce a new PRP method in which the restart strategy is also used. Moreover, the method we developed includes not only n-step quadratic convergence but also both the function value information and gradient value information. In this paper, we will show that the new PRP method (with either the Armijo line search or the Wolfe line search) is both linearly and quadratically convergent. The numerical experiments demonstrate that the new PRP algorithm is competitive with the normal CG method. [ABSTRACT FROM AUTHOR]

In this paper, we study a semi-infinite programming (SIP) problem with a convex set constraint. Using the value function of the lower level problem, we reformulate SIP problem as a nonsmooth optimization problem. Using the theory of nonsmooth Lagrange multiplier rules and Danskin's theorem, we present constraint qualifications and necessary optimality conditions. We propose a new numerical method for solving the problem. The novelty of our numerical method is to use the integral entropy function to approximate the value function and then solve SIP by the smoothing projected gradient method. Moreover we study the relationships between the approximating problems and the original SIP problem. We derive error bounds between the integral entropy function and the value function, and between locally optimal solutions of the smoothing problem and those for the original problem. Using certain second order sufficient conditions, we derive some estimates for locally optimal solutions of problem. Numerical experiments show that the algorithm is efficient for solving SIP. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyze an algorithm that couples the gradient method with a general exterior penalization scheme for constrained or hierarchical minimization of convex functions in Hilbert spaces. We prove that a proper but simple choice of the step sizes and penalization parameters guarantees the convergence of the algorithm to solutions for the optimization problem. We also establish robustness and stability results that account for numerical approximation errors, discuss implementation issues and provide examples in finite and infinite dimension. [ABSTRACT FROM AUTHOR]

Algorithms that make use of the gradient, i.e., the direction of maximum improvement, to search for the optimum of a single-objective function have been around for decades. They are commonly accepted to be important and have been applied to tackle single-objective optimization problems in many fields. For multiobjective optimization problems, much less is known about the gradient and its algorithmic use. In this paper, we aim to contribute to the understanding of gradients for numerical, i.e., real-valued, multiobjective optimization. Specifically, we provide an analytical parametric description of the set of all nondominated, i.e., most promising, directions in which a solution can be moved such that the objective values either improve or remain the same. This result completes previous work where this set is described only for one particular case, namely when some of the nondominated directions have positive, i.e., nonimproving, components and the final set can be computed by taking the subset of directions that are all nonpositive. In addition we use our result to assess the utility of using gradient information for multiobjective optimization where the goal is to obtain a Pareto set of solutions that approximates the optimal Pareto set. To this end, we design and consider various multiobjective gradient-based optimization algorithms. One of these algorithms uses the description of the multiobjective gradient provided here. Also, we hybridize an existing multiobjective evolutionary algorithm (MOEA) with the various multiobjective gradient-based optimization algorithms. During optimization, the performance of the gradient-based optimization algorithms is monitored and the available computational resources are redistributed to allow the (currently) most effective algorithm to spend the most resources. We perform an experimental analysis using a few well-known benchmark problems to compare the performance of different optimization methods. The results underline that the use of a population of solutions that is characteristic of MOEAs is a powerful concept if the goal is to obtain a good Pareto set, i.e., instead of only a single solution. This makes it hard to increase convergence speed in the initial phase using gradient information to improve any single solution. However, in the longer run, the use of gradient information does ultimately allow for better fine-tuning of the results and thus better overall convergence. [ABSTRACT FROM PUBLISHER]

The present paper describes a parallel preconditioned algorithm for the solution of partial eigenvalue problems for large sparse symmetric matrices, on parallel computers. Namely, we consider the Deflation-Accelerated Conjugate Gradient (DACG) algorithm accelerated by factorized-sparse- approximate-inverse- (FSAI-) type preconditioners. We present an enhanced parallel implementation of the FSAI preconditioner and make use of the recently developed Block FSAI-IC preconditioner, which combines the FSAI and the Block Jacobi-IC preconditioners. Results onto matrices of large size arising from finite element discretization of geomechanical models reveal that DACG accelerated by these type of preconditioners is competitive with respect to the available public parallel hypre package, especially in the computation of a few of the leftmost eigenpairs. The parallel DACG code accelerated by FSAI is written in MPI-Fortran 90 language and exhibits good scalability up to one thousand processors. [ABSTRACT FROM AUTHOR]

Abstract: Part 1 of this paper proposed a methodology for the efficient determination of gradient information, when optimising a vehicle’s suspension characteristics for ride comfort and handling. The non-linear full vehicle model, and simplified models for gradient information has been discussed, and validated. In this paper, the simplified models presented in Part 1 are used for gradient information simulations. The convergence histories of the optimisation are compared to those obtained when only the full, computationally expensive, vehicle model is used. For illustration of the proposed gradient-based optimisation methodology, up to four design variables are considered in modelling the suspension characteristics. The proposed methodology is found to be an efficient alternative for the optimisation of the vehicle’s suspension characteristics. The undesirable effects associated with noise in the gradient information is effectively reduced, using the simplified models. Substantial benefits are achieved in terms of computational time needed to reach a solution. [Copyright &y& Elsevier]

Abstract: In this paper Rannacher–Turek non-conforming rotated bilinear finite elements are applied for the numerical solution of second order elliptic boundary value problems. The preconditioned conjugate gradient method is used for the iterative solution of the arising linear algebraic system . A locally optimized construction for an M-matrix approximation B of the global stiffness matrix A is the first step of the proposed algorithm. Then, the preconditioner is obtained by modified incomplete Cholesky factorization of the auxiliary M-matrix B. A comparative analysis concerning three different approaches for construction of such matrices B is presented. The related spectral condition number estimates are derived. The most important contributions of the paper is the developed original robust preconditioning scheme for strongly anisotropic problems based on properly skewed meshes. A set of numerical tests is presented to illustrate the theoretical investigations. [Copyright &y& Elsevier]

It is well-known that the conjugate gradient method is widely used for solving large scale optimization problems. In this paper a modified trust-region method with Beale's Preconditioned Conjugate Gradient (BPCG) technique is developed for solving unconstrained optimization problems. The modified version adopts an adaptive rule and retains some useful information when an unsuccessful iteration occurs, and therefore improves the efficiency of the method. The behavior and the convergence properties are discussed. Some numerical experiments are reported. [ABSTRACT FROM AUTHOR]

A class of new spectral conjugate gradient methods are proposed in this paper. First, we modify the spectral Perry's conjugate gradient method, which is the best spectral conjugate gradient algorithm SCG by Birgin and Martinez [E.G. Birgin and J.M. Martinez, A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim. 43 (2001), 117-128.], such that it possesses sufficient descent property for any (inexact) line search. It is shown that, for strongly convex functions, the method is a global convergent. Further, a global convergence result for nonconvex minimization is established when the line search fulfils the Wolfe line search conditions. Some other spectral conjugate gradient methods with guaranteed descent are presented here. Numerical comparisons are given with both SCG and CG_DESCENT methods using the unconstrained optimization problems in the CUTE library. [ABSTRACT FROM AUTHOR]

This paper proposes a line search technique to satisfy a relaxed form of the strong Wolfe conditions in order to guarantee the descent condition at each iteration of the Polak-Ribière-Polyak conjugate gradient algorithm. It is proved that this line search algorithm preserves the usual convergence properties of any descent algorithm. In particular, it is shown that the Zoutendijk condition holds under mild assumptions. It is also proved that the resulting conjugate gradient algorithm is convergent under a strong convexity assumption. For the nonconvex case, a globally convergent modification is proposed. Numerical tests are presented. [ABSTRACT FROM AUTHOR]

This paper extends some theoretical properties of the conjugate gradient-type method FLR (Ref. 1) for iteratively solving indefinite linear systems of equations. The latter algorithm is a generalization of the conjugate gradient method by Hestenes and Stiefel (CG, Ref. 2).We develop a complete relationship between the FLR algorithm and the Lanczos process, in the case of indefinite and possibly singular matrices. Then, we develop simple theoretical results for the FLR algorithm in order to construct an approximation of the Moore-Penrose pseudoinverse of an indefinite matrix. Our approach supplies the theoretical framework for applications within unconstrained optimization. [ABSTRACT FROM AUTHOR]

In this paper we propose new globalization strategies for the Barzilai and Borwein gradient method, based on suitable relaxations of the monotonicity requirements. In particular, we define a class of algorithms that combine nonmonotone watchdog techniques with nonmonotone linesearch rules and we prove the global convergence of these schemes. Then we perform an extensive computational study, which shows the effectiveness of the proposed approach in the solution of large dimensional unconstrained optimization problems. [ABSTRACT FROM AUTHOR]

Abstract: The present paper is devoted to solve the problem of identifying an unknown heat source depending simultaneously on both space and time variables. This problem is transformed into an optimization problem and the uniqueness of minimum element is proved rigorously. Then a variational formulation for solving the optimization problem is given. A conjugate gradient method and a finite difference method are used to solve the variational problem. Some numerical examples are also provided to show the efficiency of the proposed method. [Copyright &y& Elsevier]

Abstract: Recently, Hager and Zhang (2005) proposed a new conjugate gradient method which generates sufficient descent direction , this property is independent of the line search used. In this paper, we take a modification of this method, such that the sufficient descent direction satisfies , this property is also independent of the line search used. Under appropriate conditions, we prove that the proposed method is globally convergent. Moreover, we give a sufficient condition for the global convergence of the proposed general method. The numerical results show that the proposed method is efficient. [Copyright &y& Elsevier]

Abstract: We present a new local-in-time discrete adjoint-based methodology for solving design optimization problems arising in unsteady aerodynamic applications. The new methodology circumvents storage requirements associated with the straightforward implementation of a global adjoint-based optimization method that stores the entire flow solution history for all time levels. This storage cost may quickly become prohibitive for large-scale applications. The key idea of the local-in-time method is to divide the entire time interval into several subintervals and to approximate the solution of the unsteady adjoint equations and the sensitivity derivative as a combination of the corresponding local quantities computed on each time subinterval. Since each subinterval contains relatively few time levels, the storage cost of the local-in-time method is much lower than that of the global methods, thus making the time-dependent adjoint optimization feasible for practical applications. Another attractive feature of the new technique is that the converged solution obtained with the local-in-time method is a local extremum of the original optimization problem. The new method carries no computational overhead as compared with the global implementation of adjoint-based methods. The paper presents a detailed comparison of the global- and local-in-time adjoint-based methods for design optimization problems governed by the unsteady compressible 2-D Euler equations. [Copyright &y& Elsevier]

We develop a sufficient descent method for solving large-scale unconstrained optimization problems. At each iteration, the search direction is a linear combination of the gradient at the current and the previous steps. An attractive property of this method is that the generated directions are always descent. Under some appropriate conditions, we show that the proposed method converges globally. Numerical experiments on some unconstrained minimization problems from CUTEr library are reported, which illustrate that the proposed method is promising. [ABSTRACT FROM AUTHOR]

Abstract: A methodology is proposed for the efficient determination of gradient information, when performing gradient based optimisation of an off-road vehicle’s suspension system. The methodology is applied to a computationally expensive, non-linear vehicle model, that exhibits severe numerical noise. A recreational off-road vehicle is modelled in MSC.ADAMS, and coupled to MATLAB for the execution of the optimisation. The successive approximation method, Dynamic-Q, is used for the optimisation of the spring and damper characteristics. Optimisation is performed for both ride comfort and handling. The determination of the objective function value is performed using computationally expensive numerical simulations. This paper proposes a non-linear pitch-plane model, to be used for the gradient information, when optimising ride comfort. When optimising for handling, a non-linear four wheel model, that includes roll, is used. The gradients of the objective function and constraint functions are obtained through the use of central finite differences, within Dynamic-Q, via numerical simulation using the proposed simplified models. The importance of correctly scaling these simplified models is emphasised. The models are validated against experimental results. The simplified vehicle models exhibit significantly less numerical noise than the full vehicle simulation model, and solve in significantly less computational time. [Copyright &y& Elsevier]

Abstract: In this paper we propose a fundamentally different conjugate gradient method, in which the well-known parameter is computed by an approximation of the Hessian/vector product through finite differences. For search direction computation, the method uses a forward difference approximation to the Hessian/vector product in combination with a careful choice of the finite difference interval. For the step length computation we suggest an acceleration scheme able to improve the efficiency of the algorithm. Under common assumptions, the method is proved to be globally convergent. It is shown that for uniformly convex functions the convergence of the accelerated algorithm is still linear, but the reduction in function values is significantly improved. Numerical comparisons with conjugate gradient algorithms including CONMIN by Shanno and Phua [D.F. Shanno, K.H. Phua, Algorithm 500, minimization of unconstrained multivariate functions, ACM Trans. Math. Softw. 2 (1976) 87–94], SCALCG by Andrei [N. Andrei, Scaled conjugate gradient algorithms for unconstrained optimization, Comput. Optim. Appl. 38 (2007) 401–416; N. Andrei, Scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Optim. Methods Softw. 22 (2007) 561–571; N. Andrei, A scaled BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Appl. Math. Lett. 20 (2007) 645–650], and new conjugacy condition and related new conjugate gradient by Li, Tang and Wei [G. Li, C. Tang, Z. Wei, New conjugacy condition and related new conjugate gradient methods for unconstrained optimization, J. Comput. Appl. Math. 202 (2007) 523–539] or truncated Newton TN by Nash [S.G. Nash, Preconditioning of truncated-Newton methods, SIAM J. on Scientific and Statistical Computing 6 (1985) 599–616] using a set of 750 unconstrained optimization test problems show that the suggested algorithm outperforms these conjugate gradient algorithms as well as TN. [Copyright &y& Elsevier]

Abstract: Conjugate gradient methods are important for large-scale unconstrained optimization. This paper proposes an acceleration of these methods using a modification of steplength. The idea is to modify in a multiplicative manner the steplength α k , computed by Wolfe line search conditions, by means of a positive parameter η k , in such a way to improve the behavior of the classical conjugate gradient algorithms. It is shown that for uniformly convex functions the convergence of the accelerated algorithm is still linear, but the reduction in function values is significantly improved. Numerical comparisons with some conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that the accelerated computational scheme outperform the corresponding conjugate gradient algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, a novel learning strategy for radial basis function networks (RBFN) is proposed. By adjusting the parameters of the hidden layer, including the RBF centers and widths, the weights of the output layer are adapted by local optimization methods. A new local optimization algorithm based on a combination of the gradient and Newton methods is introduced. The efficiency of some local optimization methods to update the weights of RBFN is studied in solving systems of nonlinear integral equations. [Copyright &y& Elsevier]

Abstract: In this paper we develop a new class of conjugate gradient methods for unconstrained optimization problems. A new nonmonotone line search technique is proposed to guarantee the global convergence of these conjugate gradient methods under some mild conditions. In particular, Polak–Ribiére–Polyak and Liu–Storey conjugate gradient methods are special cases of the new class of conjugate gradient methods. By estimating the local Lipschitz constant of the derivative of objective functions, we can find an adequate step size and substantially decrease the function evaluations at each iteration. Numerical results show that these new conjugate gradient methods are effective in minimizing large-scale non-convex non-quadratic functions. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations. They come from two modified conjugate gradient methods [W.Y. Cheng, A two term PRP based descent Method, Numer. Funct. Anal. Optim. 28 (2007) 1217–1230; L. Zhang, W.J. Zhou, D.H. Li, A descent modified Polak–Ribiére–Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal. 26 (2006) 629–640] recently proposed for unconstrained optimization problems. Under appropriate conditions, the global convergence of the proposed method is established. Preliminary numerical results show that the proposed method is promising. [Copyright &y& Elsevier]

Two Armijo-type line searches are proposed in this paper for nonlinear conjugate gradient methods. The two Armijo-type line searches are shown to guarantee the global convergence of the DY method for the unconstrained minimization of nonconvex differentiable functions. Further, if the function is strictly convex, the two Armijo-type line searches and another Armijo-type line search are also shown to guarantee the convergence of the DY method. [ABSTRACT FROM AUTHOR]

Three hybrid methods for solving unconstrained optimization problems are introduced. These methods are defined using proper combinations of the search directions and included parameters in conjugate gradient and quasi-Newton methods. The convergence of proposed methods with the underlying backtracking line search is analyzed for general objective functions and particularly for uniformly convex objective functions. Numerical experiments show the superiority of the proposed methods with respect to some existing methods in view of the Dolan and Moré’s performance profile. [ABSTRACT FROM AUTHOR]

We describe an algorithm for minimizing convex, not necessarily smooth, functions of several variables, based on a descent direction finding procedure that inherits some characteristics both of standard bundle method and of Wolfe's conjugate subgradient method. This is obtained by allowing appropriate upward shifting of the affine approximations of the objective function which contribute to the classic definition of the cutting plane function. The algorithm embeds a proximity control strategy. Finite termination is proved at a point satisfying an approximate optimality condition and some numerical results are provided. [ABSTRACT FROM AUTHOR]

This article presents a modified quadratic hybridization of the Polak--Ribière--Polyak and Fletcher-Reeves conjugate gradient method for solving uncon- strained optimization problems. Global convergence, with the strong Wolfe line search conditions, of the proposed quadratic hybrid conjugate gradient method is established. The new method is tested on a number of benchmark problems that have been extensively used in the literature and numerical results show the competitiveness of the new hybrid method. [ABSTRACT FROM AUTHOR]

New first-order methods are introduced for solving convex optimization problems from a fairly broad class. For composite optimization problems with an inexact stochastic oracle, a stochastic intermediate gradient method is proposed that allows using an arbitrary norm in the space of variables and a prox-function. The mean rate of convergence of this method and the probability of large deviations from this rate are estimated. For problems with a strongly convex objective function, a modification of this method is proposed and its rate of convergence is estimated. The resulting estimates coincide, up to a multiplicative constant, with lower complexity bounds for the class of composite optimization problems with an inexact stochastic oracle and for all usually considered subclasses of this class. [ABSTRACT FROM AUTHOR]

In this article, we present an improved three-term conjugate gradient algorithm for large-scale unconstrained optimization. The search directions in the developed algorithm are proved to satisfy an approximate secant equation as well as the Dai-Liao’s conjugacy condition. With the standard Wolfe line search and the restart strategy, global convergence of the algorithm is established under mild conditions. By implementing the algorithm to solve 75 benchmark test problems with dimensions from 1000 to 10,000, the obtained numerical results indicate that the algorithm outperforms the state-of-the-art algorithms available in the literature. It costs less CPU time and smaller number of iterations in solving the large-scale unconstrained optimization. [ABSTRACT FROM AUTHOR]

In order to achieve a theoretically effective and numerically efficient method for solving large-scale unconstrained optimization problems, a hybridization of the Fletcher-Reeves and Polak-Ribière-Polyak conjugate gradient methods is proposed. In the method, the hybridization parameter is computed such that the generated search directions approach to the search directions of the efficient three-term conjugate gradient method proposed by Zhang et al., to the extent possible. Under proper conditions, global convergence of the method is established without convexity assumption on the objective function. The method is numerically compared with the three-term conjugate gradient method proposed by Zhang et al. and a modified version of the Polak-Ribière-Polyak method suggested by Gilbert and Nocedal. Comparative testing results demonstrating the efficiency of the proposed method are reported. [ABSTRACT FROM AUTHOR]

A three-term conjugate gradient algorithm for large-scale unconstrained optimization using subspace minimizing technique is presented. In this algorithm the search directions are computed by minimizing the quadratic approximation of the objective function in a subspace spanned by the vectors: − g, s and y. The search direction is considered as: d = − g + a s + b y, where the scalars a and b are determined by minimization the affine quadratic approximate of the objective function. The step-lengths are determined by the Wolfe line search conditions. We prove that the search directions are descent and satisfy the Dai-Liao conjugacy condition. The suggested algorithm is of three-term conjugate gradient type, for which both the descent and the conjugacy conditions are guaranteed. It is shown that, for uniformly convex functions, the directions generated by the algorithm are bounded above, i.e. the algorithm is convergent. The numerical experiments, for a set of 750 unconstrained optimization test problems, show that this new algorithm substantially outperforms the known Hestenes and Stiefel, Dai and Liao, Dai and Yuan and Polak, Ribiére and Poliak conjugate gradient algorithms, as well as the limited memory quasi-Newton method L-BFGS and the discrete truncated-Newton method TN. [ABSTRACT FROM AUTHOR]

We present an algorithm, partitioning group correction (PGC) algorithm based on trust region and conjugate gradient method, for large-scale sparse unconstrained optimization. In large sparse optimization, computing the whole Hessian matrix and solving the Newton-like equations at each iteration can be considerably expensive when a trust region method is adopted. The method depends on a symmetric consistent partition of the columns of the Hessian matrix and an inaccurate solution to the Newton-like equations by conjugate gradient method. And we allow that the current direction exceeds the trust region bound if it is a good descent direction. Besides, we studies a method dealing with some sparse matrices having a dense structure part. Some good convergence properties are kept and we contrast the computational behavior of our method with that of other algorithms. Our numerical tests show that the algorithm is promising and quite effective, and that its performance is comparable to or better than that of other algorithms available. [ABSTRACT FROM AUTHOR]

A class of affine-scaling interior-point trust region methods with line search for bound constrained optimization problems is presented in this article. The method is globally convergent under the standard assumptions and is locally q-superlinear or q-quadratic convergent in the case where the strong second order sufficient optimality conditions at the solution are satisfied, but the strict complementarity condition is violated. Numerical experiments show that the method is efficient. [ABSTRACT FROM AUTHOR]

A hybrid method combining the FR conjugate gradient method and the WYL conjugate gradient method is proposed for unconstrained optimization problems. The presented method possesses the sufficient descent property under the strong Wolfe-Powell (SWP) line search rule relaxing the parameter σ < 1. Under the suitable conditions, the global convergence with the SWP line search rule and the weak Wolfe-Powell (WWP) line search rule is established for nonconvex function. Numerical results show that this method is better than the FR method and the WYL method. [ABSTRACT FROM AUTHOR]

Subgradient methods for nondifferentiable optimization benefit from deflection, i.e., defining the search direction as a combination of the previous direction and the current subgradient. In the constrained case they also benefit from projection of the search direction onto the feasible set prior to computing the steplength, that is, from the use of conditional subgradient techniques. However, combining the two techniques is not straightforward, especially if an inexact oracle is available which can only compute approximate function values and subgradients. We present a convergence analysis of several different variants, both conceptual and implementable, of approximate conditional deflected subgradient methods. Our analysis extends the available results in the literature by using the main stepsize rules presented so far, while allowing deflection in a more flexible way. Furthermore, to allow for (diminishing/square summable) rules where the stepsize is tightly controlled a priori, we propose a new class of deflection-restricted approaches where it is the deflection parameter, rather than the stepsize, which is dynamically adjusted using the "target value" of the optimization sequence. For both Polyak-type and diminishing/square summable stepsizes, we propose a "correction" of the standard formula which shows that, in the inexact case, knowledge about the error computed by the oracle (which is available in several practical applications) can be exploited in order to strengthen the convergence properties of the method. The analysis allows for several variants of the algorithm; at least one of them is likely to show numerical performances similar to these of "heavy ball" subgradient methods, popular within backpropagation approaches to train neural networks, while possessing stronger convergence properties. [ABSTRACT FROM AUTHOR]

We discuss the use of preconditioned conjugate gradients (CG) method for solving the reduced KKT systems arising in interior point algorithms for linear programming. The (indefinite) augmented system form of this linear system has a number of advantages, notably a higher degree of sparsity than the (positive definite) normal equations form. Therefore, we use the CG method to solve the augmented system and look for a suitable preconditioner. An explicit null space representation of linear constraints is constructed by using a nonsingular basis matrix identified from an estimate of the optimal partition in the linear program. This is achieved by means of recently developed efficient basis matrix factorisation techniques which exploit hyper-sparsity and are used in implementations of the revised simplex method. The approach has been implemented within the HOPDM interior point solver and applied to medium and large-scale problems from public domain test collections. Computational experience is encouraging. [ABSTRACT FROM AUTHOR]

A mixed-type dual for a nonsmooth multiobjective optimization problem with inequality and equality constraints is formulated. We obtain weak and strong duality theorems for a mixed-type dual without requiring the regularity assumptions and the nonnegativeness of the Lagrange multipliers associated to the equality constraints. We apply also a nonsmooth constraint qualification for multiobjective programming to establish strong duality results. In this case, our constraint qualification assures the existence of positive Lagrange multipliers associated with the vector-valued objective function. [ABSTRACT FROM AUTHOR]

Conjugate gradient methods are efficient methods for minimizing differentiable objective functions in large dimension spaces. However, converging line search strategies are usually not easy to choose, nor to implement. Sun and colleagues (Ann. Oper. Res. 103:161-173, 2001; J. Comput. Appl.Math. 146:37-45, 2002) introduced a simple stepsize formula. However, the associated convergence domain happens to be overrestrictive, since it precludes the optimal stepsize in the convex quadratic case. Here, we identify this stepsize formula with one iteration of the Weiszfeld algorithm in the scalar case. More generally, we propose to make use of a finite number of iterates of such an algorithm to compute the stepsize. In this framework, we establish a new convergence domain, that incorporates the optimal stepsize in the convex quadratic case. [ABSTRACT FROM AUTHOR]

Generally, global convergence of the conjugate gradient methods for unconstrained optimization problems needs Wolfe line search or strong Wolfe line search. In this article, we propose a cautious DY conjugate gradient method and prove that this method with Armijo line search converges globally if the objective function has Lipschitz continuous gradients. We also present some preliminary numerical results to show the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

This article deals with minimizing quadratic functions with a special form of quadratic constraints that arise in 3D contact problems of linear elasticity with isotropic friction [Haslinger, J., Kucera, R. and Dostál, Z., 2004, An algorithm for the numerical realization of 3D contact problems with Coulomb friction. Journal of Computational and Applied Mathematics, 164/165, 387-408.]. The proposed algorithm combines the active set method with the conjugate gradient method. Its general scheme is similar to the algorithms of Polyak's type that solve the quadratic programming problems with simple bounds. As the algorithm does not terminate in a finite number of steps, the convergence is proved. The implementation uses an adaptive precision control of the conjugate gradient loops. Numerical experiments demonstrate the computational efficiency of the method. [ABSTRACT FROM AUTHOR]