当期目录

2021年 第25卷 第3期    刊出日期：2021-09-15

上一期    下一期

浅谈增广Lagrange方法中的二阶分析

张立卫

2021, 25(3):  1-14.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.001

摘要 ( 2462 )   HTML ( 61)   PDF (793KB) ( 303 )  

参考文献 | 相关文章 | 多维度评价

从极大化基于增广Lagrange函数的对偶函数的角度，可将增广Lagrange方法的乘子的迭代解释为常步长的梯度方法。增广Lagrange方法的有效性可以通过分析对偶函数的二阶微分得到。给出等式约束优化问题和一般约束非线性规划问题的对偶函数的二阶微分估计，解释为什么常步长的梯度方法具有快的收敛速度。

超大规模集成电路布局的优化模型与算法

黄志鹏, 李兴权, 朱文兴

2021, 25(3):  15-36.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.002

摘要 ( 3055 )   HTML ( 59)   PDF (1145KB) ( 668 )  

参考文献 | 相关文章 | 多维度评价

布局确定集成电路单元在芯片中的具体位置，在单元互不重叠的基础上优化一些性能指标。该问题是NP困难的组合优化问题，是超大规模集成电路物理设计的核心问题之一，对集成电路的性能指标，如线网可布通性、时延、功耗、电路可靠性等有重大影响。在现代的集成电路设计中，布局问题通常包含数百万个集成电路单元，以及大小相异的异质性模块，和各种复杂的布局约束。目前的超大规模集成电路布局算法通常分解为总体布局、布局合法化和详细布局三个步骤。根据近年来集成电路布局算法的研究进展，综述并分析集成电路的总体布局、布局合法化和详细布局的相关优化模型和算法，并展望进一步的研究方向。

运筹学在整车物流智能调度决策支持系统中的研究与应用

陈峰

2021, 25(3):  37-73.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.003

摘要 ( 2877 )   HTML ( 44)   PDF (25909KB) ( 616 )  

参考文献 | 相关文章 | 多维度评价

本文基于整车物流智能调度决策支持系统的研发、实施与运维的成功应用，论述运筹学在智能化上的应用路径以及实践驱动的学术路径。该系统是国内较早在汽车物流企业实现落地的智能化调度系统，其所形成的思想理论与方法技术揭示了运筹学在智能化应用上的核心价值，以及实践驱动的学术价值，对解决“卡脖子”难题提供示范性思路。本文提出运筹学在智能化研发上“三环七步”的整体研发框架。首先，分析智能化需求的运筹学特征，详细介绍汽车整车物流的发展趋势、瓶颈及智能调度需求；其次，论述运筹学系统模型的作用与建模方法，分析汽车整车物流系统模型的决策要素、目标及约束，提出汽车整车物流智能调度的运筹学应用问题。然后，提出“模式装箱”的新装箱理论问题，明确问题的计算难解性、可解性及核心科学特征。进一步，建立汽车整车物流调度应用问题与科学问题的混合整数线性规划模型；提出求解汽车整车物流调度问题的分支定界算法，以及大规模问题求解的时空分解及滚动求解方法与技术；提出面向运筹应用的生产测试及压力测试方法，给出汽车整车物流调度的测试分析的流程与结果。此外，提出深度集成整车运输管理系统与仓库管理系统、优化算法引擎驱动的分布式、多视图、多系统融合的智能调度决策支持系统。最后，论述该系统在实施过程中的推广使用和运维情况，并对运筹学应用及实践驱动的科学研究进行总结与展望。

非凸极小极大问题的优化算法与复杂度分析

徐姿, 张慧灵

2021, 25(3):  74-86.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.004

摘要 ( 2823 )   HTML ( 47)   PDF (957KB) ( 404 )  

参考文献 | 相关文章 | 多维度评价

非凸极小极大问题是近期国际上优化与机器学习、信号处理等交叉领域的一个重要研究前沿和热点，包括对抗学习、强化学习、分布式非凸优化等前沿研究方向的一些关键科学问题都归结为该类问题。国际上凸-凹极小极大问题的研究已取得很好的成果，但非凸极小极大问题不同于凸-凹极小极大问题，是有其自身结构的非凸非光滑优化问题，理论研究和求解难度都更具挑战性，一般都是NP-难的。重点介绍非凸极小极大问题的优化算法和复杂度分析方面的最新进展。

从双层规划的角度看道德风险理论的一阶条件方法

柯荣住, 张进

2021, 25(3):  87-104.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.005

摘要 ( 2389 )   HTML ( 5)   PDF (1028KB) ( 208 )  

参考文献 | 相关文章 | 多维度评价

本文首先对双层规划的一个特殊例子即道德风险模型中使用的一阶条件方法（FOA）做简要的梳理，然后提出一种更为一般的使FOA有效的原则与方法。新方法主要依赖于代理人对委托人设置的目标的最优反应映射是否存在不动点，这个性质不要求原问题与用一阶条件放松以后的问题之间的约束集等价，从而也不要求代理人的期望效用对行动具有全局凹性。在新方法下，可以用较为简单的方法证明FOA在以下两种情形之一有效，即如果分布函数是概率分布的凸组合或者分布函数来自某些特殊的指数族分布。

具有非线性采购成本库存控制问题的研究现状与挑战

姚大成

2021, 25(3):  105-118.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.006

摘要 ( 2181 )   HTML ( 7)   PDF (867KB) ( 143 )  

参考文献 | 相关文章 | 多维度评价

库存管理是基于运筹学而发展起来的一门学科，并成为近几十年来运筹学和管理科学重要的研究领域之一。在库存系统中，采购成本是必不可少的成本之一，主要包含产品成本、运输成本、装卸成本等。现实中，采购成本依赖于采购量，且往往是采购量的非线性函数。介绍了几类常见的采购成本函数：依赖于采购量的固定成本、增量折扣、全量折扣、车载容量折扣和凸采购成本等。基于周期盘点库存模型和连续盘点库存模型，综述了带有这些非线性采购成本函数的库存模型研究进展。虽然经过了几十年的研究，但很多带有非线性采购成本的库存模型的最优采购策略因为其复杂性至今未能被完整刻画。通过综述来简单讨论该类问题的挑战和机会。

梯度法简述

孙聪, 张亚

2021, 25(3):  119-132.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.007

摘要 ( 2952 )   HTML ( 17)   PDF (914KB) ( 414 )  

参考文献 | 相关文章 | 多维度评价

梯度法是一类求解优化问题的一阶方法。梯度法形式简单、计算开销小，在大规模问题的求解中得到了广泛应用。系统地介绍了光滑无约束问题梯度法的迭代格式、理论框架。梯度法中最重要的参数是步长，步长的选取直接决定了梯度法的收敛性质与收敛速度。从线搜索框架、近似技巧、随机技巧和交替重复步长四方面介绍了梯度步长的构造思想及相应梯度法的收敛性结果，还对非光滑及约束问题的梯度法、梯度法加速技巧和随机梯度法等扩展方向做了简要介绍。

基于横截面回归和Fama-MacBeth估计的鲁棒投资组合优化问题研究

江波, 朱喜华

2021, 25(3):  133-146.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.008

摘要 ( 2189 )   HTML ( 10)   PDF (866KB) ( 142 )  

参考文献 | 相关文章 | 多维度评价

考虑了不同于Goldfarb和Iyengar （2003）的因子模型，通过横截面回归分析以及Fama-MacBeth估计构造了关于资产的平均收益向量和协方差矩阵的不确定性集合（置信区域）。基于这些不确定性集合以及Markowitz“均值-方差模型”的鲁棒投资组合问题，提出了多个鲁棒投资组合问题，并对应的推导出其等价的半正定规划形式，使得问题可以在多项式时间内求解。

排队系统中的泰勒展开方法

胡建强, 戴伟民

2021, 25(3):  147-159.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.009

摘要 ( 2165 )   HTML ( 8)   PDF (822KB) ( 159 )  

参考文献 | 相关文章 | 多维度评价

综述了排队系统中的泰勒展开方法。它由Gong和Hu在1990s首次提出，并在最近几年里有了一些新的发展。首先，通过GI/GI/1队列的简单例子介绍其基本原理；其次，展示如何应用该方法分析相关性队列和离去过程；然后，阐述如何基于该方法发展排队网络近似的高阶矩方法；最后，讨论未来的几个可能研究方向。

一类基于L_0/1软间隔损失函数的低秩支持张量机

王双月, 罗自炎

2021, 25(3):  160-172.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.010

摘要 ( 2251 )   HTML ( 8)   PDF (1546KB) ( 290 )  

参考文献 | 相关文章 | 多维度评价

支持向量机作为基于向量空间的一种传统的机器学习方法，不能直接处理张量类型的数据，否则不仅破坏数据的空间结构，还会造成维度灾难及小样本问题。作为支持向量机的一种高阶推广，用于处理张量数据分类的支持张量机已经引起众多学者的关注，并应用于遥感成像、视频分析、金融、故障诊断等多个领域。与支持向量机类似，已有的支持张量机模型中采用的损失函数多为L_0/1函数的代理函数。将直接使用L_0/1这一本原函数作为损失函数，并利用张量数据的低秩性，建立针对二分类问题的低秩支持张量机模型。针对这一非凸非连续的张量优化问题，设计交替方向乘子法进行求解，并通过对模拟数据和真实数据进行数值实验，验证模型与算法的有效性。

基因调控网络推断研究进展

刘治平

2021, 25(3):  173-182.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.011

摘要 ( 2693 )   HTML ( 32)   PDF (813KB) ( 364 )  

参考文献 | 相关文章 | 多维度评价

随着高通量技术的发展，越来越多的生物医学组学数据亟需处理与分析，基于运筹优化的生物信息学方法是有效解析高维生物医学数据的重要途径之一。综述了近年来在基因调控网络推断方面的研究进展。针对不同类型的转录组学数据和研究目的，分别建立了相应的基因调控网络推断方法，主要包括先验基因调控网络数据库的建立、基于条件互信息的因果网络推断、基于微分方程的动态基因调控网络推断、转录调控和转录后调控协同作用的网络推断以及基因调控网络活性评价等，并展望了基因调控网络推断的重要研究方向。

灾后运输网络中的最短路修复合作博弈

宣洪伟, 李振东, 盛舟山, 刘林冬

2021, 25(3):  183-199.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.012

摘要 ( 2246 )   HTML ( 15)   PDF (1327KB) ( 220 )  

参考文献 | 相关文章 | 多维度评价

在最短路修复合作博弈中，当灾后运输网络规模较大时，最优成本分摊问题难以直接求解。基于拉格朗日松弛理论，提出了一种最短路修复合作博弈成本分摊算法。该算法将最短路修复合作博弈分解为两个具有特殊结构的子博弈，进而利用两个子博弈的结构特性，可以{高效地}求解出二者的最优成本分摊，将这两个成本分摊相加，可以获得原博弈的一个近乎最优的稳定成本分摊。结果部分既包含运输网络的随机仿真，也包含玉树地震灾区的现实模拟，无论数据来源于仿真还是现实，该算法都能在短时间内为最短路修复合作博弈提供稳定的成本分摊方案。

图的平面Turán数和平面anti-Ramsey数

兰永新, 史永堂, 宋梓霞

2021, 25(3):  200-216.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.013

摘要 ( 2360 )   HTML ( 10)   PDF (1215KB) ( 318 )  

参考文献 | 相关文章 | 多维度评价

在所有顶点数为$n$且不包含图$G$作为子图的平面图中，具有最多边数的图的边数称为图$G$的平面Turán数，记为$ex_{_\mathcal{P}}（n，G）$。给定正整数$n$以及平面图$H$，用$\mathcal{T}_n （H）$来表示所有顶点数为$n$且不包含$H$作为子图的平面三角剖分图所组成的图集合。设图集合$\mathcal{T}_n （H）$中的任意平面三角剖分图的任意$k$边染色都不包含彩虹子图$H$，则称满足上述条件的$k$的最大值为图$H$的平面anti-Ramsey数，记作$ar_{_\mathcal{P}}（n，H）$。两类问题的研究均始于2015年左右，至今已经引起了广泛关注。全面地综述两类问题的主要研究成果，以及一些公开问题。