A robust discontinuous Galerkin method for solving convection-diffusion problems

In this paper, a new DG method was designed to solve the model problem of the one-dimensional singularly-perturbed convection-diffusion equation. With some special chosen numerical traces, the existence and uniqueness of the DG solution is provided. The superconvergent points inside each element are observed. Particularly, the 2p ＋ 1-order superconvergence and even uniform superconvergence under layer-adapted mesh are observed numerically.     

A robust and efficient method for solving point distance problems by homotopy

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables by introducing additional auxiliary variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all “minimal” quadratizations of negative monomials.     

A practical method for solving large-scale TRS

We present a nearly-exact method for the large scale trust region subproblem (TRS) based on the properties of the minimal-memory BFGS method. Our study is concentrated in the case where the initial BFGS matrix can be any scaled identity matrix. The proposed method is a variant of the Moré–Sorensen method that exploits the eigenstructure of the approximate Hessian B, and incorporates both the standard and the hard case. The eigenvalues of B are expressed analytically, and consequently a direction of negative curvature can be computed immediately by performing a sequence of inner products and vector summations. Thus, the hard case is handled easily while the Cholesky factorization is completely avoided. An extensive numerical study is presented, for covering all the possible cases arising in the TRS with respect to the eigenstructure of B. Our numerical experiments confirm that the method is suitable for very large scale problems.     

A method for solving stochastic eigenvalue problems

We present a novel approach for calculating stochastic eigenvalues of differential and integral equations as well as for random matrices. Five examples based on very different types of problem have been analysed and detailed numerical results obtained. It would seem that the method has considerable promise. The essence of the method is to replace the stochastic eigenvalue problem λ(ξ)?(ξ)=A(ξ)?(ξ), where ξ is a set of random variables, by the introduction of an auxiliary equation in which . This changes the problem from an eigenvalue one to an initial value problem in the new pseudo-time variable t. The new linear time-dependent equation may then be solved by a polynomial chaos expansion (PCE) and the stochastic eigenvalue and its moments recovered by a limiting process. This technique has the advantage of avoiding the non-linear terms in the conventional method of stochastic eigenvalue calculation by PCE, but it does introduce an additional, ‘pseudo-time’, independent variable t. The paper illustrates the viability of this approach by application to several examples based on realistic problems.     

A general method for solving constrained optimization problems

In this paper a general problem of constrained minimization is studied. The minima are determined by searching for the asymptotical values of the solutions of a suitable system of ordinary differential equations.For this system, if the initial point is feasible, then any trajectory is always inside the set of constraints and tends towards a set of critical points. Each critical point that is not a relative minimum is unstable. For formulas of one-step numerical integration, an estimate of the step of integration is given, so that the above mentioned qualitative properties of the system of ordinary differential equations are kept.     

A projection-filter method for solving nonlinear complementarity problems

The Josephy-Newton method attacks nonlinear complementarity problems which consists of solving, possibly inexactly, a sequence of linear complementarity problems. Under appropriate regularity assumptions, this method is known to be locally (superlinearly) convergent. Utilizing the filter method, we presented a new globalization strategy for this Newton method applied to nonlinear complementarity problem without any merit function. The strategy is based on the projection-proximal point and filter methodology. Our linesearch procedure uses the regularized Newton direction to force global convergence by means of a projection step which reduces the distance to the solution of the problem. The resulting algorithm is globally convergent to a solution. Under natural assumptions, locally superlinear rate of convergence was established.     

A numerical method for solving nonlinear ill-posed problems

A two-step iterative process for the numerical solution of nonlinear problems is suggested. In order to avoid the ill-posed inversion of the Fréchet derivative operator, some regularization parameter is introduced. A convergence theorem is proved. The proposed method is illustrated by a numerical example in which a nonlinear inverse problem of gravimetry is considered. Based on the results of the numerical experiments practical recommendations for the choice of the regularization parameter are given. Some other iterative schemes are considered.     

解变分不等式问题的混合方法

By using Fukushima‘s differentiable merit function,Taji,Fukushima and Ibaraki have given a globally convergent modified Newton method for the strongly monotone variational inequality problem and proved their method to be quadratically convergent under certain assumptions in 1993. In this paper a hybrid method for the variational inequality problem under the assumptions that the mapping F is continuously differentiable and its Jacobian matrix F(x) is positive definite for all x∈S rather than strongly monotone and that the set S is nonempty, polyhedral,closed and convex is proposed. Armijo-type line search and trust region strategies as well as Fukushima‘s differentiable merit function are incorporated into the method. It is then shown that the method is well defined and globally convergent and that,under the same assumptions as those of Taji et al. ,the method reduces to the basic Newton method and hence the rate of convergence is quadratic. Computational experiences show the efficiency of the proposed method.     

A finite volume method for solving Navier-Stokes problems

We develop a finite volume method for solving the Navier-Stokes equations on a triangular mesh. We prove that the unique solution of the finite volume method converges to the true solution with optimal order for velocity and for pressure in discrete H¹ norm and L² norm respectively.     

A regularized method for solving constrained pseudoinverse problems

For a constrained pseudoinverse problem whose operators satisfy the complementarity condition we propose a one-parameter continuous regularization method of the second order. This method is based on stabilization of solutions to Cauchy problems for a linear differential equation of the second order in a Hilbert space which is obtained from the heavy ball method. We establish requirements to the parametric regularization function and perturbation levels that ensure the stability of the method in the class of all possible bounded perturbations.     

Exact approaches for solving robust prize-collecting Steiner tree problems

In the Prize-Collecting Steiner Tree Problem (PCStT) we are given a set of customers with potential revenues and a set of possible links connecting these customers with fixed installation costs. The goal is to decide which customers to connect into a tree structure so that the sum of the link costs plus the revenues of the customers that are left out is minimized. The problem, as well as some of its variants, is used to model a wide range of applications in telecommunications, gas distribution networks, protein–protein interaction networks, or image segmentation.     

A globally convergent derivative-free method for solving large-scale nonlinear monotone equations

In this paper, we propose two derivative-free iterative methods for solving nonlinear monotone equations, which combines two modified HS methods with the projection method in Solodov and Svaiter (1998) [5]. The proposed methods can be applied to solve nonsmooth equations. They are suitable to large-scale equations due to their lower storage requirement. Under mild conditions, we show that the proposed methods are globally convergent. The reported numerical results show that the methods are efficient.     

A hybrid algorithm for solving convex separable network flow problems

Based on computational experiments with different approaches to convex separable network flow problems a hybrid algorithm is developed and implemented. Phase one of the algorithm uses a rapidly converging series of piecewise linear secant approximations in order to determine a good solution within some distance of the optimum. Starting from this solution, a feasible direction method, based on reduced Newton directions, is used in the second phase of the algorithm to determine the optimal solution. Since nonlinear network flow problems tend to be degenerate, special emphasis is put on the construction of a basis that yields a strictly positive step length at the beginning of phase two of the hybrid algorithm.A number of test problems have been solved successfully. It is expected that the approach can be extended to solve large-scale problems with convex separable objective functions. Details of the implementation and computational results are presented.

---

Zusammenfassung Ausgehend von experimentellen Ergebnissen mit unterschiedlichen Lösungsverfahren für separable Netzwerkflußprobleme wurde ein zweistufiges Verfahren entwickelt und implementiert. Auf der ersten Stufe wird in einem iterativen Prozeß das zu lösende Problem mehrfach stückweise linearisiert. Man erhält eine bereits sehr gute Lösung. Mit dieser wird ein Richtungsverfahren initialisiert, das unter Verwendung reduzierter Newton Richtungen die optimale Lösung bestimmt. Das Richtungsverfahren bildet die zweite Stufe des Verfahrens. Da nichtlineare Netzwerkflußprobleme im allgemeinen stark entartet sind, wird zu Beginn der zweiten Stufe des beschriebenen Verfahrens eine Basis konstruiert, die eine positive Schrittlänge zuläßt.Es wurden zahlreiche Testprobleme mit bis zu 600 Knoten und 1400 Kanten mit dem beschriebenen Verfahren erfolgreich gelöst. Es wird erwartet, daß das Verfahren auch auf sehr viel größere Probleme mit konvexer, separabler Zielfunktion angewendet werden kann. Es wird auf Fragen zur Implementation eingegangen und es werden numerische Ergebnisse diskutiert.

     

A numerical method for solving singular boundary value problems

Summary A numerical method is treated for solving singular boundary value problems with solutions that can be represented as series expansions on a subinterval near the singularity. A regular boundary value problem is derived on the remaining interval, for which a difference method is used. Convergence theorems are given for general schemes and for schemes of positive type for second order equations.     

非光滑最优控制问题的一种数值解法

针对非光滑最优控制问题提出一种分段数值解法.首先对问题进行全局拟谱离散,然后选取分点,将时间区域进行剖分,在每段区域上对问题进行离散,离散过程采用Chebyshev-Legendre拟谱方法,可以有效借助快速Legendre变换提高算法的运算效率,比现有算法在很大程度上节省了计算时间.给出了相关的理论分析,数值结果表明方法的高精度和有效性.     

A collocation-shooting method for solving fractional boundary value problems

In this paper, we discuss the numerical solution of special class of fractional boundary value problems of order 2. The method of solution is based on a conjugating collocation and spline analysis combined with shooting method. A theoretical analysis about the existence and uniqueness of exact solution for the present class is proven. Two examples involving Bagley–Torvik equation subject to boundary conditions are also presented; numerical results illustrate the accuracy of the present scheme.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

A method for solving to optimality uncapacitated location problems

In this paper we develop a method for solving to optimality a general 0–1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times.The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage.The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, thep-median problem and the fixed-chargep-median problem. Computational results are given for problems of up to the size 200 customers ×200 potential facility sites.     

A multi-domain method for solving numerically multi-scale elliptic problems

In this paper we present a family of iterative methods to solve numerically second order elliptic problems with multi-scale data using multiple levels of grids. These methods are based upon the introduction of a Lagrange multiplier to enforce the continuity of the solution and its fluxes across interfaces. This family of methods can be interpreted as a mortar element method with complete overlapping domain decomposition for solving numerically multi-scale elliptic problems. To cite this article: R. Glowinski et al., C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Inspired grey wolf optimizer for solving large-scale function optimization problems

Grey wolf optimizer algorithm was recently presented as a new heuristic search algorithm with satisfactory results in real-valued and binary encoded optimization problems that are categorized in swarm intelligence optimization techniques. This algorithm is more effective than some conventional population-based algorithms, such as particle swarm optimization, differential evolution and gravitational search algorithm. Some grey wolf optimizer variants were developed by researchers to improve the performance of the basic grey wolf optimizer algorithm. Inspired by particle swarm optimization algorithm, this study investigates the performance of a new algorithm called Inspired grey wolf optimizer which extends the original grey wolf optimizer by adding two features, namely, a nonlinear adjustment strategy of the control parameter, and a modified position-updating equation based on the personal historical best position and the global best position. Experiments are performed on four classical high-dimensional benchmark functions, four test functions proposed in the IEEE Congress on Evolutionary Computation 2005 special session, three well-known engineering design problems, and one real-world problem. The results show that the proposed algorithm can find more accurate solutions and has higher convergence rate and less number of fitness function evaluations than the other compared techniques.