共查询到20条相似文献,搜索用时 138 毫秒
1.
This paper considers the nonlinearly constrained continuous global minimization problem. Based on the idea of the penalty function method, an auxiliary function, which has approximately the same global minimizers as the original problem, is constructed. An algorithm is developed to minimize the auxiliary function to find an approximate constrained global minimizer of the constrained global minimization problem. The algorithm can escape from the previously converged local minimizers, and can converge to an approximate global minimizer of the problem asymptotically with probability one. Numerical experiments show that it is better than some other well known recent methods for constrained global minimization problems. 相似文献
2.
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. 相似文献
3.
A new method is proposed for solving box constrained global optimization problems. The basic idea of the method is described as follows: Constructing a so-called cut-peak function and a choice function for each present minimizer, the original problem of finding a global solution is converted into an auxiliary minimization problem of finding local minimizers of the choice function, whose objective function values are smaller than the previous ones. For a local minimum solution of auxiliary problems this procedure is repeated until no new minimizer with a smaller objective function value could be found for the last minimizer. Construction of auxiliary problems and choice of parameters are relatively simple, so the algorithm is relatively easy to implement, and the results of the numerical tests are satisfactory compared to other methods. 相似文献
4.
带有不等式约束的非线性规划问题的一个精确增广Lagrange函数 总被引:1,自引:0,他引:1
对求解带有不等式约束的非线性非凸规划问题的一个精确增广Lagrange函数进行了研究.在适当的假设下,给出了原约束问题的局部极小点与增广Lagrange函数,在原问题变量空间上的无约束局部极小点之间的对应关系.进一步地,在对全局解的一定假设下,还提供了原约束问题的全局最优解与增广Lagrange函数,在原问题变量空间的一个紧子集上的全局最优解之间的一些对应关系.因此,从理论上讲,采用该文给出的增广Lagrange函数作为辅助函数的乘子法,可以求得不等式约束非线性规划问题的最优解和对应的Lagrange乘子. 相似文献
5.
对于一般的非线性规划给出一种精确增广Lagrange函数,并讨论其性质.无需假设严格互补条件成立,给出了原问题的局部极小点与增广Lagrange函数在原问题的变量空间上的局部极小的关系.进一步,在适当的假设条件下,建立了两者的全局最优解之间的关系. 相似文献
6.
本文给出了一类新的求解箱约束全局整数规划问题的填充函数,并讨论了其填充性质.基于提出的填充函数,设计了一个求解带等式约束、不等式约束、及箱约束的全局整数规划问题的算法.初步的数值试验结果表明提出的算法是可行的。 相似文献
7.
整数规划的一类填充函数算法 总被引:9,自引:0,他引:9
填充函数算法是求解连续总体优化问题的一类有效算法。本文改造[1]的填充函数算法使之适于直接求解整数规划问题。首先,给出整数规划问题的离散局部极小解的定义,并设计找离散局部极小解的领域搜索算法。其次,构造整数规划问题的填充函数算法。该方法通过寻找填充函数的离散局部极小解以期找到整数规划问题的比当前离散局部极小解好的解。本文的算法是直接法,数值试验表明算法是有效的。 相似文献
8.
In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable. 相似文献
9.
Steffen Rebennack Josef Kallrath Panos M. Pardalos 《Journal of Global Optimization》2009,43(2-3):277-297
We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems. 相似文献
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.
Monte Carlo methods have extensively been used and studied in the area of stochastic programming. Their convergence properties
typically consider global minimizers or first-order critical points of the sample average approximation (SAA) problems and
minimizers of the true problem, and show that the former converge to the latter for increasing sample size. However, the assumption
of global minimization essentially restricts the scope of these results to convex problems. We review and extend these results
in two directions: we allow for local SAA minimizers of possibly nonconvex problems and prove, under suitable conditions,
almost sure convergence of local second-order solutions of the SAA problem to second-order critical points of the true problem.
We also apply this new theory to the estimation of mixed logit models for discrete choice analysis. New useful convergence
properties are derived in this context, both for the constrained and unconstrained cases, and associated estimates of the
simulation bias and variance are proposed.
Research Fellow of the Belgian National Fund for Scientific Research 相似文献
12.
Gianni Di Pillo Giampaolo Liuzzi Stefano Lucidi Laura Palagi 《Computational Optimization and Applications》2003,25(1-3):57-83
This paper is aimed toward the definition of a new exact augmented Lagrangian function for two-sided inequality constrained problems. The distinguishing feature of this augmented Lagrangian function is that it employs only one multiplier for each two-sided constraint. We prove that stationary points, local minimizers and global minimizers of the exact augmented Lagrangian function correspond exactly to KKT pairs, local solutions and global solutions of the constrained problem. 相似文献
13.
非线性整数规划问题是一类复杂的优化问题,填充函数算法是求解整数规划问题的一类有效方法.构造一个新的单参数填充函数,分析并证明了其填充性质;然后,基于该填充函数并结合离散最速下降法提出了一种新的填充函数算法;最后,采用新算法对6个测试函数进行数值实验,结果表明该算法具有良好的计算效果,是有效可行的. 相似文献
14.
In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained
optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence
between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling
probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace.
Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity
as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each
independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically
converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional
simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete
constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned
nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization
benchmarks and compare their performance to that of other penalty methods. 相似文献
15.
本文通过给出的一个修正的罚函数,把约束非线性规划问题转化为无约束非线性规划问题.我们讨论了原问题与相应的罚问题局部最优解和全局最优解之间的关系,并给出了乘子参数和罚参数与迭代点之间的关系,最后给出了一个简单算法,数值试验表明算法是有效的. 相似文献
16.
本文探讨了一类N车探险问题的近似算法,首先通过建模将N车问题转变为一个等价的非线性0-1混合整数规划问题,进而将该非线性0-1混合整数规划问题转化为一个一般的带约束非线性规划问题,并用罚函数的方法将得到的带约束非线性规划问题化为相应的无约束问题.我们证明了可通过求解该无约束非线性规划问题得到原N车问题的ε-近似度的近似解,并设计了-个收敛速度为二阶的迭代箅法,文章最后给出算法实例. 相似文献
17.
This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer
constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and
discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without
duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual
solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is
equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique.
Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm
is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite
programming method is revealed. 相似文献
18.
1.IntroductionAlthoughthegenerallinearintegerprogrammingproblemisNP-hard,muchworkhasbeendevotedtoit(SeeNumhauserandWolsey[1988],Schrijver[1986]).Thesolutionmethodsincludethecuttingplane,theBranch-and-Bound,thedynamicprogrammingmethodsetc..However,thegeneralnonlinearintegerprogrammingproblemisdifficulttosolve.GareyandJohnson[1979]pointedoutthattheintegerprogrammingoverRewithalinearobjectivefunctionandquadraticconstraintsisundecidable.Soifanonlinearintegerprogrammingproblemishandled,itisalw… 相似文献
19.
Le Thi Hoai An Pham Dinh Tao Nam Nguyen Canh Nguyen Van Thoai 《Journal of Global Optimization》2009,44(3):313-337
We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function
in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming
problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known
in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported. 相似文献
20.
One of the challenging optimization problems is determining the minimizer of a nonlinear programming problem that has binary
variables. A vexing difficulty is the rate the work to solve such problems increases as the number of discrete variables increases.
Any such problem with bounded discrete variables, especially binary variables, may be transformed to that of finding a global optimum of a problem in continuous variables. However, the transformed problems usually have astronomically large numbers
of local minimizers, making them harder to solve than typical global optimization problems. Despite this apparent disadvantage,
we show that the approach is not futile if we use smoothing techniques. The method we advocate first convexifies the problem
and then solves a sequence of subproblems, whose solutions form a trajectory that leads to the solution. To illustrate how
well the algorithm performs we show the computational results of applying it to problems taken from the literature and new
test problems with known optimal solutions. 相似文献