【干货书】凸随机优化，320页pdf

2022 年 9 月 16 日 专知

这本教科书介绍了Banach空间中优化问题的凸对偶性、积分理论，以及它们在静态或动态设置中的随机规划问题的应用。对随机规划的主要算法进行了介绍和分析，并对理论方面进行了细致的论述。

读者展示了如何这些工具可以应用到各种领域，包括近似理论，半定和二阶锥规划和线性决策规则。

本书推荐给那些愿意用严格的方法来研究对偶理论在不确定性优化中的应用中的数学的学生、工程师和研究人员。

凸优化工具箱

本章在巴拿赫空间中，通过极大极小法和摄动法，给出优化问题的对偶理论。在一些稳定性(限定)假设下，证明了对偶问题具有一个非空有界解集。这就引出了次微分学，这似乎只是一个偏次微分法则。提供了应用的十进制卷积，以及衰退和透视函数。利用Shapley-Folkman定理，分析了一些非凸问题的松弛性。

半定规划与半无限规划

本章讨论正半定矩阵锥上的最优化问题，以及这类线性问题的对偶理论。我们将凸旋转不变矩阵函数与谱的凸函数联系起来;这使得我们可以计算对数势垒函数的共轭和相关优化问题的对偶。给出了具有非凸二次型代价和约束的半定松弛问题。证明了二阶锥优化是半定规划的一个子类。第二部分研究有限支撑测度空间中的半无限规划及其对偶问题，并应用于Chebyshev近似和一维多项式优化问题。

集成工具箱

本章简明地介绍了一般测度空间中的积分理论，包括关于积分极限的经典定理。它扩展了在巴拿赫空间中具有值的可测函数所需要的波奇纳积分。然后，它展示了如何计算积分泛函的共轭和子微分，无论是在凸情况下，基于凸被积函数理论，或在Carathéodory被积函数的情况下。然后利用Shapley-Folkman定理分析了具有积分代价和约束函数的优化问题。

风险度量

将期望最小化几乎无法控制远低于期望值的回报的风险。因此，设计函数是很有用的，其最小化将允许人们在风险和期望值之间进行权衡。本章简要介绍了相应的风险度量理论。在介绍了效用函数之后，引入了风险的货币度量，并与它们的接受集相联系。然后讨论了偏差和半偏差的情况，以及(条件)风险值。

抽样和优化

本章讨论的不是最小化期望，而是最小化通过获得独立事件的样本得到的样本近似时会发生什么。该分析依赖于渐近定律理论(δ定理)及其在随机规划中的应用。我们将结果推广到期望约束的情况。

动态随机优化

动态随机优化问题具有以下信息约束:每个决策必须是相应时刻可用信息的函数。这可以表示为包含条件期望的线性约束。本章在充分观察状态的情况下发展了凸问题的相应理论。由此得到的最优系统涉及一个后向共态方程，控制变量是某个哈密顿函数的最小值点.

马尔可夫决策过程

本章考虑一个受控马尔可夫链过程的最小回报期望问题，无论是有限范围的马尔可夫链过程，还是有折扣的无限马尔可夫链过程，包括退出时间和停止决策的情况。比较了值和策略(Howard)迭代。对于具有期望约束、局部观察的问题，对于具有无折现代价的大视界问题的遍历情况，给出了这些结果的推广。

算法

对于凸的动态随机优化问题，Bellman函数是凸的，可以近似为仿射函数的有限上极值。从静态和确定性问题开始，展示了这如何导致有效的随机对偶动态规划算法。本章第二部分讨论了线性决策规则的一种很有前途的方法，它使我们可以得到随机优化问题的值函数的上下界。

广义凸性与运输理论

本章首先介绍了用任意集上的一般耦合函数代替对偶积时凸性理论的推广。优化问题的Fenchel共轭、循环单调性和对偶性的概念，对这种设置有一个自然的扩展，其中增广拉格朗日方法有一个自然的解释。度量空间上的凸函数，构造为连续函数的积分函数的Fenchel共轭，有时被证明等于其密度的函数的某个积分。这被用于在紧集上的最优运输理论的表述，以及相关的惩罚问题。本章最后讨论了多传输环境。

专知便捷查看