볼록 2차 최대화를 위한 활성 집합 방법의 무조건적인 하한

우리는 활성 집합 방법이 피벗 규칙에 관계없이 선형 제약 조건 하에서 볼록 2차 함수를 최대화하기 위해 최악의 경우 지수적인 반복 횟수가 필요하다는 것을 증명합니다. 이는 차원 d에서 다항식 차수 ω(d)의 목적 함수를 요구하는 IPCO 2025에서 가장 잘 알려진 하한을 크게 개선하여 차수가 2인 볼록 다항식을 사용하는 하한으로 변경합니다. 특히, 우리의 결과는 상수 차수로 충분한지를 묻는 IPCO 2025의 열린 질문을 확고히 해결하며, 활성 집합 방법이 단순 체계 방법과 일치할 때 모든 피벗 규칙에 대한 하한이 주요한 돌파구를 형성함을 나타냅니다. 우리의 결과는 변형된 곱을 사용하여 재귀적으로 구축된 새로운 확장 형식에 기초하고 있습니다. 이 연구의 주요 특징은 이들이 모든 지수적으로 많은 정점을 보존하면서 포물선의 다각형 근사로 투영된다는 점입니다. 우리는 활성 집합 방법이 이 투영의 포물선 경계를 따르도록 강제하는 2차 목적을 정의하며, 전체 차원 전상에 해당하는 엣지를 따라서 어떤 단축 경로도 허용하지 않습니다.