View Issue Details

IDProjectCategoryView StatusDate SubmittedLast Update
0025419Open CASCADEOCCT:Modeling Algorithmspublic2014-10-24 12:262015-11-10 07:16
ReporternbvAssigned Toabv 
PrioritynormalSeverityminor 
Status closedResolutionwon't fix 
Summary0025419: There is a case when math_GlobOptMin tool finds not global extremum
DescriptionThere is one-dimension function F(t) (in fact, it is square of distance multiplied on (-1)). It is necessary to find its global minimum.

math_GlobOptMin returns F(39.411308787568416) = -1536.0297734883532
However, F(39.398790420829584) = -2560.8628802440339.

(range of t-parameter changing is 12.323733986517...39.443381503357998)

I.e. value found by math_GlobOptMin is not global minimum.

Steps To Reproducerestore f.brep
explode f e
copy f_1 e

mksurf ss f
mkcurve c3d e
mk2dcurve c2d e f

checkcos c3d c2d ss
Additional information
and documentation updates		class CheckFunction : public math_MultipleVarFunctionWithHessian
{
public:
  CheckFunction(CheckFunction&);
  CheckFunction( const Handle(Geom_Curve)& theC3D,
                              const Handle(Geom2d_Curve)& theC2D,
                              const Handle(Geom_Surface)& theSurf);

  virtual Standard_Integer NbVariables() const
  {
    return 1;
  }

  virtual Standard_Boolean Value(const math_Vector& X,Standard_Real& F);
  virtual Standard_Integer GetStateNumber()
  {
    return 0;
  }

  virtual Standard_Boolean Gradient(const math_Vector& X,math_Vector& G);
  virtual Standard_Boolean Values(const math_Vector& X,
                                  Standard_Real& F,
                                  math_Vector& G);
  virtual Standard_Boolean Values(const math_Vector& X,
                                  Standard_Real& F,
                                  math_Vector& G,
                                  math_Matrix& H);

private:
  Handle(Geom_Curve) my3DCurve;
  Handle(Geom2d_Curve) my2DCurve;
  Handle(Geom_Surface) mySurf;
};

CheckFunction::CheckFunction( const Handle(Geom_Curve)& theC3D,
                              const Handle(Geom2d_Curve)& theC2D,
                              const Handle(Geom_Surface)& theSurf):
my3DCurve(theC3D),
my2DCurve(theC2D),
mySurf(theSurf)
{
}
                  
Standard_Boolean CheckFunction::Value( const math_Vector& theX,
                                                    Standard_Real& theFVal)
{
  try
  {
    const Standard_Real aPar = theX(1);

    gp_Pnt aP1, aP2;
    gp_Pnt2d aP2d;
    my3DCurve->D0(aPar, aP1);
    my2DCurve->D0(aPar, aP2d);
    mySurf->D0(aP2d.X(), aP2d.Y(), aP2);

    theFVal = -1.0*aP1.SquareDistance(aP2);
  }
  catch(...)
  {
    return Standard_False;
  }

  return Standard_True;
}

Standard_Boolean CheckFunction::Gradient(const math_Vector& theX,
                                                      math_Vector& theGrad)
{
  try
  {
    const Standard_Real aPar = theX(1);

    gp_Pnt aP1, aP2;
    gp_Vec aDC3D, aDSU, aDSV;
    gp_Pnt2d aP2d;
    gp_Vec2d aDC2D;

    my3DCurve->D1(aPar, aP1, aDC3D);
    my2DCurve->D1(aPar, aP2d, aDC2D);
    mySurf->D1(aP2d.X(), aP2d.Y(), aP2, aDSU, aDSV);

    aP1.SetXYZ(aP1.XYZ() - aP2.XYZ());
    aP2.SetXYZ(aDC3D.XYZ() - aDC2D.X()*aDSU.XYZ() - aDC2D.Y()*aDSV.XYZ());

    theGrad(1) = -2.0*aP1.XYZ().Dot(aP2.XYZ());
  }
  catch(...)
  {
    return Standard_False;
  }

  return Standard_True;
}

Standard_Boolean CheckFunction::Values(const math_Vector& theX,
                                                    Standard_Real& theVal,
                                                    math_Vector& theGrad)
{
  if(!Value(theX, theVal))
    return Standard_False;

  if(!Gradient(theX, theGrad))
    return Standard_False;

  return Standard_True;
}

Standard_Boolean CheckFunction::Values(const math_Vector& theX,
                                                    Standard_Real& theVal,
                                                    math_Vector& theGrad,
                                                    math_Matrix& theHessian)
{
  if(!Value(theX, theVal))
    return Standard_False;

  if(!Gradient(theX, theGrad))
    return Standard_False;

  theHessian(1,1) = theGrad(1);

  return Standard_True;
}


static Standard_Integer checkcos (Draw_Interpretor& theDI,
                                  Standard_Integer theArgNb,
                                  const char** theArgVec)
{
  if(theArgNb < 4)
  {
    theDI << "use checkcos 3d-curve 2d-curve surface\n";
    return 1;
  }

  Handle(Geom_Curve) aC = DrawTrSurf::GetCurve(theArgVec[1]);
  Handle(Geom2d_Curve) aC2d = DrawTrSurf::GetCurve2d(theArgVec[2]);
  Handle(Geom_Surface) aSurf = DrawTrSurf::GetSurface(theArgVec[3]);

  if(aC.IsNull() || aC2d.IsNull() || aSurf.IsNull())
  {
    theDI << "type mismatch\n";
    return 1;
  }

  Standard_Real aFirst = aC->FirstParameter(),
                aLast = aC->LastParameter();

  theDI << "Range: " << aFirst << "..." << aLast <<"\n";

  Standard_Real aBestParam = 0.0, aBestValue = 0.0;

  CheckFunction aFunc(aC, aC2d, aSurf);

  math_Vector anOutputParam(1, 1);

  anOutputParam(1) = 39.398790420829584 ;
  aFunc.Value(anOutputParam, aBestValue);
  theDI << "Expected value: F(" << anOutputParam(1) << ") = " << aBestValue <<"\n";

  //////
  aBestValue = 0.0;

  math_Vector aFirstV(1, 1), aLastV(1, 1);
  aFirstV(1) = aFirst;
  aLastV(1) = aLast;

  math_GlobOptMin aFinder(&aFunc, aFirstV, aLastV);
  aFinder.SetTol(1.0e-2, 1.0e-3);
  aFinder.Perform();

  const Standard_Integer aNbExtr = aFinder.NbExtrema();
  for(Standard_Integer i = 1; i <= aNbExtr; i++)
  {
    Standard_Real aValue = 0.0;
    aFinder.Points(i, anOutputParam);
    aFunc.Value(anOutputParam, aValue);
    
    if(aValue < aBestValue)
    {
      aBestValue = aValue;
      aBestParam = anOutputParam(1);
    }
  }

  theDI << "Value found: F(" << aBestParam << ") = " << aBestValue <<"\n";


  return 0;
}

TagsNo tags attached.
Test case number

Attached Files

Activities

nbv

2014-10-24 12:29

developer  

f.brep (91,482 bytes)

aml

2014-11-26 09:11

developer  

graphic_zoom.jpg (81,345 bytes)   

aml

2014-11-26 09:11

developer  

graphic_full.jpg (99,580 bytes)   

aml

2014-11-26 09:12

developer  

data.7z (286,815 bytes)

aml

2014-11-26 09:28

developer   ~0034687

Last edited: 2014-11-26 09:34

 Dear nbv,

I fail explanation:
There is bad objective function, on such functions only stochastic methods are applicable without optimum find guarantee. In terms of GlobOptMin method, we try to optimize function with too big Lipschitz constant (> 100 000).

II Solution:
It is not possible to modify GlobOptMin algorithm to work over such functions. Moreover, almost all first order and second order methods cannot used to find optimum.

It seems that algorithm which produce such data work wrong.

nbv

2014-11-26 10:46

developer   ~0034693

Last edited: 2015-10-28 17:24

 Unfortunately, this bug was observed on customer data (shapes) (bug is child of #0025410). Therefore, it is important to get correct result (global minimum of this function).

On the other hand, the target function is very specific. It is quite strange for current algorithm to find the value, where function is equal to ~(-1536) because its values are equal to 0 (~ 10^(-20)) almost in all points of the domain. In my point of view, it is connected with that the minimum found is near to the domain boundaries. If same minimum were near to middle point of domain then GlobOptMin method would work wrong.

At present, we are recommending customer to rebuild this shape to obtain pcurve of the edge with help of OCCT ProjLib algorithm. Therefore, I hope customer not to work with that target function in the future. Consequently, it is not necessary to create workarounds to fix this problem (because I do not know good method, which finds optimal value of same function - enumerative technique is excepted).

Conclusion:
1. In my point of view, this bug should be closed because we cannot offer a good solution to fix it.
2. We should avoid to work with analogical shapes (it was read from customer *.igs-file) because this case is limitation for OCCT algorithms. And we cannot detect these cases automatically.

nbv

2014-11-26 10:47

developer   ~0034694

Dear Andrey.

Please close this issue.

Issue History

Date Modified Username Field Change
2014-10-24 12:26 nbv New Issue
2014-10-24 12:26 nbv Assigned To => aml
2014-10-24 12:29 nbv File Added: f.brep
2014-10-24 12:44 nbv Description Updated
2014-11-26 09:11 aml File Added: graphic_zoom.jpg
2014-11-26 09:11 aml File Added: graphic_full.jpg
2014-11-26 09:12 aml File Added: data.7z
2014-11-26 09:28 aml Note Added: 0034687
2014-11-26 09:28 aml Assigned To aml => nbv
2014-11-26 09:28 aml Status new => feedback
2014-11-26 09:34 aml Note Edited: 0034687
2014-11-26 10:46 nbv Note Added: 0034693
2014-11-26 10:47 nbv Assigned To nbv => abv
2014-11-26 10:47 nbv Note Added: 0034694
2015-10-28 17:22 msv Summary There is a case when math_GlobOptMin tol finds not global extremum => There is a case when math_GlobOptMin tool finds not global extremum
2015-10-28 17:24 msv Note Edited: 0034693
2015-10-28 17:28 msv Target Version 7.0.0 => Unscheduled
2015-11-10 07:16 abv Status feedback => closed
2015-11-10 07:16 abv Resolution open => won't fix
2015-11-10 07:16 abv Target Version Unscheduled =>