Questions tagged [interior-point-method]
For questions related to the Interior Point Method for linear programming (LP), which solves LPs optimally by traversing the interior of the feasible region.
15
questions
3
votes
1
answer
62
views
What approximation is guarantees when solving an LP with floating-point numbers?
Given a linear program
$$\begin{align}
\text{maximize} \quad & c^{T}x \\
\text{s.t.} \quad & A x \leq b
\end{align}
$$
I can solve it exactly in polynomial time, using e.g. interior-point ...
0
votes
0
answers
45
views
Solving convex separable programming problem using interior point method?
In my engineering application, all decision variables are non-negative and everything is convex separable. In addition to that, the only function that I am trying to approximate with grid point are $f(...
2
votes
0
answers
100
views
Cycling in Ipopt
I am running a QCQP model in the following setup
AMPL;
MUMPS 5.6.2; And
Ipopt 3.14.14, with the following parameters (cf. https://coin-or.github.io/Ipopt/OPTIONS.html):
check_derivatives_for_naninf=...
0
votes
0
answers
72
views
Solving a max-min convex optimization problem with interior-point methods
I would like to solve the following problem:
\begin{align}
\text{ minimize } && t
\\
\text{ subject to } && f_i(x) - t \leq 0 \text{ for all $i\in 1,\ldots,n$,}
\\
&& 0\leq ...
1
vote
1
answer
161
views
interior point computational complexity for SDP
I am trying to get the complexity of the SDP problem for my specific problem, but Iām facing some problems.
I found in the literature that the complexity of the SDP problem for an interior point per ...
0
votes
1
answer
61
views
Knitro`ms_maxsolves` equivalent in Ipopt
Ipopt/Knitro are local optimization solvers, so for nonconvex problems convergence doesn't guarantee optimality. However, Knitro has a multi-start method where one can start with more random initial ...
1
vote
2
answers
117
views
My barrier function is always giving a complex number
I am working on implementing the interior point method, and the barrier function always gives me a complex number. B(x) = f(x) - t * sum(ln(hi(x))). I have changed the value of 't' to see the B(x) ...
0
votes
0
answers
75
views
Transform any linear program to its standard form used in interior point solvers
I have programmed the primal-dual simplex method as explained here.
The method requires the information to be passed in the standard form:
$$
min:\quad c^\top \cdot x\\
s.t.:\\
AĀ·x = b\\
x \geq 0
$$
...
2
votes
1
answer
114
views
Convex Optimization, Non-negativity constraints, Interior-Point or Projected Gradient?
Assume I have the following convex optimization problem, with a convex objective function on conventional non-negativity constraints.
\begin{align}
\min_{x \geq 0} \sum_{i=1}^{I} a_{i}x_{i} - f(...
2
votes
1
answer
205
views
An upper bound for the norm of solution to linear optimization problem
I am looking for a practical method to find a valid upper bound for the infinity norm of the solution to a standard linear optimization problem:
\begin{align}\min&\quad c^\top x \\
\text{s.t.}&...
1
vote
1
answer
159
views
Dual solution when solving a primal degenerate LP with the interior point algorithm
Say, we're working with an LP that is primal degenerate (optimal solution is at a vertex but with multiple bases) and not dual degenerate (optimal solution is not at a face).
If we were to solve it ...
5
votes
1
answer
408
views
Practical open source LP solvers for large linear programming problem with $10^7$ parameters
I have an LP problem of the form $\min\ c^Tx$ subject to $Ax\leq b$ where $x$ consists of 30 million parameters and $A$ is a very very sparse matrix of size 30M by 30M (with only 3 ones per row). I ...
3
votes
0
answers
421
views
On solving the Restricted Master Problem in Column Generation technique
I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ...
24
votes
5
answers
4k
views
Find feasible point in polynomial time in linear programming
Background
A while ago my team was implementing an interior point LP solver and we came across the following conundrum:
Is there a polynomial-time algorithm to find a feasible starting point
in ...
18
votes
2
answers
492
views
Guidelines for Linear Optimization approaches?
When solving a Linear Optimization model (or Linear Program), there are a lot of solution approaches.
Just to name a few:
Primal Simplex
Dual Simplex
Ellipsoid Method (as if)
...