반정형 프로그래밍을 위한 혼합 페널티 방법으로 최대 절단 문제 해결

본 논문은 볼록 및 원뿔 최적화 분야인 반정형 프로그래밍(SDP)의 기회를 활용하려는 시도입니다. 실제로, 많은 NP-난해 문제를 이 접근 방식으로 해결할 수 있습니다. 따라서, 우리는 조합적 및 이차 문제를 모델링하고 강한 완화를 제공하는 SDP의 강점을 조사하여 이 견고한 모델을 해결하기 위한 새로운 다항 시간 알고리즘을 제시하고자 합니다. 이 알고리즘은 비선형 프로그램을 해결하기 위해 처음 사용되었으며, 이를 SDP 프로그램으로 확장하려고 합니다. 실제로, 이 알고리즘은 두 가지 페널티 방법의 조합을 설계합니다. 첫 번째는 프라이멀-듀얼 내부 점(PDIM) 방법이고 두 번째는 프라이멀-듀얼 외부 점(PDEM) 방법입니다. 전역적으로 수렴하는 첫 번째 방법과 달리, 두 번째 방법은 프라이멀 듀얼 비선형 재조정 방법이라고도 하며, 지역적으로 초선형/이차 수렴을 가집니다. 따라서 내부-외부 점 방법(IEPM)을 기반으로 한 혼합 알고리즘을 사용하는 것이 적절해 보입니다. 사실, 이 해결책은 내부 방법에서 시작하여 특정 실행 수준에서 외부 방법으로 진행됩니다. 따라서, 순열 수준을 파악하기 위해 수렴 평가 함수를 사용합니다. 평가를 통해 우리의 접근 방식이 최대 절단 문제의 몇 가지 사례를 해결하는 데 사용된 것이 확인되었습니다. 이 문제는 많은 실제 문제에서 발생하는 중심 그래프 이론 모델이며, 수년 동안 많은 연구자들의 관심을 끌어온 여러 NP-난해 문제 중 하나입니다. 그런 다음, 우리는 외부 점 방법 하위 루틴을 포함하도록 수정된 반정형 프로그래밍 해결기 SDPA(반정형 프로그래밍 알고리즘)를 사용했습니다. 계산 성능 측면에서 문제 크기가 증가함에 따라 내부-외부 점 알고리즘이 상대적으로 더 빨라진다는 결론을 내립니다. 얻어진 수치 결과는 유망합니다.