problem description
solution
A multilinear function f\left ( x_{1},\cdots ,x_{n}\right ) is one which is linear with respect to each of its independent variables taken one at a time. In other words, when fixing all the independent variables except for one, then it reduces to a linear function in the one variable which is free to change. For an example, for n=2, \boxed{ f\left ( x,y\right ) =ax+by+cxy }
Where all the constants a,b,c,x_{0} have been combined into A and B. Similarly when fixing y=y_{0}, then \left . f\left ( x,y\right ) \right \vert _{y=y_{0}}=Cx+D
To illustrate what was said so far, taking n=2 and fixing x=x_{0}, then the function will be \left . f\left ( x,y\right ) \right \vert _{x=x_{0}} and when fixing y=y_{0} the function will be \left . f\left ( x,y\right ) \right \vert _{y=y_{0}}
To show that the extreme points must be at a ”corner” or a vertex, is now straight forward. From the above, the extreme value of the multilinear function must be on an edge. But on any edge, only one of the coordinates is free to change while all the others are fixed. Therefore on any edge of the hypercube (when in higher dimensions) the multilinear function is linear in only one of the parameters at an edge. Hence the function must be either increasing or decreasing on that edge (or be constant). Therefore the function extreme values on the edge is where the edge starts or ends, which is a vertex node. This is illustrated by this diagram for the \Re ^{2}case.
The following illustrates the case for \Re ^{3} by showing few edges and (the function value f\left ( x,y,z\right ) is hard to show here, since we would need fourth dimension).
This process carry over to higher dimensions hypercube.
solution
The function J\left ( u\right ) is defined on a cube. Since it is multilinear in u_{1},u_{2},u_{3}, the minimizer point must be at one of the 8 vertices of the cube as shown in problem one. The optimization method the problem asks to perform does not converge to a minimizer u^{\ast } in general. And it does not in this problem. The value of J at each corner are1 as shown below
In the first stage, we select between J_{1} and J_{2}, (this is the result of fixing u_{2}=u_{3}=1 and optimizing J\left ( u\right ) to find \hat{u}_{1}). We find that J_{2} wins, since it is smaller. Then we select between J_{2} and J_{7} and find that J_{2} still wins. Then we select between J_{2} and J_{4}, and find that J_{2} also wins. So at the end of the first phase we mark J_{2} as the winner (the minimum so far).
Now we go back to J_{1} but select the second edge leaving this node, and select between J_{1} and J_{8}, and find that J_{8} wins. Now we select between J_{8} and J_{7}, and find that J_{8} wins. Then select between J_{8} and J_{5}, and J_{8} still wins. This ends the second phase.
Between J_{8}=-3 and J_{2}=-3 (winner of phase one), there is a tie so far.
We go back to J_{1} (this is the final stage) and now take the third edge leaving this node, and select between J_{1} and J_{3}. J_{3} wins. Then select between J_{3} and J_{4} and J_{3} wins. Then select between J_{3} and J_{5} and J_{3}=-3 still is the winner.
From vertex J_{1} we have followed this algorithm over all the three edges leaving it, and found that overall minimum is J\left ( u\right ) =-3. If we continue this process, it will just repeat all over.
But J\left ( u\right ) =-3 is not the correct value for the global minimum, since the global minimum is at vertex J_{6}^{\ast }=-27, which we never got the chance to compare with due to the nature of how this algorithm works. If, for example, J_{7} had been smaller than J_{2}, say -4, then we would had the chance to select J_{7} and then compare J_{6} with J_{7} to find that it is the overall minimum. So this algorithm is not guaranteed to converge to the global minimum in general.
Here is the decision tree used for the above process.
We see that the global minimum at vertex J_{6}=-27 was not visited. Wrong turn was taken in each stage.
This appendix can be skipped. It shows the basic calculations for the first phase for illustration, and Matlab code used. Starting at \left ( 1,1,1\right ) , and fixing u_{2}=u_{3}=1.
Hence on the first edge above, we have J\left ( u_{1},u_{2},u_{3}\right ) =8u_{1}u_{2}u_{3}-4u_{1}u_{2}-4u_{1}u_{3}-4u_{2}u_{3}+2u_{1}+2u_{2}+2u_{3}-1
This is minimum when u_{1}=-1. Hence \hat{u}_{1}=-1. Now we see that on the above edge, J is smaller on vertex \left ( -1,1,1\right ) than on \left ( 1,1,1\right ) . Now we look at the next edge, where u_{1}=-1 and u_{3}=1
Fixing u_{3} at 1 and u_{1}=\hat{u}_{1}=-1 then\begin{align*} J\left ( \hat{u}_{1},u_{2},u_{3}\right ) & =J\left ( -1,u_{2},1\right ) \\ & =8\hat{u}_{1}u_{2}u_{3}-4\hat{u}_{1}u_{2}-4\hat{u}_{1}u_{3}-4u_{2}u_{3}+2\hat{u}_{1}+2u_{2}+2u_{3}-1\\ & =-8u_{2}+4u_{2}+4-4u_{2}-2+2u_{2}+2-1\\ & =3-6u_{2} \end{align*}
Hence J\left ( \hat{u}_{1},u_{2},1\right ) is minimum when u_{2}=1. Therefore \hat{u}_{2}=1. This tells us that J at vertex \left ( -1,1,1\right ) is smaller than on \left ( -1,1,-1\right ) . Traveling down the edge between \left ( -1,1,1\right ) and \left ( -1,1,-1\right ) , which is done by fixing u_{2},u_{1} and changing u_{3} gives
Now we need to find \hat{u}_{3}\begin{align*} J\left ( \hat{u}_{1},\hat{u}_{2},u_{3}\right ) & =J\left ( -1,1,u_{3}\right ) \\ & =8\hat{u}_{1}\hat{u}_{2}u_{3}-4\hat{u}_{1}\hat{u}_{2}-4\hat{u}_{1}u_{3}-4\hat{u}_{2}u_{3}+2\hat{u}_{1}+2\hat{u}_{2}+2u_{3}-1\\ & =-8u_{3}+4+4u_{3}-4u_{3}-2+2+2u_{3}-1\\ & =3-6u_{3} \end{align*}
This is minimum at u_{3}=1, Therefore \hat{u}_{3}=1. This means that J is still smallest at vertex \left ( -1,1,1\right ) . We have so far visited 3 edges, and looked at 4 vertices and found that J is smallest at \left ( -1,1,1\right ) .\begin{align*} J\left ( -1,1,1\right ) & =8u_{1}u_{2}u_{3}-4u_{1}u_{2}-4u_{1}u_{3}-4u_{2}u_{3}+2u_{1}+2u_{2}+2u_{3}-1\\ & =-8+4+4-4-2+2+2-1\\ & =-3 \end{align*}
Here is a diagram to illustrate what we did so far
We now repeat the process starting from \left ( 1,1,1\right ) . Fixing u_{1}=1, u_{3}=1, but vary u_{2}. The calculation is similar to the above, and will not be shown. A small Matlab script is given below that was used to verify the results.
Output of the above is
problem description
solution
Since N\left ( u\right ) is multilinear, its maximum and minimum values will be on a vertex. Similarly for D\left ( u\right ) . Therefore, we only need to compare the ratios \frac{N\left ( u\right ) }{D\left ( u\right ) } on the vertices to find the largest ratio. For example, for n=2, we look at the four ratios,\frac{N_{1}}{D_{1}},\frac{N_{2}}{D_{2}},\frac{N_{3}}{D_{3}},\frac{N_{4}}{D_{4}}. Where N_{i} means the value of N\left ( u\right ) at vertex i, and similarly for D_{i}.
Since one of these N_{i} will be the largest value that N\left ( u\right ) can take, and one of these D_{i} values will be the smallest D\left ( u\right ) can take, then the maximum of J\left ( u\right ) =\frac{N\left ( u\right ) }{D\left ( u\right ) } will be one of these four values.
It can not be at any other u_{i} location. Proof by contradiction: Let us assume there is a point somewhere else in the domain of J\left ( u\right ) , say an internal point u_{i} where \frac{N_{i}}{D_{i}} was the largest. This would imply that N_{i} is so large as to make \frac{N_{i}}{D_{i}} larger than any value at the vertices regardless of what D_{i} happened to be at u_{i}, which means that N_{i} is the maximum of N\left ( u\right ) , but this is not possible since the maximum of N\left ( u\right ) must be at a vertex.
Or it could mean that D_{i} is so small such that \frac{N_{i}}{D_{i}} is larger than any value at the vertices regardless of what N_{i} happened to be, which means that D_{i} is the minimum of D\left ( u\right ) , but this is also not possible, since the minimum of N\left ( u\right ) is at a vertex. Therefore the maximum of J\left ( u\right ) must be at a vertex and can not be at any other point.
problem description
solution
The total network resistance (Input impedance) is Z_{in}=R_{1}+R_{2}+R_{3}\Vert \left ( R_{4}+R_{5}+R_{6}\Vert \left ( R_{7}+R_{9}+R_{8}\right ) \right )
The above is the overall ladder network resistance. Let X=R_{4}+R_{5}+\frac{R_{6}\left ( R_{7}+R_{9}+R_{8}\right ) }{R_{6}+\left ( R_{7}+R_{9}+R_{8}\right ) } to simplify the equation Z_{in}=R_{1}+R_{2}+\frac{XR_{3}}{R_{3}+X}
Hence V_{out} is now found, using V_{in}=1, from \begin{align*} \frac{V_{out}}{V_{in}} & =\frac{Z_{out}}{Z_{in}}\\ V_{out} & =\frac{\frac{XR_{3}}{R_{3}+X}}{R_{1}+R_{2}+\frac{XR_{3}}{R_{3}+X}}=\frac{XR_{3}}{R_{1}\left ( R_{3}+X\right ) +R_{2}\left ( R_{3}+X\right ) +XR_{3}}\\ & =\frac{XR_{3}}{X\left ( R_{1}+R_{2}+R_{3}\right ) +R_{1}R_{3}+R_{2}R_{3}} \end{align*}
Since V_{out} multilinear function in R_{i},i=1\cdots 9, the maximum and minimum will occur at the end range values of each resistance, which is 90 and 110. so there are 2^{9} different cases to check. A small script is below which calculate these vertex values and shows the maximum V_{out} found. The maximum is V_{out_{\max }}=0.3147\text{ volt}
Which generates when run:
problem description
solution
Since u_{k}^{\ast } minimizes f\left ( u\right ) when all u_{i} are fixed except for u_{k}, then this is the same as saying that solving for \frac{\partial f}{\partial u_{k}}=0 gives u_{k}^{\ast }. Since this is the necessary condition for an extreme point from unconstrained calculus (we still need to check the Hessian for u_{k}^{\ast } being the minimum or the maximum, but we are told here it is a minimizer).
But \frac{\partial f}{\partial u_{k}} is partial derivative of f\left ( u\right ) w.r.t. to u_{k} when all other u_{i} are fixed (by definition). For \Re ^{n} this carries over and becomes the gradient. Therefore\begin{align*} \nabla f & =0\\\begin{pmatrix} \frac{\partial f}{\partial u_{1}}\\ \frac{\partial f}{\partial u_{2}}\\ \vdots \\ \frac{\partial f}{\partial u_{n}}\end{pmatrix} & =0 \end{align*}
Leads to minimum being at \begin{pmatrix} u_{1}^{\ast }\\ u_{2}^{\ast }\\ \vdots \\ u_{n}^{\ast }\end{pmatrix} since we are told that each \frac{\partial f}{\partial u_{k}}=0 results in u_{k}^{\ast } as the solution.
An example where the above applies is J\left ( x,y\right ) =xy on U=\left [ 0,1\right ] Since\begin{align*} \nabla f & =0\\\begin{pmatrix} \frac{\partial f}{\partial x}\\ \frac{\partial f}{\partial y}\end{pmatrix} & =\begin{pmatrix} y\\ x \end{pmatrix} =\begin{pmatrix} 0\\ 0 \end{pmatrix} \end{align*}
Hence a minimizer is u^{\ast }=\begin{pmatrix} x=0\\ y=0 \end{pmatrix} and J\left ( u^{\ast }\right ) =0 is the global minimum.
An example where part (a) does not apply is J\left ( x,y\right ) =xy on U=\left [ -1,1\right ] . Now u^{\ast }=\begin{pmatrix} 0\\ 0 \end{pmatrix} is not the minimizer, since if x=-1 and y=1 or if x=1 and y=-1, we find J\left ( u^{\ast }\right ) =-1<0.
The following is a plot of J(x,y)=xy of different sets of constraints to illustrate part(b) and (c).