Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

信赖域策略的内点投影既约Hessian方法解非线性约束优化

A interior point scaling projected reduced Hessian method with combination of nonmonotonic backtracking technique and trust region strategy for nonlinear equality constrained optimization with nonegative constraint on variables is proposed. In order to deal with large problems,a pair of trust region subproblems in horizontal and vertical subspaces is used to replace the general full trust region subproblem. The horizontal trust region subproblem in the algorithm is only a general trust region subproblem while the vertical trust region subproblem is defined by a parameter size of the vertical direction subject only to an ellipsoidal constraint. Both trust region strategy and line search technique at each iteration switch to obtaining a backtracking step generated by the two trust region subproblems. By adopting the l1 penalty function as the merit function, the global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion and the second order correction step are used to overcome Maratos effect and speed up the convergence progress in some ill-conditioned cases.     

一类无约束离散Minimax问题的区间调节熵算法

In this paper,a class of unconstrained discrete minimax problems is described,in which the objective functions are in C^1. The paper deals with this problem by means of taking the place of maximum-entropy function with adjustable entropy function. By constructing an interval extension of adjustable entropy function and some region deletion test rules, a new interval algorithm is presented. The relevant properties are proven, The minimax value and the localization of the minimax points of the problem can be obtained by this method. This method can overcome the flow problem in the maximum-entropy algorithm. Both theoretical and numerical results show that the method is reliable and efficient.     

A NEW STEPSIZE FOR THE STEEPEST DESCENT METHOD

The steepest descent method is the simplest gradient method for optimization. It is well known that exact line searches along each steepest descent direction may converge very slowly. An important result was given by Barzilar and Borwein, which is proved to be superlinearly convergent for convex quadratic in two dimensional space, and performs quite well for high dimensional problems. The BB method is not monotone, thus it is not easy to be generalized for general nonlinear functions unless certain non-monotone techniques being applied. Therefore, it is very desirable to find stepsize formulae which enable fast convergence and possess the monotone property. Such a stepsize αk for the steepest descent method is suggested in this paper. An algorithm with this new stepsize in even iterations and exact line search in odd iterations is proposed. Numerical results are presented, which confirm that the new method can find the exact solution within 3 iteration for two dimensional problems. The new method is very efficient for small scale problems. A modified version of the new method is also presented, where the new technique for selecting the stepsize is used after every two exact line searches. The modified algorithm is comparable to the Barzilar-Borwein method for large scale problems and better for small scale problems.     

A REMAPPING METHOD BASED ON MULTI-POINT FLUX CORNER TRANSPORT UPWIND ADVECTION ALGORITHM

A local remapping algorithm for scalar function on quadrilateral meshes is described. The remapper from a distorted grid to a rezoned grid is usually regarded as a conservative interpolation problem. The present paper introduces a pseudo time to transform the interpolation into an initial value problem on a moving grid, and construct a moving mesh method to solve it. The new feature of the algorithm is the introduction of multi- point information on each edge, which leads to the numerical flux consistent with grid node motion. During the procedure of deriving scheme, we illustrate a framework about how the algorithms on a rectangular mesh are easily generated to those on a moving mesh. The basic ideas include： （i） introducing coordinate transformation, which maps the irregular domain in physical space to a perfectly regular computational domain, and （ii） deriving finite volume methods in the physical domain, which can be viewed as a discretization of the transformed equation. The resulting scheme is second-order accurate, conservative and monotonicity preserving. Numerical examples are carried out to show the good performance of ore＂ schemes.     

AN EFFICIENT MOVING MESH METHOD FOR A MODEL OF TURBULENT FLOW IN CIRCULAR TUBES

This paper presents an efficient moving problem with an optimal control constrained mesh method to solve a nonlinear singular condition. The physical problem is governed by a new model of turbulent flow in circular tubes proposed by Luo et al. using Prandtl＇s mixing-length theory. Our algorithm is formed by an outer iterative algorithm for handling the optimal control condition and an inner adaptive mesh redistribution algorithm for solving the singular governing equations. We discretize the nonlinear problem by using a upwinding approach, and the resulting nonlinear equations are solved by using the Newton- Raphson method. The mesh is generated and the grid points are moved by using the arc-length equidistribution principle. The numerical results demonstrate that proposed algorithm is effective in capturing the boundary layers associated with the turbulent model.     

MULTIGRID METHOD FOR A MODIFIED CURVATURE DRIVEN DIFFUSION MODEL FOR IMAGE INPAINTING

Digital inpainting is a fundamental problem in image processing and many variational models for this problem have appeared recently in the literature. Among them are the very successfully Total Variation （TV） model [11] designed for local inpainting and its improved version for large scale inpainting： the Curvature-Driven Diffusion （CDD） model [10]. For the above two models, their associated Euler Lagrange equations are highly nonlinear partial differential equations. For the TV model there exists a relatively fast and easy to implement fixed point method, so adapting the multigrid method of [24] to here is immediate. For the CDD model however, so far only the well known but usually very slow explicit time marching method has been reported and we explain why the implementation of a fixed point method for the CDD model is not straightforward. Consequently the multigrid method as in [Savage and Chen, Int. J. Comput. Math., 82 （2005）, pp. 1001-1015] will not work here. This fact represents a strong limitation to the range of applications of this model since usually fast solutions are expected. In this paper, we introduce a modification designed to enable a fixed point method to work and to preserve the features of the original CDD model. As a result, a fast and efficient multigrid method is developed for the modified model. Numerical experiments are presented to show the very good performance of the fast algorithm.     

采用不定Dogleg路径的非单调自适应信赖域算法解无约束极小化(英文)

In this paper, we combine the nonmonotone and adaptive techniques with trust region method for unconstrained minimization problems. We set a new ratio of the actual descent and predicted descent. Then, instead of the monotone sequence, the nonmonotone sequence of function values are employed. With the adaptive technique, the radius of trust region △k can be adjusted automatically to improve the efficiency of trust region methods. By means of the Bunch-Parlett factorization, we construct a method with indefinite dogleg path for solving the trust region subproblem which can handle the indefinite approximate Hessian Bk. The convergence properties of the algorithm are established. Finally, detailed numerical results are reported to show that our algorithm is efficient.     

线性规划的对偶基线算法

In this paper,we studied the dual form of the basic line algorthm for linear programs.It can be easily implemented in tableau that similar to the primal/dual simplex method.Different from primal simplex method or dual simplex method,the dual basic line algorithm can keep primal feasibility and dual feasibility at the same time in a tableau,which makes it more efficient than the former ones.Principles and convergence of dual basic line algorthm were discussed.Some examplex and computational experience were given to illustrate the efficiency of our method.     

An efficient algorithm to clip a 2D-polygon against a rectangular clip window

Polygon clipping is of great importance in computer graphics.One of the popular algorithms to clip a polygon is Cohan–Sutherland Hodgeman algorithm which is based on line clipping.Cohan–Sutherland Hodgeman algorithm clips the polygon against the given rectangular clip window with the help of line clipping method.Cohan–Sutherland algorithm requires traversing the polygon in anti clockwise direction(positive orientation).In this work we propose an efficient polygon clipping algorithm against a rectangular clip window.Proposed algorithm uses parametric representation of polygon edges.Using the concept of point clipping,we can find required intersection points of edges of polygon with clip window boundaries.Well suited numerical illustrations are used to explain the proposed polygon clipping method.The proposed algorithm is computationally less expensive and comprehensive.     

视频车辆分类与计数的模型与应用

由于受形态变化、光照变化、视觉碰撞和视觉模糊的影响,基于监控视频的车辆分类和计数一直都是待解决的复杂问题。为了更好地解决这个问题,本文提出新的模型来更好的提取前景。详细来讲,在初次前景提取中,建立模型判断是否存在车辆碰撞,对存在碰撞的车辆通过灰度空间双阀值和YCbCr图像空间处理后,对前景进行更准确的再提取。并在此基础上针对碰撞车辆,定义间隙特征向量将车辆分割问题转换为寻找分割点的优化问题,从而给出高效的车辆分割算法,对发生碰撞的车辆进行准确分割。之后利用神经网络对车辆分类,并设计一种基于已正确对碰撞车辆分割的算法对车辆计数。实验结果表明,本文提出的模型在视频车辆的分类和计数中取得优异的表现,并且数据处理速度能够满足及时性。比起人为计算车流量或建立三维模型等进行分析车辆碰撞情况下的车辆分类与计数,此方法兼顾了准确性与时效性,效率提高,成本减少。     

Fast Surface Mesh Denoising with Regularization and Edge Preservation

We describe a hybrid algorithm that is designed to smooth, but not only smooth, noisy polygonal surface meshes with sharp edges. While denoising, our method simultaneously regularizes triangle meshes on flat regions for further mesh processing and preserves edge sharpness for faithful reconstruction. A clustering technique, which combines K-means and geometric a priori information, is first developed and refined. It is then used to implement vertex classification so that we can subsequently apply different smoothing operators on different vertex groups. This yields a highly efficient robust algorithm that is capable of handling both edge sharpness and mesh sampling irregularity without any significant cost increase. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Towards a more efficient dynamic mesh adaptation methodology for continuum discretization in complex engineering problems

A novel and efficient method of adaptive mesh generation, for dynamically adaptive unstructured grids, is proposed. A locally refined triangulation is constructed on a coarse background mesh, subdividing each triangle in the refinement region R into four congruent sub-triangles iteratively, by connecting edge midpoints, until triangles of a prescribed lengthscale are obtained. The unavoidable propagation outside the refinement region R is restricted to a single triangle in the coarse background mesh. The triangles, in the immediate vicinity of region R, are broken down using the concept of iterated function systems, widely used in fractal modeling, by recursive generation of sub-triangles with a gradation towards the region R triangles. A quantitative assessment of the present algorithm proves its superiority over other comparable models reported in the literature. The time cost of the algorithm is linear, and the method can be easily extended to three dimensions.     

Feature extraction algorithms for constrained global optimization II. Batch process scheduling application

The feature extraction algorithms developed in part I of this series are applied to solve nonconvex mixed integer nonlinear programming problems which arise in the optimal scheduling of multipurpose chemical plants. A general formulation of the multipurpose plant scheduling problem is developed which considers the allocation of plant equipment and secondary, limited resources to recipe operations so as to satisfy given production requirements while minimizing cost. Results obtained with a test example involving 135 binary and 922 continuous variables show that the successive refinement strategy is effective in identifying dominant regions of the solution space. Furthermore it is shown that multiple moment based characterization methods are superior to the interval analysis method reported in the literature. Trials using a second, larger nonlinear test problem involving 356 binary and 2402 continuous variables demonstrate that the focused successive refinement strategy is more efficient than a constant resolution strategy which employs genetic algorithm constructions. Although the conventional genetic algorithm can be significantly improved by introducing a heuristic mutation strategy which increases the likelihood of constant feasibility, the successive refinement strategy remains dominant. These studies demonstrate that the feature extraction strategy employing successive refinements and relatively low order moment based region characterization methods, offers an effective approach to solving an important class of large scale MINLP problems with multiple local optima.     

An exact feature selection algorithm based on rough set theory

Feature reduction based on rough set theory is an effective feature selection method in pattern recognition applications. Finding a minimal subset of the original features is inherent in rough set approach to feature selection. As feature reduction is a Nondeterministic Polynomial‐time‐hard problem, it is necessary to develop fast optimal or near‐optimal feature selection algorithms. This article aims to propose an exact feature selection algorithm in rough set that is efficient in terms of computation time. The proposed algorithm begins the examination of a solution tree by a breadth‐first strategy. The pruned nodes are held in a version of the trie data structure. Based on the monotonic property of dependency degree, all subsets of the pruned nodes cannot be optimal solutions. Thus, by detecting these subsets in trie, it is not necessary to calculate their dependency degree. The search on the tree continues until the optimal solution is found. This algorithm is improved by selecting an initial search level determined by the hill‐climbing method instead of searching the tree from the level below the root. The length of the minimal reduct and the size of data set can influence which starting search level is more efficient. The experimental results using some of the standard UCI data sets, demonstrate that the proposed algorithm is effective and efficient for data sets with more than 30 features. © 2014 Wiley Periodicals, Inc. Complexity 20: 50–62, 2015     

Parallel Smoothed Aggregation Multilevel Schwarz Preconditioned Newton-Krylov Algorithms for Poisson-Boltzmann Problems

We study a multilevel Schwarz preconditioned Newton-Krylov algorithm to solve the Poisson-Boltzmann equation with applications in multi-particle colloidal simulation. The smoothed aggregation-type coarse mesh space is introduced in collaboration with the one-level Schwarz method as a composite preconditioner for accelerating the convergence of a Krylov subspace method for solving the Jacobian system at each Newton step. The important feature of the proposed solution algorithm is that the geometric mesh information needed for constructing the multilevel preconditioner is the same as the one-level Schwarz method on the fine mesh. Other components, such as the definition of the coarse mesh, all the mesh transfer operators, and the coarse mesh problem, are taken care of by the Trillinos/ML packages of the Sandia National Laboratories in the United States. After algorithmic parameter tuning, we show that the proposed smoothed aggregation multilevel Newton-Krylov-Schwarz (NKS) algorithm numerically outperforms than smoothed aggregation multigrid method and one-level version of the NKS algorithm with satisfactory parallel performances up to a few thousand cores. Besides, we investigate how the electrostatic forces between particles for the separation distance depend on the radius of spherical colloidal particles and valence ratios of cation and anion in a cubic system.     

Generalized fast marching method: applications to image segmentation

In this paper, we propose a segmentation method based on the generalized fast marching method (GFMM) developed by Carlini et al. (submitted). The classical fast marching method (FMM) is a very efficient method for front evolution problems with normal velocity (see also Epstein and Gage, The curve shortening flow. In: Chorin, A., Majda, A. (eds.) Wave Motion: Theory, Modelling and Computation, 1997) of constant sign. The GFMM is an extension of the FMM and removes this sign constraint by authorizing time-dependent velocity with no restriction on the sign. In our modelling, the velocity is borrowed from the Chan–Vese model for segmentation (Chan and Vese, IEEE Trans Image Process 10(2):266–277, 2001). The algorithm is presented and analyzed and some numerical experiments are given, showing in particular that the constraints in the initialization stage can be weakened and that the GFMM offers a powerful and computationally efficient algorithm.     

Image segmentation by level set evolution with region consistency constraint

Image segmentation is a key and fundamental problem in image processing, computer graphics, and computer vision. Level set based method for image segmentation is used widely for its topology flexibility and proper mathematical formulation. However, poor performance of existing level set models on noisy images and weak boundary limit its application in image segmentation. In this paper, we present a region consistency constraint term to measure the regional consistency on both sides of the boundary, this term defines the boundary of the image within a range, and hence increases the stability of the level set model. The term can make existing level set models significantly improve the efficiency of the algorithms on segmenting images with noise and weak boundary. Furthermore, this constraint term can make edge-based level set model overcome the defect of sensitivity to the initial contour. The experimental results show that our algorithm is efficient for image segmentation and outperform the existing state-of-art methods regarding images with noise and weak boundary.     

A variational model and its numerical solution for local,selective and automatic segmentation

Variational region-based segmentation models can serve as effective tools for identifying all features and their boundaries in an image. To adapt such models to identify a local feature defined by geometric constraints, re-initializing iterations towards the feature offers a solution in some simple cases but does not in general lead to a reliable solution. This paper presents a dual level set model that is capable of automatically capturing a local feature of some interested region in three dimensions. An additive operator spitting method is developed for accelerating the solution process. Numerical tests show that the proposed model is robust in locally segmenting complex image structures.