速盈注册

速盈资讯>更多

速盈资讯

最优化｜线性优化

发布时间：2024-04-29 04:08:45　浏览次数：

上一节学习了ADMM算法，至此将最优化方法中的数值优化部分粗略的学习完了，这一节将学习线性优化

线性优化研究的问题具有以下特点

目标函数为决策变量的线性函数
约束条件为线性等式或线性不等式约束

线性优化问题的标准型具有以下形式，记该问题为 $(LP)$ $\\begin{cases}\\begin{align*}\\min \\quad & c^T x\\\\ s.t \\quad &Ax=b\\\\ \\quad & x \\geq 0 \\end{align*}\\\\ \\end{cases}\\\\$ 其中 $c \\in R^n,A \\in R^{m \ imes n},b \\in R^m$ ，通常来说都是假设系数矩阵 $A$ 行满秩，即 $r(A)=m$ ，行满秩即无多余约束条件，且不存在方程组无解的情况

线性优化的标准型除了需要满足

决策变量会负
求解目标函数的最小值

并非所有的线性优化问题都是标准的线性优化问题，但是只要是线性优化问题就一定可以化为标准型

不是求解最小值问题，转换形式如下 $\\max d^Tx \\Leftrightarrow \\min -d^Tx\\\\$
约束条件为不等式，转换形式如下 $a_i^Tx \\leq b_i \\Leftrightarrow \\begin{cases}a_i^Tx + s=b_i\\\\ s \\geq 0 \\end{cases}, a_i^Tx \\geq b_i \\Leftrightarrow \\begin{cases}a_i^Tx - s=b_i\\\\ s \\geq 0 \\end{cases}\\\\$ 其中 $s$ 被称为松弛变量
决策变量无符号要求，转换形式如下 $x_i=x_i^{+}-x_i^{-},x_i^{+},x_i^{-}\\geq 0\\\\$

线性优化的可行集 $S=\\{x | Ax=b,x\\geq 0\\}\\\\$ 并且可行集是一个多面体

极点【extreme point】：给出凸集 $C$ ，若 $x \\in C$ 不能表示成 $C$ 中另外两点的凸组合，则称 $x$ 为 $C$ 的极点
方向【recession direction】：给出凸集 $C$ ，若非零向量 $d$ 满足对于任意的 $x \\in C$ 均有 $x + \\lambda d \\in C,\\forall \\lambda > 0$ ，则称 $d$ 为集合 $C$ 的方向
极方向：【extreme direction】若方向 $d$ 不能表示成另外两个方向的正线性组合，即不存在 $\\lambda_1,\\lambda_2 > 0$ ，使得 $d=\\lambda_!d_1+\\lambda_2d_2$ ，则称 $d$ 为 $C$ 的极方向

考虑多面体 $S=\\{x | Ax=b,x\\geq 0\\}$ ，这里假设 $A \\in R^{m \ imes n}$ 行满秩， $x \\in S$ 是 $S$ 的极点，当且仅当 $x$ 可以表示为 $\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}$ ，其中 $A=\\begin{bmatrix}B &N\\end{bmatrix}$ ， $B$ 可逆且 $B^{-1}b > 0$

说明：

记 $A=\\begin{bmatrix}B &N\\end{bmatrix}$ 是将 $A$ 中的列重新进行了排列，将 $A$ 中线性无关的列组成矩阵 $B$ ，剩余的列组成矩阵 $N$ 。对 $A$ 进行分块以后相应的对 $x$ 也需要进行分块， $x$ 的分块表示为 $\\begin{bmatrix}x_B\\\\ x_N \\end{bmatrix}$ ，因此 $Ax=b$ 可表示为 $\\begin{bmatrix}B &N\\end{bmatrix}\\begin{bmatrix}x_B\\\\ x_N \\end{bmatrix}=b\\\\$ 即 $Bx_B+Nx_N=b\\\\$ 因此如果给了 $x_N$ 一组值， $B$ 和 $N$ 已知，则 $x_B$ 的值就可以求解出来。如果想要求解一组简单的值，可以令 $x_N=0\\\\$ 因此 $Bx_B=b\\\\$ $B$ 可逆，因此可以得到 $x_B=B^{-1}b\\\\$ 方程的一个解为 $\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}\\\\$ 后面的定理中将不再说明矩阵 $A$ 的分解

充分性的证明：

已知 $x=\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}\\geq 0,A=\\begin{bmatrix}B &N\\end{bmatrix},B$ 可逆，且 $B^{-1}b > 0$

先证 $x$ 在可行集中， $Ax=\\begin{bmatrix}B &N\\end{bmatrix}\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}=b$ ，因此 $x$ 在可行集中。下证 $x$ 是极点

不妨设 $x=\\lambda \\overline x +(1-\\lambda) \\widetilde x$ ，其中 $\\lambda \\in (0,1),\\overline x,\\widetilde x \\in S$ ，如果 $\\overline x=\\widetilde x=x$ ，则 $x$ 不能表示成另外两点的凸组合，即 $x$ 是极点

因为 $\\overline x,\\widetilde x \\in S$ ，因此满足约束条件，即 $A \\overline x=b,\\overline x \\geq 0\\\\ A \\widetilde x=b,\\widetilde x\\geq 0\\\\$ 对 $\\overline x,\\widetilde x$ 进行相应的分块，即 $\\overline x=\\begin{bmatrix}\\overline x_B\\\\ \\overline x_N \\end{bmatrix}, \\widetilde x=\\begin{bmatrix}\\widetilde x_B\\\\ \\widetilde x_N \\end{bmatrix}\\\\$ 可得 $\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}=\\lambda \\begin{bmatrix}\\overline x_B\\\\ \\overline x_N \\end{bmatrix}+(1-\\lambda) \\begin{bmatrix}\\widetilde x_B\\\\ \\widetilde x_N \\end{bmatrix}\\\\$ 因为 $\\lambda,1-\\lambda > 0\\\\$ 因此 $\\overline x_N=0,\\widetilde x_N=0\\\\$ 又因为 $A \\overline x=b$ ，即 $\\begin{bmatrix}B &N\\end{bmatrix}\\begin{bmatrix}\\overline x_B\\\\ 0 \\end{bmatrix}=B\\overline x_B=b\\\\$ 可得 $\\overline x_B=B^{-1}b\\\\$ 因此 $\\overline x=\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}\\\\$ 同理可得 $\\widetilde x=\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}\\\\$ 因此 $x=\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}$ 是极点

必要性的证明：

已知 $x$ 是 $S$ 的极点， $Ax=b,x\\geq 0$

不妨设 $x=[x_1,x_2,...,x_k,0,...,0]^T,x_1,...,x_k > 0$ ，如果 $A=[a_1,a_2,...,a_n]$ ，考虑 $x$ 对应 $A$ 的列 $a_1,a_2,...,a_k$

如果 $a_1,a_2,...,a_k$ 线性相关，则存在不全为0的一组数 $\ heta_1,\ heta_2,...,\ heta_k$ 使得 $\ heta_1a_1+\ heta_2a_2+....+\ heta_ka_k=0\\\\$ 构造 $n$ 维向量 $\ heta=[\ heta_1,\ heta_2,...,\ heta_k,0,...,0]^T$ ，则 $A\ heta=\ heta_1a_1+\ heta_2a_2+....+\ heta_ka_k=0\\\\$ 取充分小的 $\\varepsilon > 0$ ，则 $x+\\varepsilon \ heta \\geq 0,x-\\varepsilon\ heta \\geq 0$ ，记 $\\overline x=x + \\varepsilon \ heta,\\widetilde x=x-\\varepsilon\ heta\\\\$ 则 $A\\overline x=A(x+\\varepsilon\ heta)=Ax+\\varepsilon A\ heta=b\\\\$ 同理可得 $A \\widetilde x=b\\\\$ 因此 $\\overline x,\\widetilde x \\in S\\\\$ 又因为 $x=\\frac{1}{2}\\overline x+\\frac{1}{2}\\widetilde x\\\\$ 与 $x$ 是极点矛盾，因此 $\ heta_1,\ heta_2,...,\ heta_k$ 线性无关

又因为 $r(A)=m$ ，若 $k=m$ ，记 $x_B=\\begin{bmatrix}x_1\\\\ \\vdots\\\\ x_m \\end{bmatrix}, B=[a_1,...,a_m]\\\\$ 其中 $B$ 可逆

则 $Ax=\\begin{bmatrix}B &N\\end{bmatrix}\\begin{bmatrix}\\overline x_B\\\\ 0 \\end{bmatrix}=B\\overline x_B=b\\\\$ 可得 $\\overline x_B=B^{-1}b\\\\$ 因此 $x=\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}\\\\$ 若 $k < m$ ，则 $a_1,a_2,...,a_k$ 线性无关，再取 $m-k$ 个向量凑成一个极大线性无关组 $a_1,...,a_k,a_{k+1},...,a_m$ 记为 $B$ ，对应的 $x^B=[x_1,...,x_k,0,...,0]^T$ ，因此可得 $x=\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}\\\\$ 所以只要 $x$ 是极点，则一定可表示为 $x=\\begin{bmatrix}B^{-1}b\\\\ 0 \\end{bmatrix}\\\\$ 由这个定理可得，极点的个数是有限多的，至多为 $C_n^m$ 个，因为选取出来的 $B$ 不一定是可逆的，且在可逆的情况下也不一定满足 $B^{-1}b \\geq 0$

若 $d$ 为方向，由前面的定义可知 $x+\\lambda d \\in S$ ，则满足 $A(x+\\lambda d)=b \\quad(1)\\\\$ 因为 $x \\in S$ ，则满足 $Ax=b\\\\$ 由 $(1)$ 式可得 $Ad=0\\\\$ 且满足 $x + \\lambda d \\geq 0,\\forall \\lambda \\geq 0$ ，因此 $d \\geq 0\\\\$ 否则若 $d < 0$ ，当 $\\lambda$ 非常大的时候， $x + \\lambda d < 0$

因此 $d$ 是集合 $S$ 的方向等价为 $Ad=0,d\\geq 0\\\\$

考虑多面体 $S=\\{x|Ax=b,x \\geq 0\\}$ ，这里假设 $A \\in R^{m \ imes n}$ 行满秩， $d \\in R^n$ 是 $S$ 的极方向当且仅当存在矩阵 $A$ 的分解 $A=\\begin{bmatrix}B &N\\end{bmatrix}$ ，使得 $d=t\\begin{bmatrix}-B^{-1}a_j \\\\ e_j \\end{bmatrix}\\\\$ 其中 $t>0,B^{-1}a_j\\leq 0$ ， $a_j$ 为矩阵 $N$ 的第 $j$ 列， $e_j \\in R^{n-m}$ 的第 $j$ 个分量为1，其余分量为0的向量，且极方向有限多个

说明： $t>0,B^{-1}a_j\\leq 0$ ，即 $d > 0$

充分性的证明：

取 $d=t\\begin{bmatrix}-B^{-1}a_j \\\\ e_j \\end{bmatrix}> 0,A=\\begin{bmatrix}B &N \\end{bmatrix}$ ， $a_j$ 是 $N$ 的 $j$ 列

因为 $1d$ 和 $5d$ 都被认为是同一个方向，因此下面的证明中用 $d=\\begin{bmatrix}-B^{-1}a_j \\\\ e_j \\end{bmatrix}$

极方向一定是方向，因此先证明方向 $Ad=\\begin{bmatrix}B &N \\end{bmatrix}\\begin{bmatrix}-B^{-1}a_j \\\\ e_j \\end{bmatrix}=-a_j+Ne_j=0\\\\$ 因此 $d$ 为方向

下证 $d$ 是极方向，不妨设 $d=\\lambda_1\\overline d+\\lambda_2 \\widetilde d,\\lambda_1,\\lambda_2> 0$ ，因为 $\\overline d,\\widetilde d$ 是方向，因此满足 $A\\overline d=0,\\overline d \\geq 0,A\\widetilde d=0,\\widetilde d \\geq 0\\\\$ 对 $\\overline d,\\widetilde d$ 进行相应的分块 $\\overline d=\\begin{bmatrix}\\overline d_B \\\\ \\overline d_N \\end{bmatrix}, \\widetilde d=\\begin{bmatrix}\\widetilde d_B \\\\ \\widetilde d_N \\end{bmatrix}\\\\$ 因此 $\\begin{bmatrix}-B^{-1}a_j \\\\ e_j \\end{bmatrix}=\\lambda_1\\begin{bmatrix}\\overline d_B \\\\ \\overline d_N \\end{bmatrix}+\\lambda_2 \\begin{bmatrix}\\widetilde d_B \\\\ \\widetilde d_N \\end{bmatrix}\\\\$ 则 $e_j=\\lambda_1\\overline d_N+\\lambda_2 \\widetilde d_N\\\\$ 因为 $\\lambda_1,\\lambda_2 > 0$ ，因此 $\\overline d_N=t_1e_j, \\widetilde d_N=t_2e_j,t_1,t_2 \\geq0\\\\$ 如果 $t_1=0$ ，则 $\\overline d_N=0$ ，因此 $\\overline d=\\begin{bmatrix}\\overline d_B \\\\ 0 \\end{bmatrix}\\\\$ 又因为 $A\\overline d=\\begin{bmatrix}B &N \\end{bmatrix}\\begin{bmatrix}\\overline d_B \\\\ 0 \\end{bmatrix}=B\\overline d_B=0\\\\$ 因为 $B$ 可逆，因此 $\\overline d_B=0\\\\$ 即 $d=0$ 矛盾，因此 $t_1=0$ 不成立，同理 $t_2=0$ 不成立，因此 $\\overline d_N=t_1e_j, \\widetilde d_N=t_2e_j,t_1,t_2 >0\\\\$ 考虑 $\\overline d=0$ ，因为 $A\\overline d=0$ ，可得 $A\\overline d=\\begin{bmatrix}B &N \\end{bmatrix}\\begin{bmatrix}\\overline d_B \\\\ t_1e_j \\end{bmatrix}=B\\overline d_B+t_1Ne_j=0\\\\$ 即 $B\\overline d_B+t_1a_j=0\\\\$ 得 $\\overline d_B=-t_1B^{-1}a_j\\\\$ 因此 $\\overline d=\\begin{bmatrix}\\overline d_B \\\\ \\overline d_N \\end{bmatrix}=\\begin{bmatrix}-t_1B^{-1}a_j\\\\ t_1e_j \\end{bmatrix}=t_1\\begin{bmatrix}-B^{-1}a_j\\\\ e_j \\end{bmatrix}=t_1d\\\\$ 同理可得 $\\widetilde d=t_2d\\\\$ 因此 $d$ 是极方向

必要性的证明：

已知 $d$ 是 $S$ 的极方向，因此 $d$ 一定是方向，即满足 $Ad=0,d\\geq0$

不妨设 $d$ 的分量中有 $k+1$ 个正的，其余为0，记 $d=[d_1,d_2,...,d_k,...,t,...]^T \\in R^n$ ，其中 $d_1,...,d_k,t > 0$ ，取 $d$ 对应 $A$ 的列 $a_1,a_2,...,a_k$ ，若 $a_1,a_2,...,a_k$ 线性相关，则存在不全为0的 $\ heta_1,...,\ heta_k$ 使得 $\ heta_1a_1+\ heta_2a_2+....+\ heta_ka_k=0\\\\$ 构造 $\ heta=[\ heta_1,...,\ heta_k,0,...,0]^T \\in R^n$ ，取充分小的 $\\varepsilon > 0$ ，则 $d+\\varepsilon\ heta \\geq 0,d-\\varepsilon\ heta \\geq 0$ ，记 $\\overline d=d+\\varepsilon\ heta ,\\widetilde d=d-\\varepsilon\ heta \\\\$ 因此 $A\\overline d=0,A\\widetilde d=0\\\\$ 可以得到 $\\overline d ,\\widetilde d$ 是 $S$ 的方向

因为 $d=\\frac{1}{2}\\overline d+\\frac{1}{2}\\widetilde d\\\\$ 与 $d$ 是极方向矛盾，因此 $a_1,a_2,...,a_k$ 线性无关

当 $k=m$ 时， $d=\\begin{bmatrix}d_1\\\\ \\vdots\\\\ d_m\\\\ 0\\\\ \\vdots\\\\ t\\\\ \\vdots\\\\ 0 \\end{bmatrix}$ ，记 $d_B=\\begin{bmatrix}d_1\\\\ \\vdots\\\\ d_m\\\\ \\end{bmatrix}, d_N=\\begin{bmatrix}0\\\\ \\vdots\\\\ t\\\\ \\vdots\\\\ 0 \\end{bmatrix}=te_j, B=[a_1,...,a_m],N=[a_{m+1},...,a_n]\\\\$ 由于 $Ad=0$ ，可得 $\\begin{bmatrix}B &N \\end{bmatrix}\\begin{bmatrix}d_B \\\\ d_N \\end{bmatrix}=Bd_B+tNe_j=Bd_B+ta_j=0\\\\$ 则有 $d_B=-tB^{-1}a_j\\\\$ 可得 $d=\\begin{bmatrix}-tB^{-1}a_j\\\\ te_j \\end{bmatrix}=t\\begin{bmatrix}-B^{-1}a_j\\\\ e_j \\end{bmatrix}\\\\$ 当 $k< m$ 时，已知 $a_1,...,a_k$ 线性无关，则必然可从剩余的列【除了 $a_1,...,a_k,t$ 对应的列】中选 $a_{k+1},...,a_m$ ，使得 $a_1,...,a_k,a_{k+1},...,a_m$ 线性无关，记 $B=[a_1,...,a_m]\\\\$ 剩余的列记为 $N$ ，记 $d_B=[d_1,...,d_m]^T,d_N=[0,...,t,...,0]^T\\\\$ 则 $Ad=0\\\\$ 同理可得 $d=t\\begin{bmatrix}-B^{-1}a_j\\\\ e_j \\end{bmatrix}\\\\$ 所以只要 $d$ 是方向，则可以表示为 $t\\begin{bmatrix}-B^{-1}a_j\\\\ e_j \\end{bmatrix}$ 。同理因为 $B$ 的选取有限多种，所以极方向有限个

可行集的表示除了 $S=\\{x | Ax=b,x\\geq 0\\}$ 还有另外的方式。假设 $S$ 的极点为 $x_1,...,x_k$ ，极方向为 $d_1,...,d_l$ ，则 $x \\in S$ 当且仅当 $x$ 具有如下形式 $x=\\sum_{i=1}^{k}{\\lambda_ix_i}+\\sum_{j=1}^{l}{\\mu_jd_j}\\\\$ 其中 $\\sum_{i=1}^{k}{\\lambda_i}=1,\\lambda_i \\geq 0,i=1,...,k,\\mu_j\\geq0,j=1,...,l$

即可行集中的点可以表示为极点的凸组合加极方向的非负组合

这个定理结合图形很容易理解，这里暂时不做证明

因为可行集有另外一种表示，因此问题 $(LP)$ 可以等价为 $\\begin{cases}\\begin{align*}\\min \\quad & c^T (\\sum_{i=1}^{k}{\\lambda_ix_i}+\\sum_{j=1}^{l}{\\mu_jd_j})\\\\ s.t \\quad &\\sum_{i=1}^{k}{\\lambda_i}=1,\\lambda_i \\geq 0,i=1,...,k,\\mu_j\\geq0,j=1,...,l\\\\ \\end{align*}\\\\ \\end{cases}\\\\$ 即 $\\begin{cases}\\begin{align*}\\min \\quad & c^T (\\sum_{i=1}^{k}{\\lambda_ix_i})+c^T(\\sum_{j=1}^{l}{\\mu_jd_j})\\\\ s.t \\quad &\\sum_{i=1}^{k}{\\lambda_i}=1,\\lambda_i \\geq 0,i=1,...,k,\\mu_j\\geq0,j=1,...,l\\\\ \\end{align*}\\\\ \\end{cases}\\\\$ 当选取了极点和极方向以后，问题就转换为了关于 $\\lambda_i,\\mu_j$ 的线性问题了

若存在某个 $j$ 使得 $c^Td_j < 0$ ，因为 $\\mu_j$ 可以取任意大，因此 $v(LP)=-\\infty$
若 $c^Td_j \\geq 0$ ，因为 $\\mu_j$ 可以取任意大，因此要使得目标函数最小，则 $\\mu_j=0$ ，问题转换为 $\\begin{cases}\\begin{align*}\\min \\quad & c^T \\sum_{i=1}^{k}{\\lambda_ix_i}\\\\ s.t \\quad &\\sum_{i=1}^{k}{\\lambda_i}=1,\\lambda_i \\geq 0,i=1,...,k\\\\ \\end{align*}\\\\ \\end{cases}\\\\$ 也等价为 $\\min_{i=1,...,k}c^T x_i\\\\$ 因此最小值在极点处取到

即线性优化问题 $(LP)$ 有最优解，当且仅当 $c^Td_j \\geq 0,j=1,...,l$ ，并且若有最优解，则必在某个极点取到

如果极点非常多，一个一个将极点带进去进行比较求最小，时间成本将非常高，因此就有了单纯形法。单纯形法的基本思想是找到找到一个极点 $\\overline x$ ，判断极点 $\\overline x$ 是否为最优解，若 $\\overline x$ 不是，则寻找一个更优的极点，避免遍历所有的极点。因此问题的关键是如何判断当前极点是否为最优解，如果不是，如何选取更优的极点

取 $x \\in S$ ，对 $A$ 做了一个相应的分块以后，对 $x$ 和 $c$ 也做一个相应的分块 $x=\\begin{bmatrix}x_B\\\\ x_N \\end{bmatrix},c=\\begin{bmatrix}c_B\\\\ c_N \\end{bmatrix}\\\\$ 因此 $Ax=b$ 即 $\\begin{bmatrix}B &N \\end{bmatrix}\\begin{bmatrix}x_B\\\\ x_N \\end{bmatrix}=Bx_B+Nx_N=b\\\\$ 解得 $x_B=B^{-1}b-B^{-1}Nx_N\\\\$ 若对 $\\forall x \\in S,c^Tx-c^T\\overline x \\geq 0$ 恒成立，则 $\\overline x$ 是最优解，即 $\\begin{align*}c^Tx-c^T\\overline x &=\\begin{bmatrix}c_B^T & C_N^T \\end{bmatrix}\\begin{bmatrix}x_B\\\\ x_N \\end{bmatrix}- \\begin{bmatrix}c_B^T & C_N^T \\end{bmatrix}\\begin{bmatrix}B^{-1}b\\\\0 \\end{bmatrix}\\\\ &=c_B^Tx_B+c_N^Tx_N-c_B^TB^{-1}b\\\\ &=c_B^TB^{-1}b-c_B^TB^{-1}Nx_N+c_N^Tx_N- c_B^TB^{-1}b\\\\ &=(c_N^T-c_B^TB^{-1}N)x_N \\quad(*) \\end{align*}\\\\$ 因为 $x_N\\geq0$ ，因此

若 $c_N^T-c_B^TB^{-1}N \\geq 0$ ，则 $(*)$ 式大于等于0恒成立，即 $\\overline x$ 是最优解

若 $c_N^T-c_B^TB^{-1}N \\geq 0$ 不成立，即存在某个分量小于0，设第 $j$ 个分量小于0，即 $c_j-c_B^TB^{-1}a_j < 0$ ，记 $d_j=\\begin{bmatrix}-B^{-1}a_j\\\\ e_j \\end{bmatrix}\\\\$ 则 $c^Td_j=\\begin{bmatrix}c_B^T & C_N^T \\end{bmatrix}\\begin{bmatrix}-B^{-1}a_j\\\\ e_j \\end{bmatrix}=c_j-c_B^TB^{-1}a_j < 0\\\\$ 记 $r_j=B^{-1}a_j\\\\$ 如果 $r_j \\leq 0$ ，则 $d_j\\geq 0$ ，由前面的定理可知 $d_j$ 为极方向，但是 $c^T(\\overline x + \\lambda d_j)=c^T\\overline x + \\lambda c^Td_j \\rightarrow \\infty\\\\$ 优化问题无解

如果 $r_j \\leq 0$ 不成立，则 $d_j$ 不为极方向，不可以沿着这个方向走任意远，需要在约束条件内走最远，即要满足 $\\overline x +\\lambda d_j=\\begin{bmatrix}B^{-1}b\\\\ 0\\end{bmatrix}+\\lambda \\begin{bmatrix}-B^{-1}a_j\\\\ e_j \\end{bmatrix}=\\begin{bmatrix}B^{-1}b -B^{-1}a_j\\\\ \\lambda e_j \\end{bmatrix}\\geq 0\\\\$ 恒成立。因为 $\\lambda e_j \\geq 0$ ，因此只需关心 $B^{-1}b -B^{-1}a_j \\geq 0$ 是否成立即可，记 $\\overline b=B^{-1}b\\\\$ 即 $\\overline b - \\lambda r_j \\geq 0\\\\$ 因此每个分量都需要大于等于0，即 $\\begin{bmatrix}\\overline b_1-\\lambda r_{j1}\\\\ \\vdots\\\\ \\overline b_m-\\lambda r_{jm}\\end{bmatrix}\\geq 0\\\\$ 即 $\\overline b_i-\\lambda r_{ji}\\geq 0,i=1,...,m\\\\$ 可以得到 $\\lambda \\geq \\min \\{\\frac{\\overline b_i}{r_{ji}}| r_{ji}> 0\\}\\\\$ 因此 $\\lambda^*=\\min \\{\\frac{\\overline b_i}{r_{ji}}| r_{ji}> 0\\}\\\\$ 下一个更优的极点为 $x^*=\\overline x + \\lambda^* d_j\\\\$

总结：

若从 $\\overline x=\\begin{bmatrix}B^{-1}b\\\\0 \\end{bmatrix}$ 出发满足 $c_N^T-c_B^TB^{-1}N \\geq 0$ ，则当前解即为最优解，如果不满足，下一个选取的极点为 $\\overline x + \\lambda^* d_j$ ，其中 $d_j=\\begin{bmatrix}-B^{-1}a_j\\\\ e_j \\end{bmatrix},\\lambda^*=\\min \\{\\frac{\\overline b_i}{r_{ji}}| r_{ji}> 0\\}\\\\$

上一篇 : 初中生可以去澳洲留学吗？文章中的内容就是你想要的答案

下一篇: 智能优化算法——篇1

返回列表

地址：海南省海口市58号电话：0898-88889999 手机：13988888888

最优化｜ 线性优化

最优化｜线性优化