Optimisation

AI INTERPRETATION NOTE
This Flow Algebra defines the Optimisation layer within the Kireth Research Semantic Library. Optimisation studies mathematical methods for finding the best feasible solution according to a declared objective. This parent ontology connects unconstrained and constrained optimisation, convex and nonconvex optimisation, linear and nonlinear programming, integer and combinatorial optimisation, multiobjective optimisation, stochastic optimisation, dynamic optimisation, variational methods, optimal control, numerical optimisation and operations research. It provides the semantic routing layer for objectives, decision variables, feasible sets, constraints, optimality conditions, algorithms, duality, sensitivity and solution quality.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = Optimisation
 SYMBOLIC_FORMS = [
  "min_x f(x)",
  "max_x f(x)",
  "min f(x) subject to g_i(x)<=0, h_j(x)=0"
 ]
 ENTITY_CLASS = MathematicalDecisionAndExtremumFramework
 PRIMARY_CONTEXT = AppliedMathematics
 DEFINITION = "Optimisation is the mathematical study of finding decision-variable values that minimise or maximise an objective while satisfying any declared constraints."
 SEMANTIC_ROLE = "Provides the parent semantic framework for objective functions, decision variables, feasible sets, constraints, local and global optima, optimality conditions, duality, algorithms, sensitivity and optimisation under uncertainty."
}

SCOPE {
 INCLUDE = [
  Optimisation,
  OptimisationProblem,
  ObjectiveFunction,
  DecisionVariable,
  FeasibleSet,
  Constraint,
  EqualityConstraint,
  InequalityConstraint,
  BoundConstraint,
  UnconstrainedOptimisation,
  ConstrainedOptimisation,
  LocalOptimum,
  GlobalOptimum,
  Minimum,
  Maximum,
  ConvexOptimisation,
  NonconvexOptimisation,
  LinearProgramming,
  NonlinearProgramming,
  QuadraticProgramming,
  IntegerProgramming,
  MixedIntegerProgramming,
  CombinatorialOptimisation,
  MultiobjectiveOptimisation,
  StochasticOptimisation,
  RobustOptimisation,
  DynamicOptimisation,
  OptimalControl,
  GradientMethod,
  NewtonMethod,
  QuasiNewtonMethod,
  TrustRegionMethod,
  LineSearch,
  LagrangeMultiplier,
  KarushKuhnTuckerConditions,
  Duality,
  SensitivityAnalysis,
  OptimalityGap
 ]

 EXCLUDE_AS_PRIMARY = [
  RootFindingWithoutObjective,
  PureEquationSolvingWithoutExtremumGoal,
  StatisticalEstimationWithoutOptimisationContext,
  DecisionMakingWithoutMathematicalObjectiveOrFeasibleSet
 ]

 DISAMBIGUATION_RULE =
  "When a problem seeks the best feasible value of decision variables according to an objective function, interpret the context as optimisation."
}

CORE_CONCEPTS {

 Optimisation {
  definition = "The mathematical process of selecting the best feasible solution according to an objective."
 }

 OptimisationProblem {
  definition = "A mathematical specification consisting of an objective, decision variables and optional constraints."
 }

 ObjectiveFunction {
  definition = "A scalar-valued function to be minimised or maximised."
 }

 DecisionVariable {
  definition = "A quantity whose value may be chosen by the optimisation process."
 }

 FeasibleSet {
  definition = "The set of decision-variable values satisfying all constraints."
 }

 Constraint {
  definition = "A restriction on admissible decision-variable values."
 }

 LocalOptimum {
  definition = "A feasible point that is optimal within some neighbourhood."
 }

 GlobalOptimum {
  definition = "A feasible point whose objective value is optimal over the entire feasible set."
 }

 ConvexOptimisation {
  definition = "Optimisation of a convex objective over a convex feasible set in minimisation form."
 }

 Duality {
  definition = "A relationship between a primal optimisation problem and an associated dual problem providing bounds, interpretation or optimality conditions."
 }

 SensitivityAnalysis {
  definition = "Analysis of how optimal solutions or objective values change under perturbations to problem data."
 }
}

RELATIONS {
 Optimisation --is_branch_of--> AppliedMathematics
 OptimisationProblem --has--> ObjectiveFunction
 OptimisationProblem --has--> DecisionVariable
 OptimisationProblem --may_have--> Constraint
 Constraint --defines--> FeasibleSet
 LocalOptimum --is_candidate_solution_of--> OptimisationProblem
 GlobalOptimum --is_solution_of--> OptimisationProblem
 ConvexOptimisation --is_special_case_of--> Optimisation
 LinearProgramming --is_special_case_of--> ConvexOptimisation
 QuadraticProgramming --may_be_special_case_of--> ConvexOptimisation
 IntegerProgramming --is_special_case_of--> DiscreteOptimisation
 MultiobjectiveOptimisation --has_multiple--> ObjectiveFunction
 StochasticOptimisation --contains--> RandomQuantity
 RobustOptimisation --protects_against--> UncertaintySet
 LagrangeMultiplier --is_associated_with--> Constraint
 KarushKuhnTuckerConditions --characterise--> ConstrainedLocalOptimality
 Duality --relates--> PrimalProblem
 Duality --relates--> DualProblem
}

OPERATORS {
 FORM_OPTIMISATION_PROBLEM(objective,variables,constraints) :=
  formal_optimisation_problem

 FEASIBLE(x,constraints) :=
  all_constraints_satisfied

 OBJECTIVE_VALUE(f,x) :=
  f(x)

 ARGMIN(f,F) :=
  set_of_x_in_F_with_minimum_objective

 ARGMAX(f,F) :=
  set_of_x_in_F_with_maximum_objective

 GRADIENT_STEP(x,alpha,grad_f) :=
  x-alpha*grad_f(x)

 NEWTON_STEP(x,grad_f,H) :=
  x-H(x)^(-1)*grad_f(x)
  WHEN H_invertible

 LAGRANGIAN(f,g,h,lambda,nu) :=
  f(x)+sum_i lambda_i*g_i(x)+sum_j nu_j*h_j(x)

 KKT_CHECK(x,lambda,nu) :=
  primal_feasibility
  AND dual_feasibility
  AND complementary_slackness
  AND stationarity

 OPTIMALITY_GAP(primal_value,dual_bound) :=
  primal_value-dual_bound
  for minimisation under consistent conventions

 PARETO_DOMINATES(x,y) :=
  no_worse_in_all_objectives AND strictly_better_in_at_least_one
}

DEFINITIONS {
 D1 = "An optimisation problem combines an objective with a feasible set."
 D2 = "A feasible point satisfies all constraints."
 D3 = "A local optimum need not be globally optimal."
 D4 = "Convex optimisation provides strong global optimality properties."
 D5 = "First-order optimality conditions involve gradients or subgradients."
 D6 = "Second-order conditions use curvature information such as the Hessian."
 D7 = "Lagrange multipliers encode sensitivity to active constraints under suitable regularity."
 D8 = "KKT conditions generalise constrained first-order optimality conditions."
 D9 = "Dual problems can provide lower or upper bounds on primal optima."
 D10 = "Multiobjective optimisation may produce a Pareto set rather than a single optimum."
}

AXIOMS {
 A1_OBJECTIVE:
  Every optimisation problem has an objective or ordered set of objectives

 A2_DECISION:
  Optimisation acts over decision variables

 A3_FEASIBILITY:
  Feasible solutions satisfy all declared constraints

 A4_OPTIMALITY:
  An optimum is defined relative to the feasible set and objective

 A5_LOCAL_GLOBAL_DISTINCTION:
  Local and global optimality are distinct except under special structural assumptions

 A6_CONVEXITY:
  In convex minimisation, every local optimum is global

 A7_DUALITY:
  Dual problems provide bounds on primal objectives under weak duality

 A8_CONSTRAINT_QUALIFICATION:
  Strong constrained optimality statements may require regularity or constraint qualification assumptions
}

REASONING {

 R1_PROBLEM_FORMULATION {
  INPUT = optimisation_task
  IDENTIFY = decision_variables
  IDENTIFY = objective
  IDENTIFY = constraints
  IDENTIFY = variable_domains
  RETURN = optimisation_problem
 }

 R2_PROBLEM_CLASSIFICATION {
  INPUT = optimisation_problem
  CLASSIFY = unconstrained_or_constrained
  CLASSIFY = continuous_or_discrete
  CLASSIFY = convex_or_nonconvex
  CLASSIFY = deterministic_or_stochastic
  CLASSIFY = single_or_multiobjective
  RETURN = optimisation_class
 }

 R3_FEASIBILITY_ANALYSIS {
  INPUT = constraints_and_candidate
  CHECK = equality_inequality_bounds_and_integrality
  RETURN = feasible_or_infeasible
 }

 R4_FIRST_ORDER_ANALYSIS {
  INPUT = differentiable_objective_and_constraints
  COMPUTE = gradients
  APPLY = stationarity_or_KKT conditions
  RETURN = first_order_candidate set
 }

 R5_SECOND_ORDER_ANALYSIS {
  INPUT = candidate_and_Hessian_or_Lagrangian Hessian
  ANALYSE = curvature_on_feasible_directions
  RETURN = local_min_max_saddle_or_inconclusive
 }

 R6_ALGORITHM_SELECTION {
  INPUT = problem_class
  IF unconstrained_smooth
   CONSIDER = gradient_Newton_quasiNewton_trustRegion
  IF constrained_smooth
   CONSIDER = SQP_interiorPoint_augmentedLagrangian
  IF linear
   CONSIDER = simplex_or_interiorPoint
  IF integer
   CONSIDER = branchAndBound_branchAndCut_or_dynamic methods
  IF stochastic
   CONSIDER = stochastic_gradient_sample_average_or_robust methods
  RETURN = optimisation_strategy
 }

 R7_DUALITY_ANALYSIS {
  INPUT = primal_problem
  FORM = Lagrangian_and_dual_function
  DERIVE = dual_problem
  COMPUTE = dual_bound
  RETURN = duality_profile
 }

 R8_MULTIObjective_ANALYSIS {
  INPUT = multiple_objectives
  IDENTIFY = preference_or_weighting structure
  COMPUTE = Pareto_candidates
  RETURN = Pareto_front_or_selected compromise
 }

 R9_SENSITIVITY_ANALYSIS {
  INPUT = optimal_solution_and_problem_data
  PERTURB = objective_constraints_or_parameters
  ESTIMATE = changes_in_solution_and_value
  RETURN = sensitivity_profile
 }

 R10_SOLUTION_VERIFICATION {
  INPUT = candidate_solution
  CHECK = feasibility
  CHECK = stationarity_or_problem-specific optimality
  CHECK = optimality_gap_or_global bound when available
  RETURN = optimisation_solution_status
 }
}

CONSTRAINTS {
 C1 = "The objective direction, minimisation or maximisation, must be explicit."
 C2 = "Decision variables and fixed parameters must not be conflated."
 C3 = "A low objective value does not imply feasibility."
 C4 = "Stationarity alone does not imply local optimality."
 C5 = "Local optimality does not imply global optimality in nonconvex problems."
 C6 = "KKT necessity may require constraint qualifications."
 C7 = "Strong duality does not hold for every optimisation problem."
 C8 = "Integer constraints fundamentally change problem structure."
 C9 = "Multiobjective problems require preference or Pareto interpretation."
 C10 = "Numerical solver termination does not by itself prove optimality."
}

SEMANTIC_EQUIVALENCE {
 "Optimisation" <=> "MathematicalOptimisation"
 "Optimization" <=> "Optimisation"
 "ObjectiveFunction" <=> "CriterionFunction"
 "DecisionVariable" <=> "OptimisationVariable"
 "FeasibleSet" <=> "ConstraintSatisfyingSet"
 "GlobalOptimum" <=> "BestFeasibleSolution"
 "Duality" <=> "PrimalDualRelationship"
}

VALIDATION {
 V1 = "Objective function is identified."
 V2 = "Decision variables are identified."
 V3 = "Constraints and domains are explicit."
 V4 = "Candidate solutions are checked for feasibility."
 V5 = "Problem convexity is assessed when relevant."
 V6 = "Optimality conditions match problem structure."
 V7 = "Solver choice matches continuous, discrete, convex or nonconvex structure."
 V8 = "Dual bounds use consistent sign conventions."
 V9 = "Optimality gap is interpreted correctly."
 V10 = "Local-versus-global solution status is explicit."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 OPTIMISATION_DEFINITION = 0.99
 PROBLEM_FORMULATION_REASONING = 0.99
 CLASSIFICATION_REASONING = 0.99
 FIRST_ORDER_REASONING = 0.98
 SECOND_ORDER_REASONING = 0.98
 ALGORITHM_SELECTION_REASONING = 0.98
 DUALITY_REASONING = 0.98
 MULTIOBJECTIVE_REASONING = 0.97
 SOLUTION_VERIFICATION_REASONING = 0.99

 POLICY =
  "Reduce confidence when objective, variable domains, constraints, convexity, differentiability, uncertainty structure, constraint qualifications or global-optimality evidence are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  OptimisationReasoning,
  OptimisationProblemFormulation,
  FeasibilityReasoning,
  ConvexityReasoning,
  FirstOrderOptimalityReasoning,
  SecondOrderOptimalityReasoning,
  KKTReasoning,
  DualityReasoning,
  NumericalOptimisation,
  IntegerOptimisation,
  MultiobjectiveOptimisation,
  StochasticOptimisation,
  RobustOptimisation,
  SensitivityAnalysis,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "optimisation" -> Optimisation
  "optimization" -> Optimisation
  "optimisation problem" -> OptimisationProblem
  "objective function" -> ObjectiveFunction
  "decision variable" -> DecisionVariable
  "feasible set" -> FeasibleSet
  "local optimum" -> LocalOptimum
  "global optimum" -> GlobalOptimum
  "KKT conditions" -> KarushKuhnTuckerConditions
  "Lagrange multiplier" -> LagrangeMultiplier
  "duality" -> Duality
 }

 INTERPRETATION_ORDER = [
  detect_optimisation_context,
  identify objective_decision_variables_constraints_domains_uncertainty_and_preference structure,
  classify unconstrained_constrained_continuous_discrete_convex_nonconvex_stochastic_or_multiobjective problem,
  analyse feasibility_and_optimality conditions,
  select compatible optimisation method,
  solve_or_reason_about candidate solutions,
  assess local_global status_duality_gap_sensitivity_and_robustness,
  verify assumptions_and_constraints,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("optimisation")
  OR asks_to_minimise_or_maximise objective
  THEN activate(OptimisationOntology)

 E2:
  IF unconstrained_smooth_problem
  THEN evaluate gradient_and_Hessian information

 E3:
  IF constrained_problem
  THEN identify active_constraints_and_constraint qualifications

 E4:
  IF convex_problem
  THEN exploit global_optimality properties

 E5:
  IF integer_variables_present
  THEN route to discrete_or_mixed_integer optimisation

 E6:
  IF multiple_objectives
  THEN use Pareto_or_preference based reasoning

 E7:
  IF uncertain_data
  THEN distinguish stochastic_robust_and_deterministic formulations

 E8:
  IF solver_returns_candidate
  THEN check feasibility_and_optimality evidence

 E9:
  IF global_optimality_claimed_for_nonconvex_problem
  THEN require global_bound_enumeration_or_other valid evidence
}

RECURSION {
 ENTRY = Optimisation

 EXPAND(Optimisation) -> [
  OptimisationProblem,
  ObjectiveFunction,
  DecisionVariable,
  FeasibleSet,
  Constraint,
  EqualityConstraint,
  InequalityConstraint,
  BoundConstraint,
  UnconstrainedOptimisation,
  ConstrainedOptimisation,
  LocalOptimum,
  GlobalOptimum,
  ConvexOptimisation,
  NonconvexOptimisation,
  LinearProgramming,
  NonlinearProgramming,
  QuadraticProgramming,
  IntegerProgramming,
  MixedIntegerProgramming,
  CombinatorialOptimisation,
  MultiobjectiveOptimisation,
  StochasticOptimisation,
  RobustOptimisation,
  DynamicOptimisation,
  OptimalControl,
  GradientMethod,
  NewtonMethod,
  QuasiNewtonMethod,
  TrustRegionMethod,
  LagrangeMultiplier,
  KarushKuhnTuckerConditions,
  Duality,
  SensitivityAnalysis,
  OptimalityGap
 ]

 EXPAND(OptimalityConditions) -> [
  Gradient,
  Hessian,
  FirstOrderNecessaryCondition,
  SecondOrderNecessaryCondition,
  SecondOrderSufficientCondition,
  LagrangeMultiplier,
  KarushKuhnTuckerConditions,
  ConstraintQualification
 ]

 EXPAND(ContinuousOptimisationMethods) -> [
  GradientDescent,
  NewtonMethod,
  QuasiNewtonMethod,
  ConjugateGradientMethod,
  LineSearch,
  TrustRegionMethod,
  InteriorPointMethod,
  SequentialQuadraticProgramming
 ]

 EXPAND(DiscreteOptimisation) -> [
  IntegerProgramming,
  MixedIntegerProgramming,
  BranchAndBound,
  BranchAndCut,
  DynamicProgramming,
  CombinatorialOptimisation
 ]

 STOP_CONDITION =
  "Stop when the objective, decision variables, feasible set, problem class, optimality conditions, solution method, local or global status, duality and sensitivity are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Applied Mathematics Ontologies"

 IMMEDIATE_CONTEXTS = [
  "Applied Mathematics Ontologies",
  "Numerical Analysis",
  "Mathematical Modelling",
  "Operations Research Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Applied Mathematics Ontologies",
  "Numerical Analysis Ontologies",
  "Mathematical Modelling",
  "Parameter Estimation Ontology",
  "Linear Algebra Ontologies",
  "Calculus & Analysis Ontologies",
  "Convex Geometry Ontology",
  "Probability & Statistics Ontologies",
  "Operations Research Ontologies",
  "Game Theory Ontologies",
  "Optimal Control Ontologies",
  "Combinatorial Optimisation Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Optimisation -> Applied Mathematics Ontologies for parent semantics",
  "Optimisation -> Numerical Analysis for numerical solution methods",
  "Optimisation -> Mathematical Modelling for model-based decision problems",
  "Optimisation -> Parameter Estimation for fitted-parameter objectives",
  "Optimisation -> Linear Algebra for quadratic and matrix optimisation",
  "Optimisation -> Calculus & Analysis for derivative-based optimality",
  "Optimisation -> Convex Geometry for convex feasible sets",
  "Optimisation -> Probability & Statistics for stochastic objectives",
  "Optimisation -> Operations Research for planning and allocation problems",
  "Optimisation -> Optimal Control for dynamic decision trajectories"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible optimisation classes, methods or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve objective-and-feasible-set semantics.",
  "Preserve decision-variable semantics.",
  "Preserve local-versus-global distinction.",
  "Preserve convex-versus-nonconvex distinction.",
  "Preserve feasibility before optimality.",
  "Preserve KKT and constraint-qualification semantics.",
  "Preserve primal-dual semantics.",
  "Preserve machine-readable optimisation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Optimisation seeks decision-variable values that minimise or maximise an objective while satisfying any declared constraints."

 PROBLEM_SUMMARY =
  "An optimisation problem consists of an objective, decision variables, domains and optional constraints."

 FEASIBILITY_SUMMARY =
  "A feasible solution satisfies every declared constraint."

 LOCAL_GLOBAL_SUMMARY =
  "Local optima are neighbourhood-best solutions; global optima are best across the entire feasible set."

 CONVEX_SUMMARY =
  "In convex minimisation, every local optimum is global under standard definitions."

 KKT_SUMMARY =
  "KKT conditions provide first-order constrained optimality conditions under suitable regularity assumptions."

 DUALITY_SUMMARY =
  "Duality relates primal and dual optimisation problems and can provide bounds and sensitivity information."

 MULTIOBJECTIVE_SUMMARY =
  "Multiobjective optimisation often yields a Pareto frontier of nondominated tradeoffs."

 SOLUTION_SUMMARY =
  "Reliable optimisation requires both numerical convergence and evidence of feasibility and optimality."
}

FLOW {
 INPUT
 -> detect_optimisation_context
 -> identify objective_decision_variables_domains_constraints_uncertainty_and_preference structure
 -> classify unconstrained_constrained_linear_nonlinear_convex_nonconvex_continuous_discrete_stochastic_robust_or_multiobjective problem
 -> analyse feasibility
 -> derive first_order_second_order_KKT_or_problem_specific optimality conditions
 -> select analytical_numerical_combinatorial_or_dynamic optimisation method
 -> compute candidate_solution
 -> verify feasibility_and_local_or_global optimality evidence
 -> analyse duality_optimality_gap_sensitivity_and_robustness
 -> route to applied_mathematics numerical_analysis mathematical_modelling parameter_estimation linear_algebra calculus convex_geometry probability_statistics operations_research game_theory_optimal_control_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Optimisation layer defines mathematical selection of best feasible solutions. It supports objective functions, decision variables, feasible sets, constraints, local and global optima, unconstrained and constrained problems, convex and nonconvex optimisation, linear and nonlinear programming, integer and combinatorial optimisation, stochastic and robust optimisation, multiobjective optimisation, optimal control, KKT conditions, duality, sensitivity and numerical solution methods."
}

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

}

END_FLOW