A hybrid conjugate gradient method based on a quadratic relaxation of the Dai–Yuan hybrid conjugate gradient parameter

To take advantage of the attractive features of the Hestenes–Stiefel and Dai–Yuan conjugate gradient (CG) methods, we suggest a hybridization of these methods using a quadratic relaxation of a hybrid CG parameter proposed by Dai and Yuan. In the proposed method, the hybridization parameter is computed based on a conjugacy condition. Under proper conditions, we show that our method is globally convergent for uniformly convex functions. We give a numerical comparison of the implementations of our method and two efficient hybrid CG methods proposed by Dai and Yuan using a set of unconstrained optimization test problems from the CUTEr collection. Numerical results show the efficiency of the proposed hybrid CG method in the sense of the performance profile introduced by Dolan and Moré.     

Comments on “A hybrid conjugate gradient method based on a quadratic relaxation of the Dai-Yuan hybrid conjugate gradient parameter”

In this note, we show that the assumption condition (3.3) in Theorem 3.2 of Babaie-Kafaki can be deleted. As mentioned in Babaie-Kafaki, it is not appropriate to consider condition (3.3) as an assumption. Throughout, we use the same notations and equation numbers as in Babaie-Kafaki.     

The Dai–Liao nonlinear conjugate gradient method with optimal parameter choices

Minimizing two different upper bounds of the matrix which generates search directions of the nonlinear conjugate gradient method proposed by Dai and Liao, two modified conjugate gradient methods are proposed. Under proper conditions, it is briefly shown that the methods are globally convergent when the line search fulfills the strong Wolfe conditions. Numerical comparisons between the implementations of the proposed methods and the conjugate gradient methods proposed by Hager and Zhang, and Dai and Kou, are made on a set of unconstrained optimization test problems of the CUTEr collection. The results show the efficiency of the proposed methods in the sense of the performance profile introduced by Dolan and Moré.     

A class of adaptive Dai–Liao conjugate gradient methods based on the scaled memoryless BFGS update

Minimizing the distance between search direction matrix of the Dai–Liao method and the scaled memoryless BFGS update in the Frobenius norm, and using Powell’s nonnegative restriction of the conjugate gradient parameters, a one-parameter class of nonlinear conjugate gradient methods is proposed. Then, a brief global convergence analysis is made with and without convexity assumption on the objective function. Preliminary numerical results are reported; they demonstrate a proper choice for the parameter of the proposed class of conjugate gradient methods may lead to promising numerical performance.     

On optimality of two adaptive choices for the parameter of Dai–Liao method

Orthonormal matrices are a class of well-conditioned matrices with the least spectral condition number. Here, at first it is shown that a recently proposed choice for parameter of the Dai–Liao nonlinear conjugate gradient method makes the search direction matrix as close as possible to an orthonormal matrix in the Frobenius norm. Then, conducting a brief singular value analysis, it is shown that another recently proposed choice for the Dai–Liao parameter improves spectral condition number of the search direction matrix. Thus, theoretical justifications of the two choices for the Dai–Liao parameter are enhanced. Finally, some comparative numerical results are reported.     

A modified three–term conjugate gradient method with sufficient descent property

A hybridization of the three–term conjugate gradient method proposed by Zhang et al. and the nonlinear conjugate gradient method proposed by Polak and Ribi`ere, and Polyak is suggested. Based on an eigenvalue analysis, it is shown that search directions of the proposed method satisfy the sufficient descent condition, independent of the line search and the objective function convexity. Global convergence of the method is established under an Armijo–type line search condition. Numerical experiments show practical efficiency of the proposed method.     

Comment on “A new three-term conjugate gradient method for unconstrained problem”

Here, necessary corrections on computing an optimal parameter of the TTDES method of Andrei (Numer. Math. 68(2), 305–321 2015) are stated in brief. Throughout, we use the same notations and equation numbers as in N.Andrei.     

A new Liu–Storey type nonlinear conjugate gradient method for unconstrained optimization problems

Although the Liu–Storey (LS) nonlinear conjugate gradient method has a similar structure as the well-known Polak–Ribière–Polyak (PRP) and Hestenes–Stiefel (HS) methods, research about this method is very rare. In this paper, based on the memoryless BFGS quasi-Newton method, we propose a new LS type method, which converges globally for general functions with the Grippo–Lucidi line search. Moreover, we modify this new LS method such that the modified scheme is globally convergent for nonconvex minimization if the strong Wolfe line search is used. Numerical results are also reported.     

A prediction–correction-based primal–dual hybrid gradient method for linearly constrained convex minimization

Numerical Algorithms - The primal–dual hybrid gradient (PDHG) method has been widely used for solving saddle point problems emerged in imaging processing. In particular, PDHG can be used to...     

A Levenberg–Marquardt method based on Sobolev gradients

We extend the theory of Sobolev gradients to include variable metric methods, such as Newton’s method and the Levenberg–Marquardt method, as gradient descent iterations associated with stepwise variable inner products. In particular, we obtain existence, uniqueness, and asymptotic convergence results for a gradient flow based on a variable inner product.     

Long-time behavior of solutions to Hamilton–Jacobi equations with quadratic gradient term

We study a rate of convergence appearing in the long-time behavior of viscosity solutions of the Cauchy problem for the Hamilton–Jacobi equation

A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron–Frobenius theory

For any positive integer parameters a and b, Gurvich recently introduced a generalization mex _b of the standard minimum excludant mex = mex₁, along with a game NIM(a, b) that extends further Fraenkel’s NIM = NIM(a, 1), which in its turn is a generalization of the classical Wythoff NIM = NIM(1, 1). It was shown that P-positions (the kernel) of NIM(a, b) are given by the following recursion: $$x_n = {\rm mex}_b(\{x_i, y_i \;|\; 0 \leq i < n\}), \;\; y_n = x_n + an; \;\; n \geq 0,$$ and conjectured that for all a, b the limits ?(a, b) = x _n (a, b)/n exist and are irrational algebraic numbers. In this paper we prove that showing that ${\ell(a,b) = \frac{a}{r-1}}$ , where r > 1 is the Perron root of the polynomial $$P(z) = z^{b+1} - z - 1 - \sum_{i=1}^{a-1} z^{\lceil ib/a \rceil},$$ whenever a and b are coprime; furthermore, it is known that ?(ka, kb) = k?(a, b). In particular, ${\ell(a, 1) = \alpha_a = \frac{1}{2} (2 - a + \sqrt{a^2 + 4})}$ . In 1982, Fraenkel introduced the game NIM(a) = NIM(a, 1), obtained the above recursion and solved it explicitly getting ${x_n = \lfloor \alpha_a n \rfloor, \; y_n = x_n + an = \lfloor (\alpha_a + a) n \rfloor}$ . Here we provide a polynomial time algorithm based on the Perron–Frobenius theory solving game NIM(a, b), although we have no explicit formula for its kernel.     

On application of Euler’s differential method to a continued fraction depending on parameter

In this paper we apply Euler’s differential method, which was not used by mathematicians for a long time, to derive a new formula for a certain kind irregular continued fraction depending on a parameter. This formula is in the form of the ratio of two integrals. In case of integer values of the parameter, the formula reduces to the ratio of two finite sums. Asymptotic behavior of this continued fraction is investigated numerically and it is shown that it increases in the same rate as the root function.     

Contraction behaviour of iteration–discretization based on gradient type projections

There is a wide range of iterative methods in infinite dimensional spaces to treat variational equations or variational inequalities. As a rule, computational handling of problems in infinite dimensional spaces requires some discretization. Any useful discretization of the original problem leads to families of problems over finite dimensional spaces. Thus, two infinite techniques, namely discretization and iteration are embedded into each other. In the present paper, the behaviour of truncated iterative methods is studied, where at each discretization level only a finite number of steps is performed. In our study no accuracy dependent a posteriori stopping criterion is used. From an algorithmic point of view, the considered methods are of iteration–discretization type. The major aim here is to provide the convergence analysis for the introduced abstract iteration–discretization methods. A special emphasis is given on algorithms for the treatment of variational inequalities with strongly monotone operators over fixed point sets of quasi-nonexpansive mappings.     

Addendum to the paper “on a theorem of Miranda”

An existence theorem is proved for closed convex surfaces whose principal radii of curvature regarded as functions of the unit normal vectorn satisfy the equation

Inexact inner–outer Golub–Kahan bidiagonalization method: A relaxation strategy

We study an inexact inner–outer generalized Golub–Kahan algorithm for the solution of saddle-point problems with a two-times-two block structure. In each outer iteration, an inner system has to be solved which in theory has to be done exactly. Whenever the system is getting large, an inner exact solver is, however, no longer efficient or even feasible and iterative methods must be used. We focus this article on a numerical study showing the influence of the accuracy of an inner iterative solution on the accuracy of the solution of the block system. Emphasis is further given on reducing the computational cost, which is defined as the total number of inner iterations. We develop relaxation techniques intended to dynamically change the inner tolerance for each outer iteration to further minimize the total number of inner iterations. We illustrate our findings on a Stokes problem and validate them on a mixed formulation of the Poisson problem.     

A fourth-order Runge–Kutta method based on BDF-type Chebyshev approximations

In this paper we consider a new fourth-order method of BDF-type for solving stiff initial-value problems, based on the interval approximation of the true solution by truncated Chebyshev series. It is shown that the method may be formulated in an equivalent way as a Runge–Kutta method having stage order four. The method thus obtained have good properties relatives to stability including an unbounded stability domain and large α$\alpha$-value concerning A(α)$A(\alpha )$-stability. A strategy for changing the step size, based on a pair of methods in a similar way to the embedding pair in the Runge–Kutta schemes, is presented. The numerical examples reveals that this method is very promising when it is used for solving stiff initial-value problems.