多项式优化问题(POP)可描述为目标函数和约束条件都用多项式表示的一类优化问题, 是全局优化中的一个基本而重要的研究对象, 已被广泛应用于信号处理和系统控制等领域.近年来, 这类问题吸引了大批学者的关注, 产生了丰富的研究成果^{[1, 2]}. POP的求解是一个颇具挑战性的问题, 传统的数值求解方法有最速下降法、牛顿法、拟牛顿法、共轭梯度法、信赖域法等^[2-8].但POP一般是非凸的, 故用这些方法求出的值不一定是全局最优值, 大多情况下只是局部最优值.

POP的数学形式如下

$ \begin{array}{l} \min \;\;\;\;\;f(x)\\ {\rm{s.t.}}\;\;\;\;\;\;S = \left\{ {x \in {R^n}:{g_i}(x) \ge 0, i = 1, 2, \cdots, m} \right\}. \end{array} $

当约束集合是紧集时, 其退化为紧约束POP.此类问题是NP难的, 不易求解.经典求解采用Lagrange松弛方法, 将其松弛成一个凸优化问题.近年来, Lasserre提出了一种求解POP的全局优化算法^[2], 该方法是基于半定规划(SDP)松弛, 能无限逼近问题的全局最优值.目前该方法已广泛应用于多个领域^[2-6].此方法被相关学者称为Lasserre松弛方法.

本文主要研究紧约束POP, 基于上述松弛思想, 结合多项式平方和(SOS), 利用Lasserre将原紧约束POP转化为SOS形式及其成立条件, 给出其成立条件推导SOS式成立的证明.在进一步转化为求解另一SOS问题的基础上, 给出当其矩阵特征值的最小值大于0时, 上述条件成立的证明.从而找出其目标函数在约束集合的下界, 通过给出的理论估计出下界与最小值相差的距离, 即逼近界.最后, 文章将原有逼近界定理进一步转化, 给出新的逼近界定理.

$ \left[x\right]_d^T = \left[{\begin{array}{*{20}{c}} 1&{{x_1}}&\cdots &{{x_n}}&{x_1^2}&\cdots &{x_1^d}& \cdots &{x_n^d} \end{array}}\right],\\ {\left[{{x^d}} \right]^T}= \left[{\begin{array}{*{20}{c}}{x_1^d}&{x_1^{d-1}{x_2}}& \cdots &{x_n^d} \end{array}} \right]. $

$\mathbb{N}$:非负整数集, 对于$x \in$ $\mathbb{R}^n$, $\alpha \in$ $\mathbb{N}^n$, ${x^\alpha } = x_1^{{\alpha _1}} \cdots x_n^{{\alpha _n}}$; $\mathbb{N}_k^{{n}}$:多指标集$\left\{ {} \right.$$\alpha \in$$\mathbb{N}^n$: $\left. {\left| \alpha \right| \le k} \right\}$.

$ f(x) = \sum\limits_{\alpha \in N_{2d}^n} {{f_\alpha }} {x^\alpha },{\left\| f \right\|_G} = {(\sum\limits_{\alpha \in N_{2d}^n} {\rho {{(\alpha )}^{ - 1}}f_\alpha ^2} )^{1/2}},\\ \rho (\alpha ) = \left| {\left\{ {(\beta ,\nu ) \in } \right.} \right._d^n \times _d^n:\left. {\left. {\beta + \nu = \alpha } \right\}} \right|. $

$\Delta \subset \left\{ {1, \cdots, n} \right\}$, $\left| \Delta \right| = 2d$, 若$\Delta = \left\{ {{i_1}, \cdots, {i_{2d}}} \right\}$, 则${x_\Delta } = ({x_{i1}}, \cdots, {x_{i2d}})$, ${\Omega _{2d}} = \left\{ {\Delta \subset \left[n \right]:} \right.$ $\left. {\left| \Delta \right| = 2d} \right\}$. ${L^2}$范数: ${\left\| f \right\|_{{L^2}(S)}}: = {\left( {\int\limits_S {f{{(x)}^2}d\mu (x)} } \right)^{1/2}}$, 与S有关的常量: ${\kappa _{2d}}(S) = \mathop {\min }\limits_{p \in R{{\left[x \right]}_{2d}}} $ $\left\{ {{{\left\| p \right\|}_{{L^2}(S)}}:{{\left\| p \right\|}_G} = 1} \right\}$.

引理2.1^[3]  对于一个阶数为$2d$的多项式$f$, 存在一个对称矩阵$F$, 有$f(x) = \left[x \right]_d^TF{\left[x \right]_d}$.

引理2.2^[3-5]   $f$是SOS $\Leftrightarrow f(x) = \left[x \right]_d^TF{\left[x \right]_d}$, 其中$F \ge 0$.

考虑如下POP

$ \begin{equation} \begin{array}{l} \min \;\;\;\;\;f(x),\\ {\rm{s.t.}}\;\;\;\;\;\;S = \left\{ {x \in {R^n}:{g_i}(x) \ge 0, i = 1, 2 \cdots m} \right\}, \end{array} \end{equation} $

(3.1)

其中$S$是紧集, $f, {g_1}, \cdots, {g_m}$的阶数不大于$2d$(称$d$为松弛阶数), (3.1)式不易求解，因此Lasserre将其转化成如下$SOS$形式去找(3.1)式中${f_{\min }}$的下界^[2]

$ \begin{equation} \begin{array}{l} {\rm{max}} \;\;\;r,\\ {\rm{s.t.}}\;\;\;\;f - r = {\sigma _0} + {\sigma _1}{g_1} + \cdots + {\sigma _m}{g_m},\\ \;\;\;\;\;\;\;\deg ({\sigma _0}), \deg ({\sigma _1}{g_1}), \cdots, \deg ({\sigma _m}{g_m}) \le 2d,\\ \;\;\;\;\;\;\;\;{\sigma _0}, {\sigma _1}, \cdots, {\sigma _m}\text{是}{\rm{SOS}}, \end{array} \end{equation} $

(3.2)

其中, $\deg $表示多项式的阶数, ${f_{\min }}$(${f_{\max }}$)表示$f$在$S$上的最小值(最大值), ${f_{{\rm{sos}}}}$表示(3.2)式中的最优值.由上述知, 对于固定的$d$, 有${f_{{\rm{sos}}}} \le {f_{\min }}$. 当${g_1}, \cdots ,{g_m}$在适当的条件下, 存在 $Q = Q({g_1}, \cdots ,{g_m})$有

$ \begin{equation} \begin{array}{l} 1 \le \frac{{{f_{\max }} - {f_{{\rm{sos}}}}}}{{{f_{\max }} - {f_{\min }}}} \le Q. \end{array} \end{equation} $

(3.3)

为了保证(3.2)式成立, 需如下引理.

引理3.1^[6]  存在一个对称的正定矩阵$E$及SOS多项式${\sigma _1}, \cdots, {\sigma _m}$, 且$\deg ({\sigma _i}{g_i}) \le 2d, i = 1, \cdots, m$有${\sigma _1}{g_1} + \cdots + {\sigma _m}{g_m} = 1- \left[x \right]_d^TE{\left[x \right]_d}.$

定理3.1  这是定理内容.若$S$内部非空, $R\left[x \right]$是实多项式环, $R{\left[x \right]_k}$表示阶数最多是$k$的多项式的子空间, 那么下列叙述等价

(1) 引理3.1成立;

(2) 对于每个$f \in R{\left[x \right]_{2d}}$, (3.2)式都可求;

(3) 若(3.2)式可求, 有$f = - \left[x \right]_d^T{\left[x \right]_d}$.

证   (1)$ \Rightarrow $(2)由引理2.1, 有$f(x) = \left[x \right]_d^TF{\left[x \right]_d}$, 其中$F$是对称矩阵.由引理3.1知$E$是正定矩阵, 因此存在足够大的$\lambda $, 且$\lambda > 0$, 使

$ {\sigma _0}(x): = f(x) + \lambda \left[x \right]_d^TE{\left[x \right]_d} = \left[x \right]_d^T(F + \lambda E){\left[x \right]_d} $

是SOS.令$r = - \lambda $, 有${\sigma _0}(x): = f(x) - r\left[x \right]_d^TE{\left[x \right]_d}$.而${\sigma _1}{g_1} + \cdots + {\sigma _m}{g_m} = 1 - \left[x \right]_d^TE{\left[x \right]_d}$.故$1 - ({\sigma _1}{g_1} + \cdots + {\sigma _m}{g_m}) = \left[x \right]_d^TE{\left[x \right]_d}$, 从而${\sigma _0}(x): = f(x) - r\left[{1-({\sigma _1}{g_1} + \cdots + {\sigma _m}{g_m})} \right]$.有$ f-r = {\sigma _0} + \lambda {\sigma _1}{g_1} + \cdots + \lambda {\sigma _m}{g_m}.$故(3.2)式可求.

(2)$ \Rightarrow $(3)显然成立.

(3)$ \Rightarrow $(1)令$f(x) = - \left[x \right]_d^T{\left[x \right]_d}$, 因(3.2)式对$f$可求, 故存在$\hat \gamma $及SOS多项式${\hat \sigma _{0, }}{\hat \sigma _1}, \cdots, {\hat \sigma _m}$, 当$\deg ({\hat \sigma _i}{g_i}) \le 2d, i = 1, \cdots, m$有

$ - \left[x \right]_d^T{\left[x \right]_d} -\hat \gamma = {\hat \sigma _0} + {\hat \sigma _1}{g_1} + \cdots + {\hat \sigma _m}{g_m}. $

对于$u \in S$, 有$- \hat r \ge \left[u \right]_d^T{\left[u \right]_d} \ge 1$及

$ \frac{1}{{- \hat \gamma }}({\hat \sigma _1}{g_1} + \cdots + {\hat \sigma _m}{g_m}) = 1- \frac{1}{{- \hat \gamma }}(\left[x \right]_d^T{\left[x \right]_d} + {\hat \sigma _0}). $

因此, 引理3.1成立.故定理3.1成立.

在引理3.1中, 多项式${\sigma _1}, \cdots, {\sigma _m}$和正定矩阵$E$可能并不唯一.当${\lambda _{\min }}(E)$越大, 获得的逼近界越好.其中$X$是对称矩阵, ${\lambda _{\max }}(X)$ (${\lambda _{\min }}(X)$)表示$X$的特征值的最大值(最小值), $X > 0$意味着${\lambda _{\min }}(X) > 0$.因此, 尽可能找到${\lambda _{\min }}(E)$的最大值, 进而解决如下SOS问题

$ \begin{equation} \begin{array}{l} \mathop {\max }\limits_{{\sigma _1}, \cdots, {\sigma _m}, E} \;\;{\lambda _{\min }}(E)\\ \;\;\;{\rm{s.t.}}\;\;\;\;{\sigma _1}{g_1} + \cdots + {\sigma _m}{g_m} = 1 - \left[x \right]_d^TE{\left[x \right]_d}\\ \;\;\;\;\;\;\;\;\;\;\;\;{\sigma _0}, {\sigma _1}, \cdots, {\sigma _m}\text{是}{\rm{SOS}}\\ \;\;\;\;\;\;\;\;\;\;\;\;deg ({\sigma _1}{g_1}), \cdots, \deg ({\sigma _m}{g_m}) \le 2d \end{array} \end{equation} $

(3.4)

定理3.2  假设$\left({\sigma _1^ *, \cdots, \sigma _m^ *, {E^ * }} \right)$是(3.4)式的最优解.当且仅当${\lambda _{\min }}({E^ * }) > 0$, 引理3.1才成立.

证  因为$\left({\sigma _1^*, \cdots, \sigma _m^*, {E^*}} \right)$是(3.4)式的最优解, 且${\lambda _{\min }}({E^ * }) > 0$, 则$E$是正定矩阵.由${\hat \sigma _0}, {\hat \sigma _1}, \cdots, {\hat \sigma _m}$是SOS且$\deg ({\hat \sigma _i}{g_i}) \le 2d, i = 1, \cdots, m$, 有

$ {\hat \sigma _0} + {\hat \sigma _1}{g_1} + \cdots + {\hat \sigma _m}{g_m} = \left[x \right]_d^TE{\left[x \right]_d}. $

令${\hat \sigma _0}(x): = 2\left[x \right]_d^TE{\left[x \right]_d} + \ell $, 其中$0 < - \ell < 2\left[x \right]_d^TE{\left[x \right]_d}$, 则有

$ - \frac{1}{\ell }({\hat \sigma _1}{g_1} + \cdots + {\hat \sigma _m}{g_m}) = 1- (- \frac{1}{\ell })\left[x \right]_d^TE{\left[x \right]_d}. $

故结论得证.

令$d = \max \left\{ {\left\lceil {\frac{{\deg (f)}}{2}} \right\rceil, \left\lceil {\frac{{\deg (g)}}{2}} \right\rceil } \right\}$, 其中对于任意的$t \in R$, $\left\lceil t \right\rceil $表示不小于$t$的最小整数, $\psi $是包含$f$的$\mathbb{R}{\left[x \right]_{2d}}$的子空间, $p$为一多项式, 定义与$\psi$和$S$有关的常量为^[9]

$ \begin{equation} \begin{array}{l} \chi \left( {\psi, S} \right): = \mathop {\max }\limits_{p \in \psi } \left\{ {{{\left\| p \right\|}_G}:\left| {p(x) \le 1} \right|, \forall x \in S} \right\} \end{array} \end{equation} $

(3.5)

引理3.2^[9]  若$S$内部非空, 对于每个$\Delta \in {\Omega _{2d}}$, 且$0$在$S$内部, 则${\kappa _{2d}}(S) > 0$.

引理3.3^[10]  如果$f\in$$\mathbb{R}{\left[x \right]_{2d}}$, 那么存在一个对称矩阵$W$, 使得

$ f(x) = \left[x \right]_d^TW{\left[x \right]_d}, \;\;\;{\left\| W \right\|_F} = {\left\| f \right\|_G}. $

其中对于任意矩阵$A$, ${\left\| A \right\|_2}$是标准的二范数, ${\left\| A \right\|_F} = \sqrt {{\rm{trace}}({A^T}A)}$.注意: ${\left\| A \right\|_2} \le {\left\| A \right\|_F}$.

引理3.4^[11]  假设$\psi$是包含1的$\mathbb{R}{\left[x \right]_{2d}}$的子空间, $\chi \left({\psi, S} \right) < \infty$, $\left({{\sigma _1}, \cdots, {\sigma _m}, E} \right)$满足引理3.1.令$f\in\psi$, ${f_{\min }}({f_{\max }})$是在$S$上的最小值(最大值).如果${f_{sos}}$是(3.2)式的最优值, 则有

$ 1 \le \frac{{{f_{\max }}-{f_{{\rm{sos}}}}}}{{{f_{\max }}-{f_{\min }}}} \le \frac{{\chi \left( {\psi, S} \right)}}{{{\lambda _{\min }}(E)}}. $

若(3.4)式中的最优解$\left({\sigma _1^ *, \cdots, \sigma _{_m}^ *, {E^ * }} \right)$用到上式, 获得的最优界更好.

为了得到引理3.4的精确的逼近界, 需要估计$\chi (\psi, S)$和${\lambda _{\min }}(E)$的值.

定理3.3  假设0在$S$的内部, $({\sigma _1}, \cdots, {\sigma _m}, E)$满足引理3.1, 令$f\in$$\mathbb{R}{\left[x\right]_{2d}}$, 则有

$ 1 \le \frac{{{f_{\max }}-{f_{{\rm{sos}}}}}}{{{f_{\max }}-{f_{\min }}}} \le \frac{1}{{{\kappa _{2d}}(S){\lambda _{\min }}(E)}}. $

证  因为$S$内部非空, 由引理3.2知${\kappa _{2d}}(S)>0$.令$\psi=$$\mathbb{R}{\left[x \right]_{2d}}$, 如果$p \in \psi $, 对所有的$x \in S $都有$\left|{p(x)}\right|\le 1$, 则${\left\|p\right\|_{{L^2}(S)}}\le1$.由${\kappa _{2d}}(S) = \mathop {\min }\limits_{p \in R{{\left[x \right]}_{2d}}} \left\{ {{{\left\| p \right\|}_{{L^2}(S)}}:{{\left\| p \right\|}_G} = 1} \right\}$, 有$1 \ge {\kappa _{2d}}(S){\left\| p \right\|_G}$, $\chi (\psi, S) \le \frac{1}{{{\kappa _{2d}}(S)}}$.由引理3.4得

$1 \le \frac{{{f_{\max }} - {f_{{\rm{sos}}}}}}{{{f_{\max }} - {f_{\min }}}} \le \frac{1}{{{\kappa _{2d}}(S){\lambda _{\min }}(E)}},$

故定理得证.

注  如果(3.4)式中的最优解$\left({\sigma _1^ *, \cdots, \sigma _m^ *, {E^ * }} \right)$用到上式, 获得的最优界更好.(3.4)式中的最优值${\lambda _{\min }}({E^ * })$的选取依赖于$S$.已有文献给出$\sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} \le \frac{1}{{{\lambda _{\min }}({E^ * })}} \le d!\sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} $, 但未给$\sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} $收敛性, 下面给出具体过程并证明$\sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} $收敛.

令$R = \mathop {\max }\limits_{x \in S} {\left\| x \right\|_2}$, 有

$ \left\| x \right\|_{_2}^{2k} = {(x_1^2 + \cdots + x_n^2)^k} = \sum\limits_{\alpha \in N_k^n} {{x^{2\alpha }}\frac{{k!}}{{{\alpha _1}! \cdots {\alpha _n}!}}} \le k!\sum\limits_{\alpha \in N_k^n} {{x^{2\alpha }}} = k!\left\| {\left[{{x^k}} \right]} \right\|_2^2, $

$ \left\| {{{\left[x \right]}_d}} \right\|_{_2}^2 = 1 + \left\| {\left[{{x^1}} \right]} \right\|_2^2 + \left\| {\left[{{x^2}} \right]} \right\|_2^2 + \cdots + \left\| {\left[{{x^d}} \right]} \right\|_2^2 \ge \sum\limits_{k = 0}^d {\frac{{\left\| x \right\|_2^{2k}}}{{k!}}}, $

对于所有的$x \in S$, 有$1 \ge \left[x \right]_d^T{E^ * }{\left[x \right]_d} \ge {\lambda _{\min }}({E^ * })\left\| {{{\left[x \right]}_d}} \right\|_2^2$, 则上式变为

$ \frac{1}{{{\lambda _{\min }}({E^ * })}} \ge \sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} . $

由$\left\| {\left[{{x^k}} \right]} \right\|_{_2}^2 = \sum\limits_{\alpha \in N_k^n} {{x^{2\alpha }}} \le \sum\limits_{\alpha \in N_k^n} {{x^{2\alpha }}\frac{{k!}}{{{\alpha _1}! \cdots {\alpha _n}!}}} = {(x_1^2 + \cdots + x_n^2)^k} = \left\| x \right\|_2^{2k}$知

$ r(x): = 1- {(1 + {R^2} + \cdots + {R^{2d}})^{- 1}}\left[x \right]_d^T{\left[x \right]_d} $

在$S$上非负.若存在SOS多项式${s_0}, {s_1}, \cdots, {s_m}$, 对每个$\deg ({s_i}{g_i}) \le 2d$及

$ \begin{equation} \begin{array}{l} r = {s_0} + {s_1}{g_1} + \cdots + {s_m}{g_m}. \end{array} \end{equation} $

(3.6)

可找到一正定矩阵$\hat E$满足

$ \left[x \right]_d^T\hat E{\left[x \right]_d} = 1 - ({s_1}{g_1} + \cdots + {s_m}{g_m}) = {s_0} + {(1 + {R^2} + \cdots + {R^{2d}})^{ - 1}}\left[x \right]_d^T{\left[x \right]_d}. $

因为${s_0}$是SOS, 有

$ \frac{1}{{{\lambda _{\min }}({E^ * })}} \le \frac{1}{{{\lambda _{\min }}(\hat E)}} \le \sum\limits_{k = 0}^d {{R^{2k}}} \le d!\sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} . $

所以, 如果(3.6)式成立, 则有

$ \sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} \le \frac{1}{{{\lambda _{\min }}({E^ * })}} \le d!\sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} . $

如果(3.6)式不成立, 但已知$R$, 可以增加(3.1)式的约束条件$r(x) \ge 0$.故$\frac{1}{{{\lambda _{\min }}({E^ * })}}$可以通过$\sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} $来估计.下证其收敛性.

令${U_k} = \frac{{{R^{2k}}}}{{k!}}$, 则${U_1} = \frac{{{R^2}}}{{1!}} = {R^2}$有界, 且

$ \frac{{{U_{k + 1}}}}{{{U_k}}} = \frac{{{\textstyle{{{R^{2(k + 1)}}} \over {(k + 1)!}}}}}{{{\textstyle{{{R^{2k}}} \over {k!}}}}} = \frac{{{R^{2(k + 1)}}}}{{(k + 1)!}} \cdot \frac{{k!}}{{{R^{2k}}}} = \frac{{{R^2}}}{{k + 1}}, $

有

$ \mathop {\lim }\limits_{k \to \infty } \frac{{{U_{k + 1}}}}{{{U_k}}} = \mathop {\lim }\limits_{k \to \infty } \frac{{{R^2}}}{{k + 1}} = 0 < 1. $

故$\sum\limits_{k = 0}^d {{U_k}} $收敛, 即$\sum\limits_{k = 0}^d {\frac{{{R^{2k}}}}{{k!}}} $收敛.

紧约束POP是NP难的, 不易求解, 故Lasserre将其转化为SOS形式求目标函数在约束集合的下界.为了使得Lasserre转化的SOS可求, 在已知其成立条件前提下, 进一步给出证明过程, 从而找出所求问题的下界.在已知下界的基础上, 通过理论估计出下界与最小值相差的距离, 即逼近界.将原有的逼近界定理进行转化, 给出另外一个逼近界定理, 从而解决原紧约束POP.