Semi-infinite programming using high-degree polynomial interpolants and semidefinite programming
From MaRDI portal
Publication:5355202
DOI10.1137/15M1053578zbMATH Open1370.90279arXiv1512.06796OpenAlexW2964111768WikidataQ57428041 ScholiaQ57428041MaRDI QIDQ5355202FDOQ5355202
Authors: Dávid Papp 
Publication date: 7 September 2017
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: In a common formulation of semi-infinite programs, the infinite constraint set is a requirement that a function parametrized by the decision variables is nonnegative over an interval. If this function is sufficiently closely approximable by a polynomial or a rational function, then the semi-infinite program can be reformulated as an equivalent semidefinite program. Solving this semidefinite program is challenging if the polynomials involved are of high degree, due to numerical difficulties and bad scaling arising both from the polynomial approximations and from the fact that the semidefinite programming constraints coming from the sum-of-squares representation of nonnegative polynomials are badly scaled. We combine rational function approximation techniques and polynomial programming to overcome these numerical difficulties, using sum-of-squares interpolants. Specifically, it is shown that the conditioning of the reformulations using sum-of-squares interpolants does not deteriorate with increasing degrees, and problems involving sum-of-squares interpolants of hundreds of degrees can be handled without difficulty. The proposed reformulations are sufficiently well scaled that they can be solved easily with every commonly used semidefinite programming solver, such as SeDuMi, SDPT3, and CSDP. Motivating applications include convex optimization problems with semi-infinite constraints and semidefinite conic inequalities, such as those arising in the optimal design of experiments. Numerical results align with the theoretical predictions; in the problems considered, available memory was the only factor limiting the degrees of polynomials, to approximately 1000.
Full work available at URL: https://arxiv.org/abs/1512.06796
Recommendations
- Univariate polynomial optimization with sum-of-squares interpolants
- Semidefinite relaxations for semi-infinite polynomial programming
- On solving a class of linear semi-infinite programming by SDP method
- Semidefinite programming relaxations for linear semi-infinite polynomial programming
- Interval methods for semi-infinite programs
interpolationdesign of experimentspolynomial optimizationsemidefinite optimizationsemi-infinite programmingsum-of-squares
Optimal statistical designs (62K05) Semidefinite programming (90C22) Numerical interpolation (65D05) Semi-infinite programming (90C34)
Cites Work
- CSDP, A C library for semidefinite programming
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Title not available (Why is that?)
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Semidefinite Programming
- Title not available (Why is that?)
- Barycentric Lagrange Interpolation
- Approximation theory and approximation practice
- Semi-infinite programming. Workshop, Cottbus, Germany, September 1996
- Semidefinite programming relaxations for semialgebraic problems
- Title not available (Why is that?)
- Accuracy and Stability of Numerical Algorithms
- Optimal designs for rational function regression
- Numerical Methods for Special Functions
- Semi-infinite programming
- The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
- Title not available (Why is that?)
- The numerical stability of barycentric Lagrange interpolation
- Title not available (Why is that?)
- A new exchange method for convex semi-infinite programming
- A Central Cutting Plane Algorithm for Convex Semi-Infinite Programming Problems
- A Cutting Surface Algorithm for Semi-Infinite Convex Programming with an Application to Moment Robust Optimization
- Discretization in semi-infinite programming: the rate of convergence
- On the Runge Example
- How bad are Hankel matrices?
- Title not available (Why is that?)
- An accelerated central cutting plane algorithm for linear semi-infinite programming
- Estimating arrival rate of nonhomogeneous Poisson processes with semidefinite programming
- Title not available (Why is that?)
- On polynomials of best one sided approximation
- A homotopy interior point method for semi-infinite programming problems
Cited In (4)
Uses Software
This page was built for publication: Semi-infinite programming using high-degree polynomial interpolants and semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5355202)
