本文源於知乎問題“

目前最佳化界中，能對最高多少次的目標函式進行最佳化

？”的回答。問題裡的“次數”指的是多項式的次數。事實上，這個問題的本質是大衛·希爾伯特當年著名的23個問題的第17個的特殊版：

給定一個多維多項式，在實數域上非負，是否可以寫成有限個多項式的平方和？

當然上面的問題乍看下好像跟最佳化沒關係，我馬上會解釋。回開頭的問題，

次數

確實很關鍵，不過

維數

也同樣關鍵。

一、一維多項式最佳化：凸最佳化（半正定規劃）問題

先說結論。

如果目標函式是一維的，那麼多少次的最佳化問題，都沒什麼問題（多項式時間可解）。

考慮我們的目標函式為

n

次一維實多項式：

p(x)=p_nx^n+p_{n-1}x^{n-1}+\ldots+p_1x+p_0,

其中所有係數

p_k

都是實數，因為

x

的取值是實數所以我們也可以寫作

p(x)\in \mathbb{R}[x]

。那麼我們要

證明一個這樣的結論：

\forall~x\in\mathbb{R}:p(x)\geq 0

和

p(x)

是SOS（sum of squares）等價

。這個

p(x)

是SOS呢就是說多項式可以寫成有限個多項式的平方和。具體來說，存在

q_1,\ldots,q_m\in \mathbb{R}[x]

，使得

p(x)=\sum_{k=1}^m q_k^2(x)

好了我們現在就是要證明

p(x)

是SOS和

p(x)

非負等價。一邊是顯然的，如果

p(x)

是SOS的話根據定義顯然是非負的。那麼反過來，我們就要證明

\forall~x\in\mathbb{R}:p(x)\geq 0\Rightarrow p(x)

是SOS的。

根據代數學基本定理，我們可以將

p(x)

分解為：

p(x)=p_n\Pi_j(x-r_j)^{n_j}\Pi_k(x-a_k+ib_k)^{m_k}(x-a_k-ib_k)^{m_k}

，

其中

r_j

和

a_k\pm ib_k

就是

p(x)=0

對應的實根和復根（

n_j,m_k

是根的重複度，加起來自然是

n

）。由於

p(x)

非負，所以

p_n>0

且實根的重複度（multiplicities）都是偶數，因此我們記

n_j=2s_j

。再由

(x-a+ib)(x-a-ib)=(x-a)^2+b^2

，得到

p(x)=p_n\Pi_j(x-r_j)^{2s_j}\Pi_k((x-a_k)^2+b_k^2)^{m_k}

因為顯然SOS的乘積也是SOS，我們就得到了

p(x)

是SOS的。更進一步，我們可以利用

(\alpha^2+\beta^2)(\gamma^2+\delta^2)=(\alpha\gamma-\beta\delta)^2+(\alpha\delta+\beta\gamma)^2

，把關於復根的所有乘積展開成只包含兩項的SOS。即，存在一種分解

p(x)=q_1^2(x)+q_2^2(x)

。

接下來我們就要說明可以用半正定規劃（semidefinite programming， SDP）來判斷

\forall~x\in\mathbb{R}:p(x)\geq 0

是否成立。注意

p(x)

是偶數次多項式才有意義（記次數

n=2d

），不然顯然是不可能的。那麼考慮

p(x)=\sum_{k=1}^m q_k^2(x)

，這時候所有

q_k

的次數顯然不能超過

d

。我們則可以有表示式：（對某個矩陣

V\in \mathbb{R}^{m\times (d+1)}

）

\left[\begin{array}{c} q_1(x)\\ q_2(x)\\ \vdots\\ q_m(x) \end{array} \right] = V\underbrace{ \left[\begin{array}{c} 1\\ x\\ \vdots\\ x^d \end{array} \right] }_{:=[x]_d}

記

Q=V^\top V

，我們就有：

p(x)=\sum_{k=1}^mq_k^2(x)=(V[x]_d)^\top (V[x]_d)=[x]_d^\top V^\top V[x]_d=[x]_d^\top Q [x]_d

注意按照定義矩陣

Q

是半正定（positive semidefinite）的。反過來，如果我們假設存在一個半正定矩陣

Q

，使得

p(x)=[x]_d^\top Q [x]_d

，那麼利用半正定矩陣的對稱分解，就有存在矩陣

V

使得

Q=V^\top V

，這樣就說明

p(x)

是SOS的。

那麼實際上我就證明了這個結論

：

p(x)

非負（SOS）當且僅當存在

Q\in \mathcal{S}_+^{d+1}

（d+1維半正定矩陣）使得

p(x)=[x]_d^\top Q [x]_d

！

把

Q

的行列用

\{0,\ldots,d\}

來標記，我們有

[x]_d^\top Q [x]_d = \sum_{j=0}^d\sum_{k=0}^dQ_{jk}x^{j+k}=\sum_{i=0}^{2d}\left( \sum_{j+k=i}Q_{jk} \right)x^i

這樣子，帶回到

p(x)

的定義，我們就知道多項式係數和矩陣的關係：

p_i=\sum_{j+k=i}Q_{jk}, ~ i=0,\ldots,2d

這就給了我們半正定規劃的具體計算公式了（也就是說，我們要找到一個半正定矩陣

Q\in \mathcal{S}_+^{d+1}

，其係數滿足上面的關係式）！

具體來說，對任意實數

\gamma

，判斷

\forall~x\in \mathbb{R}:p(x)\geq \gamma \Leftrightarrow \forall~x\in \mathbb{R}: p(x)-\gamma\geq 0

也就是求解一個SDP問題。那麼比如說如果我們知道

p(x)

的最小值有界，最佳化

p(x)

就可以用個二分查詢，每次查詢判斷就是解一個SDP，這顯然是多項式時間的（近似）演算法。

上面講的都是

p(x)

在整個實數域上的無約束最佳化。如果我們要限定

p(x)

在某段閉區間（或者半開半閉區間）上求最小值，也是沒問題的，還是可以變成SDP最佳化問題。這裡我就不具體寫式子了，有興趣的可以看文章

［1］

的proposition 3。1。

二、高維多項式最佳化與希爾伯特第十七問題

事實上，希爾伯特在100多年前就證明了，除了我們前面討論的一維情況，更一般的來講只要一個

n

個變數（維數），次數

2d

在實數域上的齊次多項式

p

是SOS等價其非負——那麼一定滿足下面三種情況之一。不過，希爾伯特的證明完全基於代數學，是存在性證明而對計算沒有幫助。

n=2

2d=2

n=3,~2d=4

對於其他情況，希爾伯特猜想不成立。Motzkin在幾十年後給出過一個絕妙的反例，如下非齊次多項式（

n=2,2d=6

）是實數域上非負但不是SOS的：

M(x,y)=x^4y^2+x^2y^4+1-3x^2y^2

我們這裡不討論這個絕妙反例的證明（牽涉到一點抽象代數定義）。不過可以給張圖說明其確實非負：

希爾伯特第十七問題與多項式最佳化

事實上，我們指出判斷一個多元四次（及以上）偶多項式是否在實數域非負的是NP-hard的

［2］

。也就是說，除非NP=P，不存在通用的多項式演算法可以最佳化一個多元四次（及以上）偶多項式。

最後，我們指出希爾伯特證明可解的三種情況，是仍然可以用前一節的方法透過SDP來求解的。因為事實上我們前面一節的方法對判斷任意

n

個變數次數

2d

的多項式是SOS的SDP是可以直接推廣的。具體來說，透過同樣的步驟我們可以得到一個

Q\in \mathcal{S}_{+}^{\binom{n+d}{d}}

的SDP條件：

Q\succeq 0,~ p_\alpha=\sum_{\beta+\gamma=\alpha} Q_{\beta\gamma}

注意，這些希爾伯特欽定的多項式本身都可以高度非凸，但是我們還是可以很有效的最佳化他們（除此之外其它的多項式一般來講就不行了）。

對SDP不熟悉的同學，也可以看看我之前的一個回答：

參考

^

Bertsimas， Dimitris， and Ioana Popescu。 “Optimal inequalities in probability theory： A convex optimization approach。” SIAM Journal on Optimization 15。3 （2005）： 780-804。

^

Nesterov， Yurii。 “Squared functional systems and optimization problems。” High performance optimization。 Springer， Boston， MA， 2000。 405-440。