Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs.
Saved in:
| Title: | Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs. |
|---|---|
| Authors: | Hubert, Evelyne1 (AUTHOR) evelyne.hubert@inria.fr, Metzlaff, Tobias1,2 (AUTHOR) tobias.metzlaff@rptu.de, Moustrou, Philippe3 (AUTHOR) philippe.moustrou@math.univ-toulouse.fr, Riener, Cordian4 (AUTHOR) cordian.riener@uit.no |
| Source: | Mathematical Programming. Sep2025, Vol. 213 Issue 1/2, p517-573. 57p. |
| Subjects: | Crystal symmetry, Chebyshev polynomials, Mathematical optimization, Graph coloring, Coxeter groups, Trigonometric functions, Graph theory |
| Abstract: | We provide a new approach to the optimization of trigonometric polynomials with crystallographic symmetry. This approach widens the bridge between trigonometric and polynomial optimization. The trigonometric polynomials considered are supported on weight lattices associated to crystallographic root systems and are assumed invariant under the associated reflection group. On one hand the invariance allows us to rewrite the objective function in terms of generalized Chebyshev polynomials of the generalized cosines; On the other hand the generalized cosines parameterize a compact basic semi algebraic set, this latter being given by an explicit polynomial matrix inequality. The initial problem thus boils down to a polynomial optimization problem that is straightforwardly written in terms of generalized Chebyshev polynomials. The minimum is to be computed by a converging sequence of lower bounds as given by a hierarchy of relaxations based on the Hol–Scherer Positivstellensatz and indexed by the weighted degree associated to the root system. This new method for trigonometric optimization was motivated by its application to estimate the spectral bound on the chromatic number of set avoiding graphs. We examine cases of the literature where the avoided set affords crystallographic symmetry. In some cases we obtain new analytic proofs for sharp bounds on the chromatic number while in others we compute new lower bounds numerically. [ABSTRACT FROM AUTHOR] |
| Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 187668708 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Hubert%2C+Evelyne%22">Hubert, Evelyne</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> evelyne.hubert@inria.fr</i><br /><searchLink fieldCode="AR" term="%22Metzlaff%2C+Tobias%22">Metzlaff, Tobias</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> tobias.metzlaff@rptu.de</i><br /><searchLink fieldCode="AR" term="%22Moustrou%2C+Philippe%22">Moustrou, Philippe</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> philippe.moustrou@math.univ-toulouse.fr</i><br /><searchLink fieldCode="AR" term="%22Riener%2C+Cordian%22">Riener, Cordian</searchLink><relatesTo>4</relatesTo> (AUTHOR)<i> cordian.riener@uit.no</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Mathematical+Programming%22">Mathematical Programming</searchLink>. Sep2025, Vol. 213 Issue 1/2, p517-573. 57p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Crystal+symmetry%22">Crystal symmetry</searchLink><br /><searchLink fieldCode="DE" term="%22Chebyshev+polynomials%22">Chebyshev polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+coloring%22">Graph coloring</searchLink><br /><searchLink fieldCode="DE" term="%22Coxeter+groups%22">Coxeter groups</searchLink><br /><searchLink fieldCode="DE" term="%22Trigonometric+functions%22">Trigonometric functions</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We provide a new approach to the optimization of trigonometric polynomials with crystallographic symmetry. This approach widens the bridge between trigonometric and polynomial optimization. The trigonometric polynomials considered are supported on weight lattices associated to crystallographic root systems and are assumed invariant under the associated reflection group. On one hand the invariance allows us to rewrite the objective function in terms of generalized Chebyshev polynomials of the generalized cosines; On the other hand the generalized cosines parameterize a compact basic semi algebraic set, this latter being given by an explicit polynomial matrix inequality. The initial problem thus boils down to a polynomial optimization problem that is straightforwardly written in terms of generalized Chebyshev polynomials. The minimum is to be computed by a converging sequence of lower bounds as given by a hierarchy of relaxations based on the Hol–Scherer Positivstellensatz and indexed by the weighted degree associated to the root system. This new method for trigonometric optimization was motivated by its application to estimate the spectral bound on the chromatic number of set avoiding graphs. We examine cases of the literature where the avoided set affords crystallographic symmetry. In some cases we obtain new analytic proofs for sharp bounds on the chromatic number while in others we compute new lower bounds numerically. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=187668708 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10107-024-02149-1 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 57 StartPage: 517 Subjects: – SubjectFull: Crystal symmetry Type: general – SubjectFull: Chebyshev polynomials Type: general – SubjectFull: Mathematical optimization Type: general – SubjectFull: Graph coloring Type: general – SubjectFull: Coxeter groups Type: general – SubjectFull: Trigonometric functions Type: general – SubjectFull: Graph theory Type: general Titles: – TitleFull: Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Hubert, Evelyne – PersonEntity: Name: NameFull: Metzlaff, Tobias – PersonEntity: Name: NameFull: Moustrou, Philippe – PersonEntity: Name: NameFull: Riener, Cordian IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Sep2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 00255610 Numbering: – Type: volume Value: 213 – Type: issue Value: 1/2 Titles: – TitleFull: Mathematical Programming Type: main |
| ResultId | 1 |
