机器学习与优化专辑
针对机器学习中广泛存在的一类问题：结构化随机优化问题（其中“结构化”是指问题的可行域具有块状结构，且目标函数的非光滑正则化部分在变量块之间是可分离的），我们研究了小批量随机块坐标下降算法（mSBD）。按照求解非复合问题和复合问题分别给出了基本的mSBD和它的变体，对于非复合问题，分析了算法在没有一致有界梯度方差假设情况下的收敛性质。而对于复合问题，在不需要通常的Lipschitz梯度连续性假设条件下得到了算法的收敛性。最后通过数值实验验证了mSBD的有效性。
受启发于近些年频繁曝出的消费者权益保护问题，为探析消费者行为对电商生态系统中其他群体策略选择的影响，本文基于演化博弈理论，考虑消费者的投诉行为，构建由政府、电商平台、商家以及消费者组成的四方演化博弈模型；讨论各方主体的策略选择，分析策略组合稳定点，并应用MATLAB工具进行仿真模拟实验。经上述研究，本文得出结论：消费者的投诉行为有利于促进政府严格监管、电商平台严格管理、商家诚信经营。由此，建议政府和电商平台充分发挥监督管理作用，以更好地保障消费者的合法权益，并遏制消费者的恶意投诉行为，从而实现电商生态系统的稳定可持续发展。
加权l1最小化是稀疏优化的主流方法之一。本文对带非负约束的l0最小化问题与加权l1最小化问题的解之间的关系进行了研究，给出了加权l1最小化问题的约束矩阵和目标函数的系数是"s-权优"的定义，并通过该定义给出了加权l1最小化问题的解是带非负约束的l0最小化问题的解的条件。进一步，本文给出了"s-权优"的充分条件及其具体表示形式，并对其上下界进行了可计算的有效估计。
给定一个赋权图$G=（V，E；w，c）$以及图$G$的一个支撑子图$G_{1}=（V，E_{1}）$，这里源点集合$S=\{s_{1}，s_{2}，\cdots，s_{k}\}\subseteq V$，权重函数$w：E\rightarrow\mathbb{R}^{+}$，费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$，本文考虑两类限制性多源点偏心距增广问题，具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$，满足约束条件$c（E_{2}）$$\leq$$B$，目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小；（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$，满足约束条件$c（E_{2}）$$\leq$$B$，目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。
自20世纪70年代开始，随着计算复杂性理论的建立，近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象，装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强，广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外，装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天，对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型，简述若干经典Fit算法的发展历程，分析基于线性规划松弛的近似方案的主要思路，总结当前的研究现状并对未来的研究提供一些参考建议。
本文研究在基数约束下具有单调性的次模+超模函数最大化问题的流模型。该问题在数据处理、机器学习和人工智能等方面都有广泛应用。借助于目标函数的收益递减率（$\gamma$），我们设计了单轮读取数据的过滤-流算法，并结合次模、超模函数的全局曲率（$\kappa^{g}$）得到算法的近似比为$\min\left\{\frac{（1-\varepsilon）\gamma}{2^{\gamma}}，1-\frac{\gamma}{2^{\gamma}（1-\kappa^{g}）^{2}}\right\}$。数值实验验证了过滤-流算法对BP最大化问题的有效性并且得出：次模函数和超模函数在同量级条件下，能保证在较少的时间内得到与贪婪算法相同的最优值。
$k$-均值问题是聚类中的经典问题，亦是NP-难问题。如果允许数据点不聚类，而是支付惩罚费用，则引出带惩罚的$k$-均值问题。本文将带惩罚的$k$-均值问题从欧氏距离推广到更一般的$\mu$-相似Bregman散度，研究了带惩罚$\mu$-相似Bregman散度$k$-均值问题的初始化算法。本文给出的初始化算法，近似比与$\mu$和数据点惩罚最大值与最小值的比例$r$相关。
经典$k$-均值问题是一类应用广泛的聚类问题，它是指给定$\mathbb{R}^d$中观测点集合$D$和整数$k$，目的是在空间中寻找$k$个点作为中心集合$S$，使得集合$D$中的每个观测点到$S$中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典$k$-均值问题有很多推广，本文研究的带惩罚的相同容量$k$-均值问题就是其中之一。与经典$k$-均值问题相比，惩罚性质是指每个观测点都给定惩罚费用，当某个观测点到最近中心的距离大于惩罚费用时，其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方，相同容量约束要求每个中心至多连接$U$个观测点。针对这种问题，我们设计了局部搜索算法，该算法在至多选取$（3+\alpha）k$个中心的情况下，可以达到$\beta$-近似，其中，参数$\alpha>34$，$\beta>\frac{\alpha+34}{\alpha-34}$。
本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达，系统中有一台运输机，该运输机每次最多运输$k$个工件，每个工件需要先在单机上完成加工，然后再被运输机运往目的地，问题的优化目标为最小化完工时间，即所有工件被加工完并且运往目的地的时间最短。针对该问题，作者研究了工件满足一致性条件的模型，并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法，并且证明该算法是最优在线算法。
本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达，目标是最小化时间表长。在时刻$t$，在线算法能够预见到$（t，t+\Delta（t）]$内到达工件的信息，这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长，其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长，$\beta\in（0，1）$是常数。本文对于工件加工时长的一般情形，给出了当 0<β≤1/6 时最好可能的在线算法；对于工件加工时长被限制在一个区间的情形，给出了当 0<β<1 时最好可能的在线算法。
机器学习与优化专辑
