A simplicial decomposition framework for large scale convex quadratic programming

2017/05/25 by Enrico Bettiol, Bettiol, Enrico, Lucas Létocart +5
Computer Science · Decision Sciences · Engineering · Mathematics · #65K05 #90C06 #90C30 #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Risk and Portfolio Optimization #Sparse and Compressive Sensing Techniques #math.OC #msc:65K05 #msc:90C06 #msc:90C30

paper · pdf · doi:10.48550/arxiv.1705.09210

arxiv created 2017/05/25 · openalex publication_date 2017/05/25 · arxiv updated 2017/05/26 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

In this paper, we analyze in depth a simplicial decomposition like algorithmic framework for large scale convex quadratic programming. In particular, we first propose two tailored strategies for handling the master problem. Then, we describe a few techniques for speeding up the solution of the pricing problem. We report extensive numerical experiments on both real portfolio optimization and general quadratic programming problems, showing the efficiency and robustness of the method when compared to Cplex.

Citations

• Benchmarking optimization software with performance profiles
• Fast projection onto the simplex and the \pmb l_\mathbf 1 l 1 ball

Related

• Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization
• An exact dynamic programming algorithm, lower and upper bounds, applied to the large block sale problem
• An Outer Approximation Method for Solving Mixed-Integer Convex Quadratic Programs with Indicators
• Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra
• Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs