共查询到20条相似文献,搜索用时 31 毫秒
1.
Ai-Fan Ling Cheng-Xian Xu Feng-Min Xu 《Journal of Computational and Applied Mathematics》2008,220(1-2):643-660
A discrete filled function algorithm is proposed for approximate global solutions of max-cut problems. A new discrete filled function is defined for max-cut problems and the properties of the filled function are studied. Unlike general filled function methods, using the characteristic of max-cut problems, the parameters in proposed filled function need not be adjusted. This greatly increases the efficiency of the filled function method. By combining a procedure that randomly generates initial points for minimization of the filled function, the proposed algorithm can greatly reduce the calculation cost and be applied to large scale max-cut problems. Numerical results on different sizes and densities test problems indicate that the proposed algorithm is efficient and stable to get approximate global solutions of max-cut problems. 相似文献
2.
The filled function method is an approach to find the global minimum of multidimensional functions. This paper proposes a new definition of the filled function for integer programming problem. A filled function which satisfies this definition is presented. Furthermore, we discuss the properties of the filled function and design a new filled function algorithm. Numerical experiments on several test problems with up to 50 integer variables have demonstrated the applicability and efficiency of the proposed method. 相似文献
3.
The global optimization method based on discrete filled function is a new method that solves large scale max-cut problems. We first define a new discrete filled function based on the structure of the max-cut problem and analyze its properties. Unlike the continuous filled function methods, by the characteristic of the max-cut problem, the parameters in the proposed filled function does not need to be adjusted. By combining a procedure that randomly generates initial points for minimization of the proposed filled function, the proposed algorithm can greatly reduce the computational time and be applied to large scale max-cut problems. Numerical results and comparisons with several heuristic methods indicate that the proposed algorithm is efficient and stable to obtain high quality solution of large scale max-cut problems. 相似文献
4.
In this paper, a discrete filled function algorithm embedded with continuous approximation is proposed to solve max-cut problems. A new discrete filled function is defined for max-cut problems, and properties of the function are studied. In the process of finding an approximation to the global solution of a max-cut problem, a continuation optimization algorithm is employed to find local solutions of a continuous relaxation of the max-cut problem, and then global searches are performed by minimizing the proposed filled function. Unlike general filled function methods, characteristics of max-cut problems are used. The parameters in the proposed filled function need not to be adjusted and are exactly the same for all max-cut problems that greatly increases the efficiency of the filled function method. Numerical results and comparisons on some well known max-cut test problems show that the proposed algorithm is efficient to get approximate global solutions of max-cut problems. 相似文献
5.
离散填充函数是一种用于求解多极值优化问题最优解的一种行之有效的方法.已被证明对于求解大规模离散优化问题是有效的.本文基于改进的离散填充函数定义,构造了一个新的无参数填充函数,并在理论上给出了证明,提出了一个新的填充函数算法.该填充函数无需调节参数,而且只需极小化一次目标函数.数值结果表明,该算法是高效的、可行的. 相似文献
6.
Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison. 相似文献
7.
整数规划的一类填充函数算法 总被引:9,自引:0,他引:9
填充函数算法是求解连续总体优化问题的一类有效算法。本文改造[1]的填充函数算法使之适于直接求解整数规划问题。首先,给出整数规划问题的离散局部极小解的定义,并设计找离散局部极小解的领域搜索算法。其次,构造整数规划问题的填充函数算法。该方法通过寻找填充函数的离散局部极小解以期找到整数规划问题的比当前离散局部极小解好的解。本文的算法是直接法,数值试验表明算法是有效的。 相似文献
8.
Discrete Clifford analysis is a higher dimensional discrete function theory, based on skew Weyl relations. The basic notions are discrete monogenic functions, i.e. Clifford algebra valued functions in the kernel of a discrete Dirac operator. In this paper, we introduce the discrete Fueter polynomials, which form a basis of the space of discrete spherical monogenics, i.e. discrete monogenic, homogeneous polynomials. Their definition is based on a Cauchy–Kovalevskaya extension principle. We present the explicit construction for this discrete Fueter basis, in arbitrary dimension m and for arbitrary homogeneity degree k. 相似文献
9.
10.
《Journal of Computational and Applied Mathematics》2005,181(1):200-210
The paper gives a definition of the filled function for nonlinear integer programming. This definition is modified from that of the global convexized filled function for continuous global optimization. A filled function with only one parameter which satisfies this definition is presented. We also discuss the properties of the proposed function and give a filled function method to solve the nonlinear integer programming problem. The implementation of the algorithm on several test problems is reported with satisfactory numerical results. 相似文献
11.
Grazyna Wolczynska 《Applied Mathematical Finance》2013,20(3-4):165-179
Various methods of option pricing in discrete time models are discussed. The classical risk minimization method often results in negative prices and a natural modification is proposed. Another method of risk minimization using an inductive procedure as in the Cox-Ross-Rubinstein model is also proposed. The definition of the risk interpreted as the maximum of possible loss is discussed. 相似文献
12.
Yanyuan Ma Marc G. Genton Emanuel Parzen 《Annals of the Institute of Statistical Mathematics》2011,63(2):227-243
The asymptotic distribution of sample quantiles in the classical definition is well-known to be normal for absolutely continuous
distributions. However, this is no longer true for discrete distributions or samples with ties. We show that the definition
of sample quantiles based on mid-distribution functions resolves this issue and provides a unified framework for asymptotic
properties of sample quantiles from absolutely continuous and from discrete distributions. We demonstrate that the same asymptotic
normal distribution result as for the classical sample quantiles holds at differentiable points, whereas a more general form
arises for distributions whose cumulative distribution function has only one-sided differentiability. For discrete distributions
with finite support, the same type of asymptotics holds and the sample quantiles based on mid-distribution functions either
follow a normal or a two-piece normal distribution. We also calculate the exact distribution of these sample quantiles for
the binomial and Poisson distributions. We illustrate the asymptotic results with simulations. 相似文献
13.
The filled function method is an effective approach to find a global minimizer for a general class of nonsmooth programming problems with a closed bounded domain. This paper gives a new definition for the filled function, which overcomes some drawbacks of the previous definition. It proposes a two-parameter filled function and a one-parameter filled function to improve the efficiency of numerical computation. Based on these analyses, two corresponding filled function algorithms are presented. They are global optimization methods which modify the objective function as a filled function, and which find a better local minimizer gradually by optimizing the filled function constructed on the minimizer previously found. Numerical results obtained indicate the efficiency and reliability of the proposed filled function methods. 相似文献
14.
15.
Luis Nunes Vicente 《Optimization Letters》2009,3(3):475-482
This paper addresses derivative-free optimization problems where the variables lie implicitly in an unknown discrete closed
set. The evaluation of the objective function follows a projection onto the discrete set, which is assumed dense (and not
sparse as in integer programming). Such a mathematical setting is a rough representation of what is common in many real-life
applications where, despite the continuous nature of the underlying models, a number of practical issues dictate rounding
of values or projection to nearby feasible figures. We discuss a definition of minimization for these implicitly discrete
problems and outline a direct-search algorithm framework for its solution. The main asymptotic properties of the algorithm
are analyzed and numerically illustrated. 相似文献
16.
The filled function method is an effective approach to find a global minimizer. In this paper, based on a new definition of the filled function for nonsmooth constrained programming problems, a one-parameter filled function is constructed to improve the efficiency of numerical computation. Then a corresponding algorithm is presented. It is a global optimization method which modify the objective function as a filled function, and which find a better local minimizer gradually by optimizing the filled function constructed on the minimizer previously found. Illustrative examples are provided to demonstrate the efficiency and reliability of the proposed filled function method. 相似文献
17.
The Hartley transform is an integral transformation that maps a real valued function into a real valued frequency function via the Hartley kernel, thereby avoiding complex arithmetic as opposed to the Fourier transform. Approximation of the Hartley integral by the trapezoidal quadrature results in the discrete Hartley transform, which has proven a contender to the discrete Fourier transform because of its involutory nature. In this paper, a discrete transform is proposed as a real transform with a convolution property and is an alternative to the discrete Hartley transform. Copyright © 2015 John Wiley & Sons, Ltd. 相似文献
18.
Discrete Filled Function Method for Discrete Global Optimization 总被引:6,自引:0,他引:6
A discrete filled function method is developed in this paper to solve discrete global optimization problems over strictly pathwise connected domains. Theoretical properties of the proposed discrete filled function are investigated and a solution algorithm is proposed. Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the applicability and efficiency of the proposed method. 相似文献
19.
Taogetusang Sirendaoerji 《高校应用数学学报(英文版)》2008,23(3):286-294
Based on the homogenous balance method and the trial function method, several trial function methods composed of exponential functions are proposed and applied to nonlinear discrete systems. With the.help of symbolic computation system, the new exact solitary wave solutions to discrete nonlinear mKdV lattice equation, discrete nonlinear (2 + 1) dimensional Toda lattice equation, Ablowitz-Ladik-lattice system are constructed.The method is of significance to seek exact solitary wave solutions to other nonlinear discrete systems. 相似文献
20.
Discrete global descent method for discrete global optimization and nonlinear integer programming 总被引:2,自引:0,他引:2
A novel method, entitled the discrete global descent method, is developed in this paper to solve discrete global optimization
problems and nonlinear integer programming problems. This method moves from one discrete minimizer of the objective function
f to another better one at each iteration with the help of an auxiliary function, entitled the discrete global descent function.
The discrete global descent function guarantees that its discrete minimizers coincide with the better discrete minimizers
of f under some standard assumptions. This property also ensures that a better discrete minimizer of f can be found by some classical local search methods. Numerical experiments on several test problems with up to 100 integer
variables and up to 1.38 × 10104 feasible points have demonstrated the applicability and efficiency of the proposed method. 相似文献