对于大量约束和“热启动"，我应该使用哪个线性编程包. [英] Which linear programming package should I use for high numbers of constraints and "warm starts"
问题描述
我也想知道答案在细微扰动下如何解决基本问题.因此，我希望能够基于附近的解决方案向求解器提供初始条件.我相信这种功能被称为热启动".
有人可以帮助我区分各种LP软件包吗?我不太关心用户友好性，例如速度(对于大量约束)，高精度算术和热启动.
谢谢！
从到目前为止与问题解答者的对话来看，我应该更加清楚自己要解决的问题.简化的版本如下:
我有单个实变量y的N个固定函数f_i(y).我想找到x_i(i = 1，...，N)，它将\ sum_ {i = 1} ^ N x_i f_i(0)最小化，这取决于约束条件:
- \ sum_ {i = 1} ^ N x_i f_i(1)= 1，并且 对于所有y> 2，
- \ sum_ {i = 1} ^ N x_i f_i(y)> = 0
更简洁地说，如果我们定义函数F(y)= \ sum_ {i = 1} ^ N x_i f_i(y)，那么我想在F(1)= 1，并且F(y)在整个间隔[2，infinity)上为正.请注意，这后一个阳性条件实际上是x_i上线性约束的无限个，每个y约束.您可以将y视为标签-它不是优化变量.特定的y_0将我限制为x_i的空间的半角空间F(y_0)> = 0.当我在2和无穷大之间改变y_0时，这些半空间会连续变化，从而雕刻出弯曲的凸形.这种形状的几何形状隐含地(复杂地)取决于函数f_i.
-
对于LP解算器建议，最好的两个是Gurobi和CPLEX(用谷歌搜索).它们对于学术用户是免费的，并且能够解决大规模问题.我相信它们具有您需要的所有功能.您可以从影子价格(即拉格朗日乘数)中获得敏感度信息(对扰动).
-
但是我对您的原始问题更感兴趣.据我了解，它看起来像这样:
让S = {1,2，...，N}，其中N是函数总数. y是一个标量. f_ {i}:R ^ {1}-> R ^ {1}.
minimize sum{i in S} (x_{i} * f_{i}(0))
x_{i}
s.t.
(1) sum {i in S} x_{i} * f_{i}(1) = 1
(2) sum {i in S} x_{i} * f_{i}(y) >= 0 for all y in (2,inf]
-
在我看来，您可能想尝试以凸NLP而非LP解决此问题.像IPOPT这样的大型内部点NLP求解器应该能够轻松处理这些问题.我强烈建议尝试IPOPT http://www.coin-or.org/Ipopt
-
从数值的角度来看:对于凸问题，使用内点求解器无需热启动；而且您不必担心活动集的组合循环.您所说的热启动"实际上是在干扰解决方案，这更类似于敏感性分析.用优化的话来说，热启动通常意味着向求解器提供初始猜测-求解器将采用该猜测并最终得到相同的解决方案，而这并不是您真正想要的.唯一的例外是，如果活动集的更改具有不同的初始猜测-但是对于具有唯一最优值的凸问题，则不会发生这种情况.
如果您需要更多信息，我很乐意提供.
很抱歉使用非标准符号-我希望我可以像在MathOverflow.net上一样输入LaTeX. (顺便说一句，您可以尝试在此处发布它-我认为那里的数学家会对这个问题感兴趣)
现在我看到有关"y> 2"的信息.实际上，它并不是一个优化约束，而只是一个定义空间的间隔(我已经在上面编辑了我的描述).我的错.我想知道您是否可以通过某种方式将问题从无穷大转化为有限无穷大?我现在什么都想不起来，但我只是想知道是否有可能.
所以您的方法是将(2，inf]中的y离散化.我猜您正在选择一个很大的数字来表示inf和一个精细的离散化网格.最好的选择.也许进行真正分析的人都有想法.
对于涉及Lyapunov函数的问题，我已经看到了类似的处理方法，在这些函数中，必须在凸包内的每个点上强制执行属性.但是那个空间是有限的.
I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the convex space is piecewise curved -- that is, it has faces, edges, and vertices, but the edges aren't straight and the faces aren't flat. Instead of being specified by a finite number of linear inequalities, I have a continuously infinite number. I'm currently dealing with this by approximating the surface by a polytope, which means discretizing the continuously infinite constraints into a very large finite number of constraints.
I'm also in the situation where I'd like to know how the answer changes under small perturbations to the underlying problem. Thus, I'd like to be able to supply an initial condition to the solver based on a nearby solution. I believe this capability is called a "warm start."
Can someone help me distinguish between the various LP packages out there? I'm not so concerned with user-friendliness as speed (for large numbers of constraints), high-precision arithmetic, and warm starts.
Thanks!
EDIT: Judging from the conversation with question answerers so far, I should be clearer about the problem I'm trying to solve. A simplified version is the following:
I have N fixed functions f_i(y) of a single real variable y. I want to find x_i (i=1,...,N) that minimize \sum_{i=1}^N x_i f_i(0), subject to the constraints:
- \sum_{i=1}^N x_i f_i(1) = 1, and
- \sum_{i=1}^N x_i f_i(y) >= 0 for all y>2
More succinctly, if we define the function F(y)=\sum_{i=1}^N x_i f_i(y), then I want to minimize F(0) subject to the condition that F(1)=1, and F(y) is positive on the entire interval [2,infinity). Note that this latter positivity condition is really an infinite number of linear constraints on the x_i's, one for each y. You can think of y as a label -- it is not an optimization variable. A specific y_0 restricts me to the half-space F(y_0) >= 0 in the space of x_i's. As I vary y_0 between 2 and infinity, these half-spaces change continuously, carving out a curved convex shape. The geometry of this shape depends implicitly (and in a complicated way) on the functions f_i.
As for LP solver recommendations, two of the best are Gurobi and CPLEX (google them). They are free for academic users, and are capable of solving large-scale problems. I believe they have all the capabilities that you need. You can get sensitivity information (to a perturbation) from the shadow prices (i.e. the Lagrange multipliers).
But I'm more interested in your original problem. As I understand it, it looks like this:
Let S = {1,2,...,N} where N is the total number of functions. y is a scalar. f_{i}:R^{1} -> R^{1}.
minimize sum{i in S} (x_{i} * f_{i}(0))
x_{i}
s.t.
(1) sum {i in S} x_{i} * f_{i}(1) = 1
(2) sum {i in S} x_{i} * f_{i}(y) >= 0 for all y in (2,inf]
It just seems to me that you might want to try solve this problem as an convex NLP rather than an LP. Large-scale interior point NLP solvers like IPOPT should be able to handle these problems easily. I strongly recommended trying IPOPT http://www.coin-or.org/Ipopt
From a numerical point of view: for convex problems, warm-starting is not necessary with interior point solvers; and you don't have to worry about the combinatorial cycling of active sets. What you've described as "warm-starting" is actually perturbing the solution -- that's more akin to sensitivity analysis. In optimization parlance, warm-starting usually means supplying a solver with an initial guess -- the solver will take that guess and end up at the same solution, which isn't really what you want. The only exception is if the active set changes with a different initial guess -- but for a convex problem with a unique optimum, this cannot happen.
If you need any more information, I'd be pleased to supply it.
EDIT:
Sorry about the non-standard notation -- I wish I could type in LaTeX like on MathOverflow.net. (Incidentally, you might try posting this there -- I think the mathematicians there would be interested in this problem)
Ah now I see about the "y > 2". It isn't really an optimization constraint so much as an interval defining a space (I've edited my description above). My mistake. I'm wondering if you could somehow transform/project the problem from an infinite to a finite one? I can't think of anything right now, but I'm just wondering if that's possible.
So your approach is to discretize the problem for y in (2,inf]. I'm guessing you're choosing a very big number to represent inf and a fine discretization grid. Oooo tricky. I suppose discretization is probably your best bet. Maybe guys who do real analysis have ideas.
I've seen something similar being done for problems involving Lyapunov functions where it was necessary to enforce a property in every point within a convex hull. But that space was finite.
这篇关于对于大量约束和“热启动"，我应该使用哪个线性编程包.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
