A Gradient Search Algorithm for the Maximal Visible Area Polygon Problem

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 .

New Diamond Block Based Gradient Descent Search Algorithm for Motion Estimation in the MPEG- 4 Encoder

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.

GLOBAL CONVERGENCE RESULTS OF A THREE TERM MEMORY GRADIENT METHOD WITH A NON-MONOTONE LINE SEARCH TECHNIQUE

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.

GLOBAL CONVERGENCE OF THE GENERAL THREE TERM CONJUGATE GRADIENT METHODS WITH THE RELAXED STRONG WOLFE LINE SEARCH

The global convergence of the general three term conjugate gradient methods with the relaxed strong Wolfe line search is proved.

ON THE GLOBAL CONVERGENCE OF CONJUGATE GRADIENT METHODS WITH INEXACT LINESEARCH

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.

A Scaled Conjugate Gradient Method Based on New BFGS Secant Equation with Modified Nonmonotone Line Search

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 New Class of Nonlinear Conjugate Gradient Methods with Global Convergence Properties

非线性共轭梯度法由于其迭代简单和储存量小,且搜索方向不需要满足正割条件,在求解大规模无约束优化问题时占据及其重要的地位.提出了一类新的共轭梯度法,其搜索方向是目标函数的下降方向.若假设目标函数连续可微且梯度满足Lipschitz条件,线性搜索满足Wolfe原则,讨论了所设计算法的全局收敛性.

A SUBSPACE PROJECTED CONJUGATE GRADIENT ALGORITHM FOR LARGE BOUND CONSTRAINED QUADRATIC PROGRAMMING

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.

BAS-ADAM:An ADAM Based Approach to Improve the Performance of Beetle Antennae Search Optimizer

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.

A CLASSOF NONMONOTONE CONJUGATE GRADIENT METHODSFOR NONCONVEX FUNCTIONS

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

A projected gradient method with nonmonotonic backtracking technique for solving convex constrained monotone variational inequality problem

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.

Global Convergence of a Hybrid Conjugate Gradient Method

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 conjugate gradient method for optimization 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.

双线性参数系统的极大似然递推参数估计

研究具有自回归滑动平均噪声的双线性参数系统,该系统结构复杂,噪声项的研究更具普遍意义。为实现系统参数的在线辨识,采用梯度搜索方法,推导了双线性参数系统的随机梯度算法。对于出现的未知项,基于递阶辨识原理使用其估计值进行替代。极大似然估计方法基于概率论,具有良好的一致性、渐近正态性和可用性,在引入极大似然估计方法后得到了相应的极大似然随机梯度算法,为进一步减小有色噪声对参数估计精度的影响,结合多新息辨识理论,将标量单新息扩展为多新息向量,研究了具有自回归滑动平均噪声的双线性参数系统的极大似然多新息随机梯度参数估计方法,并进行了仿真验证。

Multi-component joint inversion of gravity gradient based on fast forward calculation

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.

PRP-Type Direct Search Methods for Unconstrained Optimization

Three PRP-type direct search methods for unconstrained optimization are presented. The methods adopt three kinds of recently developed descent conjugate gradient methods and the idea of frame-based direct search method. Global convergence is shown for continuously differentiable functions. Data profile and performance profile are adopted to analyze the numerical experiments and the results show that the proposed methods are effective.

基于改进遗传算法的图像边缘检测

针对经典边缘检测算法在一定程度上的局限性,提出了一种改进的遗传算法进行边缘检测。阐述了图像梯度的幅值和变化率,并将遗传算法引入到图像边缘检测中。利用天牛须搜索算法来引导遗传算法中交叉点位置的移动方向。通过提高子辈种群的多样性,防止了搜索区域逐渐缩小,克服了传统遗传算法早熟收敛的现象。实验结果表明,与传统的边缘检测算法相比,改进的遗传算法应用于不同的图像检测具有良好的稳定性和较快的收敛速度,可以收敛到全局最优解甚至逼近全局最优解,从而提高被检测图像边缘的完整性。

CONVERGENCE ANALYSIS ON A CLASS OF CONJUGATE GRADIENT METHODS WITHOUTSUFFICIENT DECREASE CONDITION

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.

基于拉普拉斯算法和梯度边缘特征的鱼货去鳞机表面磨损检测方法

为了确保鱼货去鳞机的正常使用,需要检测其表面磨损情况。提出基于拉普拉斯算法和梯度边缘特征的鱼货去鳞机表面磨损检测方法。首先,采用布谷鸟搜索算法优化二维高斯函数,结合拉普拉斯算法与优化后的二维高斯函数对鱼货去鳞机表面图像展开卷积处理,以此增强磨损区域边缘细节信息,实现磨损区域边缘检测;其次,对磨损区域展开Gamma校正,在此基础上提取磨损区域的HOG特征与LSS特征,结合上述特征构成梯度边缘特征;最后,基于S-SVM建立鱼货去鳞机表面磨损检测模型,将梯度边缘特征输入模型内,实现鱼货去鳞机表面磨损检测。实验结果表明,所提方法可准确确定磨损边缘,高精度地完成磨损特征提取与检测。

一种近似BFGS的自适应双参数共轭梯度法

为了更加有效的求解大规模无约束优化问题,本文基于自调比无记忆BFGS拟牛顿法,提出一个自适应双参数共轭梯度法,设计的搜索方向满足充分下降性,在一般假设和标准Wolfe线搜索准则下,证明该方法具有全局收敛性,数值实验结果证明提出的新算法是有效的.