A reduced proximal-point homotopy method for large-scale non-convex BQP

Xiubo Liang (), Guoqiang Wang () and Bo Yu ()
Additional contact information
Xiubo Liang: Dalian University of Technology
Guoqiang Wang: Business Research and Development department JD.com
Bo Yu: Dalian University of Technology

Computational Optimization and Applications, 2022, vol. 81, issue 2, No 7, 539-567

Abstract: Abstract In this paper, a reduced proximal-point homotopy (RPP-Hom) method is presented for large-scale non-convex box constrained quadratic programming (BQP) problems. As the outer iteration, at each step, the reduced proximal-point (RPP) algorithm applies the proximal point algorithm to a reduced BQP problem. The variables of the reduced subproblem include all free variables and variables at bound with respect to which the optimality conditions are violated. The RPP subproblem is solved by, as the inner iteration, an efficient piecewise linear homotopy path following method. A special termination criterion for the RPP algorithm is given and the global convergence as well as the locally linear convergence to a Karush-Kuhn-Tucker point is proved. Furthermore, a random perturbation procedure is given to modify RPP such that it converges to a local minimizer with probability 1. An accelerated version of RPP is also presented. Numerical experiments show that the RPP-Hom method outperforms the state-of-the-art algorithms for most of the benchmark problems, especially for training non-convex support vector machine.

Keywords: Quadratic programming; Box constraints; Non-convex; Proximal point method; Homotopy method (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-021-00330-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:81:y:2022:i:2:d:10.1007_s10589-021-00330-2

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-021-00330-2

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().