<p>In this paper we focus on nonconvex optimization problems with expectation constraints. To address the challenges posed by possibly nonconvex constraints and the stochastic nature of the problem, we propose a two-phase stochastic momentum-based algorithm TStoM. The first phase of TStoM aims to minimize the infeasibility measure searching for a nearly feasible point in the expectation sense. This point is used to initialize the second phase. In each iteration of the second phase, we perform a proximal stochastic gradient step to update the primal variable, while the dual update relies on stochastic constraint function values calculated in a moving average way. Under certain conditions, TStoM can find a stochastic <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2941_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-stationary point with a sample complexity in order <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2941_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}(\epsilon ^{-6})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>6</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Furthermore, under a nonsingularity condition we show that the sample complexity is in order <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2941_Article_IEq3.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}(\epsilon ^{-5})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>5</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> to reach a stochastic <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2941_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-KKT point. At this point the expected error of approximate constraint values is bounded by <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2941_Article_IEq5.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="64" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}(I^{-1/5})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>I</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>5</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <i>I</i> being the number of samples generated during the algorithmic process. Numerical experiments are conducted to demonstrate the efficiency and effectiveness of TStoM.</p>

A Two-phase Stochastic Momentum-Based Algorithm for Nonconvex Expectation-Constrained Optimization

期刊论文
发表日期：

2025年5月21日

查看全文

Yawen Cui,
Xiao Wang,
Xiantao Xiao

摘要

In this paper we focus on nonconvex optimization problems with expectation constraints. To address the challenges posed by possibly nonconvex constraints and the stochastic nature of the problem, we propose a two-phase stochastic momentum-based algorithm TStoM. The first phase of TStoM aims to minimize the infeasibility measure searching for a nearly feasible point in the expectation sense. This point is used to initialize the second phase. In each iteration of the second phase, we perform a proximal stochastic gradient step to update the primal variable, while the dual update relies on stochastic constraint function values calculated in a moving average way. Under certain conditions, TStoM can find a stochastic $\epsilon $ $ϵ$ -stationary point with a sample complexity in order $\mathcal {O}(\epsilon ^{-6})$ $O (ϵ^{- 6})$ . Furthermore, under a nonsingularity condition we show that the sample complexity is in order $\mathcal {O}(\epsilon ^{-5})$ $O (ϵ^{- 5})$ to reach a stochastic $\epsilon $ $ϵ$ -KKT point. At this point the expected error of approximate constraint values is bounded by $\mathcal {O}(I^{-1/5})$ $O (I^{- 1 / 5})$ with I being the number of samples generated during the algorithmic process. Numerical experiments are conducted to demonstrate the efficiency and effectiveness of TStoM.