共查询到20条相似文献,搜索用时 437 毫秒
1.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献
2.
一类值型双层凸规划的Johri一般对偶 总被引:1,自引:0,他引:1
本文首先给出一类特殊的值型凸二次双层规划一其下层子规划只含有线性约束(简记为VBCP);然后证明了一般形式的VBCP可以等价变换为非增值型凸二次双层规划的形式;最后给出该类双层规划VBCP的Johri对偶规划及其对偶性质. 相似文献
3.
本文提出一种基于最优D.C.分解的单二次约束非凸二次规划精确算法.本文首先对非凸二次日标函数进行D.C.分解,然后对D.C.分解中凹的部分进行线性下逼近得到一个凸二次松弛问题.本文证明了最优D.C.分解可通过求解一个半定规划问题得到,而原问题的最优解可以通过计算最优凸二次松弛问题的满足某种互补条件的解得到.最后,本文报告了初步数值计算结果. 相似文献
4.
一类反凸规划的全局新算法 总被引:2,自引:0,他引:2
§1.引言 到目前为止,大多数非线性规划的有效算法都是寻求它的局部最优解,由于很难判断一个局部解是否就是一个全局解,全局规划的研究是个困难问题,反凸规划由于其可行域的非凸性甚至非连通性,目前有效算法更少。 [1]已经指出很容易把D.C.规划(即目标函数和约束函数均为二个凸函数之差)转化成为一个目标函数为线性的反凸规划: 相似文献
5.
针对一类生化系统的稳态优化问题,建立了一种具有二层递阶结构的双层规划优化模型,其上层和下层问题的优化目标分别为最大化产物产率(或代谢物浓度)和最小化生化系统的代谢物浓度之和.模型的生物意义是在尽可能小的代谢成本条件下使产物的产率或浓度达到最大.为了有效求解所建立的NP-hard、非凸双层规划问题,在S-系统建模框架下应用等价变换策略提出了一种可求其最优解的优化算法.算法具有操作简便和计算成本低的优点.最后,将所提双层规划模型与求解方法应用于两个生化系统的稳态优化中.结果表明,方法可行且有效. 相似文献
6.
根据广义乘子法的思想,将具有等式约束和非负约束的凸二次规划问题转化只有非负约束的简单凸二次规划,通过简单凸二次规划来得到解等式约束一非负约束的凸二次规划新算法,新算法不用求逆矩阵,这样可充分保持矩阵的稀疏性,用来解大规模稀疏问题,数值结果表明:在微机486/33上就能解较大规模的凸二次规划。 相似文献
7.
8.
9.
本文提出一类基于DC分解的非凸二次规划问题SDP松弛方法,并通过求解一个二阶锥问题得到原问题的近似最优解.我们首先对非凸二次目标函数进行DC分解,然后利用线性下逼近得到一个凸二次松弛问题,而最优的DC分解可通过求解一个SDP问题得到.数值试验表明,基于DC分解的SDP近似解平均优于经典SDP松弛和随机化方法产生的近似解。 相似文献
10.
给出了粒子群算法中惯性权值和学习因子的一种简单改进,并将其应用到非凸二次规划的求解中,通过数值试验与现有的求解非凸二次规划问题的分支定界法进行了比较,得到了较好的结果. 相似文献
11.
1. IntroductionA bilevel programming problem (BLPP) involves two sequential optimization problems where the constraint region of the upper one is implicitly determined by the solutionof the lower. It is proved in [1] that even to find an approximate solution of a linearBLPP is strongly NP-hard. A number of algorithms have been proposed to solve BLPPs.Among them, the descent algorithms constitute an important class of algorithms for nonlinear BLPPs. However, it is assumed for almost all… 相似文献
12.
基于粒子群算法的非线性二层规划问题的求解算法 总被引:3,自引:0,他引:3
粒子群算法(Particle Swarm Optimization,PSO)是一种新兴的优化技术,其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最好解和整个群的最好解来完成优化。该算法简单易实现,可调参数少,已得到了广泛研究和应用。本文根据该算法能够有效的求出非凸数学规划全局最优解的特点,对非线性二层规划的上下层问题求解,并根据二层规划的特点,给出了求解非线性二层规划问题全局最优解的有效算法。数值计算结果表明该算法有效。 相似文献
13.
In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem. 相似文献
14.
Parametric global optimisation for bilevel programming 总被引:2,自引:2,他引:0
Nuno P. Faísca Vivek Dua Berç Rustem Pedro M. Saraiva Efstratios N. Pistikopoulos 《Journal of Global Optimization》2007,38(4):609-623
We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based
on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s)
problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables
of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem
is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved
to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without
right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global
optimisation strategy. 相似文献
15.
A neural network is proposed for solving a convex quadratic bilevel programming problem. Based on Lyapunov and LaSalle theories, we prove strictly an important theoretical result that, for an arbitrary initial point, the trajectory of the proposed network does converge to the equilibrium, which corresponds to the optimal solution of a convex quadratic bilevel programming problem. Numerical simulation results show that the proposed neural network is feasible and efficient for a convex quadratic bilevel programming problem. 相似文献
16.
In this paper we propose an optimal method for solving the linear bilevel programming problem with no upper-level constraint. The main idea of this method is that the initial point which is in the feasible region goes forward along the optimal direction firstly. When the iterative point reaches the boundary of the feasible region, it can continue to go forward along the suboptimal direction. The iteration is terminated until the iterative point cannot go forward along the suboptimal direction and effective direction, and the new iterative point is the solution of the lower-level programming. An algorithm which bases on the main idea above is presented and the solution obtained via this algorithm is proved to be optimal solution to the bilevel programming problem. This optimal method is effective for solving the linear bilevel programming problem. 相似文献
17.
18.
Exact Penalty Functions for Convex Bilevel Programming Problems 总被引:2,自引:0,他引:2
Liu G. S. Han J. Y. Zhang J. Z. 《Journal of Optimization Theory and Applications》2001,110(3):621-643
In this paper, we propose a new constraint qualification for convex bilevel programming problems. Under this constraint qualification, a locally and globally exact penalty function of order 1 for a single-level reformulation of convex bilevel programming problems is given without requiring the linear independence condition and the strict complementarity condition to hold in the lower-level problem. Based on these results, locally and globally exact penalty functions for two other single-level reformulations of convex bilevel programming problems can be obtained. Furthermore, sufficient conditions for partial calmness to hold in some single-level reformulations of convex bilevel programming problems can be given. 相似文献
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.
Descent approaches for quadratic bilevel programming 总被引:7,自引:0,他引:7
The bilevel programming problem involves two optimization problems where the data of the first one is implicitly determined by the solution of the second. In this paper, we introduce two descent methods for a special instance of bilevel programs where the inner problem is strictly convex quadratic. The first algorithm is based on pivot steps and may not guarantee local optimality. A modified steepest descent algorithm is presented to overcome this drawback. New rules for computing exact stepsizes are introduced and a hybrid approach that combines both strategies is discussed. It is proved that checking local optimality in bilevel programming is a NP-hard problem.Support of this work has been provided by INIC (Portugal) under Contract 89/EXA/5, by FCAR (Québec), and by NSERC and DND-ARP (Canada). 相似文献