非线性等式和不等式约束 PSO：此代码有助于通过使用粒子群优化找出非线性等式和不等式约束的最小值-matlab...
2021-05-29 02:48:39
此代码有助于通过使用粒子群优化找出非线性等式和不等式约束的最小值
收起
matlab

等式约束优化与不等式约束优化

千次阅读 2019-01-12 22:18:30

在学习SVM的原理时，接触到了等式约束优化与不等式约束优化，下面是根据相关资料自己总结出来的自己的，希望对大家有所帮助，这是第一篇博客。 1.等式约束优化 1.1.问题描述当目标函数加上等式约束条件之后，...

在学习SVM的原理时，接触到了等式约束优化与不等式约束优化，下面是根据相关资料自己总结出来的自己的，希望对大家有所帮助，这是第一篇博客。

1.等式约束优化

1.1.问题描述

当目标函数加上等式约束条件之后，原本的非约束优化变成了等式约束优化，如下：

$\min_{x} f(x)$ .....................................................................................(1)

$s.t. \ \ \ h(x)=0$ ............................................................................(2)

因为存在约束条件，所以将 $f(x)$ 的解限定在了一个可行域的区域，此时可能找不到可以使得 $\nabla_xf(x)$ 为0的点，但是我们的目的是找到可行域范围内 $f(x)$ 的最小值即可。

1.2.解法

利用拉格朗日乘子法，引入拉格朗日算子 $\alpha \in R^m$ ,构建拉格朗日函数如下：

$L(x,\alpha)=f(x)+\alpha*h(x)$ ..........................................................(3)

然后对拉格朗日函数 $L(x,\alpha)$ 求 $x$ 的偏导，令偏导为0，即：

$\nabla_xL(x,\alpha)=0$ ..............................................................................(4)

对（2）（4）式进行求解即得到此类问题的最优解。

1.3.解释

假设我们的目标函数为二维的，即 $f(x,y)$ ，在平面中画出 $f(x,y)$ 的等高线，如下图的虚线所示

显而易见，只有当等高线与目标函数的曲线相切时才有可能得到可行解。因此拉格朗日取得极值的必要条件是目标函数与约束函数相切，这时两者的法向量是平行的，即

$\nabla_xf(x)-\alpha\nabla_xh(x)=0$ ................................................................(5)

所以正好可以得到（3）式，需要注意的是， $\alpha$ 仅仅要求不等于0即可，正负号不需要确定。

2.不等式约束优化

2.1.问题描述

不等式约束优化问题为：

$\min_{x} f(x)$ ...........................................................................................(6)

$s.t. \ \ \ g(x)\leq0$ ..................................................................................(7)

2.2.解法

首先构建拉格朗日函数如下：

$L(x,\alpha)=f(x)+\beta *h(x)$ ...............................................................(8)

对(8)式关于 $x$ 求偏导，可得

$\nabla_xL(x,\beta)=0$ ...................................................................................(9)

另外还有KKT条件如下：

$\beta=0 \ and \ h(x)> 0$ 或者 $\beta> 0 \ and \ h(x)=0$ .....................(10)

由（9）（10）两式可以得出最后的最优解。对于（10）式的解释请看2.3节。

2.3.解释

假设我们的目标函数为二维的，下图给出了目标函数的等高线与不等式约束：

根据上图可知，可行解存在于 $g(x)< 0$ 或者 $g(x)=0$ 的区域里取到，存在下列两种情况：

a)当可行解 $x$ 落在 $g(x)< 0$ 的区域内，此时约束条件不起作用，直接极小化 $f(x)$ 即可，所以（1）式 $L(x,\alpha)=f(x)+\beta *h(x)$ 中，只需满足 $\beta=0$ 即可。即上图左侧所示.

b)当可行解 $x$ 落在 $g(x)= 0$ 的区域内，此时等价于等式约束优化问题。即上图右侧所示。此时目标函数的梯度方向为指向中心位置的反方向，而约束函数 $h(x)$ 由约束区域指向非约束区域。由下图可以看出，在最优解的位置，约束函数的梯度方向于目标函数的梯度方向正好相反，从而有：

$-\nabla_xf(x)=\beta*\nabla_xg(x)$ ..................................................(11)

（11）式其实就是（9）式的变形。当然（11）式有一个限制条件 $\beta> 0$ 。

收起

展开全文

不等式约束优化问题及KKT条件理解
2020-12-14 18:56:31
不等式约束优化问题及KKT条件理解我们只考虑不等式约束下的优化问题，如: minf(x) minf(x) minf(x) s.t.g(x)≤0 s.t.g(x)\leq0 s.t.g(x)≤0 这里xxx是多维的向量，约束不等式g(x)≤0g(x)\leq0g(x)≤0表示的是多维...
收起

《最优化导论》-21不等式约束优化

2019-02-19 09:37:58

在上面的包含等式、不等式的约束形式下：分析： u和g(x*)至少一个为0，既g起作用时u可以>=0，g不起作用时u=0 几何解释：总结： g>=0的情况： u与g方向上极小点相反，极大点相同。 ...

1一般形式

1.1起作用、不起作用约束

1.2KKT条件

在上面的包含等式、不等式的约束形式下：

分析：

u和g(x*)至少一个为0，既g起作用时u可以>=0，g不起作用时u=0

几何解释：

总结：

g>=0的情况：

u与g方向上极小点相反，极大点相同。

推广：

收起

展开全文

凸优化第四章凸优化问题 4.6广义不等式约束

千次阅读 2019-01-26 20:59:45

则称此问题为广义不等式意义下的凸优化问题。结论：可行集、任意下水平集和最优集都是凸的。上述问题的任意局部最优解都是全局最优解。可微函数的最优性条件都成立。锥形式问题锥形式问题也称锥规划，有...

4.6广义不等式约束

锥形式问题
半定规划
例子

广义不等式约束

将不等式约束函数扩展为向量，并使用广义不等式，得到：

$minimize \, \,f_0(x) \\ subject \, \, to \, \,\begin{matrix} f_i(x)\preceq _{K_i} 0,i=1,2,\cdots m\\ Ax=b \end{matrix}$

其中 $f_0:R^n\rightarrow R$ ， $K_i\subseteq R^{k_i}$ 为正常锥， $f_i:R^n\rightarrow R^{k_i}$ 为 $K_i$ 凸的。则称此问题为广义不等式意义下的凸优化问题。

结论：

可行集、任意下水平集和最优集都是凸的。
上述问题的任意局部最优解都是全局最优解。
可微函数 $f_0$ 的最优性条件都成立。

锥形式问题

锥形式问题也称锥规划，有线性目标函数和一个不等式约束函数（仿射函数）：

$minimize \, \,c^Tx \\ subject \, \,to \, \,\begin{matrix} Fx+g\preceq _K0\\ Ax=b \end{matrix}$

标准形式的锥形式问题：

$minimize \, \,c^Tx \\ subject \, \,to \, \,\begin{matrix} x\succeq _K0\\ Ax=b \end{matrix}$

不等式形式的锥形式问题：

$minimize \, \,c^Tx \\ subject \, \,to \, \,\begin{matrix} Fx+g\preceq _K0\end{matrix}$

半定规划

当K为 $S_+^k$ ，即 $k\times k$ 半正定矩阵锥时，相应的锥形式问题为半定规划（SDP）：

$minimize \,\, c^Tx \\ subject \, \, to \, \, \begin{matrix} x_1F_1+\cdots +x_nF_n+G\preceq 0\\ Ax=b \end{matrix}$

其中 $G,F_1,\cdots F_n\in S^k,A\in R^{p\times n}$ ，且不等式是线性矩阵不等式（LMI）。

如果 $G,F_1,\cdots F_n$ 都是对角阵，那么上式中的线性矩阵不等式等价于n个线性不等式，SDP退化为线性规划。

标准形式的半定规划

标准形式的SDP具有对变量 $X\in S^n$ 的线性等式约束和非负约束：

$minimize \, \, tr(CX) \\ subject \, \, to \, \,\begin{matrix} tr(A_iX)=b_i,i=1,2,\cdots p\\ X\succeq 0 \end{matrix}$

其中 $C,A_1,A_2,\cdots A_p\in S^n$ 。

不等式形式的半定规划

$minimize \, \, c^Tx \\ subject \, \, to \, \,x_1A_1+x_2A_2+\cdots x_nA_n\preceq B$

其优化变量 $x\in R^n,B,A_1,A_2,\cdots A_n\in S^k,c\in R^n$ 。

多个LMI：

$minimize \, \, c^Tx \\ subject \, \, to \, \,F^{(i)}(x)=x_1F^{(i)}_1+x_2F^{(i)}_2+\cdots x_nF^{(i)}_n+G^{(i)}\preceq 0$

多个LMI和一个LMI是等价的，例如

$minimize \, \, c^Tx \\ subject \, \, to \, \,\begin{matrix} F^{(1)}(x)=x_1F^{(1)}_1+x_2F^{(1)}_2+\cdots x_nF^{(1)}_n+G^{(1)}\preceq 0\\ F^{(2)}(x)=x_1F^{(2)}_1+x_2F^{(2)}_2+\cdots x_nF^{(2)}_n+G^{(2)}\preceq 0 \end{matrix}$

其约束函数可以写成：

$x_1\begin{bmatrix} F^{(1)}_1 & 0\\ 0 & F^{(2)}_1 \end{bmatrix}+x_2\begin{bmatrix} F^{(1)}_2 & 0\\ 0 & F^{(2)}_2 \end{bmatrix}+\cdots +x_n\begin{bmatrix} F^{(1)}_n & 0\\ 0 & F^{(2)}_n \end{bmatrix}\preceq 0$

新的约束的矩阵仍然属于 $S^k$

LP 、SOCP、SDP

首先解释为什么当 $G,F_1,\cdots F_n$ 都是对角阵时，那么上式中的线性矩阵不等式等价于n个线性不等式，SDP退化为线性规划

当 $G,F_1,\cdots F_n$ 都是对角阵时，取k=2，n=2，此时约束函数：

$x_1\begin{bmatrix} F^{(1)}_{11} & 0\\ 0 & F^{(1)}_{22} \end{bmatrix}+x_2\begin{bmatrix} F^{(2)}_{11} & 0\\ 0 & F^{(2)}_{22} \end{bmatrix}+\begin{bmatrix} G_{11} & 0\\ 0 & G_{22} \end{bmatrix}\preceq 0$

$\Rightarrow\begin{matrix} x_1F^{(1)}_{11}+x_2F^{(2)}_{11}+G_{11}\preceq 0 \\ x_1F^{(1)}_{22}+x_2F^{(2)}_{22}+G_{22}\preceq 0 \\ \end{matrix}$

显然SDP退化为线性规划。

SOCP和等价的SDP

SOCP：

$minimize \, \, f^Tx \\ subject \,\, to \,\,\begin{Vmatrix} A_ix+b_i\end{Vmatrix}_2\leq c_i^Tx+d_i,i=1,2,\cdots m$

想要得到其等价的SDP，关键在于对其约束函数的转变，即由SOCP的约束函数得到一个矩阵半定约束。

$minimize \, \, f^Tx \\ subject \,\, to \,\,\begin{bmatrix} (c_i^Tx+d_i)I & A_ix+b_i\\ ( A_ix+b_i)^T& (c_i^Tx+d_i) \end{bmatrix}\succeq 0$

显然矩阵正定有两个约束：（1） $(c_i^Tx+d_i)I\geq 0$ （2） $(c_i^Tx+d_i)I(c_i^Tx+d_i)-(A_ix+b_i)^T(A_ix+b_i)\geq 0$ 由这两个约束可推出SOCP的约束。

例子

最小化矩阵最大的特征值

$minimize \, \, \lambda _{max}(A(x))$

$A(x)=A_0+x_1A_1+x_2A_2+\cdots x_nA_n,A_i\in S^k$

相当于找到一个最小的t，使得 $\lambda _{max}(A(x))\leq t$ ，即 $\forall y,x,y^TA(x)y\preceq y^Tty\Leftrightarrow A(x)\preceq tI\Leftrightarrow A(x)-tI\preceq 0$

等价于SDP：

$minimize \, \, t \\ subject \, \, to \, \,A(x)-tI\preceq 0$

矩阵范数极小化

$minimize \, \, \begin{Vmatrix} A(x)\end{Vmatrix}_2=(\lambda _{max}(A(x)^TA(x)))^{1/2}\\ A(x)=A_0+x_1A_1+x_2A_2+\cdots x_nA_n,A_i \in R^{p\times q}$

即找到一个最小t，使得 $\begin{Vmatrix}A(x) \end{Vmatrix}_2\leq t\Leftrightarrow A^TA\preceq t^2I,t\geq 0\Leftrightarrow \begin{bmatrix} tI & A\\A^T & tI \end{bmatrix}\succeq 0$

所以其对应的SDP问题为：

$minimize \, \, t \\ subject \, \, to \, \,\begin{bmatrix} tI & A\\A^T & tI \end{bmatrix}\succeq 0$

收起

展开全文

凸优化第四章凸优化问题 4.6 广义不等式约束

2020-12-17 09:54:45

4.6 广义不等式约束

锥形式问题
半定规划
例子

广义不等式约束

将不等式约束函数扩展为向量，并使用广义不等式，得到：

$minimize \, \,f_0(x) \\ subject \, \, to \, \,\begin{matrix} f_i(x)\preceq _{K_i} 0,i=1,2,\cdots m\\ Ax=b \end{matrix}$

其中 $f_0:R^n\rightarrow R$ ， $K_i\subseteq R^{k_i}$ 为正常锥， $f_i:R^n\rightarrow R^{k_i}$ 为 $K_i$ 凸的。则称此问题为广义不等式意义下的凸优化问题。

结论：

可行集、任意下水平集和最优集都是凸的。
上述问题的任意局部最优解都是全局最优解。
可微函数 $f_0$ 的最优性条件都成立。