DANG TUAN HIEP

Describing convex semialgebraic sets by linear matrix inequalities

Posted on October 24, 2009 by Đặng Tuấn Hiệp

Filed under: Control theory, Convex Algebraic Geometry, Convex Optimization, Real Algebraic Geometry, Studying | Tagged: Prof. Schweighofer | Leave a Comment »

Semialgebraic techniques in nonsmooth optimization

Posted on October 24, 2009 by Đặng Tuấn Hiệp

Lewis

Filed under: Optimization, Real Algebraic Geometry, Studying | Leave a Comment »

Hyperbolic programs

Posted on October 24, 2009 by Đặng Tuấn Hiệp

Renegar

Filed under: Control theory, Convex Algebraic Geometry, Convex Optimization, Optimization, Studying | Tagged: Prof. Schweighofer | Leave a Comment »

Homogeneous polynomials

Posted on October 23, 2009 by Đặng Tuấn Hiệp

A polynomial $P(x_1,\ldots,x_n)$ of degree $k$ is called homogeneous if $P(cx_1,\ldots,cx_n)=c^kP(x_1,\ldots,x_n)$ for all constants $c$ .

An equivalent definition is that all terms of the polynomial have the same degree (i.e. $k$ ).

Observe that a polynomial $P$ is homogeneous if and only if $deg P=ord P$ .

As an important example of homogeneous polynomials one can mention the symmetric polynomial.

Example. $P(x_1,x_2)=x^2_1+x_1x_2+x^2_2$ is a homogeneous polynomial of degree $2$ .

Proposition 1. If $P(x_1,\ldots,x_n)$ is a homogeneous polynomial of degree $k$ , then

$\displaystyle\sum_{i=1}^nx_i\frac{\partial P}{\partial x_i}=kP$ .

Proposition 2. Any factor of a homogeneous polynomial is homogeneous.

Filed under: Studying | Leave a Comment »

Hyperbolic polynomials and their cones

Posted on October 23, 2009 by Đặng Tuấn Hiệp

We will consider a homogeneous multivariate polynomial $p\in\mathbb R[x_1,\ldots,x_n]$ of degree $d$ . Here homogeneous of degree $d$ means that the sum of degrees of each monomial is constant and equal to $d$ , i.e.,

$p(x)=\displaystyle\sum_{|\alpha|=d}c_{\alpha}x^{\alpha}$ ,

where $\alpha=(\alpha_1,\ldots,\alpha_n), \alpha_i\in\mathbb N$ and $|\alpha|=\alpha_1+\cdots+\alpha_n$ . A homogeneous polynomial satisfies $p(tx)=t^dp(x)$ for all real $t$ and vectors $x\in\mathbb R^n$ . We denote the set of such polynomials by $\mathcal H_n(d)$ . By identifying a polynomial with its vector of coefficients, we can consider $\mathcal H_n(d)$ as a normed vector space of dimension $\left(\begin{array}{c}n+d-1\\ d\end{array}\right)$ .

Definition. Let $e$ be a fixed vector in $\mathbb R^n$ . A polynomial $p\in\mathcal H_n(d)$ is hyperbolic with respect to $e$ if $p(e)>0$ and, for all vectors $x\in\mathbb R^n$ , the univariate polynomial $q(t)=p(x-te)$ has only real roots.

A natural geometric interpretation is the following: consider the hypersurface in $\mathbb R^n$ given by $p(x)=0$ . Then, hyperbolicity is equivalent to the condition that every line in $\mathbb R^n$ parallel to $e$ intersects this hypersurface at exactly $d$ points (counting multiplicities), where $d=\deg p$ .

The hyperbolic polynomials were originally studied in the context of partial differential equations. As we will see, they have many surprising properties, and are intimately linked with convex optimization problems that have an algebraic structure.

If $p$ is hyperbolic in direction $e$ , let $\Lambda_{++}(p,e)$ be the connected component of $e$ in the set $\{x\in\mathbb R^n\mid p(x)>0\}$ . The hyperbolicity cone of $p$ in direction $e$ , denoted $\Lambda_+(p,e)$ , is the closure of $\Lambda_{++}(p,e)$ . If $K$ is the hyperbolicity cone of some hyperbolic polynomial in some direction we say that $K$ is a hyperbolic cone.

Lemma. Given $p$ is a hyperbolic polynomial in direction $e$ , then

$\Lambda_{++}(p,e):=\{x\in\mathbb R^n\mid p(x-te)=0\Rightarrow t>0\}$ .

Example 1. The polynomial $x_1x_2\ldots x_n$ is hyperbolic with respect to the vector $(1,1,\ldots,1)$ , since the univariate polynomial $p(x-te)=(x_1-t)(x_2-t)\ldots (x_n-t)$ has only real roots $x_1,x_2,\ldots,x_n$ . The corresponding hyperbolicity cone is

$\Lambda_+=\{x\in\mathbb R^n\mid x_i\ge 0\}$ .

Hyperbolic polynomials are of interest in convex optimization, because they unify in a quite appealing way many facts about the most important tractable classes: linear, second order, and semidefinite programming.

Example 2. Let $\displaystyle p(x)=x^2_{n+1}-\sum_{k=1}^nx^2_k$ . This is a homogeneous quadratic polynomial, hyperbolic in the direction $e=(0,\ldots,0,1)$ , since

$\displaystyle p(x-te)=(x_{n+1}-t)^2-\sum_{k=1}^nx^2_k=t^2-2tx_{n+1}+(x^2_{n+1}-\sum_{k=1}^nx^2_k)$

and the discriminant of this quadratic equation is equal to

$\displaystyle 4x^2_{n+1}-4(x^2_{n+1}-\sum_{k=1}^nx^2_k)=4\sum_{k=1}^nx^2_k$

which is always nonnegative, so the polynomial $p(x-te)$ has only real roots. The corresponding hyperbolicity cone is

$\displaystyle\Lambda_+=\{x\in\mathbb R^n\mid x_{n+1}\ge 0, x^2_{n+1}\ge\sum_{i=1}^nx^2_k\}$ .

Example 3. Consider the homogeneous polynomial

$p(x)=\det(x_1A_1+\cdots+ x_nA_n)$ ,

where $A_i\in\mathcal S^d$ are given symmetric matrices, with $A_1$ is positive definite. The polynomial $p(x)$ is homogeneous of degree $d$ . Letting $e=(1,0,\ldots,0)$ , we have

$p(x-te)=\displaystyle\det\left(\sum_{k=1}^nx_kA_k-tA_1\right)$

$=\det A_1.\det\left(\sum_{k=1}^nx_kA_1^{-1/2}A_kA_1^{-1/2}-tI\right)$ ,

and as a consequence the roots of $p(x-te)$ are always real since they are the eigenvalues of a symmetric matrix. Thus, $p(x)$ is hyperbolic with respect to $e$ . The corresponding hyperbolicity cone is

$\Lambda_+=\{x\in\mathbb R^n\mid x_1A_1+\cdots+x_nA_n\succeq 0\}$ .

Filed under: Algebraic geometry, Convex Algebraic Geometry, Real Algebraic Geometry, Studying | Tagged: Prof. Schweighofer | Leave a Comment »

Hyperbolicity and the Lax conjecture

Posted on October 22, 2009 by Đặng Tuấn Hiệp

We have seen that every polynomial of the form

$p(x)=\det(x_1A_1+\cdots+x_nA_n)$ , (1)

where $A_i\in\mathcal S^d$ and $A_1\succ 0$ , is hyperbolic with respect to the $(1,0,\ldots,0)$ direction.

A 1958 conjecture by Peter Lax, asks whether the converse is true in the case $n=3$ . In other words, is it true that for every hyperbolic polynomial $p(x)$ in three variables of degree $d$ , there exist three symmetric matrices $\{A_1,A_2,A_3\}\subset\mathcal S^d$ for which (1) holds?

This conjecture was proved by A. S. Lewis, P. A. Parrilo, and M. V. Ramana in 2005.

http://arxiv.org/abs/math.OC/0304104

Filed under: Convex Algebraic Geometry, Matrix Theory, Studying | Leave a Comment »

Spectrahedra

Posted on October 20, 2009 by Đặng Tuấn Hiệp

Let $\mathbb R[x]$ denote the polynomial ring in $n$ variables $x=(x_1,\ldots,x_n)$ with coefficients in $\mathbb R$ . A subset $S$ of $\mathbb R^n$ is called basic closed if there exist polynomials $p_1,\ldots,p_m\in\mathbb R[x]$ such that

$S=\{x\in\mathbb R^n\mid p_1(x)\ge 0,\ldots,p_m(x)\ge 0\}$ .

A linear matrix (of dimension $k$ in the variables $x$ ) is a linear polynomial whose coefficients are real symmetric $k\times k$ – matrices, i.e. an expression $A(x) = A_0 + x_1A_1 + \cdots + x_nA_n$ with $A_0,\ldots,A_n\in Sym_k(\mathbb R)$ . A subset $S$ of $\mathbb R^n$ is called a spectrahedron, if it is defined by a linear matrix inequality, i.e. if there exists a linear matrix polynomial $A(x)$ such that

$S = \{x\in\mathbb R^n\mid A(x) = A_0 + x_1A_1 + \cdots + x_nA_n \succeq 0\},$

where $\succeq 0$ denotes positive semidefiniteness. It is obvious that spectrahedra are closed and convex. They are also basic closed: A real symmetric matrix is positive semidefinite if and only if the coefficients of its characteristic polynomial have alternating signs; write

$\det(A(x)-sI_k) = c_0(x) + c_1(x)s + \cdots + c_{k-1}(x)s^{k-1} + (-1)^ks^k,$

with $c_i \in\mathbb R[x]$ , then

$S = \{x\in\mathbb R^n\mid (-1)^{i+k}c_i(x)\ge 0,\forall i=0,1,\ldots,k-1\}.$

Filed under: Convex Algebraic Geometry, Real Algebraic Geometry, Studying | Tagged: Prof. Schweighofer | Leave a Comment »

Real zero polynomials and rigidly convex sets

Posted on October 15, 2009 by Đặng Tuấn Hiệp

Definition. A polynomial $p\in\mathbb R[x]$ is a real zero polynomial with respect to $e\in\mathbb R^n$ (RZ-e polynomial) if $p(e)>0$ and for every $x\in\mathbb R^n$ all zeros of the univariate polynomial $p(e+tx)\in\mathbb R[t]$ are real.

Definition. A set $S$ is called rigidly convex if there exists $e\in S$ and an RZ-e polynomial $p$ such that $S$ is the closure of the connected component of $\{x\in\mathbb R^n\mid p(x)>0\}$ containing $e$ .