Semi-infinite programming using high-degree polynomial interpolants and semidefinite programming
From MaRDI portal
Publication:5355202
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.
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
Cites work
- scientific article; zbMATH DE number 3528170 (Why is no real title available?)
- scientific article; zbMATH DE number 1070896 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 800961 (Why is no real title available?)
- scientific article; zbMATH DE number 3246461 (Why is no real title available?)
- scientific article; zbMATH DE number 3191390 (Why is no real title available?)
- scientific article; zbMATH DE number 3110365 (Why is no real title available?)
- 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
- A homotopy interior point method for semi-infinite programming problems
- A new exchange method for convex semi-infinite programming
- Accuracy and Stability of Numerical Algorithms
- An accelerated central cutting plane algorithm for linear semi-infinite programming
- Approximation theory and approximation practice
- Barycentric Lagrange Interpolation
- CSDP, A C library for semidefinite programming
- Discretization in semi-infinite programming: the rate of convergence
- Estimating arrival rate of nonhomogeneous Poisson processes with semidefinite programming
- How bad are Hankel matrices?
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Numerical Methods for Special Functions
- On polynomials of best one sided approximation
- On the Runge Example
- Optimal designs for rational function regression
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Semi-infinite programming
- Semi-infinite programming. Workshop, Cottbus, Germany, September 1996
- Semidefinite Programming
- Semidefinite programming relaxations for semialgebraic problems
- The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
- The numerical stability of barycentric Lagrange interpolation
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(4)
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)
