Constraint Optimisation Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Constraint Optimisation Ontology within the Kireth Research Semantic Library. Constraint optimisation studies optimisation problems in which admissible decision-variable values are restricted by equality, inequality, bound, logical, integrality, geometric, dynamic or other explicit constraints. This ontology supports feasible sets, active and inactive constraints, Lagrange multipliers, Karush-Kuhn-Tucker conditions, constraint qualifications, projected methods, penalty and barrier methods, augmented Lagrangians, sequential quadratic programming, interior-point methods, active-set methods, feasibility restoration, constraint violation, duality, sensitivity and relationships with convex optimisation, nonlinear optimisation, integer programming, numerical analysis and operations research.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = ConstrainedOptimisation
 SYMBOLIC_FORMS = [
  "min_x f(x) subject to g_i(x)<=0, h_j(x)=0",
  "x in F",
  "KKT(x,lambda,nu)=0"
 ]
 ENTITY_CLASS = ConstraintAwareOptimisationFramework
 PRIMARY_CONTEXT = Optimisation
 DEFINITION = "Constrained optimisation is the optimisation of an objective function over decision variables restricted by one or more constraints."
 SEMANTIC_ROLE = "Provides the machine-readable framework for feasible sets, equality and inequality constraints, active sets, Lagrange multipliers, KKT systems, feasibility restoration, penalties, barriers, projections, duality and constrained numerical methods."
}

SCOPE {
 INCLUDE = [
  ConstrainedOptimisation,
  Constraint,
  EqualityConstraint,
  InequalityConstraint,
  BoundConstraint,
  LinearConstraint,
  NonlinearConstraint,
  IntegralityConstraint,
  LogicalConstraint,
  DynamicConstraint,
  FeasibleSet,
  FeasiblePoint,
  InfeasiblePoint,
  ConstraintViolation,
  ActiveConstraint,
  InactiveConstraint,
  ActiveSet,
  FeasibleDirection,
  TangentCone,
  NormalCone,
  Lagrangian,
  LagrangeMultiplier,
  KarushKuhnTuckerConditions,
  ConstraintQualification,
  LICQ,
  MFCQ,
  SlaterCondition,
  ComplementarySlackness,
  PrimalFeasibility,
  DualFeasibility,
  ProjectedGradientMethod,
  ActiveSetMethod,
  PenaltyMethod,
  ExactPenaltyMethod,
  BarrierMethod,
  InteriorPointMethod,
  AugmentedLagrangianMethod,
  SequentialQuadraticProgramming,
  FeasibilityRestoration,
  MeritFunction,
  FilterMethod,
  DualProblem,
  ShadowPrice,
  SensitivityAnalysis
 ]

 EXCLUDE_AS_PRIMARY = [
  UnconstrainedOptimisation,
  PureEquationSolvingWithoutObjective,
  ConstraintSatisfactionWithoutOptimisationGoal,
  GenericLogicalConstraintsWithoutMathematicalOptimisation
 ]

 DISAMBIGUATION_RULE =
  "When an optimisation problem restricts candidate decisions through explicit admissibility conditions, interpret the context as constrained optimisation."
}

CORE_CONCEPTS {

 ConstrainedOptimisation {
  definition = "Optimisation over a feasible region defined by one or more constraints."
 }

 Constraint {
  definition = "A mathematical condition restricting admissible values of decision variables."
 }

 EqualityConstraint {
  definition = "A constraint of the form h(x)=0."
 }

 InequalityConstraint {
  definition = "A constraint of the form g(x)<=0 or an equivalent declared convention."
 }

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

 FeasiblePoint {
  definition = "A candidate point belonging to the feasible set."
 }

 ActiveConstraint {
  definition = "An inequality constraint satisfied at equality at a candidate point."
 }

 FeasibleDirection {
  definition = "A direction that preserves feasibility to first order from a feasible point."
 }

 Lagrangian {
  definition = "A scalar function combining the objective with weighted constraints."
 }

 LagrangeMultiplier {
  definition = "A dual variable associated with a constraint in the Lagrangian."
 }

 KarushKuhnTuckerConditions {
  definition = "A system combining stationarity, primal feasibility, dual feasibility and complementary slackness."
 }

 ConstraintQualification {
  definition = "A regularity condition supporting validity of multiplier-based optimality conditions."
 }
}

RELATIONS {
 ConstrainedOptimisation --is_special_case_of--> Optimisation
 Constraint --defines--> FeasibleSet
 EqualityConstraint --is_type_of--> Constraint
 InequalityConstraint --is_type_of--> Constraint
 BoundConstraint --is_type_of--> Constraint
 ActiveConstraint --is_state_of--> InequalityConstraint
 FeasiblePoint --is_element_of--> FeasibleSet
 InfeasiblePoint --is_not_element_of--> FeasibleSet
 FeasibleDirection --belongs_to--> TangentCone
 LagrangeMultiplier --is_associated_with--> Constraint
 Lagrangian --combines--> ObjectiveFunction
 Lagrangian --combines--> Constraint
 KarushKuhnTuckerConditions --characterise--> ConstrainedStationarity
 ConstraintQualification --supports--> KKTNecessity
 ComplementarySlackness --links--> InequalityConstraint
 ProjectedGradientMethod --maintains--> Feasibility
 PenaltyMethod --penalises--> ConstraintViolation
 BarrierMethod --discourages--> BoundaryApproach
 InteriorPointMethod --follows--> InteriorPath
 AugmentedLagrangianMethod --combines--> MultiplierAndPenalty
 SequentialQuadraticProgramming --solves--> QuadraticSubproblem
}

OPERATORS {
 FEASIBLE(x,g,h,bounds) :=
  all_i g_i(x)<=0
  AND all_j h_j(x)=0
  AND bounds_satisfied

 ACTIVE_SET(x,g,tol) :=
  {i : abs(g_i(x))<=tol}

 CONSTRAINT_VIOLATION(x,g,h) :=
  sum_i max(0,g_i(x))
  + sum_j abs(h_j(x))

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

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

 COMPLEMENTARY_SLACKNESS(g,lambda,x) :=
  lambda_i*g_i(x)=0
  for_all inequality constraints

 PROJECT_ONTO_FEASIBLE_SET(y,F) :=
  argmin_{x in F} ||x-y||

 PENALISED_OBJECTIVE(f,violation,rho) :=
  f(x)+rho*violation(x)

 LOG_BARRIER_OBJECTIVE(f,g,mu) :=
  f(x)-mu*sum_i log(-g_i(x))
  when g_i(x)<0

 AUGMENTED_LAGRANGIAN(f,h,lambda,rho) :=
  f(x)+lambda^T*h(x)+(rho/2)*||h(x)||^2

 SQP_SUBPROBLEM(f,g,h,x,B) :=
  quadratic_model_of_Lagrangian
  subject_to linearised_constraints
}

DEFINITIONS {
 D1 = "Constrained optimisation restricts the admissible decision space."
 D2 = "Feasibility must be established before constrained optimality."
 D3 = "Active constraints shape first-order feasible directions."
 D4 = "Lagrange multipliers represent local objective sensitivity to constraints under suitable assumptions."
 D5 = "KKT conditions generalise first-order optimality to constrained problems."
 D6 = "Constraint qualifications determine when multiplier-based conditions are valid."
 D7 = "Penalty methods trade objective quality against constraint violation."
 D8 = "Barrier methods approach constrained boundaries from the interior."
 D9 = "Projected methods restore or preserve feasibility by projection."
 D10 = "Sequential quadratic programming solves local constrained quadratic approximations."
}

AXIOMS {
 A1_FEASIBILITY:
  A constrained optimum must belong to the feasible set

 A2_CONSTRAINT_STRUCTURE:
  FeasibleSet is defined by the intersection of all declared constraints

 A3_ACTIVE_SET:
  Only active inequality constraints can carry nonzero KKT multipliers under complementary slackness

 A4_KKT:
  Under suitable regularity, local constrained optima satisfy KKT conditions

 A5_DUAL_FEASIBILITY:
  Inequality multipliers follow the declared sign convention

 A6_COMPLEMENTARY_SLACKNESS:
  Each inequality multiplier times its constraint slack is zero at a KKT point

 A7_PROJECTION:
  Projection-based methods map trial points back to the feasible region

 A8_CERTIFICATION:
  Constrained solver success requires both feasibility and optimality evidence
}

REASONING {

 R1_CONSTRAINT_EXTRACTION {
  INPUT = optimisation_problem
  IDENTIFY = equality_inequality_bound_integrality_logical_and_dynamic constraints
  RETURN = constraint_structure
 }

 R2_FEASIBILITY_ANALYSIS {
  INPUT = candidate
  COMPUTE = equality_residuals
  COMPUTE = inequality_violations
  COMPUTE = bound_violations
  RETURN = feasible_or_infeasible
 }

 R3_ACTIVE_SET_ANALYSIS {
  INPUT = feasible_candidate
  IDENTIFY = active_inequalities
  BUILD = active_constraint Jacobian
  RETURN = active_set_profile
 }

 R4_CONSTRAINT_QUALIFICATION {
  INPUT = active_constraint gradients
  TEST = LICQ_MFCQ_Slater_or_other applicable condition
  RETURN = qualification_status
 }

 R5_KKT_ANALYSIS {
  INPUT = candidate_and_multipliers
  CHECK = primal_feasibility
  CHECK = dual_feasibility
  CHECK = complementary_slackness
  CHECK = stationarity
  RETURN = KKT_status
 }

 R6_PROJECTED_METHOD {
  INPUT = x_and_gradient
  COMPUTE = trial_point
  PROJECT = onto feasible_set
  RETURN = projected_iterate
 }

 R7_PENALTY_METHOD {
  INPUT = constrained_problem_and_penalty_parameter
  FORM = penalised objective
  SOLVE = unconstrained_or_less_constrained subproblem
  UPDATE = penalty_parameter
  RETURN = penalty_sequence
 }

 R8_INTERIOR_POINT_METHOD {
  INPUT = inequality_constrained_problem
  FORM = barrier_or_primal_dual equations
  REDUCE = barrier_parameter
  APPLY = Newton-like steps
  RETURN = interior_path_and_candidate
 }

 R9_SQP_REASONING {
  INPUT = nonlinear_constrained_problem
  BUILD = quadratic_model
  LINEARISE = constraints
  SOLVE = QP_subproblem
  GLOBALISE = merit_or_filter method
  RETURN = next_iterate
 }

 R10_SENSITIVITY_REASONING {
  INPUT = constrained_optimum_and_multipliers
  PERTURB = right_hand_sides_or_parameters
  ESTIMATE = change_in_optimal_value_and_solution
  RETURN = constrained_sensitivity_profile
 }
}

CONSTRAINTS {
 C1 = "Constraint sign conventions must remain consistent."
 C2 = "Equality and inequality constraints must not be conflated."
 C3 = "KKT necessity can require constraint qualifications."
 C4 = "Penalty methods may remain infeasible for finite penalty values."
 C5 = "Barrier methods require interior feasibility for logarithmic barriers."
 C6 = "Projection may be computationally difficult for complex feasible sets."
 C7 = "Active-set identification is tolerance dependent."
 C8 = "Poor scaling can distort feasibility and multiplier interpretation."
 C9 = "Numerical feasibility tolerances must be reported."
 C10 = "Solver termination does not certify constrained optimality without feasibility and stationarity checks."
}

SEMANTIC_EQUIVALENCE {
 "ConstrainedOptimisation" <=> "ConstraintOptimisation"
 "ConstraintOptimization" <=> "ConstrainedOptimisation"
 "FeasibleSet" <=> "ConstraintSatisfyingDomain"
 "ActiveConstraint" <=> "BindingConstraint"
 "LagrangeMultiplier" <=> "ConstraintDualVariable"
 "KKTConditions" <=> "KarushKuhnTuckerConditions"
}

VALIDATION {
 V1 = "All constraints are identified."
 V2 = "Constraint directions and signs are explicit."
 V3 = "Feasibility tolerances are declared."
 V4 = "Active constraints are correctly detected."
 V5 = "Constraint qualification assumptions are checked."
 V6 = "KKT conditions use consistent multiplier signs."
 V7 = "Penalty or barrier parameters are documented."
 V8 = "Projected methods use the correct feasible set."
 V9 = "Sensitivity interpretations remain local unless stronger evidence exists."
 V10 = "Feasible, stationary and optimal statuses are distinguished."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 CONSTRAINED_OPTIMISATION_DEFINITION = 0.99
 FEASIBILITY_REASONING = 0.99
 ACTIVE_SET_REASONING = 0.98
 CONSTRAINT_QUALIFICATION_REASONING = 0.98
 KKT_REASONING = 0.99
 PENALTY_REASONING = 0.98
 INTERIOR_POINT_REASONING = 0.98
 SQP_REASONING = 0.97
 SENSITIVITY_REASONING = 0.98

 POLICY =
  "Reduce confidence when constraint signs, scaling, feasibility tolerances, active-set status, multiplier conventions, constraint qualifications, barrier parameters or solver status are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  ConstrainedOptimisationReasoning,
  FeasibilityReasoning,
  ActiveSetReasoning,
  KKTReasoning,
  ConstraintQualificationReasoning,
  ProjectedGradientReasoning,
  PenaltyMethodReasoning,
  BarrierMethodReasoning,
  InteriorPointReasoning,
  AugmentedLagrangianReasoning,
  SQPReasoning,
  FeasibilityRestoration,
  SensitivityReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "constraint optimisation" -> ConstrainedOptimisation
  "constrained optimisation" -> ConstrainedOptimisation
  "constraint optimization" -> ConstrainedOptimisation
  "feasible set" -> FeasibleSet
  "active constraint" -> ActiveConstraint
  "binding constraint" -> ActiveConstraint
  "constraint violation" -> ConstraintViolation
  "KKT conditions" -> KarushKuhnTuckerConditions
  "penalty method" -> PenaltyMethod
  "interior-point method" -> InteriorPointMethod
 }

 INTERPRETATION_ORDER = [
  detect_constrained_optimisation_context,
  identify objective_decision_variables_domains_and_constraint classes,
  construct feasible_set,
  evaluate feasibility_and_active set,
  test constraint qualifications,
  derive KKT_or_problem-specific optimality conditions,
  select projected_activeSet_penalty_barrier_interiorPoint_augmentedLagrangian_or_SQP method,
  compute_or_assess candidate_solution,
  verify feasibility_dual feasibility_complementary slackness_and_stationarity,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("constraint optimisation")
  OR optimisation_has_explicit_constraints
  THEN activate(ConstrainedOptimisationOntology)

 E2:
  IF candidate_given
  THEN check feasibility_before optimality

 E3:
  IF inequality_constraint_is_strictly_inactive
  THEN set corresponding KKT_multiplier_to_zero under complementary slackness

 E4:
  IF smooth_constrained_problem
  THEN assess KKT_conditions_and_constraint qualification

 E5:
  IF simple_convex_feasible_set
  THEN consider projected_gradient

 E6:
  IF constraint_violation_is_difficult_to_eliminate
  THEN consider penalty_augmentedLagrangian_or_feasibility_restoration

 E7:
  IF logarithmic_barrier_used
  THEN maintain strict interior feasibility

 E8:
  IF nonlinear_constraints
  THEN consider SQP_or_primal_dual interior-point method

 E9:
  IF solver_reports_success_but_constraints_exceed_tolerance
  THEN classify solution_as_infeasible_or_not_converged
}

RECURSION {
 ENTRY = ConstrainedOptimisation

 EXPAND(ConstrainedOptimisation) -> [
  Constraint,
  EqualityConstraint,
  InequalityConstraint,
  BoundConstraint,
  LinearConstraint,
  NonlinearConstraint,
  IntegralityConstraint,
  LogicalConstraint,
  DynamicConstraint,
  FeasibleSet,
  FeasiblePoint,
  InfeasiblePoint,
  ConstraintViolation,
  ActiveConstraint,
  InactiveConstraint,
  ActiveSet,
  FeasibleDirection,
  TangentCone,
  NormalCone,
  Lagrangian,
  LagrangeMultiplier,
  KarushKuhnTuckerConditions,
  ConstraintQualification,
  LICQ,
  MFCQ,
  SlaterCondition,
  ComplementarySlackness,
  PrimalFeasibility,
  DualFeasibility,
  ProjectedGradientMethod,
  ActiveSetMethod,
  PenaltyMethod,
  ExactPenaltyMethod,
  BarrierMethod,
  InteriorPointMethod,
  AugmentedLagrangianMethod,
  SequentialQuadraticProgramming,
  FeasibilityRestoration,
  MeritFunction,
  FilterMethod,
  DualProblem,
  ShadowPrice,
  SensitivityAnalysis
 ]

 EXPAND(KKTStructure) -> [
  Stationarity,
  PrimalFeasibility,
  DualFeasibility,
  ComplementarySlackness,
  ConstraintQualification
 ]

 EXPAND(ConstraintMethods) -> [
  ProjectedGradientMethod,
  ActiveSetMethod,
  PenaltyMethod,
  BarrierMethod,
  InteriorPointMethod,
  AugmentedLagrangianMethod,
  SequentialQuadraticProgramming
 ]

 EXPAND(ConstraintGeometry) -> [
  FeasibleSet,
  TangentCone,
  NormalCone,
  FeasibleDirection,
  ActiveSet
 ]

 STOP_CONDITION =
  "Stop when the constraint classes, feasible set, active set, constraint qualification, KKT system, selected constrained method, feasibility, stationarity and sensitivity 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",
  "Linear Programming Ontology",
  "Integer Programming Ontology",
  "Dynamic Optimisation Ontology",
  "Numerical Analysis Ontologies",
  "Linear Algebra Ontologies",
  "Calculus & Analysis Ontologies",
  "Operations Research Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Constraint Optimisation -> Optimisation Ontology for formal optimisation semantics",
  "Constraint Optimisation -> Nonlinear Optimisation for nonlinear constraints and SQP",
  "Constraint Optimisation -> Convex Optimisation for convex feasible sets and global KKT interpretation",
  "Constraint Optimisation -> Linear Programming for linear constraints",
  "Constraint Optimisation -> Integer Programming for integrality constraints",
  "Constraint Optimisation -> Dynamic Optimisation for path and dynamic constraints",
  "Constraint Optimisation -> Numerical Analysis for feasibility tolerances and solver stability",
  "Constraint Optimisation -> Linear Algebra for KKT systems and projections",
  "Constraint Optimisation -> Calculus & Analysis for gradients and tangent geometry",
  "Constraint Optimisation -> Operations Research for practical constrained decision models"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

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

 RULES = [
  "Preserve feasibility-before-optimality semantics.",
  "Preserve equality-versus-inequality distinction.",
  "Preserve active-versus-inactive constraint semantics.",
  "Preserve KKT and constraint-qualification semantics.",
  "Preserve projection, penalty and barrier distinctions.",
  "Preserve primal-versus-dual feasibility semantics.",
  "Preserve numerical-feasibility tolerance semantics.",
  "Preserve machine-readable constrained-optimisation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Constrained optimisation seeks the best feasible decision while satisfying one or more explicit mathematical constraints."

 FEASIBILITY_SUMMARY =
  "A constrained candidate must satisfy all equality, inequality, bound and domain restrictions."

 ACTIVE_SET_SUMMARY =
  "Active constraints bind at a candidate point and shape feasible first-order directions."

 KKT_SUMMARY =
  "KKT conditions combine stationarity, primal feasibility, dual feasibility and complementary slackness."

 QUALIFICATION_SUMMARY =
  "Constraint qualifications determine when multiplier-based optimality conditions are valid."

 PENALTY_SUMMARY =
  "Penalty methods transform constraint violation into objective cost."

 BARRIER_SUMMARY =
  "Barrier and interior-point methods approach constrained boundaries from within the feasible region."

 SQP_SUMMARY =
  "Sequential quadratic programming solves a sequence of local quadratic constrained approximations."

 STATUS_SUMMARY =
  "A valid constrained optimisation result should distinguish feasibility, stationarity, local optimality and certified global optimality."
}

FLOW {
 INPUT
 -> detect_constrained_optimisation_context
 -> identify objective_decision_variables_domains_equality_inequality_bound_linear_nonlinear_integrality_logical_and_dynamic constraints
 -> construct feasible_set
 -> evaluate candidate_feasibility_and_constraint violation
 -> identify active_and_inactive constraints
 -> test LICQ_MFCQ_Slater_or_other relevant constraint qualification
 -> derive Lagrangian_KKT_or_problem_specific optimality conditions
 -> select projected_activeSet_penalty_barrier_interiorPoint_augmentedLagrangian_SQP_or_feasibility_restoration method
 -> compute_or_assess candidate_solution
 -> verify primal_feasibility_dual_feasibility_complementary_slackness_stationarity_and_tolerances
 -> analyse sensitivity_and_shadow prices when appropriate
 -> route to optimisation_ontology nonlinear_optimisation convex_optimisation linear_programming integer_programming dynamic_optimisation numerical_analysis linear_algebra calculus operations_research_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Constraint Optimisation Ontology defines optimisation over explicitly restricted feasible regions. It supports equality, inequality, bound, linear, nonlinear, integrality, logical and dynamic constraints, feasible sets, active sets, tangent and normal geometry, Lagrangians, multipliers, KKT conditions, LICQ, MFCQ and Slater-type qualifications, projected and active-set methods, penalty, barrier and interior-point methods, augmented Lagrangians, SQP, feasibility restoration, merit and filter methods, duality, shadow prices and constrained sensitivity reasoning."
}

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

}

END_FLOW