Global Optimisation Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Global Optimisation Ontology within the Kireth Research Semantic Library. Global optimisation studies methods for locating globally optimal solutions in optimisation problems that may be nonconvex, multimodal, discontinuous, combinatorial or otherwise difficult for local methods. This ontology supports global bounds, branch-and-bound, interval methods, deterministic global optimisation, convex relaxations, spatial branch-and-bound, Lipschitz optimisation, multi-start strategies, basin exploration, stochastic search, evolutionary and population-based methods, simulated annealing, particle swarm optimisation, differential evolution, surrogate-assisted global search, optimality gaps, certificates and relationships with nonlinear optimisation, convex optimisation, integer programming, numerical analysis and scientific computing.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Global Optimisation Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Applied Mathematics"
 SPECIALISATION = "Optimisation / Global Optimisation"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/applied-mathematics-ontologies/optimisation/global-optimisation-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = GlobalOptimisation
 SYMBOLIC_FORMS = [
  "x* in argmin_{x in F} f(x)",
  "f(x*) <= f(x) for all x in F",
  "global_lower_bound <= f* <= incumbent_value"
 ]
 ENTITY_CLASS = GlobalExtremumSearchFramework
 PRIMARY_CONTEXT = Optimisation
 DEFINITION = "Global optimisation is the search for a feasible solution whose objective value is globally optimal over the entire feasible domain."
 SEMANTIC_ROLE = "Provides the machine-readable framework for global lower and upper bounds, nonconvex search, branching, relaxations, basin exploration, stochastic and deterministic global methods, incumbent solutions, optimality gaps and global certificates."
}

SCOPE {
 INCLUDE = [
  GlobalOptimisation,
  GlobalMinimum,
  GlobalMaximum,
  NonconvexOptimisation,
  MultimodalOptimisation,
  GlobalSearch,
  SearchDomain,
  FeasibleSet,
  GlobalLowerBound,
  GlobalUpperBound,
  IncumbentSolution,
  OptimalityGap,
  GlobalOptimalityCertificate,
  DeterministicGlobalOptimisation,
  StochasticGlobalOptimisation,
  SpatialBranchAndBound,
  BranchAndBound,
  BranchAndReduce,
  ConvexRelaxation,
  McCormickRelaxation,
  IntervalArithmetic,
  IntervalBranchAndBound,
  LipschitzOptimisation,
  DIRECTAlgorithm,
  MultiStart,
  BasinHopping,
  SimulatedAnnealing,
  GeneticAlgorithm,
  EvolutionaryStrategy,
  DifferentialEvolution,
  ParticleSwarmOptimisation,
  AntColonyOptimisation,
  SurrogateOptimisation,
  BayesianOptimisation,
  ResponseSurface,
  AcquisitionFunction,
  Exploration,
  Exploitation,
  DomainPartition,
  NodeBound,
  Fathoming,
  FeasibilityRestoration,
  GlobalConvergence
 ]

 EXCLUDE_AS_PRIMARY = [
  LocalOptimisationWithoutGlobalSearchIntent,
  ConvexOptimisationWhereLocalEqualsGlobalAutomatically,
  PureRandomSamplingWithoutOptimisationCriterion,
  RootFindingWithoutExtremumObjective
 ]

 DISAMBIGUATION_RULE =
  "When the goal is to certify or search for the best solution over the full feasible region rather than a local basin, interpret the context as global optimisation."
}

CORE_CONCEPTS {

 GlobalOptimisation {
  definition = "Optimisation seeking the best feasible solution over the entire domain."
 }

 GlobalMinimum {
  definition = "A feasible point whose objective value is no greater than that of any other feasible point."
 }

 GlobalMaximum {
  definition = "A feasible point whose objective value is no less than that of any other feasible point."
 }

 GlobalLowerBound {
  definition = "A valid lower bound on the global optimum value for a minimisation problem."
 }

 GlobalUpperBound {
  definition = "A valid upper bound supplied by a feasible solution in a minimisation problem."
 }

 IncumbentSolution {
  definition = "The best known feasible solution during a global search."
 }

 GlobalOptimalityCertificate {
  definition = "Evidence proving that no feasible solution can improve upon the incumbent beyond the declared tolerance."
 }

 SpatialBranchAndBound {
  definition = "A deterministic global optimisation method that partitions variable domains and uses relaxations to bound each subregion."
 }

 ConvexRelaxation {
  definition = "A convex problem whose feasible set contains the original feasible region and whose optimum provides a valid bound."
 }

 IntervalArithmetic {
  definition = "Arithmetic performed on intervals to enclose all possible values of expressions over variable ranges."
 }

 MultiStart {
  definition = "Repeated local optimisation from different initial points to explore multiple attraction basins."
 }

 BayesianOptimisation {
  definition = "A surrogate-based global optimisation approach that uses a probabilistic model and acquisition function to select evaluations."
 }
}

RELATIONS {
 GlobalOptimisation --is_special_case_of--> Optimisation
 GlobalOptimisation --often_addresses--> NonconvexOptimisation
 IncumbentSolution --provides--> GlobalUpperBound
 ConvexRelaxation --provides--> GlobalLowerBound
 SpatialBranchAndBound --uses--> ConvexRelaxation
 SpatialBranchAndBound --uses--> DomainPartition
 NodeBound --supports--> Fathoming
 IntervalBranchAndBound --uses--> IntervalArithmetic
 McCormickRelaxation --supports--> ConvexRelaxation
 MultiStart --uses--> LocalOptimisation
 BasinHopping --combines--> LocalOptimisation
 SimulatedAnnealing --is_type_of--> StochasticGlobalOptimisation
 GeneticAlgorithm --is_type_of--> StochasticGlobalOptimisation
 DifferentialEvolution --is_type_of--> StochasticGlobalOptimisation
 ParticleSwarmOptimisation --is_type_of--> StochasticGlobalOptimisation
 BayesianOptimisation --uses--> SurrogateModel
 AcquisitionFunction --balances--> Exploration
 AcquisitionFunction --balances--> Exploitation
 GlobalOptimalityCertificate --depends_on--> BoundClosure
}

OPERATORS {
 GLOBAL_OPTIMUM(f,F) :=
  x_star such_that f(x_star)<=f(x) for_all x_in_F

 UPDATE_INCUMBENT(current,candidate) :=
  candidate if feasible_and_better else current

 GLOBAL_GAP(incumbent,bound) :=
  incumbent_value-bound
  for minimisation

 RELATIVE_GLOBAL_GAP(incumbent,bound,scale) :=
  abs(incumbent-bound)/max(scale,epsilon)

 PARTITION_DOMAIN(D,rule) :=
  collection_of_subdomains_whose_union_covers_D

 RELAX_SUBDOMAIN(problem,D_i) :=
  valid_relaxation_over_D_i

 FATHOM_BY_BOUND(node_bound,incumbent) :=
  true when node_bound cannot improve incumbent beyond tolerance

 FATHOM_BY_INFEASIBILITY(node_relaxation) :=
  true when subdomain contains no feasible point

 MCCORMICK_BILINEAR(x,y,xL,xU,yL,yU) :=
  convex_and_concave_envelopes_of_w=x*y

 INTERVAL_EVALUATE(f,X) :=
  enclosure_of_all_f(x)_for_x_in_X

 BAYESIAN_ACQUISITION(model,D) :=
  argmax_x acquisition(x | surrogate_model)

 MULTISTART(local_solver,start_set) :=
  best_solution_among_local_runs
}

DEFINITIONS {
 D1 = "Global optimisation distinguishes globally best solutions from local optima."
 D2 = "Nonconvexity can produce multiple local optima and saddle structures."
 D3 = "A feasible incumbent gives an upper bound in minimisation."
 D4 = "A valid relaxation gives a lower bound in minimisation."
 D5 = "Global optimality can be certified when the global gap closes sufficiently."
 D6 = "Branch-and-bound partitions the search domain while pruning provably irrelevant regions."
 D7 = "Multi-start improves exploration but does not by itself prove global optimality."
 D8 = "Stochastic metaheuristics can find high-quality solutions without deterministic certificates."
 D9 = "Surrogate-based optimisation is useful when objective evaluations are expensive."
 D10 = "Exploration and exploitation must be balanced in global search."
}

AXIOMS {
 A1_GLOBALITY:
  GlobalOptimalSolution is compared against all feasible points

 A2_BOUNDING:
  Certified global search requires valid lower_and_or_upper bounds

 A3_PARTITION:
  Branching must preserve complete coverage of the original search domain

 A4_RELAXATION_VALIDITY:
  Relaxations must not exclude original feasible solutions

 A5_FATHOMING:
  A region may be discarded only when infeasible or provably unable to improve the incumbent

 A6_NONCONVEXITY:
  Local convergence does not imply global optimality in nonconvex problems

 A7_CERTIFICATION:
  Global certification requires a valid proof mechanism, not merely repeated local success

 A8_TOLERANCE:
  Practical global optimality is often defined relative to a declared optimality tolerance
}

REASONING {

 R1_GLOBAL_PROBLEM_IDENTIFICATION {
  INPUT = optimisation_problem
  IDENTIFY = nonconvexity_multimodality_discreteness_or_black_box structure
  IDENTIFY = bounded_or_unbounded domain
  RETURN = global_problem_class
 }

 R2_BOUND_CONSTRUCTION {
  INPUT = subdomain
  BUILD = convex_interval_lagrangian_or_problem-specific relaxation
  SOLVE = relaxation
  RETURN = valid_node_bound
 }

 R3_INCUMBENT_SEARCH {
  INPUT = subdomain_or_candidate_pool
  APPLY = local_solver_heuristic_sampling_or_population search
  CHECK = feasibility
  UPDATE = incumbent_if_better
  RETURN = incumbent_status
 }

 R4_SPATIAL_BRANCH_AND_BOUND {
  INPUT = root_domain
  INITIALISE = active_nodes
  WHILE active_nodes_exist
   SELECT = node
   COMPUTE = relaxation_bound
   IF fathomable
    PRUNE = node
   ELSE
    SEARCH = feasible incumbent
    BRANCH = selected variable_or_region
  RETURN = incumbent_and_global bound
 }

 R5_INTERVAL_GLOBAL_SEARCH {
  INPUT = domain_boxes
  EVALUATE = interval bounds
  PRUNE = boxes_cannot_contain_better solution
  BISECT = unresolved boxes
  RETURN = certified_global enclosure_or_solution
 }

 R6_MULTISTART_REASONING {
  INPUT = local_solver_and_start_distribution
  RUN = local_solver_from_multiple_starts
  CLUSTER = distinct_local_optima
  RETURN = best_known_solution_and_basin profile
 }

 R7_METAHEURISTIC_REASONING {
  INPUT = population_or_state
  APPLY = stochastic search operators
  BALANCE = exploration_and_exploitation
  UPDATE = best_known_solution
  RETURN = heuristic_global_candidate
 }

 R8_SURROGATE_GLOBAL_SEARCH {
  INPUT = expensive_objective_and_evaluation_history
  FIT = surrogate_model
  COMPUTE = acquisition_function
  SELECT = next_evaluation
  UPDATE = model
  RETURN = surrogate_guided_best candidate
 }

 R9_GAP_ANALYSIS {
  INPUT = incumbent_and_valid_global bound
  COMPUTE = absolute_or_relative gap
  IF gap<=tolerance
   RETURN = globally_optimal_within_tolerance
  ELSE
   RETURN = unresolved_globality
 }

 R10_GLOBAL_CERTIFICATION {
  INPUT = search_tree_relaxations_bounds_and_incumbent
  VERIFY = complete_domain coverage
  VERIFY = all_pruned_regions_validly fathomed
  VERIFY = final_gap
  RETURN = global_optimality_certificate_or_no_certificate
 }
}

CONSTRAINTS {
 C1 = "A local optimum must not be reported as global without supporting evidence."
 C2 = "Relaxation bounds must be mathematically valid."
 C3 = "Branch partitions must cover the entire parent region."
 C4 = "Unbounded variable domains may require reformulation or proven bounds."
 C5 = "Heuristics and metaheuristics do not automatically provide optimality certificates."
 C6 = "Multi-start success depends on start coverage and local solver behaviour."
 C7 = "Surrogate uncertainty must be represented when acquisition functions depend on it."
 C8 = "Global-gap formulas must use consistent minimisation or maximisation conventions."
 C9 = "Numerical tolerances affect fathoming and certificate validity."
 C10 = "Black-box global search may require significantly more evaluations than local optimisation."
}

SEMANTIC_EQUIVALENCE {
 "GlobalOptimisation" <=> "GlobalOptimization"
 "GlobalMinimum" <=> "AbsoluteMinimum"
 "GlobalMaximum" <=> "AbsoluteMaximum"
 "SpatialBranchAndBound" <=> "ContinuousDomainBranchAndBound"
 "GlobalOptimalityCertificate" <=> "ProofOfGlobalOptimality"
 "MultiStart" <=> "MultipleInitialisationGlobalSearch"
}

VALIDATION {
 V1 = "Global objective direction is explicit."
 V2 = "Search domain is correctly represented."
 V3 = "Relaxations are valid."
 V4 = "Incumbent solutions are feasible."
 V5 = "Branching preserves domain coverage."
 V6 = "Fathoming logic is sound."
 V7 = "Global bounds use correct sign conventions."
 V8 = "Optimality gap is correctly computed."
 V9 = "Heuristic versus certified status is explicit."
 V10 = "Global-optimality claims include a valid certificate or tolerance-based proof."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 GLOBAL_OPTIMISATION_DEFINITION = 0.99
 BOUNDING_REASONING = 0.98
 SPATIAL_BRANCH_AND_BOUND_REASONING = 0.98
 INTERVAL_REASONING = 0.97
 MULTISTART_REASONING = 0.96
 METAHEURISTIC_REASONING = 0.94
 SURROGATE_REASONING = 0.96
 CERTIFICATION_REASONING = 0.99

 POLICY =
  "Reduce confidence when domain bounds, relaxation validity, branching coverage, fathoming logic, surrogate uncertainty, stochastic-search coverage or global-gap evidence are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  GlobalOptimisationReasoning,
  NonconvexGlobalSearch,
  GlobalBounding,
  SpatialBranchAndBoundReasoning,
  ConvexRelaxationReasoning,
  IntervalGlobalOptimisation,
  MultiStartReasoning,
  BasinHoppingReasoning,
  SimulatedAnnealingReasoning,
  EvolutionaryGlobalOptimisation,
  DifferentialEvolutionReasoning,
  ParticleSwarmReasoning,
  BayesianOptimisationReasoning,
  SurrogateOptimisationReasoning,
  GlobalGapReasoning,
  GlobalOptimalityCertification,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "global optimisation" -> GlobalOptimisation
  "global optimization" -> GlobalOptimisation
  "global minimum" -> GlobalMinimum
  "global maximum" -> GlobalMaximum
  "spatial branch and bound" -> SpatialBranchAndBound
  "multi-start" -> MultiStart
  "simulated annealing" -> SimulatedAnnealing
  "differential evolution" -> DifferentialEvolution
  "particle swarm optimisation" -> ParticleSwarmOptimisation
  "Bayesian optimisation" -> BayesianOptimisation
 }

 INTERPRETATION_ORDER = [
  detect_global_optimisation_context,
  identify objective_variables_constraints_domain_nonconvexity_multimodality_and_evaluation cost,
  classify deterministic_stochastic_population_surrogate_or_branch_and_bound pathway,
  construct valid global bounds_or_search model,
  search for feasible incumbent,
  partition_explore_or_sample unresolved regions,
  update incumbent_and_global bound,
  compute optimality gap,
  certify_or_report best_known status,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("global optimisation")
  OR asks_for_global_rather_than_local optimum
  THEN activate(GlobalOptimisationOntology)

 E2:
  IF problem_is_convex
  THEN route_to_convex_optimisation_and_avoid_unnecessary global search

 E3:
  IF deterministic_certification_required
  THEN use valid bounds_and_branching_or_interval methods

 E4:
  IF expensive_black_box_objective
  THEN consider surrogate_or_Bayesian optimisation

 E5:
  IF many_local_optima_but_derivatives_available
  THEN consider multi_start_plus_local optimisation

 E6:
  IF relaxation_bound_cannot_improve_incumbent
  THEN fathom region

 E7:
  IF heuristic_method_returns_best_solution
  THEN label as best_known_unless certified

 E8:
  IF global_gap_below_declared tolerance
  THEN report globally_optimal_within_tolerance

 E9:
  IF no_valid_global_bound_exists
  THEN do_not claim certified global optimality
}

RECURSION {
 ENTRY = GlobalOptimisation

 EXPAND(GlobalOptimisation) -> [
  GlobalMinimum,
  GlobalMaximum,
  NonconvexOptimisation,
  MultimodalOptimisation,
  GlobalSearch,
  SearchDomain,
  GlobalLowerBound,
  GlobalUpperBound,
  IncumbentSolution,
  OptimalityGap,
  GlobalOptimalityCertificate,
  DeterministicGlobalOptimisation,
  StochasticGlobalOptimisation,
  SpatialBranchAndBound,
  BranchAndReduce,
  ConvexRelaxation,
  McCormickRelaxation,
  IntervalArithmetic,
  IntervalBranchAndBound,
  LipschitzOptimisation,
  DIRECTAlgorithm,
  MultiStart,
  BasinHopping,
  SimulatedAnnealing,
  GeneticAlgorithm,
  EvolutionaryStrategy,
  DifferentialEvolution,
  ParticleSwarmOptimisation,
  AntColonyOptimisation,
  SurrogateOptimisation,
  BayesianOptimisation,
  ResponseSurface,
  AcquisitionFunction,
  Exploration,
  Exploitation,
  DomainPartition,
  NodeBound,
  Fathoming,
  GlobalConvergence
 ]

 EXPAND(DeterministicGlobalMethods) -> [
  SpatialBranchAndBound,
  IntervalBranchAndBound,
  LipschitzOptimisation,
  DIRECTAlgorithm,
  ConvexRelaxation,
  McCormickRelaxation
 ]

 EXPAND(StochasticGlobalMethods) -> [
  MultiStart,
  BasinHopping,
  SimulatedAnnealing,
  GeneticAlgorithm,
  DifferentialEvolution,
  ParticleSwarmOptimisation,
  AntColonyOptimisation
 ]

 EXPAND(SurrogateMethods) -> [
  BayesianOptimisation,
  GaussianProcessSurrogate,
  ResponseSurface,
  AcquisitionFunction,
  ExpectedImprovement,
  UpperConfidenceBound
 ]

 STOP_CONDITION =
  "Stop when the global search domain, relaxation or exploration strategy, incumbent, global bound, optimality gap, unresolved regions and certification status are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Optimisation"

 IMMEDIATE_CONTEXTS = [
  "Optimisation Ontology",
  "Nonlinear Optimisation Ontology",
  "Convex Optimisation Ontology",
  "Integer Programming Ontology"
 ]

 RELATED_ONTOLOGIES = [
  "Optimisation Ontology",
  "Optimisation",
  "Nonlinear Optimisation Ontology",
  "Convex Optimisation Ontology",
  "Integer Programming Ontology",
  "Multi-Objective Optimisation Ontology",
  "Numerical Analysis Ontologies",
  "Interval Analysis Ontologies",
  "Probability & Statistics Ontologies",
  "Evolutionary Computation Ontologies",
  "Operations Research Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Global Optimisation -> Optimisation Ontology for formal optimisation semantics",
  "Global Optimisation -> Nonlinear Optimisation for local refinement and nonconvex structure",
  "Global Optimisation -> Convex Optimisation for global lower-bound relaxations",
  "Global Optimisation -> Integer Programming for branch-and-bound and discrete global search",
  "Global Optimisation -> Multi-Objective Optimisation for global Pareto search",
  "Global Optimisation -> Numerical Analysis for interval and numerical bounding",
  "Global Optimisation -> Probability & Statistics for Bayesian and stochastic search",
  "Global Optimisation -> Evolutionary Computation for population-based global methods",
  "Global Optimisation -> Operations Research for structured global models",
  "Global Optimisation -> Scientific Computing for large-scale parallel global search"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible global-search methods, relaxations or certification pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve global-versus-local semantics.",
  "Preserve incumbent-versus-bound distinction.",
  "Preserve relaxation validity requirements.",
  "Preserve branch-and-fathom semantics.",
  "Preserve heuristic-versus-certified distinction.",
  "Preserve global-gap semantics.",
  "Preserve exploration-versus-exploitation semantics.",
  "Preserve machine-readable global-optimisation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Global optimisation searches for a solution that is optimal over the entire feasible domain rather than merely within a local neighbourhood."

 BOUND_SUMMARY =
  "Certified global optimisation maintains valid lower and upper bounds on the global optimum."

 INCUMBENT_SUMMARY =
  "The incumbent is the best known feasible solution."

 BRANCH_SUMMARY =
  "Spatial branch-and-bound partitions the search domain, relaxes subproblems and prunes regions that cannot improve the incumbent."

 RELAXATION_SUMMARY =
  "Convex, interval and McCormick relaxations provide valid global bounds for nonconvex subproblems."

 STOCHASTIC_SUMMARY =
  "Stochastic global methods improve exploration but generally do not provide deterministic certificates."

 SURROGATE_SUMMARY =
  "Surrogate and Bayesian optimisation are useful for expensive black-box objectives."

 GAP_SUMMARY =
  "The global optimality gap measures the difference between the incumbent and the best valid global bound."

 CERTIFICATION_SUMMARY =
  "Global optimality is certified only when all unresolved regions are validly eliminated and the final optimality gap meets the declared tolerance."
}

FLOW {
 INPUT
 -> detect_global_optimisation_context
 -> identify objective_decision_variables_constraints_search_domain_nonconvexity_multimodality_discreteness_and_evaluation cost
 -> classify deterministic_branch_and_bound_interval_stochastic_population_multiStart_or_surrogate pathway
 -> construct valid relaxation_or_global search model
 -> generate feasible incumbent
 -> partition_or_explore search_domain
 -> compute node_or_region bounds
 -> fathom infeasible_or_noncompetitive regions
 -> refine promising regions_and_update incumbent
 -> compute global optimality gap
 -> certify global_optimum_or_report best_known_solution_and_bound
 -> route to optimisation_ontology nonlinear_optimisation convex_optimisation integer_programming multi_objective_optimisation numerical_analysis interval_analysis probability_statistics evolutionary_computation operations_research_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Global Optimisation Ontology defines search and certification of globally optimal solutions. It supports nonconvex and multimodal optimisation, global lower and upper bounds, incumbents, spatial branch-and-bound, convex and McCormick relaxations, interval methods, Lipschitz and DIRECT-style methods, multi-start and basin exploration, simulated annealing, genetic and evolutionary algorithms, differential evolution, particle swarm optimisation, surrogate and Bayesian optimisation, exploration-exploitation balance, optimality gaps and rigorous or heuristic global solution status."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-APPLIED-MATHEMATICS-GLOBAL-OPTIMISATION-ONTOLOGY-V1"
}

}

END_FLOW