**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Polynomial Optimization: SOS and Nonnegative Polynomials

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

In course

MGT-418: Convex optimization

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

Related concepts (62)

Instructor

Related lectures (2)

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.

Max-Cut Problem: SDP Relaxation and Randomized RoundingMGT-418: Convex optimization

Explores the Max-Cut Problem, its relaxation using SDP, and Polynomial Optimization.

Algebraic Curves: NormalizationMATH-410: Riemann surfaces

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