Convex underestimators of polynomials |
| |
Authors: | Jean B Lasserre Tung Phan Thanh |
| |
Institution: | 1. LAAS-CNRS and Institute of Mathematics, University of Toulouse, 7 Avenue du Colonel Roche, 31077, Toulouse Cedex 4, France 2. University of Toulouse, 7 Avenue du Colonel Roche, 31077, Toulouse Cedex 4, France
|
| |
Abstract: | Convex underestimators of a polynomial on a box. Given a non convex polynomial ${f\in \mathbb{R}{\rm x}]}$ and a box ${{\rm B}\subset \mathbb{R}^n}$ , we construct a sequence of convex polynomials ${(f_{dk})\subset \mathbb{R}{\rm x}]}$ , which converges in a strong sense to the “best” (convex and degree-d) polynomial underestimator ${f^{*}_{d}}$ of f. Indeed, ${f^{*}_{d}}$ minimizes the L 1-norm ${\Vert f-g\Vert_1}$ on B, over all convex degree-d polynomial underestimators g of f. On a sample of problems with non convex f, we then compare the lower bounds obtained by minimizing the convex underestimator of f computed as above and computed via the popular α BB method and some of its other refinements. In most of all examples we obtain significantly better results even with the smallest value of k. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|