论文标题
功能性约束优化对风险规避和稀疏控制
Functional Constrained Optimization for Risk Aversion and Sparsity Control
论文作者
论文摘要
在许多应用中，例如在投资组合优化，分类计划和治疗计划中，通常需要同时执行风险和稀疏性要求。正确平衡这些潜在的矛盾要求需要与凸或非凸目标的功能约束优化提出。在本文中，我们专注于可以生成稀疏轨迹来解决这些具有挑战性的功能约束优化问题的稀疏轨迹的方法。具体而言，对于凸设置，我们提出了一个水平条件梯度（LCG）方法，该方法利用级别集合框架来更新最佳值和内部条件梯度甲骨文（CGO）的近似值，以求解Mini-Max亚问题。我们表明该方法获得了$ \ Mathcal {O} \ big（\ frac {1} {ε^2} \ log \ frac {1}ε\ big）$迭代复杂性，用于求解平滑和非依赖的情况，而无需依赖于最佳的双重lagrange乘数大小。对于非convex设置，我们介绍了级别不切度的近端点（IPP-LCG）方法和直接的非coNVEX条件梯度（DNCG）方法。第一种方法通过将问题转换为一系列凸子问题来探讨LCG的优势，并展示$ \ Mathcal {o} \ big（\ frac {1} {ε^3} \ log \ log \ log \ frac {1} 1}ε\ big）$ itseration $ itsection $ itseration $ itsection $ its（$ to） DNCG是第一个单循环投影方法，其迭代复杂性由$ \ Mathcal {o} \ big（1/ε^4 \ big）$界定，用于计算所谓的$ε$ -Wolfe点。我们通过设计配方并对两种风险避免稀疏优化应用进行数值实验来证明LCG，IPP-LCG和DNCG的有效性：有和没有基数性要求的投资组合选择问题以及医疗保健中的放射治疗计划问题。
Risk and sparsity requirements often need to be enforced simultaneously in many applications, e.g., in portfolio optimization, assortment planning, and treatment planning. Properly balancing these potentially conflicting requirements entails the formulation of functional constrained optimization with either convex or nonconvex objectives. In this paper, we focus on projection-free methods that can generate a sparse trajectory for solving these challenging functional constrained optimization problems. Specifically, for the convex setting, we propose a Level Conditional Gradient (LCG) method, which leverages a level-set framework to update the approximation of the optimal value and an inner conditional gradient oracle (CGO) for solving mini-max subproblems. We show that the method achieves $\mathcal{O}\big(\frac{1}{ε^2}\log\frac{1}ε\big)$ iteration complexity for solving both smooth and nonsmooth cases without dependency on a possibly large size of optimal dual Lagrange multiplier. For the nonconvex setting, we introduce the Level Inexact Proximal Point (IPP-LCG) method and the Direct Nonconvex Conditional Gradient (DNCG) method. The first approach taps into the advantage of LCG by transforming the problem into a series of convex subproblems and exhibits an $\mathcal{O}\big(\frac{1}{ε^3}\log\frac{1}ε\big)$ iteration complexity for finding an ($ε,ε$)-KKT point. The DNCG is the first single-loop projection-free method, with iteration complexity bounded by $\mathcal{O}\big(1/ε^4\big)$ for computing a so-called $ε$-Wolfe point. We demonstrate the effectiveness of LCG, IPP-LCG and DNCG by devising formulations and conducting numerical experiments on two risk averse sparse optimization applications: a portfolio selection problem with and without cardinality requirement, and a radiation therapy planning problem in healthcare.
