ERROR: Non-negative step lengths expected.

[caoweiquan322]

When I try to solve a QP problem with qpmad, I met the problems below:

>>>>>>>>>11<<<<<<<<<
||| Objective = -266.027021065978
||| Chosen ctr index = 25
||| Chosen ctr dual = 0
||| Chosen ctr violation = -10.7694141622394
===============================[Dual variables]=================================
 0E dual -2.31584178474632e+77 | ref 0.847380199791219 | 
 1E dual 2.00390016832115 | ref 1.11677628384381 | 
 2E dual 1.14490461843211e+243 | ref 0.0919589241032566 | 
 3E dual 2.64519867696432e+185 | ref -1.62334528075241 | 
 4E dual 1.43258072459788e+161 | ref 1.34227884497892 | 
 5E dual 5.73840351395146e+180 | ref -1.3422789927618 | 
 6E dual 2.3159651696868e+251 | ref -1.17315363316991e-13 | 
 7E dual 1.67521846802284e+243 | ref -1.02173146207707e-14 | 
 8E dual 6.08532827064867e+247 | ref 3.59648630389018e-15 | 
 9E dual 5.83468418597657e+252 | ref 2.12444063644432e-13 | 
 10E dual 1.46923002450926e+195 | ref 1.62521176045069e-15 | 
 11E dual 7.74563968475407e+228 | ref 3.4903781308604e-15 | 
 12E dual 1.27641000478602e-152 | ref 2.28880585373315e-14 | 
 13E dual 7.70438900955491e-90 | ref -4.80928202710854e-13 | 
 14E dual 7.67700263219408e+170 | ref 4.12643806784079e-14 | 
 15E dual 2.21058545138405e+161 | ref 1.61423242543404e-14 | 
 16E dual 6.19076424193706e+223 | ref 3.31166896615516e-13 | 
 17E dual 2.04912601056586e+190 | ref -3.83668853818299e-13 | 
 18E dual 4.07056057379651e+180 | ref 9.29047182931297e-16 | 
 19E dual 4.96042859615768e+180 | ref 9.13925016340583e-16 | 
 20E dual 2.12716100930499e+233 | ref -2.02293698722773e-12 | 
 21E dual 1.7222152387511e+97 | ref 2.70343617324218e-12 | 
 22E dual 9.77824555674643e+199 | ref -8.15106830795058e-13 | 
 23E dual 2.3215932807431e-152 | ref 1.32020928566434e-12 | 
 24E dual 5.83015342134422e+252 | ref -8.4267188924131e-15 | 
 25E dual 1.47716090065559e+248 | ref 5.30039451860025e-13 | 
 26E dual 2.60987680268875e+180 | ref 4.48756888326984e-16 | 
 27E dual 3.17247816371551e+180 | ref 6.66447883268854e-14 | 
 28E dual 1.87300534664135e-152 | ref -0.847380199791223 | 
 29E dual 1.12184972768542e+200 | ref -1.1167762838438 | 
 30E dual 2.25246903361602e+223 | ref -0.0919589241032573 | 
 31E dual 1.2169800223046e-152 | ref 1.62334528075241 | 
 32E dual 4.82410895759326e+228 | ref -1.34227884497892 | 
 33E dual 8.87709131853017e+252 | ref 1.3422789927618 | 
 34E dual 6.88935657826008e-154 | ref -0.018519904616543 | 
 35E dual 5.04041307916274e+180 | ref 0.00523917439104987 | 
 36E dual 3.39007028937108e+175 | ref -0.0164622332980626 | 
 37E dual 1.84953534501144e-86 | ref -0.0174884153223189 | 
 38E dual nan | ref 0.00523917425002763 | 
 39E dual 7.90505033345994e-323 | ref -0.016463050204563 | 
 40E dual -2.31584178474632e+77 | ref -0.0185199042198221 | 
 41E dual -2.31584178474632e+77 | ref 0.00266045053911009 | 
 42E dual 6.94253005788901e-310 | ref -0.0154975844954167 | 
 43E dual 6.99196245722783e+228 | ref -0.0174884149255979 | 
 44E dual 1.63041663127611e-322 | ref 0.00266045039808784 | 
 45E dual 1.48219693752374e-322 | ref -0.0154984014019171 | 
 46L dual 0.154294851361175 | ref 0.154294851355922 | err 5.25268717410654e-12 | dir -0.0508685638547752 | len -3.03320635907221
 47L dual 0.353613172582382 | ref 0.353613172582856 | err 4.73399097700167e-13 | dir -0.184262627453409 | len -1.91907158532076
 48L dual 0.268191031564586 | ref 0.268191031571021 | err 6.4341310057614e-12 | dir -0.127093742940045 | len -2.11018280963763
 49L dual 0.0688727103433377 | ref 0.0688727103440457 | err 7.07961467227847e-13 | dir 0.00630032065861702 | len 10.9316198452756
 50L dual 0.0119246380237897 | ref 0.0119246380166749 | err 7.11484517135208e-12 | dir 0.0444128960414374 | len 0.268494943735801
 51L dual 0.0688727103433281 | ref 0.068872710340688 | err 2.64019361928547e-12 | dir 0.00630032065861693 | len 10.9316198452742
 52L dual 0.0688727199795147 | ref 0.0688727199796115 | err 9.6783692171698e-14 | dir 0.00630030969143695 | len 10.9316404038238
 53L dual 0.125820792299065 | ref 0.125820792303637 | err 4.57203719328447e-12 | dir -0.0318122656913913 | len -3.95510315171022
 54L dual 0.142370213337378 | ref 0.142370213331593 | err 5.7846782919313e-12 | dir -0.0952814598962123 | len -1.49420688445011
 55L dual 0.284740452602855 | ref 0.284740452603391 | err 5.36182209742719e-13 | dir -0.190562937144846 | len -1.49420688445007
 56L dual 0.142370239265507 | ref 0.142370239272597 | err 7.08991199083187e-12 | dir -0.0952814772486529 | len -1.49420688445004
 MAX DIFF = 7.11484517135208e-12
================================================================================
======================
||| Primal step length = 78.7673142464265
||| Dual step length = 1.49420688445004
======================
||| Chosen ctr dual = 1.49420688445004
||| Chosen ctr violation = -10.5651196152352
||| PARTIAL STEP
>>>>>>>>>12<<<<<<<<<
||| Objective = -265.874391906683
||| Chosen ctr index = 25
||| Chosen ctr dual = 1.49420688445004
||| Chosen ctr violation = -10.5651196152352
===============================[Dual variables]=================================
 0E dual -2.31584178474632e+77 | ref 0.886573742095105 | 
 1E dual 2.00390016832115 | ref 1.12764340299259 | 
 2E dual 1.14490461843211e+243 | ref -0.0614739612564278 | 
 3E dual 2.64519867696432e+185 | ref -1.83674603359391 | 
 4E dual 1.43258072459788e+161 | ref 1.447062102309 | 
 5E dual 5.73840351395146e+180 | ref -0.0973741132420379 | 
 6E dual 2.3159651696868e+251 | ref 0.000228886643272592 | 
 7E dual 1.67521846802284e+243 | ref 9.9415457331306e-06 | 
 8E dual 6.08532827064867e+247 | ref 3.68649647330121e-05 | 
 9E dual 5.83468418597657e+252 | ref 0.00870311912048286 | 
 10E dual 1.46923002450926e+195 | ref -0.000185927222331279 | 
 11E dual 7.74563968475407e+228 | ref 9.39463840217075e-05 | 
 12E dual 1.27641000478602e-152 | ref -8.32622515673602e-05 | 
 13E dual 7.70438900955491e-90 | ref -0.00157533210917213 | 
 14E dual 7.67700263219408e+170 | ref -7.07805050086286e-05 | 
 15E dual 2.21058545138405e+161 | ref 0.000106248804518329 | 
 16E dual 6.19076424193706e+223 | ref -0.00128009850656904 | 
 17E dual 2.04912601056586e+190 | ref 0.0143080914993456 | 
 18E dual 4.07056057379651e+180 | ref -1.4120995518549e-05 | 
 19E dual 4.96042859615768e+180 | ref -1.38887483494349e-05 | 
 20E dual 2.12716100930499e+233 | ref -0.0114536213337148 | 
 21E dual 1.7222152387511e+97 | ref 0.0265209960110948 | 
 22E dual 9.77824555674643e+199 | ref -0.00314189280415674 | 
 23E dual 2.3215932807431e-152 | ref -0.00688035543957179 | 
 24E dual 5.83015342134422e+252 | ref -0.000152379267024313 | 
 25E dual 1.47716090065559e+248 | ref 0.0347960532372014 | 
 26E dual 2.60987680268875e+180 | ref -8.50405119200722e-07 | 
 27E dual 3.17247816371551e+180 | ref 0.0080831773684757 | 
 28E dual 1.87300534664135e-152 | ref -0.886573742095112 | 
 29E dual 1.12184972768542e+200 | ref -1.12764340299258 | 
 30E dual 2.25246903361602e+223 | ref 0.0614739612564277 | 
 31E dual 1.2169800223046e-152 | ref 1.83674603359391 | 
 32E dual 4.82410895759326e+228 | ref -1.447062102309 | 
 33E dual 8.87709131853017e+252 | ref 0.0973741132420379 | 
 34E dual 6.88935657826008e-154 | ref -0.00495412091083688 | 
 35E dual 5.04041307916274e+180 | ref 0.00697480784849025 | 
 36E dual 3.39007028937108e+175 | ref -0.00744542486174347 | 
 37E dual 1.84953534501144e-86 | ref -0.00451948758482517 | 
 38E dual nan | ref 0.00697480779940703 | 
 39E dual 7.90505033345994e-323 | ref -0.00768554702463583 | 
 40E dual -2.31584178474632e+77 | ref -0.00495412087608622 | 
 41E dual -2.31584178474632e+77 | ref 0.00588822437130159 | 
 42E dual 6.94253005788901e-310 | ref -0.00993688370706451 | 
 43E dual 6.99196245722783e+228 | ref -0.00451948755007455 | 
 44E dual 1.63041663127611e-322 | ref 0.00588822432221839 | 
 45E dual 1.48219693752374e-322 | ref -0.0101770058699569 | 
 46L dual 0.0782866930472833 | ref 0.123230147629422 | err 0.0449434545821387 | dir -7.39002786393771e-05 | len -1059.35585749698
 47L dual 0.0782866860946451 | ref 0.12890637727751 | err 0.0506196911828649 | dir -7.3900272081347e-05 | len -1059.35585742458
 48L dual 0.0782866858930478 | ref 0.111057958573474 | err 0.0327712726804262 | dir -7.39002718863067e-05 | len -1059.35585749251
 49L dual 0.078286692845686 | ref 0.105381728925385 | err 0.0270950360796987 | dir -7.39002784442859e-05 | len -1059.35585756564
 50L dual 0.0782866930472694 | ref -0.0235570420455935 | err 0.101843735092863 | dir -7.39002786339279e-05 | len -1059.35585757491
 51L dual 0.0782866928456764 | ref -0.0309102703125844 | err 0.109196963158261 | dir -7.39002784437659e-05 | len -1059.35585757296
 52L dual 0.0782866860946271 | ref -0.0283759922908618 | err 0.106662678385489 | dir -7.390027207082e-05 | len -1059.35585757524
 53L dual 0.0782866858930339 | ref -0.0357292205578535 | err 0.114015906450887 | dir -7.39002718807976e-05 | len -1059.35585757129
 54L dual 6.80011602582908e-15 | ref 0.0504613690635848 | err 0.050461369063578 | dir -6.77419390045117e-15 | len -1.00382659926168
 55L dual 6.55031584528842e-15 | ref 0.0519395293108705 | err 0.051939529310864 | dir -9.79694358307954e-15 | len -0.668608101061395
 MAX DIFF = 0.114015906450887
================================================================================
======================
||| Primal step length = 3.61930122381096
||| Dual step length = 1059.35585742458
======================
||| Chosen ctr dual = 5.113508108261
||| Chosen ctr violation = 0
||| FULL STEP
>>>>>>>>>13<<<<<<<<<
||| Objective = -230.968742265996
||| Chosen ctr index = 65
||| Chosen ctr dual = 0
||| Chosen ctr violation = -4.04184784113166
===============================[Dual variables]=================================
 0E dual -2.31584178474632e+77 | ref 3.04918279211611 | 
 1E dual 2.00390016832115 | ref 1.12413747651584 | 
 2E dual 1.14490461843211e+243 | ref -0.125255515328256 | 
 3E dual 2.64519867696432e+185 | ref -1.83893035099962 | 
 4E dual 1.43258072459788e+161 | ref 5.11350785674386 | 
 5E dual 5.73840351395146e+180 | ref 1.94222372525932e-07 | 
 6E dual 2.3159651696868e+251 | ref -9.68976537539258e-14 | 
 7E dual 1.67521846802284e+243 | ref -2.1654960716527e-15 | 
 8E dual 6.08532827064867e+247 | ref 1.70349627136747e-14 | 
 9E dual 5.83468418597657e+252 | ref -2.02500446485189e-12 | 
 10E dual 1.46923002450926e+195 | ref -1.22785769899246e-14 | 
 11E dual 7.74563968475407e+228 | ref 6.27829256898271e-15 | 
 12E dual 1.27641000478602e-152 | ref 6.80154947810221e-14 | 
 13E dual 7.70438900955491e-90 | ref 8.68995698493004e-13 | 
 14E dual 7.67700263219408e+170 | ref 2.22642161095133e-14 | 
 15E dual 2.21058545138405e+161 | ref 7.88447389421712e-14 | 
 16E dual 6.19076424193706e+223 | ref 4.09552115930556e-13 | 
 17E dual 2.04912601056586e+190 | ref 8.63601598915939e-14 | 
 18E dual 4.07056057379651e+180 | ref -7.96662274191102e-16 | 
 19E dual 4.96042859615768e+180 | ref -7.44010543003327e-16 | 
 20E dual 2.12716100930499e+233 | ref 3.14333753181173e-12 | 
 21E dual 1.7222152387511e+97 | ref -5.95074351645333e-12 | 
 22E dual 9.77824555674643e+199 | ref 1.25377132210274e-12 | 
 23E dual 2.3215932807431e-152 | ref -5.28088247540395e-12 | 
 24E dual 5.83015342134422e+252 | ref 9.39870318111121e-15 | 
 25E dual 1.47716090065559e+248 | ref 5.11350810820591 | 
 26E dual 2.60987680268875e+180 | ref 4.87482017245795e-16 | 
 27E dual 3.17247816371551e+180 | ref 4.15385016024913e-13 | 
 28E dual 1.87300534664135e-152 | ref -3.04918279211613 | 
 29E dual 1.12184972768542e+200 | ref -1.12413747651584 | 
 30E dual 2.25246903361602e+223 | ref 0.125255515328259 | 
 31E dual 1.2169800223046e-152 | ref 1.83893035099962 | 
 32E dual 4.82410895759326e+228 | ref -5.11350785674387 | 
 33E dual 8.87709131853017e+252 | ref -1.94222372438214e-07 | 
 34E dual 6.88935657826008e-154 | ref -0.0109464710004562 | 
 35E dual 5.04041307916274e+180 | ref 0.00466126535438098 | 
 36E dual 3.39007028937108e+175 | ref -0.0158876222947721 | 
 37E dual 1.84953534501144e-86 | ref -0.0102597974340946 | 
 38E dual nan | ref 0.00466126526010093 | 
 39E dual 7.90505033345994e-323 | ref -0.015878888583466 | 
 40E dual -2.31584178474632e+77 | ref -0.0109464707515207 | 
 41E dual -2.31584178474632e+77 | ref 0.00294458104351762 | 
 42E dual 6.94253005788901e-310 | ref -0.0155773571068212 | 
 43E dual 6.99196245722783e+228 | ref -0.0102597971851592 | 
 44E dual 1.63041663127611e-322 | ref 0.00294458094923757 | 
 45E dual 1.48219693752374e-322 | ref -0.0155686233955151 | 
 46L dual 0.0780192256783639 | ref 0.0780192256869664 | err 8.6025214729446e-12 | dir 0.469626750350798 | len 0.166130284571919
 47L dual 0.0780192187494611 | ref 0.0780192187539232 | err 4.46209735827097e-12 | dir -0.930373166688562 | len -0.0838579846699058
 48L dual 0.0780192185485697 | ref 0.0780192185410391 | err 7.53061502045682e-12 | dir -0.330373241826028 | len -0.236154774876272
 49L dual 0.0780192254774727 | ref 0.0780192254740824 | err 3.39024641693442e-12 | dir 1.06962667521362 | len 0.0729406130993237
 50L dual 0.0780192256783696 | ref 0.078019225684088 | err 5.71839797736118e-12 | dir 0.469626476848115 | len 0.166130381323458
 51L dual 0.0780192254774649 | ref 0.0780192254757563 | err 1.70852221259565e-12 | dir 0.069626675213618 | len 1.1205364213945
 52L dual 0.0780192187494813 | ref 0.078019218746493 | err 2.98830404865669e-12 | dir 0.0696265598085509 | len 1.12053818203868
 53L dual 0.0780192185485757 | ref 0.0780192185381602 | err 1.04155017943697e-11 | dir -0.330373241826028 | len -0.23615477487629
 54L dual -1.77177322484066e-14 | ref 1.0673391694978e-11 | err 1.06911094272264e-11 | dir 2.735026831556e-07 | len -6.47808352151584e-08
 55L dual -2.89077740545583e-14 | ref 4.69476248705315e-12 | err 4.72367026110771e-12 | dir -0.999999726497111 | len 2.89077819609202e-14
 56L dual 5.113508108261 | ref 5.11350810820591 | err 5.50892664819003e-11 | dir 0.382518527973002 | len 13.3680011145026
 MAX DIFF = 5.50892664819003e-11
================================================================================
======================
||| Primal step length = 33.0194794715322
||| Dual step length = -2.89077819609202e-14
======================
[!] MainWnd: Error occurs: In solve() // Non-negative step lengths expected., terminating ...

I read the related paper, but did not fully understand it yet.
By tracing the raised exception, I tried modified one line (within solver.h):
for (MatrixIndex i = active_set_.num_equalities_; i < active_set_.size_; ++i)
{
if (dual_step_direction_(i) < -param.tolerance_)
{
// This line was modified !!! // double dual_step_length_i = -dual(i) / dual_step_direction_(i);_
double dual_step_length_i = -std::max(dual_(i), 0.0) / dual_step_direction_(i);
if (dual_step_length_i < dual_step_length)
{
dual_step_length = dual_step_length_i;
dual_blocking_index = i;
}
}
}

I just want to confirm that: is the operation above safe? Is it totally wrong? What is the correct way to fix this issue?
Thanks.

[asherikov]

Hello, this is an internal sanity check, in general, a solution you get by bypassing it is trash. The reason why you get this error is most likely numerical issues (the solver is not very good at handling numerically difficult problems). Could also be a bug, it is hard to say not seeing the actual problem.

I recommend you to check:

• feasibility of the constraints, I suspect that there is a conflict between equalities and inequalities,
• proper initialization of the inputs,
• that Hessian is positive definite and its condition number is reasonable,
• size of the problem -- it should not be too large, I haven't tested, but the solver is likely to struggle with large problems with thousands of decision variables.

[caoweiquan322]

Hello, this is an internal sanity check, in general, a solution you get by bypassing it is trash. The reason why you get this error is most likely numerical issues (the solver is not very good at handling numerically difficult problems). Could also be a bug, it is hard to say not seeing the actual problem.

I recommend you to check:

• feasibility of the constraints, I suspect that there is a conflict between equalities and inequalities,
• proper initialization of the inputs,
• that Hessian is positive definite and its condition number is reasonable,
• size of the problem -- it should not be too large, I haven't tested, but the solver is likely to struggle with large problems with thousands of decision variables.

Thanks for the fast reply!
For the 4 valuable tips:
2-4. The problem to be solved is a general WBC(i.e. whole body control) QP problem. Hessian is regularized by adding a small (1e-8) norm loss for X. i.e. Objective function f(X) = actual_f(X) + 1e-8*||X||. Size of the decision variables and constraints are both below 100. I think the size is not a problem.

1. I think it's the most possible issue. Inequality constraints come from joint torque limits, joint limits, contact friction cones, contact non-penetration restriction, etc. They may conflict under specific conditions.

[asherikov]

Ok then I correct my guess: there are redundant constraints. ~~More precisely, friction cone constraints guarantee non-penetration.~~ Sorry, this was misleading, what I wanted to say is that nonpenetration inequalities are redundant, only friction cone + contact point equalities are needed. I am still thinking that you have redundant constraints though.

[asherikov]

Hi, any progress? I would like to get the actual problem for testing (just the numbers not the formulation), otherwise I cannot help you.