论文标题
通过弗里茨约翰条件增强的确切多项式优化
Exact polynomial optimization strengthened with Fritz John conditions
论文作者
论文摘要
令$ f，g_1，\ dots，g_m $为多项式，在变量向量中具有实际系数$ x =（x_1，\ dots，x_n）$。用$ \ text {diag}（g）用系数$ g =（g_1，\ dots，g_m）$，用$ \ nabla g $表示$ g $的jacobian。令$ c $是\ begin {equation}定义的关键点集 c = \ {x \ in \ mathbb r^n \，：\，\ text {rank}（φ（x））<m \} \ quad \ text {with} \quadφ：= \quadφ：= \ begin {bmatrix} \ end {equation}假设$ f $下的$ c $的图像为$ f（c）$表示为空或有限。 (Our assumption holds generically since $C$ is empty in a Zariski open set in the space of the coefficients of $g_1,\dots,g_m$ with given degrees.) We provide a sequence of values, returned by semidefinite programs, finitely converges to the minimal value attained by $f$ over the basic semi-algebraic set $S$ defined by \begin{equation} s：= \ {x \ in \ mathbb r^n \，：\，g_j（x）\ ge 0 \ ,, \，j = 1，\ dots，m \} \，。因此，\ end {equation}，我们可以准确地计算以下一组中的$ x $中的任何多项式的最小值：单位球，单位hyperpulcube和单位单纯性。在一个稍微更一般的假设下，我们将此结果扩展到在具有非空内部的基本凸半代数集上的任何多项式的最小化，并由凹凹多项式的不平等定义。
Let $f,g_1,\dots,g_m$ be polynomials with real coefficients in a vector of variables $x=(x_1,\dots,x_n)$. Denote by $\text{diag}(g)$ the diagonal matrix with coefficients $g=(g_1,\dots,g_m)$ and denote by $\nabla g$ the Jacobian of $g$. Let $C$ be the set of critical points defined by \begin{equation} C=\{x\in\mathbb R^n\,:\,\text{rank}(φ(x))< m\}\quad\text{with}\quadφ:=\begin{bmatrix} \nabla g\\ \text{diag}(g) \end{bmatrix}\,. \end{equation} Assume that the image of $C$ under $f$, denoted by $f(C)$, is empty or finite. (Our assumption holds generically since $C$ is empty in a Zariski open set in the space of the coefficients of $g_1,\dots,g_m$ with given degrees.) We provide a sequence of values, returned by semidefinite programs, finitely converges to the minimal value attained by $f$ over the basic semi-algebraic set $S$ defined by \begin{equation} S:=\{x\in\mathbb R^n\,:\,g_j(x)\ge 0\,,\,j=1,\dots,m\}\,. \end{equation} Consequently, we can compute exactly the minimal value of any polynomial with real coefficients in $x$ over one of the following sets: the unit ball, the unit hypercube and the unit simplex. Under a slightly more general assumption, we extend this result to the minimization of any polynomial over a basic convex semi-algebraic set that has non-empty interior and is defined by the inequalities of concave polynomials.
