Reference

Contents

Index

NonSmoothDynamics.boyle_dykstra!Method
boyle_dykstra!(sol::Vector{Float64}, x0::Vector{Float64}, projections::Vector{Function}; tol::Float64=1e-6, max_iter::Int=1000)

Implements the Boyle-Dykstra algorithm to project a point onto the intersection of multiple convex sets.

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x0::Vector{Float64}: The initial point to be projected.
  • projections::Vector{Function}: A vector of projection functions, where each function computes the projection onto a specific convex set.
  • tol::Float64=1e-6: Convergence tolerance. The algorithm stops if the change in x between iterations is less than this value.
  • max_iter::Int=1000: Maximum number of iterations to run the algorithm.

Returns

  • x::Vector{Float64}: The projection of x0 onto the intersection of the convex sets.
  • num_iter::Int: The number of iterations performed.
  • converged::Bool: Whether the algorithm converged within the maximum number of iterations.

Example

# Define projection functions
project_C1(sol, x) = sol .= clamp.(x, 0.0, 1.0)    # Projection onto the box [0, 1]^n
project_C2(sol, x) = sol .= x ./ sum(x)            # Projection onto the simplex

# Initial point
x0 = [1.5, 2.0, -0.5]

# Run the Boyle-Dykstra algorithm
x, num_iter, converged = boyle_dykstra(x0, [project_C1, project_C2])

println("Projection: ", x)
println("Converged: ", converged, " in ", num_iter, " iterations.")
source
NonSmoothDynamics.numerical_projection!Method
numerical_projection!(sol::Vector{Float64},
                      x::Vector{Float64}, Px::AbstractMatrix,
                      Aeq::AbstractMatrix, beq::AbstractVector,
                      Ain::AbstractMatrix, bin::AbstractVector,
                      l::Vector{Float64}, u::Vector{Float64}) -> Vector{Float64}

Computes the numerical projection of a vector x onto a constrained set defined by equality and inequality constraints, as well as variable bounds.

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x::AbstractVector: The input vector to be projected.
  • Px::AbstractMatrix: Projection matrix.
  • Aeq::AbstractMatrix: Coefficient matrix for equality constraints Aeq x = beq.
  • beq::AbstractVector: Right-hand side of the equality constraints.
  • Ain::AbstractMatrix: Coefficient matrix for inequality constraints Ain x ≤ bin.
  • bin::AbstractVector: Right-hand side of the inequality constraints.
  • l::AbstractVector: Lower bounds for the variables.
  • u::AbstractVector: Upper bounds for the variables.

Returns

  • AbstractVector: The projection of x that satisfies the constraints.

Example

# Example data
x   = [0.5, -1.0]
Px  = I
Aeq = [1.0 1.0]          # Equality constraint: x₁ + x₂ = 1
beq = [1.0]
Ain = [1.0 0.0; 0.0 1.0] # Inequality constraints: x₁ ≤ 0.8, x₂ ≤ 0.6
bin = [0.8, 0.6]
l = [-Inf, -Inf]         # No lower bounds
u = [Inf, Inf]           # No upper bounds

# Compute the projection
proj_x = numerical_projection(x, Px, Aeq, beq, Ain, bin, l, u)
println("Projected x: ", proj_x)
source
NonSmoothDynamics.project_ball!Method
project_ball!(sol::Vector{Float64}, x::Vector{Float64}, c::Vector{Float64}, r::Float64) -> Vector{Float64}

Projects a vector x onto the ball centered at c with radius r.

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x::Vector{Float64}: The vector to project.
  • c::Vector{Float64}: The center of the ball.
  • r::Float64: The radius of the ball.

Returns

true if the projection is successful.

source
NonSmoothDynamics.project_box!Method
project_box!(sol::Vector{Float64}, x::Vector{Float64}, l::Vector{Float64}, u::Vector{Float64}) -> Vector{Float64}

Projects a vector x onto the box defined by lower bounds l and upper bounds u.

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x::Vector{Float64}: The vector to project.
  • l::Vector{Float64}: The lower bounds of the box.
  • u::Vector{Float64}: The upper bounds of the box.

Returns

true if the projection is successful.

source
NonSmoothDynamics.project_halfspace!Method
project_halfspace!(sol::Vector{Float64}, x::Vector{Float64}, a::Vector{Float64}, b::Float64) -> Vector{Float64}

Projects a vector x onto the half-space defined by a^T * x <= b.

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x::Vector{Float64}: The vector to project.
  • a::Vector{Float64}: The normal vector defining the half-space.
  • b::Float64: The offset of the half-space.

Returns

true if the projection is successful.

source
NonSmoothDynamics.project_hyperplane!Method
project_hyperplane!(sol::Vector{Float64}, x::Vector{Float64}, a::Vector{Float64}, b::Float64) -> Vector{Float64}

Projects a vector x onto the hyperplane defined by a^T * x = b.

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x::Vector{Float64}: The vector to project.
  • a::Vector{Float64}: The normal vector defining the hyperplane.
  • b::Float64: The offset of the hyperplane.

Returns

true if the projection is successful.

source
NonSmoothDynamics.project_l2_ball!Method
project_l2_ball!(sol::Vector{Float64}, x::Vector{Float64}, r::Float64) -> Vector{Float64}

Projects a vector x onto the L2 norm ball of radius r.

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x::Vector{Float64}: The vector to project.
  • r::Float64: The radius of the L2 norm ball.

Returns

true if the projection is successful.

source
NonSmoothDynamics.project_positive_orthant!Method
project_positive_orthant!(sol::Vector{Float64}, x::Vector{Float64}) -> Vector{Float64}

Projects a vector x onto the positive orthant (all elements >= 0).

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x::Vector{Float64}: The vector to project.

Returns

true if the projection is successful.

source
NonSmoothDynamics.project_simplex!Method
project_simplex!(sol::Vector{Float64}, x::Vector{Float64}) -> Vector{Float64}

Projects a vector x onto the probability simplex, defined as: {y ∈ R^n : yi ≥ 0, ∑ yi = 1}

This implementation avoids sorting by iteratively adjusting the elements of x to meet the simplex constraints.

Arguments

  • sol::Vector{Float64}: The solution vector to be updated.
  • x::Vector{Float64}: The input vector to be projected.

Returns

true if the projection is successful.

source
NonSmoothDynamics.projected_dynamical_system!Method
projected_dynamical_system!(vals::InterpolationStruct,
                            x0::Vector{Float64}, F::Function, project_fun!::Function;
                            kwargs...)
projected_dynamical_system(x0::Vector{Float64}, F::Function, project_fun!::Function,
                           args...; kwargs...)

The args... are passed to InterpolationStruct constructor.

Simulates the discretized dynamics of a Projected Dynamical System (PDS): x(t+1) = P_{C}(x(t) - h * F(x(t)))

Arguments

  • vals::InterpolationStruct: Interpolation struct containing the time and state values.
  • x0::Vector{Float64}: Initial state (starting point within the set C).
  • F::Function: The vector field defining the dynamics (e.g., gradient, payoff vector, etc.).
  • project_fun!::Function: A function to compute the projection onto the feasible set C.
  • verbose::Int=0: Verbosity level.
  • proj_verbose::Int=0: Verbosity level for the projection step.
  • project_x0::Bool = true:
  • atol::Float64=1e-6: Convergence tolerance. The algorithm stops if the norm of the change is less than this value.
  • rtol::Float64=1e-6: Convergence tolerance.
  • stop_first_stable::Bool=true: Stop the simulation if the first stable point is found.

Returns

  • stats::Bool: Whether the system computation was successful.

vals.x_vals::Matrix{Float64}: Matrix where each column is the state of the system at a time step.

Example

# Define the vector field F(x) = x - 1 (gradient of f(x) = 0.5 * ||x - 1||^2)
F(x) = x - 1.0

# Define projection onto the box [0, 1]^2
project_fun!(x) = clamp.(x, 0.0, 1.0)

# Initial point
x0 = [2.0, -1.0]

# Simulate the PDS
x_vals, t_vals, converged = projected_dynamical_system(x0, F, project_fun!)
source