Mixing
Primal Dual Interior Point convergence.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I have developed a Primal Dual Interior point algorithm to solve linear inequality constrained Quadratic problems. But sometimes it cannot reduce the residual so as to satisfy the stop criteria. I mean the residual decreases and reaches some value (that I think depends on the scale of the matrices) and then it gets stuck at that value. How should I deal with this dilemma? I have studied an article about Predictor Corrector method, but it is noted in the article that sometimes this method does not converge. Is there any method that leads to definite convergence? And one more question,Is PDIPM even a good choice for solving quadratic problems? Is there any more advanced stop criteria other than primal and residual norm ,that varies with scale and size of variables ?
optimization convex-optimization quadratic-programming
asked Aug 2 at 10:42
MAh2014
1299
 |Â
show 3 more comments
up vote
0
down vote
favorite
I have developed a Primal Dual Interior point algorithm to solve linear inequality constrained Quadratic problems. But sometimes it cannot reduce the residual so as to satisfy the stop criteria. I mean the residual decreases and reaches some value (that I think depends on the scale of the matrices) and then it gets stuck at that value. How should I deal with this dilemma? I have studied an article about Predictor Corrector method, but it is noted in the article that sometimes this method does not converge. Is there any method that leads to definite convergence? And one more question,Is PDIPM even a good choice for solving quadratic problems? Is there any more advanced stop criteria other than primal and residual norm ,that varies with scale and size of variables ?
optimization convex-optimization quadratic-programming
asked Aug 2 at 10:42
MAh2014
1299
PDIPM with predictors/correctors is the method of choice, all major solvers rely on it. Look at the MOSEK paper for ideas; a good starting point helps. Residual of what? Primal/dual feasibility? What does stuck mean? Is your step length severely limited by the boundary?
– LinAlg
Aug 2 at 15:39
@LinAlg by residual I meant primal and dual residual,and getting stuck means in line search the step length become so small such that $ x + alpha dx = x$ and so the algorithm does not proceed.the step length is computed via back tracking line search and it has to be small enough not to exceed primal and dual feasibility.So you mean predictor corrector is a good choice?
– MAh2014
Aug 2 at 19:01
I assume that you are performing your computations in double precision. In practice, the Newton’s method step equations become very badly conditioned as you approach an optimal solution. Have you considered this I’ll-conditioning?
– Brian Borchers
Aug 2 at 19:34
You can mitigate small steps by using a better starting point and by using predictor/corrector methods. Standard Mehrotra should be a big step forward (hehe), but Gondzio's papers are worth looking into.
– LinAlg
Aug 2 at 20:37
@BrianBorchers yes exactly, the matrix associated with linear systems going to be solved in each iteration some times become nearly singular,What should I do about that?
– MAh2014
Aug 2 at 21:06
 |Â
show 3 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have developed a Primal Dual Interior point algorithm to solve linear inequality constrained Quadratic problems. But sometimes it cannot reduce the residual so as to satisfy the stop criteria. I mean the residual decreases and reaches some value (that I think depends on the scale of the matrices) and then it gets stuck at that value. How should I deal with this dilemma? I have studied an article about Predictor Corrector method, but it is noted in the article that sometimes this method does not converge. Is there any method that leads to definite convergence? And one more question,Is PDIPM even a good choice for solving quadratic problems? Is there any more advanced stop criteria other than primal and residual norm ,that varies with scale and size of variables ?
optimization convex-optimization quadratic-programming
asked Aug 2 at 10:42
MAh2014
1299
I have developed a Primal Dual Interior point algorithm to solve linear inequality constrained Quadratic problems. But sometimes it cannot reduce the residual so as to satisfy the stop criteria. I mean the residual decreases and reaches some value (that I think depends on the scale of the matrices) and then it gets stuck at that value. How should I deal with this dilemma? I have studied an article about Predictor Corrector method, but it is noted in the article that sometimes this method does not converge. Is there any method that leads to definite convergence? And one more question,Is PDIPM even a good choice for solving quadratic problems? Is there any more advanced stop criteria other than primal and residual norm ,that varies with scale and size of variables ?
optimization convex-optimization quadratic-programming
asked Aug 2 at 10:42
MAh2014
1299
edited Aug 2 at 12:44
asked Aug 2 at 10:42
MAh2014
1299
asked Aug 2 at 10:42
MAh2014
1299
asked Aug 2 at 10:42
MAh2014
1299
1299
PDIPM with predictors/correctors is the method of choice, all major solvers rely on it. Look at the MOSEK paper for ideas; a good starting point helps. Residual of what? Primal/dual feasibility? What does stuck mean? Is your step length severely limited by the boundary?
– LinAlg
Aug 2 at 15:39
@LinAlg by residual I meant primal and dual residual,and getting stuck means in line search the step length become so small such that $ x + alpha dx = x$ and so the algorithm does not proceed.the step length is computed via back tracking line search and it has to be small enough not to exceed primal and dual feasibility.So you mean predictor corrector is a good choice?
– MAh2014
Aug 2 at 19:01
I assume that you are performing your computations in double precision. In practice, the Newton’s method step equations become very badly conditioned as you approach an optimal solution. Have you considered this I’ll-conditioning?
– Brian Borchers
Aug 2 at 19:34
You can mitigate small steps by using a better starting point and by using predictor/corrector methods. Standard Mehrotra should be a big step forward (hehe), but Gondzio's papers are worth looking into.
– LinAlg
Aug 2 at 20:37
@BrianBorchers yes exactly, the matrix associated with linear systems going to be solved in each iteration some times become nearly singular,What should I do about that?
– MAh2014
Aug 2 at 21:06
 |Â
show 3 more comments
PDIPM with predictors/correctors is the method of choice, all major solvers rely on it. Look at the MOSEK paper for ideas; a good starting point helps. Residual of what? Primal/dual feasibility? What does stuck mean? Is your step length severely limited by the boundary?
– LinAlg
Aug 2 at 15:39
@LinAlg by residual I meant primal and dual residual,and getting stuck means in line search the step length become so small such that $ x + alpha dx = x$ and so the algorithm does not proceed.the step length is computed via back tracking line search and it has to be small enough not to exceed primal and dual feasibility.So you mean predictor corrector is a good choice?
– MAh2014
Aug 2 at 19:01
I assume that you are performing your computations in double precision. In practice, the Newton’s method step equations become very badly conditioned as you approach an optimal solution. Have you considered this I’ll-conditioning?
– Brian Borchers
Aug 2 at 19:34
You can mitigate small steps by using a better starting point and by using predictor/corrector methods. Standard Mehrotra should be a big step forward (hehe), but Gondzio's papers are worth looking into.
– LinAlg
Aug 2 at 20:37
@BrianBorchers yes exactly, the matrix associated with linear systems going to be solved in each iteration some times become nearly singular,What should I do about that?
– MAh2014
Aug 2 at 21:06
PDIPM with predictors/correctors is the method of choice, all major solvers rely on it. Look at the MOSEK paper for ideas; a good starting point helps. Residual of what? Primal/dual feasibility? What does stuck mean? Is your step length severely limited by the boundary?
– LinAlg
Aug 2 at 15:39
PDIPM with predictors/correctors is the method of choice, all major solvers rely on it. Look at the MOSEK paper for ideas; a good starting point helps. Residual of what? Primal/dual feasibility? What does stuck mean? Is your step length severely limited by the boundary?
– LinAlg
Aug 2 at 15:39
@LinAlg by residual I meant primal and dual residual,and getting stuck means in line search the step length become so small such that $ x + alpha dx = x$ and so the algorithm does not proceed.the step length is computed via back tracking line search and it has to be small enough not to exceed primal and dual feasibility.So you mean predictor corrector is a good choice?
– MAh2014
Aug 2 at 19:01
@LinAlg by residual I meant primal and dual residual,and getting stuck means in line search the step length become so small such that $ x + alpha dx = x$ and so the algorithm does not proceed.the step length is computed via back tracking line search and it has to be small enough not to exceed primal and dual feasibility.So you mean predictor corrector is a good choice?
– MAh2014
Aug 2 at 19:01
I assume that you are performing your computations in double precision. In practice, the Newton’s method step equations become very badly conditioned as you approach an optimal solution. Have you considered this I’ll-conditioning?
– Brian Borchers
Aug 2 at 19:34
I assume that you are performing your computations in double precision. In practice, the Newton’s method step equations become very badly conditioned as you approach an optimal solution. Have you considered this I’ll-conditioning?
– Brian Borchers
Aug 2 at 19:34
You can mitigate small steps by using a better starting point and by using predictor/corrector methods. Standard Mehrotra should be a big step forward (hehe), but Gondzio's papers are worth looking into.
– LinAlg
Aug 2 at 20:37
You can mitigate small steps by using a better starting point and by using predictor/corrector methods. Standard Mehrotra should be a big step forward (hehe), but Gondzio's papers are worth looking into.
– LinAlg
Aug 2 at 20:37
@BrianBorchers yes exactly, the matrix associated with linear systems going to be solved in each iteration some times become nearly singular,What should I do about that?
– MAh2014
Aug 2 at 21:06
@BrianBorchers yes exactly, the matrix associated with linear systems going to be solved in each iteration some times become nearly singular,What should I do about that?
– MAh2014
Aug 2 at 21:06
 |Â
show 3 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2869940%2fprimal-dual-interior-point-convergence%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
PDIPM with predictors/correctors is the method of choice, all major solvers rely on it. Look at the MOSEK paper for ideas; a good starting point helps. Residual of what? Primal/dual feasibility? What does stuck mean? Is your step length severely limited by the boundary?
– LinAlg
Aug 2 at 15:39
@LinAlg by residual I meant primal and dual residual,and getting stuck means in line search the step length become so small such that $ x + alpha dx = x$ and so the algorithm does not proceed.the step length is computed via back tracking line search and it has to be small enough not to exceed primal and dual feasibility.So you mean predictor corrector is a good choice?
– MAh2014
Aug 2 at 19:01
I assume that you are performing your computations in double precision. In practice, the Newton’s method step equations become very badly conditioned as you approach an optimal solution. Have you considered this I’ll-conditioning?
– Brian Borchers
Aug 2 at 19:34
You can mitigate small steps by using a better starting point and by using predictor/corrector methods. Standard Mehrotra should be a big step forward (hehe), but Gondzio's papers are worth looking into.
– LinAlg
Aug 2 at 20:37
@BrianBorchers yes exactly, the matrix associated with linear systems going to be solved in each iteration some times become nearly singular,What should I do about that?
– MAh2014
Aug 2 at 21:06