An Accelerated Proximal Gradient Algorithm for Singly Linearly Constrained Quadratic Programs with Box Constraints
Recently, the existed proximal gradient algorithms had been used to solve non-smooth convex optimization problems. As a special nonsmooth convex problem, the singly linearly constrained quadratic programs with box constraints appear in a wide range of applications. Hence, we propose an accelerated p...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2013/246596 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850229411141386240 |
|---|---|
| author | Congying Han Mingqiang Li Tong Zhao Tiande Guo |
| author_facet | Congying Han Mingqiang Li Tong Zhao Tiande Guo |
| author_sort | Congying Han |
| collection | DOAJ |
| description | Recently, the existed proximal gradient algorithms had been used to solve non-smooth convex optimization problems. As a special nonsmooth convex problem, the singly linearly constrained quadratic programs with box constraints appear in a wide range of applications. Hence, we propose an accelerated proximal gradient algorithm for singly linearly constrained quadratic programs with box constraints. At each iteration, the subproblem whose Hessian matrix is diagonal and positive definite is an easy model which can be solved efficiently via searching a root of a piecewise linear function. It
is proved that the new algorithm can terminate at an ε-optimal solution within O(1/ε) iterations. Moreover, no line search is needed in this algorithm, and the global convergence can be proved under mild conditions. Numerical results are reported for solving quadratic programs arising from the training of support vector machines, which show that the new algorithm is efficient. |
| format | Article |
| id | doaj-art-1f96d53e95f34e0fbd656ebcfac3ae30 |
| institution | OA Journals |
| issn | 1537-744X |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-1f96d53e95f34e0fbd656ebcfac3ae302025-08-20T02:04:14ZengWileyThe Scientific World Journal1537-744X2013-01-01201310.1155/2013/246596246596An Accelerated Proximal Gradient Algorithm for Singly Linearly Constrained Quadratic Programs with Box ConstraintsCongying Han0Mingqiang Li1Tong Zhao2Tiande Guo3School of Mathematical Sciences, University of Chinese Academy of Sciences, Shijingshan District, Beijing 100049, ChinaCollege of Information Science and Engineering, Shandong University of Science and Technology, Qingdao 266590, ChinaSchool of Mathematical Sciences, University of Chinese Academy of Sciences, Shijingshan District, Beijing 100049, ChinaSchool of Mathematical Sciences, University of Chinese Academy of Sciences, Shijingshan District, Beijing 100049, ChinaRecently, the existed proximal gradient algorithms had been used to solve non-smooth convex optimization problems. As a special nonsmooth convex problem, the singly linearly constrained quadratic programs with box constraints appear in a wide range of applications. Hence, we propose an accelerated proximal gradient algorithm for singly linearly constrained quadratic programs with box constraints. At each iteration, the subproblem whose Hessian matrix is diagonal and positive definite is an easy model which can be solved efficiently via searching a root of a piecewise linear function. It is proved that the new algorithm can terminate at an ε-optimal solution within O(1/ε) iterations. Moreover, no line search is needed in this algorithm, and the global convergence can be proved under mild conditions. Numerical results are reported for solving quadratic programs arising from the training of support vector machines, which show that the new algorithm is efficient.http://dx.doi.org/10.1155/2013/246596 |
| spellingShingle | Congying Han Mingqiang Li Tong Zhao Tiande Guo An Accelerated Proximal Gradient Algorithm for Singly Linearly Constrained Quadratic Programs with Box Constraints The Scientific World Journal |
| title | An Accelerated Proximal Gradient Algorithm for Singly Linearly Constrained Quadratic Programs with Box Constraints |
| title_full | An Accelerated Proximal Gradient Algorithm for Singly Linearly Constrained Quadratic Programs with Box Constraints |
| title_fullStr | An Accelerated Proximal Gradient Algorithm for Singly Linearly Constrained Quadratic Programs with Box Constraints |
| title_full_unstemmed | An Accelerated Proximal Gradient Algorithm for Singly Linearly Constrained Quadratic Programs with Box Constraints |
| title_short | An Accelerated Proximal Gradient Algorithm for Singly Linearly Constrained Quadratic Programs with Box Constraints |
| title_sort | accelerated proximal gradient algorithm for singly linearly constrained quadratic programs with box constraints |
| url | http://dx.doi.org/10.1155/2013/246596 |
| work_keys_str_mv | AT congyinghan anacceleratedproximalgradientalgorithmforsinglylinearlyconstrainedquadraticprogramswithboxconstraints AT mingqiangli anacceleratedproximalgradientalgorithmforsinglylinearlyconstrainedquadraticprogramswithboxconstraints AT tongzhao anacceleratedproximalgradientalgorithmforsinglylinearlyconstrainedquadraticprogramswithboxconstraints AT tiandeguo anacceleratedproximalgradientalgorithmforsinglylinearlyconstrainedquadraticprogramswithboxconstraints AT congyinghan acceleratedproximalgradientalgorithmforsinglylinearlyconstrainedquadraticprogramswithboxconstraints AT mingqiangli acceleratedproximalgradientalgorithmforsinglylinearlyconstrainedquadraticprogramswithboxconstraints AT tongzhao acceleratedproximalgradientalgorithmforsinglylinearlyconstrainedquadraticprogramswithboxconstraints AT tiandeguo acceleratedproximalgradientalgorithmforsinglylinearlyconstrainedquadraticprogramswithboxconstraints |