Random projections for quadratic programs
- PDF / 754,772 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 216 Views
Series B
Random projections for quadratic programs Claudia D’Ambrosio1 · Leo Liberti1
· Pierre-Louis Poirion2 · Ky Vu3
Received: 10 June 2019 / Accepted: 29 April 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract Random projections map a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Although random projections are usually applied to numerical data, we show in this paper that they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving the higher-dimensional original problem, we solve the projected problem more efficiently. This yields a feasible solution of the original problem. We prove lower and upper bounds of this feasible solution w.r.t. the optimal objective function value of the original problem. We then discuss some computational results on randomly generated instances, as well as a variant of Markowitz’ portfolio problem. It turns out that our method can find good feasible solutions of very large instances. Keywords Nonlinear programming · Polynomial optimization · Large-scale optimization · Approximation · Johnson–Lindenstrauss lemma Mathematics Subject Classification 90C20 · 60B20
This paper has received Funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant Agreement n. 764759 “MINOA”.
B
Leo Liberti [email protected] Claudia D’Ambrosio [email protected] Pierre-Louis Poirion [email protected] Ky Vu [email protected]
1
CNRS LIX École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France
2
RIKEN Center for Advanced Intelligence Project, Tokyo, Japan
3
Department of Mathematics, FPT University, Hoa Lac Hi-Tech Park, Hanoi, Vietnam
123
C. D’Ambrosio et al.
1 Introduction The goal of this paper is to show that Random Projections (RP) applied to Quadratic Programming (QP) problems subject to linear inequality constraints yield a QP with fewer variables, the solution of which is an approximate solution for the original QP. We consider the following QP formulation: P ≡ max x x Qx + c x Ax ≤ b,
(1)
where x is a vector of n decision variables, Q is a symmetric n × n matrix, c ∈ Rn , A is m × n and b ∈ Rm . We make three assumptions about Eq. (1): 1. We assume that Ax ≤ b defines a full dimensional polytope. 2. We assume we are given the radius R of a ball containing the polytope Ax ≤ b. 3. We assume that all the rows of A are unit vectors. This assumption, however, is without loss of generality (w.l.o.g.): we let μi = Ai , where Ai is the i-th row of A; we then replace each Ai by μAii and bi by μbii ; this yields ∀i ≤ n Aμi i x ≤ μbii , which satisfies the assumption. We remark that Assumption 3 might affect the problem input adversely, yielding instances that end up being difficult to solve for numerical instability reasons. No assumption is made on Q, whi
Data Loading...
