  


Random projections for quadratic programs
Claudia D'Ambrosio(dambrosiolix.polytechnique.fr) Abstract: Random projections map a set of points in a high dimensional space to a lower dimen sional one while approximately preserving all pairwise Euclidean distances. While random projections are usually applied to numerical data, we show they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving the higherdimensional original problem, we solve the projected problem more efficiently. We also show how to retrieve a feasible solution of the original problem from the lowerdimensional solution of the projected problem. We then show that the retrieved solution can be used to bound the optimal objective function value of the original problem from below and above, and show that the lower and upper bounds are not too far apart. We then discuss a set of computational results on randomly generated instances, as well as a variant of Markowitz’ portfolio problem. Keywords: nonlinear programming, polynomial optimization, largescale optimization, approximation, JohnsonLindenstrauss Lemma Category 1: Nonlinear Optimization (Quadratic Programming ) Citation: CNRS Ecole Polytechnique May 2019 (preliminary version published in IPCO Proceedings 2019). Download: [PDF] Entry Submitted: 07/31/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  