arXiv:2506.20630math.OCcs.LG2025-06被引 2

提出新方法,让优化约束几乎必然满足且解接近最优。

First-order methods for stochastic and finite-sum convex optimization with deterministic constraints

  • 用二次惩罚法结合一次加速梯度求解,确保约束不越界。
  • 在随机和有限求和优化中,首次实现确定性约束满足与期望最优性双达标。
  • 适合对约束可靠性要求高的实际应用,如金融、医疗决策。

本文研究一类带有确定性约束的随机与有限求和凸优化问题。现有方法通常寻找 $ε$-预期可行的随机最优解,即期望约束违规和期望最优性差距均不超过 $ε$。但在许多实际场景中,约束必须以高概率严格满足,此类解可能因存在显著违规风险而不适用。为此,我们提出用于寻找 $ε$-确定可行的随机最优($ε$-SFSO)解的新随机一阶方法:约束违规被确定性地控制在 $ε$ 内,期望最优性差距亦不超过 $ε$。所提方法仅需对一系列带合适惩罚参数的二次惩罚子问题执行一次加速随机梯度(ASG)或改进的方差减少型 ASG。我们建立了计算 $ε$-SFSO 解的一阶原语复杂度上界。作为副产品,我们也给出了样本平均近似法在求解随机优化问题时的复杂度结果,通过我们提出的方法求解样本平均问题。

原文摘要 · Abstract (English)

In this paper, we study a class of stochastic and finite-sum convex optimization problems with deterministic constraints. Existing methods typically aim to find an $ε$-$expectedly\ feasible\ stochastic\ optimal$ solution, in which the expected constraint violation and expected optimality gap are both within a prescribed tolerance $ε$. However, in many practical applications, constraints must be nearly satisfied with certainty, rendering such solutions potentially unsuitable due to the risk of substantial violations. To address this issue, we propose stochastic first-order methods for finding an $ε$-$surely\ feasible\ stochastic\ optimal$ ($ε$-SFSO) solution, where the constraint violation is deterministically bounded by $ε$ and the expected optimality gap is at most $ε$. Our methods apply an accelerated stochastic gradient (ASG) scheme or a modified variance-reduced ASG scheme $only\ once$ to a sequence of quadratic penalty subproblems with appropriately chosen penalty parameters. We establish first-order oracle complexity bounds for the proposed methods in computing an $ε$-SFSO solution. As a byproduct, we also derive first-order oracle complexity results for sample average approximation method in computing an $ε$-SFSO solution of the stochastic optimization problem using our proposed methods to solve the sample average problem.

优化算法约束满足随机优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。