Options

Configuration options for the algorithm.

Fields:

• tolerance::Float64: Convergence tolerance for primal and dual errors (default: 1e-4).
• max_iterations::Int64: Maximum number of iterations to run (default: 1000).
• mu::Float64: Penalty parameter for the augmented Lagrangian (default: 1.0).
• overlap_distance::Int64: Distance for overlap in subproblem expansion (default: 1).
• use_node_objectives::Bool: Whether to use node-specific objectives instead of a global graph objective (default: true).
• subproblem_optimizer: The optimizer to use for solving subproblems (default: nothing).

SchwarzAlgorithm{GT<:Plasmo.AbstractOptiGraph}

Represents a Schwarz-based optimization algorithm applied to a partitioned graph.

Fields:

• graph::GT: The global optimization graph passed to the algorithm.
• subproblems::Vector{GT}: A list of subgraphs representing the (expanded) subproblems.
• element_subproblem_map::Dict{Plasmo.OptiElement,GT}: Maps elements in the graph to their associated subproblems.
• objective_func::Plasmo.AbstractJuMPScalar: The global objective function for the graph.
• options::Options: Configuration options for the algorithm.
• initialized::Bool: Whether the algorithm has been initialized.
• status::MOI.TerminationStatusCode: The current status of the algorithm.
• err_pr::Union{Nothing,Float64}: Current primal error.
• err_du::Union{Nothing,Float64}: Current dual error.
• objective_value::Union{Nothing,Float64}: Current objective value.
• iteration::Int64: Current iteration count.
• primal_error_iters::Vector{Float64}: History of primal errors per iteration.
• dual_error_iters::Vector{Float64}: History of dual errors per iteration.
• objective_iters::Vector{Float64}: History of objective values per iteration.
• solve_time::Float64: Total solve time.
• timers::Timers: Timers to measure performance metrics.

SchwarzAlgorithm(graph::OptiGraph, expanded_subgraphs::Vector{OptiGraph}; kwargs...)

Create an algorithm instance by providing the subproblems directly.

SchwarzAlgorithm(graph::OptiGraph, partition::Plasmo.Partition; kwargs...)

Create an algorithm instance by providing a valid Plasmo.Partition.

SchwarzAlgorithm(graph::OptiGraph, partition::Plasmo.Partition; kwargs...)

Create an algorithm instance and use Metis internally to create partitions.

SubProblemData{GT<:Plasmo.AbstractOptiGraph}

Holds data specific to a subproblem in the optimization graph.

Fields:

• restricted_subgraph::GT: The subgraph representing the "restricted" subproblem. This is the subproblem before adding overlap.
• incident_variable_map::OrderedDict{NodeVariableRef,GT}: Maps incident variables to their owning subgraphs.
• incident_constraint_map::OrderedDict{EdgeConstraintRef,GT}: Maps incident constraints to their owning subgraphs.
• primal_values::OrderedDict{NodeVariableRef,Float64}: Stores the current primal variable values.
• dual_values::OrderedDict{EdgeConstraintRef,Float64}: Stores the current dual variable values.
• primal_parameters::OrderedDict{NodeVariableRef,NodeVariableRef}: Maps primal variables to their parameter values.
• dual_parameters::OrderedDict{EdgeConstraintRef,NodeVariableRef}: Maps dual variables to their parameter values.
• node_objectives::OrderedDict{OptiNode,Plasmo.AbstractJuMPScalar}: Objective functions associated with nodes in the subproblem.
• objective_function::Union{Nothing,Plasmo.AbstractJuMPScalar}: The total objective function for the subproblem, including penalties.
• last_termination_status::MOI.TerminationStatusCode: The termination status from the last solve.

Timers

Simple data structure to track the timing of various stages of the SchwarzAlgorithm.

Fields:

• start_time::Float64: Time when the algorithm starts.
• initialize_time::Float64: Time taken to initialize the algorithm.
• eval_objective_time::Float64: Time taken to evaluate the objective function.
• eval_primal_feasibility_time::Float64: Time taken to evaluate primal feasibility.
• eval_dual_feasibility_time::Float64: Time taken to evaluate dual feasibility.
• communicate_time::Float64: Time spent in inter-subproblem communication.
• update_subproblem_time::Float64: Time taken to update subproblems.
• solve_subproblem_time::Float64: Time taken to solve subproblems.
• total_time::Float64: Total time for the entire process.

_check_tolerance(algorithm::SchwarzAlgorithm) -> Bool

Check if the primal or dual residuals exceed the specified tolerance. This determines whether the algorithm should continue iterating.

_extract_constraints(subgraph_boundary_edges::Vector{Vector{OptiEdge}}) -> Vector{Vector{ConstraintRef}}

Retrieve the constraints associated with boundary edges for a set of subgraphs. For each subgraph, the constraints tied to its boundary edges are collected.

Args:

• subgraph_boundary_edges::Vector{Vector{OptiEdge}}: A vector of vectors, where each inner vector contains the boundary edges of a specific subgraph.

Returns: A vector of vectors, where each inner vector contains the constraints associated with the boundary edges of a specific subgraph.

_extract_node_objectives(algorithm::SchwarzAlgorithm)

Extracts separable objective terms from the global graph and assigns them to the nodes of each subproblem's restricted subgraph.

_find_boundary_edges(graph::OptiGraph, subgraphs::Vector{OptiGraph}) -> Vector{Vector{OptiEdge}}

Identify the boundary edges for a set of subgraphs within a given hypergraph. Boundary edges are those incident to nodes at the interface between the subgraphs and the rest of the graph.

Args:

• graph::OptiGraph: The main graph containing the subgraphs and edges.
• subgraphs::Vector{OptiGraph}: A vector of subgraphs for which boundary edges need to be identified.

Returns: A vector of vectors, where each inner vector contains the boundary edges associated with a specific subgraph.

_formulate_objective_penalty(expanded_subgraph::OptiGraph, mu::Float64)

Adds dual penalties and an augmented Lagrangian penalty term to the objective of the given subproblem.

Args:

• expanded_subgraph: The subproblem graph with overlap regions.
• mu: The penalty parameter for the augmented Lagrangian method.

_get_subproblem(algorithm::SchwarzAlgorithm, element::Plasmo.OptiElement) -> GT

Retrieves the subproblem associated with a given element in the optimization graph.

_initialize_subproblem_objectives(algorithm::SchwarzAlgorithm)

Initializes the objective functions for each subproblem in the algorithm.

This function either sets node objectives directly, if specified, or extracts and assigns the graph's separable objective terms to the subproblems.

Additionally, augmented Lagrangian penalty terms are added to the objectives.

_is_hierarchical(graph::OptiGraph)

Check whether the given graph is hierarchical (i.e. contains nodes and subgraphs.)

_retrieve_neighbor_values(subproblem_graph::OptiGraph)

Fetches primal and dual values from neighboring subproblems linked via incident variables and constraints.

_solve_subproblem(subproblem_graph::OptiGraph)

Solves an individual subproblem and logs its termination status.

_update_objective_penalty(expanded_subgraph::OptiGraph)

Updates the terms in the subproblem's objective based on the current primal and dual values.

_update_suproblem(subproblem_graph::OptiGraph)

Updates the objective penalty terms of the given subproblem based on the current neighbor values.

calculate_dual_feasibility(algorithm::SchwarzAlgorithm) -> Vector{Float64}

Evaluate the dual feasibility of the linking constraints defined over the algorithm's graph. For each linking constraint, the function calculates the difference between the maximum and minimum dual values across subproblems.

Args:

• algorithm::SchwarzAlgorithm: The algorithm object containing the graph and linking constraints.

Returns: A vector of dual residuals for the linking constraints.

calculate_objective_value(algorithm::SchwarzAlgorithm) -> Float64

Evaluate the objective value defined over the algorithm's graph. The function uses the current variable values from the subproblems to compute the overall objective.

Args:

• algorithm::SchwarzAlgorithm: The algorithm object containing the objective function and subproblem mappings.

Returns: The evaluated objective value as a Float64.

calculate_primal_feasibility(algorithm::SchwarzAlgorithm) -> Vector{Float64}

Evaluate the primal feasibility of the linking constraints defined over the algorithm's graph. This is done by checking the residuals between the linking constraints and their expected values based on the subproblem solutions.

Args:

• algorithm::SchwarzAlgorithm: The algorithm object containing the graph and linking constraints.

Returns: A vector of primal residuals for the linking constraints.

check_valid_problem(algorithm::SchwarzAlgorithm) -> Bool

Validates the setup of an optimization problem for the specified algorithm. This function performs the following checks:

1. Ensures a subproblem optimizer is defined in the algorithm options.
2. Validates the consistency of subproblem graphs with their respective restricted subgraphs.
3. Confirms that the objective function is separable. Non-separable objectives are currently unsupported.
4. Verifies that the optimization graph does not exhibit a hierarchical structure, which is unsupported.

If some of these checks fail, the algorithm's status is set to MOI.INVALID_MODEL, and an appropriate error is thrown.

Notes:

• Additional validations planned for future implementations:
  • Checking for non-contiguous partitions.
  • Ensuring there is sufficient overlap (at least 1) in expanded graphs.

do_iteration(algorithm::SchwarzAlgorithm)

Performs a single iteration of the algorithm. This involves:

1. Solving each subproblem.
2. Communicating primal and dual values between subproblems.
3. Updating subproblem objectives, penalties, and neighbor values.

eval_iteration(algorithm::SchwarzAlgorithm; save_iteration::Bool=true)

Evaluate the current iterate of the algorithm by calculating primal and dual feasibility, as well as the objective value. Optionally, the iterate values can be stored internally for tracking progress.

Args:

• algorithm::SchwarzAlgorithm: The algorithm object representing the current optimization state.
• save_iteration::Bool: Whether to save the iterate values. Default is true.

Returns: Nothing. Updates the algorithm state with current feasibility and objective values.

initialize!(algorithm::SchwarzAlgorithm)

Initializes the algorithm by validating the input problem and setting up subproblems. This includes:

• Validating the global graph and subproblem consistency.
• Assigning incident constraints and variables.
• Setting up objective penalties for the subproblems.

Throws:

• ArgumentError if the algorithm fails to initialize.

reset_iterations(algorithm::SchwarzAlgorithm)

Resets the algorithm's iteration counters and initializes the timers. Also sets up optimizers for each subproblem.

run_algorithm!(algorithm::SchwarzAlgorithm)

Execute the optimization algorithm, iteratively solving subproblems and updating the solution until convergence or a stopping criterion is met.