整数规划的一类填充函数算法

填充函数算法是求解连续总体优化问题的一类有效算法。本文改造[1]的填充函数算法使之适于直接求解整数规划问题。首先,给出整数规划问题的离散局部极小解的定义,并设计找离散局部极小解的领域搜索算法。其次,构造整数规划问题的填充函数算法。该方法通过寻找填充函数的离散局部极小解以期找到整数规划问题的比当前离散局部极小解好的解。本文的算法是直接法,数值试验表明算法是有效的。     

非线性整数规划的一个新的无参数填充函数算法

离散填充函数是一种用于求解多极值优化问题最优解的一种行之有效的方法.已被证明对于求解大规模离散优化问题是有效的.本文基于改进的离散填充函数定义,构造了一个新的无参数填充函数,并在理论上给出了证明,提出了一个新的填充函数算法.该填充函数无需调节参数,而且只需极小化一次目标函数.数值结果表明,该算法是高效的、可行的.     

NONLINEAR INTEGER PROGRAMMING AND GLOBALOPTIMIZATION

1.IntroductionAlthoughthegenerallinearintegerprogrammingproblemisNP-hard,muchworkhasbeendevotedtoit(SeeNumhauserandWolsey[1988],Schrijver[1986]).Thesolutionmethodsincludethecuttingplane,theBranch-and-Bound,thedynamicprogrammingmethodsetc..However,thegeneralnonlinearintegerprogrammingproblemisdifficulttosolve.GareyandJohnson[1979]pointedoutthattheintegerprogrammingoverRewithalinearobjectivefunctionandquadraticconstraintsisundecidable.Soifanonlinearintegerprogrammingproblemishandled,itisalw…     

求解Lipschitz型规划全局极小点的改进的填充函数法

1 引言 考虑问题 (P)min(x), x∈Ω其中F:ΩR~n→R是局部Lipschitz函数,Ω为紧集,且F(x)在Ω内有极小点。文[1,2,3]在一定条件下给出了求解一般非光滑规划全局极小点的填充函数法,并给出了求解的全过程。本文根据文[1,2,3]的思想,为求解(P),结合函数的特点,给出了一种改进     

整数线性规划的一种新的割平面法

本文提出了一种新的求解整数线性规划的割平面思路 .它利用目标函数等值面的移动来切割与(IL P)相应的 (SL P)可行域的“无用”部分 ,再通过扩大与 (SL P)最优基相应的非基变量的取值来压缩 (SL P)的可行域 ,由此求得整数线性规划的最优解 .     

全局最优化问题的一个无参数的填充函数算法

本文研究了全局最优化问题.利用构造填充函数的方法,提出了一个新的无参数填充函数,它是目标函数的一个明确表达式.得到了一个新的无参数填充函数算法,数值试验结果表明该填充函数算法是有效的,从而推广了填充函数算法在求解全局最优化问题方面的应用.     

凸整数规划最优点的判定条件

本文得到判别已知可行整值点为凸整数规划最优解的一个充分条件,此条件只涉及目标函数在该整值点为中心的边长为2的超立方体上的性态.     

A NEW SQP-FILTER METHOD PROGRAMMING FOR SOLVING NONLINEAR PROBLEMS

In [4], Fletcher and Leyffer present a new method that solves nonlinear programming problems without a penalty function by SQP-Filter algorithm. It has attracted much attention due to its good numerical results. In this paper we propose a new SQP-Filter method which can overcome Maratos effect more effectively. We give stricter acceptant criteria when the iterative points are far from the optimal points and looser ones vice-versa. About this new method, the proof of global convergence is also presented under standard assumptions. Numerical results show that our method is efficient.     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数一对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

约束全局整数规划问题的填充函数法

本文给出了一类新的求解箱约束全局整数规划问题的填充函数，并讨论了其填充性质．基于提出的填充函数，设计了一个求解带等式约束、不等式约束、及箱约束的全局整数规划问题的算法．初步的数值试验结果表明提出的算法是可行的。     

一类非线性两级整数规划问题的全局优化方法

本文研究了整数规划连续化的途径,对一类非线性两级整数规划问题的上级规划连续化以后采用模拟退火算法;其对应的下级规划问题采用离散搜索法求解,从而给出了求解一类非线性两级整数规划问题的一种全局优化算法,并通过算例验证了该算法是有效的.     

THE CONVERGENCE OF APPROACH PENALTY FUNCTION METHOD FOR APPROXIMATE BILEVEL PROGRAMMING PROBLEM

' 1 IntroductionWe collsider the fOllowi11g bilevel programndng problen1:max f(x, y),(BP) s.t.x E X = {z E RnIAx = b,x 2 0}, (1)y e Y(x).whereY(x) = {argmaxdTyIDx Gy 5 g, y 2 0}, (2)and b E R", d, y E Rr, g E Rs, A, D.and G are m x n1 s x n aild 8 x r matrices respectively. If itis not very difficult to eva1uate f(and/or Vf) at all iteration points, there are many algorithmeavailable fOr solving problem (BP) (see [1,2,3etc1). However, in some problems (see [4]), f(x, y)is too com…     

A NEW FRAMEWORK OF PRIMAL-DUAL INFEASIBLE INTERIOR-POINT METHOD FOR LINEAR PROGRAMMING*

On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear programming, we propose a new framework of primal-dual infeasible interiorpoint method for linear programming problems. Without the strict convexity of the logarithmic barrier function, we get the following results: (a) if the homotopy parameterμcan not reach to zero,then the feasible set of these programming problems is empty; (b) if the strictly feasible set is nonempty and the solution set is bounded, then for any initial point x, we can obtain a solution of the problems by this method; (c) if the strictly feasible set is nonempty and the solution set is unbounded, then for any initial point x, we can obtain a (?)-solution; and(d) if the strictly feasible set is nonempty and the solution set is empty, then we can get the curve x(μ), which towards to the generalized solutions.     

非线性二层规划问题的全局优化方法

对于下层为线性规划问题的一类非线性二层规划问题,利用线性规划的对偶理论,将其转化为一个单层优化问题,同时取下层问题的对偶间隙作为惩罚项,构造了一个相应的罚问题,然后提出了一个求解该类二层规划问题的全局优化方法。最后,数值结果表明,所提出的方法是可行的。     

连续化方法求解约束凸规划问题

1．引言大型规划问题数值求解一直是计算数学工作者感兴趣的课题之一．针对大型约束规划问题,1991年李兴斯山提出凝聚函数法,该方法用光滑的凝聚函数逼近非光滑的极大值函数,从而把多个约束函数转化为带参数的单个光滑函数约束,从而降低了问题的规模．近年来,K3］研究了凸规划问题的凝聚函数法的收敛性,在目标函数强凸性及对一般凸规划研究了收敛性质．向讨论了可行解集有界的线性规划问题的凝聚函数求解算法并证明了收效性定理．上述文章均预先把凝聚参数取得充分小,然后对固定参数的单约束近似问题进行求解．一般地,凝聚参数取得…     

一类非负二次整数规划问题的分支定界缩减方法

针对一类非负整数二次规划问题,提出了一个新的分枝定界缩减方法.在这个方法里,使用了一个新的超矩形二分技术和一个新的线性规划松弛定下界技术,同时为了提高逼近程度和加快收敛速度,使用了超矩形缩减策略.数值结果表明所提出的算法是可行的和有效的.     

选择决策的整数规划模型

在中国，决策者常常须在满足一定的均衡条件下从许多替代方案中选出一个最佳方案。本文提出了一个整数规划模型来描述这类问题，同时也给出了该模型的算法．     

多目标规划的一类基于精确罚函数的交互式方法

该文在约束集的线性化锥非空的条件下,得到了带有等式和不等式约束的多目标规划问题的精确罚函数的存在性,用原问题的二次近似在某些点上的Kuhn－Tucker乘子给出了罚因子的下界．在此基础上,利用极大熵方法的思想将罚问题转化为可微的无约束多目标规划问题并给出了求解该问题的一种交互式算法．数值结果表明：该文算法具有计算速度快、精度高、适用范围广且易于理解和使用等优点．     

一类改进的非光滑规划的填充函数法

本文考虑优化问题     

补偿随机规划的一种新数值方法

本文给出解决两阶段求援随机规划的一种新的数值方法.由于引进了新的逼近技术,该方法具有全局收敛性和局部超线性收敛性.