A Comparative Study of the Proximal Distance Algorithm and the Primal Dual Hybrid Gradient method for Statistical Problems

Abstract

In this thesis, we compare the proximal distance algorithm and the primal dual hybrid gradient methods for solving convex constrained problems with linear operators in constraints. Unlike other algorithms containing inner minimization subproblem, both algorithms can be applied with simple update rules. Algorithms are implemented and compared with existing software through six examples: linear programming, constrained least squares, estimating the closest kinship matrix, projection onto a second-order cone, low rank matrix completion, and logistic regression with partially ordered constraints. The solution of the proximal distance algorithm would lose optimality and stability when parameters are chosen inappropriately, while the output of the primal dual hybrid gradient methods is robust to the selection of parameters. Numerical results show that the primal dual hybrid gradient methods usually outperform and the proximal distance algorithm is still competitive with existent programs.

본 논문에서는 제약조건에 선형연산자가 포함된 볼록 최적화 문제에 대한 근위 거리 알고리즘과 원시-쌍대 복합 경사법을 비교한다. 타 알고리즘들이 제약조건의 선형연산자로 인한 계산상의 어려움을 겪는데 비해, 두 알고리즘은 간단한 업데이트 식으로 문제를 쉽게 해결할 수 있다. 본 논문에서는 근위 거리 알고리즘과 원시-쌍대 복합 경사법을 소개하고, 이들을 여러 통계적 문제들에 적용한 해답을 제시하고, 결과값을 비교하였다. 이 때, 원시-쌍대 복합 경사법의 최적해는 파라미터의 선택의 영향을 적게 받는 반면 근위 거리 알고리즘의 최적해는 파라미터가 부적절하게 선택될 경우 최적성이나 안정성을 잃을 수 있다. 마지막으로, 결과값을 통하여 원시-쌍대 복합 경사법이 뛰어난 성능을 보이며 근위 거리 알고리즘 또한 현존하는 알고리즘에 뒤지지 않음을 확인하였다.