Lower Bounds for Cubic Optimization over the Sphere

Christoph Buchheim (), Marcia Fampa () and Orlando Sarmiento ()
Additional contact information
Christoph Buchheim: Technische Universität Dortmund
Marcia Fampa: Universidade Federal do Rio de Janeiro
Orlando Sarmiento: Universidade de São Paulo

Journal of Optimization Theory and Applications, 2021, vol. 188, issue 3, No 10, 823-846

Abstract: Abstract We consider the problem of minimizing a polynomial function of degree three over the boundary of the sphere. If the objective is quadratic instead of cubic, this is the well-studied trust region subproblem, which is known to be tractable. In the cubic case, the problem turns out to be NP-hard. In this paper, we derive and evaluate different approaches for computing lower bounds for the cubic problem. Alternatively to semidefinite programming relaxations proposed in the literature, our approaches do not lift the problem to higher dimensions. The strongest bounds are obtained by Lagrangian decomposition, resulting in a number of parameterized quadratic problems for which the above-mentioned results can be exploited, in particular the existence of a tractable dual problem. In an experimental evaluation, we consider the cubic one-spherical optimization problem, with homogeneous objective function, and compare the bounds generated with the different approaches proposed, for small examples from the literature and for randomly generated instances of varied dimensions.

Keywords: Cubic optimization problem; Trust region subproblem; Global optimization; Dual bound (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-021-01809-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:188:y:2021:i:3:d:10.1007_s10957-021-01809-y

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-021-01809-y

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().