3 ms·

What do you mean by a not full dimensional feasible region? Interior point methods can handle equality constraints just fine, so do you mean two inequality cons

by jules 12y ago

What do you mean by a not full dimensional feasible region? Interior point methods can handle equality constraints just fine, so do you mean two inequality constraints that conspire to be an equality? I think any method that uses inexact arithmetic will have trouble with that. The very nice feature of interior point methods is that they also work for non-linear optimization, which has far broader applicability. That's why in my opinion courses that teach simplex but not interior point are outdated. With interior point you simply get far more usefulness in fewer lectures, so if you have to make a choice, make it interior point.

wolfgke 12y ago
> so do you mean two inequality constraints that conspire to be an equality? Exactly. This can be solved by the described method (but there are probably better ones). > The very nice feature of interior point methods is that they also work for non-linear optimization, which has far broader applicability. I would not argue with broader applicability, if adding a constraint after finding an optimal solution requires a complete new fresh start (the dual simplex algorithm doesn't have this problem). This is very important for cutting plane algorithms for solving (mixed-)integer linear programs.
- jules 12y ago
  Interior point methods can benefit greatly from a hot restart too. You simply initialize it with the previous optimal point, and you start from there. For integer linear programming, sure, you should probably use simplex for solving the relaxation. I'm talking about continuous problems in engineering, statistics, machine learning, etcetera. Very few of those problems are linear, and you don't care at all about the corner case you described. That is a completely different world than combinatorial optimization. In continuous optimization if you have two or more inequality constraints that make the space lower dimensional that simply means that your problem statement is wrong, because the parameters are not exact, and with a small variation in the parameters your space will become empty.

by jules 12y ago

wolfgke 12y ago

> so do you mean two inequality constraints that conspire to be an equality? Exactly. This can be solved by the described method (but there are probably better ones). > The very nice feature of interior point methods is that they also work for non-linear optimization, which has far broader applicability. I would not argue with broader applicability, if adding a constraint after finding an optimal solution requires a complete new fresh start (the dual simplex algorithm doesn't have this problem). This is very important for cutting plane algorithms for solving (mixed-)integer linear programs.

jules 12y ago
Interior point methods can benefit greatly from a hot restart too. You simply initialize it with the previous optimal point, and you start from there. For integer linear programming, sure, you should probably use simplex for solving the relaxation. I'm talking about continuous problems in engineering, statistics, machine learning, etcetera. Very few of those problems are linear, and you don't care at all about the corner case you described. That is a completely different world than combinatorial optimization. In continuous optimization if you have two or more inequality constraints that make the space lower dimensional that simply means that your problem statement is wrong, because the parameters are not exact, and with a small variation in the parameters your space will become empty.