Complexity Results and Active-Set Identification of a Derivative-Free Method for Bound-Constrained Problems
分析了针对有界约束问题的无导数线搜索方法，证明了其最坏情况复杂度，并展示了该方法在有限步后能正确识别满足严格互补条件的主动约束。
Abstract 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})}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> iterations are needed to drive a criticality measure below a predefined threshold $$\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> , requiring at most $$\mathcal {O}{(n^2\epsilon ^{-2})}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> function evaluations. We also show that the total number of iterations where the criticality measure is not below $$\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> is upper bounded by $$\mathcal {O}{(n^2\epsilon ^{-2})}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . 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.