pythongeometrydistancegekko

How would I implement the Hausdorff distance using Gekko?


If the following function took in arrays A and B that contain arrays of Gekko variables instead of floats, how would I find the Hausdorff distance, aka, how would I define np.inf and modify the rest of the code?

def hausdorff_distance(A, B):
  """
  Compute the Hausdorff distance between two sets of points A and B.
  """
  dist = 0
  for a in A:
    min_dist = np.inf
    for b in B:
      dist = np.linalg.norm(a - b)
      if dist < min_dist:
        min_dist = dist
    if min_dist > dist:
      dist = min_dist
  return dist

Solution

  • Use the m.min2() function to calculate the minimum of two values. Here is an example implementation of the minimum distance function with Gekko operators.

    from gekko import GEKKO
    import numpy as np
    
    def hausdorff_distance(A, B):
        """
        Compute the Hausdorff distance between two sets of points A and B,
        where A and B contain arrays of Gekko variables.
        """    
        j=0
        min_dist = 1e9
        for a in A:
            for b in B:
                diff = [a[i] - b[i] for i in range(2)]
                norm = m.Intermediate(m.sqrt(sum([diff[i]**2 for i in range(2)])))
                min_dist = m.Intermediate(m.min2(norm,min_dist))                
        return min_dist
    
    m = GEKKO(remote=False)
    A = m.Array(m.Var, (3,2))
    B = m.Array(m.Param, (3,2))
    
    # Assign values to A and B for demonstration
    np.random.seed(10)
    for i in range(3):
        for j in range(2):
            A[i,j].value = 5*np.random.random()
            B[i,j].value = 10*np.random.random()
    min_distance = hausdorff_distance(A, B)
    m.Equation(min_distance>=1)
    m.Minimize(min_distance)
    m.options.SOLVER = 'APOPT'
    m.solve(disp=True)
    print(f'Hausdorff Distance: {min_distance.value[0]}')
    

    There is a constraint that min_distance>=1 and the objective is to minimize min_distance. For these random numbers, it converges with the following solver output:

     ----------------------------------------------------------------
     APMonitor, Version 1.0.1
     APMonitor Optimization Suite
     ----------------------------------------------------------------
     
     
     --------- APM Model Size ------------
     Each time step contains
       Objects      :            9
       Constants    :            0
       Variables    :           40
       Intermediates:           18
       Connections  :           27
       Equations    :           38
       Residuals    :           20
     
     Number of state variables:             52
     Number of total equations: -           37
     Number of slack variables: -            1
     ---------------------------------------
     Degrees of freedom       :             14
     
     ----------------------------------------------
     Steady State Optimization with APOPT Solver
     ----------------------------------------------
     
     Iter    Objective  Convergence
        0  9.90552E+18  1.00000E+09
        1  2.38606E+11  1.00000E+09
        2  1.04285E+09  2.80978E+01
        3  1.03024E+09  2.43451E+01
        4  2.56078E+13  2.00741E+01
        5  1.01917E+09  2.00741E+01
        6  2.94752E+13  1.51037E+01
        7  1.00988E+09  1.51037E+01
        8  2.26979E+13  2.67173E+01
        9  1.76442E+11  2.67173E+01
     
     Iter    Objective  Convergence
       10  9.99849E+08  1.51037E+01
       11  9.98865E+08  3.91030E+06
       12  4.99434E+08  8.53990E+09
       13  9.12931E+06  1.24481E+12
       14  1.39486E+09  1.54845E+11
       15  6.87536E+07  1.51693E+11
       16  2.16440E+08  3.71750E+10
       17  1.64817E+21  3.63778E+10
       18  6.94013E+20  1.40348E+10
       19  2.19541E+21  5.90979E+09
     
     Iter    Objective  Convergence
       20  9.46806E+11  1.86947E+09
       21  1.00000E+00  8.06243E-01
       22  1.00000E+00  5.72972E-03
       23  1.00000E+00  3.86073E-04
       24  1.00000E+00  1.23727E-06
       25  1.00000E+00  4.54747E-13
       26  1.00000E+00  4.54747E-13
     Successful solution
     
     ---------------------------------------------------
     Solver         :  APOPT (v1.0)
     Solution time  :   1.619999999820720E-002 sec
     Objective      :    1.00000000000000     
     Successful solution
     ---------------------------------------------------
     
    Hausdorff Distance: 1.0
    

    Gekko calculates all of the distance norms simultaneously and uses MPCC function m.min2() for continuous derivatives that are compatible with the gradient-based optimizers. Another function is the m.min3() that uses binary variables, but then the problem becomes Mixed Integer Nonlinear Programming (MINLP) and may be more challenging to solve with the APOPT solver.