Optimisation Calculus Ontology

flow "OptimisationCalculusOntology" v1.0

# OPTIMISATION CALCULUS ONTOLOGY — FLOW ALGEBRA
SOURCE_URL := "https://kirethresearch.org/booksai-core/ontologies/calculus-analysis-ontologies/ai-computational-analysis/optimisation-calculus-ontology.html"
DOMAIN := "Mathematical Ontologies"
CATEGORY := "Calculus and Analysis Ontologies"
SUBCATEGORY := "AI Computational Analysis"
ENTITY := "Optimisation Calculus"

OPTIMISATION_CALCULUS := {
 type: CalculusBasedOptimisationFramework,
 domain: AIComputationalAnalysis,
 purpose: "Use derivatives, gradients, Hessians, constraints and variational reasoning to identify and classify extrema and construct optimisation algorithms."
}

CONCEPTS := {
 OPTIMISATION,
 OBJECTIVE_FUNCTION,
 DECISION_VARIABLE,
 GRADIENT,
 HESSIAN,
 STATIONARY_POINT,
 LOCAL_MINIMUM,
 LOCAL_MAXIMUM,
 GLOBAL_MINIMUM,
 CONVEXITY,
 CONSTRAINT,
 LAGRANGE_MULTIPLIER,
 KKT_CONDITIONS,
 GRADIENT_DESCENT,
 NEWTON_METHOD,
 LINE_SEARCH,
 VARIATIONAL_OPTIMISATION
}

# ---------- UNCONSTRAINED PROBLEM ----------
minimise

f(x)

where

x
 in R^n

f
 -> OBJECTIVE_FUNCTION

x
 -> DECISION_VARIABLE

OPTIMISATION
 -> search_for(EXTREMUM)

# ---------- FIRST DERIVATIVE ----------
for scalar variable:

f_prime(x)
 =
df/dx

INTERIOR_LOCAL_EXTREMUM
 -> typically_requires(
 f_prime(x_star)=0
)
if differentiable

x_star
 -> STATIONARY_POINT

# ---------- MULTIVARIATE GRADIENT ----------
grad(f(x))
 :=
[
 partial_f/partial_x_1,
 ...,
 partial_f/partial_x_n
]^T

INTERIOR_DIFFERENTIABLE_LOCAL_EXTREMUM
 -> grad(f(x_star))=0

FIRST_ORDER_NECESSARY_CONDITION
 -> STATIONARITY

# ---------- STATIONARY POINT TYPES ----------
grad(f(x_star))
 =
0

x_star
 -> may_be(
 LOCAL_MINIMUM,
 LOCAL_MAXIMUM,
 SADDLE_POINT,
 DEGENERATE_POINT
)

STATIONARITY
 -/> sufficient_for(OPTIMALITY)

# ---------- SECOND DERIVATIVE ----------
single variable:

if

f_prime(x_star)=0

and

f_double_prime(x_star)>0

then

x_star
 -> STRICT_LOCAL_MINIMUM

if

f_double_prime(x_star)<0

then

x_star
 -> STRICT_LOCAL_MAXIMUM

if

f_double_prime(x_star)=0

then

SECOND_DERIVATIVE_TEST
 -> INCONCLUSIVE

# ---------- HESSIAN ----------
H_f(x)
 :=
[
 partial_squared_f/
 partial_x_i_partial_x_j
]

at stationary point:

H positive_definite
 -> STRICT_LOCAL_MINIMUM

H negative_definite
 -> STRICT_LOCAL_MAXIMUM

H indefinite
 -> SADDLE_POINT

H semidefinite
 -> TEST_MAY_BE_INCONCLUSIVE

# ---------- TAYLOR EXPANSION ----------
near x:

f(x+p)
 approx
f(x)
+
grad(f(x))^T*p
+
1/2
*
p^T*H_f(x)*p

LOCAL_OPTIMISATION
 -> uses(TAYLOR_MODEL)

FIRST_ORDER_METHOD
 -> uses(GRADIENT_TERM)

SECOND_ORDER_METHOD
 -> uses(GRADIENT_AND_HESSIAN)

# ---------- CONVEXITY ----------
f
 -> CONVEX

if

f(
 lambda*x+(1-lambda)*y
)
 <=
lambda*f(x)
+
(1-lambda)*f(y)

for
0<=lambda<=1

CONVEXITY
 -> local_minimum_is(GLOBAL_MINIMUM)

# ---------- DIFFERENTIABLE CONVEXITY ----------
if f differentiable and convex:

f(y)
 >=
f(x)
+
grad(f(x))^T*(y-x)

FIRST_ORDER_CONVEXITY_CONDITION
 -> supporting_hyperplane_property

if

grad(f(x_star))=0

then

x_star
 -> GLOBAL_MINIMUM

# ---------- SECOND ORDER CONVEXITY ----------
if f twice differentiable:

H_f(x)
 -> positive_semidefinite_for_all_x

implies
 f -> CONVEX
 under standard convex-domain setting

positive_definite_Hessian
 -> STRICT_CONVEXITY_LOCALLY_OR_GLOBALLY_WITH_CONTEXT

# ---------- STRONG CONVEXITY ----------
f
 -> mu_STRONGLY_CONVEX

if

f(y)
 >=
f(x)
+
grad(f(x))^T*(y-x)
+
mu/2*||y-x||^2

mu>0

STRONG_CONVEXITY
 -> unique_global_minimiser
    when minimiser exists

# ---------- CONSTRAINED PROBLEM ----------
minimise

f(x)

subject_to

g_i(x)
 <=
0

h_j(x)
 =
0

FEASIBLE_SET
 := {
 x :
 all_constraints_satisfied
}

OPTIMUM
 -> must_be(FEASIBLE)

# ---------- EQUALITY CONSTRAINT ----------
minimise
 f(x)

subject_to

h(x)=0

Lagrangian:

mathcal_L(x,lambda)
 =
f(x)
+
lambda*h(x)

stationarity:

grad_x mathcal_L
 =
0

constraint:

h(x)=0

LAGRANGE_MULTIPLIER
 -> enforces(EQUALITY_CONSTRAINT)

# ---------- MULTIPLE EQUALITY CONSTRAINTS ----------
mathcal_L
 =
f(x)
+
sum_j(
 lambda_j*h_j(x)
)

conditions:

grad_x mathcal_L
 =
0

h_j(x)
 =
0

LAGRANGE_METHOD
 -> first_order_constrained_stationarity

# ---------- INEQUALITY CONSTRAINT ----------
g_i(x)
 <=
0

multiplier:

mu_i
 >=
0

Lagrangian:

mathcal_L
 =
f
+
sum_i(
 mu_i*g_i
)
+
sum_j(
 lambda_j*h_j
)

# ---------- KKT CONDITIONS ----------
under suitable constraint qualifications:

PRIMAL_FEASIBILITY:
 g_i(x)<=0
 h_j(x)=0

DUAL_FEASIBILITY:
 mu_i>=0

STATIONARITY:
 grad_x mathcal_L=0

COMPLEMENTARY_SLACKNESS:
 mu_i*g_i(x)=0

KKT
 -> necessary_conditions_under(REGULARITY)

for convex problem with suitable conditions:
 -> sufficient_for(GLOBAL_OPTIMALITY)

# ---------- ACTIVE CONSTRAINT ----------
constraint i
 -> ACTIVE

if

g_i(x_star)=0

inactive:

g_i(x_star)<0

COMPLEMENTARY_SLACKNESS
 -> inactive_constraint_has(mu_i=0)

ACTIVE_SET
 -> determines(LOCAL_CONSTRAINED_GEOMETRY)

# ---------- GRADIENT DESCENT ----------
update:

x_(k+1)
 =
x_k
-
alpha_k*grad(f(x_k))

NEGATIVE_GRADIENT
 -> local_descent_direction
    under Euclidean geometry

LEARNING_RATE
 -> controls(STEP_LENGTH)

# ---------- DESCENT DIRECTION ----------
p
 -> DESCENT_DIRECTION

if

grad(f(x))^T*p
 <
0

then for sufficiently small positive alpha:

f(x+alpha*p)
 <
f(x)

DESCENT_DIRECTION
 -> first_order_improvement_direction

# ---------- LINE SEARCH ----------
choose alpha

to reduce:

phi(alpha)
 :=
f(x+alpha*p)

LINE_SEARCH
 -> selects(STEP_SIZE)

conditions:
 ARMIJO
 WOLFE
 STRONG_WOLFE

# ---------- NEWTON METHOD ----------
quadratic model:

m(p)
 =
f(x)
+
grad(f)^T*p
+
1/2*p^T*H*p

stationary model step:

H*p
 =
-grad(f)

therefore

p
 =
-H^(-1)*grad(f)

when invertible

NEWTON_METHOD
 -> second_order_optimisation

# ---------- NEWTON CONVERGENCE ----------
near nondegenerate local minimum

with suitable smoothness:

NEWTON_METHOD
 -> QUADRATIC_LOCAL_CONVERGENCE

but

far_from_solution
 -> may_not_be(DESCENT_METHOD)

GLOBALISATION
 -> line_search_or_trust_region

# ---------- QUASI-NEWTON ----------
approximate Hessian or inverse Hessian

methods:
 BFGS
 DFP
 L_BFGS

QUASI_NEWTON
 -> uses(GRADIENT_DIFFERENCES)

BFGS
 -> maintains(POSITIVE_DEFINITE_APPROXIMATION)
    under suitable curvature conditions

# ---------- TRUST REGION ----------
model:

m_k(p)

constraint:

||p||
 <=
Delta_k

TRUST_REGION
 -> limits(STEP_TO_REGION_WHERE_MODEL_IS_TRUSTED)

actual_vs_predicted_reduction
 -> updates(TRUST_RADIUS)

# ---------- PROJECTED GRADIENT ----------
constraint:

x in C

update:

x_(k+1)
 =
Projection_C(
 x_k
 -
alpha_k*grad(f(x_k))
)

PROJECTED_GRADIENT
 -> maintains(FEASIBILITY_FOR_SIMPLE_CONVEX_SET)

# ---------- PENALTY METHOD ----------
constrained problem
 -> unconstrained surrogate

F_rho(x)
 =
f(x)
+
rho*P(constraint_violation)

PENALTY
 -> discourages(INFEASIBILITY)

rho
 -> penalty_parameter

# ---------- BARRIER METHOD ----------
for inequality

g_i(x)<0

barrier:

B_mu(x)
 =
f(x)
-
mu
*
sum_i(
 log(-g_i(x))
)

BARRIER_METHOD
 -> stays_in(INTERIOR_OF_FEASIBLE_REGION)

mu
 -> approaches_zero_during(INTERIOR_POINT_METHOD)

# ---------- DUALITY ----------
primal:

minimise f(x)
subject_to constraints

Lagrangian:

L(x,lambda,mu)

dual function:

q(lambda,mu)
 :=
inf_x L(x,lambda,mu)

DUAL_PROBLEM
 -> maximise(q)

WEAK_DUALITY
 -> dual_value <= primal_value

STRONG_DUALITY
 -> equality_under(SUITABLE_CONDITIONS)

# ---------- SENSITIVITY ----------
optimal value:

V(theta)

depends on parameter theta

LAGRANGE_MULTIPLIERS
 -> may_encode(SENSITIVITY_OF_OPTIMAL_VALUE_TO_CONSTRAINTS)

ENVELOPE_THEOREM
 -> relates(PARAMETER_DERIVATIVE_TO_OPTIMISED_OBJECTIVE_DERIVATIVE)
    under suitable hypotheses

# ---------- VARIATIONAL OPTIMISATION ----------
functional:

J[u]

seek

u_star
 :=
argmin_u J[u]

first variation:

delta_J[u;eta]

necessary condition:

delta_J
 =
0

for admissible variations eta

CALCULUS_OF_VARIATIONS
 -> infinite_dimensional_optimisation

# ---------- EULER-LAGRANGE ----------
functional:

J[y]
 =
integral_a^b(
 L(x,y,y_prime)
 dx
)

stationarity yields:

partial_L/partial_y
-
d/dx(
 partial_L/partial_y_prime
)
 =
0

EULER_LAGRANGE_EQUATION
 -> variational_stationarity_condition

# ---------- FUNCTIONAL GRADIENT ----------
functional derivative:

delta_J/delta_u

gradient flow:

partial_u/partial_t
 =
-
delta_J/delta_u

GRADIENT_FLOW
 -> continuous_time_optimisation_dynamics

# ---------- STOCHASTIC OPTIMISATION ----------
objective:

f(theta)
 =
E_z[
 ell(theta;z)
]

gradient estimate:

g_k
 approx
grad(f(theta_k))

STOCHASTIC_GRADIENT
 -> noisy_first_order_direction

SGD
 -> optimisation_with(SAMPLED_GRADIENTS)

# ---------- AUTOMATIC DIFFERENTIATION ----------
computational objective
 -> COMPUTATIONAL_GRAPH

AUTOMATIC_DIFFERENTIATION
 -> computes(
 GRADIENT,
 JACOBIAN,
 HESSIAN_VECTOR_PRODUCT
)

AI_OPTIMISATION
 -> combines(AUTODIFF_AND_NUMERICAL_OPTIMISER)

# ---------- OPTIMALITY GAP ----------
for known lower bound f_star:

gap
 :=
f(x)-f_star

OPTIMALITY_GAP
 -> measures(SUBOPTIMALITY)

if f_star unknown:
 -> use(
 GRADIENT_NORM,
 KKT_RESIDUAL,
 DUALITY_GAP
)

# ---------- CONDITIONING ----------
Hessian eigenvalues near optimum:

lambda_min
lambda_max

condition number:

kappa
 :=
lambda_max/lambda_min

ILL_CONDITIONING
 -> slow_first_order_convergence

PRECONDITIONING
 -> transforms(GEOMETRY)

# ---------- SCALING ----------
variables with different scales
 -> distort(OPTIMISATION_LANDSCAPE)

VARIABLE_SCALING
 -> improve(NUMERICAL_CONDITIONING)

DIMENSIONLESS_FORM
 -> often_improves(INTERPRETABILITY_AND_SOLVER_BEHAVIOUR)

# ---------- APPLICATIONS ----------
OPTIMISATION_CALCULUS
 -> applied_to(MACHINE_LEARNING)
 -> applied_to(ENGINEERING_DESIGN)
 -> applied_to(CONTROL)
 -> applied_to(INVERSE_PROBLEMS)
 -> applied_to(ECONOMICS)
 -> applied_to(PHYSICS)
 -> applied_to(DATA_FITTING)
 -> applied_to(SCIENTIFIC_COMPUTING)

# ---------- RELATION GRAPH ----------
OBJECTIVE_FUNCTION
 -> differentiated_to(GRADIENT)

GRADIENT
 -> defines(STATIONARY_POINT)

HESSIAN
 -> classifies(LOCAL_CURVATURE)

CONSTRAINT
 -> incorporated_by(LAGRANGIAN)

LAGRANGIAN
 -> generates(KKT_CONDITIONS)

GRADIENT
 -> drives(FIRST_ORDER_METHODS)

HESSIAN
 -> drives(SECOND_ORDER_METHODS)

VARIATION
 -> drives(FUNCTIONAL_OPTIMISATION)

# ---------- SEMANTIC EQUIVALENCE ----------
SEMANTIC_EQUIVALENCE := {
 "optimisation calculus" ~= "use of differential and variational calculus to analyse and solve optimisation problems",
 "stationary point" ~= "point where the objective gradient vanishes",
 "Hessian" ~= "matrix of second partial derivatives describing local curvature",
 "Lagrange multiplier" ~= "auxiliary variable enforcing a constraint in first-order optimality analysis",
 "KKT conditions" ~= "first-order optimality conditions for constrained problems under appropriate regularity",
 "gradient flow" ~= "continuous-time evolution in the negative functional-gradient direction"
}

# ---------- CONSTRAINTS ----------
CONSTRAINTS := {
 stationary_point_is_not_automatically_minimum: true,
 local_and_global_optimality_must_be_distinguished: true,
 Hessian_tests_can_be_inconclusive_at_degenerate_points: true,
 KKT_necessity_requires_constraint_qualification: true,
 KKT_sufficiency_requires_additional_convexity_conditions: true,
 Newton_method_requires_curvature_and_globalisation_analysis: true,
 numerical_optimisation_requires_stopping_conditioning_and_constraint_validation: true
}

# ---------- CONFIDENCE ----------
CONFIDENCE := {
 core_definition: 0.99,
 gradient_Hessian_relation: 0.99,
 convexity_relation: 0.99,
 Lagrange_KKT_relation: 0.99,
 Newton_gradient_relation: 0.99,
 variational_relation: 0.99,
 semantic_equivalence: 0.97
}

# ---------- RECURSIVE REASONING ----------
RECURSIVE_REASONING(query):
 identify(objective_variables_domain_and_constraints)
 -> compute(first_derivatives_and_gradient)
 -> identify(stationary_or_feasible_candidates)
 -> compute(Hessian_or_second_variation)
 -> classify(local_curvature_and_convexity)
 -> construct(Lagrangian_and_KKT_conditions_if_constrained)
 -> choose(first_order_second_order_projected_barrier_or_variational_method)
 -> select(step_size_globalisation_and_scaling)
 -> iterate_and_monitor(optimality_residuals)
 -> validate(feasibility_constraint_qualification_conditioning_and_solution_scope)
 -> return(semantic_result)

# ---------- AI CONSUMPTION ----------
AI_CONSUMPTION := {
 parse_as: "typed optimisation-calculus semantic graph",
 primary_entity: OPTIMISATION_CALCULUS,
 preserve: [
  objective,
  variables,
  domain,
  constraints,
  gradient,
  Hessian,
  convexity,
  multipliers,
  solver_state
 ],
 infer_through: [
  stationary_points,
  local_extrema,
  global_optima,
  Lagrange_conditions,
  KKT_conditions,
  gradient_methods,
  Newton_methods,
  duality,
  variational_derivatives
 ],
 avoid: [
  declaring_stationary_point_a minimum_without classification,
  assuming_local_minimum_is global_without convexity,
  applying_KKT_without constraint qualification context,
  ignoring_feasibility,
  inverting_indefinite_or_singular_Hessian_without safeguards,
  accepting_solver_termination_without optimality_residual checks
 ]
}

# ---------- UPDATE MODEL ----------
UPDATE_MODEL(new_information):
 validate(new_information)
 -> identify(optimisation_calculus_context)
 -> compare(existing_relations)
 -> preserve(objective_variable_constraint_derivative_and_optimality_invariants)
 -> update(affected_entities)
 -> update(affected_edges)
 -> recompute(CONFIDENCE)
 -> regenerate(FLOW_HASH)

# ---------- FLOW HASH ----------
FLOW_HASH := hash(
 SOURCE_URL
 + ENTITY
 + CONCEPTS
 + OPTIMISATION_CALCULUS
 + OBJECTIVE_FUNCTION
 + GRADIENT
 + HESSIAN
 + STATIONARY_POINT
 + CONVEXITY
 + CONSTRAINT
 + LAGRANGE_MULTIPLIER
 + KKT_CONDITIONS
 + GRADIENT_DESCENT
 + NEWTON_METHOD
 + VARIATIONAL_OPTIMISATION
 + SEMANTIC_EQUIVALENCE
 + CONSTRAINTS
)

# ---------- EXECUTION ----------
INPUT(query)
 -> OPTIMISATION_CALCULUS
 -> PROBLEM_IDENTIFICATION
 -> FIRST_ORDER_ANALYSIS
 -> CANDIDATE_IDENTIFICATION
 -> SECOND_ORDER_CONVEXITY_ANALYSIS
 -> CONSTRAINT_KKT_ANALYSIS
 -> METHOD_SELECTION
 -> STEP_GLOBALISATION_ANALYSIS
 -> ITERATIVE_OPTIMISATION
 -> OPTIMALITY_VALIDATION
 -> RECURSIVE_REASONING(query)
 -> CONFIDENCE
 -> OUTPUT(semantic_result)

END FLOW