Lecture

Polynomial Optimization: SOS and Nonnegative Polynomials

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MGT-418: Convex optimization

This course introduces the theory and application of modern convex optimization from an engineering perspective. ...

Description

This lecture by the instructor covers the concept of polynomial optimization, focusing on sum-of-squares (SOS) polynomials and nonnegative polynomials. The lecture explains how to minimize polynomials by checking nonnegativity and introduces the theorem by Hilbert. It also delves into the representation of polynomials as quadratic functions of monomials and provides theorems and proofs related to SOS polynomials.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Daniel Kuhn

Official source

Related concepts (32)

Monomial

In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: A monomial, also called power product, is a product of powers of variables with nonnegative integer exponents, or, in other words, a product of variables, possibly with repetitions. For example, is a monomial. The constant is a monomial, being equal to the empty product and to for any variable . If only a single variable is considered, this means that a monomial is either or a power of , with a positive integer.

Residual sum of squares

In statistics, the residual sum of squares (RSS), also known as the sum of squared residuals (SSR) or the sum of squared estimate of errors (SSE), is the sum of the squares of residuals (deviations predicted from actual empirical values of data). It is a measure of the discrepancy between the data and an estimation model, such as a linear regression. A small RSS indicates a tight fit of the model to the data. It is used as an optimality criterion in parameter selection and model selection.

Lack-of-fit sum of squares

In statistics, a sum of squares due to lack of fit, or more tersely a lack-of-fit sum of squares, is one of the components of a partition of the sum of squares of residuals in an analysis of variance, used in the numerator in an F-test of the null hypothesis that says that a proposed model fits well. The other component is the pure-error sum of squares. The pure-error sum of squares is the sum of squared deviations of each value of the dependent variable from the average value over all observations sharing its independent variable value(s).

Monomial order

In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all (monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i.e., If and is any other monomial, then . Monomial orderings are most commonly used with Gröbner bases and multivariate division. In particular, the property of being a Gröbner basis is always relative to a specific monomial order.

Partition of sums of squares

The partition of sums of squares is a concept that permeates much of inferential statistics and descriptive statistics. More properly, it is the partitioning of sums of squared deviations or errors. Mathematically, the sum of squared deviations is an unscaled, or unadjusted measure of dispersion (also called variability). When scaled for the number of degrees of freedom, it estimates the variance, or spread of the observations about their mean value.

Related lectures (64)

Quadratic Forms and Symmetric Bilinear Forms

Explores quadratic forms, symmetric bilinear forms, and their properties.

Decomposition: Simple and Quadratic Factors MOOC: Analysis I (part 7) : Indefinite and definite integrals, integration (selected chapters)MOOC: Analysis I

Explores the decomposition of a function into simple and quadratic factors.

ANOVA: Partitioning Total SS

Covers ANOVA method, focusing on partitioning total sum of squares into treatment and error components, mean square calculations, Fisher statistic, and F-distribution.

Algebraic Curves: Normalization

Covers the normalization process of plane algebraic curves, focusing on irreducible polynomials and affine curves.

Multilinear Regression: Design Optimization