高阶优化算法分析简介

高阶优化算法是利用目标函数的高阶导数信息进行优化的算法,是最优化领域中的一个新兴的研究方向.高阶算法具有更低的迭代复杂度,但是需要求解一个更难的子问题.主要介绍三种高阶算法,分别为求解凸问题的高阶加速张量算法和A-HPE框架下的最优张量算法,以及求解非凸问题的ARp算法.同时也介绍了怎样求解高阶算法的子问题.希望通过对高阶算法的介绍,引起更多学者的关注与重视.     

工件具有任意尺寸的混合分批平行机排序问题的近似算法

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足考虑了不同于Goldfarb和Iyengar （2003）的因子模型,通过横截面回归分析以及Fama-MacBeth估计构造了关于资产的平均收益向量和协方差矩阵的不确定性集合（置信区域）。基于这些不确定性集合以及Markowitz“均值-方差模型”的鲁棒投资组合问题,提出了多个鲁棒投资组合问题,并对应的推导出其等价的半正定规划形式,使得问题可以在多项式时间内求解。