“内点法”的实现解决LP（和QP）
我想了解一些 IPM 的实现。优选的语言是 C/C++、Java 或任何脚本语言，如 python、perl。其他也都还好。
我正在寻找一个可以帮助我了解
- 优化技术基础知识、
- 内点法基础知识及其与其他技术的基础差异、
- IPM 类型、
- 算法细节和
- 示例实现的良好资源。
我对此很感兴趣，作为我项目的一部分，我将使用这些想法/逻辑来求解线性或二次方程组。
如果您有有关上述资源的任何信息，请告诉我。
I would like to look at a couple of implementations of IPMs. The languages preferable are C/C++, Java or any scripting languages like python, perl. Others are also fine.
I am searching for a good resource which can help me with,
- basics of optimization techniques,
- basics of Interior Point Method and its basics differences with the other techniques,
- types of IPMs,
- algorithmic details, and
- sample implementations.
I am interested in this as part of my project where I would be using these ideas/logic to solve a sys of linear or quadratic equations.
Let me know if you have any info about the above resources.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
另一个开源内点线性规划求解器是用 C 编写的 GLPK：
http://www.gnu.org/software/glpk/
和
http://en.wikibooks.org/wiki/GLPK
Bob Vanderbei 的线性规划书籍 ( http://www.princeton.edu/~rvdb/LPbook/）是一本解释二次规划内点算法使用的好书。引用的网站也有软件链接，但它似乎不是“商业质量”软件。 Vanderbei 还拥有 LOQO，这是一种更具工业强度的二次规划内点代码 (http://www.princeton.edu/~rvdb/ps/loqo5.pdf)。内点 qp 的另一个最新想法是： http://www-personal.umich .edu/~murty/Grav-QP.pdf
Another open source interior point linear programming solver is GLPK written in C:
http://www.gnu.org/software/glpk/
and
http://en.wikibooks.org/wiki/GLPK
The linear programming book by Bob Vanderbei (http://www.princeton.edu/~rvdb/LPbook/) is a good book for explaining the use of interior point algorithms for quadratic programming. The cited website also has links to software, but it doesn't seem to be "commercial quality" software. Vanderbei also has LOQO, a more industrial strength interior point code for quadratic programming (http://www.princeton.edu/~rvdb/ps/loqo5.pdf). Another recent idea in interior point qp is: http://www-personal.umich.edu/~murty/Grav-QP.pdf
单纯形法和内点法都有其用武之地。一个没有更好或更快
一般来说，你会发现每种方法在不同的情况下都表现得更好
类问题。
至于代码，开源Coin-OR项目Clp有Simplex，用 C++ 实现的对偶单纯形和内点方法。
但是，如果您只是想求解线性或二次方程组
形式 f(x) = 0，那么这根本不是你想要的。如果你想要的系统是
线性，那么您需要了解直接或迭代线性求解器。如果出现问题
是非线性的，您应该研究牛顿法或拟牛顿法。
祝你好运。
Simplex methods and interior point methods both have their place. One is not better or faster
than the other in general and you will find that each method performs better on different
classes of problems.
As for codes, the open source Coin-OR project, Clp has Simplex, Dual Simplex, and Interior Point methods implemented in C++.
However, if you are just looking to solve a system of linear or quadratic equations of
the form f(x) = 0, then this is not what you want at all. If the system you want is
linear, then you need to understand direct or iterative linear solvers. If the problem
is nonlinear, you should look into Newton's method or quasi-Newton methods.
best of luck.
首先，不要比较单纯形法和内点法。他们有不同的方法来解决问题。单纯形法用于最大化或最小化函数，内点法用于通过加或减来确定给定函数内满足具有δ（非常小的值）的集合函数的所有可能点。您可以在这里找到有关它们的详细信息
[1]: http://www-personal.umich.edu/~穆蒂/Grav-QP.pdf
First of all, don't compare the simplex method and the interior point method. They have different approaches to solve the problem. The simplex method is used to maximize or minimize the function and the interior point method is used to determine all possible points within the given function which satisfies the set function with delta(very small value) by adding or subtracting it. You can find detailed information regarding them here
[1]: http://www-personal.umich.edu/~murty/Grav-QP.pdf