{'fraction_non_alphanumeric': 0.040576655248993114, 'fraction_numerical': 0.011706252117288365, 'mean_word_length': 4.644359464627151, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Scenario optimization with certificates and applications to anti-windup design

In this paper, we introduce a significant extension, called scenario with certificates (SwC), of the so-called scenario approach for uncertain optimization problems. This extension is motivated by the observation that in many control problems only some of the optimization variables are used in the design phase, while the other variables play the role of certificates. Examples are all those control problems that can be reformulated in terms of linear matrix inequalities involving parameter-dependent Lyapunov functions. These control problems include static anti-windup compensator design for uncertain linear systems with input saturation, where the goal is the minimization of the nonlinear gain from an exogenous input to a performance output. The main contribution of this paper is to show that randomization is a useful tool, specifically for anti-windup design, to make the overall approach less conservative compared to its robust counterpart. In particular, we demonstrate that the scenario with certificates reformulation is appealing because it provides a way to implicitly design the parameter-dependent Lyapunov functions. Finally, to further reduce the computational cost of this one-shot approach, we present a sequential randomized algorithm for iteratively solving this problem.


I. INTRODUCTION
Randomized and probabilistic methods for control received a growing attention in the systems and control community in recent years [22]. These methods deal with the design of controllers for systems affected by possibly nonlinear, structured and unstructured uncertainties. One of the key features of these methods is to break the curse of dimensionality, i.e., uncertainty is "lifted" and the resulting controller satisfies a given performance for "almost" all uncertainty realizations. In other words, in this framework, we accept a "small" risk of performance violation.
One of the successful methods that have been developed in the area of randomized and probabilistic methods is the so-called scenario approach, which provides an effective tool for solving control problems formulated in terms of robust optimization [5]. In this case, the sample complexity, which is the number of random samples that should be drawn according to a given probabilistic distribution, is derived a priori, and it depends only on the number of design parameters n θ , and probabilistic parameters called accuracy ǫ and confidence δ. In particular, it has been shown that n θ , and 1/ǫ enter linearly into the sample complexity and δ in a logarithmic fashion. Therefore, we can conclude that δ is computationally cheap, while accuracy is more expensive, and for very tiny values of ǫ, the sample complexity becomes very large. For this reason, sequential approaches have been developed [11]. In this case, at each iteration of the algorithm, the idea is to construct (temporarily) a controller, whose performance is then validated through a Monte Carlo approach. If the controller does not enjoy the required probabilistic performance specification, a new controller is designed based on new sample extractions. At each step of the sequence, a reduced-size scenario problem is solved. This method is more effective in practical applications where the standard scenario approach fails because of the large sample complexity, but has other drawbacks including the fact that the sample complexity cannot be determined a priori.
The classical scenario approach and its sequential version may be applied to specific control problems such as designing a common quadratic Lyapunov function. In these cases, however, the fact that a single common Lyapunov function should hold for all possible uncertainties leads to an overly conservative design. The same drawback is known in classical robust control, where the design of a common quadratic Lyapunov function requires an exponential number of computations [2], [8]. For these reasons, parameterized Lyapunov functions have been developed and used in many control problems subject to uncertainty [3,Chapter 19.4].
In the first part of the paper (Section II), we develop a new framework, denoted as scenario with certificates, which is very effective in dealing with parameter-dependent Lyapunov functions. This framework continues the research originally proposed in [19] for feasibility problems in the context of randomized methods. The main idea in this approach is to distinguish between design variables θ and certificates ξ and has the advantage, compared to classical robust methods, that no explicit parameterization (linear or nonlinear) of the Lyapunov functions is required. In other words, the method is based on a "hidden" parameterization of the Lyapunov functions, and has the clear advantage compared to the methods based on the design of common Lyapunov functions to reduce the conservatism.
In the second part of the paper (Section III and IV), we show the application of the scenario with certificates approach to the design of anti-windup schemes. We recall that robust approaches for these schemes have been developed by proposing several successful solutions, see, e.g., [16], [23], [21], [13], [20].
In [14], the classical scenario optimization approach has been applied to anti-windup schemes in order to obtain probabilistic guarantees for the L 2 gain of the uncertain systems, without enforcing any constraint on the uncertainty set. However, in that formulation, both the certificates and the design variables were treated as optimization variables over the whole operating region, thus leading to a conservative solution, and sometimes -to unfeasibility. With the proposed SwC optimization approach, we show that robust compensators can be obtained without enforcing any additional constraints on the certificates. Moreover, by computing the (probabilistic) worst case L 2 gain with the SwC version of the analysis problem, we can show that the estimate of the worst case L 2 gain becomes much more accurate. This is demonstrated using the benchamrk example introduced in [24] (Section IV) to show the performance of static anti-windup augmentation. The paper is ended by some concluding remarks.

II. SCENARIO WITH CERTIFICATES
In this section, we briefly recall the scenario approach for dealing with convex optimization problems in the presence of uncertainty, and subsequently introduce a novel framework that we name scenario with certificates.

A. The scenario approach
The so-called scenario approach has been developed, [5] [9], to deal with robust convex optimization problems of the form where, for given q within the uncertainty set Q, f (θ, q) are convex functions of the optimization variable θ ∈ Θ, and the domain Θ is a convex and compact set in R n θ . Following the probabilistic approach discussed for instance in [22], [6] a probabilistic description of the uncertainty is considered over Q, that is we formally assume that q is a random variable with given probability distribution with support Q. Such a probability distribution may describe the likelihood of each occurrence of the uncertainty or a user-defined weight for all possible uncertain situations. Then, N independent identically distributed (iid) samples q (1) , . . . , q (N ) are extracted according to the probability distribution of the uncertainty over Q, forming the multisample These samples are used to construct the following scenario optimization (SO) problem, based on N instances (scenarios) of the uncertain constraints s.t. f (θ, q (i) ) ≤ 0, i = 1, . . . , N.
The problem (SO) can be seen as a probabilistic relaxation of the problem (RO), since it deals only with a subset of the constraints considered in (RO), according to the probability distribution of the uncertainty. However, under rather mild assumptions on problem (RO), by suitably choosing N , this approximation may in practice become negligible. Specifically, N can be selected depending on the level of "risk" of constraint violation that the user is willing to accept. Then, we define the violation probability of the design θ as Similarly, the reliability of the design θ is given by Then the following result has been proven in [10]. Proposition 1: [10] Assume that, for any multisample extraction, problem (SO) is feasible and attains a unique optimal solution. Then, given an accuracy level ǫ ∈ (0, 1), the solution θ SO of problem (SO) satisfies where We note that non-uniqueness of the optimal solution can be circumvented by imposing additional "tie-break" rules in the problem, see, e.g., Appendix A of [5]. Also, in [7] it is shown that the feasibility assumption can be removed at the expense of substituting n θ − 1 with n θ in B(N, ǫ, n θ ).
From Equation (2), explicit bounds on the number of samples necessary to guarantee the "goodness" of the solution have been derived. The bound provided in [1] shows that, if, for given ǫ, δ ∈ (0, 1), the sample complexity N is chosen to satisfy the bound (where e denotes the Euler number), then the solution θ SO of problem (SO) satisfies Viol(θ SO ) ≤ ǫ with probability 1 − δ. This bound shows that problem (SO) exhibits linear dependence in 1/ǫ and n θ , and logarithmic dependence on 1/δ. Note however that, from a practical viewpoint, it is always preferable to numerically solve the one dimensional problem of finding the smallest N such that B(N, ǫ, n θ ) ≤ δ.

B. Scenario with certificates
The classical scenario approach previously discussed deals with uncertain optimization problems where all variables θ are to be designed. On the other hand, following the approach introduced in [19] for feasibility problems, in the design with certificates approach we distinguish between design variables θ and certificates ξ. In particular, we consider now a function f (θ, ξ, q), jointly convex in θ ∈ Θ and ξ ∈ Ξ for given q ∈ Q, and construct the robust optimization problem with certificates where the set S(q) is defined as Remark 1: [Convexity of problem (RwC)] Note that, for any given q, the set S(q) is convex: to see this, consider θ 1 , θ 2 ∈ S(q). Then, there exist ξ 1 , ξ 2 such that Then, from convexity of f with respect to both θ and ξ it immediately follows hence θ λ ∈ S(q), which proves convexity.
• We propose to approximate problem (RwC) introducing the following scenario optimization with certificates problem, based again on a multisample extraction Note that, contrary to problem (SO), in this case a new certificate variable ξ i is created for every sample q (i) , i = 1, . . . , N . To analyze the properties of the solution θ SwC , we note that, in the case of SwC, the reliability and violation probabilities of design θ rewrite We now state the main result regarding the scenario optimization with certificates.
Theorem 1: Assume that, for any multisample extraction, problem (SwC) is feasible and attains a unique optimal solution. Then, given an accuracy level ǫ ∈ (0, 1), the solution θ SwC of problem (SwC) satisfies (5) Proof: Observe that the condition θ ∈ S(q) is equivalent to requiring Note that, from joint convexity of f with respect to θ, ξ for given q, it follows that for given q the function f ξ (θ, q) is convex in θ, see for instance [4, p. 113]. Hence, problem (10) is a robust convex optimization problem, for which we can construct the following scenario counterpart s.t. min where the subscript i for the variables ξ i highlights that the different minimization problems are independent. Finally, we note that (7) immediately rewrites as problem (SwC).

C. Sequential randomized algorithm for SwC
When ǫ is small and n θ is large, the smallest value of N satisfying (4) is typically very large. This fact makes the computational burden for SwC prohibitive for real world applications. In this section, we present a sequential randomized algorithm that alleviates the computational load of solving the SwC problem in one-shot. The algorithm is a minor modification of [11,Algorithm 1], and it is based on separate design and validation steps. The design step requires the solution of a reduced-size SwC problem. In the validation step, contrary to [11] where only functional evaluations are required, a number of feasibility problems (one for each sample extraction) need to be solved. However, it should be pointed out that these problems are of small size, and can be solved independently, and hence parallelized. The sequential procedure is presented in Algorithm 1, and its theoretical properties are stated in the subsequent theorem. The proof is omitted because it follows the same lines of [11,Theorem 1].

Sequential Algorithm for SwC
1) INITIALIZATION set the iteration counter k = 0. Choose the desired probabilistic levels ǫ, δ and the desired number of is unfeasible goto step (2).
(11) In the second part of this paper, we introduce the problem of robust L 2 gain minimization for linear anti-windup systems. The SwC approach appears to be very suited for such a design problem, for several reasons: i) the nominal design can be formulated in terms of linear matrix inequalities (LMIs), ii) the uncertainty set can in principle be of any size and shape, and iii) the optimization variables can be clearly divided in design variables for the anti-windup augmentation and certificates for stability and performance guarantees.

III. ANTI-WINDUP COMPENSATOR DESIGN
Consider the linear uncertain continuous-time plant with input saturatioṅ where x p is the plant state, σ is the control input, w is an external input (possibly comprising references and disturbances), z is the performance output, y is the measured output and q denotes a random uncertainty within the set Q. We denote byq ∈ Q the nominal value of the uncertain parameters.
As customary with linear anti-windup design [24], we assume that a linear controller has been designed, based on the nominal system, in order to induce suitable nominal closed-loop properties when interconnected to plant (12) where x c is the controller state, w typically comprises references (but may also contain disturbances), u is the T is an extra input available for anti-windup action. Controller (13) is typically designed in such a way that the so-called unconstrained closed-loop system given by (12), (13), σ = u, v = 0 is asymptotically stable and satisfies some performance requirements.
Consider now the (physically more reasonable) saturated interconnection σ = sat(u), where the k th entry of σ is sat k (u k ) = max(min(ū k , u k ), −ū k ), denoting the k th input by u k . When the input saturates, the closed loop system composed by the feedback loop between (12) and (13) is no longer linear and may exhibit undesirable behavior, usually called controller windup. Then, one may wish to use the free input v to design a suitable static anti-windup compensator This signal can be injected into the right hand side of the controller dynamics (13) to recover stability and performance of the unconstrained closed-loop system.
When lumping together the plant-controller-anti-windup components (12), (13), (14), σ = sat(u), one obtains the socalled anti-windup closed-loop system, a nonlinear control system which can be compactly written using the state x = [x T p x T c ] T as in (15) (at the top of the next page), where dz denotes the deadzone function, i.e., dz(u) = u − sat(u), and all the matrices are uniquely determined by the data in (12), (13), (14) (see, e.g., the full authority anti-windup section in [24] for explicit expressions of these matrices).
The compact form in (15) may be used to represent both the saturated closed loop before anti-windup compensation, by selecting D aw = 0, or the closed loop with antiwindup compensation, by performing some nonzero selection of D aw .
We start by analyzing the system (15) for the nominal case, that is when no uncertainty is present and Q is a singleton coinciding with the nominal value of the parameters. We recall the following stability and performance analysis result from [15,Theorem 2].
Proposition 2 (Regional stability/performance analysis): Given a scalar s > 0, consider the nominal system, that is let Q ≡ {q}. Assume that the LMI problem (16) in the variables γ 2 , Q, Y and U is feasible. Then: (a) the nonlinear algebraic loop in (15) is well posed, (b) the origin of (15) is locally exponentially stable with region of attraction containing the set (c) for each w satisfying w 2 ≤ s, the zero state solution to (15) satisfies z 2 ≤γ w 2 , where the L 2 gain of the system is given bŷ s.t. (16).
As suggested in [15], one may use the result of Proposition 2 to compute an estimate of all the nonlinear L 2 gain curve (see [17], namely a function s →γ(s) such that for each s in the feasibility set of (16) and for each w satisfying w 2 ≤ s, the zero state solution to (15) satisfies To do so, it is possible to sample the nonlinear gain curve s →γ(s) by selecting suitable positive values s 1 < · · · < s n and, for each k = 1, . . . , n, solving Problem (18), after replacing s = s k . Then, the L 2 gain curve estimate can be constructed by interpolating the points (s k ,γ k (s k )), k = 1, . . . , n.
Following the derivations in [12] (which generalize the global results of [18]), one may notice that the product D aw U appears in a linear way in equation (16b) and, for a fixed value of s, the synthesis of a static anti-windup gain minimizing the nonlinear L 2 gain can be written as a convex optimization problem, as stated next.
Consider now the uncertain case, when the system matrices in (15) defining the dynamics of x and z are continuous (possibly nonlinear) functions of the uncertainty q ∈ Q. Then, the interest is in finding robust solutions to the analysis and design problems discussed before. For instance, in the analysis case, one could search for common certificates Q, Y, U such that γ 2 is minimized over (16) for all q ∈ Q. This approach is the one pursued in the paper [14], where scenario results are used to find probabilistic guaranteed estimates.
However, as discussed in Section II-C, an approach based on common certificates is in general very conservative, and one would be more interested in finding parameterdependent certificates. To do this, we would need to solve the following robust optimization problem with certificateŝ A similar rationale can be applied to robustify the antiwindup synthesis problem of Proposition 3. As a matter of fact, when the system matrices are uncertain, one meets similar obstructions to those highlighted as far as analysis was concerned. Again, instead of looking for common Lyapunov certificates as done in [14], we write the following RwC problem Note that both problems (21) and (22) are difficult nonconvex semi-infinite optimization problems, due to the fact that one has to determine the certificates as functions of the uncertain parameter q. A classicall approach in this case is to assume a specific dependence (e.g., affine) of the certificates on the uncertainty. Instead, in this paper we adopt a probabilistic approach, assuming that q is a random variable with given probability distribution over Q, and apply the SwC approach discussed in Section II-C. This allows us to find an implicit dependence on q of the certificates. This is in the spirit of the original idea proposed in [19].
The following two theorems, whose proofs come straightforwardly from Propositions 1 and 2, exploit the SwC approach to address the robust nonlinear L 2 gain estimation and synthesis for saturated systems. In particular, the next theorem provides a convex optimization procedure to obtain probabilistic information about the worst case nonlinear L 2 gain.

Theorem 3 (Probabilistic performance analysis):
Fix a positive value s denoting an upper bound for w 2 and define an acceptable level of probability of constraint violation ǫ ∈ (0, 1) and a level of confidence δ ∈ (0, 1). Let the design variable and the certificates be, respectively, θ = γ 2 and ξ = {Q, U, Y } and choose N as the smallest integer such that B(N, ǫ, n θ ) ≤ δ. Construct the SwC approximation of problem (21) assuming that, for any multisample extraction, the ensuing problem (SwC) is feasible and attains a unique optimal solution. Then, for each w 2 < s, the zero state solution of system (15) satisfies Pr( z 2 >γ(s) w 2 ) < ǫ, with level of confidence no smaller than 1 − δ.
The next theorem provides the formal result for robust randomized synthesis using the SwC approach.
Theorem 4 (Probabilistic anti-windup synthesis): Fix a positive value s denoting an upper bound for w 2 , and define an acceptable level of probability of constraint violation ǫ ∈ (0, 1) and a level of confidence δ ∈ (0, 1). Let the design variable and the certificates be, respectively, θ = γ 2 , X, U and ξ = {Q, Y } and choose N as the smallest integer such that B(N, ǫ, n θ ) ≤ δ. Construct the SwC approximation of problem (22) assuming that, for any multisample extraction, the ensuing problem (SwC) is feasible and attains a unique optimal solution. Then, for each w 2 < s, the zero state solution of the uncertain system (15) with anti-windup static compensator (20) satisfies with level of confidence no smaller than 1 − δ.
For completeness, in (23) we report the SwC problem arising from the application of Theorem 4. The SwC problem arising from the application of Theorem 3 can be constructed following the same rationale and it is not reported here for the sake of space.
The reformulation of the SwC approach for nonlinear gain analysis and synthesis in Theorems 3 and 4 is appealing from an engineering viewpoint. As a matter of fact, since the N instances of the system matrices are extracted according to the probability distribution of the uncertainty, the solution of the problem provides a view of what may happen in most of practical situations. Moreover, we stress that the proposed formulation does not constrain the unknown Lyapunov matrices Q i 's to be the same for all the sampled perturbations. Instead, it allows them to vary from one sample to another. This is possible because the Q i 's (as well as the Y i 's) are only instrumental for the computation of the robust compensator. Notice that, unlike system matrices, e.g., the A cl (q (i) )'s, which are uncertain by definition, the certificates are unknown but they are not random variables.

IV. SIMULATION EXAMPLE
In this section, we show the effectiveness of the proposed approach, by designing an anti-windup compensator for the passive electrical network in Fig. 1. The circuit is a benchmark example in the anti-windup literature and was already employed in [24] to show the potential of static compensators.
The dynamics of the network is determined by 5 resistors and 3 capacitors, whose nominal values are reported in Table I. The gain k is instead selected such that the transfer function between V i and V o is monic. 313 315 Ω R 4 17 Ω R 5 10  Assume now that the input V i is saturated between the minimum and the maximum voltage ±1. An anti-windup compensator based on the nominal model can be designed to minimize the nonlinear gain between the reference and the tracking error. The gain obtained using s = 0.003 is D nom aw = [−0.0855, 0.0011, 0.9887] T . Under the hypothesis that the parameters are Gaussian distributed with mean values as in Table I and standard deviation of 10%, also the robust randomized compensator can be computed. Using the same value of s of the nominal case, i.e., s = 0.003, D rand aw = [−2.1493, 0.0266, 0.6407] T is obtained. For this example, ǫ = 0.01 and δ = 10 −6 are selected. Therefore, we notice that, in principle, at least N = 7565 are required to give the desired probabilistic guarantees (n θ = 35 in (3)). However, since Algorithm 1 is employed, only 2270 samples are actually used for the design.
The results of nominal and robust anti-windup compensators are reported in Fig. 2, where both the nominal and the robust L 2 gain estimates are computed. As expected, we observe that the robust compensator outperforms the  one designed for the nominal system, as far as the robust L 2 gain is concerned (solid lines). Conversely, when the performance is evaluated on the nominal system (dashed lines), the robust compensator yields worse results, since it is more conservative. From the analysis point of view, notice also that the L 2 gain estimated using the robust probabilistic method is larger than the one given by nominal analysis. This holds for any configuration of the saturated closed-loop system (without anti-windup, with nominal compensator and with robust compensator). The degradation of the performance of the nominal closedloop system using the robust compensator in place of the nominal one can be assessed by looking at the time responses illustrated in Fig. 3. From the figure, we conclude that, although in any case the use of a compensator increases the overall performance in terms of tracking error and overshoot, we have to accept worse behavior in nominal conditions when using robust anti-windup. However, this choice is rewarding when acting on a system subject to uncertainty. Specifically, in Fig. 4, we show that the response of the system with the robust anti-windup is less sensitive to parameter uncertainties than the other solutions. Specifically, in the figure, we illustrate, as an example, the responses

V. CONCLUSIONS
In this paper, we proposed a distinction between standard robust convex optimization problems (RO), where all the optimization variables are used for design, and robust optimization problems with certificates (RwC), where some optimization variables play just the role of certificates of performance. Then, we defined the scenario counterpart for randomized solution of RwC, that we called Scenario with Certificates (SwC). Unlike standard scenario optimization (SO), SwC allows one to create one certificate variable for each sample of the uncertainty, thus leading to less conservative solutions. Static anti-windup augmentation is a typical problem where some variables, like the Lyapunov matrix, appear in the LMIs only to certify stability of the closed-loop system, but are not used inside the formula to compute the compensator gains. We applied the SwC approach to anti-windup compensator design and showed that this method leads to better design than the state of the art. In future works, we will concentrate on the application of such an approach on a broader class of problems, to better analyze the potential of SwC with respect to standard scenario optimization.