Lecture

Polynomial Optimization: Theory and Applications

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 covers topics in polynomial optimization, focusing on the theory and applications of sum-of-squares polynomials. It discusses the challenges of checking nonnegativity in polynomials and presents the Hilbert theorem on SOS polynomials. The instructor explains the concept of monomials and demonstrates how any polynomial can be represented as a quadratic function of monomials. The session concludes with the theorem stating the conditions for a polynomial to be SOS. Practical examples and proofs are provided throughout the lecture.

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.

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.

Hilbert's basis theorem

In mathematics, specifically commutative algebra, Hilbert's basis theorem says that a polynomial ring over a Noetherian ring is Noetherian. If is a ring, let denote the ring of polynomials in the indeterminate over . Hilbert proved that if is "not too large", in the sense that if is Noetherian, the same must be true for . Formally, Hilbert's Basis Theorem. If is a Noetherian ring, then is a Noetherian ring. Corollary. If is a Noetherian ring, then is a Noetherian ring.

Hilbert's syzygy theorem

In mathematics, Hilbert's syzygy theorem is one of the three fundamental theorems about polynomial rings over fields, first proved by David Hilbert in 1890, which were introduced for solving important open questions in invariant theory, and are at the basis of modern algebraic geometry. The two other theorems are Hilbert's basis theorem that asserts that all ideals of polynomial rings over a field are finitely generated, and Hilbert's Nullstellensatz, which establishes a bijective correspondence between affine algebraic varieties and prime ideals of polynomial rings.

Quadratic function

In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before the 20th century, the distinction was unclear between a polynomial and its associated polynomial function; so "quadratic polynomial" and "quadratic function" were almost synonymous. This is still the case in many elementary courses, where both terms are often abbreviated as "quadratic".

Related lectures (64)

Algebraic Geometry: Forms and Maps

Covers the concept of forms in algebraic geometry and the implications of constructing Bloch(A) from glued copies of A.

Stein Algorithm: Polynomial Identity Testing

Explores the Stein algorithm for polynomial identity testing and the minimization of a cut problem.

Polynomial Identity Testing

Covers polynomial identity testing using oracles and random point evaluation, with applications in graph theory and algorithmic aspects.

Error Analysis and Interpolation

Explores error analysis and limitations in interpolation on evenly distributed nodes.

Tori: Character Forms and Monomials