定积分计算方法及其数值试验

以定积分概念所蕴含的数学思想和哲学思想为指导,给出定积分近似计算的两种方法,即定义法和蒙特卡罗方法,并借助Matlab软件编程对其加以验证,数值试验结果显示所给方法可行且有效．     

Optimality condition and algorithm with deviation integral for global optimization

To study the integral global minimization, a general form of deviation integral is introduced and its properties are examined in this work. In terms of the deviation integral, optimality condition and algorithms are given. Algorithms are implemented by a properly designed Monte Carlo simulation. Numerical tests are given to show the effectiveness of the method.     

Lagrangian duality of concave minimization subject to linear constraints and an additional facial reverse convex constraint

This paper is concerned with the global optimization problem of minimizing a concave function subject to linear constraints and an additional facial reverse convex constraint. Here, the feasible set is the union of some faces of the polyhedron determined by the linear constraints. Several well-known mathematical problems can be written or transformed into the form considered. The paper addresses the Lagrangian duality of the problem. It is shown that, under slight assumptions, the duality gap can be closed with a finite dual multiplier. Finite methods based on solving concave minimization problems are also proposed. We deal with the advantages accrued when outer approximation, cutting plane, or branch-and-bound methods are used for solving these subproblems.This research was supported in part by the Hungarian National Research Foundation, Grant OTKA 2568. The author wishes to thank the Associate Editor and the referees for their valuable comments.     

A parallel stochastic method for solving linearly constrained concave global minimization problems

A parallel stochastic algorithm is presented for solving the linearly constrained concave global minimization problem. The algorithm is a multistart method and makes use of a Bayesian stopping rule to identify the global minimum with high probability. Computational results are presented for more than 200 problems on a Cray X-MP EA/464 supercomputer.     

Semi-Iterative Minimum Cross-Entropy Algorithms for Rare-Events,Counting, Combinatorial and Integer Programming

We present a new generic minimum cross-entropy method, called the semi-iterative MinxEnt, or simply SME, for rare-event probability estimation, counting, and approximation of the optimal solutions of a broad class of NP-hard linear integer and combinatorial optimization problems (COP’s). The main idea of our approach is to associate with each original problem an auxiliary single-constrained convex MinxEnt program of a special type, which has a closed-form solution. We prove that the optimal pdf obtained from the solution of such a specially designed MinxEnt program is a zero variance pdf, provided the “temperature” parameter is set to minus infinity. In addition we prove that the parametric pdf based on the product of marginals obtained from the optimal zero variance pdf coincides with the parametric pdf of the standard cross-entropy (CE) method. Thus, originally designed at the end of 1990s as a heuristics for estimation of rare-events and COP’s, CE has strong connection with MinxEnt, and thus, strong mathematical foundation. The crucial difference between the proposed SME method and the standard CE counterparts lies in their simulation-based versions: in the latter we always require to generate (via Monte Carlo) a sequence of tuples including the temperature parameter and the parameter vector in the optimal marginal pdf’s, while in the former we can fix in advance the temperature parameter (to be set to a large negative number) and then generate (via Monte Carlo) a sequence of parameter vectors of the optimal marginal pdf’s alone. In addition, in contrast to CE, neither the elite sample no the rarity parameter is needed in SME. As result, the proposed SME algorithm becomes simpler, faster and at least as accurate as the standard CE. Motivated by the SME method we introduce a new updating rule for the parameter vector in the parametric pdf of the CE program. We show that the CE algorithm based on the new updating rule, called the combined CE (CCE), is at least as fast and accurate as its standard CE and SME counterparts. We also found numerically that the variance minimization (VM)-based algorithms are the most robust ones. We, finally, demonstrate numerically that the proposed algorithms, and in particular the CCE one, allows accurate estimation of counting quantities up to the order of hundred of decision variables and hundreds of constraints. This research was supported by the Israel Science Foundation (grant No 191-565).     

Convexlike and concavelike conditions in alternative,minimax, and minimization theorems

Convexlike and concavelike conditions are of interest for extensions of the Von Neumann minimax theorem. Since the beginning of the 80's, these conditions also play a certain role in deriving generalized alternative theorems of the Gordan, Motzkin, and Farkas type and Lagrange multiplier results for constrained minimization problems.In this paper, we study various known convexlike conditions for vector-valued functions on a set and investigate convexlike and concavelike conditions for real-valued functions on a product setC×D, where we are mainly interested in the relationships between these conditions. At the end of the paper, we point out several conclusions from our results for the above-mentioned mathematical fields.The author is indebted to Dr. R. Reemtsen and Dr. V. Jeyakumar for their helpful comments during the preparations of this paper.     

Selective Search for Global Optimization of Zero or Small Residual Least-Squares Problems: A Numerical Study

In this paper, we consider approximating global minima of zero or small residual, nonlinear least-squares problems. We propose a selective search approach based on the concept of selective minimization recently introduced in Zhang et al. (Technical Report TR99-12, Rice University, Department of Computational and Applied Mathematics MS-134, Houston, TX 77005, 1999). To test the viability of the proposed approach, we construct a simple implementation using a Levenberg-Marquardt type method combined with a multi-start scheme, and compare it with several existing global optimization techniques. Numerical experiments were performed on zero residual nonlinear least-squares problems chosen from structural biology applications and from the literature. On the problems of significant sizes, the performance of the new approach compared favorably with other tested methods, indicating that the new approach is promising for the intended class of problems.     

Interior-Point Algorithms,Penalty Methods and Equilibrium Problems

In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPECs)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties and provide substantial numerical results. We go on to show that penalty methods can resolve some problems that interior-point algorithms encounter in general. An erratum to this article is available at .     

计算多项式函数的全局下确界和全局最小值的有效算法

通过捕获所谓的严格临界点, 本文提出了一个计算实多项式函数的全局下确界和全局最小值的有效方法. 对于实数域R 上一个n 元多项式f, 该方法可用来判定f 在Rⁿ 上是否具有有限的全局下确界. 在f 具有有限的全局下确界的情况下, f 的下确界可严格地表示为码(h; a, b), 其中h 是一个实单元多项式, a 和b 是使得a < b 的两个有理数, 而(h; a, b) 代表h(z) 在开区间]a, b[ 中仅有的实根.此外, 当f 具有有限下确界时, 本文的方法可进一步判定f 的下确界能否达到. 在我们的算法设计中,著名的吴方法起着重要作用.     

A C0 interior penalty discontinuous Galerkin method for fourth‐order total variation flow. I: Derivation of the method and numerical results

We consider the numerical solution of a fourth‐order total variation flow problem representing surface relaxation below the roughening temperature. Based on a regularization and scaling of the nonlinear fourth‐order parabolic equation, we perform an implicit discretization in time and a C⁰ Interior Penalty Discontinuous Galerkin (C⁰IPDG) discretization in space. The C⁰IPDG approximation can be derived from a mixed formulation involving numerical flux functions where an appropriate choice of the flux functions allows to eliminate the discrete dual variable. The fully discrete problem can be interpreted as a parameter dependent nonlinear system with the discrete time as a parameter. It is solved by a predictor corrector continuation strategy featuring an adaptive choice of the time step sizes. A documentation of numerical results is provided illustrating the performance of the C⁰IPDG method and the predictor corrector continuation strategy. The existence and uniqueness of a solution of the C⁰IPDG method will be shown in the second part of this paper.     

Algorithms for computing the global infimum and minimum of a polynomial function

By catching the so-called strictly critical points,this paper presents an effective algorithm for computing the global infimum of a polynomial function.For a multivariate real polynomial f ,the algorithm in this paper is able to decide whether or not the global infimum of f is finite.In the case of f having a finite infimum,the global infimum of f can be accurately coded in the Interval Representation.Another usage of our algorithm to decide whether or not the infimum of f is attained when the global infimum of f is finite.In the design of our algorithm,Wu’s well-known method plays an important role.     

The simplex method as a global optimizer: A c-programming perspective

In this paper we give a brief account of the important role that the conventional simplex method of linear programming can play in global optimization, focusing on its collaboration with composite concave programming techniques. In particular, we demonstrate how rich and powerful the c-programming format is in cases where its parametric problem is a standard linear programming problem.     

Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization,reverse convex constraints,DC-programming,and Lipschitzian optimization

A crucial problem for many global optimization methods is how to handle partition sets whose feasibility is not known. This problem is solved for broad classes of feasible sets including convex sets, sets defined by finitely many convex and reverse convex constraints, and sets defined by Lipschitzian inequalities. Moreover, a fairly general theory of bounding is presented and applied to concave objective functions, to functions representable as differences of two convex functions, and to Lipschitzian functions. The resulting algorithms allow one to solve any global optimization problem whose objective function is of one of these forms and whose feasible set belongs to one of the above classes. In this way, several new fields of optimization are opened to the application of global methods.     

线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization

Solutions of learning problems by Empirical Risk Minimization (ERM) – and almost-ERM when the minimizer does not exist – need to be consistent, so that they may be predictive. They also need to be well-posed in the sense of being stable, so that they might be used robustly. We propose a statistical form of stability, defined as leave-one-out (LOO) stability. We prove that for bounded loss classes LOO stability is (a) sufficient for generalization, that is convergence in probability of the empirical error to the expected error, for any algorithm satisfying it and, (b) necessary and sufficient for consistency of ERM. Thus LOO stability is a weak form of stability that represents a sufficient condition for generalization for symmetric learning algorithms while subsuming the classical conditions for consistency of ERM. In particular, we conclude that a certain form of well-posedness and consistency are equivalent for ERM. Dedicated to Charles A. Micchelli on his 60th birthday Mathematics subject classifications (2000) 68T05, 68T10, 68Q32, 62M20. Tomaso Poggio: Corresponding author.     

Resampling Markov Chain Monte Carlo Algorithms: Basic Analysis and Empirical Comparisons

Sampling from complex distributions is an important but challenging topic in scientific and statistical computation. We synthesize three ideas, tempering, resampling, and Markov moving, and propose a general framework of resampling Markov chain Monte Carlo (MCMC). This framework not only accommodates various existing algorithms, including resample-move, importance resampling MCMC, and equi-energy sampling, but also leads to a generalized resample-move algorithm. We provide some basic analysis of these algorithms within the general framework, and present three simulation studies to compare these algorithms together with parallel tempering in the difficult situation where new modes emerge in the tails of previous tempering distributions. Our analysis and empirical results suggest that generalized resample-move tends to perform the best among all the algorithms studied when the Markov kernels lead to fast mixing or even locally so toward restricted distributions, whereas parallel tempering tends to perform the best when the Markov kernels lead to slow mixing, without even converging fast to restricted distributions. Moreover, importance resampling MCMC and equi-energy sampling perform similarly to each other, often worse than independence Metropolis resampling MCMC. Therefore, different algorithms seem to have advantages in different settings.     

The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization

A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the Reactive Tabu Search recently proposed by the authors, locates the most promising boxes, in which starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications without user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a variety of benchmark tasks.     

Error Estimation and Optimization of the Functional Algorithms of a Random Walk on a Grid Which Are Applied to Solving the Dirichlet Problem for the Helmholtz Equation

We consider the algorithms of a random walk on a grid which are applied to global solution of the Dirichlet problem for the Helmholtz equation (the direct and conjugate methods). In the metric space C we construct some upper error bounds and obtain optimal values (in the sense of the error bound) of the parameters of the algorithms (the number of nodes and the sample size).