\documentstyle{article}
\begin{document}
\input latex_abbr.tex
\section{Optimization of networks}
\subsection{Description of electrical networks}
Consider an electrical network of $N$ nodes $n_1, \ldots 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
\beq
e_{k}= u_p - u_q + v_{k}\quad \mbox {or } e= A u  + B v 
\eeq{1}
 where $u= (u_1, \ldots u_N)$ is the vector of potentials at the
  nodes,
  $v= (v_1, \ldots 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=\pmatrix{0 & \dots & 1&0  & \dots &-1 &0 \cr
\dots &\dots &\dots &\dots &\dots &\dots &\dots &}
$$

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
 \beq
j_{k}= \frac{1}{R_{k}}e_{k}, \quad \mbox {or } j= R^{-1}e
 =R^{-1}(A u + B v )
  \eeq{2}
where $R$ is the $ M\times M$ diagonal matrix of resistivity. Its
 entries represent the resistances in the links, $
 R_k=\frac{1}{\Gs_k}$, where $\Gs_k$ is the conductance of the link.

Finally, the Kirchoff law states that the sum of all current at each
node equals zero, or
 \beq
 A^T j-B^j j_0=0
 \eeq{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 =\pmatrix{ 1/2 \cr1/2 \cr 0 \cr -1 \cr 0}
$$ 
The total current injected in the system must be zero, therefore
the sum of vector entries $B^j j_0$ is zero,
$$
(1, \ldots 1) B^j j_0=0.
$$
Excluding $j$ by means of  \eq{1} and \eq{2} we find the equation  for
 the potentials $u$ in the nodes of the network
 \beq
A^T R^{-1} A u = A^T R^{-1} B v + B^j j_0= b
 \eeq{4}
where $b= A^T R^{-1} B  v +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 \left((A^T R^{-1} A)^{-1}b + Bv \right) $$
In optimization problem, we refer to  equations \eq{1}- \eq{3} or
\eq{4} as ``direct system''.

\subsection{Optimization of resistances}
Consider the problems: Choose the resistors $R_{k}$ in the network
subject to constraints
$$
0 \leq R_{\min}\leq R_{k}\leq R_{\max} \leq \infty
$$
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
 \beq
F= \Gj^T j + \Gu^T u
 \eeq{n1}
  where $\Gj\in R^M$ and  $ \Gu \in R^N$ are given vectors.

Using Lagrange multipliers $\Gl \in R^N$ and $\Gm\in R^M$ 
to account for the equations \eq{2} and \eq{3} of the
network, respectively,  we rewrite the problem as
$$
\min_{R}\min_{ J, u} \max_{\Gl, \Gm}L(R, J, u, \Gl, \Gm)
$$
where
\beq
 L(R, J, u, \Gl, \Gm)=\Gj^T j + \Gu^T u + \Gl^T(A^T j-B^j j_0)+ \Gm^T (j- 
 R^{-1}(A u + B v ).
\eeq{5}
is the extended Lagrangian. 
The stationary of $u$ and $j$ ($\pd{L}{u}=0$ and $\pd{L}{j}=0$) 
 corresponds to the conditions (adjoint
system) for $\Gl$ and $\Gm$:
\beq
\Gu+ A^T R^{-1}\Gm=0, \quad \Gj+ A \Gl+ \Gm=0
\eeq{6}
Excluding $\Gm$ from these conditions, we find
\beq
(A^T R^{-1} A) \Gl= - \Gu+  A^T R^{-1} \Gj
\eeq{7}
This equation shows that $\Gl$ can be interpreted as a potentials in
the nodes of the same network excited by the batteries $- \Gj$ and the
current sources $- \Gu$. Vector $\Gm$ is the corresponding current.
Notice that the sources in the adjoint system correspond to the goal
function \eq{n1} and are independent of real sources.

The stationarity conditions with respect to the design variables --
conductivities $ \Gs_{k}=\frac{1}{R_{k}}$ are easily derived since
$R^{-1}$ is a diagonal matrix. The optimality of an intermediate value
of $\Gs_{k}$ corresponds to the conditions
$$
\pd{}{\Gs_{k}}   \Gm^T  R^{-1}(Au +B v )= -\pd{}{\Gs_{k}}  (\Gj+ A
\Gl)^T  R^{-1}(Au + B v )=0
$$
Since the dependence on  $\Gs_{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 
 $ (\Gj+ A\Gl)_{k}
(Au + B v )_{k}$
of elements
 $ (\Gj+ A\Gl)_{k} $ and  $(Au + B v )_{k}$ which represent the currents
in the direct and adjoint systems through the $k$th link. 
\beq
R_k= \left\{ \begin{array}{ll}  R_{\max} &\If (\Gj+ A\Gl)_{k}
(A u + B v )_{k} >0 \\
  R_{\min} &\If (\Gj+ A\Gl)_{k}
(A u + B v )_{k} <0 \end{array} \right.
\eeq{8}
If these current are codirected, the resistance is
minimal, and if they are opposite directed, the resistance is
maximal.
\paragraph{Minimal networks}
Assume that  $ R_{\max}=\infty$ 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?

\subsection{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 \eq{n1} correspond to the vectors
$$
 \Gr=0, \quad \Gu= B^j j_0
$$
and the adjoint system becomes
$$
(A^T R^{-1} A) \Gl= -\Gu= - B^j j_0.
$$
Its solution is negative to the solution $u$ of the direct system, $
\Gl=-u$.

The optimality conditions \eq{8} 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.
\paragraph{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| \leq |j_2|\leq \ldots \leq |j_M|$$
Then we assign the resistors  $R_{\min}$ to the links with currents 
$ |j_{M-T}|\leq \ldots \leq |j_M|$ and  resistors  $R_{\max}$ to the
rest of links.


\subsection{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
\beq
\Gr ^T  j_0=1 \quad  \mbox {and} ~ \Gy ^T v =1
\eeq{10}
where $\Gr$ and $\Gy$ are given vectors, together with inequalities 
 \beq
  j_0\geq 0 \quad v \geq 0
 \eeq{12}
(these mean that each element of the corresponding vector is
 nonnegative).

 Adding these two constraints
with the Lagrange multipliers $\Ga$ and $\Gb$, respectively, 
to the extended Lagrangian and computing the  stationarity conditions.
The conditions for stationarity of $u$ and $j$ are given by \eq{6}.
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
\beq
\Gl=\Ga (B^j)^T \Gr, \quad R^{-1} \mu =-\Gb(B)^T \Gy
\eeq{11}

Here, we face the problem: the potentials $\Gl$ and the currents $\Gm$
in the adjointed system are
completely defined from the system \eq{6} or  \eq{7}
 and the extra conditions \eq{11}
cannot be satisfied. The only remaining possibility is that the optimal
excitation corresponds to the boundary of the set of currents set by
inequalities \eq{12}. This means that
all independent 
sources $j_0$ but one are zero 
$$
(j_0)_{opt}=( 0, \ldots, 1/\Gr_k, \ldots, 0 )
$$
and similarly,
$$
(v)_{opt}=( 0, \ldots, 1/\psi_k, \ldots, 0 )
$$




\subsection{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. 
\subsection{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 \eq{8} 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.

\end{document}
