On the stationarity for nonlinear optimization problems with polyhedral constraints
研究了多面体约束优化问题中负梯度在切锥上的投影的正交分解，并基于此开发了一种用于凸二次规划的有效集算法，通过比较两个分量范数来调整算法流程。
Abstract For polyhedral constrained optimization problems and a feasible point $$\textbf{x}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>x</mml:mi> </mml:math> , it is shown that the projection of the negative gradient on the tangent cone, denoted $$\nabla _\varOmega f(\textbf{x})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>∇</mml:mi> <mml:mi>Ω</mml:mi> </mml:msub> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , has an orthogonal decomposition of the form $$\varvec{\beta }(\textbf{x}) + \varvec{\varphi }(\textbf{x})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>β</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> <mml:mo>+</mml:mo> <mml:mrow> <mml:mi>φ</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . At a stationary point, $$\nabla _\varOmega f(\textbf{x}) = \textbf{0}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>∇</mml:mi> <mml:mi>Ω</mml:mi> </mml:msub> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> so $$\Vert \nabla _\varOmega f(\textbf{x})\Vert $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>‖</mml:mo> </mml:mrow> <mml:msub> <mml:mi>∇</mml:mi> <mml:mi>Ω</mml:mi> </mml:msub> <mml:mrow> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>‖</mml:mo> </mml:mrow> </mml:mrow> </mml:math> reflects the distance to a stationary point. Away from a stationary point, $$\Vert \varvec{\beta }(\textbf{x})\Vert $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mrow> <mml:mi>β</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> <mml:mo>‖</mml:mo> </mml:mrow> </mml:math> and $$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mrow> <mml:mi>φ</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> <mml:mo>‖</mml:mo> </mml:mrow> </mml:math> measure different aspects of optimality since $$\varvec{\beta }(\textbf{x})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>β</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> only vanishes when the KKT multipliers at $$\textbf{x}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>x</mml:mi> </mml:math> have the correct sign, while $$\varvec{\varphi }(\textbf{x})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>φ</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> only vanishes when $$\textbf{x}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>x</mml:mi> </mml:math> is a stationary point in the active manifold. As an application of the theory, an active set algorithm is developed for convex quadratic programs which adapts the flow of the algorithm based on a comparison between $$\Vert \varvec{\beta }(\textbf{x})\Vert $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mrow> <mml:mi>β</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> <mml:mo>‖</mml:mo> </mml:mrow> </mml:math> and $$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mrow> <mml:mi>φ</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> <mml:mo>‖</mml:mo> </mml:mrow> </mml:math> .