Optimization of Univariate Functions on Bounded Intervals by Interpolation and Semidefinite Programming
- 11 April 2006
- preprint
- Published by Elsevier BV in SSRN Electronic Journal
Abstract
We consider the problem of minimizing a univariate function f on an interval [a, b]. When f is a polynomial, we review how this problem may be reformulated as a semidefinite programming (SDP) problem, and review how to extract all global minimizers from the solution of the SDP problem. For general f, we approximate the global minimum by minimizing the Lagrange or Hermite interpolant of f on the Chebyshev nodes using the SDP approach. We provide numerical results for a set of test functions.Keywords
This publication has 18 references indexed in Scilit:
- Detecting Global Optimality and Extracting Solutions in GloptiPolyLecture Notes in Control and Information Sciences, 2005
- Semidefinite Approximations for Global Unconstrained Polynomial OptimizationSIAM Journal on Optimization, 2005
- From coefficients to samples: a new approach to SOS optimizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Barycentric Lagrange InterpolationSiam Review, 2004
- The condition number of real Vandermonde, Krylov and positive definite Hankel matricesNumerische Mathematik, 2000
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial OptimizationSIAM Journal on Optimization, 2000
- Global Optimization by Multilevel Coordinate SearchJournal of Global Optimization, 1999
- Remark on Algorithms to Find Roots of PolynomialsSIAM Journal on Scientific Computing, 1994
- Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparisonMathematical Programming, 1992
- Global optimization using interval analysis: The one-dimensional caseJournal of Optimization Theory and Applications, 1979