This paper provides a gradient search algorithm for finding the maximal visible area polygon (VAP) viewed by an interior point in a simple polygon P. The algorithm is based on a natural partition of P into convex sets...This paper provides a gradient search algorithm for finding the maximal visible area polygon (VAP) viewed by an interior point in a simple polygon P. The algorithm is based on a natural partition of P into convex sets, such that each element of the partition is associated with a unique analytical form of the area function. We call this partition a back diagonal partition of P. Our maximal VAP algorithm converges in a finite number of steps, and is polynomial with a complexity of , for a simple polygon P with n vertices, and r reflex vertices. We use the maximal VAP algorithm as a basis for a greedy heuristic for the well known guardhouse problem with a computation complexity of .展开更多
The Runge-Kutta optimiser(RUN)algorithm,renowned for its powerful optimisation capabilities,faces challenges in dealing with increasing complexity in real-world problems.Specifically,it shows deficiencies in terms of ...The Runge-Kutta optimiser(RUN)algorithm,renowned for its powerful optimisation capabilities,faces challenges in dealing with increasing complexity in real-world problems.Specifically,it shows deficiencies in terms of limited local exploration capabilities and less precise solutions.Therefore,this research aims to integrate the topological search(TS)mechanism with the gradient search rule(GSR)into the framework of RUN,introducing an enhanced algorithm called TGRUN to improve the performance of the original algorithm.The TS mechanism employs a circular topological scheme to conduct a thorough exploration of solution regions surrounding each solution,enabling a careful examination of valuable solution areas and enhancing the algorithm’s effectiveness in local exploration.To prevent the algorithm from becoming trapped in local optima,the GSR also integrates gradient descent principles to direct the algorithm in a wider investigation of the global solution space.This study conducted a serious of experiments on the IEEE CEC2017 comprehensive benchmark function to assess the enhanced effectiveness of TGRUN.Additionally,the evaluation includes real-world engineering design and feature selection problems serving as an additional test for assessing the optimisation capabilities of the algorithm.The validation outcomes indicate a significant improvement in the optimisation capabilities and solution accuracy of TGRUN.展开更多
Motion estimation is an important part of the MPEG- 4 encoder, due to its significant impact on the bit rate and the output quality of the encoder sequence. Unfortunately this feature takes a significant part of the e...Motion estimation is an important part of the MPEG- 4 encoder, due to its significant impact on the bit rate and the output quality of the encoder sequence. Unfortunately this feature takes a significant part of the encoding time especially when the straightforward full search(FS) algorithm is used. In this paper, a new algorithm named diamond block based gradient descent search (DBBGDS) algorithm, which is significantly faster than FS and gives similar quality of the output sequence, is proposed. At the same time, some other algorithms, such as three step search (TSS), improved three step search (ITSS), new three step search (NTSS), four step search (4SS), cellular search (CS) , diamond search (DS) and block based gradient descent search (BBGDS), are adopted and compared with DBBGDS. As the experimental results show, DBBGDS has its own advantages. Although DS has been adopted by the MPEG- 4 VM, its output sequence quality is worse than that of the proposed algorithm while its complexity is similar to the proposed one. Compared with BBGDS, the proposed algorithm can achieve a better output quality.展开更多
In this paper, a new class of three term memory gradient method with non-monotone line search technique for unconstrained optimization is presented. Global convergence properties of the new methods are discussed. Comb...In this paper, a new class of three term memory gradient method with non-monotone line search technique for unconstrained optimization is presented. Global convergence properties of the new methods are discussed. Combining the quasi-Newton method with the new method, the former is modified to have global convergence property. Numerical results show that the new algorithm is efficient.展开更多
This paper puts forward a two-parameter family of nonlinear conjugate gradient(CG)method without line search for solving unconstrained optimization problem.The main feature of this method is that it does not rely on a...This paper puts forward a two-parameter family of nonlinear conjugate gradient(CG)method without line search for solving unconstrained optimization problem.The main feature of this method is that it does not rely on any line search and only requires a simple step size formula to always generate a sufficient descent direction.Under certain assumptions,the proposed method is proved to possess global convergence.Finally,our method is compared with other potential methods.A large number of numerical experiments show that our method is more competitive and effective.展开更多
In this paper, a new steplength formula is proposed for unconstrained optimization,which can determine the step-size only by one step and avoids the line search step. Global convergence of the five well-known conjugat...In this paper, a new steplength formula is proposed for unconstrained optimization,which can determine the step-size only by one step and avoids the line search step. Global convergence of the five well-known conjugate gradient methods with this formula is analyzed,and the corresponding results are as follows：（1） The DY method globally converges for a strongly convex LC^1 objective function;（2） The CD method, the FR method, the PRP method and the LS method globally converge for a general, not necessarily convex, LC^1 objective function.展开更多
In this paper we consider the global convergence of any conjugate gradient method of the form d1=-g1,dk+1=-gk+1+βkdk(k≥1)with any βk satisfying sume conditions,and with the strong wolfe line search conditions.Under...In this paper we consider the global convergence of any conjugate gradient method of the form d1=-g1,dk+1=-gk+1+βkdk(k≥1)with any βk satisfying sume conditions,and with the strong wolfe line search conditions.Under the convex assumption on the objective function,we preve the descenf property and the global convergence of this method.展开更多
In this paper, we provide and analyze a new scaled conjugate gradient method and its performance, based on the modified secant equation of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method and on a new modified nonmo...In this paper, we provide and analyze a new scaled conjugate gradient method and its performance, based on the modified secant equation of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method and on a new modified nonmonotone line search technique. The method incorporates the modified BFGS secant equation in an effort to include the second order information of the objective function. The new secant equation has both gradient and function value information, and its update formula inherits the positive definiteness of Hessian approximation for general convex function. In order to improve the likelihood of finding a global optimal solution, we introduce a new modified nonmonotone line search technique. It is shown that, for nonsmooth convex problems, the proposed algorithm is globally convergent. Numerical results show that this new scaled conjugate gradient algorithm is promising and efficient for solving not only convex but also some large scale nonsmooth nonconvex problems in the sense of the Dolan-Moré performance profiles.展开更多
A subspace projected conjugate gradient method is proposed for solving large bound constrained quadratic programming. The conjugate gradient method is used to update the variables with indices outside of the active se...A subspace projected conjugate gradient method is proposed for solving large bound constrained quadratic programming. The conjugate gradient method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. At every iterative level, the search direction consists of two parts, one of which is a subspace trumcated Newton direction, another is a modified gradient direction. With the projected search the algorithm is suitable to large problems. The convergence of the method is proved and same numerical tests with dimensions ranging from 5000 to 20000 are given.展开更多
In this paper,we propose enhancements to Beetle Antennae search(BAS)algorithm,called BAS-ADAIVL to smoothen the convergence behavior and avoid trapping in localminima for a highly noin-convex objective function.We ach...In this paper,we propose enhancements to Beetle Antennae search(BAS)algorithm,called BAS-ADAIVL to smoothen the convergence behavior and avoid trapping in localminima for a highly noin-convex objective function.We achieve this by adaptively adjusting the step-size in each iteration using the adaptive moment estimation(ADAM)update rule.The proposed algorithm also increases the convergence rate in a narrow valley.A key feature of the ADAM update rule is the ability to adjust the step-size for each dimension separately instead of using the same step-size.Since ADAM is traditionally used with gradient-based optimization algorithms,therefore we first propose a gradient estimation model without the need to differentiate the objective function.Resultantly,it demonstrates excellent performance and fast convergence rate in searching for the optimum of noin-convex functions.The efficiency of the proposed algorithm was tested on three different benchmark problems,including the training of a high-dimensional neural network.The performance is compared with particle swarm optimizer(PSO)and the original BAS algorithm.展开更多
Recently, Gilbert and Nocedal([3]) investigated global convergence of conjugate gradient methods related to Polak-Ribiere formular, they restricted beta(k) to non-negative value. [5] discussed the same problem as that...Recently, Gilbert and Nocedal([3]) investigated global convergence of conjugate gradient methods related to Polak-Ribiere formular, they restricted beta(k) to non-negative value. [5] discussed the same problem as that in [3] and relaxed beta(k) to be negative with the objective function being convex. This paper allows beta(k) to be selected in a wider range than [5]. Especially, the global convergence of the corresponding algorithm without sufficient decrease condition is proved.展开更多
This paper discusses the global convergence of a class of nonmonotone conjugate gra- dient methods(NM methods) for nonconvex object functions.This class of methods includes the nonmonotone counterpart of modified Po...This paper discusses the global convergence of a class of nonmonotone conjugate gra- dient methods(NM methods) for nonconvex object functions.This class of methods includes the nonmonotone counterpart of modified Polak- Ribière method and modified Hestenes- Stiefel method as special cases展开更多
Based on a differentiable merit function proposed by Taji, et al in “Mathematical Programming, 1993, 58： 369-383”, a projected gradient trust region method for the monotone variational inequality problem with conve...Based on a differentiable merit function proposed by Taji, et al in “Mathematical Programming, 1993, 58： 369-383”, a projected gradient trust region method for the monotone variational inequality problem with convex constraints is presented. Theoretical analysis is given which proves that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.展开更多
Conjugate gradient method is one of successful methods for solving the unconstrained optimization problems. In this paper, absorbing the advantages of FR and CD methods, a hybrid conjugate gradient method is proposed....Conjugate gradient method is one of successful methods for solving the unconstrained optimization problems. In this paper, absorbing the advantages of FR and CD methods, a hybrid conjugate gradient method is proposed. Under the general Wolfe linear searches, the proposed method can generate the sufficient descent direction at each iterate,and its global convergence property also can be established. Some preliminary numerical results show that the proposed method is effective and stable for the given test problems.展开更多
A hybrid method of the Polak-Ribière-Polyak (PRP) method and the Wei-Yao-Liu (WYL) method is proposed for unconstrained optimization pro- blems, which possesses the following properties: i) This method inherits a...A hybrid method of the Polak-Ribière-Polyak (PRP) method and the Wei-Yao-Liu (WYL) method is proposed for unconstrained optimization pro- blems, which possesses the following properties: i) This method inherits an important property of the well known PRP method: the tendency to turn towards the steepest descent direction if a small step is generated away from the solution, preventing a sequence of tiny steps from happening;ii) The scalar holds automatically;iii) The global convergence with some line search rule is established for nonconvex functions. Numerical results show that the method is effective for the test problems.展开更多
With the development of gravity gradient full tensor measurement technique,three-dimensional( 3D) inversion based on gravity gradient tensor can provide more accurate information. But the forward calculation of 3D ful...With the development of gravity gradient full tensor measurement technique,three-dimensional( 3D) inversion based on gravity gradient tensor can provide more accurate information. But the forward calculation of 3D full tensor sensitivity matrix is very time-consuming,which restricts its development and application.According to the symmetry of the kernel function,the authors reconstruct the underground source of geological body to avoid repeat computation of the same value,and work out the corresponding relationship between the response of geological body to the observation point and the response of reconstructed geological body to the observation point. According to the relationship,rapid calculation of full tensor gravity sensitivity matrix can be achieved. The model calculation shows that this method can increase the speed of 30-45 times compared with the traditional calculation method. The sensitivity matrix is applied to the multi-component inversion of gravity gradient. The application of this method on the measured data provides the basis for the promotion of the method.展开更多
文摘This paper provides a gradient search algorithm for finding the maximal visible area polygon (VAP) viewed by an interior point in a simple polygon P. The algorithm is based on a natural partition of P into convex sets, such that each element of the partition is associated with a unique analytical form of the area function. We call this partition a back diagonal partition of P. Our maximal VAP algorithm converges in a finite number of steps, and is polynomial with a complexity of , for a simple polygon P with n vertices, and r reflex vertices. We use the maximal VAP algorithm as a basis for a greedy heuristic for the well known guardhouse problem with a computation complexity of .
基金Natural Science Foundation of Zhejiang Province,Grant/Award Numbers:LTGS23E070001,LZ22F020005,LTGY24C060004National Natural Science Foundation of China,Grant/Award Numbers:62076185,62301367,62273263。
文摘The Runge-Kutta optimiser(RUN)algorithm,renowned for its powerful optimisation capabilities,faces challenges in dealing with increasing complexity in real-world problems.Specifically,it shows deficiencies in terms of limited local exploration capabilities and less precise solutions.Therefore,this research aims to integrate the topological search(TS)mechanism with the gradient search rule(GSR)into the framework of RUN,introducing an enhanced algorithm called TGRUN to improve the performance of the original algorithm.The TS mechanism employs a circular topological scheme to conduct a thorough exploration of solution regions surrounding each solution,enabling a careful examination of valuable solution areas and enhancing the algorithm’s effectiveness in local exploration.To prevent the algorithm from becoming trapped in local optima,the GSR also integrates gradient descent principles to direct the algorithm in a wider investigation of the global solution space.This study conducted a serious of experiments on the IEEE CEC2017 comprehensive benchmark function to assess the enhanced effectiveness of TGRUN.Additionally,the evaluation includes real-world engineering design and feature selection problems serving as an additional test for assessing the optimisation capabilities of the algorithm.The validation outcomes indicate a significant improvement in the optimisation capabilities and solution accuracy of TGRUN.
文摘Motion estimation is an important part of the MPEG- 4 encoder, due to its significant impact on the bit rate and the output quality of the encoder sequence. Unfortunately this feature takes a significant part of the encoding time especially when the straightforward full search(FS) algorithm is used. In this paper, a new algorithm named diamond block based gradient descent search (DBBGDS) algorithm, which is significantly faster than FS and gives similar quality of the output sequence, is proposed. At the same time, some other algorithms, such as three step search (TSS), improved three step search (ITSS), new three step search (NTSS), four step search (4SS), cellular search (CS) , diamond search (DS) and block based gradient descent search (BBGDS), are adopted and compared with DBBGDS. As the experimental results show, DBBGDS has its own advantages. Although DS has been adopted by the MPEG- 4 VM, its output sequence quality is worse than that of the proposed algorithm while its complexity is similar to the proposed one. Compared with BBGDS, the proposed algorithm can achieve a better output quality.
文摘In this paper, a new class of three term memory gradient method with non-monotone line search technique for unconstrained optimization is presented. Global convergence properties of the new methods are discussed. Combining the quasi-Newton method with the new method, the former is modified to have global convergence property. Numerical results show that the new algorithm is efficient.
基金Supported by 2023 Inner Mongolia University of Finance and Economics,General Scientific Research for Universities directly under Inner Mon‐golia,China (NCYWT23026)2024 High-quality Research Achievements Cultivation Fund Project of Inner Mongolia University of Finance and Economics,China (GZCG2479)。
文摘This paper puts forward a two-parameter family of nonlinear conjugate gradient(CG)method without line search for solving unconstrained optimization problem.The main feature of this method is that it does not rely on any line search and only requires a simple step size formula to always generate a sufficient descent direction.Under certain assumptions,the proposed method is proved to possess global convergence.Finally,our method is compared with other potential methods.A large number of numerical experiments show that our method is more competitive and effective.
基金Supported by the National Natural Science Foundation of China(Grant No.11761014)the Natural Science Foundation of Guangxi Zhuang Autonomous Region(Grant No.2017GXNSFAA198243)+2 种基金Guangxi Basic Ability Improvement Project for the Middle-Aged and Young Teachers of Colleges and Universities(Grant Nos.2017KY0068KY2016YB069)Guangxi Higher Education Undergraduate Course Teaching Reform Project(Grant No.2017JGB147)
文摘In this paper, a new steplength formula is proposed for unconstrained optimization,which can determine the step-size only by one step and avoids the line search step. Global convergence of the five well-known conjugate gradient methods with this formula is analyzed,and the corresponding results are as follows：（1） The DY method globally converges for a strongly convex LC^1 objective function;（2） The CD method, the FR method, the PRP method and the LS method globally converge for a general, not necessarily convex, LC^1 objective function.
基金This work is supported by the National Natural Science Foundation of China
文摘In this paper we consider the global convergence of any conjugate gradient method of the form d1=-g1,dk+1=-gk+1+βkdk(k≥1)with any βk satisfying sume conditions,and with the strong wolfe line search conditions.Under the convex assumption on the objective function,we preve the descenf property and the global convergence of this method.
文摘In this paper, we provide and analyze a new scaled conjugate gradient method and its performance, based on the modified secant equation of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method and on a new modified nonmonotone line search technique. The method incorporates the modified BFGS secant equation in an effort to include the second order information of the objective function. The new secant equation has both gradient and function value information, and its update formula inherits the positive definiteness of Hessian approximation for general convex function. In order to improve the likelihood of finding a global optimal solution, we introduce a new modified nonmonotone line search technique. It is shown that, for nonsmooth convex problems, the proposed algorithm is globally convergent. Numerical results show that this new scaled conjugate gradient algorithm is promising and efficient for solving not only convex but also some large scale nonsmooth nonconvex problems in the sense of the Dolan-Moré performance profiles.
基金This research was supported by Chinese NNSF grant and NSF grant of Jiangsu Province
文摘A subspace projected conjugate gradient method is proposed for solving large bound constrained quadratic programming. The conjugate gradient method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. At every iterative level, the search direction consists of two parts, one of which is a subspace trumcated Newton direction, another is a modified gradient direction. With the projected search the algorithm is suitable to large problems. The convergence of the method is proved and same numerical tests with dimensions ranging from 5000 to 20000 are given.
文摘In this paper,we propose enhancements to Beetle Antennae search(BAS)algorithm,called BAS-ADAIVL to smoothen the convergence behavior and avoid trapping in localminima for a highly noin-convex objective function.We achieve this by adaptively adjusting the step-size in each iteration using the adaptive moment estimation(ADAM)update rule.The proposed algorithm also increases the convergence rate in a narrow valley.A key feature of the ADAM update rule is the ability to adjust the step-size for each dimension separately instead of using the same step-size.Since ADAM is traditionally used with gradient-based optimization algorithms,therefore we first propose a gradient estimation model without the need to differentiate the objective function.Resultantly,it demonstrates excellent performance and fast convergence rate in searching for the optimum of noin-convex functions.The efficiency of the proposed algorithm was tested on three different benchmark problems,including the training of a high-dimensional neural network.The performance is compared with particle swarm optimizer(PSO)and the original BAS algorithm.
文摘Recently, Gilbert and Nocedal([3]) investigated global convergence of conjugate gradient methods related to Polak-Ribiere formular, they restricted beta(k) to non-negative value. [5] discussed the same problem as that in [3] and relaxed beta(k) to be negative with the objective function being convex. This paper allows beta(k) to be selected in a wider range than [5]. Especially, the global convergence of the corresponding algorithm without sufficient decrease condition is proved.
基金Supported by the National Natural Science Foundation of China(1 0 1 6 1 0 0 2 ) and Guangxi Natural Sci-ence Foundation (0 1 3 5 0 0 4 )
文摘This paper discusses the global convergence of a class of nonmonotone conjugate gra- dient methods(NM methods) for nonconvex object functions.This class of methods includes the nonmonotone counterpart of modified Polak- Ribière method and modified Hestenes- Stiefel method as special cases
基金Supported by the National Natural Science Foundation of China (10871130)the Ph.D.Foundation of China Education Ministry (0527003)+1 种基金Shanghai Educational Development Foundationthe Science Foundation of Shanghai Education Committee(06A110)
文摘Based on a differentiable merit function proposed by Taji, et al in “Mathematical Programming, 1993, 58： 369-383”, a projected gradient trust region method for the monotone variational inequality problem with convex constraints is presented. Theoretical analysis is given which proves that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.
文摘Conjugate gradient method is one of successful methods for solving the unconstrained optimization problems. In this paper, absorbing the advantages of FR and CD methods, a hybrid conjugate gradient method is proposed. Under the general Wolfe linear searches, the proposed method can generate the sufficient descent direction at each iterate,and its global convergence property also can be established. Some preliminary numerical results show that the proposed method is effective and stable for the given test problems.
文摘A hybrid method of the Polak-Ribière-Polyak (PRP) method and the Wei-Yao-Liu (WYL) method is proposed for unconstrained optimization pro- blems, which possesses the following properties: i) This method inherits an important property of the well known PRP method: the tendency to turn towards the steepest descent direction if a small step is generated away from the solution, preventing a sequence of tiny steps from happening;ii) The scalar holds automatically;iii) The global convergence with some line search rule is established for nonconvex functions. Numerical results show that the method is effective for the test problems.
基金Support by Project of Geophysical Comprehensive Survey and Information Extraction of Deep Mineral Resources(2016YFC0600505)
文摘With the development of gravity gradient full tensor measurement technique,three-dimensional( 3D) inversion based on gravity gradient tensor can provide more accurate information. But the forward calculation of 3D full tensor sensitivity matrix is very time-consuming,which restricts its development and application.According to the symmetry of the kernel function,the authors reconstruct the underground source of geological body to avoid repeat computation of the same value,and work out the corresponding relationship between the response of geological body to the observation point and the response of reconstructed geological body to the observation point. According to the relationship,rapid calculation of full tensor gravity sensitivity matrix can be achieved. The model calculation shows that this method can increase the speed of 30-45 times compared with the traditional calculation method. The sensitivity matrix is applied to the multi-component inversion of gravity gradient. The application of this method on the measured data provides the basis for the promotion of the method.
