Nonadaptive methods for polyhedral approximation of the Edgeworth—Pareto hull using suboptimal coverings on the direction sphere

For multicriteria convex optimization problems, new nonadaptive methods are proposed for polyhedral approximation of the multidimensional Edgeworth-Pareto hull (EPH), which is a maximal set having the same Pareto frontier as the set of feasible criteria vectors. The methods are based on evaluating the support function of the EPH for a collection of directions generated by a suboptimal covering on the unit sphere. Such directions are constructed in advance by applying an asymptotically effective adaptive method for the polyhedral approximation of convex compact bodies, namely, by the estimate refinement method. Due to the a priori definition of the directions, the proposed EPH approximation procedure can easily be implemented with parallel computations. Moreover, the use of nonadaptive methods considerably simplifies the organization of EPH approximation on the Internet. Experiments with an applied problem (from 3 to 5 criteria) showed that the methods are fairly similar in characteristics to adaptive methods. Therefore, they can be used in parallel computations and on the Internet.     

Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier

New hybrid methods for approximating the Pareto frontier of the feasible set of criteria vectors in nonlinear multicriteria optimization problems with nonconvex Pareto frontiers are considered. Since the approximation of the Pareto frontier is an ill-posed problem, the methods are based on approximating the Edgeworth-Pareto hull (EPH), i.e., the maximum set having the same Pareto frontier as the original feasible set of criteria vectors. The EPH approximation also makes it possible to visualize the Pareto frontier and to estimate the quality of the approximation. In the methods proposed, the statistical estimation of the quality of the current EPH approximation is combined with its improvement based on a combination of random search, local optimization, adaptive compression of the search region, and genetic algorithms.     

Convergence analysis of two-phase methods for approximating the Edgeworth-Pareto hull in nonlinear multicriteria optimization problems

The convergence of two-phase methods for approximating the Edgeworth-Pareto hull (EPH) in nonlinear multicriteria optimization problems is analyzed. The methods are based on the iterative supplement of the finite set of feasible criteria vectors (approximation basis) whose EPH approximates the desired set. A feature of two-phase methods is that the criteria images of randomly generated points of the decision space approach the Pareto frontier via local optimization of adaptively chosen convolutions of criteria. The convergence of two-phase methods is proved for both an abstract form of the algorithm and for a two-phase method based on the Germeier convolution.     

Decomposition methods for polyhedral approximation of the Edgeworth–Pareto hull

In the framework of multiobjective optimization (MOO) techniques, there is a group of methods that attract growing attention. These methods are based on the approximation of the Edgeworth–Pareto hull (EPH), that is, the largest set (in the sense of inclusion) that has the same Pareto frontier as the feasible objective set [1, 2]. The block separable structure of MOO problems is used in this paper to improve the efficiency of EPH approximation methods in the case when EPH is convex. In this case, polyhedral approximation can be applied to EPH. Its practical importance was shown, for example, in [3, 4]. In this paper, a two-level system is considered that consists of an upper (coordinating) level and a finite number of blocks interacting through the upper level. It is assumed that the optimization objectives are related only to the variables of the upper level. The approximation method is based on the polyhedral approximation of EPH for single blocks, followed by the application of these results for approximating the EPH for the whole MOO problem.     

Study of an adaptive single-phase method for approximating the multidimensional Pareto frontier in nonlinear systems

The problem of approximating the Pareto frontier (nondominated frontier) of the feasible set of criteria vectors in nonlinear multicriteria optimization problems is considered. The problem is solved by approximating the Edgeworth-Pareto hull (EPH), i.e., the maximum set with the same Pareto frontier as the original feasible set of criteria vectors. An EPH approximation method is studied that is based on the statistical accuracy estimation of the current approximation and on adaptive supplement of a metric net whose EPH approximates the desired set. The convergence of the method is proved, estimates for the convergence rate are obtained, and the efficiency of the method is studied in the case of a compact feasible set and continuous criteria functions. It is shown that the convergence rate of the method with respect to the number k of iterations is no lower than $ o\left( {k^{{1 \mathord{\left/ {\vphantom {1 {\overline {dm} Y}}} \right. \kern-\nulldelimiterspace} {\overline {dm} Y}}} } \right) $ o\left( {k^{{1 \mathord{\left/ {\vphantom {1 {\overline {dm} Y}}} \right. \kern-\nulldelimiterspace} {\overline {dm} Y}}} } \right) , where $ \overline {dm} Y $ \overline {dm} Y is the upper metric dimension of the feasible set of criteria vectors.     

On approximation of functions by algebraic polynomials in Hölder spaces

We study approximation of functions by algebraic polynomials in the Hölder spaces corresponding to the generalized Jacobi translation and the Ditzian–Totik moduli of smoothness. By using modifications of the classical moduli of smoothness, we give improvements of the direct and inverse theorems of approximation and prove the criteria of the precise order of decrease of the best approximation in these spaces. Moreover, we obtain strong converse inequalities for some methods of approximation of functions. As an example, we consider approximation by the Durrmeyer–Bernstein polynomial operators.     

On nondecreasing sequences of regularization parameters for nonstationary iterated Tikhonov

Nonstationary iterated Tikhonov is an iterative regularization method that requires a strategy for defining the Tikhonov regularization parameter at each iteration and an early termination of the iterative process. A classical choice for the regularization parameters is a decreasing geometric sequence which leads to a linear convergence rate. The early iterations compute quickly a good approximation of the true solution, but the main drawback of this choice is a rapid growth of the error for later iterations. This implies that a stopping criteria, e.g. the discrepancy principle, could fail in computing a good approximation. In this paper we show by a filter factor analysis that a nondecreasing sequence of regularization parameters can provide a rapid and stable convergence. Hence, a reliable stopping criteria is no longer necessary. A geometric nondecreasing sequence of the Tikhonov regularization parameters into a fixed interval is proposed and numerically validated for deblurring problems.     

Un método de captura de choques basado en las funciones de forma para Galerkin discontinuo de alto orden

This article presents a high-order Discontinuous Galerkin method for compressible flow problems, in which is very frequent the formation of shocks. The stabilization is introduced by a new basis functions. This base has the flexibility to vary locally (within each element) between continuous polynomial functions space and a space of piecewise polynomial functions. Thus, the proposed method provides a bridge between the standard methods of high-order Discontinuous Galerkin and classical Finite Volume methods, maintaining the locality and compactness of the scheme. The variation of basis functions is automatically set according to the regularity of the solution and the stabilization is introduced by the jump operator, standard in Discontinuous Galerkin methods. Unlike the classical methods of slope limiting, the strategy here presented is very local, robust, and applies to any order of approximation. Moreover, the proposed method does not require adaptive mesh refinement techniques and it can be used with any temporal integration scheme. Several applications of the Euler equations are shown, demonstrating the validity and effectiveness of the method, especially for high orders of approximation.     

Two Numerical Methods for Computing the Probability of Outcome of a Battle of Lanchester Type

Methods are developed for the computation of victory probabilities in the classical Lanchester ‘modern warfare’ model. The first method employs a bivariate normal approximation for state probabilities and a kind of steepest descents technique for the evaluation of the integral: the second proposes a truncated binomial approximation along certain diagonal lines. Both methods depend on moments. Computational performance is discussed.     

Duality for Algebraic Linear Programming

A duality theory for algebraic linear (integer) programming (ALP) is developed which is of the same importance for linear (integer) programming with linear algebraic objectives as linear programming duality is for classical LP. In particular, optimality criteria for primal, primal-dual, and dual methods are given which generalize feasibility and complementarity criteria of classical LP. Strong duality results are given for special combinatorial problems. Further, the validity and finiteness of a primal simplex method based on a feasibility criterion are proved in the case of nondiscrete variables. In this case a strong duality result is shown.     

Approximation algorithms for the bi-criteria weighted MAX-CUT problem

We consider a generalization of the classical MAX-CUT problem where two objective functions are simultaneously considered. We derive some theorems on the existence and the non-existence of feasible cuts that are at the same time near optimal for both criteria. Furthermore, two approximation algorithms with performance guarantee are presented. The first one is deterministic while the second one is randomized. A generalization of these results is given for the bi-criteria MAX-k-CUT problem.     

Best Fourier Approximation and Application in Efficient Blurred Signal Reconstruction

We expand upon the known results on sharp linear Fourier methods of approximation where the approximation is the best in terms of both rate and constant among all polynomial procedures of approximation. So far these results have been studied due to their mathematical beauty rather than their practical importance. In this paper we show that they are the core mathematics underlying best statistical methods of solving noisy ill-posed problems. In particular, we suggest a procedure for recovery of noisy blurred signals based on samples of small sizes where a traditional statistics concludes that the complexity of such a setting makes the problem not worthy of a further study. Thus, we present a problem where a combination of the classical approximation theory and statistics leads to interesting practical results.     

求解单变量无约束优化问题的一类新割线法

本文基于分式逼近提出了一类求解单变量无约束优化问题的新割线法,给出并证明了该方法的收敛阶是(√2+1).并进一步对新方法的性能进行了分析,给出了新方法、经典的牛顿法和其他修正的割线类方法解单变量无约束优化问题的数值实验.理论和数值结果均表明新的割线法是有效的.     

Galerkin method for Wiener-Hopf operators with piecewise continuous symbol

This paper is concerned with the applicability of maximum defect polynomial (Galerkin) spline approximation methods with graded meshes to Wiener-Hopf operators with matrix-valued piecewise continuous generating function defined on R. For this, an algebra of sequences is introduced, which contains the approximating sequences we are interested in. There is a direct relationship between the stability of the approximation method for a given operator and invertibility of the corresponding sequence in this algebra. Exploring this relationship, the methods of essentialization, localization and identification of the local algebras are used in order to derive stability criteria for the approximation sequences.Supported by grant Praxis XXI/BD/4501/94 from FCT.Partly supported by FCT/BMFT grant 423.     

解非线性方程组的一类离散的Newton算法

1．引言考虑非线性方程组设xi是当前的迭代点，为计算下一个迭代点，Newton法是求解方程若用差商代替导数，离散Newton法要解如下的方程其中这里为了计算J（；；h），需计算n‘个函数值．为了提高效能，Brown方法l‘］使用代入消元的办法来减少函数值计算量．它是再通过一次内选代从h得到下一个迭代点14＋1．设n；＝（《1，…，Zn尸，t二（ti，…，t＊”，t为变量．BfOWll方法的基本思想如下．对人（x）在X；处做线性近似解出然后代入第二个函数，得到这是关于tZ，…，tn的函数．当（tZ，…，t。尸一（ZZ，…，Z。厂时，由（1．4），…     

Strong uniqueness

Summary In the present work a common basis of convergence analysis is given for a large class of iterative procedures which we call general approximation methods. The concept of strong uniqueness is seen to play a fundamental role. The broad range of applications of this proposed classification will be made clear by means of examples from various areas of numerical mathematics. Included in this classification are methods for solving systems of equations, the Remes algorithm, methods for nonlinear Chebyshev-approximation, the classical Newton method along with its variants such as Newton's method for partially ordered spaces and for degenerate tangent spaces. As an example of the latter the approximation with exponential sums having coalescing frequencies is discussed, that is the case where the tangent space is degenerate.     

A note on the singular linear system of the generalized finite element methods

We characterize the kernel of the global stiffness matrix in the singular linear system of the generalized finite element methods (GFEM) which uses the classical finite element (FE) shape functions and local approximation space of harmonic polynomials.     

Bernstein-type operators diminish the φ-variation

We show that a large class of Bernstein-type operators usually considered in approximation theory diminish the total and the fine φ-variation, thus extending a classical result on 1-variation diminution concerning the Bernstein polynomials. Also, the closely related problem of approximation in φ-variation is thoroughly discussed. For these purposes, we use a probabilistic approach in which coupling methods play a fundamental role.     

互补约束均衡问题一个新的磨光技术

研究了一类带非线性互补约束的均衡问题．借助于逐步逼近思想,构造了一个在求解意义上与原问题等价的磨光非线性规划．从而保证一些经典的标准优化算法可以应用到该类优化问题上．最后提出了两个算法模型并分析了其全局收敛性．     

Sufficient criteria are necessary for monotone control volume methods

Control volume methods are prevailing for solving the potential equation arising in porous media flow. The continuous form of this equation is known to satisfy a maximum principle, and it is desirable that the numerical approximation shares this quality. Recently, sufficient criteria were derived guaranteeing a discrete maximum principle for a class of control volume methods. We show that most of these criteria are also necessary. An implication of our work is that no linear nine-point control volume method can be constructed for quadrilateral grids in 2D that is exact for linear solutions while remaining monotone for general problems.