<p>In this paper, we analyze a derivative-free line search method designed for bound-constrained problems. Our analysis demonstrates that this method exhibits a worst-case complexity comparable to other derivative-free methods for unconstrained and linearly constrained problems. In particular, when minimizing a function with <i>n</i> variables, we prove that at most <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {O}{(n\epsilon ^{-2})}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> iterations are needed to drive a criticality measure below a predefined threshold <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>, requiring at most <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {O}{(n^2\epsilon ^{-2})}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> function evaluations. We also show that the total number of iterations where the criticality measure is not below <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation> is upper bounded by <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {O}{(n^2\epsilon ^{-2})}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. Moreover, we investigate the method capability to identify active constraints at the final solutions. We show that, after a finite number of iterations, all the active constraints satisfying the strict complementarity condition are correctly identified.</p>

Complexity Results and Active-Set Identification of a Derivative-Free Method for Bound-Constrained Problems

期刊论文
出版模式：

开放获取
发表日期：

2026年3月11日

查看全文

Andrea Brilli,
Andrea Cristofari,
Giampaolo Liuzzi,
Stefano Lucidi

摘要

In this paper, we analyze a derivative-free line search method designed for bound-constrained problems. Our analysis demonstrates that this method exhibits a worst-case complexity comparable to other derivative-free methods for unconstrained and linearly constrained problems. In particular, when minimizing a function with n variables, we prove that at most $\mathcal {O}{(n\epsilon ^{-2})}$ $O (n ϵ^{- 2})$ iterations are needed to drive a criticality measure below a predefined threshold $\epsilon $ $ϵ$ , requiring at most $\mathcal {O}{(n^2\epsilon ^{-2})}$ $O (n^{2} ϵ^{- 2})$ function evaluations. We also show that the total number of iterations where the criticality measure is not below $\epsilon $ $ϵ$ is upper bounded by $\mathcal {O}{(n^2\epsilon ^{-2})}$ $O (n^{2} ϵ^{- 2})$ . Moreover, we investigate the method capability to identify active constraints at the final solutions. We show that, after a finite number of iterations, all the active constraints satisfying the strict complementarity condition are correctly identified.