ADMM difficulty in finding active inequality constraints.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I have implemented a convex optimization algorithm based on the ADMM approach for quadratic programming of the form below:
$$ beginarrayll textminimize & x^T Q x + px\ textsubject to & Ax + b = 0\ text & Dx + E <=0endarray$$
the problem is that when some of the inequalities become active in the optimal solution, ADMM get too slow and actually it can't find the active ones, I thought it might be caused by ill-scaled matrices and I used a preconditioning method from "An Operator Splitting Solver for Quadratic Programs" article, but nothing changed and it still cannot find active inequalities. I have used Active-Set method to polish the solution obtained by the ADMM method, but as the active set is not known after running the ADMM algorithm it takes too many iterations to reach the optimal solution, Do you know any method other than the Active-Set method for polishing the solution?
linear-algebra optimization convex-optimization numerical-linear-algebra numerical-optimization
edited Sep 10 at 22:31
Royi
3,16512147
asked Sep 10 at 11:59
MAh2014
1439
 |Â
show 6 more comments
up vote
0
down vote
favorite
I have implemented a convex optimization algorithm based on the ADMM approach for quadratic programming of the form below:
$$ beginarrayll textminimize & x^T Q x + px\ textsubject to & Ax + b = 0\ text & Dx + E <=0endarray$$
the problem is that when some of the inequalities become active in the optimal solution, ADMM get too slow and actually it can't find the active ones, I thought it might be caused by ill-scaled matrices and I used a preconditioning method from "An Operator Splitting Solver for Quadratic Programs" article, but nothing changed and it still cannot find active inequalities. I have used Active-Set method to polish the solution obtained by the ADMM method, but as the active set is not known after running the ADMM algorithm it takes too many iterations to reach the optimal solution, Do you know any method other than the Active-Set method for polishing the solution?
linear-algebra optimization convex-optimization numerical-linear-algebra numerical-optimization
edited Sep 10 at 22:31
Royi
3,16512147
asked Sep 10 at 11:59
MAh2014
1439
1
Have you spent much time tuning the ADMM step size? That can make a big difference. For diagnosing the problem it would be useful to see a plot of the residuals $|Ax^k + b|$ and $sum(max(Dx^k + E,0))$ versus iteration number.
– littleO
Sep 11 at 0:26
@littleO Actually, I once used a method to calculate the step size it was something related to the eigenvalues of matrices, but it wasn't helpful that much so I dropped it.
– MAh2014
Sep 11 at 6:46
For debugging, you could try solving a version of the problem that uses artificially constructed matrices that are well conditioned. You can see if that works at least.
– littleO
Sep 11 at 6:54
@littleO I create my test cases by using matrices with random elements and it works for some range of elements values, but when I change the range of values it gets inaccurate.
– MAh2014
Sep 11 at 7:26
@littleO Do you know any method that can be used for polishing the solution obtained by ADMM? because it can obtain the solution with modest accuracy.
– MAh2014
Sep 12 at 12:16
 |Â
show 6 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have implemented a convex optimization algorithm based on the ADMM approach for quadratic programming of the form below:
$$ beginarrayll textminimize & x^T Q x + px\ textsubject to & Ax + b = 0\ text & Dx + E <=0endarray$$
the problem is that when some of the inequalities become active in the optimal solution, ADMM get too slow and actually it can't find the active ones, I thought it might be caused by ill-scaled matrices and I used a preconditioning method from "An Operator Splitting Solver for Quadratic Programs" article, but nothing changed and it still cannot find active inequalities. I have used Active-Set method to polish the solution obtained by the ADMM method, but as the active set is not known after running the ADMM algorithm it takes too many iterations to reach the optimal solution, Do you know any method other than the Active-Set method for polishing the solution?
linear-algebra optimization convex-optimization numerical-linear-algebra numerical-optimization
edited Sep 10 at 22:31
Royi
3,16512147
asked Sep 10 at 11:59
MAh2014
1439
I have implemented a convex optimization algorithm based on the ADMM approach for quadratic programming of the form below:
$$ beginarrayll textminimize & x^T Q x + px\ textsubject to & Ax + b = 0\ text & Dx + E <=0endarray$$
the problem is that when some of the inequalities become active in the optimal solution, ADMM get too slow and actually it can't find the active ones, I thought it might be caused by ill-scaled matrices and I used a preconditioning method from "An Operator Splitting Solver for Quadratic Programs" article, but nothing changed and it still cannot find active inequalities. I have used Active-Set method to polish the solution obtained by the ADMM method, but as the active set is not known after running the ADMM algorithm it takes too many iterations to reach the optimal solution, Do you know any method other than the Active-Set method for polishing the solution?
linear-algebra optimization convex-optimization numerical-linear-algebra numerical-optimization
linear-algebra optimization convex-optimization numerical-linear-algebra numerical-optimization
edited Sep 10 at 22:31
Royi
3,16512147
asked Sep 10 at 11:59
MAh2014
1439
edited Sep 10 at 22:31
Royi
3,16512147
asked Sep 10 at 11:59
MAh2014
1439
edited Sep 10 at 22:31
Royi
3,16512147
edited Sep 10 at 22:31
Royi
3,16512147
edited Sep 10 at 22:31
Royi
3,16512147
3,16512147
asked Sep 10 at 11:59
MAh2014
1439
asked Sep 10 at 11:59
MAh2014
1439
asked Sep 10 at 11:59
MAh2014
1439
1439
1
Have you spent much time tuning the ADMM step size? That can make a big difference. For diagnosing the problem it would be useful to see a plot of the residuals $|Ax^k + b|$ and $sum(max(Dx^k + E,0))$ versus iteration number.
– littleO
Sep 11 at 0:26
@littleO Actually, I once used a method to calculate the step size it was something related to the eigenvalues of matrices, but it wasn't helpful that much so I dropped it.
– MAh2014
Sep 11 at 6:46
For debugging, you could try solving a version of the problem that uses artificially constructed matrices that are well conditioned. You can see if that works at least.
– littleO
Sep 11 at 6:54
@littleO I create my test cases by using matrices with random elements and it works for some range of elements values, but when I change the range of values it gets inaccurate.
– MAh2014
Sep 11 at 7:26
@littleO Do you know any method that can be used for polishing the solution obtained by ADMM? because it can obtain the solution with modest accuracy.
– MAh2014
Sep 12 at 12:16
 |Â
show 6 more comments
1
Have you spent much time tuning the ADMM step size? That can make a big difference. For diagnosing the problem it would be useful to see a plot of the residuals $|Ax^k + b|$ and $sum(max(Dx^k + E,0))$ versus iteration number.
– littleO
Sep 11 at 0:26
@littleO Actually, I once used a method to calculate the step size it was something related to the eigenvalues of matrices, but it wasn't helpful that much so I dropped it.
– MAh2014
Sep 11 at 6:46
For debugging, you could try solving a version of the problem that uses artificially constructed matrices that are well conditioned. You can see if that works at least.
– littleO
Sep 11 at 6:54
@littleO I create my test cases by using matrices with random elements and it works for some range of elements values, but when I change the range of values it gets inaccurate.
– MAh2014
Sep 11 at 7:26
@littleO Do you know any method that can be used for polishing the solution obtained by ADMM? because it can obtain the solution with modest accuracy.
– MAh2014
Sep 12 at 12:16
1
1
Have you spent much time tuning the ADMM step size? That can make a big difference. For diagnosing the problem it would be useful to see a plot of the residuals $|Ax^k + b|$ and $sum(max(Dx^k + E,0))$ versus iteration number.
– littleO
Sep 11 at 0:26
Have you spent much time tuning the ADMM step size? That can make a big difference. For diagnosing the problem it would be useful to see a plot of the residuals $|Ax^k + b|$ and $sum(max(Dx^k + E,0))$ versus iteration number.
– littleO
Sep 11 at 0:26
@littleO Actually, I once used a method to calculate the step size it was something related to the eigenvalues of matrices, but it wasn't helpful that much so I dropped it.
– MAh2014
Sep 11 at 6:46
@littleO Actually, I once used a method to calculate the step size it was something related to the eigenvalues of matrices, but it wasn't helpful that much so I dropped it.
– MAh2014
Sep 11 at 6:46
For debugging, you could try solving a version of the problem that uses artificially constructed matrices that are well conditioned. You can see if that works at least.
– littleO
Sep 11 at 6:54
For debugging, you could try solving a version of the problem that uses artificially constructed matrices that are well conditioned. You can see if that works at least.
– littleO
Sep 11 at 6:54
@littleO I create my test cases by using matrices with random elements and it works for some range of elements values, but when I change the range of values it gets inaccurate.
– MAh2014
Sep 11 at 7:26
@littleO I create my test cases by using matrices with random elements and it works for some range of elements values, but when I change the range of values it gets inaccurate.
– MAh2014
Sep 11 at 7:26
@littleO Do you know any method that can be used for polishing the solution obtained by ADMM? because it can obtain the solution with modest accuracy.
– MAh2014
Sep 12 at 12:16
@littleO Do you know any method that can be used for polishing the solution obtained by ADMM? because it can obtain the solution with modest accuracy.
– MAh2014
Sep 12 at 12:16
 |Â
show 6 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%2f2911843%2fadmm-difficulty-in-finding-active-inequality-constraints%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
1
Have you spent much time tuning the ADMM step size? That can make a big difference. For diagnosing the problem it would be useful to see a plot of the residuals $|Ax^k + b|$ and $sum(max(Dx^k + E,0))$ versus iteration number.
– littleO
Sep 11 at 0:26
@littleO Actually, I once used a method to calculate the step size it was something related to the eigenvalues of matrices, but it wasn't helpful that much so I dropped it.
– MAh2014
Sep 11 at 6:46
For debugging, you could try solving a version of the problem that uses artificially constructed matrices that are well conditioned. You can see if that works at least.
– littleO
Sep 11 at 6:54
@littleO I create my test cases by using matrices with random elements and it works for some range of elements values, but when I change the range of values it gets inaccurate.
– MAh2014
Sep 11 at 7:26
@littleO Do you know any method that can be used for polishing the solution obtained by ADMM? because it can obtain the solution with modest accuracy.
– MAh2014
Sep 12 at 12:16