[Clp] how change convergence tolerances for barrier method
William H. Patton
pattonwh at comcast.net
Tue Nov 27 13:51:22 EST 2012
On 11/27/2012 12:19 PM, William H. Patton wrote:
> I think your issue is poor scaling of the vars. Try scaling the
> quadratic vars by 1e-3 so that the objective should be around -1.3
> e+03 instead.
> Then maybe the complementarity will down scale by 1e-3 or so and quit
> within its tolerance.
>
>
> Any sensible person would want to quit around here at iter 18 or 22.
> The relative Complementary is 40/ 10^9 which is 8 digits of precision.
> Pretty good when you should expect only 5 to 6 digits after a bunch
> of double precision scalar products on the 911766 elements in sparse
> Cholesky,.
>
> 16 Primal -1.3318262e+09 Dual -1.3318287e+09 Complementarity 2519.259
> - 76 fixed, rank 3924
>
> 17 Primal -1.3318263e+09 Dual -1.3318263e+09 Complementarity 40.523345
> - 134 fixed, rank 3924
>
> *18 Primal -1.3318263e+09 Dual -1.3318263e+09 Complementarity
> 40.006314 - 134 fixed, rank 3924*
>
> 19 Primal -1.3318263e+09 Dual -1.3318264e+09 Complementarity 39.542777
> - 134 fixed, rank 3924
>
> 20 Primal -1.3318263e+09 Dual -1.3318265e+09 Complementarity 39.128027
> - 134 fixed, rank 3924
>
> 21 Primal -1.3318263e+09 Dual -1.3318266e+09 Complementarity 38.757635
> - 134 fixed, rank 3924
>
> *22 Primal -1.3318263e+09 Dual -1.3318263e+09 Complementarity
> 0.87384878 - 134 fixed, rank 3924*
>
> 23 Primal -1.3318263e+09 Dual -1.331649e+09 Complementarity
> 0.0061784205 - 134 fixed, rank 3924
>
> 24 Primal -1.3318263e+09 Dual -1.3047041e+09 Complementarity
> 4.0066434e-05 - 134 fixed, rank 39
>
> Check the code again. *Complementarity *
> Searching for: Complementarity
> ClpHelperFunctions.hpp(197): // Form residuals for the complementarity
> equations.
> ClpHelperFunctions.hpp(200): // Cinf is the complementarity residual
> for X1 z1 = mu e, etc.
> ClpMessage.cpp(73): {CLP_BARRIER_ITERATION, 35, 1, "%d Primal %g Dual
> %g Complementarity %g - %d fixed, rank %d"},
> ClpMessage.cpp(76): {CLP_BARRIER_CLOSE_TO_OPTIMAL, 38, 2, "Close to
> optimal after %d iterations with complementarity %g"},
> ClpMessage.cpp(77): {CLP_BARRIER_COMPLEMENTARITY, 39, 2,
> "Complementarity %g - %s"},
> ClpMessage.cpp(84): {CLP_BARRIER_END, 46, 1, "At end primal/dual
> infeasibilities %g/%g, complementarity gap %g, objective %g"},
> ClpPdco.cpp(480): // Initialize mu and complementarity residuals:
> ClpPredictorCorrector.cpp(461): << "- small complementarity gap"
> ClpPredictorCorrector.cpp(468): << "- objective gap and
> complementarity gap both small"
> ClpPredictorCorrector.cpp(480): << "- objective gap and
> complementarity gap both smallish and small steps"
> ClpPredictorCorrector.cpp(952): //std::cout<<"Absolute complementarity
> at end "<<complementarityGap_<<std::endl;
> ClpPredictorCorrector.cpp(954): //std::cout<<"maximum complementarity
> "<<worstComplementarity_<<std::endl;
> ClpPredictorCorrector.cpp(1125): // minimize complementarity +
> norm*dual inf ? primal inf
> ClpPredictorCorrector.cpp(1127): // Complementarity gap will be
> a*change*change + b*change +c
> ClpPredictorCorrector.cpp(1265): // Complementarity gap will be
> a*change*change + b*change +c
> ClpPredictorCorrector.cpp(2621): printf("good complementarity range %g
> to %g\n", minBeta, maxBeta);
> ClpPredictorCorrector.cpp(3423): CoinWorkDouble complementarity =
> zVec_[iColumn] * lowerSlack_[iColumn];
> ClpPredictorCorrector.cpp(3424): if (complementarity < nextMu) {
> ClpPredictorCorrector.cpp(3437): CoinWorkDouble complementarity =
> wVec_[iColumn] * upperSlack_[iColumn];
> ClpPredictorCorrector.cpp(3438): if (complementarity > nextMu) {
> ClpPredictorCorrector.cpp(3441): (complementarity - nextMu) /
> upperSlack_[iColumn]);
> ClpPredictorCorrector.cpp(3453): CoinWorkDouble complementarity =
> zVec_[iColumn] * lowerSlack_[iColumn];
> ClpPredictorCorrector.cpp(3454): if (complementarity > nextMu) {
> ClpPredictorCorrector.cpp(3467): CoinWorkDouble complementarity =
> wVec_[iColumn] * upperSlack_[iColumn];
> ClpPredictorCorrector.cpp(3468): if (complementarity < nextMu) {
> ClpPredictorCorrector.cpp(3471): (complementarity - nextMu) /
> upperSlack_[iColumn]);
> ClpSimplex.hpp(771): /// Large bound value (for complementarity etc)
> ClpSimplex.hpp(1346): /// Large bound value (for complementarity etc)
> Found 28 occurrence(s) in 5 file(s)
>
> So
> *ClpPredictorCorrector.cpp(246)*:
> handler_->message(CLP_BARRIER_ITERATION, messages_)
> context *18 Primal -1.3318263e+09 Dual -1.3318263e+09 Complementarity
> 40.006314 - 134 fixed, rank 3924*
> complementarityGap_ =
> complementarityGap(numberComplementarityPairs_,
> numberComplementarityItems_, 0);
> handler_->message(CLP_BARRIER_ITERATION, messages_)
> << numberIterations_
> << static_cast<double>(primalObjective_ * objScale
> - dblParam_[ClpObjOffset])
> << static_cast<double>(dualObjective_ * objScale -
> dblParam_[ClpObjOffset])
> << static_cast<double>(complementarityGap_)
> << numberFixedTotal
> << cholesky_->rank()
> << CoinMessageEol;
>
> line 336
> if (CoinAbs(primalObjective_ - dualObjective_) <
> *dualTolerance*()) { << so maybe relax the toleerance
> gapO = 0.0;
> }
>
> line 361 <<< figure out how to enable sloppyOptimal
> if (sloppyOptimal) {
> // vaguely optimal
> if (maximumBoundInfeasibility_ > 1.0e-2 ||
> scaledRHSError > 1.0e-2 ||
> maximumDualError_ > objectiveNorm_
> * 1.0e-2) {
> handler_->message(CLP_BARRIER_EXIT2, messages_)
> << saveIteration
> << CoinMessageEol;
> problemStatus_ = 0; // benefit of doubt
>
>
> Feel free to continue reading this area for other stopping rules.
> continues to the last break at line 485 ( I have source for
> 1.14.7 not.8).
> Searching for: sloppyOptimal it seems to be locally detected
> ClpPredictorCorrector.cpp(212): bool sloppyOptimal = false;
> ClpPredictorCorrector.cpp(275): if (!sloppyOptimal) {
> ClpPredictorCorrector.cpp(361): if (sloppyOptimal) {
> ClpPredictorCorrector.cpp(403): if ((gapO < 1.0e-6 || (gapO < 1.0e-4
> && complementarityGap_ < 0.1)) && !sloppyOptimal) {
> ClpPredictorCorrector.cpp(404): sloppyOptimal *= true;*
> ClpPredictorCorrector.cpp(417): if (saveIteration >= 0 && sloppyOptimal) {
>
> So if you keep your current scale for the problem you need to tweek
> the block around line 403 perhaps the bold blocke needs tweeking by
> relative ratio of gap to objective
The +1 is to shield small near 0 objective divisors and leave the test
approximately as the original test with a denominator near 1.
> say the bold gap0/(primalObjective_ * objScale -
> dblParam_[ClpObjOffset] +1.0) and same for *complementarityGap_*
> *18 Primal -1.3318263e+09 Dual -1.3318263e+09 Complementarity
> 40.006314 - 134 fixed, rank 3924 *
> if ((gapO < 1.0e-6 ||*(gapO < 1.0e-4 && complementarityGap_
> < 0.1)) && !sloppyOptimal)* {
> sloppyOptimal = true;
>
>
> Good luck
>
> William
>
> On 11/27/2012 10:50 AM, Stephanie Jakus wrote:
>> Dear Clp mailing list,
>> I'm using the Clp executable with the barrier method, and running
>> into problems where the complementarity value gets small and then
>> diverges. I'm wondering if there is an option to change the
>> convergence tolerance value for the complementarity when using the
>> barrier method. (I see the options for tolerance on primal and dual
>> feasibility... but are those enough?)
>> Thanks very much!
>> Sincerely,
>> Stephanie Jakus
>> Coin LP version 1.14.8, build Nov 26 2012
>>
>> Clp takes input from arguments ( - switches to stdin)
>>
>> Enter ? for list of commands or help
>>
>> Clp:import /cygdrive/c/Users/StephanieJ/Desktop/3892762.mps
>>
>> At line 8 NAME Model
>>
>> At line 9 ROWS
>>
>> At line 1364 COLUMNS
>>
>> At line 4998 RHS
>>
>> At line 5038 QUADOBJ
>>
>> Problem Model has 1353 rows, 1218 columns and 4830 elements
>>
>> At line 6257 ENDATA
>>
>> Model was imported from
>> /cygdrive/c/Users/StephanieJ/Desktop/3892762.mps in 0.015 seconds
>>
>> Clp:presolve off
>>
>> Clp:barr
>>
>> 911766 elements in sparse Cholesky, flop count 1.38983e+09
>>
>> 0 Primal 2.0281794e+14 Dual -5.1285362e+16 Complementarity
>> 5.7194998e+16 - 0 fixed, rank 3924
>>
>> 1 Primal 6.4401297e+11 Dual -1.4397286e+15 Complementarity
>> 4.5782888e+15 - 0 fixed, rank 3924
>>
>> 2 Primal 9.0405659e+10 Dual -6.7439781e+14 Complementarity
>> 1.8042711e+15 - 0 fixed, rank 3924
>>
>> 3 Primal -4.6446979e+08 Dual -2.2353578e+14 Complementarity
>> 2.5748948e+14 - 0 fixed, rank 3924
>>
>> 4 Primal -6.1493992e+08 Dual -4.9256197e+13 Complementarity
>> 5.1971454e+13 - 0 fixed, rank 3924
>>
>> 5 Primal -6.2519141e+08 Dual -9.5993463e+12 Complementarity
>> 9.8821256e+12 - 0 fixed, rank 3924
>>
>> 6 Primal -6.4251057e+08 Dual -6.5604007e+11 Complementarity
>> 6.6713932e+11 - 0 fixed, rank 3924
>>
>> 7 Primal -7.7860822e+08 Dual -3.6508427e+10 Complementarity
>> 3.6354368e+10 - 0 fixed, rank 3924
>>
>> 8 Primal -1.0644153e+09 Dual -7.4875479e+09 Complementarity
>> 6.5249957e+09 - 0 fixed, rank 3924
>>
>> 9 Primal -1.2085383e+09 Dual -3.5784324e+09 Complementarity
>> 2.4161606e+09 - 0 fixed, rank 3924
>>
>> 10 Primal -1.2797358e+09 Dual -2.1299084e+09 Complementarity
>> 8.6888912e+08 - 0 fixed, rank 3924
>>
>> 11 Primal -1.3185777e+09 Dual -1.4373535e+09 Complementarity
>> 1.2056077e+08 - 0 fixed, rank 3924
>>
>> 12 Primal -1.3295276e+09 Dual -1.3574632e+09 Complementarity 28320570
>> - 0 fixed, rank 3924
>>
>> 13 Primal -1.3314339e+09 Dual -1.3388477e+09 Complementarity
>> 7525528.9 - 0 fixed, rank 3924
>>
>> 14 Primal -1.3317815e+09 Dual -1.3331553e+09 Complementarity
>> 1386412.8 - 13 fixed, rank 3924
>>
>> 15 Primal -1.3318236e+09 Dual -1.3319518e+09 Complementarity
>> 128945.31 - 46 fixed, rank 3924
>>
>> 16 Primal -1.3318262e+09 Dual -1.3318287e+09 Complementarity 2519.259
>> - 76 fixed, rank 3924
>>
>> 17 Primal -1.3318263e+09 Dual -1.3318263e+09 Complementarity
>> 40.523345 - 134 fixed, rank 3924
>>
>> 18 Primal -1.3318263e+09 Dual -1.3318263e+09 Complementarity
>> 40.006314 - 134 fixed, rank 3924
>>
>> 19 Primal -1.3318263e+09 Dual -1.3318264e+09 Complementarity
>> 39.542777 - 134 fixed, rank 3924
>>
>> 20 Primal -1.3318263e+09 Dual -1.3318265e+09 Complementarity
>> 39.128027 - 134 fixed, rank 3924
>>
>> 21 Primal -1.3318263e+09 Dual -1.3318266e+09 Complementarity
>> 38.757635 - 134 fixed, rank 3924
>>
>> 22 Primal -1.3318263e+09 Dual -1.3318263e+09 Complementarity
>> 0.87384878 - 134 fixed, rank 3924
>>
>> 23 Primal -1.3318263e+09 Dual -1.331649e+09 Complementarity
>> 0.0061784205 - 134 fixed, rank 3924
>>
>> 24 Primal -1.3318263e+09 Dual -1.3047041e+09 Complementarity
>> 4.0066434e-05 - 134 fixed, rank 3924
>>
>> 25 Primal -1.3318262e+09 Dual 1.3928076e+09 Complementarity
>> 1.3321456e-05 - 134 fixed, rank 3924
>>
>> 26 Primal -1.3318262e+09 Dual 1.3945074e+09 Complementarity
>> 3.4243478e-06 - 134 fixed, rank 3924
>>
>> 27 Primal -1.3318262e+09 Dual 2.3040717e+11 Complementarity
>> 7.2045846e-07 - 134 fixed, rank 3924
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20121127/14cecb79/attachment-0001.html>
More information about the Clp
mailing list