精华内容
下载资源
问答
  • 本文主要讲解有关原问题和拉格朗日对偶问题,以及它们之间的关系,从而引出弱对偶性和强对偶性以及 KKT 条件和 Slater 条件。 原问题 优化问题一般都可以写为下面的形式: min⁡f0(x),x∈Rn \min f_0(x),\quad x\in...

    本文主要讲解有关原问题和拉格朗日对偶问题,以及它们之间的关系,从而引出弱对偶性和强对偶性以及 KKT 条件和 Slater 条件。

    原问题

    优化问题一般都可以写为下面的形式:
    min ⁡ f 0 ( x ) , x ∈ R n \min f_0(x),\quad x\in R^n minf0(x),xRn

    s . t . f i ( x ) ≤ 0 , i = 1 , 2 , . . . , m s.t.\quad f_i(x)\leq0,\quad i=1,2,...,m s.t.fi(x)0,i=1,2,...,m

    h j ( x ) = 0 , j = 1 , 2 , . . . , p \quad \quad h_j(x)=0,\quad j=1,2,...,p hj(x)=0,j=1,2,...,p

    以上形式被成为原问题,即求解一个满足 m 个不等式约束和 p 个等式约束的函数 f 0 ( x ) f_0(x) f0(x) 的最小值。实际上我们并不关心最小值是什么,而是关心最小值在 x 是什么的时候取得。

    上述是一般的优化问题,而凸优化问题在以上形式的基础上多了几个限制条件:1. f i ( x ) f_i(x) fi(x) 为凸函数 2. h j ( x ) h_j(x) hj(x) 为仿射函数。将一般的优化问题转化为凸优化问题的好处是凸优化只有一个极小值点,也就是说凸优化问题的局部最优解即全局最优解。下面的讨论如果不加以说明都是针对一般的优化问题来说的。

    拉格朗日函数

    解决带约束的条件的优化问题的一般解决办法是拉格朗日乘子法,也就是先写出拉格朗日函数,再让拉氏函数对 x 求导得到导数为 0 的点,将这些点带入原函数,则其中的最大值即为原函数的最大值,最小值即为原函数的最小值。上述凸优化问题的拉氏函数为:
    L ( x , u , v ) = f 0 ( x ) + ∑ i = 1 m u i f i ( x ) + ∑ j = 1 p v j h j ( x ) L(x,u,v)=f_0(x)+\sum_{i=1}^mu_if_i(x)+\sum_{j=1}^pv_jh_j(x) L(x,u,v)=f0(x)+i=1muifi(x)+j=1pvjhj(x)
    其中 u i ≥ 0 u_i\geq0 ui0 v j ∈ R v_j\in R vjR,这是因为在可行域内,因为 f i ( x ) ≤ 0 f_i(x)\leq0 fi(x)0,所以当 u i ≥ 0 u_i\geq0 ui0 时, ∑ i = 1 m u i f i ( x ) \sum_{i=1}^mu_if_i(x) i=1muifi(x) 的最大值为 0;因为 h j ( x ) = 0 h_j(x)=0 hj(x)=0,所以 ∑ j = 1 p v j h j ( x ) \sum_{j=1}^pv_jh_j(x) j=1pvjhj(x) 恒为0, v j v_j vj 可以取任意值。这样就保证了 L ( x , u , v ) L(x,u,v) L(x,u,v) 的最大值为原函数 f 0 ( x ) f_0(x) f0(x) ,即 max ⁡ u , v L ( x , u , v ) = f 0 ( x ) \max_{u,v} L(x,u,v)=f_0(x) maxu,vL(x,u,v)=f0(x)

    对于固定的 x 来说,拉氏函数 L ( x , u , v ) L(x,u,v) L(x,u,v) u u u 和 v 的仿射函数。

    拉格朗日对偶函数

    由此一来,就把原来的求解带约束条件的原函数转换为了不带约束条件的拉格朗日函数。求解 min ⁡ x f 0 ( x ) \min_x f_0(x) minxf0(x) 就等价于求解 min ⁡ x max ⁡ u , v L ( x , u , v ) \min_x\max_{u,v}L(x,u,v) minxmaxu,vL(x,u,v)。但是该式子并不容易求解,所以引入了拉格朗日对偶函数(注意不是对偶问题),拉格朗日对偶函数就是拉格朗日函数关于 x 取最小值,即:
    g ( u , v ) = inf ⁡ x ∈ D L ( x , u , v ) = inf ⁡ x ∈ D [ f 0 ( x ) + ∑ i = 1 m u i f i ( x ) + ∑ j = 1 p v j h j ( x ) ] g(u,v)=\inf_{x\in D}L(x,u,v)=\inf_{x\in D}[f_0(x)+\sum_{i=1}^mu_if_i(x)+\sum_{j=1}^pv_jh_j(x)] g(u,v)=xDinfL(x,u,v)=xDinf[f0(x)+i=1muifi(x)+j=1pvjhj(x)]
    其中 inf ⁡ x ∈ D \inf_{x\in D} infxD 表示函数逐点对 x 求下确界,也就是对任意的 u u u 和 v 求出一个使得 L ( x , u , v ) L(x,u,v) L(x,u,v) 最小的 x 。当拉氏函数没有下确界时,定义下确界为 − ∞ -\infty ,即 g ( u , v ) = − ∞ g(u,v)=-\infty g(u,v)=; D 是可行域。拉格朗日对偶函数是一个凹函数,也就是说它存在一个唯一的极大值点。

    拉氏对偶函数为凹函数证明

    先来感性的看一下这个问题,因为是拉氏对偶函数是关于 u 和 v 的仿射函数,所以可以用下面两张示意图表示对 x 逐点取最小值的结果:

    上图是随便画的多个仿射函数,对其逐点取最小值得到下图:

    可以发现结果是一个凹函数。

    拉氏对偶函数和原函数的关系

    因为 min ⁡ x f 0 ( x ) = min ⁡ x max ⁡ u , v L ( x , u , v ) ≥ max ⁡ u , v min ⁡ x L ( x , u , v ) = m a x u , v g ( u , v ) \min_x f_0(x)=\min_x\max_{u,v}L(x,u,v)\geq\max_{u,v}\min_xL(x,u,v)=max_{u,v}g(u,v) minxf0(x)=minxmaxu,vL(x,u,v)maxu,vminxL(x,u,v)=maxu,vg(u,v),所以可以用拉格朗日对偶的最大值去逼近原函数的最小值。下面来证明一下上面式子的正确性:

    因为任何函数都不大于其对某个变量求最大值,故:
    f ( x , y ) ≤ max ⁡ x f ( x , y ) f(x,y)\leq\max_x f(x,y) f(x,y)xmaxf(x,y)
    上式两边对 y 求最小值得:
    min ⁡ y f ( x , y ) ≤ min ⁡ y max ⁡ x f ( x , y ) \min_yf(x,y)\leq\min_y\max_x f(x,y) yminf(x,y)yminxmaxf(x,y)
    上式中不等式的前面是一个关于 x 的函数,不妨记为 G(x),不等式后面是一个定值,不妨记为 A,所以说 G ( x ) ≤ A G(x)\leq A G(x)A,所以 G(x) 的最大值也不大于 A:
    max ⁡ x min ⁡ y f ( x , y ) ≤ min ⁡ y max ⁡ x f ( x , y ) \max_x\min_yf(x,y)\leq\min_y\max_x f(x,y) xmaxyminf(x,y)yminxmaxf(x,y)
    得证。

    弱对偶和强对偶

    我们用 p ∗ p^* p 表示原问题的最优解,即 p ∗ = min ⁡ x f 0 ( x ) p^*=\min_xf_0(x) p=minxf0(x);用 d ∗ d^* d 表示拉氏对偶函数的最优解,即 d ∗ = max ⁡ u , v g ( u , v ) d^*=\max_{u,v}g(u,v) d=maxu,vg(u,v)。并定义原问题的最优解与拉氏对偶问题的最优解之间的差值为 对偶间隙(dual gap),即 p ∗ − d ∗ p^*-d^* pd

    前面我们已经证明了原问题的最优解大于等于对偶问题的最优解,即 p ∗ ≥ d ∗ p^*\geq d^* pd,这个性质被称作 弱对偶性 ,也可以表示为对偶间隙大于等于 0,即 p ∗ − d ∗ ≥ 0 p^*-d^*\geq 0 pd0。即使当 p ∗ p^* p d ∗ d^* d 无限时,弱对偶性仍然成立。如果原问题无下界,则对偶问题也无下界;如果对偶问题无上界,则原问题也无上界,即原问题不可行。

    如果原问题的最优解和拉氏对偶问题的最优解相等,也就是对偶间隙为 0,则 强对偶性 成立。

    一般情况下强对偶性不成立,但是如果原问题是凸优化问题,即原函数和不等式约束 f i ( x ) f_i(x) fi(x) 为凸函数,而等式约束 h j ( x ) h_j(x) hj(x) 为仿射函数,则强对偶性通常(但不总是)成立。而强对偶性成立的条件一般被称为 约束准则。下面主要讲解两个约束准则—— KKT 条件Slater 条件

    KKT 条件

    之前证明了我们可以用拉格朗日对偶的最大值去逼近原函数的最小值的思路是正确的,但是什么时候两者的最大值和最小值相等呢?

    首先假设函数 f 0 ( x ) , . . . , f m ( x ) , h 1 ( x ) , . . . , h p ( x ) f_0(x),...,f_m(x),h_1(x),...,h_p(x) f0(x),...,fm(x),h1(x),...,hp(x) 都可微,但并不假设这些函数为凸函数,则拉氏对偶函数:
    g ( u ∗ , v ∗ ) = inf ⁡ x [ f 0 ( x ) + ∑ i = 1 m u i ∗ f i ( x ) + ∑ j = 1 p v j ∗ h j ( x ) ] g(u^*,v^*)=\inf_x[f_0(x)+\sum_{i=1}^mu_i^*f_i(x)+\sum_{j=1}^pv_j^*h_j(x)] g(u,v)=xinf[f0(x)+i=1muifi(x)+j=1pvjhj(x)]
    因为一个函数的下确界(最小值)不大于函数本身,故:
    ≤ f 0 ( x ∗ ) + ∑ i = 1 m u i ∗ f i ( x ∗ ) + ∑ j = 1 p v j ∗ h j ( x ∗ ) \leq f_0(x^*)+\sum_{i=1}^mu_i^*f_i(x^*)+\sum_{j=1}^pv_j^*h_j(x^*) f0(x)+i=1muifi(x)+j=1pvjhj(x)
    又因为后两项的最大值为 0,故:
    ≤ f 0 ( x ∗ ) \leq f_0(x^*) f0(x)
    上面三式中, u ∗ u^* u v ∗ v^* v x ∗ x^* x 分别是拉格朗日对偶函数和原函数的最优解。所以说要想让拉格朗日对偶函数的最大值和原函数最小值相等,需要让上面三式中的小于等于号全部取等号。

    因为拉格朗日函数在 x ∗ x^* x 处取得极小值,因此拉氏函数在 x ∗ x^* x 处的导数为 0 。所以第一个 ≤ \leq 取等号的条件是拉氏函数对 x ∗ x^* x 的偏导为 0,即:
    ∇ f 0 ( x ∗ ) + ∑ i = 1 m u i ∗ ∇ f i ( x ) + ∑ j = 1 p v j ∗ ∇ h j ( x ) = 0 条 件 ( 1 ) \nabla f_0(x^*)+\sum_{i=1}^mu_i^*\nabla f_i(x)+\sum_{j=1}^pv_j^*\nabla h_j(x)=0\quad\quad\quad\quad 条件 (1) f0(x)+i=1muifi(x)+j=1pvjhj(x)=0(1)
    第二个 ≤ \leq 取等号的条件是 ∑ i = 1 m u i ∗ f i ( x ∗ ) \sum_{i=1}^mu_i^*f_i(x^*) i=1muifi(x) ∑ j = 1 p v j ∗ h j ( x ∗ ) \sum_{j=1}^pv_j^*h_j(x^*) j=1pvjhj(x) 全部为 0,前面说了,后者恒等于 0,而前者为 0 的条件是:
    ∑ i = 1 m u i ∗ f i ( x ∗ ) = 0 \sum_{i=1}^mu_i^*f_i(x^*)=0 i=1muifi(x)=0
    但是因为在可行域内,以上求和项的每一项都是非正的,因此以上条件等价于:
    u i ∗ f i ( x ∗ ) = 0 条 件 ( 2 ) u_i^*f_i(x^*)=0\quad\quad\quad\quad\quad\quad\quad条件(2) uifi(x)=0(2)
    以上 2 个约束条件,再加上凸优化问题自身的三个约束条件就得到了著名的 KKT 条件,和 KMP 算法的名称类似,所谓的 KKT 条件的命名其实是三位科学家名字的英文首字母的组合,KKT 条件即:
    f i ( x ∗ ) ≤ 0 , i = 1 , . . . , m f_i(x^*)\leq0,\quad i=1,...,m fi(x)0,i=1,...,m

    h i ( x ∗ ) = 0 , i = 1 , . . . , p h_i(x^*)=0,\quad i=1,...,p hi(x)=0,i=1,...,p

    u i ∗ ≥ 0 , i = 1 , . . . , m u_i^*\geq0,\quad i=1,...,m ui0,i=1,...,m

    ∇ f 0 ( x ∗ ) + ∑ i = 1 m u i ∗ ∇ f i ( x ) + ∑ j = 1 p v j ∗ ∇ h j ( x ) = 0 \nabla f_0(x^*)+\sum_{i=1}^mu_i^*\nabla f_i(x)+\sum_{j=1}^pv_j^*\nabla h_j(x)=0 f0(x)+i=1muifi(x)+j=1pvjhj(x)=0

    u i ∗ f i ( x ∗ ) = 0 u_i^*f_i(x^*)=0 uifi(x)=0


    KKT 条件中的条件 (2) u i ∗ f i ( x ∗ ) = 0 u_i^*f_i(x^*)=0 uifi(x)=0 也被成为 互补松弛性,我们可以将互补松弛条件等价地改写为:
    u i ∗ > 0 ⇒ f i ( x ∗ ) = 0 u_i^*>0\Rightarrow f_i(x^*)=0 ui>0fi(x)=0
    或者:
    f i ( x ∗ ) < 0 ⇒ u i ∗ = 0 f_i(x^*)<0\Rightarrow u_i^*=0 fi(x)<0ui=0
    这是因为在可行域内有 u i ∗ ≥ 0 u_i^*\geq 0 ui0 并且 f i ( x ∗ ) ≤ 0 f_i(x^*)\leq 0 fi(x)0

    Slater 条件

    如果原始问题为凸优化问题,并且存在一点 x 使得所有的约束条件都小于 0,即:
    f i ( x ) < 0 , i = 1 , . . . , m f_i(x)<0,\quad i=1,...,m fi(x)<0,i=1,...,m
    则强对偶性成立。

    上述条件就是所谓的 Slater 条件,而满足上述条件的点被称为 严格可行,这是因为不等式约束严格成立。

    当不等式约束函数 f i ( x ) f_i(x) fi(x) 中有一些函数是仿射函数时,Slater 条件可以进一步改进。我们假设前 k 个不等式约束函数为仿射函数,则强对偶性成立的条件(即改进后的 Slater 条件)为:存在一点 x 使得前 k 个不等式约束函数小于等于 0,而其他不等式约束函数小于 0,即
    f i ( x ) ≤ 0 , i = 1 , . . . , k f_i(x)\leq 0,\quad i=1,...,k fi(x)0,i=1,...,k

    f i ( x ) < 0 , i = k + 1 , . . . , m f_i(x)<0,\quad i=k+1,...,m fi(x)<0,i=k+1,...,m

    换句话说,仿射函数不等式不需要严格成立。

    展开全文
  • 动态规划算法的基本要素[^2]5.1 最优子结构5.2 重叠子问题6.一些经典的动态规划问题 1.序 近期笔者会写一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法...

    1.序

    近期笔者会写一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。

    2.动态规划的基本概念[^1]

    在学习动态规划之前,先思考这样一个问题:什么是动态规划?为什么叫动态规划?
    当读者在试图探索这个问题的时候,不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的,应用于工程领域。
    动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

    所谓多阶段决策过程是指这样一类决策过程:它可以把一一个复杂问题按时间(或空间)分成若干个阶段,每个阶段都需要作出决策,
    以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何,不但与该阶段的经济效果有关,
    还影响以后各阶段的经济效果,可见这类多阶段决策问题是一个动态的问题,因此,处理的方法称为动态规划方法。然而,动态
    规划也可以处理一些本来与时间没有关系的静态模型,这只要在静态模型中人为地引入“时间”因素,分成时段,就可以把它看作
    是多阶段的动态模型,用动态规划方法去处理。
    

    简言之,多阶段决策过程是指这样的一类特殊的活动过程:问题可以按时间顺序分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。
    下面举例说明什么是多阶段决策问题。
    例1(最短路线问题)在线路网络图1中,从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离,为使总运费最少,必须找出一条由A至E总里程最短的路线。
    在这里插入图片描述

    图1

    为了找到由A至E的最短线路,可以将该问题分成A—B—C—D—E 4个阶段,在每个阶段都需要作出决策,即在A点需决策下一步到B1还是到B2或B3;同样,若到达第二阶段某个状态,比如B1 ,需决定走向C1还是C2 ;依次类推,可以看出:各个阶段的决策不同,由A至E的路线就不同,当 从某个阶段的某个状态出发作出一个决策,则这个决策不仅影响到下一个阶段的距离,而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策,使这些决策序列所决定的一条路线对应的总路程最短。

    3.动态规划算法的基本思想[^2]

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。
    在这里插入图片描述

    图2

    但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
    如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
    在这里插入图片描述

    图3

    4.动态规划的求解步骤[^2]

    a. 找出最优解的性质,并刻划其结构特征。
    b. 递归地定义最优值。
    c. 以自底向上的方式计算出最优值。
    d. 根据计算最优值时得到的信息,构造最优解

    5.动态规划算法的基本要素[^2]

    5.1 最优子结构

    • 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质
    • 在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。
    • 利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

    注意:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)

    5.2 重叠子问题

    • 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
    • 动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。
    • 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。
      在这里插入图片描述
      图4

    6.一些经典的动态规划问题

    题目描述:
    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

    示例 1:

    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    

    示例 2:

    输入: "cbbd"
    输出: "bb"
    

    分析:
    一个问题要使用动态规划求解,一定要满足【最优子结构】,只有满足最优子结构,才能通过子问题的解 构造出 整个问题的解。

    在编码时,一般采用【备忘录】或 dp table来实现。
    最关键的要找出:该问题的递推关系式(状态转移方程)

    假设dp[i][j]=true,表示字符串s从s[i]到s[j]的子串为最长回文子串
    反之false.

    考虑 abcba 这个示例。如果我们已经知道 bca 是回文,那么要判断 abcba 是不是回文串,只需判断它的左首字母和右尾字母是否相等。这里左=右=a,因此abcba 是回文串

    从这里我们可以归纳出状态转移方程
    dp[i][j] = true
    前提是
    dp[i+1][j-1]为true,且 s[i] == s[j]

    #include <iostream>
    using namespace std;
    class MySolution {
    public:
        string longestPalindrome(string s) {
    
            int len = s.size();
            if (len < 2)
                return s;
            //bool dp[len][len];
            bool** dp;
            dp = new bool* [len];
            for (int i = 0; i < len; i++)
                dp[i] = new bool[len];//分配了len行len列的二维数组空间
        
            int max_len=1;//最大回文串长度
            int max_left;//最长回文串的起始位置
            for (int j = 0; j < len; j++)
            {
                for (int i = 0; i < j; i++)
                {
                    if (s[j] != s[i])
                        dp[i][j] = false;
                    else if (j - i < 3) // (j-1)-(i+1)+1< 2 即表明dp[i][j]是回文串
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];//s[i]==s[j]
                    if (j - i + 1 > max_len && dp[i][j])
                    {
                        max_len = j - i + 1;
                        max_left = i;
                    }
    
                }
            }
            return s.substr(max_left, max_len);
            // 用完要释放:
            for (int i = 0; i < len; i++)
            {
                delete[] dp[i]; 
                delete[]dp;
            }   
        }
    };
    int main()
    {
        MySolution sl;
        string s = sl.longestPalindrome("abcdedcabcdefggfedcba");
        cout << s << endl;
    }
    

    参考文献
    [1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html
    [2]引用自老师的课件

    展开全文
  • 一、原问题与对偶问题标准形式、 二、互补松弛定理、 三、已知原问题最优解求对偶问题最优解、 四、使用单纯形法求解、 五、使用互补松弛定理公式一求解、 六、使用互补松弛定理公式二求解 ( 无效方法 )、 七、总结





    一、原问题与对偶问题标准形式



    原问题 P \rm P P : m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} \rm maxZ = C X \\\\ \rm s.t\begin{cases} \rm AX \leq b \\\\ \rm X \geq 0 \end{cases}\end{array} maxZ=CXs.tAXbX0 ;              \ \ \ \ \ \ \ \ \ \ \,            对偶问题 D \rm D D : m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \begin{array}{lcl} \rm minW = b^T Y \\\\ \rm s.t\begin{cases} \rm A^TY \geq C^T \\\\ \rm Y \geq 0 \end{cases}\end{array} minW=bTYs.tATYCTY0


    等价方法 :

    • 生产 : 目标函数追求 利润最大化 , 约束方程设备的使用时长受约束 , 小于等于 某个时间值 ;
    • 出租设备 : 目标函数追求 租金最小化 , 约束方程设备产生的利润要 大于等于 生产的利润 , 不能亏钱 ;




    二、互补松弛定理



    X 0 \rm X^0 X0 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D可行解 ,

    这两个解各自都是对应 线性规划问题最优解

    的 充要条件是 : { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} Y0Xs=0YsX0=0

    其中 X s , Y s \rm X_s , Y_s Xs,Ys松弛变量剩余变量 ;





    三、已知原问题最优解求对偶问题最优解



    已知线性规划 :

    m a x Z = 3 x 1 + 4 x 2 + x 3 { x 1 + 2 x 2 + x 3 ≤ 10 2 x 1 + 2 x 2 + x 3 ≤ 16 x 1 , x 2 , x 3 ≥ 0 \begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 \leq 10 \\\\ \rm 2x_1 + 2x_2 + x_3 \leq 16 \\\\ \rm x_1,x_2, x_3 \geq 0 \end{cases}\end{array} maxZ=3x1+4x2+x3x1+2x2+x3102x1+2x2+x316x1,x2,x30

    上述线性规划的最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) , 求其对偶问题最优解 ;





    四、使用单纯形法求解



    方法一 : 写出上述线性规划的对偶问题 , 然后使用单纯形法求最优解 ,

    首先写出 对偶问题 , 然后转为 标准形式 , 找 单位阵 作为基矩阵 , 然后得到基变量 , 假设非基变量为 0 0 0 求出 基解 ,

    在单纯形表中计算 检验数 , 如果 检验数都小于 0 0 0 就是最优解 , 如果检验数都大于 0 0 0 , 则不是最优解 ;

    根据检验数确定 出基变量 , 然后计算出 入基变量 , 进行下一次迭代 ;

    方程组 同解变换, 构造单位阵 , 然后计算检验数 , 继续按照上述方法进行迭代 ;

    该方法比较麻烦 ;





    五、使用互补松弛定理公式一求解



    方法二 : 利用 互补松弛定理 计算 ;

    写出原问题的对偶问题 :

    m i n W = 10 y 1 + 16 y 2 { y 1 + 2 y 2 ≥ 3 2 y 1 + 2 y 2 ≥ 4 y 1 + y 2 ≥ 1 y 1 , y 2 ≥ 0 \begin{array}{lcl} \rm minW = 10y_1 + 16y_2 \\\\ \rm \begin{cases} \rm y_1 + 2y_2 \geq 3 \\\\ \rm 2y_1 + 2y_2 \geq 4 \\\\ \rm y_1 + y_2 \geq 1 \\\\ \rm y_1,y_2 \geq 0 \end{cases}\end{array} minW=10y1+16y2y1+2y232y1+2y24y1+y21y1,y20


    给对偶问题的约束方程添加剩余变量 :

    { y 1 + 2 y 2 − y 3 = 3 2 y 1 + 2 y 2 − y 4 = 4 y 1 + y 2 − y 5 = 1 y 1 , y 2 , y 3 , y 4 , y 5 ≥ 0 \begin{cases} \rm y_1 + 2y_2 - y_3 = 3 \\\\ \rm 2y_1 + 2y_2 - y_4 = 4 \\\\ \rm y_1 + y_2 - y_5 = 1 \\\\ \rm y_1,y_2, y_3 , y _4, y_5 \geq 0 \end{cases} y1+2y2y3=32y1+2y2y4=4y1+y2y5=1y1,y2,y3,y4,y50



    互补松弛定理 :

    " X 0 \rm X^0 X0 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D最优解 " ⇔ \Leftrightarrow { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} Y0Xs=0YsX0=0

    其中 X s , Y s \rm X_s , Y_s Xs,Ys松弛变量剩余变量 ;



    原问题 P \rm P P 线性规划最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) ,

    对偶问题的剩余变量是 Y s = ( y 3 y 4 y 5 ) \rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} Ys=y3y4y5

    互补松弛定理中 Y s X 0 = 0 \rm Y_sX^0 = 0 YsX0=0 , 将上述 X 0 \rm X^0 X0 Y s \rm Y_s Ys 代入上述式子得到 :

    Y s X 0 = ( 6 2 0 ) × ( y 3 y 4 y 5 ) = 6 y 3 + 2 y 4 + 0 y 5 = 6 y 3 + 2 y 4 = 0 \rm Y_sX^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} \times \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} = 6y_3 + 2y_4 + 0y_5 = 6y_3 + 2y_4 =0 YsX0=(620)×y3y4y5=6y3+2y4+0y5=6y3+2y4=0

    已知 y 3 , y 4 ≥ 0 \rm y_3, y_4 \geq 0 y3,y40 , 上述 6 y 3 + 2 y 4 = 0 \rm 6y_3 + 2y_4 = 0 6y3+2y4=0 , 因此 y 3 = 0 , y 4 = 0 \rm y_3 = 0 , y_4 = 0 y3=0,y4=0 ;

    y 3 = 0 , y 4 = 0 \rm y_3 = 0 , y_4 = 0 y3=0,y4=0 代入到约束方程 { y 1 + 2 y 2 − y 3 = 3 2 y 1 + 2 y 2 − y 4 = 4 y 1 + y 2 − y 5 = 1 y 1 , y 2 , y 3 , y 4 , y 5 ≥ 0 \begin{cases} \rm y_1 + 2y_2 - y_3 = 3 \\\\ \rm 2y_1 + 2y_2 - y_4 = 4 \\\\ \rm y_1 + y_2 - y_5 = 1 \\\\ \rm y_1,y_2, y_3 , y _4, y_5 \geq 0 \end{cases} y1+2y2y3=32y1+2y2y4=4y1+y2y5=1y1,y2,y3,y4,y50 中 ;

    得到 { y 1 + 2 y 2 = 3 2 y 1 + 2 y 2 = 4 \begin{cases} \rm y_1 + 2y_2 = 3 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases} y1+2y2=32y1+2y2=4 , 解上述方程 ,

    ① 变换 : { 2 y 1 + 4 y 2 = 6 2 y 1 + 2 y 2 = 4 \begin{cases} \rm 2y_1 + 4y_2 = 6 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases} 2y1+4y2=62y1+2y2=4

    ② 求解 : { y 1 = 1 y 2 = 1 \begin{cases} \rm y_1 = 1 \\\\ \rm y_2 = 1 \end{cases} y1=1y2=1

    上述求出的值就是最优解 , 即 Y 0 = ( 1 1 ) \rm Y^0 = \begin{pmatrix} \quad \rm 1 \quad 1 \quad \end{pmatrix} Y0=(11) ;





    六、使用互补松弛定理公式二求解 ( 无效方法 )



    方法三 : 利用 互补松弛定理 计算 ;


    互补松弛定理 :

    " X 0 \rm X^0 X0 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D最优解 " ⇔ \Leftrightarrow { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} Y0Xs=0YsX0=0

    其中 X s , Y s \rm X_s , Y_s Xs,Ys松弛变量剩余变量 ;



    上面 " 五、使用互补松弛定理公式一求解 " 小节 使用的是 Y s X 0 = 0 \rm Y_sX^0 = 0 YsX0=0 公式进行求解 , 在本小节中使用 Y 0 X s = 0 \rm Y^0 X_s = 0 Y0Xs=0 公式进行求解 ;


    原问题 P \rm P P 线性规划最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) , 将该最优解代入原问题的约束条件中 , 求出原问题的约束变量 X s \rm X_s Xs ;

    原问题 :

    m a x Z = 3 x 1 + 4 x 2 + x 3 { x 1 + 2 x 2 + x 3 ≤ 10 2 x 1 + 2 x 2 + x 3 ≤ 16 x 1 , x 2 , x 3 ≥ 0 \begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 \leq 10 \\\\ \rm 2x_1 + 2x_2 + x_3 \leq 16 \\\\ \rm x_1,x_2, x_3 \geq 0 \end{cases}\end{array} maxZ=3x1+4x2+x3x1+2x2+x3102x1+2x2+x316x1,x2,x30

    原问题添加松弛变量后 :

    m a x Z = 3 x 1 + 4 x 2 + x 3 { x 1 + 2 x 2 + x 3 + x 4 = 10 2 x 1 + 2 x 2 + x 3 + x 5 = 16 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 \begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 + x_4 = 10 \\\\ \rm 2x_1 + 2x_2 + x_3 + x_5 =16 \\\\ \rm x_1,x_2, x_3, x_4 , x_5 \geq 0 \end{cases}\end{array} maxZ=3x1+4x2+x3x1+2x2+x3+x4=102x1+2x2+x3+x5=16x1,x2,x3,x4,x50

    将最优解 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) 代入原问题 :

    { 6 + 2 × 2 + 0 + x 4 = 10 2 × 6 + 2 × 2 + 0 + x 5 = 16 \begin{cases} \rm 6 + 2\times 2 + 0 + x_4 = 10 \\\\ \rm 2 \times 6 + 2 \times 2 + 0 + x_5 = 16 \end{cases} 6+2×2+0+x4=102×6+2×2+0+x5=16

    得到 : { x 4 = 0 x 5 = 10 \begin{cases} \rm x_4 = 0 \\\\ \rm x_5 = 10 \end{cases} x4=0x5=10

    X s = ( 0 0 ) \rm X_s = \begin{pmatrix} \quad \rm 0 \quad \\\\ \quad \rm 0 \quad \end{pmatrix} Xs=00

    这个信息是无用的 , 根据这个 X s \rm X_s Xs 乘以任意的 Y 0 \rm Y^0 Y0 值都是 0 0 0 , 求不出对偶问题的最优解 ;





    七、总结



    互补松弛定理 :

    " X 0 \rm X^0 X0 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D最优解 " ⇔ \Leftrightarrow { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} Y0Xs=0YsX0=0

    其中 X s , Y s \rm X_s , Y_s Xs,Ys松弛变量剩余变量 ;


    原问题 P \rm P P 线性规划最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) ,

    对偶问题的剩余变量是 Y s = ( y 3 y 4 y 5 ) \rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} Ys=y3y4y5

    最优解中不等于 0 0 0 的 , 对应的剩余变量中对应的一定为 0 0 0 ,

    如果最优解中等于 0 0 0 , 那么剩余变量中的对应的值就不确定了 ;

    展开全文
  • 最优化问题(Optimization)是人工智能机器学习的最底层的基石明珠。系统性的讲最优化问题在一篇文章中实在无法办到。 喜欢最优化问题的读者不妨先关注一下这个公众号,因为后面我们会用一个系列来讨论最优化...

    更多专业的人工智能相关文章,微信搜索  : robot-learner , 或扫码

     

    最优化问题(Optimization)是人工智能和机器学习的最底层的基石和明珠。系统性的讲最优化问题在一篇文章中实在无法办到。

     

    喜欢最优化问题的读者不妨先关注一下这个公众号,因为后面我们会用一个系列来讨论最优化问题。

     

     

    今天我们简单的讨论一下,约束最优化问题中常常预见的几个名词关系,比如原问题(primal problem),对偶问题(dual problem), KKT约束条件,和拉格朗日符号等。他们之间的关系是什么?

     

    1.

     

    什么是最优化问题? 比如我们要找到最佳的变量值x0,从而使得下列的方程达到最小值:

     

                 

    上面式子表的的意思就是一个最小化问题,即寻找最佳的变量,从而使得f(x)方程的值最小。

    如果f(x)满足凸函数特性(convex function),上面问题是相对容易的。

     

    2.

     

    但是问题来了,有时候我们需要对变量x做一些约束,比如在一定的距离内找到短的路径等。最小化问题就成了约束最小化问题。用公式表达就是这个意思:

     

     

     

    上式的意思是:我们仍然要找到x使得f(x)最小,但是x也必须满足条件 h(x)<=0。这个约束条件在实际情况中很普遍。但是却使得最优化问题不再具有凸函数特性,从而大大增加了寻找最值的难度。

     

    3.

     

    这个问题的救星就是原问题和对偶问题的关系。上面的式子称为原问题或者primal problem,我们可以把这个问题转化为一个标准的拉格朗日dual problem 或者对偶问题来解决:

     

     

     

     

    上面式子中,g(λ)= L(x,λ) 以x作为变量的最小值  , 并且 L(λ) = f(x) + λh(x) 叫做拉格朗日式子。λ就是新引入的限制因子。这个形式的表达式在机器学习算法中很常见。如果要对算法中的参数做一些约束,很多时候就是加上这种形式的限制因子。

     

    需要注意的是上面的对偶问题可以证明只是为原问题提供了一个下限:假设 f* 是f(x)的最小值,g*是g(λ)的最小值,那么存在这样的的关系 f* >= g*。 但在满足一定的条件下,如KKT条件,可以证明 原问题和对偶问题等价即 f* = g*。

     

    为什么要解决对偶问题?因为有的时候对偶问题更好解决,并且在一定条件下,两者等价。即使条件不满足,我们仍然获得一个下限,在实际问题中通常可行。

     

    我们可以注意到上面的对偶问题中,其实是先求拉格朗日式子最小值,再求最大值。如果我们把顺序颠倒一下,先求max 再求min, 则这个问题完全等价于原问题:

     

     

     

    4.

     

    我们注意最小化问题中的条件,一个是 h(x)<=0, 另一个是λ>=0,并且在拉格朗日式子中λ前面的符号是正的。如果你的限制条件 h(x)>=0, 那么λ前面的符号需要改为负的。

     

    为什么一定要这样?因为对偶问题提供的是原问题的一个下限答案。 在最小化问题中,只有提供下限才有意义, 如果提供的是一个上限,那么直接用无穷大就好了。

     

     

    为什么我们只讲最小化问题,而不是最大化问题?因为最大化问题只需前面添加一个负号,就可以转化为最小化问题了。

     

     

    上面也说到了,对偶问题很多时候只是一个下限。但实际问题中没有多大关系。另外,在利用机器学习算法解决问题时候,我们只是需要利用约束条件来限制一下参数以求稀疏化的目的。所以λ都是我们事先给定的或者用validation的方法来挑选。所以上面的有约束的对偶问题就进一步简化为:

     

     

    这个形式大家就更加熟悉了。

    展开全文
  • 算法:棋盘覆盖问题

    千次阅读 多人点赞 2019-10-09 20:04:47
    分治的技巧在于如何划分棋盘,使划分后的棋盘的大小相同,并且每个棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题。k>0时,可将2k×2k的棋盘划分为4个2(k-1)×2(k-1)的棋盘,如图...
  • SEO行业种很多人都认为域名比目录权重高,但仍有一大部分人认为来看,搭建一个...今天就一次说清楚目录和子域名哪个好?目录和子域名如何利用seo优化?  一个网站又数个或者N个页面,他们分别用url进行标识
  • 序列子串问题算法的全面总结

    千次阅读 多人点赞 2019-05-08 19:59:14
    1.分清楚什么是子串,什么是序列 看文章前首先要搞清楚...2.有关子串问题的算法 (1)最大子串 何为最大子串,例如:最大子串是要找出由数组成的一维数组中和最大的连续子串。比如{5,-3,4,2}的最大子串就是 {5,-3...
  • 你真的了解动态规划中的重叠子问题吗?! 他真的是你想的那样的吗?!
  • 最长公共序列问题和动态规划

    千次阅读 2018-01-28 19:31:17
    可以注意到,序列不要求所选的字母连续,只要求是按次序组成就好 这是子串的一个区别 最长公共序列定义 最长公共序列(L ongest C ommon S equence) 简称为LCS,下同 直观明了,就是两个序列的共有...
  • 动态规划-重叠子问题

    千次阅读 2015-08-23 19:06:51
    动态规划-重叠子问题flyfish 2015-8-23名词解释 重叠子问题 overlapping subproblems动态...例如LCS(最长公共子序列)问题,给定两个序列XY,长度分别是mn,穷举子问题是指数级的,而不同子问题的数量只是mn.a recur
  • 如今最好,没有来日方长! 一、简述动态规划算法1....值得注意的是,这个技术名字中的“programming”是计划规划的意思,不是计算机领域中的编程。它有着有趣的历史。 它由20世纪50年代初美国一
  • 网站301跳转问题的探讨用法以及网站做301跳转的相关问题 作者:叶涛(华军软件园seo) 相信站长朋友们都对301跳转有一定的了解,知道在网站优化中可以帮助自己,但是有些站长朋友却对如何合理使用301跳转不太...
  • 对偶问题的转换

    万次阅读 2019-07-21 10:57:32
    这个是百度里面的解释,是原问题和对偶问题的转变。 例子 小明同学拥有一家工厂,他现在有2种获利途径: 自己经营,卖出产品获得利润; 出租给他人,收取租金获得利润。 那么对于途径1,小明同学想要...
  • 一、问题描述 在数字序列A中,按下标递增的顺序选出一个序列B,如果选出的序列B是严格递增的,则该序列B称为数字序列A的递增序列。最长递增序列问题就是找到数字序列A中最长的递增序列。例如数...
  • 分治算法详解(超详细)

    万次阅读 多人点赞 2019-09-20 23:03:30
    分治算法详解 ...
  • 最大子序列和问题

    万次阅读 多人点赞 2018-10-14 11:48:08
    有几种不同的方法求解最大序列和问题,但它们的复杂度相差甚远,尤其在面对大量数据的时候。实际上,效率最高的算法非常简短,只需要几行代码,最主要的是理解它的思想。 基本算法 这是一种比较容...
  • 动态规划基础篇之最长公共序列问题

    万次阅读 多人点赞 2017-08-08 21:12:15
    (1)序列: 一个序列A = a1,a2,……an,中任意删除若干项,剩余的序列叫做A的一个子序列。也可以认为是从序列A按顺序保留任意若干项得到的序列。 例如: 对序列 1,3,5,4,2,6,8,7来说,序列3,4,8,7 是它的...
  • 都能看懂的LIS(最长上升序列)问题

    万次阅读 多人点赞 2018-07-31 21:32:35
    LIS问题介绍: 首先来说一下什么是LIS问题: ...aj的序列,该问题被称为最长上升序列(LIS,Longest Increasing Subsequence)的著名问题。 举个栗子:给你一个序列为(1,5 ,2,6,9,1...
  • 压缩感知原理简介

    万次阅读 多人点赞 2019-07-15 21:51:23
    压缩感知问题就是在已知测量值y测量矩阵Φ的基础上,求解欠定方程组y=Φx得到信号x。 然而,一般的自然信号x本身并不是稀疏的,需要在某种稀疏基上进行稀疏表示。令x=Ψs,Ψ为稀疏基矩阵,s为稀疏系数。 于是...
  • 问题  求长为m的序列长为n的序列的最长公共子序列(可以不连续),如ABCBDABBDCABA,BCABBCBA都是...要写出动态规划,首先要写出递归式,然后试着找出最优子结构与重叠子问题。 1.最优子结构就是一个问题的最优解
  • 浦发银行 信息科技岗 大数据方向 面经

    万次阅读 多人点赞 2018-08-09 23:00:31
    浦发银行总行信息科技部(大数据方向)面试 浦发银行总行信息科技部(大数据方向)面试 8.6面试 ...第三部分 上机考试(只有开发测试岗需要,别的岗可选) 浦发总行信息岗校招面经(上海...
  • 九种 0-1 背包问题详解

    千次阅读 2020-08-10 16:55:34
    问题1:0-1背包问题 问题2:完全背包问题 问题3:多重背包问题 问题4:混合背包问题 问题5:二维背包问题 问题6:分组背包问题 问题7:有依赖的背包问题(困难) 问题8:背包问题求方案数 问题9:背包问题求...
  • 线性规划对偶问题

    千次阅读 多人点赞 2021-04-28 23:49:31
    非对称形式的-对偶问题关系四. 对偶问题的基本性质五. 对偶问题的单纯形法描述六. 影子价格七. 利用Matlab解决线性规划问题八. 参考SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX...
  • 动态规划解最长公共序列问题(LCS)C语言加注释

    万次阅读 多人点赞 2015-10-27 14:56:13
    问题】 求两字符序列的最长公共字符序列 问题描述:字符序列的序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1...
  • 最大子段和问题:蛮力、递归及动态规划

    万次阅读 多人点赞 2018-06-05 18:10:10
    求一个序列的最大子段即最大连续序列之。例如序列[4, -3, 5, -2, -1, 2, 6, -2]的最大子段为11=[4+(-3)+5+(-2)+(-1)+(2)+(6)]。 1. 蛮力算法 思想:从序列首元素开始穷举所有可能的序列。 代码示例...
  • 问题描述 使用如下sql,先在查询中进行order by排序,再对查询结果进行group by分组,但查到的结果并没有正确排序。 MySQL版本为5.7。 SELECT * FROM ( SELECT * FROM app_login_record ORDER BY ctime DESC ) ...
  • SVM从原始问题到对偶问题的转换及原因

    万次阅读 多人点赞 2018-10-13 13:34:59
    1、转化对偶问题 上篇博客中我们得到的目标函数: (1) 我们在优化时喜欢求最小值,将上式转化正等价的求最小值如下:  (2) 对于(2)式,这是一个凸二次规划问题,我们可以使用拉格朗日乘数法进行优化。 ...
  • hebernate,JPA select 查询语句问题

    万次阅读 2017-01-06 16:34:22
    hebernate select 查询语句的问题 表class 字段名 类型 描述 id int 班级id name varchar(30) 名称 表student 字段名 类型 描述 id int 学生id name varchar(30) 学生...
  • 材料配送问题 1.建立模型 1.1问题描述 有一个材料供应商,从工厂出发,用一辆货车为若干个下游工厂配送材料且只配送一次,最后仍回到工厂,问应如何选择行车路线,使总耗油量最少。 模型的基本假设: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 425,356
精华内容 170,142
关键字:

原问题和子问题