Optimisation Computation

AI INTERPRETATION NOTE
This Flow Algebra defines the Optimisation Computation parent ontology within the Kireth Research Semantic Library. Optimisation computation studies numerical methods for finding decision variables that minimise or maximise objective functions subject to constraints. This ontology supports unconstrained and constrained optimisation, linear and nonlinear programming, convex and nonconvex optimisation, gradient-based and derivative-free methods, first- and second-order algorithms, line search, trust regions, penalty and barrier methods, duality, KKT conditions, stochastic and large-scale optimisation, numerical stability, convergence, stopping criteria, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = OptimisationComputation
 ENTITY_CLASS = ComputationalOptimisationFramework
 PRIMARY_CONTEXT = ComputationalMathematicsOntologies
 DEFINITION = "Optimisation computation is the numerical determination of decision variables that minimise or maximise an objective function while satisfying declared constraints, domains and tolerances."
 SYMBOLIC_FORMS = [
  "min_x f(x)",
  "max_x f(x)",
  "min_x f(x) subject_to g_i(x)<=0, h_j(x)=0",
  "x_star=argmin_x f(x)"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for optimisation problem classes, objective functions, constraints, algorithms, derivatives, duality, convergence, stopping, conditioning, verification and reproducibility."
}

SCOPE {
 INCLUDE = [
  OptimisationComputation,OptimisationProblem,MinimisationProblem,
  MaximisationProblem,ObjectiveFunction,DecisionVariable,Parameter,
  FeasibleSet,Constraint,EqualityConstraint,InequalityConstraint,
  BoundConstraint,LinearConstraint,NonlinearConstraint,
  ConstraintQualification,FeasiblePoint,InfeasiblePoint,
  UnconstrainedOptimisation,ConstrainedOptimisation,
  LinearProgramming,LP,QuadraticProgramming,QP,
  NonlinearProgramming,NLP,ConvexOptimisation,NonconvexOptimisation,
  SmoothOptimisation,NonsmoothOptimisation,DiscreteOptimisation,
  IntegerProgramming,MixedIntegerProgramming,MIP,
  CombinatorialOptimisation,GlobalOptimisation,LocalOptimisation,
  DeterministicOptimisation,StochasticOptimisation,
  MultiobjectiveOptimisation,ParetoOptimality,
  Gradient,Jacobian,Hessian,DirectionalDerivative,
  Subgradient,GeneralisedGradient,
  FirstOrderMethod,SecondOrderMethod,ZeroOrderMethod,
  GradientDescent,SteepestDescent,ConjugateGradientOptimisation,
  NewtonOptimisation,QuasiNewtonMethod,BFGS,DFP,LBFGS,
  GaussNewtonMethod,LevenbergMarquardtMethod,
  CoordinateDescent,BlockCoordinateDescent,
  LineSearch,ExactLineSearch,InexactLineSearch,
  ArmijoCondition,WolfeCondition,StrongWolfeCondition,
  BacktrackingLineSearch,TrustRegion,TrustRegionRadius,
  DoglegMethod,TruncatedNewtonMethod,
  NelderMeadMethod,PowellMethod,PatternSearch,
  DirectSearch,DerivativeFreeOptimisation,
  PenaltyMethod,ExteriorPenalty,InteriorPenalty,
  BarrierMethod,LogBarrier,AugmentedLagrangian,
  LagrangeMultiplier,Lagrangian,DualFunction,DualProblem,
  WeakDuality,StrongDuality,ComplementarySlackness,
  KarushKuhnTuckerConditions,KKTConditions,
  PrimalProblem,DualProblem,PrimalDualMethod,
  InteriorPointMethod,ActiveSetMethod,SequentialQuadraticProgramming,SQP,
  ProjectedGradient,ProximalMethod,ProximalGradient,
  ADMM,AlternatingDirectionMethodOfMultipliers,
  SimplexMethod,RevisedSimplexMethod,
  BranchAndBound,BranchAndCut,CuttingPlaneMethod,
  DynamicProgramming,Heuristic,Metaheuristic,
  SimulatedAnnealing,GeneticAlgorithm,ParticleSwarmOptimisation,
  BayesianOptimisation,SurrogateOptimisation,
  StochasticGradientDescent,SGD,MiniBatchGradient,
  Momentum,NesterovAcceleration,AdaptiveGradientMethod,
  AdaGrad,RMSProp,Adam,
  LargeScaleOptimisation,SparseOptimisation,
  DistributedOptimisation,ParallelOptimisation,
  DecompositionMethod,DomainDecomposition,
  MatrixFreeOptimisation,AutomaticDifferentiation,
  NumericalDifferentiation,FiniteDifferenceGradient,
  FiniteDifferenceHessian,
  Scaling,Preconditioning,VariableScaling,ObjectiveScaling,
  Conditioning,Sensitivity,IllConditioning,
  ConstraintViolation,PrimalResidual,DualResidual,
  StationarityResidual,KKTResidual,
  OptimalityCondition,FirstOrderOptimality,
  SecondOrderOptimality,LocalMinimum,GlobalMinimum,
  SaddlePoint,StationaryPoint,CriticalPoint,
  ConvexSet,ConvexFunction,StrongConvexity,LipschitzGradient,
  Coercivity,Regularisation,L1Regularisation,L2Regularisation,
  Sparsity,PenaltyParameter,BarrierParameter,
  StepSize,LearningRate,Iteration,MaximumIterations,
  FunctionEvaluationCount,GradientEvaluationCount,
  HessianEvaluationCount,StoppingCriterion,
  GradientTolerance,StepTolerance,FunctionTolerance,
  ConstraintTolerance,KKT_Tolerance,
  Convergence,ConvergenceRate,LinearConvergence,
  SuperlinearConvergence,QuadraticConvergence,
  SublinearConvergence,Divergence,Stagnation,
  NumericalStability,FloatingPointArithmetic,MachinePrecision,
  RoundOffError,Overflow,Underflow,
  Verification,Benchmarking,ReferenceSolution,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  PureEquationSolvingWithoutObjectiveFunction,
  StatisticalEstimationWithoutOptimisationContext,
  SymbolicExtremumDerivationWithoutComputationalOptimisation,
  ControlSimulationWithoutOptimisationObjective
 ]
 DISAMBIGUATION_RULE = "When the task is to compute decision variables that optimise an objective subject to optional constraints, interpret the context as optimisation computation."
}

CORE_CONCEPTS {
 OptimisationProblem = "Problem of minimising or maximising an objective over a feasible set."
 ObjectiveFunction = "Scalar criterion whose value is minimised or maximised."
 FeasibleSet = "Set of decision variables satisfying all constraints."
 GradientDescent = "First-order iterative optimisation using the negative gradient direction."
 NewtonOptimisation = "Second-order optimisation based on local quadratic approximation."
 LineSearch = "Procedure selecting a step length along a search direction."
 TrustRegion = "Method restricting each local model step to a neighbourhood where the model is trusted."
 KKTConditions = "First-order optimality conditions for constrained optimisation under suitable regularity."
 DualProblem = "Optimisation problem constructed from Lagrange multipliers that bounds or characterises the primal problem."
}

RELATIONS {
 OptimisationComputation --is_child_of--> ComputationalMathematicsOntologies
 OptimisationProblem --has--> ObjectiveFunction
 OptimisationProblem --has_optional--> Constraint
 Constraint --defines--> FeasibleSet
 GradientDescent --uses--> Gradient
 NewtonOptimisation --uses--> Hessian
 QuasiNewtonMethod --approximates--> HessianOrInverseHessian
 BFGS --is_type_of--> QuasiNewtonMethod
 LBFGS --is_type_of--> QuasiNewtonMethod
 LineSearch --controls--> StepSize
 TrustRegion --controls--> ModelValidityRegion
 ConstrainedOptimisation --uses--> KKTConditions
 Lagrangian --combines--> ObjectiveAndConstraints
 DualProblem --is_derived_from--> Lagrangian
 InteriorPointMethod --uses--> BarrierMethod
 SQP --uses--> QuadraticProgrammingSubproblem
 ProximalGradient --uses--> ProximalOperator
 ADMM --uses--> AugmentedLagrangian
 StochasticGradientDescent --uses--> StochasticGradient
 Verification --checks--> OptimisationResult
}

OPERATORS {
 MINIMISE(f,X) := argmin_x_in_X f(x)
 MAXIMISE(f,X) := argmax_x_in_X f(x)
 GRADIENT_STEP(x,g,alpha) := x_next=x-alpha*g
 NEWTON_STEP(x,g,H) := solve(H*p=-g); x_next=x+p
 PROJECTED_STEP(x,g,alpha,C) := x_next=Projection_C(x-alpha*g)
 LAGRANGIAN(x,lambda,mu) := f(x)+sum_i lambda_i*g_i(x)+sum_j mu_j*h_j(x)
 KKT_RESIDUAL(x,lambda,mu) := combine(stationarity,primal_feasibility,dual_feasibility,complementarity)
 TRUST_REGION_SUBPROBLEM(g,H,Delta) := min_p g^T*p+0.5*p^T*H*p subject_to ||p||<=Delta
 LINE_SEARCH(phi,alpha) := choose_alpha_satisfying_declared_conditions
}

AXIOMS {
 A1 = "Optimisation requires an objective function and a declared admissible domain or feasible set."
 A2 = "Local optimality and global optimality are distinct."
 A3 = "Gradient, Hessian and constraint information influence method suitability."
 A4 = "Constrained optimisation requires feasibility semantics in addition to objective reduction."
 A5 = "Stopping criteria should distinguish optimality, feasibility, step size and resource limits."
 A6 = "Convexity can strengthen local-to-global optimality guarantees."
 A7 = "Numerical conditioning and scaling can materially affect optimisation performance."
 A8 = "Optimisation results require objective, constraint, convergence and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(objective,decision_variables,domain,constraints,smoothness,convexity,scale,accuracy_goal)
 R2_CLASSIFY = classify(unconstrained,constrained,linear,quadratic,nonlinear,convex,nonconvex,discrete,stochastic_or_multiobjective)
 R3_DERIVATIVES = determine(analytic,automatic_differentiation,numerical_or_derivative_free_information)
 R4_METHOD = select(first_order,second_order,line_search,trust_region,interior_point,SQP,proximal,derivative_free,stochastic_or_global_method)
 R5_CONFIGURATION = set(initial_guess,scaling,tolerances,step_controls,penalty_or_barrier_parameters)
 R6_ITERATE = compute_search_direction_or_candidate_update
 R7_GLOBALISE = apply(line_search,trust_region,projection,penalty,barrier_or_filter_if_required)
 R8_MONITOR = track(objective,gradient_norm,constraint_violation,KKT_residual,step_size_and_progress)
 R9_CONVERGENCE = classify(convergence,stagnation,divergence_or_resource_limit)
 R10_VALIDATE = check(feasibility,optimality_conditions,sensitivity,reference_solution_and_reproducibility)
}

CONSTRAINTS {
 C1 = "A stationary point need not be a local minimum in nonconvex problems."
 C2 = "Local optimisation methods need not find the global optimum."
 C3 = "Poor scaling can degrade search directions and stopping tests."
 C4 = "Finite-difference derivatives involve truncation-roundoff tradeoffs."
 C5 = "Hessian indefiniteness can make raw Newton directions non-descent directions."
 C6 = "Penalty parameters that are too small can permit constraint violation; excessively large values can cause ill-conditioning."
 C7 = "Barrier methods require feasible interior semantics for standard formulations."
 C8 = "Stochastic objective estimates introduce sampling noise into progress and convergence tests."
 C9 = "Resource-limit termination is not equivalent to optimisation convergence."
 C10 = "A small objective change alone does not guarantee first-order optimality or feasibility."
}

SEMANTIC_EQUIVALENCE {
 "OptimisationComputation" <=> "ComputationalOptimisation"
 "GradientDescent" <=> "SteepestDescentInEuclideanMetric"
 "LBFGS" <=> "LimitedMemoryBFGS"
 "KKTConditions" <=> "KarushKuhnTuckerConditions"
 "SGD" <=> "StochasticGradientDescent"
 "ADMM" <=> "AlternatingDirectionMethodOfMultipliers"
}

VALIDATION {
 V1 = "Objective function and optimisation direction are explicit."
 V2 = "Decision-variable domain and constraints are documented."
 V3 = "Initial guess or initial population is documented."
 V4 = "Derivative source and optimisation method are documented."
 V5 = "Stopping criteria and tolerances are documented."
 V6 = "Constraint feasibility is checked for constrained problems."
 V7 = "Gradient, KKT or other optimality residuals are reported where applicable."
 V8 = "Sensitivity to scaling and initialisation is assessed where relevant."
 V9 = "Reference, benchmark or independently verified solutions are used where feasible."
 V10 = "Results are reproducible under documented arithmetic and algorithm settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 OPTIMISATION_COMPUTATION_DEFINITION = 0.99
 UNCONSTRAINED_REASONING = 0.99
 CONSTRAINED_REASONING = 0.99
 GRADIENT_METHOD_REASONING = 0.99
 NEWTON_REASONING = 0.99
 KKT_REASONING = 0.99
 STOCHASTIC_REASONING = 0.98
 GLOBAL_OPTIMISATION_REASONING = 0.97
 POLICY = "Reduce confidence when objective definition, constraints, convexity, derivative quality, scaling, initialisation, stopping criteria or stochastic noise are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,OptimisationReasoning,
  UnconstrainedOptimisationReasoning,ConstrainedOptimisationReasoning,
  LinearProgrammingReasoning,QuadraticProgrammingReasoning,
  NonlinearProgrammingReasoning,ConvexOptimisationReasoning,
  GradientDescentReasoning,NewtonOptimisationReasoning,
  QuasiNewtonReasoning,LineSearchReasoning,TrustRegionReasoning,
  InteriorPointReasoning,SQPReasoning,KKTReasoning,DualityReasoning,
  ProximalReasoning,ADMMReasoning,DerivativeFreeReasoning,
  StochasticOptimisationReasoning,GlobalOptimisationReasoning,
  LargeScaleOptimisationReasoning,VerificationReasoning,
  KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "optimisation computation" -> OptimisationComputation
  "optimization computation" -> OptimisationComputation
  "computational optimisation" -> OptimisationComputation
  "BFGS" -> BFGS
  "L-BFGS" -> LBFGS
  "KKT" -> KKTConditions
  "SGD" -> StochasticGradientDescent
  "ADMM" -> AlternatingDirectionMethodOfMultipliers
 }
}

EXECUTION_RULES {
 E1 = "If a numerical procedure seeks variables minimising or maximising an objective, activate OptimisationComputation."
 E2 = "Classify constraints, smoothness, convexity, discreteness and stochasticity before method selection."
 E3 = "Use derivative-based methods when reliable derivative information is available and appropriate."
 E4 = "Use line search or trust-region globalisation when raw local steps are unreliable."
 E5 = "For constrained smooth problems, assess KKT conditions and constraint qualifications."
 E6 = "For large sparse problems, exploit matrix-free derivatives, sparsity and preconditioning."
 E7 = "For nonsmooth composite objectives, consider proximal or splitting methods."
 E8 = "For stochastic objectives, use noise-aware convergence and validation semantics."
 E9 = "Validate objective value, feasibility, optimality residuals, sensitivity and reproducibility."
}

RECURSION {
 ENTRY = OptimisationComputation
 EXPAND(OptimisationComputation) -> [
  OptimisationProblem,MinimisationProblem,MaximisationProblem,
  ObjectiveFunction,DecisionVariable,FeasibleSet,Constraint,
  EqualityConstraint,InequalityConstraint,BoundConstraint,
  UnconstrainedOptimisation,ConstrainedOptimisation,LinearProgramming,
  QuadraticProgramming,NonlinearProgramming,ConvexOptimisation,
  NonconvexOptimisation,SmoothOptimisation,NonsmoothOptimisation,
  IntegerProgramming,MixedIntegerProgramming,GlobalOptimisation,
  StochasticOptimisation,MultiobjectiveOptimisation,Gradient,Jacobian,
  Hessian,Subgradient,FirstOrderMethod,SecondOrderMethod,
  DerivativeFreeOptimisation,GradientDescent,NewtonOptimisation,
  QuasiNewtonMethod,BFGS,LBFGS,GaussNewtonMethod,
  LevenbergMarquardtMethod,CoordinateDescent,LineSearch,
  ArmijoCondition,WolfeCondition,TrustRegion,PenaltyMethod,
  BarrierMethod,AugmentedLagrangian,Lagrangian,DualProblem,
  KKTConditions,InteriorPointMethod,ActiveSetMethod,SQP,
  ProjectedGradient,ProximalMethod,ProximalGradient,ADMM,
  SimplexMethod,BranchAndBound,CuttingPlaneMethod,
  SimulatedAnnealing,GeneticAlgorithm,ParticleSwarmOptimisation,
  BayesianOptimisation,StochasticGradientDescent,Momentum,Adam,
  LargeScaleOptimisation,SparseOptimisation,DistributedOptimisation,
  AutomaticDifferentiation,NumericalDifferentiation,Scaling,
  Conditioning,ConstraintViolation,PrimalResidual,DualResidual,
  StationarityResidual,KKTResidual,OptimalityCondition,LocalMinimum,
  GlobalMinimum,SaddlePoint,ConvexFunction,StrongConvexity,
  Regularisation,L1Regularisation,L2Regularisation,StoppingCriterion,
  Convergence,ConvergenceRate,NumericalStability,FloatingPointArithmetic,
  Verification,Benchmarking,ReferenceSolution,Reproducibility
 ]
 EXPAND(OptimisationFamilies) -> [
  UnconstrainedOptimisation,
  ConstrainedOptimisation,
  LinearAndQuadraticProgramming,
  NonlinearProgramming,
  ConvexOptimisation,
  DerivativeFreeOptimisation,
  StochasticOptimisation,
  GlobalAndDiscreteOptimisation,
  LargeScaleAndDistributedOptimisation
 ]
 STOP_CONDITION = "Stop when objective, variables, constraints, derivatives, method, globalisation, convergence, optimality and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Mathematics Ontologies"
 RELATED_ONTOLOGIES = [
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Differentiation Ontology 2",
  "Equation Solver Ontology",
  "Linear Solver Ontology",
  "Nonlinear Solver Ontology",
  "Numerical Linear Algebra Ontology 2",
  "Numerical Error Ontology",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology",
  "Floating Point Arithmetic Ontology",
  "Scientific Computing Ontology 2",
  "Artificial Intelligence Mathematics"
 ]
 ROUTE_RULES = [
  "Optimisation Computation -> Computational Mathematics for parent semantics",
  "Optimisation Computation -> Numerical Differentiation for derivative approximation",
  "Optimisation Computation -> Equation Solver for optimality-condition equations",
  "Optimisation Computation -> Linear Solver for Newton, SQP and interior-point subproblems",
  "Optimisation Computation -> Nonlinear Solver for nonlinear KKT and constrained systems",
  "Optimisation Computation -> Numerical Linear Algebra for Hessians, factorisations and preconditioning",
  "Optimisation Computation -> Numerical Analysis for convergence, conditioning and error",
  "Optimisation Computation -> Scientific Computing for large-scale and distributed execution",
  "Optimisation Computation -> Artificial Intelligence Mathematics for training and learning optimisation"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible optimisation classes, algorithms or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve minimisation-versus-maximisation distinction.",
  "Preserve unconstrained-versus-constrained distinction.",
  "Preserve local-versus-global optimum distinction.",
  "Preserve objective-reduction-versus-feasibility distinction.",
  "Preserve first-order-versus-second-order distinction.",
  "Preserve deterministic-versus-stochastic distinction.",
  "Preserve continuous-versus-discrete optimisation distinction.",
  "Preserve machine-readable optimisation-computation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Optimisation computation numerically determines decision variables that minimise or maximise an objective subject to optional constraints."
 CLASSIFICATION_SUMMARY = "Optimisation problems are classified by constraints, smoothness, convexity, variable type, stochasticity and objective structure."
 DERIVATIVE_SUMMARY = "Gradient, Hessian, Jacobian and subgradient information determine the applicability of first- and second-order methods."
 GLOBALISATION_SUMMARY = "Line searches, trust regions, projections, penalties and barriers improve robustness of local optimisation steps."
 CONSTRAINED_SUMMARY = "KKT conditions, duality, interior-point, active-set and SQP methods define central constrained-optimisation semantics."
 LARGE_SCALE_SUMMARY = "Sparse, matrix-free, stochastic and distributed methods extend optimisation to high-dimensional computational problems."
 VALIDATION_SUMMARY = "Optimisation results should be checked for objective quality, feasibility, optimality residuals, sensitivity, convergence and reproducibility."
}

FLOW {
 INPUT
 -> detect_optimisation_computation_context
 -> identify_objective_variables_domain_constraints_smoothness_convexity_scale_and_accuracy_goal
 -> classify_problem_family
 -> determine_derivative_information
 -> select_optimisation_algorithm
 -> configure_initialisation_scaling_tolerances_and_globalisation
 -> compute_candidate_search_direction_or_update
 -> apply_line_search_trust_region_projection_penalty_barrier_or_other_control_if_required
 -> evaluate_objective_constraints_gradient_KKT_residual_and_step
 -> monitor_convergence_stagnation_divergence_and_resource_limits
 -> assess_conditioning_sensitivity_roundoff_and_stochastic_noise
 -> validate_feasibility_optimality_reference_quality_and_reproducibility
 -> route_to_related_numerical_methods_differentiation_equation_solver_linear_algebra_analysis_stability_convergence_scientific_computing_and_AI_mathematics_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Optimisation Computation ontology defines numerical methods for minimisation and maximisation. It supports unconstrained and constrained optimisation, linear, quadratic and nonlinear programming, convex and nonconvex problems, gradient descent, Newton and quasi-Newton methods, BFGS and L-BFGS, Gauss-Newton and Levenberg-Marquardt methods, coordinate descent, line searches, trust regions, penalties, barriers and augmented Lagrangians, KKT conditions and duality, interior-point, active-set and SQP methods, projected and proximal methods, ADMM, simplex and branch-and-bound methods, derivative-free and global optimisation, stochastic gradient methods, Adam and momentum, Bayesian and surrogate optimisation, sparse, matrix-free, distributed and large-scale optimisation, conditioning, convergence, stopping criteria, finite precision, verification, benchmarking and reproducibility."
}

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

}

END_FLOW