Proximal Distance Algorithms: Theory and Practice.

Area of Science:

• Optimization Theory
• Numerical Analysis
• Applied Mathematics

Background:

• Constrained minimization problems are fundamental in various scientific and engineering disciplines.
• Classical penalty methods and distance majorization are established optimization techniques.
• There is a continuous need for efficient and robust algorithms for high-dimensional optimization.

Purpose of the Study:

• To introduce and analyze proximal distance algorithms for constrained minimization.
• To demonstrate the applicability and efficiency of these algorithms in diverse high-dimensional settings.
• To compare the performance of proximal distance algorithms against established methods like Interior Point and ADMM.

Main Methods:

• Proximal distance algorithms combine penalty methods with distance majorization.
• Each iteration involves minimizing a surrogate function using proximal maps and projections.
• The algorithms are analyzed for both convex and non-convex optimization problems.

Main Results:

• Proximal distance algorithms exhibit competitive or superior speed compared to traditional methods.
• The algorithms are successfully applied to a range of problems: linear programming, constrained least squares, kinship matrix projection, second-order cone projection, Horn's copositive index, linear complementarity programming, and sparse principal components analysis.
• For convex problems, convergence properties align with proximal gradient algorithms; for non-convex problems, convergence can be analyzed using Zangwill's theorem.

Conclusions:

• Proximal distance algorithms provide a versatile and efficient framework for solving constrained optimization problems.
• The simplicity of each iteration allows for competitive performance despite potentially high iteration counts.
• The developed algorithms are readily implementable due to known explicit projections and proximal maps.