On the approximation of unstable parametric minimal surfaces

We prove optimal convergence results for discrete approximations to (possibly unstable) minimal surfaces. This appears to be the first class of results of this type for geometric objects solving a highly non-linear geometric variational problem. We introduce a number of new techniques which we expect will be of use in other geometric problems. The theoretical approximation results are confirmed by numerical test computations.     

A fast algorithm for solving diagonally dominant symmetric pentadiagonal Toeplitz systems

Banded Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Recently, significant advancement has been made in algorithm development of fast parallel scalable methods to solve tridiagonal Toeplitz problems. In this paper we will derive a new algorithm for solving symmetric pentadiagonal Toeplitz systems of linear equations based upon a technique used in [J.M. McNally, L.E. Garey, R.E. Shaw, A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Int. J. Comput. Math. 75 (2000) 303-313] for tridiagonal Toeplitz systems. A common example which arises in natural quintic spline problems will be used to demonstrate the algorithm’s effectiveness. Finally computational results and comparisons will be presented.     

Multigrid Methods with Newton-Gauss-Seidel Smoothing and Constraint Preserving Interpolation for Obstacle Problems

In this paper, we propose a multigrid algorithm based on the full approximate scheme for solving the membrane constrained obstacle problems and the minimal surface obstacle problems in the formulations of HJB equations. A Newton-Gauss-Seidel (NGS) method is used as smoother. A Galerkin coarse grid operator is proposed for the membrane constrained obstacle problem. Comparing with standard FAS with the direct discretization coarse grid operator, the FAS with the proposed operator converges faster. A special prolongation operator is used to interpolate functions accurately from the coarse grid to the fine grid at the boundary between the active and inactive sets. We will demonstrate the fast convergence of the proposed multigrid method for solving two model obstacle problems and compare the results with other multigrid methods.     

A Particle Filtering Approach for Tracking an Unknown Number of Objects with Dynamic Relations

In recent years there has been a growing interest on particle filters for solving tracking problems, thanks to their applicability to problems with continuous, non-linear and non-Gaussian state spaces, which makes them more suited than hidden Markov models, Kalman filters and their derivations, in many real world tasks. Applications include video surveillance, sensor fusion, tracking positions and behaviors of moving objects, situation assessment in civil and bellic scenarios, econometric and clinical data series analysis. In many environments it is possible to recognize classes of similar entities, like pedestrians or vehicles in a video surveillance system, or commodities in econometric. In this paper, a relational particle filter for tracking an unknown number of objects is presented which exploits possible interactions between objects to improve the quality of filtering. We will see that taking into account relations between objects will ease the tracking of objects in presence of occlusions and discontinuities in object dynamics. Experimental results on a benchmark data set are presented.     

符号和数值混合计算

符号计算和数值计算是两种不同的解决科学和技术发展中问题的计算方法.符号计算可以得到问题精确的完备解,但是计算量大且表达形式往往十分庞大;数值计算可以快速地处理很多实际应用中的问题,但是一般只能得到近似的局部解.特别地,数值计算处理病态问题时,收敛往往较慢且容易出错.着重介绍了符号计算和数值计算之间的密切联系,以及如何运用这两大领域的最新研究成果,探索和开发符号和数值混合计算算法和软件,使之兼备符号计算的完备化和数值计算的高效性.     

The Bound-Constrained Conjugate Gradient Method for Non-negative Matrices

Existing conjugate gradient (CG)-based methods for convex quadratic programs with bound constraints require many iterations for solving elastic contact problems. These algorithms are too cautious in expanding the active set and are hampered by frequent restarting of the CG iteration. We propose a new algorithm called the Bound-Constrained Conjugate Gradient method (BCCG). It combines the CG method with an active-set strategy, which truncates variables crossing their bounds and continues (using the Polak–Ribière formula) instead of restarting CG. We provide a case with n=3 that demonstrates that this method may fail on general cases, but we conjecture that it always works if the system matrix A is non-negative. Numerical results demonstrate the effectiveness of the method for large-scale elastic contact problems.     

The Finite Difference Based Fast Adaptive Composite Grid Method

The fast adaptive composite grid (FAC) method is an iterative method for solving discrete boundary value problems on composite grids. McCormick introduced the method in [8] and considered the convergence behaviour for discrete problems resulting from finite volume element discretization on composite grids. In this paper we consider discrete problems resulting from finite difference discretization on composite grids. We distinguish between two obvious discretization approaches at the grid points on the interfaces between fine and coarse subgrids. The FAC method for solving such discrete problems is described. In the FAC method several intergrid transfer operators appear. We study how the convergence behaviour depends on these intergrid transfer operators. Based on theoretical insights, (quasi-)optimal intergrid transfer operators are derived. Numerical results illustrate the fast convergence of the FAC method using these intergrid transfer operators.     

Interior point methods 25 years later

Interior point methods for optimization have been around for more than 25 years now. Their presence has shaken up the field of optimization. Interior point methods for linear and (convex) quadratic programming display several features which make them particularly attractive for very large scale optimization. Among the most impressive of them are their low-degree polynomial worst-case complexity and an unrivalled ability to deliver optimal solutions in an almost constant number of iterations which depends very little, if at all, on the problem dimension. Interior point methods are competitive when dealing with small problems of dimensions below one million constraints and variables and are beyond competition when applied to large problems of dimensions going into millions of constraints and variables.In this survey we will discuss several issues related to interior point methods including the proof of the worst-case complexity result, the reasons for their amazingly fast practical convergence and the features responsible for their ability to solve very large problems. The ever-growing sizes of optimization problems impose new requirements on optimization methods and software. In the final part of this paper we will therefore address a redesign of interior point methods to allow them to work in a matrix-free regime and to make them well-suited to solving even larger problems.     

Evaluating naval tactical missile systems by fuzzy AHP based on the grade value of membership function

Many decision making problems which are complicated and fuzzy in nature exist in modern society. How to solve them is becoming increasingly important for human society. For solving multiple criteria's decision making in a fuzzy environment, in this paper, we will propose a new algorithm for evaluating naval tactical missile systems by the fuzzy Analytical Hierarchy Process based on grade value of membership function. Generally, we are given scores by experience of experts to represent judgmental objects. In this paper, from viewpoint of many experts, we will build membership functions of judgement criteria for all sub-items. When the membership function is built, we can calculate the grade value by data of missile performance. The grade value is called performance score. Our methods can be summarized in the following.

• 1.1. Building membership function of judgement criteria for all sub-items, it is called fuzzy standard.
• 2.2. Calculate the grade of membership function by practical data to represent performance scores.
• 3.3. Use fuzzy AHP method and entropy concepts to calculate aggregate weights.

Finally, for a simple and efficient computation, we have developed a systematic and practical program to calculate all algorithms, and apply the new algorithm to a naval tactical missile systems valuation and selection problem.     

An iterative thresholding algorithm for linear inverse problems with multi-constraints and its applications

In this paper, we will present a generalization for a minimization problem from I. Daubechies, M. Defrise, and C. DeMol (2004) [3]. This generalization is useful for solving many practical problems in which more than one constraint are involved. In this regard, we will conclude the findings of many papers (most of which are on image processing) from this generalization. It is hoped that the approach proposed in this paper will be a suitable reference for some applied works where multi-frames, multi-wavelets, or multi-constraints are present in linear inverse problems.     

Stochastic Survivable Network Design Problems

In this paper we introduce survivable network design problems under a two-stage stochastic model with fixed recourse and finitely many scenarios. We propose a new cut-based formulation based on orientation properties which is stronger than the undirected cut-based model. We use a two-stage branch&cut algorithm for solving the decomposed model to provable optimality. In order to accelerate the computations, we suggest a new cut strengthening technique for the decomposed L-shaped optimality cuts that is computationally fast and easy to implement.     

New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.     

Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems

New variants of greedy algorithms, called advanced greedy algorithms, are identified for knapsack and covering problems with linear and quadratic objective functions. Beginning with single-constraint problems, we provide extensions for multiple knapsack and covering problems, in which objects must be allocated to different knapsacks and covers, and also for multi-constraint (multi-dimensional) knapsack and covering problems, in which the constraints are exploited by means of surrogate constraint strategies. In addition, we provide a new graduated-probe strategy for improving the selection of variables to be assigned values. Going beyond the greedy and advanced greedy frameworks, we describe ways to utilize these algorithms with multi-start and strategic oscillation metaheuristics. Finally, we identify how surrogate constraints can be utilized to produce inequalities that dominate those previously proposed and tested utilizing linear programming methods for solving multi-constraint knapsack problems, which are responsible for the current best methods for these problems. While we focus on 0–1 problems, our approaches can readily be adapted to handle variables with general upper bounds.     

Simultaneous pseudo-time stepping for aerodynamic shape optimization

In this paper we discuss about numerical methods for aerodynamic shape optimization problems. These problems require efficient CFD techniques to solve the state (as well as costate) equations and fast algorithms for solving the optimization problems. Both of these are independent active areas of research since long time. Wide range of applications in science and engineering involve solution of optimization problems where the governing PDEs appear as constraints. Therefore, merging the two for the purpose of practical applicability is relatively new. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fast inversion of matrices arising in image processing

In recent years, new nonlinear partial differential equation (PDE) based approaches have become popular for solving image processing problems. Although the outcome of these methods is often very promising, their actual realization is in general computationally intensive. Therefore, accurate and efficient schemes are needed. The aim of this paper is twofold. First, we will show that the three dimensional alignment problem of a histological data set of the human brain may be phrased in terms of a nonlinear PDE. Second, we will devise a fast direct solution technique for the associated structured large systems of linear equations. In addition, the potential of the derived method is demonstrated on real-life data. This revised version was published online in June 2006 with corrections to the Cover Date.     

Mimicry of proofs with computers: the case of Linear Algebra

In common teaching practice the habit of connecting mathematics classroom activities with reality is still substantially delegated to wor(l)d problems. During recent decades, a growing body of empirical research has documented that the practice of word problem solving in school mathematics does not match this idea of mathematical modelling and mathematization. If we wish to construct ‘real problems arising from real experiences of the child’ following the spirit of these new suggestions, we have to make changes. On the one hand we have to replace the type of activity in which we delegate the process of creating an interplay between reality and mathematics by substituting the word problems with an activity of realistic mathematical modelling, i.e. of both real-world based and quantitatively constrained sense-making; and, on the other hand, to ask for a change in teacher beliefs; furthermore, a directed effort to change the classroom socio-math norms will be needed. This paper discusses some classroom activities that takes these factors into account.     

A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis

We will propose a new cutting plane algorithm for solving a class of semi-definite programming problems (SDP) with a small number of variables and a large number of constraints. Problems of this type appear when we try to classify a large number of multi-dimensional data into two groups by a hyper-ellipsoidal surface. Among such examples are cancer diagnosis, failure discrimination of enterprises. Also, a certain class of option pricing problems can be formulated as this type of problem. We will show that the cutting plane algorithm is much more efficient than the standard interior point algorithms for solving SDP.     

An Augmented ADMM Algorithm With Application to the Generalized Lasso Problem

In this article, we present a fast and stable algorithm for solving a class of optimization problems that arise in many statistical estimation procedures, such as sparse fused lasso over a graph, convex clustering, and trend filtering, among others. We propose a so-called augmented alternating direction methods of multipliers (ADMM) algorithm to solve this class of problems. Compared to a standard ADMM algorithm, our proposal significantly reduces the computational cost at each iteration while maintaining roughly the same overall convergence speed. We also consider a new varying penalty scheme for the ADMM algorithm, which could further accelerate the convergence, especially when solving a sequence of problems with tuning parameters of different scales. Extensive numerical experiments on the sparse fused lasso problem show that the proposed algorithm is more efficient than the standard ADMM and two other existing state-of-the-art specialized algorithms. Finally, we discuss a possible extension and some interesting connections to two well-known algorithms. Supplementary materials for the article are available online.     

Numerical Solution of Contact Problems using Level Set Methods on Voxel Discretizations

Fast solvers performing on a regular grid are often used for problems in elasticity, in order to avoid expensive mesh generations. However, if overlaps between solid materials occur without any interactions, these might deteriorate the results, especially for the stresses. Therefore, we want to present an approach for developing numerical methods for contact problems on a regular mesh with the help of signed distance data and multi-material voxels. In this contribution we will focus on problems in linear elastostatics with contact between several different bodies. Finally, we present the results from a numerical test for the two dimensional Hertz problem, solved on a triangular regular mesh. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

ECO:a methodology for the enumeration of combinatorial objects

In this Paper, we illustrate a method (called the ECO method) for enumerating some classes of combinatorial objects. The basic idea of this method is the following: by means of an operator that performs a "local expansion" on the objects, we give some recursive constructions of these classes. We use these constructions to deduce some new funtional equations verified by classes' generating functions. By solving the functional equations, we enumerate the combinatorial objects according to various parameters. We show some applications of the method referring to some classical combinatorial objects, such as: trees, paths, polyminoes and permutations