Convex Optimisation Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Convex Optimisation Ontology within the Kireth Research Semantic Library. Convex optimisation studies optimisation problems in which the objective function is convex for minimisation and the feasible set is convex. This structure provides powerful guarantees: every local optimum is global, first-order conditions often become globally meaningful, duality theory is especially strong, and many numerical algorithms admit rigorous convergence guarantees. This ontology supports convex functions, convex sets, epigraphs, subgradients, smooth and nonsmooth convex optimisation, linear and quadratic programming, second-order cone programming, semidefinite programming, proximal methods, projected methods, interior-point methods, Fenchel duality, KKT conditions, Slater’s condition, strong duality, optimality certificates and relationships with convex geometry, linear algebra, numerical analysis and operations research.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = ConvexOptimisation
 SYMBOLIC_FORMS = [
  "min_x f(x) subject to x in C",
  "f(theta x + (1-theta)y) <= theta f(x)+(1-theta)f(y)",
  "min f(x) subject to g_i(x)<=0, Ax=b"
 ]
 ENTITY_CLASS = ConvexMathematicalProgrammingFramework
 PRIMARY_CONTEXT = Optimisation
 DEFINITION = "Convex optimisation is the minimisation of a convex objective over a convex feasible set, including equivalent maximisation of concave objectives."
 SEMANTIC_ROLE = "Provides the machine-readable framework for convex functions, convex feasible sets, global optimality, subgradient conditions, duality, conic formulations, proximal algorithms and optimality certificates."
}

SCOPE {
 INCLUDE = [
  ConvexOptimisation,
  ConvexFunction,
  StrictlyConvexFunction,
  StronglyConvexFunction,
  ConcaveFunction,
  ConvexSet,
  AffineSet,
  ConvexCone,
  Epigraph,
  Hypograph,
  Subgradient,
  Subdifferential,
  Gradient,
  Hessian,
  LipschitzGradient,
  StrongConvexity,
  SmoothConvexOptimisation,
  NonsmoothConvexOptimisation,
  ConstrainedConvexOptimisation,
  UnconstrainedConvexOptimisation,
  LinearProgramming,
  ConvexQuadraticProgramming,
  SecondOrderConeProgramming,
  SemidefiniteProgramming,
  ConicOptimisation,
  ProjectedGradientMethod,
  SubgradientMethod,
  ProximalGradientMethod,
  ProximalPointMethod,
  AcceleratedGradientMethod,
  NesterovAcceleration,
  CoordinateDescent,
  InteriorPointMethod,
  BarrierMethod,
  Lagrangian,
  DualFunction,
  ConvexDuality,
  FenchelDuality,
  WeakDuality,
  StrongDuality,
  SlaterCondition,
  KarushKuhnTuckerConditions,
  ComplementarySlackness,
  OptimalityCertificate,
  PrimalDualGap
 ]

 EXCLUDE_AS_PRIMARY = [
  NonconvexOptimisation,
  ArbitraryIntegerProgrammingWithoutConvexRelaxationContext,
  RootFindingWithoutOptimisationStructure,
  GenericLinearAlgebraWithoutObjectiveOrFeasibleSet
 ]

 DISAMBIGUATION_RULE =
  "When the objective is convex in minimisation form and the feasible region is convex, interpret the problem as convex optimisation."
}

CORE_CONCEPTS {

 ConvexOptimisation {
  definition = "Optimisation over convex structure with global optimality guarantees."
 }

 ConvexFunction {
  definition = "A function whose graph lies below chords connecting any two points in its domain."
 }

 StrictlyConvexFunction {
  definition = "A convex function for which the convexity inequality is strict for distinct points and interior convex combinations."
 }

 StronglyConvexFunction {
  definition = "A convex function possessing a positive quadratic lower-curvature bound."
 }

 ConvexSet {
  definition = "A set containing the full line segment between any two of its points."
 }

 ConvexCone {
  definition = "A convex set closed under multiplication by nonnegative scalars."
 }

 Epigraph {
  definition = "The set of points lying on or above a function graph."
 }

 Subgradient {
  definition = "A vector defining a global affine lower bound to a convex function at a point."
 }

 Subdifferential {
  definition = "The set of all subgradients of a convex function at a point."
 }

 ProximalOperator {
  definition = "The minimiser of a function plus a quadratic proximity penalty."
 }

 ConicOptimisation {
  definition = "Optimisation where constraints are represented using membership in convex cones."
 }

 SlaterCondition {
  definition = "A strict-feasibility condition that commonly guarantees strong duality for convex problems."
 }
}

RELATIONS {
 ConvexOptimisation --is_special_case_of--> Optimisation
 ConvexOptimisation --has--> ConvexObjective
 ConvexOptimisation --has--> ConvexFeasibleSet
 ConvexFunction --has--> Epigraph
 ConcaveFunction --has--> Hypograph
 StrictlyConvexFunction --is_type_of--> ConvexFunction
 StronglyConvexFunction --is_type_of--> StrictlyConvexFunction
 Subgradient --is_element_of--> Subdifferential
 LinearProgramming --is_special_case_of--> ConvexOptimisation
 ConvexQuadraticProgramming --is_special_case_of--> ConvexOptimisation
 SecondOrderConeProgramming --is_special_case_of--> ConicOptimisation
 SemidefiniteProgramming --is_special_case_of--> ConicOptimisation
 ConicOptimisation --is_special_case_of--> ConvexOptimisation
 ProjectedGradientMethod --solves--> ConstrainedConvexOptimisation
 ProximalGradientMethod --uses--> ProximalOperator
 InteriorPointMethod --uses--> BarrierMethod
 ConvexDuality --relates--> PrimalProblem
 ConvexDuality --relates--> DualProblem
 SlaterCondition --supports--> StrongDuality
 KarushKuhnTuckerConditions --characterise--> ConvexOptimality
 PrimalDualGap --certifies--> ApproximateOptimality
}

OPERATORS {
 CONVEXITY_TEST(f,x,y,theta) :=
  f(theta*x+(1-theta)*y) <= theta*f(x)+(1-theta)*f(y)
  for theta in [0,1]

 SET_CONVEXITY_TEST(C,x,y,theta) :=
  theta*x+(1-theta)*y in C
  for x,y in C and theta in [0,1]

 FIRST_ORDER_CONVEXITY(f,x,y) :=
  f(y) >= f(x)+grad_f(x)^T*(y-x)
  for differentiable convex f

 HESSIAN_CONVEXITY_TEST(H) :=
  H positive_semidefinite
  on convex domain

 SUBGRADIENT_CONDITION(f,x,g) :=
  f(y) >= f(x)+g^T*(y-x)
  for all y

 PROXIMAL_OPERATOR(f,v,lambda) :=
  argmin_x f(x)+(1/(2*lambda))*||x-v||^2

 PROJECTED_GRADIENT_STEP(x,alpha,C) :=
  projection_C(x-alpha*grad_f(x))

 PROXIMAL_GRADIENT_STEP(x,alpha,f,g) :=
  prox_{alpha*g}(x-alpha*grad_f(x))

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

 DUAL_FUNCTION(lambda,nu) :=
  inf_x L(x,lambda,nu)

 PRIMAL_DUAL_GAP(primal_value,dual_value) :=
  primal_value-dual_value
  for minimisation

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

DEFINITIONS {
 D1 = "Convex optimisation minimises a convex objective over a convex feasible set."
 D2 = "Every local optimum of a convex optimisation problem is global."
 D3 = "Strict convexity can imply uniqueness of the optimum."
 D4 = "Strong convexity provides quantitative curvature and often faster convergence guarantees."
 D5 = "Subgradients generalise gradients to nonsmooth convex functions."
 D6 = "Projection maps a point to the nearest point in a convex feasible set under the chosen norm."
 D7 = "Proximal operators handle nonsmooth convex terms through regularised local minimisation."
 D8 = "Slater's condition commonly guarantees strong duality in convex problems."
 D9 = "KKT conditions can become necessary and sufficient under convexity and appropriate regularity."
 D10 = "Primal-dual gaps provide practical optimality certificates."
}

AXIOMS {
 A1_CONVEX_OBJECTIVE:
  ConvexOptimisation in minimisation form has a convex objective

 A2_CONVEX_FEASIBILITY:
  FeasibleSet is convex

 A3_LOCAL_GLOBAL:
  Every local optimum is global

 A4_STRICT_UNIQUENESS:
  Strict convexity over a convex feasible set implies at most one minimiser

 A5_SUBGRADIENT_OPTIMALITY:
  For unconstrained convex f, x_star is optimal iff 0 belongs to subdifferential(f,x_star)

 A6_KKT_SUFFICIENCY:
  For convex differentiable problems, KKT conditions are sufficient for global optimality

 A7_SLATER_STRONG_DUALITY:
  Under Slater-type conditions, strong duality holds for broad convex problem classes

 A8_GAP_CERTIFICATION:
  A small valid primal-dual gap certifies near-optimality
}

REASONING {

 R1_CONVEXITY_IDENTIFICATION {
  INPUT = optimisation_problem
  CHECK = objective_convexity
  CHECK = each_inequality_constraint_convexity
  CHECK = equality_constraints_affine
  RETURN = convex_or_not
 }

 R2_OBJECTIVE_CONVEXITY {
  INPUT = objective
  IF differentiable_twice
   CHECK = Hessian_positive_semidefinite
  ELSE
   CHECK = convexity_definition_or_known composition rules
  RETURN = convexity_profile
 }

 R3_FEASIBLE_SET_CONVEXITY {
  INPUT = constraints
  CHECK = affine_equalities
  CHECK = convex_inequalities
  CHECK = cone_or_set memberships
  RETURN = convex_feasible_set_status
 }

 R4_FIRST_ORDER_OPTIMALITY {
  INPUT = unconstrained_convex_problem_and_candidate
  IF smooth
   CHECK = gradient_zero
  ELSE
   CHECK = zero_in_subdifferential
  RETURN = global_optimality_status
 }

 R5_CONSTRAINED_KKT {
  INPUT = constrained_convex_problem
  CHECK = primal_feasibility
  CHECK = constraint_qualification
  FORM = Lagrangian
  SOLVE_OR_TEST = KKT_system
  RETURN = global_optimality_status
 }

 R6_DUALITY_REASONING {
  INPUT = primal_convex_problem
  FORM = Lagrangian
  DERIVE = dual_function
  CONSTRUCT = dual_problem
  CHECK = Slater_or_other regularity
  RETURN = weak_or_strong_duality profile
 }

 R7_ALGORITHM_SELECTION {
  INPUT = convex_problem_structure
  IF smooth_unconstrained
   CONSIDER = gradient_accelerated_gradient_Newton
  IF simple_convex_constraints
   CONSIDER = projected_gradient
  IF composite_smooth_plus_nonsmooth
   CONSIDER = proximal_gradient
  IF conic_structure
   CONSIDER = interior_point_or_first_order conic method
  RETURN = solver_strategy
 }

 R8_PROXIMAL_REASONING {
  INPUT = composite_objective f_plus_g
  COMPUTE = gradient_of_smooth_part
  APPLY = proximal_operator_of_nonsmooth_part
  RETURN = proximal_gradient_iterate
 }

 R9_ACCELERATED_REASONING {
  INPUT = smooth_convex_problem
  APPLY = momentum_or_Nesterov acceleration
  MONITOR = objective_and_gradient behaviour
  RETURN = accelerated_sequence
 }

 R10_CERTIFICATION {
  INPUT = primal_candidate_dual_candidate
  CHECK = feasibility
  COMPUTE = primal_dual_gap
  RETURN = exact_or_approximate_optimality certificate
 }
}

CONSTRAINTS {
 C1 = "Convexity claims require a convex domain."
 C2 = "Equality constraints must be affine in standard convex programming form."
 C3 = "A local optimum is globally optimal only when convexity assumptions hold."
 C4 = "Strict convexity is sufficient for uniqueness but not necessary."
 C5 = "Subgradient methods may converge slowly."
 C6 = "Projection must be onto the correct feasible set and norm."
 C7 = "Proximal operators must correspond to the intended nonsmooth term."
 C8 = "Strong duality requires appropriate regularity conditions."
 C9 = "Interior-point methods require numerically stable linear algebra."
 C10 = "A numerical solver's termination status is not a certificate unless feasibility and optimality conditions are verified."
}

SEMANTIC_EQUIVALENCE {
 "ConvexOptimisation" <=> "ConvexOptimization"
 "ConvexFunction" <=> "FunctionWithConvexEpigraph"
 "ConvexSet" <=> "SetClosedUnderLineSegments"
 "Subgradient" <=> "GlobalAffineUnderestimatorSlope"
 "ProximalGradientMethod" <=> "ForwardBackwardSplitting"
 "PrimalDualGap" <=> "ConvexOptimalityGapCertificate"
}

VALIDATION {
 V1 = "Objective convexity is established."
 V2 = "Feasible-set convexity is established."
 V3 = "Equality constraints are affine where required."
 V4 = "Candidate feasibility is checked."
 V5 = "Gradient or subgradient conditions are applied correctly."
 V6 = "Constraint qualification is considered."
 V7 = "Dual formulation uses consistent conventions."
 V8 = "Primal-dual gap is nonnegative under weak-duality conventions."
 V9 = "Solver structure matches smooth, nonsmooth or conic form."
 V10 = "Global-optimality claim is grounded in convexity and valid conditions."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 CONVEX_OPTIMISATION_DEFINITION = 0.99
 CONVEXITY_IDENTIFICATION_REASONING = 0.99
 FIRST_ORDER_REASONING = 0.99
 KKT_REASONING = 0.99
 DUALITY_REASONING = 0.99
 PROXIMAL_REASONING = 0.98
 ACCELERATED_REASONING = 0.98
 CERTIFICATION_REASONING = 0.99

 POLICY =
  "Reduce confidence when domain convexity, Hessian definiteness, subgradient structure, constraint qualification, dual feasibility, cone representation or solver tolerances are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  ConvexOptimisationReasoning,
  ConvexityChecking,
  ConvexSetReasoning,
  ConvexFunctionReasoning,
  SubgradientReasoning,
  KKTReasoning,
  ConvexDualityReasoning,
  SlaterConditionReasoning,
  ProjectedGradientReasoning,
  ProximalGradientReasoning,
  NesterovAccelerationReasoning,
  ConicOptimisationReasoning,
  InteriorPointReasoning,
  OptimalityCertification,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "convex optimisation" -> ConvexOptimisation
  "convex optimization" -> ConvexOptimisation
  "convex function" -> ConvexFunction
  "convex set" -> ConvexSet
  "subgradient" -> Subgradient
  "subdifferential" -> Subdifferential
  "proximal gradient" -> ProximalGradientMethod
  "projected gradient" -> ProjectedGradientMethod
  "Slater's condition" -> SlaterCondition
  "primal-dual gap" -> PrimalDualGap
 }

 INTERPRETATION_ORDER = [
  detect_convex_optimisation_context,
  identify objective_feasible_set_constraints_domains_smoothness_and_conic structure,
  verify objective_and_feasible_set convexity,
  classify smooth_nonsmooth_constrained_unconstrained_linear_quadratic_conic_or_semidefinite problem,
  derive gradient_subgradient_KKT_or_dual optimality conditions,
  select gradient_projected_proximal_accelerated_interior_point_or_conic solver pathway,
  compute_or_assess candidate_solution,
  derive dual_certificate_and_primal_dual gap,
  assign global_optimality_or_approximate certificate,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("convex optimisation")
  OR convex_objective_with_convex_feasible_set
  THEN activate(ConvexOptimisationOntology)

 E2:
  IF twice_differentiable_objective
  THEN use Hessian_positive_semidefinite test where appropriate

 E3:
  IF nonsmooth_convex_objective
  THEN use subgradient_or_proximal reasoning

 E4:
  IF simple_convex_constraint_set
  THEN consider projected_gradient

 E5:
  IF objective_is_smooth_plus_proximable_nonsmooth
  THEN consider proximal_gradient

 E6:
  IF constrained_problem
  THEN assess Slater_condition_or_other qualification

 E7:
  IF primal_and_dual_feasible
  THEN compute primal_dual gap

 E8:
  IF KKT_conditions_hold_under_convexity_and_valid qualification
  THEN certify global_optimality

 E9:
  IF solver_reports_local_optimum_in_convex_problem
  THEN reinterpret as global only after verifying convexity assumptions
}

RECURSION {
 ENTRY = ConvexOptimisation

 EXPAND(ConvexOptimisation) -> [
  ConvexFunction,
  StrictlyConvexFunction,
  StronglyConvexFunction,
  ConcaveFunction,
  ConvexSet,
  AffineSet,
  ConvexCone,
  Epigraph,
  Hypograph,
  Subgradient,
  Subdifferential,
  Gradient,
  Hessian,
  SmoothConvexOptimisation,
  NonsmoothConvexOptimisation,
  LinearProgramming,
  ConvexQuadraticProgramming,
  SecondOrderConeProgramming,
  SemidefiniteProgramming,
  ConicOptimisation,
  ProjectedGradientMethod,
  SubgradientMethod,
  ProximalGradientMethod,
  ProximalPointMethod,
  AcceleratedGradientMethod,
  NesterovAcceleration,
  CoordinateDescent,
  InteriorPointMethod,
  BarrierMethod,
  Lagrangian,
  DualFunction,
  FenchelDuality,
  SlaterCondition,
  KarushKuhnTuckerConditions,
  ComplementarySlackness,
  OptimalityCertificate,
  PrimalDualGap
 ]

 EXPAND(ConvexFunctionStructure) -> [
  Epigraph,
  Gradient,
  Hessian,
  Subgradient,
  StrongConvexity,
  LipschitzGradient
 ]

 EXPAND(ConicOptimisation) -> [
  LinearProgramming,
  SecondOrderConeProgramming,
  SemidefiniteProgramming,
  ConeConstraint,
  DualCone,
  PrimalDualInteriorPointMethod
 ]

 EXPAND(FirstOrderMethods) -> [
  GradientDescent,
  ProjectedGradientMethod,
  SubgradientMethod,
  ProximalGradientMethod,
  AcceleratedGradientMethod,
  CoordinateDescent
 ]

 STOP_CONDITION =
  "Stop when convexity, feasible-set geometry, optimality conditions, solver pathway, duality, primal-dual gap and global optimality status are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Optimisation"

 IMMEDIATE_CONTEXTS = [
  "Optimisation Ontology",
  "Linear Programming Ontology",
  "Convex Geometry Ontology",
  "Numerical Analysis Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Optimisation Ontology",
  "Optimisation",
  "Linear Programming Ontology",
  "Nonlinear Optimisation Ontology",
  "Convex Geometry Ontology",
  "Linear Algebra Ontologies",
  "Calculus & Analysis Ontologies",
  "Numerical Analysis Ontologies",
  "Operations Research Ontologies",
  "Probability & Statistics Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Convex Optimisation -> Optimisation Ontology for formal optimisation semantics",
  "Convex Optimisation -> Linear Programming for polyhedral convex problems",
  "Convex Optimisation -> Nonlinear Optimisation for smooth nonlinear convex problems",
  "Convex Optimisation -> Convex Geometry for feasible-set and cone structure",
  "Convex Optimisation -> Linear Algebra for quadratic forms and semidefinite constraints",
  "Convex Optimisation -> Calculus & Analysis for convexity, gradients and Hessians",
  "Convex Optimisation -> Numerical Analysis for convergence and solver stability",
  "Convex Optimisation -> Operations Research for resource allocation and conic models",
  "Convex Optimisation -> Probability & Statistics for convex estimation objectives",
  "Convex Optimisation -> Scientific Computing for large-scale first-order and interior-point implementations"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible convex problem classes, duality results or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve convex-objective and convex-feasible-set semantics.",
  "Preserve local-equals-global semantics under convexity.",
  "Preserve subgradient semantics.",
  "Preserve Slater and strong-duality semantics.",
  "Preserve primal-dual-gap certification.",
  "Preserve conic optimisation structure.",
  "Preserve nonsmooth proximal semantics.",
  "Preserve machine-readable convex-optimisation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Convex optimisation minimises a convex objective over a convex feasible set."

 GLOBAL_OPTIMALITY_SUMMARY =
  "Every local optimum of a convex optimisation problem is global."

 CONVEXITY_SUMMARY =
  "Convexity can be established through definitions, composition rules, epigraphs or positive-semidefinite Hessians when twice differentiable."

 SUBGRADIENT_SUMMARY =
  "For unconstrained convex problems, zero in the subdifferential characterises global optimality."

 KKT_SUMMARY =
  "Under convexity and suitable regularity, KKT conditions are necessary and sufficient for global optimality."

 DUALITY_SUMMARY =
  "Convex duality provides strong lower bounds and, under regularity such as Slater's condition, zero duality gap."

 PROXIMAL_SUMMARY =
  "Proximal methods efficiently handle composite objectives containing nonsmooth convex terms."

 CONIC_SUMMARY =
  "Linear, second-order cone and semidefinite programmes are major convex conic optimisation classes."

 CERTIFICATION_SUMMARY =
  "Primal-dual feasibility and a small primal-dual gap provide a practical certificate of near-optimality."
}

FLOW {
 INPUT
 -> detect_convex_optimisation_context
 -> identify objective_decision_variables_domains_constraints_cones_smoothness_and_nonsmooth structure
 -> verify convexity_of_objective_and_feasible set
 -> classify unconstrained_constrained_smooth_nonsmooth_linear_quadratic_SOCP_SDP_or_general conic problem
 -> derive gradient_subgradient_KKT_Fenchel_or_primal_dual optimality conditions
 -> select gradient_projected_subgradient_proximal_accelerated_coordinate_descent_interior_point_or_conic method
 -> compute_or_assess primal_candidate
 -> derive dual_candidate_and_bounds
 -> evaluate primal_feasibility_dual_feasibility_complementary_slackness_and_primal_dual gap
 -> certify global_or_approximate optimality
 -> route to optimisation_ontology linear_programming nonlinear_optimisation convex_geometry linear_algebra calculus numerical_analysis operations_research probability_statistics_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Convex Optimisation Ontology defines globally structured optimisation over convex objectives and feasible sets. It supports convex and strongly convex functions, convex sets and cones, epigraphs, subgradients, smooth and nonsmooth optimisation, linear, quadratic, second-order cone and semidefinite programming, projected, subgradient, proximal and accelerated methods, interior-point algorithms, KKT conditions, Slater's condition, Fenchel and Lagrangian duality, complementary slackness, primal-dual gaps and global optimality certification."
}

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

}

END_FLOW