where c R is arbitrary. It is customary to normalize storage and Lyapunov functions so that their minimum equals zero, which yields c=2 and 72 Now, summing the inequalities(7. 2)from t=0 to t= T yields T-1 y y(t)≤v(x(0)-Vx()+∑m(), t=0 which is implies the desired relation between the numbers of 1s in the input and in the output, since V(a(O))-V(a(r)cannot be larger than 2 7.1.2 Storage functions via cutting plane algorithms The possibility to reduce the search for a valid storage function to convex optimization as demonstrated by the example above, is a general trend. One general situation in which an efficient search for a storage function can be performed is when a cheap procedure of checking condition(7.3)(an oracle) is available Assume that for every given element V E v it is possible to find out whether condition (7. 3 )is satisfied, and, in the case when the answer is negative, to produce a pair of vectors tEX, w EW for which the inequality in(7.3)does not hold. Select a sufficiently large set To(a polytope or an ellipsoid)in the space of parameter vector T=(aI(this set will limit the search for a valid storage function). Let T*be the "center"of To. Define V by the r*, and apply the verification "oracle" to it. If V is a valid storage function the search for storage function ends successfully. Otherwise, the "invalidity certificate I, a) produced by the oracle yields a hyperplane separating T* and the(unknown)set of T defining valid storage functions, thus cutting a substantial portion from the search set To, reducing it to a smaller set T1. Now re-define T'as the center of Ti and repeat the process by constructing a sequence of monotonically decreasing search sets Tk, until either a valid storage function is found, or Tk shrinks to nothing With an appropriate selection of a class of search sets Tk(ellipsoids or polytopes are most frequently used) and with an adequate definition of a "center"(the so-called "analytical center"is used for polytopes), the volume of Tk can be made exponentially decreasing, which constitutes fast convergence of the search algorithm 7.1.3 Completion of squares The success of the search procedure described in the previous section depends heavily on the choice of the basis functions Vk. A major difficulty to overcome is verification of (7.3) for a given V. It turns out that the only known large linear space of functionals3 where c ≤ R is arbitrary. It is customary to normalize storage and Lyapunov functions so that their minimum equals zero, which yields c = 2 and φ1 = 2, φ2 = 0, φ3 = 1. Now, summing the inequalities (7.2) from t = 0 to t = T yields T −1 T −1 3 y(t) → V (x(0)) − V (x(T)) + w(t), t=0 t=0 which is implies the desired relation between the numbers of 1’s in the input and in the output, since V (x(0)) − V (x(T)) cannot be larger than 2. 7.1.2 Storage functions via cutting plane algorithms The possibility to reduce the search for a valid storage function to convex optimization, as demonstrated by the example above, is a general trend. One general situation in which an efficient search for a storage function can be performed is when a cheap procedure of checking condition (7.3) (an oracle) is available. Assume that for every given element V ≤ V it is possible to find out whether condition (7.3) is satisfied, and, in the case when the answer is negative, to produce a pair of vectors x¯ ¯ ≤ X, w ≤ W for which the inequality in (7.3) does not hold. Select a sufficiently large set T0 (a polytope or an ellipsoid) in the space of parameter vector φ = (φq)q N =1 (this set will limit the search for a valid storage function). Let φ � be the “center” of T0. Define V by the φ �, and apply the verification “oracle” to it. If V is a valid storage function, the search for storage function ends successfully. Otherwise, the “invalidity certificate” x, w¯(¯ ) produced by the oracle yields a hyperplane separating φ � and the (unknown) set of φ defining valid storage functions, thus cutting a substantial portion from the search set T0, reducing it to a smaller set T1. Now re-define φ � as the center of T1 and repeat the process by constructing a sequence of monotonically decreasing search sets Tk, until either a valid storage function is found, or Tk shrinks to nothing. With an appropriate selection of a class of search sets Tk (ellipsoids or polytopes are most frequently used) and with an adequate definition of a “center” (the so-called “analytical center” is used for polytopes), the volume of Tk can be made exponentially decreasing, which constitutes fast convergence of the search algorithm. 7.1.3 Completion of squares The success of the search procedure described in the previous section depends heavily on the choice of the basis functions Vk. A major difficulty to overcome is verification of (7.3) for a given V . It turns out that the only known large linear space of functionals