Using Positive Spanning Sets to Achieve d-Stationarity with the Boosted DC Algorithm.

Area of Science:

• Optimization Algorithms
• Numerical Analysis
• Machine Learning

Background:

• The Difference of Convex functions Algorithm (DCA) is a standard method for minimizing the difference between two convex functions.
• The Boosted DC Algorithm (BDCA) accelerates DCA using a line search, often leading to faster convergence.
• However, both DCA and BDCA may converge to critical points that are not local minima.

Purpose of the Study:

• To enhance the solution quality of the Boosted DC Algorithm (BDCA) by ensuring d-stationarity.
• To combine BDCA with Derivative-Free Optimization (DFO) to address limitations in finding local minima.
• To evaluate the performance of the combined approach on a Minimum-Sum-of-Squares clustering problem.

Main Methods:

• Integration of a Derivative-Free Optimization (DFO) algorithm with the Boosted DC Algorithm (BDCA).
• The DFO component is used to enforce d-stationarity at the solution points found by BDCA.
• Computational experiments were conducted using a Minimum-Sum-of-Squares clustering problem.

Main Results:

• The proposed hybrid method successfully enforces d-stationarity, leading to improved solution quality.
• Numerical results indicate that the new approach yields better solutions compared to standalone BDCA.
• The combined method remains faster than the original Difference of Convex functions Algorithm (DCA) in most tested scenarios.

Conclusions:

• Combining BDCA with DFO is an effective strategy for finding higher-quality solutions in optimization problems.
• The enhanced method addresses the issue of converging to non-local minima critical points.
• This approach offers a practical improvement for problems like Minimum-Sum-of-Squares clustering, balancing solution quality and computational speed.