Iterated linear optimization
Authors:
Pedro F. Felzenszwalb, Caroline J. Klivans and Alice Paul
Journal:
Quart. Appl. Math. 79 (2021), 601-615
MSC (2020):
Primary 90C25, 90C27, 15B48, 15A18
DOI:
https://doi.org/10.1090/qam/1594
Published electronically:
May 6, 2021
MathSciNet review:
4328140
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
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.
References
- Farid Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim. 5 (1995), no. 1, 13–51. MR 1315703, DOI 10.1137/0805002
- M. D. Ašić and D. D. Adamović, Limit points of sequences in metric spaces, Amer. Math. Monthly 77 (1970), 613–616. MR 264599, DOI 10.2307/2316738
- Boaz Barak, Jonathan A. Kelner, and David Steurer, Rounding sum-of-squares relaxations, Proceedings of the forty-sixth annual acm symposium on theory of computing, 2014, pp. 31–40.
- Heinz H. Bauschke, Regina S. Burachik, Patrick L. Combettes, Veit Elser, D. Russell Luke, and Henry Wolkowicz (eds.), Fixed-point algorithms for inverse problems in science and engineering, Springer Optimization and Its Applications, vol. 49, Springer, New York, 2011. MR 2858828, DOI 10.1007/978-1-4419-9569-8
- Vasile Berinde, Iterative approximation of fixed points, 2nd ed., Lecture Notes in Mathematics, vol. 1912, Springer, Berlin, 2007. MR 2323613
- Diego Cifuentes, Sameer Agarwal, Pablo A. Parrilo, and Rekha R. Thomas, On the local stability of semidefinite relaxations, arXiv preprint arXiv:1710.04287 (2017).
- Diego Cifuentes, Corey Harris, and Bernd Sturmfels, The geometry of SDP-exactness in quadratic optimization, Math. Program. 182 (2020), no. 1-2, Ser. A, 399–428. MR 4115654, DOI 10.1007/s10107-019-01399-8
- Pedro Felzenszwalb, Caroline Klivans, and Alice Paul, Clustering with semidefinite programming and fixed point iteration, arXiv preprint arXiv:2012.09202 (2020).
- Marguerite Frank and Philip Wolfe, An algorithm for quadratic programming, Naval Res. Logist. Quart. 3 (1956), 95–110. MR 89102, DOI 10.1002/nav.3800030109
- A. Frieze and M. Jerrum, Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION, Algorithmica 18 (1997), no. 1, 67–81. MR 1432029, DOI 10.1007/BF02523688
- Oded Galor, Discrete dynamical systems, Springer, Berlin, 2007. MR 2311904, DOI 10.1007/3-540-36776-4
- Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228, DOI 10.1145/227683.227684
- Richard A. Holmgren, A first course in discrete dynamical systems, Universitext, Springer-Verlag, New York, 1994. MR 1269109, DOI 10.1007/978-1-4684-0222-3
- Monique Laurent, Cuts, matrix completions and graph rigidity, Math. Programming 79 (1997), no. 1-3, Ser. B, 255–283. Lectures on mathematical programming (ismp97) (Lausanne, 1997). MR 1464770, DOI 10.1016/S0025-5610(97)00043-9
- Monique Laurent and Svatopluk Poljak, On a positive semidefinite relaxation of the cut polytope, Linear Algebra Appl. 223/224 (1995), 439–461. Special issue honoring Miroslav Fiedler and Vlastimil Pták. MR 1340705, DOI 10.1016/0024-3795(95)00271-R
- Prasad Raghavendra and David Steurer, How to round any CSP, 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 586–594. MR 2648437, DOI 10.1109/FOCS.2009.74
- Cynthia Vinzant, What is $\ldots$ a spectrahedron?, Notices Amer. Math. Soc. 61 (2014), no. 5, 492–494. MR 3203240, DOI 10.1090/noti1116
References
- Farid Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim. 5 (1995), no. 1, 13–51. MR 1315703, DOI 10.1137/0805002
- M. D. Ašić and D. D. Adamović, Limit points of sequences in metric spaces, Amer. Math. Monthly 77 (1970), 613–616. MR 264599, DOI 10.2307/2316738
- Boaz Barak, Jonathan A. Kelner, and David Steurer, Rounding sum-of-squares relaxations, Proceedings of the forty-sixth annual acm symposium on theory of computing, 2014, pp. 31–40.
- Heinz H. Bauschke, Regina S. Burachik, Patrick L. Combettes, Veit Elser, D. Russell Luke, and Henry Wolkowicz (eds.), Fixed-point algorithms for inverse problems in science and engineering, Springer Optimization and Its Applications, vol. 49, Springer, New York, 2011. MR 2858828, DOI 10.1007/978-1-4419-9569-8
- Vasile Berinde, Iterative approximation of fixed points, 2nd ed., Lecture Notes in Mathematics, vol. 1912, Springer, Berlin, 2007. MR 2323613
- Diego Cifuentes, Sameer Agarwal, Pablo A. Parrilo, and Rekha R. Thomas, On the local stability of semidefinite relaxations, arXiv preprint arXiv:1710.04287 (2017).
- Diego Cifuentes, Corey Harris, and Bernd Sturmfels, The geometry of SDP-exactness in quadratic optimization, Math. Program. 182 (2020), no. 1-2, Ser. A, 399–428. MR 4115654, DOI 10.1007/s10107-019-01399-8
- Pedro Felzenszwalb, Caroline Klivans, and Alice Paul, Clustering with semidefinite programming and fixed point iteration, arXiv preprint arXiv:2012.09202 (2020).
- Marguerite Frank and Philip Wolfe, An algorithm for quadratic programming, Naval Res. Logist. Quart. 3 (1956), 95–110. MR 89102, DOI 10.1002/nav.3800030109
- A. Frieze and M. Jerrum, Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION, Algorithmica 18 (1997), no. 1, 67–81. MR 1432029, DOI 10.1007/BF02523688
- Oded Galor, Discrete dynamical systems, Springer, Berlin, 2007. MR 2311904, DOI 10.1007/3-540-36776-4
- Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228, DOI 10.1145/227683.227684
- Richard A. Holmgren, A first course in discrete dynamical systems, Universitext, Springer-Verlag, New York, 1994. MR 1269109, DOI 10.1007/978-1-4684-0222-3
- Monique Laurent, Cuts, matrix completions and graph rigidity: Lectures on mathematical programming (ismp97) (Lausanne, 1997), Math. Programming 79 (1997), no. 1-3, Ser. B, 255–283. MR 1464770, DOI 10.1016/S0025-5610(97)00043-9
- Monique Laurent and Svatopluk Poljak, On a positive semidefinite relaxation of the cut polytope: Special issue honoring Miroslav Fiedler and Vlastimil Pták, Linear Algebra Appl. 223/224 (1995), 439–461. MR 1340705, DOI 10.1016/0024-3795(95)00271-R
- Prasad Raghavendra and David Steurer, How to round any CSP, 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 586–594. MR 2648437, DOI 10.1109/FOCS.2009.74
- Cynthia Vinzant, What is $\ldots$ a spectrahedron?, Notices Amer. Math. Soc. 61 (2014), no. 5, 492–494. MR 3203240, DOI 10.1090/noti1116
Similar Articles
Retrieve articles in Quarterly of Applied Mathematics
with MSC (2020):
90C25,
90C27,
15B48,
15A18
Retrieve articles in all journals
with MSC (2020):
90C25,
90C27,
15B48,
15A18
Additional Information
Pedro F. Felzenszwalb
Affiliation:
School of Engineering, Brown University, Providence, Rhode Island 02912
MR Author ID:
820866
Email:
pff@brown.edu
Caroline J. Klivans
Affiliation:
Division of Applied Mathematics, Brown University, Providence, Rhode Island 02912
MR Author ID:
754274
Email:
klivans@brown.edu
Alice Paul
Affiliation:
Department of Biostatistics, Brown University, Providence, Rhode Island 02912
MR Author ID:
937436
Email:
alice\textunderscore paul@brown.edu
Keywords:
Fixed point iteration,
linear optimization,
semidefinite programming,
elliptope
Received by editor(s):
March 3, 2021
Received by editor(s) in revised form:
March 29, 2021
Published electronically:
May 6, 2021
Article copyright:
© Copyright 2021
Brown University
