Iterated linear optimization

DOI10.1090/QAM/1594MaRDI QIDQ5157412zbMATH OpenOpenAlexFDO

Authors Pedro F. Felzenszwalb, Alice Paul, Caroline Klivans

Publication date 18 October 2021

Published in Quarterly of Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.02213

zbMATH Keywords

elliptopefixed point iterationlinear optimizationsemidefinite programming

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Positive matrices and their generalizations; cones of matrices (15B48) Convex programming (90C25) Combinatorial optimization (90C27)

Abstract: We introduce a fixed point iteration process built on optimization of a linear function over a compact domain. We prove the process always converges to a fixed point and explore the set of fixed points in various convex sets. In particular, we consider elliptopes and derive an algebraic characterization of their fixed points. We show that the attractive fixed points of an elliptope are exactly its vertices. Finally, we discuss how fixed point iteration can be used for rounding the solution of a semidefinite programming relaxation.

Recommendations

• An ellipsoid algorithm for the computation of fixed points
• scientific article; zbMATH DE number 3936945
• On a generalization of iterated and randomized rounding
• New developments in iterated rounding (invited talk)
• scientific article; zbMATH DE number 932403

Cites work

• A first course in discrete dynamical systems
• Cuts, matrix completions and graph rigidity
• Discrete dynamical systems.
• Fixed-point algorithms for inverse problems in science and engineering. Based on the presentations at the interdisciplinary workshop, BIRS, Banff, Canada, November 1--6, 2009.
• How to Round Any CSP
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Iterative approximation of fixed points
• Limit Points of Sequences in Metric Spaces
• On a positive semidefinite relaxation of the cut polytope
• Rounding sum-of-squares relaxations
• The geometry of SDP-exactness in quadratic optimization
• What is \dots a spectrahedron?

Cited in

(2)

• Iterative linear programming solution of convex programs
• Iterative Optimization with Equality Constraints

This page was built for publication: Iterated linear optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5157412)