Random projections for conic programs

Autor: Ky Khac Vu, Pierre-Louis Poirion, Leo Liberti
Přispěvatelé: Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), RIKEN Center for Advanced Intelligence Project [Tokyo] (RIKEN AIP), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN), FPT University
Jazyk: angličtina
Rok vydání: 2021
Předmět:
[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC]
010103 numerical & computational mathematics
01 natural sciences
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Numerical Analysis
0101 mathematics
Johnson-Lindenstrauss Lemma
Approximation
Mathematics - Optimization and Control
Mathematics
Numerical Analysis
Mathematical Programming
90C22
90C06
Algebra and Number Theory
Conic programming
Probability (math.PR)
010102 general mathematics
Jordan algebra
Order (ring theory)
Numerical Analysis (math.NA)
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Algebra
Optimization and Control (math.OC)
Conic section
Computer Science::Programming Languages
Geometry and Topology
2000 MSC: 90C22
90C06
Mathematics - Probability
Zdroj: Linear Algebra and its Applications
Linear Algebra and its Applications, Elsevier, 2021, 626, pp.204-220. ⟨10.1016/j.laa.2021.06.010⟩
ISSN: 0024-3795
DOI: 10.1016/j.laa.2021.06.010⟩
Popis: International audience; We discuss the application of random projections to conic programming: notably linear, second-order and semidefinite programs. We prove general approximation results on feasibility and optimality using the framework of formally real Jordan algebras. We then discuss some computational experiments on randomly generated semidefinite programs in order to illustrate the practical applicability of our ideas.
Databáze: OpenAIRE
Externí odkaz: