An accelerated proximal gradient algorithm for singly linearly constrained quadratic programs with box constraints.

Area of Science:

• Optimization Theory
• Machine Learning
• Numerical Analysis

Background:

• Proximal gradient algorithms are established for non-smooth convex optimization.
• Singly linearly constrained quadratic programs with box constraints are prevalent in various applications.
• Existing methods may lack efficiency or require complex procedures for these specific problems.

Purpose of the Study:

• To propose an accelerated proximal gradient algorithm tailored for singly linearly constrained quadratic programs with box constraints.
• To enhance the efficiency and convergence properties of solving this class of optimization problems.
• To demonstrate the algorithm's applicability and performance in a real-world machine learning context.

Main Methods:

• An accelerated proximal gradient algorithm is introduced.
• Each iteration involves solving a simplified subproblem with a diagonal, positive-definite Hessian matrix.
• The subproblem is efficiently solved by finding the root of a piecewise linear function, eliminating the need for line search.

Main Results:

• The proposed algorithm achieves an ε-optimal solution within a proven number of iterations.
• Global convergence is established under mild conditions.
• Numerical experiments on training support vector machines indicate the algorithm's high efficiency.

Conclusions:

• The novel accelerated proximal gradient algorithm provides an efficient and robust method for solving singly linearly constrained quadratic programs with box constraints.
• The algorithm's ability to avoid line search and guarantee convergence makes it a practical tool.
• Its demonstrated effectiveness in support vector machine training highlights its potential for broader applications in machine learning and optimization.