约束最优化方法 (二) Zoutendijk容许方向法

作者: 小小何先生 | 来源:发表于2019-12-07 09:26 被阅读0次

约束最优化方法 (二) Zoutendijk容许方向法
无约束优化方法-一阶导数（最速下降法）
【转】约束优化方法之拉格朗日乘子法与KKT条件
拉格朗日乘子与KKT条件(转载)
Newton's method and Quasi Ne
数组去重的方法有哪些？
约束优化方法
无约束最优化(二) 共轭方向法与共轭梯度法
[机器学习必知必会]牛顿法与拟牛顿法
04 最优化方法

算法：(Zoutendijk法)

已知目标函数 $f(x)$ 及其梯度 $\nabla f(x)$ ，不等式约束中的矩阵 $A$ 和向量 $b$ ，等式约束中的矩阵 $C$ 和向量 $d$ ，终止限 $\varepsilon$ 。

选定初始容许点 $x_{0}$ ；置 $k=0$ 。
把 $A$ 分解为 $A_{k}^{'}$ 和 $A_{k}^{''}$ ，相应地把 $b$ 分解为 $b_{k}^{'}$ 和 $b_{k}^{''}$ ，使得 $A_{k}^{'}x_{k}=b^{'}$ ， $A_{k}^{''}x_{k}^{''} \geq b_{k}^{''}$ 。设 $b_{k}^{''}$ 的维数为 $\tau$ 。
求解线性规划问题：
$min_{p} \ \nabla f(x_{k})^{T}p \\ s.t. \ \ A_{k}^{'}p \geq 0 \\ Cp =0 \\ -e \leq p \leq e$
设其最优解为 $p_{k}$ 。
若 $|\nabla f(x_{k})^{T}p_{k}| < \varepsilon$ ，则打印 $x_{k}$ ，停机；否则，计算 $u=A_{k}^{''}x_{k}-b_{k}^{''}$ ， $v=A_{k}^{''}p_{k}$ 。
若 $p \geq 0$ ，则作直线搜索 $x_{k+1}=1s(x_{k}，p_{k})$ ；否则，计算
$\overline{t}=min_{1 \leq i \leq \varepsilon} \{ -\frac{u_{i}}{v_{i}}| v_{i} < 0 \}$
并求解：
$min_{t}f(x_{k}+tp_{k}); \\ s.t. \ \ 0 \leq t \leq \overline{t}$
设其最优解为 $t_{k}$ ；计算 $x_{x+1}=x_{k}+t_{k}p_{k}$ 。
置 $k=k+1$ ，转2。

我的微信公众号名称：深度学习与先进智能决策
微信公众号ID：MultiAgent1024
公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！

约束最优化方法 (二) Zoutendijk容许方向法
算法：(Zoutendijk法) 已知目标函数及其梯度，不等式约束中的矩阵和向量，等式约束中的矩阵和向量，终止限。...
无约束优化方法-一阶导数（最速下降法）
利用导数信息的方法皆为间接方法。在无约束优化法最开始介绍时，提到迭代形式的优化方法关键步骤是确定搜索方向和步长。间...
【转】约束优化方法之拉格朗日乘子法与KKT条件
约束优化方法之拉格朗日乘子法与KKT条件引言本篇文章将详解带有约束条件的最优化问题，约束条件分为等式约束与不等...
拉格朗日乘子与KKT条件(转载)
拉格朗日乘子法和KKT（Karush-Kuhn-Tucker）条件是求解约束优化问题的重要方法，再有等式约束时使用...
Newton's method and Quasi Ne
Welcome To My Blog 牛顿法和拟牛顿法是求解无约束最优化问题的常用方法,优点是收敛速度快.牛顿法...
数组去重的方法有哪些？
一：最简单的方法二、对象键值法去重三、排序后相邻去除法四、数组下标法五、优化遍历数组法本文参考：[htt...
约束优化方法
在机器学习中，常常需要对损失函数进行优化，但是我们可能希望在给定的集合中来搜索函数的最大值或者最小值，这就是约束优...
无约束最优化(二) 共轭方向法与共轭梯度法
基本思想之前文章最速下降法、Newton法、修正Newton法介绍的最速下降法存在锯齿现象，Newton法需...
[机器学习必知必会]牛顿法与拟牛顿法
前言同梯度下降法一样，牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法。牛顿法本身属于迭代算法，每一步需要求解...
04 最优化方法
推荐书籍：《最优化方法》李元科基本概念：目标函数无约束优化约束优化迭代下降法 1）图解法： 2）迭...