Dimensionality Reduction of Affine Variational Inequalities Using Random Projections
This work addresses computational efficiency for researchers and practitioners dealing with high-dimensional optimization problems, offering an incremental improvement through dimensionality reduction techniques.
The paper tackles the problem of solving high-dimensional affine variational inequalities (AVIs) by proposing a randomized algorithm based on the Johnson-Lindenstrauss lemma to reduce dimensionality, producing approximate solutions with high probability and enabling faster exact solutions through initial point generation. Numerical experiments show the algorithm provides good approximations at low dimensions and substantial time savings.
We present a method for dimensionality reduction of an affine variational inequality (AVI) defined over a compact feasible region. Centered around the Johnson Lindenstrauss lemma, our method is a randomized algorithm that produces with high probability an approximate solution for the given AVI by solving a lower-dimensional AVI. The algorithm allows the lower dimension to be chosen based on the quality of approximation desired. The algorithm can also be used as a subroutine in an exact algorithm for generating an initial point close to the solution. The lower-dimensional AVI is obtained by appropriately projecting the original AVI on a randomly chosen subspace. The lower-dimensional AVI is solved using standard solvers and from this solution an approximate solution to the original AVI is recovered through an inexpensive process. Our numerical experiments corroborate the theoretical results and validate that the algorithm provides a good approximation at low dimensions and substantial savings in time for an exact solution.