共查询到20条相似文献,搜索用时 0 毫秒
1.
Ya-xiang Yuan 《Mathematical Programming》2010,123(2):339-343
This short note gives the sharp bound for the Q-linear convergence rate of the iterates generated by the steepest descent
method with exact line searches when the objective function is strictly convex quadratic. 相似文献
2.
The aim of this paper is to establish the local convergence of the steepest descent method for C1-functionals defined on an infinite-dimensional Hilbert space H, under a Palais–Smale-type condition. The functionals f under consideration are also assumed to have a locally Lipschitz continuous gradient operator f. Our approach is based on the solutions of the ordinary differential equation . 相似文献
3.
A method of truncated codifferential descent for minimizing continuously codifferentiable functions is suggested. The convergence of the method is studied. Results of numerical experiments are presented. Application of the suggested method for the solution of some problems of cluster analysis are discussed. In numerical experiments Wisconsin Diagnostic Breast Cancer database was used. 相似文献
4.
A descent modified Polak-Ribiere-Polyak conjugate gradient method and its global convergence 总被引:3,自引:0,他引:3
** Email: zl606{at}tom.com*** Corresponding author. Email: weijunzhou{at}126.com**** Email: dhli{at}hnu.cn In this paper, we propose a modified PolakRibièrePolyak(PRP) conjugate gradient method. An attractive property of theproposed method is that the direction generated by the methodis always a descent direction for the objective function. Thisproperty is independent of the line search used. Moreover, ifexact line search is used, the method reduces to the ordinaryPRP method. Under appropriate conditions, we show that the modifiedPRP method with Armijo-type line search is globally convergent.We also present extensive preliminary numerical experimentsto show the efficiency of the proposed method. 相似文献
5.
On the convergence of the coordinate descent method for convex differentiable minimization 总被引:3,自引:0,他引:3
The coordinate descent method enjoys a long history in convex differentiable minimization. Surprisingly, very little is known about the convergence of the iterates generated by this method. Convergence typically requires restrictive assumptions such as that the cost function has bounded level sets and is in some sense strictly convex. In a recent work, Luo and Tseng showed that the iterates are convergent for the symmetric monotone linear complementarity problem, for which the cost function is convex quadratic, but not necessarily strictly convex, and does not necessarily have bounded level sets. In this paper, we extend these results to problems for which the cost function is the composition of an affine mapping with a strictly convex function which is twice differentiable in its effective domain. In addition, we show that the convergence is at least linear. As a consequence of this result, we obtain, for the first time, that the dual iterates generated by a number of existing methods for matrix balancing and entropy optimization are linearly convergent.This work was partially supported by the U.S. Army Research Office, Contract No. DAAL03-86-K-0171, by the National Science Foundation, Grant No. ECS-8519058, and by the Science and Engineering Research Board of McMaster University. 相似文献
6.
Zaid M. Odibat 《Applied mathematics and computation》2010,217(2):782-789
In this study, a reliable approach for convergence of the homotopy analysis method when applied to nonlinear problems is discussed. First, we present an alternative framework of the method which can be used simply and effectively to handle nonlinear problems. Then, mainly, we address the sufficient condition for convergence of the method. The convergence analysis is reliable enough to estimate the maximum absolute truncated error of the homotopy series solution. The analysis is illustrated by investigating the convergence results for some nonlinear differential equations. The study highlights the power of the method. 相似文献
7.
J. C. Bezdek R. J. Hathaway R. E. Howard C. A. Wilson M. P. Windham 《Journal of Optimization Theory and Applications》1987,54(3):471-477
LetF(x,y) be a function of the vector variablesxR
n
andyR
m
. One possible scheme for minimizingF(x,y) is to successively alternate minimizations in one vector variable while holding the other fixed. Local convergence analysis is done for this vector (grouped variable) version of coordinate descent, and assuming certain regularity conditions, it is shown that such an approach is locally convergent to a minimizer and that the rate of convergence in each vector variable is linear. Examples where the algorithm is useful in clustering and mixture density decomposition are given, and global convergence properties are briefly discussed.This research was supported in part by NSF Grant No. IST-84-07860. The authors are indebted to Professor R. A. Tapia for his help in improving this paper. 相似文献
8.
Kimon Fountoulakis Rachael Tappenden 《Computational Optimization and Applications》2018,70(2):351-394
We present a novel randomized block coordinate descent method for the minimization of a convex composite objective function. The method uses (approximate) partial second-order (curvature) information, so that the algorithm performance is more robust when applied to highly nonseparable or ill conditioned problems. We call the method Flexible Coordinate Descent (FCD). At each iteration of FCD, a block of coordinates is sampled randomly, a quadratic model is formed about that block and the model is minimized approximately/inexactly to determine the search direction. An inexpensive line search is then employed to ensure a monotonic decrease in the objective function and acceptance of large step sizes. We present several high probability iteration complexity results to show that convergence of FCD is guaranteed theoretically. Finally, we present numerical results on large-scale problems to demonstrate the practical performance of the method. 相似文献
9.
Heath Emerson 《Topology》2007,46(2):185-209
Let G be a torsion-free discrete group with a finite-dimensional classifying space BG. We show that G has a dual-Dirac morphism if and only if a certain coarse (co-)assembly map is an isomorphism. Hence the existence of a dual-Dirac morphism for such groups is a metric, that is, coarse, invariant. We get results for groups with torsion as well. 相似文献
10.
Alex Orden 《Mathematical Programming》1980,19(1):3-13
Probability distributions are assumed for the coefficients in simplex tableaus. A probability of success in one simplex iteration is then derived; for example, the probability of a tableau which satisfies the criteria for optimality except in one row becoming fully optimal in one iteration. Such results are expressed in terms of tableau size parameters. 相似文献
11.
The main goal of this paper is to develop accuracy estimates for stochastic programming problems by employing stochastic approximation (SA) type algorithms. To this end we show that while running a Mirror Descent Stochastic Approximation procedure one can compute, with a small additional effort, lower and upper statistical bounds for the optimal objective value. We demonstrate that for a certain class of convex stochastic programs these bounds are comparable in quality with similar bounds computed by the sample average approximation method, while their computational cost is considerably smaller. 相似文献
12.
A method for accelerating linear iterations in a Banach space is studied as a linear iterative method in an augmented space, and sufficient conditions for convergence are derived in the general case and in ordered Banach spaces. An acceleration of convergence takes place if an auxiliary functional is chosen sufficiently close to a dual eigenvector associated with a dominant simple eigenvalue of the iteration operator; in this case, the influence of this eigenvalue on the asymptotic rate of convergence is eliminated. Quantitative estimates and bounds on convergence are given. 相似文献
13.
Roger Fletcher 《Mathematical Programming》2012,135(1-2):413-436
The possibilities inherent in steepest descent methods have been considerably amplified by the introduction of the Barzilai–Borwein choice of step-size, and other related ideas. These methods have proved to be competitive with conjugate gradient methods for the minimization of large dimension unconstrained minimization problems. This paper suggests a method which is able to take advantage of the availability of a few additional ‘long’ vectors of storage to achieve a significant improvement in performance, both for quadratic and non-quadratic objective functions. It makes use of certain Ritz values related to the Lanczos process (Lanczos in J Res Nat Bur Stand 45:255–282, 1950). Some underlying theory is provided, and numerical evidence is set out showing that the new method provides a competitive and more simple alternative to the state of the art l-BFGS limited memory method. 相似文献
14.
Error bounds and convergence analysis of feasible descent methods: a general approach 总被引:4,自引:0,他引:4
We survey and extend a general approach to analyzing the convergence and the rate of convergence of feasible descent methods that does not require any nondegeneracy assumption on the problem. This approach is based on a certain error bound for estimating the distance to the solution set and is applicable to a broad class of methods.The research of the first author is supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. OPG0090391, and the research of the second author is supported by the National Science Foundation, Grant No. CCR-9103804. 相似文献
15.
The boundary node method (BNM) exploits the dimensionality of the boundary integral equation (BIE) and the meshless attribute of the moving least-square (MLS) approximations. However, since MLS shape functions lack the property of a delta function, it is difficult to exactly satisfy boundary conditions in BNM. Besides, the system matrices of BNM are non-symmetric. 相似文献
16.
Christian Malivert 《Journal of Mathematical Analysis and Applications》1982,88(2):610-631
A descent method on a closed set X of a Hilbert space, adapted to the multi-objective optimization, is presented. After solving a differential inclusion, the limit points of the solutions are used to characterize a critical set, which contains the set of Pareto optima. Under suitable assumptions existence of a Pareto optimum is proved. Then the Lusternik-Schnirelman theory is generalized to this framework and the critical set is related to the topological properties of X. 相似文献
17.
A sorted partial jacobi method and its convergence analysis 总被引:1,自引:0,他引:1
Jacobi methods for computing the eigendecomposition of a class of so-called low-rank-plus-shift symmetric matrices are investigated. An order-of-magnitude reduction in the computational complexity can be achieved for this special class of matrices by terminating the Jacobi sweep early in a cyclic ordering. It is proved that these partial sweeps combined with sorting the diagonals still deliver quadratic convergence. It is also shown that useful results can still be obtained even if the low-rank-plus-shift structure only holds approximately. 相似文献
18.
L. Wittmeyer-Koch 《BIT Numerical Mathematics》1968,8(4):328-342
A procedure is developed for the calculation of a best Chebyshev approximation among linear combinations of given continuous functions
0,
1,...,
N
, to a continuous function in a compact interval. The procedure uses a descent method to minimize the Chebyshev norm of the error function. In some cases the choice of direction of descent resembles an idea developed by Zuhovickii for discrete approximations. However, in general, a different way to calculate this direction is used. This choice of direction, made in an adaptive manner, makes it possible to work with an easily determined estimate of the stepsize.Even with very bad initial values the given method converges. It is easily extended to the case when the approximating functions do not fulfil the Haar condition. The effectiveness is illustrated with numerical examples. 相似文献
19.
20.
We obtain exact (unimprovable) estimates for the rate of convergence of the s-step method of steepest descent for finding the least (greatest) eigenvalue of a linear bounded self-adjoint operator in a Hilbert space. 相似文献