1 Optimization of networks

1.1 Description of electrical networks

Consider an electrical network of N nodes n_{1}, … n_{N} and M links that join them together. Each link l_{pq} = l_{k} joints the notes numbered p and q and has the the resistivity R_{pq} = R_{k}. The potential differences v on some nodes are prescribed that is batteries are added to the network at some links. The current sources are added at some nodes as well. The potentials u_{n} and currents j_{k} in the network are found from the following linear system.

The potential difference u_{pq} = u_{k} in each link is

e_{k} = u_{p} − u_{q} + v_{k} or e = Au + Bv  (1)

where u = (u_{1}, … u_{N}) is the vector of potentials at the nodes, v = (v_{1}, … v_{M}) is the vector of added potential differences (batteries), A is the matrix of the structure that shows whether two nodes are connected. It has entries equal to zero, one or negative one, and each row has only two nonzero entries equal to one and to negative one, respectively.

A = ( \begin{matrix}0 & … & 1 & 0 & … & −1 & 0 \\ … & … & … & … & … & … & … \end{matrix} )

Matrix B is the matrix of sources that shows to which link the battaries are attached It structure is similar to the structure of A. One potential is assumed to be zero, u_{1} = 0.

The currents j_{k} in the links are equal to

j_{k} = \frac{1}{R_{k}} e_{k}, or j = R^{−1}e = R^{−1}(Au + Bv)  (2)

where R is the M × M diagonal matrix of resistivity. Its entries represent the resistances in the links, R_{k} = \frac{1}{σ_{k}}, where σ_{k} is the conductance of the link.

Finally, the Kirchoff law states that the sum of all current at each node equals zero, or

A^{T} j − B^{j}j_{0} = 0  (3)

where j_{0} are the added independent external currents and B^{j} is the matrix of current sources that shows where they are attached and how they are distributed. For example, if two equal positive currents are injected in the nodes numbered one and two, and the negative current is injected into note four, the matrix B^{j} is

B^{j} = ( \begin{matrix}1/2 \\ 1/2 \\ 0 \\ −1 \\ 0 \end{matrix} )

The total current injected in the system must be zero, therefore the sum of vector entries B^{j}j_{0} is zero,

(1, … 1)B^{j}j_{0} = 0.

Excluding j by means of (1) and (2) we find the equation for the potentials u in the nodes of the network

A^{T} R^{−1}Au = A^{T} R^{−1}Bv + B^{j}j_{0} = b  (4)

where b = A^{T} R^{−1}Bv + B^{j}j_{0} is the vector or external excitation. that combines both batteries and the current sources.

The potentials u at the nodes are

u = (A^{T} R^{−1}A)^{−1}b

assuming that the matrix A^{T} R^{−1}A is nondegenerative that is that the all nodes are really connected in one system and the potentials can be defined.

The currents j in the links are

j = R^{−1}A ((A^{T} R^{−1}A)^{−1}b + Bv)

In optimization problem, we refer to equations (1)- (3) or (4) as “direct system”.

1.2 Optimization of resistances

Consider the problems: Choose the resistors R_{k} in the network subject to constraints

0 ≤ R_{min} ≤ R_{k} ≤ R_{max} ≤ ∞

to minimize or maximize the potential difference between two nodes, or to minimize or maximize the total current at selected links. The minimizing function for these problems can be represented as

F = τ^{T} j + υ^{T} u  (5)

where τ ∈ R^{M} and υ ∈ R^{N} are given vectors.

Using Lagrange multipliers λ ∈ R^{N} and μ ∈ R^{M} to account for the equations (2) and (3) of the network, respectively, we rewrite the problem as

min_{R} min_{J,u} max_{λ,μ} L(R, J, u, λ, μ)

where

L(R, J, u, λ, μ) = τ^{T} j + υ^{T} u + λ^{T} (A^{T} j − B^{j}j_{0}) + μ^{T} (j − R^{−1}(Au + Bv). (6)

is the extended Lagrangian. The stationary of u and j (\frac{∂L}{∂u} = 0 and \frac{∂L}{∂j} = 0) corresponds to the conditions (adjoint system) for λ and μ:

υ + A^{T} R^{−1}μ = 0, τ + Aλ + μ = 0  (7)

Excluding μ from these conditions, we find

(A^{T} R^{−1}A)λ = −υ + A^{T} R^{−1}τ  (8)

This equation shows that λ can be interpreted as a potentials in the nodes of the same network excited by the batteries −τ and the current sources −υ. Vector μ is the corresponding current. Notice that the sources in the adjoint system correspond to the goal function (5) and are independent of real sources.

The stationarity conditions with respect to the design variables – conductivities σ_{k} = \frac{1}{R_{k}} are easily derived since R^{−1} is a diagonal matrix. The optimality of an intermediate value of σ_{k} corresponds to the conditions

\frac{∂}{∂σ_{k}} μ^{T} R^{−1}(Au + Bv) = −\frac{∂}{∂σ_{k}} (τ + Aλ)^{T} R^{−1}(Au + Bv) = 0

Since the dependence on σ_{k} is linear, this conditions cannot be satisfied unless the potential difference in the corresponding link l_{k} in either the direct or adjoint problem is zero. The last condition would mean that the function F is invariant to this resistance. We conclude that the resistance take only the limiting values R_{min} or R_{max}. The choice depends only on the sign of the product (τ + Aλ)_{k}(Au + Bv)_{k} of elements (τ + Aλ)_{k} and (Au + Bv)_{k} which represent the currents in the direct and adjoint systems through the kth link.

R_{k} = \{ \begin{matrix}R_{max} & if (τ + Aλ)_{k}(Au + Bv)_{k} > 0 \\ R_{min} & if (τ + Aλ)_{k}(Au + Bv)_{k} < 0 \end{matrix}  (9)

If these current are codirected, the resistance is minimal, and if they are opposite directed, the resistance is maximal.

Minimal networks Assume that R_{max} = ∞ or that we can remove a link from the system. Then the optimal network consists of only links in which the currents are codirected. How many links survive?

1.3 Energy minimization

The special case is minimization or maximization of the total energy of the network or its total resistance. Assume for clearness that there is no battaries v = 0 and the equation for the network is

(A^{T} R^{−1}A)u = B^{j}j_{0}

and minimize the work of external currents

F = u^{T} B^{j}j_{0}

equal to the energy of the network. The corresponding objective function (5) correspond to the vectors

ρ = 0, υ = B^{j}j_{0}

and the adjoint system becomes

(A^{T} R^{−1}A)λ = −υ = −B^{j}j_{0}.

Its solution is negative to the solution u of the direct system, λ = −u.

The optimality conditions (9) for the resistances show that R_{k} = R_{min} for all k which is physically evident: To minimize the total resistivity, use the smaller resistances everywhere.

Additional constraints on the resistors To make the problem nontrivial, let us add an additional constraint: Assume that the number of each type of resistors is prescribed: There are T resistors with resistivity R_{min} and the rest have the resistivity R_{max}. The stationarity conditions are correspondingly changed: In this case, the smaller current is put through the larger resister and larger current – through smaller resistance. To find the layout of the resistors, we need to range the currents and renumber them

|j_{1}| ≤ |j_{2}| ≤ … ≤ |j_{M}|

Then we assign the resistors R_{min} to the links with currents |j_{M−T} | ≤ … ≤ |j_{M}| and resistors R_{max} to the rest of links.

1.4 Optimization of sources

The sources j_{0} and v can be optimized as well. Assume that these vectors are free but two linear constraints are prescribed

ρ^{T} j_{0} = 1 and ψ^{T} v = 1  (10)

where ρ and ψ are given vectors, together with inequalities

j_{0} ≥ 0 v ≥ 0  (11)

(these mean that each element of the corresponding vector is nonnegative).

Adding these two constraints with the Lagrange multipliers α and β, respectively, to the extended Lagrangian and computing the stationarity conditions. The conditions for stationarity of u and j are given by (7). Stationarity with respect to j_{0} and v we obtain conditions for the potential and currents in the adjoined system at the points of excitation

λ = α(B^{j})^{T} ρ, R^{−1}μ = −β(B)^{T} ψ  (12)

Here, we face the problem: the potentials λ and the currents μ in the adjointed system are completely defined from the system (7) or (8) and the extra conditions (12) cannot be satisfied. The only remaining possibility is that the optimal excitation corresponds to the boundary of the set of currents set by inequalities (11). This means that all independent sources j_{0} but one are zero

(j_{0})_{opt} = (0, …, 1/ρ_{k}, …, 0)

and similarly,

(v)_{opt} = (0, …, 1/ψ_{k}, …, 0)

1.5 Optimization of sources and resistances

When the resistances are optimized along with the sources, the rule for optimal resistances must be added to the equations, this rule determines the matrix R. Here me may expect that the resistivity layout is chosen to equalize the impact of several different current sources.

1.6 Numerical solution

The optimization problems are solved using iterative scheme. Consider optimization of the resistances. Assigning the design parameters R_{k}, one solves the direct and adjoint problem and checks the optimality conditions (9) for R_{k}. If some of them are not satisfied, the design changes; then the iteration repeats until all conditions are satisfied. Similar scheme is used for optimization of sources.