PaperlayerView exact revision on arXiv

Source-linked AI summary

A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem via Output Feedback

Luca Claude Gino Lebon, Jorke de Vlas, Johannes K. Fichte, Claudio Altafini

arXiv:2610.22735v1eess.SYcs.SYmath.OC

TL;DR

The paper addresses the lack of an efficient algorithm for finding minimal input and measurement node sets that achieve disturbance decoupling via output feedback. It encodes the node constraints in a modified min-cut/max-flow problem and proves that the method returns an optimal solution in polynomial time.

  • Problem

    An efficient algorithm for computing the minimal input and output node sets for DDPOF had remained unavailable.

    Source: §I · p. 1, §IV · p. 3

  • Method

    The algorithm encodes the optimality constraints in an extended network and uses a modified min-cut/max-flow procedure to find the minimal-cardinality input and output node sets.

    Source: §I · p. 1, A. Min-cut/max-flow algorithm revisited · p. 4

  • Results

    The algorithm returns an optimal solution in polynomial time.

    Source: §I · p. 1, B. Optimality · p. 5

  • Takeaways & Limitations

    The computed sets provide the minimal number of control input and measurement output nodes required to achieve disturbance decoupling.

    Source: §III · p. 3, §VI · p. 6

Abstract

from arXiv · show

In this paper, we propose an algorithm that solves, in polynomial-time, the minimal input/output node cardinality disturbance decoupling problem via output feedback. The optimal solution, intended as a minimal-cardinality pair of sets of control inputs and measurement output nodes needed to achieve the decoupling, is computed by solving a modified min-cut/max-flow problem.

I. INTRODUCTION

The introduction frames DDPOF for networked systems as isolating designated targets from disturbances, then identifies the missing efficient algorithm for minimizing the required input and output nodes. The background establishes graph and node-set concepts used to express the problem.

I. INTRODUCTION

  • For networked systems, DDPOF isolates designated target nodes from disturbances acting on a subset of nodes.When the full state is unavailable, output feedback takes the form u = −Gy, with y = Cx.Source: §I · p. 1
  • In the node-based formulation, control and measurement nodes containing the out- and in-boundaries of W make W controlled and conditioned invariant; solvability follows when W contains disturbance nodes and avoids targets.Prior work [10] formulated the minimal input/output node-cardinality problem and characterized optimal solutions [10]; the framework was also applied to power networks [11].Source: §I · p. 1
  • The paper fills the stated gap by encoding optimality constraints in an extended network and applying a modified min-cut/max-flow algorithm that returns an optimal solution in polynomial time.A MATLAB implementation is available.Source: §I · p. 1

II. BACKGROUND MATERIAL

  • A directed graph represents nodes and edges, and a directed path is a sequence of distinct nodes joined by directed edges.The path length is its number of edges.Source: §II · p. 1
  • A terminal node subset has no outgoing edge to nodes outside the subset.Source: §II · p. 1
  • A node set is associated with the span of the elementary vectors for its nodes, and the paper identifies node-set union with the sum of these subspaces.The notation Z⊥ denotes both the complement node set and the orthogonal subspace.Source: §II · p. 2
  • The in-boundary of W contains nodes in W with edges leaving W, while its out-boundary contains nodes outside W reached by edges from W.The boundaries correspond under complementation and edge reversal.Source: §II · p. 2

A. Linear systems over networks

The network model assigns a state variable to each graph node and represents selected nodes as control inputs and measured outputs.

A. Linear systems over networks

  • Selected input nodes B define the input matrix through their elementary columns, while selected output nodes C define the output matrix through their elementary rows.The resulting linear time-invariant system uses the graph adjacency matrix as its state update matrix.Source: A. Linear systems over networks · p. 2
  • The node-based input and output selections connect the graph representation to a linear time-invariant control system.Source: A. Linear systems over networks · p. 2
  • Each graph node vi is associated with a state variable xi in the state vector x.Source: A. Linear systems over networks · p. 2

B. Invariance, controlled invariance and conditioned invariance for node sets

The section defines invariant node sets through graph structure and gives equivalent conditions for invariance, controlled invariance, and conditioned invariance. It also characterizes when a set satisfies both controlled and conditioned invariance.

B. Invariance, controlled invariance and conditioned invariance for node sets

  • A-invariance means the adjacency action maps a node set into itself, equivalently the set is terminal in the graph.Source: B. Invariance, controlled invariance… · p. 2
  • Controlled invariance permits adjacency effects outside the set to be accounted for by the input nodes; its equivalent graph condition allows edges from the set only to the set or B.The definition is AZ ⊆ Z + B.Source: B. Invariance, controlled invariance… · p. 2
  • Conditioned invariance requires that adjacency effects from nodes outside the measured set C remain in S; its graph condition preserves successors of unmeasured nodes in S.The paper also gives an equivalent matrix characterization using a friend of S.Source: B. Invariance, controlled invariance… · p. 2
  • A set is both controlled and conditioned invariant exactly when it is A-invariant or every exiting edge runs from a measured node in C to an input node in B.If the set is not A-invariant, the proof treats its exiting edges as C × B.Source: B. Invariance, controlled invariance… · p. 2

C. Standard disturbance decoupling problem via output feedback over networks

The standard network DDPOF setup adds disturbance and target node sets to the system. The problem is to choose output feedback that prevents disturbances at D from affecting targets at T.

C. Standard disturbance decoupling problem via output feedback over networks

III. MINIMAL INPUT/OUTPUT CARDINALITY DDPOF

The section formulates the minimal input/output-node-cardinality DDPOF problem and gives solvability conditions for disturbance and target node sets. It seeks the smallest pair of control-input and measurement-output node sets that achieves decoupling.

III. MINIMAL INPUT/OUTPUT CARDINALITY DDPOF

  • Under Assumption 1, the disturbance and target node sets are disjoint.Source: §III · p. 3
  • For system (2), the DDPOF is solvable iff an (A, B)- and (C, A)-invariant subspace contains ImD and is contained in ker T [7, Thm. 3.2].Source: §III · p. 3
  • In the node-based criterion of [10], each D-to-T path must contain an adjacent pair with its C node before its B node.The theorem states equivalent solvability conditions under Assumption 1.Source: §III · p. 3
  • Problem 2 asks for minimum-cardinality input-node set B and output-node set C that solve the DDPOF.The selected nodes correspond in practice to elementary-column matrices B and Cᵀ.Source: §III · p. 3

A. Solution to the minimal input/output cardinality DDPOF

The section characterizes feasible and optimal input/output node sets through invariant node sets and their boundaries. It also states that these boundary sets determine the unique feedback friend for the DDPOF.

A. Solution to the minimal input/output cardinality DDPOF

  • The optimal solutions characterized in [10] use minimal-cardinality boundary node sets for W, with P the union of all D-to-T paths.Source: A. Solution to the minimal… · p. 3
  • For Problem 2, feasible B and C contain W’s out- and in-boundaries, respectively; when optimal, they equal those boundaries, and optimality is equivalent to being minimal-cardinality node sets with these equalities.Source: A. Solution to the minimal… · p. 3
  • Given an invariant node set W, choosing C = ∂−(W, A) and B = ∂+(W, A) yields its unique friend solving the DDPOF [10, Thm. 11].Source: A. Solution to the minimal… · p. 3

IV. SOLVING THE MINIMAL INPUT/OUTPUT CARDINALITY DDPOF

The section identifies the missing efficient algorithm for computing the optimal input/output node sets. It establishes that an optimal pair has disjoint input and output sets.

IV. SOLVING THE MINIMAL INPUT/OUTPUT CARDINALITY DDPOF

  • The paper identifies an efficient algorithm for computing the optimal {B, C} as the missing step following [10]’s characterization.Source: §IV · p. 3
  • For an optimal solution, B ∩ C = ∅, so |B| + |C| = |B ∪ C|.Source: §IV · p. 3
  • If an input and output node overlapped, a D-to-T path would have two qualifying adjacent subpaths, contradicting minimality.Source: §IV · p. 4

A. Min-cut/max-flow algorithm revisited

The algorithm converts the node-cut problem into a weighted edge-cut problem on an extended network, then applies min-cut/max-flow. Its cut value equals the total number of selected input and output nodes, and the algorithms converge to an optimum under Assumption 1.

A. Min-cut/max-flow algorithm revisited

  • The solution pair {B, C} is a minimum-cardinality node cut separating D from T, and the corresponding special min-cut/max-flow problem is solvable in polynomial time.Source: A. Min-cut/max-flow algorithm revisited · p. 4
  • Under Assumption 1, the algorithms converge in finite time to an optimal solution because the network has finitely many nodes and edges.Source: A. Min-cut/max-flow algorithm revisited · p. 4
  • The extended network adds two nodes per original node, unit-weight selection edges, and infinite-weight copies of each original edge.It also adds source and sink nodes linked to the disturbance and target nodes; the extended network has 3n + 2 nodes.Source: A. Min-cut/max-flow algorithm revisited · p. 4
  • The extended-network min-cut value equals |B| + |C|, the total cardinality of the selected input and output node sets.The cut edges map to node choices in the original network.Source: A. Min-cut/max-flow algorithm revisited · p. 5

B. Optimality

Under Assumption 1, Algorithms 1–3 produce an optimal solution to Problem 2. The proof maps input and output node choices to a cut in the extended network and uses minimum-cut cardinality to establish optimality.

B. Optimality

  • Under Assumption 1, the solution computed by Algorithms 1–3 is optimal for Problem 2.The proof establishes feasibility and minimal cardinality through the corresponding cut in the extended network.Source: B. Optimality · p. 5
  • Only edges of the form (vi, vi+n) and (vi+2n, vi) can be cut; these encode output nodes C and input nodes B, respectively.The resulting cut set H corresponds to the selected input and output nodes.Source: B. Optimality · p. 5
  • A minimum cut must yield a feasible pair {B, C}, because any uncovered D-to-T path would mean the proposed edges do not form a cut.The proof examines paths in the extended network to rule out cut configurations that fail the feasibility conditions.Source: B. Optimality · p. 5
  • The minimum cut’s cardinality establishes minimum node cardinality: a smaller feasible pair would induce a smaller cut, contradicting min-cut optimality.The proof links the cardinalities of the edge cuts induced by candidate node pairs to their node-set cardinalities.Source: B. Optimality · pp. 5–6
  • The optimal pair {B, C} need not be unique; distinguishing equal-cardinality optima requires a secondary objective.Residual graph analysis or Gomory–Hu trees are mentioned as ways to enumerate equal-cardinality cuts.Source: B. Optimality · p. 6
  • An optimal node pair does not necessarily correspond to a minimum edge cut; setting all edge weights to 1 and running standard min-cut computes one.A secondary objective can minimize the number of edges cut when multiple node-pair optima exist.Source: B. Optimality · p. 6

V. NUMERICAL EXAMPLE

The numerical example applies Algorithms 1–3 to a 10-node network with disturbance nodes v1–v3 and target nodes v8–v10. The reported solution selects inputs v6 and v7 and outputs v4 and v5.

V. NUMERICAL EXAMPLE

  • The example uses disturbance nodes D = {v1, v2, v3} and target nodes T = {v8, v9, v10} in a network of 10 nodes.Algorithm 2 constructs the extended network used to find the solution.Source: §V · p. 6
  • The minimal-cardinality solution of Problem 2 is B = {v6, v7} and C = {v4, v5}, as depicted in Fig. 3.The minimal cut set of edges in the extended network G is H = {(v26, v6), (v27, v7), (v4, v14), (v5, v15)}.Source: §V · p. 6
  • A classical edge min-cut from D to T instead yields either B = {v4, v5}, C = D or B = T, C = {v6, v7}, both suboptimal under |B| + |C|.The comparison illustrates why the example uses the modified approach to optimize input/output node cardinality.Source: §V · p. 6

VI. CONCLUSIONS

The paper develops a polynomial-time algorithm for finding minimal-cardinality control-input and measurement-output node sets for disturbance rejection. MATLAB functions implementing the results are available in a GitLab repository.

VI. CONCLUSIONS

  • The algorithm determines in polynomial time the minimal-cardinality control-input and measurement-output node sets required to reject disturbances.The paper notes that MATLAB functions implementing its results are available in a GitLab repository.Source: §VI · p. 6
Loading 2610.22735v1…