非线性规划的对偶问题
线性规划的对偶问题很容易写出，但非线性规划的对偶问题有点不一样。考虑非线性规划问题：minxf(x)s.t.gi(x)≥0,i=1,…,m,hj(x)=0,j=1,…,l,x∈D.\begin{aligned}\min_{\textbf x}\quad& f(\bf x)&\\\text{s.t.}\quad & g_i(\textbf x)\geq 0, & i
线性规划的对偶问题很容易写出，但非线性规划的对偶问题有点不一样。
考虑非线性规划问题：
minxf(x)s.t.gi(x)≥0,i=1,…,m,hj(x)=0,j=1,…,l,x∈D. \begin{aligned} \min_{\textbf x}\quad & f(\bf x)&\\ \text{s.t.}\quad & g_i(\textbf x)\geq 0, & i= 1, \dots, m,\\ & h_j(\textbf x)=0, & j=1,\dots, l,\\ &\textbf{x}\in D.& \end{aligned} xmins.t.f(x)gi(x)≥0,hj(x)=0,x∈D.i=1,…,m,j=1,…,l,
其对偶问题为：
maxw,vinf{f(x)−∑wigi(x)−∑vjhj(x)}s.t.wi≥0,i=1,…,m. \begin{aligned} \max_{\textbf {w,v}}\quad & \inf\left\{f(\textbf x)-\sum w_ig_i(\textbf x)-\sum v_jh_j(\textbf x)\right\}\\ \text{s.t.}\quad & w_i\geq 0, \quad i= 1, \dots, m. \end{aligned} w,vmaxs.t.inf{f(x)−∑wigi(x)−∑vjhj(x)}wi≥0,i=1,…,m.
当原问题为凸规划时，其 KKT 条件的解就是该对偶问题的最优解，也是原问题的最优解，并且原问题与对偶问题的最优值相等。
非线性规划的对偶也广泛应用于机器学习的一些算法中（例如支持向量机）。
常见的线性规划的对偶模型，其实是上面拉格朗日对偶的特殊情况。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
3
0- 0
已为社区贡献12条内容
所有评论(0)