CaltechAUTHORS
  A Caltech Library Service

A note on convex relaxations for the inverse eigenvalue problem

Candogan, Utkan and Soh, Yong Sheng and Chandrasekaran, Venkat (2021) A note on convex relaxations for the inverse eigenvalue problem. Optimization Letters . ISSN 1862-4472. (In Press) https://resolver.caltech.edu/CaltechAUTHORS:20201016-144215019

[img] PDF - Submitted Version
See Usage Policy.

994Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20201016-144215019

Abstract

The affine inverse eigenvalue problem consists of identifying a real symmetric matrix with a prescribed set of eigenvalues in an affine space. Due to its ubiquity in applications, various instances of the problem have been widely studied in the literature. Previous algorithmic solutions were typically nonconvex heuristics and were often developed in a case-by-case manner for specific structured affine spaces. In this short note we describe a general family of convex relaxations for the problem by reformulating it as a question of checking feasibility of a system of polynomial equations, and then leveraging tools from the optimization literature to obtain semidefinite programming relaxations. Our system of polynomial equations may be viewed as a matricial analog of polynomial reformulations of 0/1 combinatorial optimization problems, for which semidefinite relaxations have been extensively investigated. We illustrate numerically the utility of our approach in stylized examples that are drawn from various applications.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/s11590-021-01708-1DOIArticle
https://link.springer.com/article/10.1007/s11590-021-01708-1PublisherArticle
https://rdcu.be/cfjRKPublisherFree ReadCube access
https://arxiv.org/abs/1911.02225arXivDiscussion Paper
ORCID:
AuthorORCID
Candogan, Utkan0000-0003-3920-402X
Soh, Yong Sheng0000-0003-3367-1401
Additional Information:© The Author(s), under exclusive licence to Springer-Verlag GmbH, DE part of Springer Nature 2021. Received 06 November 2019; Accepted 22 January 2021; Published 15 February 2021. The authors were supported in part by NSF Grants CCF-1350590 and CCF-1637598, by AFOSR Grant FA9550-16-1-0210, and by a Sloan research fellowship.
Funders:
Funding AgencyGrant Number
NSFCCF-1350590
NSFCCF-1637598
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0210
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:Combinatorial optimization; Real algebraic geometry; Schur–Horn orbitope; Semidefinite programming; Sums of squares polynomials
Classification Code:MSC: 15A18, 15A29, 90C22
Record Number:CaltechAUTHORS:20201016-144215019
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20201016-144215019
Official Citation:Candogan, U., Soh, Y.S. & Chandrasekeran, V. A note on convex relaxations for the inverse eigenvalue problem. Optim Lett (2021). https://doi.org/10.1007/s11590-021-01708-1
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106118
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:16 Oct 2020 22:10
Last Modified:16 Feb 2021 23:10

Repository Staff Only: item control page