{'fraction_non_alphanumeric': 0.04110165922681715, 'fraction_numerical': 0.015328897498526067, 'mean_word_length': 4.3376039559451565, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sparse Output Feedback Synthesis via Proximal Alternating Linearization Method

We consider the co-design problem of sparse output feedback and row/column-sparse output matrix. A row-sparse (resp. column-sparse) output matrix implies a small number of outputs (resp. sensor measurements). We impose row/column-cardinality constraint on the output matrix and the cardinality constraint on the output feedback gain. The resulting nonconvex, nonsmooth optimal control problem is solved by using the proximal alternating linearization method (PALM). One advantage of PALM is that the proximal operators for sparsity constraints admit closed-form expressions and are easy to implement. Furthermore, the bilinear matrix function introduced by the multiplication of the feedback gain and the output matrix lends itself well to PALM. By establishing the Lipschitz conditions of the bilinear function, we show that PALM is globally convergent and the objective value is monotonically decreasing throughout the algorithm. Numerical experiments verify the convergence results and demonstrate the effectiveness of our approach on an unstable system with 60,000 design variables.


I. INTRODUCTION
Recent years have seen progress on the design of sparse, structured feedback controllers [1]- [11]. One driving force for this research direction is its wide range of applications in the control of complex systems, including power systems [12], [13], multi-agent systems [14], [15], oscillator networks [16], [17], and social networks [18]. A recent survey on the development of this research effort can be found in [19].
A diverse set of tools for optimal sparsity control have been developed and tailored to specific design requirements. In [1], an augmented Lagrangian method was proposed for the structured state feedback problem. In [2], [3], sparse LQR state feedback controllers were obtained via the alternating direction method of multipliers. In [4], an approach based on linear matrix inequality was proposed for the row/column sparse feedback problem. In [5], a convex-concave decomposition method for bilinear matrix inequality was shown effective for static output feedback problems. In [6], a rank constrained optimization method was developed for the sparse output feedback design. In [9], a sparse H 2 output feedback controller that resembles the centralized controller in frequency characteristics was proposed. In [7], [10], localized output feedback controllers with communication delay were developed.
In this work, we design of the output feedback and the output matrix simultaneously. The motivation for this co-F. Lin  design output feedback problem is two-fold. First, output feedback controllers require fewer sensors than state feedback controllers. One may have a limited budget for the number of sensors and is thus constrained to output feedback design. Second, it is useful to estimate the tradeoff between the number of sensors and the number of communication links for the output controllers. In practice, it is challenging to strike a good balance between the choice of sensor networks and the communication networks. Our work is a step to this direction by including the output matrix in the design process. Co-design problems of linear systems with system matrices have been considered in [20], [21].
The placement of sensors and actuators for feedback control has been an active research topic [22]- [25]. In [23], a two-part cost function was proposed for state feedback with full information and the state estimation with candidate sensors. From system integration and cost perspective, it is desired to use the least number of sensors to achieve the required performance objective [24], [25]. In this context, we design simultaneously feedback sensor structure and sparse feedback gains to reduce the sensing cost and the number of communication links in distributed control.
We impose the row/column-sparsity condition on the output matrix and sparsity condition on the output feedback gain. In particular, we employ the row/column cardinality constraint in order to directly control the number of nonzero rows/columns of the output matrix. The nonconvex, nonsmooth optimal control problem is solved by using the proximal alternating linearization method (PALM). We establish the global convergence of PALM by proving the Lipschitz conditions of the bilinear matrix function. Furthermore, when the closed-loop performance index satisfies the Kurdyka-Lojasiewicz property, we show that PALM is guaranteed to converge to a critical point of the optimal control problem.
The presentation is organized as follows. In Section II, we formulate the co-design output feedback problem. In Section III, we develop the PALM algorithm and in Section IV, we provide the convergence analysis. In Section V, we demonstrate the convergence behavior of PALM via numerical experiments. In Section VI, we summarize our contributions.

II. CO-DESIGN OUTPUT FEEDBACK PROBLEM
Consider the static output feedback desigṅ where x(t) ∈ R n is the state, d(t) ∈ R q is the disturbance input, u(t) ∈ R m is the control input, and y(t) ∈ R p is the measured output.
In this work, we design both the output matrix C ∈ R p×n and the output feedback gain K ∈ R m×p simultaneously. We impose sparsity conditions on both design variables. The cardinality of the output feedback K is defined as card(K) := number of nonzero entries of K.
A sparser K implies a smaller number of communication channels from the sensors to the actuators. We are interested in the output matrix C with sparse rows or sparse columns. Because a row-sparse C implies a small number of outputs, while a column-sparse C implies a small number of sensors to measure the states. The row-cardinality of a matrix is defined as card row (C) := number of nonzero rows of C.
Or equivalently, where C i denotes the ith row of C and · denotes the Euclidean norm. Column-cardinality of C is equal to the rowcardinality of its transpose, C T . In what follows, we use rowsparsity without loss of generality.
The co-design problem of the sparse output feedback can be expressed as follows: where s and r are prespecified positive integers. Here, J is a user-specified performance index of the closed-loop system. We assume that J is bounded below for all F . When A − BF is not Hurwitz, J is defined as the positive infinity.
Problem (1) is a nonconvex, nonsmooth optimal control problem. Because the cardinality constraints are nonconvex, nonsmooth, and the bilinear constraint F = KC is nonconvex. This difficulty limits the number of solution algorithms since exiting algorithms typically require convexity or smoothness or both properties [26]- [29]. One may relax the cardinality constraint by using the convex surrogates such as the 1 norm. It is noteworthy that the PALM algorithm can handle both convex and nonconvex penalty functions [29].
We next put the co-design problem into a formulation suited to PALM, the proximal alternating linearization method, originally proposed for generic nonconvex, nonsmooth problems [29]. We begin by penalizing the difference between F and KC in the cost function where γ is a sufficiently large, positive coefficient and · F denotes the Frobenius norm. By introducing the indicator for the cardinality constraint, and the indicator function for the row-cardinality constraint, problem (2) can be expressed as Note that Φ is separable with respect to K, C, and F except for the coupling function It turns out that this bilinear matrix function lends itself well to PALM. In particular, the Lipschitz constants of the partial gradient of H can be calculated explicitly, which facilitates the implementation of PALM and the proof of its convergence.

III. PROXIMAL ALTERNATING LINEARIZATION METHOD
PALM falls in the class of proximal methods for nonconvex, nonsmooth optimization problems recently developed in [26]- [29]. It is also closely related to the alternating direction method of multipliers for convex problems. In this section, we show that the co-design problem is well suited to PALM; in particular, the proximal operators for the sparsity constraints can be computed efficiently.
The PALM algorithm computes the minimum of the proximal functions iteratively The quadratic term K−X k 2 F encourages the solution of (7a) to be in the proximity of X k , where Note that X k is a linear combination of the current iterate K k and the partial gradient of H with respect to K, hence the name linearization in PALM. A key requirement for the convergence of PALM is that the coefficient a k be chosen to be greater than the Lipschitz constant of ∇ K H. For fixed (C k , F k ), the Lipschitz constant L 1 satisfies for all K 1 and K 2 . We set a k = γ 1 L 1 for some γ 1 > 1.
Similarly, the proximal points (Y k , Z k ) are linear combination of the current iterate (C k , F k ) and the partial gradients . Let L 2 and L 3 be the Lipschitz constants of ∇ C H and ∇ F H, respectively. That is, L 2 satisfies for all C 1 and C 2 , and L 3 satisfies

A. Lipschitz conditions
The Lipschitz conditions of the partial gradient of H are critical for the global convergence of PALM. Furthermore, the Lipschitz conditions are necessary for the implementation of PALM because they determine the coefficients a k , b k , c k in the proximal operators (7). The Lipschitz constants for the codesign problem can be computed via a closed-form expression. This is because the partial gradient of the bilinear coupling function is linear; in particular, the partial gradients of H with respect to K, C, and F are given by Since ∇ K H, ∇ C H, and ∇ F H are linear functions of K, C, and F , respectively, it follows that the Lipschitz constants are given by

B. Explicit formulas for proximal operators
We next show that the proximal operators (7a) and (7b) can be computed efficiently via explicit formulas. As a result, the implementation of PALM is particularly simple.
The proximal operator (7a) can be written as The solution is obtained by keeping the s largest entries of X k in magnitude and set the remaining entries to zero. This result is well known; e.g., see [29]. Let X k s be the sth largest entry of X k in magnitude and let I k s ∈ R m×n be such that The solution is obtained by truncating the entries whose magnitude is less than X k where • denotes the entry-wise multiplication of matrices. When 1 norm is used to promote sparsity, an efficient algorithm for the projection to the 1 ball can be found in [30]. The proximal operator (7b) can be written as Similar to the entry-wise truncation, the row-wise truncation amounts to keeping the r largest rows of Y k in Euclidean norm and set the remaining rows to zero. Let δ k be the rth Then the row truncation of Y k can be expressed as where 1 ∈ R n is the vector of all ones. For column sparsity constraint, apply the truncation operator to the rows of C T .
C. Computation of proximal operator (7c) One advantage of PALM is that it allows the computation of the proximal operator (7c) to be independent of other proximal operators (7a)-(7b). In other words, it does not rely on a specific performance index J in the minimization problem This feature of separability has been noted in the state feedback design by using the alternating direction method of multipliers (ADMM); see [3]. For example, we consider the closed-loop H 2 norm from the disturbance d to the performance output where Q and R are positive definite matrices. In [3] the Anderson-Moore method was developed for the minimization step (11); see Appendix for details.
We summarize PALM in Algorithm 1.

IV. CONVERGENCE ANALYSIS
The global convergence of PALM for nonconvex, nonsmooth problems are analyzed in [28], [29]. In this section, we build on the results in [29] and show the global convergence of PALM for the co-design problem. Furthermore, the objective value is monotonically decreasing throughout the PALM algorithm. When the performance index J satisfies the so-called KL property, PALM is guaranteed to converge to a critical point. The proofs can be found in Appendix.
We begin with a technical lemma on the Lipschitz conditions of Φ.
. Perform the entry-wise truncation of X k by using (9). // C-minimization step Compute the Lipschitz constant . Perform the row-wise truncation of Y k by using (10). // F -minimization step When J is the closed-loop H 2 norm, employ the Anderson-Moore method in Appendix D. end for 2) The partial gradients ∇ K H, ∇ C H, and ∇ F H are globally Lipschitz.

3) There exist bounded constants q
4) The entire gradient ∇H is Lipschitz continuous on the bounded subsets of R m×n × R n×n × R m×n .
Property 1) ensures that proximal operators in PALM are well defined and the minimization of Φ is also well defined. Property 2) on the boundedness of the Lipschitz constants is critical for convergence. Note that the block-Lipschitz property in K, C, and F is weaker than standard assumptions in proximal methods that require Φ to be globally Lipschitz in joint variables (K, C, F ); see [29]. Property 3) guarantees that the Lipschitz constants for the partial gradients are lower and upper bounded by finite numbers. Property 4) is a technical condition for controlling the distance between two consecutive steps in the sequence (K k , C k , F k ). This is a mild condition that holds when H is twice continuously differentiable as in (6).
Here J is defined as the positive infinity for an unstable state feedback gain F . From Lemma 1 and from the convergence results established in Lemma 3.3 of [29] for generic PALM, it follows that the objective value Φ is monotonically decreasing in PALM. Specifically, we have the following result.
Proposition 1: Suppose that Assumption 1 holds. Let G k := (K k , C k , F k ) be a sequence generated by Algorithm 1. Then where δ = min{(γ i − 1)q − i } for i = 1, 2, 3. Note that δ > 0 throughout PALM iterations because γ i > 1 for i = 1, 2, 3 (see Algorithm 1) and q − i > 0 for i = 1, 2, 3 (see Lemma 1). Thus, the convergence of the decision variable G k can be measured by the convergence of the objective value Φ. The numerical experiments in Section V verify this convergence behavior.
Proposition 1 guarantees global convergence of PALM starting from any initial point. We next show that PALM converges to a critical point of Φ when the closed-loop performance metric satisfies the Kurdyka-Lojasiewicz (KL) property; see Appendix A for definition.
Lemma 2: If the performance index J in (5) satisfies the KL property, then Φ in (5) satisfies the KL property.
The KL property of Φ established in Lemma 2 allows us to invoke the convergence results in [29].
Proposition 2: Let G k = (K k , C k , F k ) be a sequence generated by Algorithm 1. If the performance index J in (5) satisfies the KL property, then the following results hold.
1) The sequence {G k } has a finite length, that is, 2) The sequence {G k } converges to a critical point G * = (K * , C * , F * ) of Φ. Proposition 2 follows from Lemma 1 and the convergence result for generic PALM; see Theorem 3.1 in [29].
Remark 1 (Comparison with ADMM): The convergence analysis of ADMM typically relies on convexity assumption [31]. As aforementioned, no convexity assumption is required for PALM. Another noteworthy point is that ADMM is primarily used for two-block problems (i.e., two variables with a coupling constraint), while the co-design problem (5) is a three-block problem. It is shown in [32] via a counterexample that direct extension of ADMM for multi-block convex problem may not converge. In contrast, the convergence of PALM for multi-block problems has been established in [29].
Remark 2 (KL property and semi-algebraic functions): While it may not be straightforward to establish the KL property for a given function, it is useful to show the semialgebraic property; see Appendix A for definition. More importantly, a variety of nonsmooth functions that arise in modern applications can be shown KL via the semi-algebraic analysis, for example, all polynomial functions, indicator functions of semi-algebraic sets, finite sums and product of semialgebraic functions, composition of semi-algebraic functions, supremum/infimum functions of semi-algebraic functions. Furthermore, several important sets are semi-algebraic, including the cone of positive semidefinite matrices, Stiefel manifolds, and matrices with constant rank. More details on the KL property and its relation to semi-algebraic functions can be found in [26]- [29].
Remark 3 (Convergence rate): Convergence rate of PALM for nonconvex, nonsmooth problems with KL property is still an on-going research topic. For semi-algebraic problems with special forms, a desingularizing technique has been developed to characterize the convergence rate. Depending on the desingularization parameters of the semi-algebraic functions, PALM converges with a finte number of steps, with a linear convergence rate, or with a sublinear rate [26]. Our numerical experience suggests a linear convergence rate for the co-design output feedback problem; see Section V.

V. NUMERICAL EXPERIMENTS
In this section, we illustrate the convergence property of PALM for the sparse output feedback problem. We consider a mass-spring system with 600 design variables and an unstable system with 60, 000 design variables. For both systems PALM finds sparse solutions with prespecified sparsity levels in a few hundred steps. 1 We take the closed-loop H 2 norm as the performance index with Q = I and R = 10I. PALM is initialized with the state feedback LQR solution and the output matrix whose elements are all ones.

A. Mass-spring system
We consider the mass-spring system with N = 10 masses connected in series. Let x = [ p T , v T ] T where p and v ∈ R N denote the position and velocity of the masses, respectively. The state-space representation is given by where T ∈ R N ×N is a tridiagonal Toeplitz matrix with −2 on the main diagonal and 1 on the first subdiagonal. The total number of unknown variables in C ∈ R 20×20 and K ∈ R 10×20 is 600. We set r = N nonzero columns in C and s = 2N 2 /5 nonzero elements in K. In other words, we take 50% column-sparsity of C and 20% entry-sparsity of K. Figure 1 shows the convergence results of the objective value Φ and the error of variables in consecutive steps As predicted in Proposition 1, the objective value decreases monotonically with the PALM iterations. The errors between two consecutive steps converge fast; in particular, it takes less than 300 iterations to reach e k K = 4.81 × 10 −7 , e k C = 8.30 × 10 −6 , and e k F = 7.07 × 10 −6 . The sparsity patterns of K and C are shown in Fig. 2. Note that only the velocity of the masses is measured. On the other hand, the sparsity pattern of K shows that the velocity of the neighboring masses is used to control the masses. The product F = KC is a column sparse matrix with the same columnsparsity pattern of C. Therefore, one only needs N sensors to measure the velocity of the masses to implement the sparse output feedback controller.

B. Distributed system
We next consider N = 100 identical unstable systems in a square of 10 × 10 units; see Fig. 3. The state-space representation for the i-th system is given bẏ The coupling coefficient α ij is determined by the Euclidean distance between two systems, where p i denotes the position of the i-th system. The total number of unknown variables in C ∈ R 200×200 and K ∈ R 100×200 is 60,000. We consider the co-design problem with 10% nonzero rows in C and 10% nonzero entries in K, in other words, r = 20 and s = 200. Figure 4 shows the convergence results of the objective value Φ and the error of variables in consecutive PALM steps. As in the mass-spring example, Φ is monotonically decreasing with the PALM iterations. It takes less than 500 iterations to achieve e K ≤ 6.6 × 10 −3 , e C ≤ 10 −2 , and e k F ≤ 2.6 × 10 −2 .

Number of inputs
Number of outputs

Number of outputs
Number of states Fig. 2: Sparsity pattern of K with 20% nonzero entries (top) and column-sparsity pattern of C (bottom) for the mass-spring system. Fig. 3: A network of 100 unstable coupled systems randomly distributed in a square. The coupling strength is determined by the distance between two subsystems as in (13). Figure 5 shows the sparsity pattern of K and C. As required, the output matrix C has exactly r = 20 nonzero rows (10% row-sparsity) and the output feedback gain K has exactly s = 400 nonzero entries (10% sparsity).

VI. CONCLUSIONS
We consider the co-design problem of output feedback and output matrix simultaneously. We impose row/columncardinality constraint to guarantee row/column sparsity on the output matrix. We use the cardinality constraint to obtain sparse output feedback gain. The resulting nonconvex, nonsmooth problem is solved by using the PALM algorithm. We show the global convergence of PALM by establishing the Lipschitz conditions of bilinear matrix function. When {u ∈ R d : g ij (u) = 0 and h ij (u) < 0}.
The connection between the KL functions and the semialgebraic functions is provided by the following result.

B. Proof of Lemma 1
Property 1) is a consequence of the coupling function H in (6), the indicator function f in (3) and g in (4), and the performance metric J in Assumption 1. Property 2) follows from the Lipschitz constants derived in (8). To show property 3), L 3 (F ) = γ is a constant throughout the PALM iterations. On the other hand, L 1 (C) in (8) is bounded below for all C. Since C k is the minimizer of a feasible problem over a bounded set, it is bounded above for all k. Hence the entire sequence L 1 (C k ) satisfies the upper and lower bounds in (12). An analogous argument shows that the Lipschitz constant L 2 (K) satisfies (12). Finally, Property 4) is a direct consequence of the twice continuous differentiability of H.

C. Proof of Lemma 2
Since KL functions are stable with respect to summation and since J is assumed to be a KL function, one needs to show that f and g are KL functions. From Proposition 3, we proceed to show that the indicator functions f and g are semialgebraic. To this end, we use the results that the indicator function of the semi-algebraic set {K | card(K) ≤ s} is semialgebraic. This is because the graph of the cardinality function can be represented by a finite union of piecewise linear sets; see [29,Example 5.2]. Similarly, the set of row/column sparsity matrices is also semi-algebraic. Since the indicator function of a semi-algebraic set is semi-algebraic, it follows that f and g are semi-algebraic functions. This completes the proof.

D. Anderson-Moore method
Let J be the closed-loop H 2 norm from the disturbance d to the performance output z. The necessary and sufficient conditions for the optimality of (11) are determined by the following coupled matrix equations [1], [3] 2(RF − B T 2 P )L + c k (F − Z k ) = 0 (14a) When F is fixed, then (14b)-(14c) are two Lyapunov equations in L and P . On the other hand, when L and P are fixed, then (14a) is a Sylvester equation in F . This observation motivates the Anderson-Moore method [3], namely, solving the Sylvester equation for F and two Lyapunov equations for (L, P ) iteratively. The descent property of the new direction in conjunction with the Armijo line-search guarantees convergence of this approach [2]. The Anderson-Moore method is provided in Algorithm 2.

Algorithm 2 Anderson-Moore method
Initialization: Start with a stabilizing F 0 for l = 0, 1, 2, . . . until convergence do Solve (14b)-(14c) to get the solutions (L l , P l ) . Solve (14a) to get the solutionF l . Form the direction ∆F l =F l − F l . Determine stepsize α by using the Armijo rule. Update F l+1 = F l + α∆F l . end for