一、一类线性约束凸规划的几种多项式算法的研究(论文文献综述)
吴铮[1](2021)在《动约束函数的构造及其在非凸优化中的应用》文中认为动约束组合同伦方法是求解非凸规划问题的一种有效方法,该方法不要求初始点是可行集的内点,相比于“拟法锥条件”、“伪锥条件”下求解非凸规划问题的修正组合同伦内点法,同伦映射的构造更加容易,所给条件更弱、更便于应用.其中,动约束组合同伦方法的关键在于动约束函数如何进行构造.本文基于特定的一类非凸域给出了动约束函数的具体构造方法,利用在原约束函数中添加参数t的方式,使原约束函数变成含参变量t的函数,且满足随参数t的变化,含参变量约束函数构成的可行域可由凸可行域连续形变到原非凸可行域.首先,针对多尖非凸域和星型非凸域的约束函数进行构造,在对星型非凸域约束函数构造的过程中,分别从不同情况下对约束函数进行了构造.其次,在较弱的条件下证明了以上动约束函数满足边界正则性条件以及法锥条件.最后,通过数值例子表明该构造方法是可行的、有效的.
李丽丹[2](2020)在《几类二次规划逆问题的有效数值方法》文中提出对于一个连续优化模型来说,通常它由两部分变量构成,一部分变量是参数变量,另一部分变量是决策变量.所谓一个正问题,即当参数变量已知时进而来求解最优决策变量的值.而有些实际情况往往是无法得到参数变量的准确值,却能得到该问题的参数估计值及最优决策变量值,逆优化问题即是求解参数变量值,使得在满足给定的最优解仍为问题的解的前提下,与估计参数的距离最小.在本论文中我们主要研究了两类二次规划逆问题及一类半定二次规划逆问题的求解.其主要内容概括如下:1.论文的第3章考虑了一类带l1范数度量的二次规划逆问题,我们将该问题整理为一个含有半正定锥约束的最小化问题.利用凸优化理论,将该问题的一阶最优性条件改写为一个广义方程.在非常简单的假设下,证明了该方程在其最优解处的广义雅可比元素都是非奇异的.由此,我们构造了带Armijo线搜索的非精确牛顿法来求解方程,并给出算法的全局收敛性定理.最后,给出了该牛顿方法有效性的数值实验.2.论文的第4章研究了在矩阵谱范数与向量l∞范数度量之下的一类二次规划逆问题.先将该问题转化为目标函数为可分离变量的凸优化问题,提出用Gauss回代交替方向法求解该问题.并结合奇异值阈值算法,Moreau-Yosida正则化算法,matlab优化工具箱的quadprog函数来求解相应的子问题.而对于第一个子问题的求解过程中发现其仍是目标函数可分离变量的凸优化问题,所以我们分别采用了精确和非精确的交替方向法求解该子问题.最后给出采用Gauss回代交替方向法求解问题的收敛性分析以及数值实验.数据表明,本文所采用的方法能够有效地解决该二次规划逆问题.3.论文的第5章考虑了一个带l1范数度量的半定二次规划逆问题,它是包含两个半正定锥约束的l1向量范数的极小化问题.利用凸优化理论,将该问题的求解转化为求解一个半光滑方程.在两个假设下,证明该方程在其解处的广义雅克比的任何元素都是非奇异的.在此基础上,给出了光滑逼近算子,提出了求解半光滑方程的光滑化牛顿法.最后给出数值结果,表明了光滑牛顿法求解该逆问题的有效性与稳定性.
张彦微[3](2018)在《一种基于Freudenthal单纯形细分的二次规划方法》文中提出二次规划是一种以二次函数为目标函数,以线性函数为约束的极值问题,它是一种包含了线性规划的特殊形式的非线性规划。二次规划问题是一种典型的优化问题,与经济数学、管理科学等问题有着密切的联系,并在金融、生产制造等领域内有着广泛和重要的应用。本文针对凸二次规划问题的对偶解法进行了研究。首先,利用Glover、Greenberg和Pierskalla提出的不等式约束非线性规划的代理约束及代理对偶问题的解法,推导二次规划的代理对偶问题。每一个约束都乘上一个不小于0的代理乘子,这些乘子之和为1。每个乘子的大小代表其所对应约束的积极或有效程度。如果某一乘子为0则表示其所对应的约束为无效约束。把所有乘上代理乘子的约束相加形成一个约束,即为代理约束。通过推到,得出了一个目标函数为显式分式形式表达的代理对偶问题,其约束仅为一个单纯形函数。其次,对显示的目标函数进行分析,分式的分子和分母均为凸函数,因此构成的目标函数无法确定是凸函数还是凹函数,因此构成了一个非凸规划问题。第三,鉴于对偶问题的约束仅为一个单纯形,提出一种基于Freudenthal单纯形细分的优化方法,通过使用Freudenthal的细分方法,对单纯形进行均匀细分,得到各细分节点的坐标值,把坐标值带入目标函数,确定最大值,实现二次函数的全局优化。最后,通过二次规划例题对提出的方法进行了验证。提出的方法对约束数目小于自变量数目的二次规划问题求解非常有效,因为对偶问题的自变量数是原问题的约束数。但对于约束数大的二次规划问题,会导致对偶问题的约束是一个高维的单纯形,方法求解效率不高。因为在提高精度的要求下,必须把单纯形划分得非常细,带来了较大的计算量。因此下一步工作是结合分支定界方法,通过先粗分,再在小范围内细分的办法来加以解决。
白婷[4](2018)在《基于异质性时间价值和拥堵费用预算的交通分配与拥堵收费问题研究》文中进行了进一步梳理时间价值和拥堵费用预算都是收费网络中影响出行者道路选择的重要经济参数,它们与道路使用者的收入水平、出行目的等密切相关,直接影响出行行为,进而影响整体路网的流量分布即拥堵收费方案的效果。在之前的研究中,关于时间价值的异质性对交通分配与拥堵收费的影响都已经讨论过,而基于拥堵费用预算异质性的研究较少。拥堵费用预算的定义与一些研究中提到的“心理预算”有相似之处。考虑到出行者出行时可调度资金的有限性、用户不同种类心理账户余额不可互换性以及不同出行者对于花费在拥堵费上的心理承受能力不同,出行者的拥堵费用预算确实对出行者的交通出行行为产生重要影响,且存在异质性。这种影响与时间价值一起,影响出行者对同一拥堵收费方案的不同反应。本文的创新点在于提出了拥堵费用预算对交通分配模型和拥堵收费方案的影响,并把时间价值和拥堵费用预算两个出行者特征要素同时融入到模型中,并考虑了异质拥堵费预算以及两者都为异质性的情况。以往的研究人员并没有对此进行研究。本文主要目的是提供收费网络交通需求流量分布预测的模型和算法工具以及对应的最优拥堵收费方案。首先,假定所有出行者拥有共同的时间价值,我们定义了用户均衡准则,提出了基于异质性拥堵费用预算的网络均衡问题并提出了这一问题的数学模型。随后,使用弗兰克-沃尔夫算法解决了这一问题。使用弗兰克-沃尔夫算法解决这一问题的难点在于网络负载子模型的解决方案,我们提出一个基于异质性拥堵费用预算的网络流负载方法解决了这一问题。在此基础上,通过对系统最优交通流模式最优解的推导,验证了异质性拥堵费用预算条件下第一最优拥堵收费方案的存在。需要注意的是,此时用于计算第一最优拥堵费用的系统最优交通流量应该是基于异质性收费预算的交通流量。在这个模型中,我们假设时间价值是同质的,然而,由于个人收入水平、出行目的、对节约资金的偏好性等因素的不同,时间价值也是异质的,因此,产生了本文第二个模型,基于异质性时间价值与拥堵费用预算的网络均衡问题与拥堵收费方案。在此之前,没有研究同时考虑这两个因素的异质性对网络流均衡问题的影响。由于数学模型的凸性,我们仍可以采用弗兰克-沃尔夫算法解决这一问题,与第一个模型对应算法的最大区别在于网络负载过程中的需求分配,我们提出一个三阶段网络负载方法。通过算例分析,验证本文的模型和算法的有效性,研究异质性时间价值与拥堵费用预算对交通网络流模式的影响和改变。随后,给出了一个考虑拥堵收费预算基于时间差的最优拥堵收费方案及其存在的充分条件。
聂嘉明[5](2017)在《线性约束下的组合优化问题研究》文中研究指明组合优化是运筹学的一个重要研究分支,包含很多经典问题,如排序问题、网络流问题、背包问题、装箱问题等。每个组合优化问题都有各自的参数,如排序问题中工件的加工时间、背包问题中物品的权重和价值、装箱问题中物品的大小等。在传统的组合优化研究中,这些参数一般独立于问题的决策,由外部环境预先给定。在实际的应用中,决定这些参数往往也是一个需要优化的问题,例如参数需要满足一些资源的约束或满足一定的供求关系。本文研究一些线性约束下的经典组合优化问题,即组合优化问题的参数需要满足一些线性约束,因此也是决策的一部分。本文研究的问题包括线性约束下的排序问题、线性约束下的背包问题、线性约束下的装箱问题等。这些问题具有全新的结构,在实际生活中有广泛的应用场景,蕴含着丰富的研究内容,但文献中却很少有相关的研究。本文首先给出了这些线性约束下的组合优化问题的具体模型,提供它们的研究动机和实际背景。很多线性约束下的组合优化问题,都能自然地表示成一些复杂的数学规划问题,如混合双线性规划问题。一般而言,这些数学规划问题都是十分困难的,不容易直接应用它们的结论去求解本文研究的问题。利用线性规划和组合优化的技术,本文分析这些问题的计算复杂性和提出相应的算法。本文通过研究发现,有一些原来困难的组合优化问题,例如平行机排序问题、装箱问题等,其线性约束下的问题在某些情况下,如约束的个数并不多时是多项式可解的;也有一些原来可解的组合优化问题,例如不含负权的最短路问题等,其线性约束下的问题一般情况下是困难和难以近似的。本文主要的创新点总结如下:1.根据实际应用需要,提出了线性约束下的组合优化问题的概念,并建立了一系列线性约束下的经典组合优化问题。2.探索线性约束下的组合优化问题的结构与性质,并建立它们与线性规划、经典组合优化问题的联系。3.分析这些问题在不同情形下的计算复杂性,并设计相应的多项式时间算法或近似算法。
陈涵[6](2017)在《柔性运动系统能量与振动同步优化的轨迹规划方法研究》文中指出柔性伺服运动系统普遍存在于工业装备中,轨迹规划是影响其运动性能的关键环节。随着工业装备在满足高速高精的同时追求节能降耗,柔性运动系统的能量与振动同步优化(energy-vibration-optimal,EVO)诉求突显,通过轨迹规划方法降低柔性运动系统能耗和振动具有重要意义。本文面向柔性运动系统的点到点轨迹规划问题,以抑制柔性结构振动与降低系统能耗为目标,对EVO轨迹的全局最优化方法、鲁棒性优化方法以及在线实现方法展开研究。为实现柔性运动系统在零振动前提下能耗最优,提出一种基于零残余振动能约束的全局最优EVO轨迹规划方法。该方法的问题模型通过零残余振动能约束在能量维度下统一了能耗与振动性能指标,同时满足了抑振优先于节能的实际应用需求;通过凸化和离散化,提出基于凸二次规划的问题求解算法,可保证收敛到全局最优解;结合Hamilton方法与残余振动能精确数值约束,进一步提升了算法的求解精度与效率。为解决模型参数摄动引起的性能恶化问题,提出一种基于时/频残余振动能敏感度约束的EVO轨迹鲁棒性优化方法。该方法证明了时域残余振动能敏感度约束等价于在频域柔性系统极点处的二重零点,建立了频域零点与时域约束间的联系;借鉴频域鲁棒滤波器的零点设计思想,给出二重、单鼓包和多鼓包的零点排布策略及对应的时域约束,可提升参数摄动界内的轨迹鲁棒性。为减小EVO轨迹计算耗时以便于实际应用,针对广泛使用的梯形与S形轨迹,分别提出一种在线EVO轨迹规划方法。该方法在梯形和S形轨迹的参数空间内分别简化全局最优和鲁棒EVO轨迹规划问题模型,得到基于轨迹参数的非线性整数规划问题;分别提出基于连续松弛法与基于近似极值点附近枚举法的求解算法,该算法仅含解析算式和一维搜索,计算快速。以单关节柔性铰链机械臂为对象,对所提的EVO轨迹规划方法进行仿真和实验验证。相较传统轨迹,全局最优EVO轨迹抑制了96%振动,同时降低了25%能耗;鲁棒EVO轨迹在模型参数摄动±20%时仍能抑制90%振动,节能性能仅牺牲13%;梯形和S形EVO轨迹则以牺牲一定节能与抑振性能为代价,换取了计算快速性——计算耗时约160?s,可在线实现。
戴彧虹,刘新为[7](2014)在《线性与非线性规划算法与理论》文中研究表明线性规划与非线性规划是数学规划中经典而重要的研究方向.主要介绍该研究方向的背景知识,并介绍线性规划、无约束优化和约束优化的最新算法与理论以及一些前沿与热点问题.交替方向乘子法是一类求解带结构的约束优化问题的方法,近年来倍受重视.全局优化是一个对于应用优化领域非常重要的研究方向.因此也试图介绍这两个方面的一些最新研究进展和问题.
龚小玉[8](2013)在《互补问题最优化算法研究及其应用》文中提出最优化理论与算法是一门广泛应用的学科,它主要讨论决策问题的最佳选择之特性,并构造寻求最佳的计算方法,以及研究这些计算方法的理论性质和实际计算效果。数学规划是最优化理论的一个重要分支,和其它数学分支相比,它是一门非常年轻但又十分活跃的应用数学分支。而互补问题又是另外一类相当广泛的数学模型。事实上,许多实际问题的数学模型其实就是一个特殊的互补问题,并且经典的线性规划问题与非线性问题都可以转化为互补问题来进行求解计算。1947年,Danzig提出了线性规划的概念及其着名的单纯型算法,该算法在实际计算过程中具有良好的计算性能,但从理论上来讲其复杂性并不理想,主要原因是随着问题规模的扩大,算法迭代次数迅速增长,这给实际计算带来很大的麻烦。受计算复杂性理论的影响,很多学者曾在很长一段时间内,希望通过证明单纯形法具有多项式时间算法。但是,Klee和Minty在1972年通过举反例,证明了单纯形算法法它并不是一个多项式算法,这样线性规划问题是否存在多项式算法就成为众多学者迫切想知道的问题。接下来,在1979年,Khachiyan针对线性规划问题是否为多项式算法的这一困惑,提出了着名的“椭球算法”,该算法是线性规划的第一个多项式算法,但是此算法的理论上的优势并不能在实际计算性能上超越单纯形算法法,这就引起了众多学者试图再去寻找另外一种新的具有较好实际计算性能的线性规划的多项式算法。直到1984年,Karmarkar的“投影尺度算法”使得线性规划算法出现了真正的突破,这种新算法不仅在理论上优越于单纯形算法,而且也显示出对求解大规模实际问题的巨大潜力。Karmarkar算法再一次真正不同于单纯形算法(单纯性算法是从可行域的一个顶点迭代到另外一个顶点,直到达到问题的最优解),而Karmarkar算法它是从可行域的内部沿着某个方向逼近问题的最优解,所以有时候也称为“内点算法”。经过众多学者对Karmarkar内点算法的深入探讨与研究,现在已经发展成最具有代表性的有三类:势函数下降投影变换方法(即Karmarkar内点算法)、仿射均衡变换方法和原始-对偶跟踪中心轨迹方法。虽然这三大类内点算法具有很强的计算效果,但是现有可行内点算法也并非完美无缺,其中最突出的问题是,由其计算复杂性分析所得出的多项式时间界限不能作为衡量一个算法好坏的唯一依据,其原因如下:其一,小步长(窄邻域)原始-对偶内点算法的多项式复杂性为O((?)nlog(n/ε)),远远低于大步长(宽邻域)原始-对偶内点算法的复杂性O(n log(n/ε)).但是在实际的计算效果上,前者计算效果比后者差很多(主要原因是小步长算法较大步长算法极大的限制了步长的选取)。针对这种不一致现象,在90年代,Ye和Huang提出了一种高阶(r阶)预估校正原始-对偶大步长(宽邻域)内点算法,将算法的迭代复杂性降到O(n(r+1)/(2r)L),其中r∈[1,n)。可以看出,当r=n时,该算法的迭代复杂性近似变为O(√nL)。而其他基于高阶内点算法来降低大步长(宽邻域)原始-对偶内点算法的工作也有一些。比如,Peng等人通过定义自正则(Self-Regular)邻近度量,用这种新的分析工具将大步长(宽邻域)内点算法的多项式时间复杂性降低到O(nq+1/2qlog(n/ε))其中q>1。2006年,Pan等人通过分析发现,上述自正则邻近度量方法在证明上面的结论时所使用的牛顿方向,是通过对“中心方程”用一个等价的幂等变换得到。虽然这种幂函数变换从代数意义上讲等价的,但是到达最优解的速度却不一样,而且也容易理解。因此,基于适当的代数等价变换,也可以达到降低原始-对偶内点算法的计算复杂性的效果。其二,就是可行内点算法在初始迭代点选取上太过于苛刻,既要满足严格等式约束又要满足非负约束条件,并且在实际问题中这种初始点的选取很难获得,而不可行内点算法却放松了这一条件,只要在迭代开始时满足非负条件,而不再需要满足等式约束。这一放松大大降低了初始可行点在选取上的困难性。因此,不可行内点算法在处理实际问题中被广泛应用。本文主要分为理论和应用两大部分。第一部分(第二章到第五章),理论部分主要利用优化算法解决一些理论上存在的问题,比如大步长与小步长在迭代与计算复杂性上的矛盾以及初始可行点在选取上的困难等;第二部分(第六、七章)是利用优化算法解决一些实际问题,如利用之前的内点算法中的路径跟踪算法和仿射尺度算法解决双矩阵对策问题以及利用优化问题和演化博弈算法解决农村合作组织中的经济问题,通过编程简单的模拟算法的迭代过程以及最后的稳定状态。在理论部分,首先在前人的研究基础上,将P矩阵线性互补问题高阶内点算法推广到更一般的P.(k)阵高阶线性互补问题中去,并基于不同的邻域(大步长和小步长)讨论了算法的复杂性。其次,基于代数等价变换的思想以及KMM算法的框架,对P0阵线性互补问题提出了新的原始-对偶不可行内点算法。该算法的创新点首先是基于KMM算法的框架,该算法在处理不可行内点算法结构上很简单,其次就是利用一个特殊的代数等价代换,因此在复杂性上较之前的算法有了很大改进,主要体现在代数等价变换上,虽然从代数的角度上是等价的,但是达到最优解的速度却不相同,可以在后面的数值试验中体现出来。最后,在前人的研究基础上,将线性规划问题推广到更一般的互补问题中去,分别讨论了基于核函数求解线性互补问题和非线性互补问题的不可行内点算法并证明了其计算具有多项式复杂性,在讨论非线性互补问题时,在前人研究的基础上,构造了一个新的核函数,利用该函数来衡量算法是否达到最优解,最后证明算法经过次迭代达到问题的最优解。第二部分为应用部分,由于互补问题是一类非常重要的优化问题,它广泛应用在经济分析、交通平衡策略等社会经济模型中。因此,对互补问题的研究具有十分重要的现实意义。所以,本文第六章以博弈论理论为基础,探讨了线性互补问题在经济学中的双矩阵博弈中的应用,并提炼出了两个典型双矩阵博弈实例(囚徒困境博弈和监察博弈),借鉴线性互补问题中的势函数下降法和中心路径跟踪算法有效的解决了上述实例。其次是利用演化博弈理论和最优化算法探求农村合作组织的合作机制,建立了异质农民群体(具有组织管理才能与影响力的阶层与普通农民阶层)在农村合作组织运行的演化博弈模型,局中人根据前一轮合作的结果,通过模仿或学习调整下一轮是否合作的博弈对策,逐步寻求演化稳定均衡解。为了求出演化稳定均衡解提出了一种新的演化博弈算法。该算法的基本思想是将最优化问题的搜索空间映射到博弈论中的策略组合空间中去,目标函数f映射到博弈论的效用函数,通过不完全理性博弈主体的达到局部稳定均衡状态,根据据局部均衡结果博弈主体调整各自对策,进行下一轮博弈,搜寻到更优的均衡,最终达到演化稳定均衡解,从而求解出实际问题的进化稳定状态。
李学良[9](2012)在《炼油厂混合整数二次规划调度模型的算法研究》文中研究指明二次规划问题,作为运筹学中一种特殊类型的最优化问题,在最优化理论中有着十分重要的研究意义。二次规划问题在现实生活中有着广泛的应用背景,如经济、金融、图象处理、化工、工程控制、分子生物学、环境工程学等领域。二次规划无论是在局部优化问题还是在全局优化问题的研究中,始终是研究的重要课题之一。炼油厂混合整数二次规划调度模型是一类大规模的优化问题,其求解算法的研究具有理论意义和实用价值。本文从炼油行业动态规划过程入手,对其中的一类炼油厂动态调度模型进行分析,并根据分析结果对二次规划的一个分支——半正定二次规划问题进行讨论与研究。一个规划问题可以转化成等价的凸规划问题,而且只需使用一种求解局部极小值的方法就可得到整个问题的全局最优解。所以,本文将沿着这个方向,提出一种基于改进的内点法和分支定界算法的混合算法。首先,将对数罚函数法和拟Newton算法有效结合,将约束问题转化为无约束问题,采用Wolf-Powell线搜索确定步长,避免了搜索步长过小的问题。之后,对算法的收敛性进行分析,通过设定合理的停止准则,使算法经过有限步的迭代后终止。使用改进的牛顿内点法对松弛问题进行求解后,针对原函数特点,本文制定了特殊的分支策略,使改进的分支定界法能够有效率地获取满足整数约束条件的可行解,根据凸规划自身的特性,即可得到原问题的最优解。最后,利用本文设计的混合优化算法对实际生产中的炼油厂混合整数二次规划动态调度模型进行求解。与现有的同类算法比较表明了本文所提算法的有效性。
杨吉祥[10](2012)在《低群延迟误差IIR数字滤波器的minimax设计方法》文中进行了进一步梳理随着计算机和微电子等学科的飞速发展,数字信号处理的理论、算法以及实现手段都获得了较快的发展,并且在各个领域中得到广泛应用。数字滤波是数字信号处理的重要环节,数字滤波器设计则是数字信号处理的基本任务。本论文考虑无限冲激响应(IIR)数字滤波器的设计问题,主要研究具有低群延迟误差的IIR数字滤波器的minimax设计。为了得到具有低群延迟误差的IIR数字滤波器,本论文没有对群延迟误差直接进行约束,而是对相位误差进行了约束,这样便构成了带相位误差约束的IIR数字滤波器minimax设计问题。本论文应用序列约束最小二乘方法把此约束minimax设计问题转化为一系列约束最小二乘设计子问题,并用L-SK策略和泰勒级数展开处理子问题中的目标函数和频率响应误差约束条件的非凸性以及相位误差约束的非线性问题,把问题转化为一系列具有圆约束和线性约束的二次规划问题。本论文在介绍了IIR数字滤波器及其设计的研究现状,回顾和总结了已有IIR数字滤波器minimax设计算法之优缺点的基础上,重点在以下三个方面开展了研究工作,并取得了一定的进展:1.研究了IIR数字滤波器minimax设计的序列约束最小二乘方法,以及减小滤波器群延迟误差的相位误差上界函数方法。序列约束最小二乘方法的主要思想是,把IIR数字滤波器的minimax设计转化为一系列约束最小二乘问题,以此增大获得更好数字滤波器的可能性。减小滤波器群延迟误差的相位误差上界函数方法,则是通过选择合适的相位误差上界函数来控制群延迟误差,特别是减小通带边缘附近的群延迟误差的一种有效方法。2.提出了IIR数字滤波器相位误差约束minimax设计的序列约束最小二乘方法,并应用S形相位误差上界函数有效地减小了滤波器的最大群延迟误差。在IIR数字滤波器minimax设计问题中,引入相位误差约束。应用序列约束最小二乘方法、L-SK策略和泰勒展开,把非凸的相位误差约束minimax设计问题转化为一系列圆形和线性约束二次规划问题。设计例子表明,在适当的S形相位误差上界函数下,所提设计方法得到了比现有方法小得多的群延迟误差和相对较小的相位误差。3.提出了减小IIR数字滤波器最大群延迟误差的相位误差上界函数自动更新方法。S形相位误差上界函数方法能够有效地减小滤波器的最大群延迟误差,但S形相位误差上界函数的选择需人工进行。本论文把有限冲激响应(FIR)滤波器设计中减小群延迟误差的相位误差上界函数自动更新方法应用到IIR数字滤波器的设计,取得了很好的设计效果,扩展了减小群延迟误差的相位误差上界函数方法的应用。
二、一类线性约束凸规划的几种多项式算法的研究(论文开题报告)
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、一类线性约束凸规划的几种多项式算法的研究(论文提纲范文)
(1)动约束函数的构造及其在非凸优化中的应用(论文提纲范文)
摘要 |
Abstract |
第1章 绪论 |
1.1 研究背景及意义 |
1.2 国内外研究现状 |
1.3 本文研究内容与结果 |
1.4 结构安排 |
第2章 预备知识 |
2.1 解优化问题的组合同伦法 |
2.2 求解优化问题的动边界组合同伦法 |
2.2.1 求解非线性规划问题的动边界组合同伦法 |
2.2.2 求解多目标规划问题的动约束组合同伦法 |
第3章 动约束函数的构造方法 |
3.1 多尖非凸域的动约束函数构造 |
3.2 非凸非光滑区域动约束构造方法(星形区域动约束函数构造方法) |
3.2.1 星型非凸可行域转化为多尖非凸域 |
3.2.2 多尖非凸域转化为凸四边形区域 |
3.2.3 多尖非凸域凝聚成光滑非凸可行域 |
第4章 动约束构造在非凸优化中的应用 |
4.1 同伦算法 |
4.2 多尖非凸域数值算例 |
4.3 星型非凸域数值算例 |
第5章 总结与展望 |
致谢 |
参考文献 |
作者简介 |
攻读硕士学位期间研究成果 |
附录 |
(2)几类二次规划逆问题的有效数值方法(论文提纲范文)
摘要 |
abstract |
1 绪论 |
1.1 逆问题简介 |
1.2 逆优化问题的研究现状 |
1.3 本论文的主要内容 |
2 预备知识 |
2.1 变分分析中的基本概念和结论 |
2.2 算法的基本思想 |
2.2.1 非精确牛顿法 |
2.2.2 Gauss回代交替方向法 |
3 一类l_1向量范数度量的二次规划逆问题 |
3.1 引言 |
3.2 问题重建 |
3.3 带Armijo线搜索的非精确牛顿法求解方程 |
3.4 数值实验 |
3.5 本章小结 |
4 Gauss回代交替方向法求解一类二次规划逆问题 |
4.1 引言 |
4.2 Gauss回代交替方向法求解逆问题 |
4.2.1 求解ADM步中的第一个子问题 |
4.2.2 求解ADM步中的第二个子问题 |
4.2.3 求解ADM步中的第三个子问题 |
4.3 收敛性分析 |
4.4 数值实验 |
4.5 本章小结 |
5 一类l_1向量范数度量的半定二次规划逆问题 |
5.1 引言 |
5.2 问题重建 |
5.3 光滑化牛顿法求解方程 |
5.4 数值实验 |
5.5 本章小结 |
6 结论与展望 |
6.1 结论 |
6.2 创新点 |
6.3 展望 |
参考文献 |
攻读博士学位期间发表学术论文情况 |
致谢 |
作者简介 |
(3)一种基于Freudenthal单纯形细分的二次规划方法(论文提纲范文)
中文摘要 |
abstract |
第1章 绪论 |
1.1 引论 |
1.2 国内外二次规划问题的研究现状 |
1.2.1 二次规划问题的研究现状 |
1.2.2 二次规划的发展趋势 |
1.3 论文的研究内容及主要工作 |
第2章 二次规划的概述及基础知识 |
2.1 二次规划介绍 |
2.2 最优化的基础概念 |
2.2.1 最优化问题的提法和基本概念 |
2.2.2 二维最优化问题的几何意义 |
2.2.3 最优化问题分类 |
2.3 优化方法中的基本数学表达式 |
2.4 凸集和凸函数 |
2.4.1 凸集 |
2.4.2 凸函数 |
第3章 二次规划常用算法的描述与分析 |
3.1 二次规划算法综述 |
3.2 二次规划常用算法 |
3.2.1 Lagrange算法 |
3.2.2 路径跟踪法 |
3.2.3 内点法 |
3.3 代理对偶的思想同Karmarkar算法的联系 |
第4章 二次规划的代理对偶问题及其解法 |
4.1 引言 |
4.2 一般约束优化的代理约束与代理对偶的概念及结论 |
4.3 显示对偶问题与隐式对偶问题的几何意义 |
4.4 二次规划的显式的代理对偶问题 |
4.5 对偶目标函数的非凸性 |
4.6 结束语 |
第5章 单纯形细分的一个推广 |
5.1 问题介绍 |
5.2 单纯形细分 |
5.3 该算法的实例实现 |
5.4 结论 |
第6章 验证算例 |
参考文献 |
致谢 |
申请学位期间的研究成果及发表的学术论文 |
(4)基于异质性时间价值和拥堵费用预算的交通分配与拥堵收费问题研究(论文提纲范文)
摘要 |
abstract |
第一章 绪论 |
1.1 研究背景及意义 |
1.1.1 交通拥堵现象日益加剧 |
1.1.2 交通需求管理方法的出现 |
1.1.3 智能交通系统的迅速发展 |
1.1.4 拥堵收费的实施现状 |
1.2 研究内容与技术路线 |
1.3 论文结构与章节安排 |
1.4 本章小结 |
第二章 文献综述 |
2.1 交通流分配问题 |
2.1.1 时间价值的定义及测算 |
2.1.2 具有时间价值异质性的交通分配模型 |
2.1.3 基于拥堵费预算异质性的交通分配 |
2.2 拥堵收费问题 |
2.3 算法综述 |
2.4 本章小结 |
第三章 具有用户异质性的拥堵收费模型概述 |
3.1 具有用户异质性的交通网络均衡问题 |
3.1.1 用户均衡和系统最优 |
3.1.2 基于出行者时间价值异质性的广义用户均衡 |
3.1.3 异质性时间价值与拥堵费预算对交通分配的影响 |
3.2 具有用户异质性的拥堵收费 |
3.2.1 拥堵收费基本原理 |
3.2.2 用户异质性拥堵收费方案 |
3.3 本章小结 |
第四章 具有用户拥堵费预算异质性的拥堵收费研究 |
4.1 问题提出与模型公式 |
4.1.1 路径选择行为及平衡条件定义 |
4.1.2 建立模型 |
4.2 网络均衡模型解决方法 |
4.2.1 基本步骤 |
4.2.2 网络负载子问题模型 |
4.2.3 极值“帕累托最优”路径集 |
4.2.4 网络负载子模型解决方法 |
4.2.5 算例 |
4.3 最优定价方案 |
4.4 本章小结 |
第五章 具有用户时间价值异质性与拥堵费预算异质性的拥堵收费研究 |
5.1 问题提出与模型公式 |
5.1.1 路径选择行为及平衡条件定义 |
5.1.2 建立模型 |
5.2 网络均衡模型解决方法 |
5.2.1 基本步骤 |
5.2.2 网络负载子问题模型 |
5.2.3 网络负载方法 |
5.2.4 算例 |
5.3 算例分析 |
5.3.1 算例一 |
5.3.2 算例二 |
5.4 基于时间差的最优拥堵收费方案 |
5.5 本章小结 |
第六章 总结与展望 |
参考文献 |
附录 符号定义 |
致谢 |
攻读硕士学位期间已发表或录用的文章 |
(5)线性约束下的组合优化问题研究(论文提纲范文)
摘要 |
abstract |
主要符号对照表 |
第1章 引言 |
1.1 研究背景和选题意义 |
1.2 线性约束下的组合优化问题 |
1.3 相关研究 |
1.4 论文主要工作和内容安排 |
第2章 相关知识概述 |
2.1 组合优化 |
2.2 计算复杂性 |
2.3 近似算法 |
2.4 线性规划和相关数学规划问题 |
第3章 线性约束下的排序问题 |
3.1 SLC问题及背景介绍 |
3.1.1 问题描述 |
3.1.2 应用背景 |
3.1.3 排序问题简介 |
3.2 一台机器或一个约束的情形 |
3.2.1 一台机器的情形 |
3.2.2 一个约束的情形 |
3.3 常数台机器的情形(m≥2) |
3.3.1 常数个约束的情形(k≥2) |
3.3.2 任意个约束的情形(k≥2) |
3.4 任意台机器的情形(m≥2) |
3.4.1 两个约束的情形(k=2) |
3.4.2 常数或任意个约束的情形(k≥3) |
3.5 本章小结 |
第4章 线性约束下的背包问题 |
4.1 KLC问题及背景介绍 |
4.1.1 问题描述 |
4.1.2 应用背景 |
4.1.3 背包问题简介 |
4.2 常数个约束的情形 |
4.3 任意个约束的情形 |
4.3.1 KLC1问题 |
4.3.2 KLC2问题 |
4.4 线性约束下的多背包问题 |
4.5 本章小结 |
第5章 线性约束下的装箱问题 |
5.1 BLC问题及背景介绍 |
5.1.1 问题描述 |
5.1.2 应用背景 |
5.1.3 装箱问题简介 |
5.2 任意个约束的情形(k≥2) |
5.3 常数个约束的情形 |
5.4 物品大小受限的情形 |
5.5 本章小结 |
第6章 线性约束下的最短路和顶点覆盖问题 |
6.1 问题描述 |
6.2 相关问题简介 |
6.3 常数个约束的情形 |
6.4 不可近似性 |
6.5 本章小结 |
第7章 总结和展望 |
参考文献 |
致谢 |
个人简历、在学期间发表的学术论文与研究成果 |
(6)柔性运动系统能量与振动同步优化的轨迹规划方法研究(论文提纲范文)
摘要 |
abstract |
第1章 绪论 |
1.1 研究背景及意义 |
1.2 柔性运动系统轨迹规划方法综述 |
1.2.1 基本描述、定义和模型 |
1.2.2 轨迹优化方法 |
1.2.3 轨迹规划的鲁棒性优化方法 |
1.2.4 轨迹规划的在线实现方法 |
1.3 论文研究内容 |
1.3.1 研究问题的提出 |
1.3.2 主要研究内容 |
1.3.3 论文章节 |
第2章 基于零残余振动能约束的全局最优EVO轨迹规划 |
2.1 引言 |
2.2 基于零残余振动能约束的EVO轨迹问题建模 |
2.2.1 零残余振动能约束 |
2.2.2 全局最优EVO轨迹规划问题模型 |
2.2.3 模型凸化 |
2.3 基于凸二次规划的求解策略 |
2.3.1 最优控制问题数值求解算法框架简介 |
2.3.2 问题模型离散化为凸二次规划问题并基于原对偶内点法求解 |
2.4 结合Hamilton与残余振动能数值约束的求解策略 |
2.4.1 基于Hamilton函数的算法改进 |
2.4.2 残余振动能精确约束的算法改进 |
2.5 本章小节 |
第3章 基于时/频残余振动能敏感度约束的EVO轨迹鲁棒性优化 |
3.1 引言 |
3.2 能量与振动目标函数对模型参数摄动的敏感度分析 |
3.3 残余振动能对摄动不敏感的EVO轨迹鲁棒性优化 |
3.3.1 鲁棒EVO轨迹规划问题建模 |
3.3.2 残余振动能敏感度函数约束的频域解释 |
3.3.3 基于凸二次规划的求解算法 |
3.4 残余振动能对摄动有界的EVO轨迹鲁棒性优化 |
3.4.1 残余振动能单鼓包约束的鲁棒EVO轨迹 |
3.4.2 残余振动能双鼓包约束的鲁棒EVO轨迹 |
3.5 本章小节 |
第4章 面向简单轨迹结构的在线EVO轨迹规划 |
4.1 引言 |
4.2 基于梯形轨迹的EVO轨迹及其快速求解算法 |
4.2.1 零残余振动条件 |
4.2.2 能耗目标函数 |
4.2.3 优化问题建模 |
4.2.4 基于连续松弛法的快速求解算法 |
4.3 基于S形轨迹的鲁棒EVO轨迹及其快速求解算法 |
4.3.1 优化问题建模 |
4.3.2 鲁棒振动抑制条件 |
4.3.3 基于近似极值点附近枚举的快速求解算法 |
4.4 本章小节 |
第5章 仿真与实验验证 |
5.1 柔性伺服运动系统实验平台 |
5.2 全局最优EVO轨迹仿真与实验验证 |
5.2.1 算法求解精度与速度 |
5.2.2 节能与抑振性能分析与讨论 |
5.2.3 实验验证 |
5.3 鲁棒EVO轨迹仿真与实验验证 |
5.3.1 鲁棒性能分析与讨论 |
5.3.2 实验验证 |
5.4 基于梯形轨迹的EVO轨迹仿真与实验验证 |
5.4.1 计算耗时、节能与抑振性能分析与讨论 |
5.4.2 实验验证 |
5.5 基于S形轨迹的鲁棒EVO轨迹仿真与实验验证 |
5.5.1 计算耗时、节能与抑振性能分析与讨论 |
5.5.2 实验验证 |
5.6 本章小结 |
第6章 结论与展望 |
6.1 研究内容总结 |
6.2 论文主要创新点 |
6.3 后续研究展望 |
参考文献 |
致谢 |
附录A 能量和振动目标函数对模型参数摄动的敏感曲线 |
个人简历、在学期间发表的学术论文与研究成果 |
(8)互补问题最优化算法研究及其应用(论文提纲范文)
摘要 |
Abstract |
1 绪论 |
1.1 研究背景与意义 |
1.2 互补问题的基本概念 |
1.3 本文的主要研究内容 |
2 高阶内点算 |
2.1 窄邻域高阶内点算法 |
2.2 宽邻域高阶内点算法 |
2.3 小结 |
3 代数等价变换的不可行内点算法 |
3.1 算法的描述 |
3.2 算法的全局收敛性 |
3.3 数值试验 |
3.4 小结 |
4 基于核函数求解互补问题的不可行内点算法 |
4.1 算法的描述 |
4.2 算法的全局收敛性 |
4.3 小结 |
5 利用核函数求解非线性互补问题的内点算法 |
5.1 算法描述 |
5.2 复杂性分析 |
5.3 小结 |
6 利用线性互补问题求解双矩阵博弈 |
6.1 博弈论简介 |
6.2 双矩阵对策转化为线性互补问题 |
7 演化博弈视角下的农村合作组织优化模型及仿真实验 |
7.1 演化博弈论简介 |
7.2 农村合作组织的合作机制 |
7.3 演化博弈视角下的农村合作组织优化模型及仿真实验 |
7.4 小结 |
8 总结与展望 |
8.1 本文主要工作和研究成果 |
8.2 研究展望 |
参考文献 |
攻读博士学位期间发表和完成的学术论文 |
致谢 |
(9)炼油厂混合整数二次规划调度模型的算法研究(论文提纲范文)
目录 |
CONTENTS |
摘要 |
ABSTRACT |
符号说明 |
第一章 绪论 |
1.1 研究意义 |
1.2 研究现状 |
1.2.1 二次规划研究现状 |
1.2.2 内点法研究现状 |
1.3 目前存在的问题 |
1.4 本文的工作 |
第二章 炼油厂动态调度模型分析与预备知识 |
2.1 K-K-T条件 |
2.2 炼油厂动态调度模型分析 |
2.2.1 炼油生产过程 |
2.2.2 炼油厂动态调度模型 |
2.2.3 模型分析 |
2.3 分支定界法 |
2.3.1 分支定界法概述 |
2.3.2 算法关键点 |
2.4 内点法 |
2.4.1 内点法的分类 |
2.4.2 拟Newton内点算法 |
2.5 本章小结 |
第三章 基于改进内点法与分支定界法的混合算法 |
3.1 内点法起始点的确定 |
3.1.1 算法分析与描述 |
3.1.2 实例运算 |
3.2 改进的Newton内点法 |
3.2.1 理论分析 |
3.2.2 内点算法描述 |
3.2.3 收敛性分析 |
3.2.4 实例运算 |
3.3 分支策略的确立 |
3.4 基于改进内点法与分支定界法的混合算法 |
3.5 本章小结 |
第四章 炼油厂动态调度实例求解 |
4.1 动态调度实例 |
4.2 模型求解与比较 |
4.2.1 初始可行点的计算 |
4.2.2 松弛问题的拟Newton算法计算 |
4.2.3 离散过程 |
4.2.4 综合分析与大规模实例测试 |
4.3 本章小节 |
第五章 结论 |
5.1 文章总结 |
5.2 未来的工作 |
参考文献 |
致谢 |
攻读硕士学位期间参与的项目 |
附录1 炼油厂生产流程图 |
学位论文评阅及答辩情况表 |
(10)低群延迟误差IIR数字滤波器的minimax设计方法(论文提纲范文)
摘要 |
ABSTRACT |
第1章 绪论 |
1.1 研究背景及意义 |
1.2 国内外研究现状 |
1.3 存在问题和解决办法 |
1.4 论文的结构安排和主要工作 |
第2章 数字滤波器及优化理论基础 |
2.1 数字滤波器概述 |
2.2 IIR 数字滤波器简介 |
2.2.1 IIR 数字滤波器的数学模型 |
2.2.2 IIR 数字滤波器的网络结构 |
2.3 最优化理论基础 |
2.3.1 优化的基本概念 |
2.3.2 最优化问题的数学模型及分类 |
2.4 本章小结 |
第3章 IIR 数字滤波器设计方法 |
3.1 设计的基本概念 |
3.2 间接设计方法 |
3.3 优化设计法 |
3.3.1 IIR 数字滤波器优化设计准则 |
3.3.2 IIR 数字滤波器优化设计方法 |
3.4 IIR 数字滤波器 minimax 设计的序列约束最小二乘方法 |
3.5 本章小结 |
第4章 减小滤波器群延迟误差的相位误差上界函数方法 |
4.1 引言 |
4.2 S 形相位误差上界函数 |
4.3 相位误差上界函数的自动更新方法 |
4.4 本章小结 |
第5章 低群延迟误差 IIR 数字滤波器 minimax 设计 |
5.1 引言 |
5.2 相位误差约束 minimax 设计问题 |
5.3 相位误差约束的线性化 |
5.4 设计算法 |
5.5 仿真实例比较 |
5.6 本章小结 |
第6章 自动更新相位误差上界函数 |
6.1 引言 |
6.2 自动更新程序迭代步骤 |
6.3 仿真实例比较 |
6.4 本章小结 |
第7章 总结与展望 |
7.1 论文研究工作总结 |
7.2 展望 |
致谢 |
参考文献 |
附录 |
四、一类线性约束凸规划的几种多项式算法的研究(论文参考文献)
- [1]动约束函数的构造及其在非凸优化中的应用[D]. 吴铮. 长春工业大学, 2021(08)
- [2]几类二次规划逆问题的有效数值方法[D]. 李丽丹. 大连理工大学, 2020(07)
- [3]一种基于Freudenthal单纯形细分的二次规划方法[D]. 张彦微. 天津职业技术师范大学, 2018(01)
- [4]基于异质性时间价值和拥堵费用预算的交通分配与拥堵收费问题研究[D]. 白婷. 上海交通大学, 2018(01)
- [5]线性约束下的组合优化问题研究[D]. 聂嘉明. 清华大学, 2017(02)
- [6]柔性运动系统能量与振动同步优化的轨迹规划方法研究[D]. 陈涵. 清华大学, 2017(02)
- [7]线性与非线性规划算法与理论[J]. 戴彧虹,刘新为. 运筹学学报, 2014(01)
- [8]互补问题最优化算法研究及其应用[D]. 龚小玉. 武汉大学, 2013(05)
- [9]炼油厂混合整数二次规划调度模型的算法研究[D]. 李学良. 山东大学, 2012(02)
- [10]低群延迟误差IIR数字滤波器的minimax设计方法[D]. 杨吉祥. 杭州电子科技大学, 2012(10)