约束二次函数的原始对偶算法中是否有更简单的提前终止条件
is there a simpler, early termination condition in primal dual algorithm for constrained quadratic function
目前，我正在使用原始对偶方法来最小化具有简单线性约束（具体而言，x >= 0）的二次问题。对于终止条件，我目前使用的标准是：即error "e" term must be less than a threshold value.
但是，计算 "e" 项相对昂贵，因为我需要计算完整的二次函数。是否可以有一个 simpler/faster 终止条件，例如以下之一：
1）如果x的所有变化之和低于某个阈值，则终止；或者，
2) 如果 x 的最大变化低于某个阈值，则终止？
直觉上，这对我来说很有意义，但我发现我的直觉有一半是错误的这些最小化问题，所以我不确定我的直觉在理论上是否合理....
练习一：
For the termination condition, I'm currently using the standard: ie error "e" term must be less than a threshold value. 你不是假设 objective 可以在这里被推到 0 吗？您如何先验确定此阈值？
关于理论：
1) if the sum of all the changes in x is below a certain threshold, then terminate
- 这是一种启发式方法（采用外部绝对值可能是个好主意）我想我在其他代码中看到过类似的东西）
- 它没有理论上的保证；不充分，但必要条件
2) if the max change in x is below a certain threshold, then terminate
- 经常使用的启发式
- 再次：没有理论上的保证；不充分，但必要条件
您应该查看 Karush–Kuhn–Tucker conditions（解的一阶必要条件）
- 您需要的 KKT 条件类型取决于您的问题：凸面与非凸面 -> Q psd or not (edit 根据你的标签，你的似乎是凸的！）
- Interesting read with special-treatment of your problem
备注：你的问题是box-constrained QP，其实比inequality-constrained QP简单！ 这很重要！
- 为什么重要？：因为预计的无约束优化方法也会起作用，而且无约束优化更容易实现。另外，在这种情况下很重要：与计算 objective 相比，您的投影似乎便宜（在您的情况下投影是线性的）！
- 查看pages 8- 11
现在这可能会影响一些繁重的理论工作，然后是一些实施。考虑使用已有的工具！
练习二：
查看框约束 QP 求解器（凸或非凸；取决于您的问题）。这些应该是可用的并且会为您省去麻烦！
你甚至可以使用几乎无处不在的 LBFGS-B 如果你给它梯度（反对数值微分），它可能已经很难被击败。虽然它更通用，但它通常非常强大！ （在python，使用scipy，使用这个会少几行）
L-BFGS-B is a limited-memory quasi-Newton code for bound-constrained optimization, i.e. for problems where the only constraints are of the form l<= x <= u.
可能还有其他已经可用的替代品。 Trust Region Reflective and co.
（旁注：我想知道与原始对偶（IPM？）算法中的其他操作相比，评估成本如何如此昂贵，正如您所描述的那样）
目前，我正在使用原始对偶方法来最小化具有简单线性约束（具体而言，x >= 0）的二次问题。对于终止条件，我目前使用的标准是：即error "e" term must be less than a threshold value.
但是，计算 "e" 项相对昂贵，因为我需要计算完整的二次函数。是否可以有一个 simpler/faster 终止条件，例如以下之一：
1）如果x的所有变化之和低于某个阈值，则终止；或者， 2) 如果 x 的最大变化低于某个阈值，则终止？
直觉上，这对我来说很有意义，但我发现我的直觉有一半是错误的这些最小化问题，所以我不确定我的直觉在理论上是否合理....
练习一：
For the termination condition, I'm currently using the standard: ie error "e" term must be less than a threshold value. 你不是假设 objective 可以在这里被推到 0 吗？您如何先验确定此阈值？
关于理论：
1) if the sum of all the changes in x is below a certain threshold, then terminate- 这是一种启发式方法（采用外部绝对值可能是个好主意）我想我在其他代码中看到过类似的东西）
- 它没有理论上的保证；不充分，但必要条件
2) if the max change in x is below a certain threshold, then terminate- 经常使用的启发式
- 再次：没有理论上的保证；不充分，但必要条件
您应该查看 Karush–Kuhn–Tucker conditions（解的一阶必要条件）
- 您需要的 KKT 条件类型取决于您的问题：凸面与非凸面 -> Q psd or not (edit 根据你的标签，你的似乎是凸的！）
- Interesting read with special-treatment of your problem
备注：你的问题是box-constrained QP，其实比inequality-constrained QP简单！ 这很重要！
- 为什么重要？：因为预计的无约束优化方法也会起作用，而且无约束优化更容易实现。另外，在这种情况下很重要：与计算 objective 相比，您的投影似乎便宜（在您的情况下投影是线性的）！
- 查看pages 8- 11
现在这可能会影响一些繁重的理论工作，然后是一些实施。考虑使用已有的工具！
练习二：
查看框约束 QP 求解器（凸或非凸；取决于您的问题）。这些应该是可用的并且会为您省去麻烦！
你甚至可以使用几乎无处不在的 LBFGS-B 如果你给它梯度（反对数值微分），它可能已经很难被击败。虽然它更通用，但它通常非常强大！ （在python，使用scipy，使用这个会少几行）
L-BFGS-B is a limited-memory quasi-Newton code for bound-constrained optimization, i.e. for problems where the only constraints are of the form l<= x <= u.
可能还有其他已经可用的替代品。 Trust Region Reflective and co.
（旁注：我想知道与原始对偶（IPM？）算法中的其他操作相比，评估成本如何如此昂贵，正如您所描述的那样）