11.最优化方法-等式约束优化.pdf

最优化⽅法 东南⼤学 计算机&⼈⼯智能学院 宋沫飞 songmf@seu.edu.cn 1 等式约束优化 ❑ 等式约束优化问题 ❑ 消去等式约束 ❑ 带有等式约束的Newton⽅法 ❑ 不可⾏初始点的Newton⽅法 ❑ 实现 2 等式约束优化问题 3 等式约束优化问题 3 等式约束优化问题 ❑ 函数f为凸函数，⼆次连续可微 3 等式约束优化问题 ❑ 函数f为凸函数，⼆次连续可微 ❑ A ∈ R p×n，秩rank A = p 3 等式约束优化问题 ❑ 函数f为凸函数，⼆次连续可微 ❑ A ∈ R p×n，秩rank A = p ❑ 假设最优值p*有限且存在 3 等式约束优化问题 ❑ 函数f为凸函数，⼆次连续可微 ❑ A ∈ R p×n，秩rank A = p ❑ 假设最优值p*有限且存在 ❑ 最优条件：x*为最优解，当且仅当存在v*满⾜ 3 等式约束优化问题 ❑ 函数f为凸函数，⼆次连续可微 ❑ A ∈ R p×n，秩rank A = p ❑ 假设最优值p*有限且存在 ❑ 最优条件：x*为最优解，当且仅当存在v*满⾜ 3 等式约束凸⼆次规划 4 等式约束凸⼆次规划 4 等式约束凸⼆次规划 ❑ 最优化条件： 4 等式约束凸⼆次规划 ❑ 最优化条件： 4 等式约束凸⼆次规划 ❑ 最优化条件： ❑ 系数矩阵成为KKT矩阵 4 等式约束凸⼆次规划 ❑ 最优化条件： ❑ 系数矩阵成为KKT矩阵 ❑ KKT矩阵为⾮奇异，当且仅当 4 等式约束凸⼆次规划 ❑ 最优化条件： ❑ 系数矩阵成为KKT矩阵 ❑ KKT矩阵为⾮奇异，当且仅当 4 等式约束凸⼆次规划 ❑ 最优化条件： ❑ 系数矩阵成为KKT矩阵 ❑ KKT矩阵为⾮奇异，当且仅当 ❑ ⾮奇异的等价条件： 4 等式约束凸⼆次规划 ❑ 最优化条件： ❑ 系数矩阵成为KKT矩阵 ❑ KKT矩阵为⾮奇异，当且仅当 ❑ ⾮奇异的等价条件： 4 消除等式约束 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 ❑ x为任意⼀特定解 ̂ 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 ❑ x为任意⼀特定解 ̂ ❑ F ∈ R n×(n−p)的值域为矩阵A的零空间 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 ❑ x为任意⼀特定解 ̂ ❑ F ∈ R n×(n−p)的值域为矩阵A的零空间 ❑ rank F = n − p且AF = 0 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 ❑ x为任意⼀特定解 ̂ ❑ F ∈ R n×(n−p)的值域为矩阵A的零空间 ❑ rank F = n − p且AF = 0 ❑ 消去约束后的问题 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 ❑ x为任意⼀特定解 ̂ ❑ F ∈ R n×(n−p)的值域为矩阵A的零空间 ❑ rank F = n − p且AF = 0 ❑ 消去约束后的问题 ❑ 为⽆约束问题，其优化变量为 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 ❑ x为任意⼀特定解 ̂ ❑ F ∈ R n×(n−p)的值域为矩阵A的零空间 ❑ rank F = n − p且AF = 0 ❑ 消去约束后的问题 ❑ 为⽆约束问题，其优化变量为 ❑ 根据解z*，可获取x*和 v* 5 消除等式约束 ❑ 将{x | Ax = b}的求解表⽰为 ❑ x为任意⼀特定解 ̂ ❑ F ∈ R n×(n−p)的值域为矩阵A的零空间 ❑ rank F = n − p且AF = 0 ❑ 消去约束后的问题 ❑ 为⽆约束问题，其优化变量为 ❑ 根据解z*，可获取x*和 v* 5 例：受资源约束的最优配置 6 例：受资源约束的最优配置 6 例：受资源约束的最优配置 ❑ 消去 ，指选择 6 例：受资源约束的最优配置 ❑ 消去 ，指选择 6 例：受资源约束的最优配置 ❑ 消去 ，指选择 ❑ 消去后的问题 6 例：受资源约束的最优配置 ❑ 消去 ，指选择 ❑ 消去后的问题 6 Newton⽅向 7 Newton⽅向 ❑ 函数f在可⾏点x的Newton⽅向 由解v给出 7 Newton⽅向 ❑ 函数f在可⾏点x的Newton⽅向 由解v给出 7 Newton⽅向 ❑ 函数f在可⾏点x的Newton⽅向 ❑ 由解v给出 解决了⼆阶近似问题（优化变量为v） 7 Newton⽅向 ❑ 函数f在可⾏点x的Newton⽅向 ❑ 由解v给出 解决了⼆阶近似问题（优化变量为v） 7 Newton⽅向 ❑ 函数f在可⾏点x的Newton⽅向 由解v给出 ❑ 解决了⼆阶近似问题（优化变量为v） ❑ 等式来源于线性化最优条件 7 Newton⽅向 ❑ 函数f在可⾏点x的Newton⽅向 由解v给出 ❑ 解决了⼆阶近似问题（优化变量为v） ❑ 等式来源于线性化最优条件 7 Newton减量 8 Newton减量 8 Newton减量 ❑ 给出了 的⼀个估计，使⽤了⼆次近似： 8 Newton减量 ❑ 给出了 的⼀个估计，使⽤了⼆次近似： 8 Newton减量 ❑ 给出了 的⼀个估计，使⽤了⼆次近似： ❑ Newton⽅向的⽅向导数： 8 Newton减量 ❑ 给出了 的⼀个估计，使⽤了⼆次近似： ❑ Newton⽅向的⽅向导数： 8 Newton减量 ❑ 给出了 的⼀个估计，使⽤了⼆次近似： ❑ Newton⽅向的⽅向导数： ❑ ⼀般的， 8 带有等式约束的Newton⽅法 9 带有等式约束的Newton⽅法 9 带有等式约束的Newton⽅法 ❑ 可⾏的下降⽅法： ❑ 仿射不变性 可⾏且 9 Newton⽅法和消除法 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 ❑ 优化变量 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 ❑ 优化变量 ❑ 满⾜ 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 ❑ 优化变量 ❑ 满⾜ ❑ 对函数执⾏Newton⽅法，起始点为 ，进⾏迭代 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 ❑ 优化变量 ❑ 满⾜ ❑ 对函数执⾏Newton⽅法，起始点为 ，进⾏迭代 ❑ 带有等式约束的Newton⽅法 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 ❑ 优化变量 ❑ 满⾜ ❑ 对函数执⾏Newton⽅法，起始点为 ，进⾏迭代 ❑ 带有等式约束的Newton⽅法 ❑ 当起始点为 时，迭代为 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 ❑ 优化变量 ❑ 满⾜ ❑ 对函数执⾏Newton⽅法，起始点为 ，进⾏迭代 ❑ 带有等式约束的Newton⽅法 ❑ 当起始点为 时，迭代为 10 Newton⽅法和消除法 ❑ ⾯向简化问题的Newton⽅法 ❑ 优化变量 ❑ 满⾜ ❑ 对函数执⾏Newton⽅法，起始点为 ，进⾏迭代 ❑ 带有等式约束的Newton⽅法 ❑ 当起始点为 时，迭代为 ❑ 因此，不需要分离的收敛分析 10 不可⾏初始点的Newton⽅法 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 ❑ 原对偶Newton⽅向的解释 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 ❑ 原对偶Newton⽅向的解释 ❑ 最优条件为 ，其中 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 ❑ 原对偶Newton⽅向的解释 ❑ 最优条件为 ，其中 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 ❑ 原对偶Newton⽅向的解释 ❑ 最优条件为 ❑ 线性化 ，其中 可得 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 ❑ 原对偶Newton⽅向的解释 ❑ 最优条件为 ❑ 线性化 ，其中 可得 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 ❑ 原对偶Newton⽅向的解释 ❑ 最优条件为 ❑ 线性化 ，其中 可得 11 不可⾏初始点的Newton⽅法 ❑ 在不可⾏点x线性化最优条件 ❑ 原对偶Newton⽅向的解释 ❑ 最优条件为 ❑ 线性化 ，其中 可得 11 不可⾏初始点Newton⽅法 12 不可⾏初始点Newton⽅法 12 不可⾏初始点Newton⽅法 ❑ 不是下降法：可能存在 12 不可⾏初始点Newton⽅法 ❑ 不是下降法：可能存在 ❑ 的有向导数在⽅向上 为 12 求解KKT系统 13 求解KKT系统 13 求解KKT系统 ❑ 求解⽅法 13 求解KKT系统 ❑ 求解⽅法 ❑ LDLT因式分解 13 求解KKT系统 ❑ 求解⽅法 ❑ LDLT因式分解 ❑ 消去（若H⾮奇异）： 13 求解KKT系统 ❑ 求解⽅法 ❑ LDLT因式分解 ❑ 消去（若H⾮奇异）： 13 求解KKT系统 ❑ 求解⽅法 ❑ LDLT因式分解 ❑ 消去（若H⾮奇异）： ❑ 消去奇异矩阵H： 13 求解KKT系统 ❑ 求解⽅法 ❑ LDLT因式分解 ❑ 消去（若H⾮奇异）： ❑ 消去奇异矩阵H： 13 求解KKT系统 ❑ 求解⽅法 ❑ LDLT因式分解 ❑ 消去（若H⾮奇异）： ❑ 消去奇异矩阵H： ❑ 其中， ，满⾜ 13 等式约束的解析中⼼ 14 等式约束的解析中⼼ ❑ 原问题： 14 等式约束的解析中⼼ ❑ 原问题： ❑ 对偶问题： 14 等式约束的解析中⼼ ❑ 原问题： ❑ 对偶问题： ❑ 使⽤三种⽅法求解 同起始点 中的例⼦，三个不 14 等式约束的解析中⼼ ❑ 原问题： ❑ 对偶问题： ❑ 使⽤三种⽅法求解 中的例⼦，三个不 同起始点 ❑ 带有等式约束的Newton⽅法，需. ） 14 等式约束的解析中⼼ ❑ 原问题： ❑ 对偶问题： ❑ 使⽤三种⽅法求解 中的例⼦，三个不 同起始点 ❑ 带有等式约束的Newton⽅法，需. ） 14 其他两个⽅法 15 其他两个⽅法 ❑ Newton⽅法应⽤于对偶问题，需 15 其他两个⽅法 ❑ Newton⽅法应⽤于对偶问题，需 15 其他两个⽅法 ❑ Newton⽅法应⽤于对偶问题，需 ❑ 不可⾏初始点的Newton⽅法，需 15 其他两个⽅法 ❑ Newton⽅法应⽤于对偶问题，需 ❑ 不可⾏初始点的Newton⽅法，需 15 三个⽅法每次迭代的复杂度 16 三个⽅法每次迭代的复杂度 ❑ 使⽤分块消元求解KKT系统 16 三个⽅法每次迭代的复杂度 ❑ 使⽤分块消元求解KKT系统 16 三个⽅法每次迭代的复杂度 ❑ 使⽤分块消元求解KKT系统 ❑ 简化为求解 16 三个⽅法每次迭代的复杂度 ❑ 使⽤分块消元求解KKT系统 ❑ 简化为求解 ❑ 求解Newton系统 16 三个⽅法每次迭代的复杂度 ❑ 使⽤分块消元求解KKT系统 ❑ 简化为求解 ❑ 求解Newton系统 ❑ 使⽤分块消元求解KKT系统 16 三个⽅法每次迭代的复杂度 ❑ 使⽤分块消元求解KKT系统 ❑ 简化为求解 ❑ 求解Newton系统 ❑ 使⽤分块消元求解KKT系统 16 三个⽅法每次迭代的复杂度 ❑ 使⽤分块消元求解KKT系统 ❑ 简化为求解 ❑ 求解Newton系统 ❑ 使⽤分块消元求解KKT系统 ❑ 简化为求解 16 三个⽅法每次迭代的复杂度 ❑ 使⽤分块消元求解KKT系统 ❑ 简化为求解 ❑ 求解Newton系统 ❑ 使⽤分块消元求解KKT系统 ❑ 简化为求解 ❑ 结论：求解带有正对⾓矩阵D的 16 最优⽹络流 最优⽹络流 最优⽹络流 ❑ 有向图带有n条边和p+1个结点 最优⽹络流 ❑ 有向图带有n条边和p+1个结点 ❑ xi：通过边i的流量； 边i的流程成本函数（ ） 最优⽹络流 ❑ 有向图带有n条边和p+1个结点 ❑ xi：通过边i的流量； ❑ 结点进⼊矩阵 边i的流程成本函数（ ） 最优⽹络流 ❑ 有向图带有n条边和p+1个结点 ❑ xi：通过边i的流量； ❑ 结点进⼊矩阵 边i的流程成本函数（ ） 最优⽹络流 ❑ 有向图带有n条边和p+1个结点 ❑ xi：通过边i的流量； 边i的流程成本函数（ ❑ 结点进⼊矩阵 ❑ 简化结点进⼊矩阵 ，去除最后⼀⾏的 ） 最优⽹络流 ❑ 有向图带有n条边和p+1个结点 ❑ xi：通过边i的流量； 边i的流程成本函数（ ❑ 结点进⼊矩阵 ❑ 简化结点进⼊矩阵 ❑ （简化的）资源向量 ，去除最后⼀⾏的 ） 最优⽹络流 ❑ 有向图带有n条边和p+1个结点 ❑ xi：通过边i的流量； 边i的流程成本函数（ ❑ 结点进⼊矩阵 ❑ 简化结点进⼊矩阵 ❑ （简化的）资源向量 ❑ 若图是连接的， ，去除最后⼀⾏的 ） 最优⽹络流 ❑ 有向图带有n条边和p+1个结点 ❑ xi：通过边i的流量； 边i的流程成本函数（ ） ❑ 结点进⼊矩阵 ❑ 简化结点进⼊矩阵 ❑ （简化的）资源向量 ❑ 若图是连接的， ，去除最后⼀⾏的 17 最优控制 18 最优控制 ❑ KKT系统 18 最优控制 ❑ KKT系统 ❑ ，正对⾓矩阵 18 最优控制 ❑ KKT系统 ❑ ❑ 通过消元法求解： ，正对⾓矩阵 18 最优控制 ❑ KKT系统 ❑ ❑ 通过消元法求解： ，正对⾓矩阵 18 最优控制 ❑ KKT系统 ❑ ❑ 通过消元法求解： ，正对⾓矩阵 ❑ 系数矩阵的稀疏模式通过图的连接性获取 18 最优控制 ❑ KKT系统 ❑ ❑ 通过消元法求解： ，正对⾓矩阵 ❑ 系数矩阵的稀疏模式通过图的连接性获取 结点i和j存在边连接 18 线性矩阵不等式的解析中⼼ 19 线性矩阵不等式的解析中⼼ 19 线性矩阵不等式的解析中⼼ ❑ 优化变量 19 线性矩阵不等式的解析中⼼ ❑ 优化变量 ❑ 优化条件 19 线性矩阵不等式的解析中⼼ ❑ 优化变量 ❑ 优化条件 19 线性矩阵不等式的解析中⼼ ❑ 优化变量 ❑ 优化条件 ❑ 在可⾏点X的Newton等式 19 线性矩阵不等式的解析中⼼ ❑ 优化变量 ❑ 优化条件 ❑ 在可⾏点X的Newton等式 19 线性矩阵不等式的解析中⼼ ❑ 优化变量 ❑ 优化条件 ❑ 在可⾏点X的Newton等式 ❑ 根据线性近似 得到 个变量 19 分块消元求解 20 分块消元求解 ❑ 从第⼀个⽅程中消去 ： 20 分块消元求解 ❑ 从第⼀个⽅程中消去 ： ❑将 带⼊第⼆个⽅程 20 分块消元求解 ❑ 从第⼀个⽅程中消去 ： ❑将 带⼊第⼆个⽅程 20 分块消元求解 ❑ 从第⼀个⽅程中消去 ： ❑将 带⼊第⼆个⽅程 ❑ 为⼀个密集正定的线性⽅程组，变量为 20 分块消元求解 ❑ 从第⼀个⽅程中消去 ： ❑将 带⼊第⼆个⽅程 ❑ 为⼀个密集正定的线性⽅程组，变量为 ❑ 使⽤Cholesky因式分解X=LLT的浮点运算次数： 20 分块消元求解 ❑ 从第⼀个⽅程中消去 ： ❑将 带⼊第⼆个⽅程 ❑ 为⼀个密集正定的线性⽅程组，变量为 ❑ 使⽤Cholesky因式分解X=LLT的浮点运算次数： ❑ 计算p个乘积 20 分块消元求解 ❑ 从第⼀个⽅程中消去 ： ❑将 带⼊第⼆个⽅程 ❑ 为⼀个密集正定的线性⽅程组，变量为 ❑ 使⽤Cholesky因式分解X=LLT的浮点运算次数： ❑ 计算p个乘积 ❑ 计算 个内积： 20 分块消元求解 ❑ 从第⼀个⽅程中消去 ： ❑将 带⼊第⼆个⽅程 ❑ 为⼀个密集正定的线性⽅程组，变量为 ❑ 使⽤Cholesky因式分解X=LLT的浮点运算次数： ❑ 计算p个乘积 ❑ 计算 个内积： ❑ 通过Cholesky因式分解求解： 20