A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems

This paper presents a proximal bundle (PB) framework based on a generic bundle update scheme for solving the hybrid convex composite optimization (HCCO) problem and establishes a common iteration-complexity bound for any variant belonging to it. As a consequence, iteration-complexity bounds for three PB variants based on different bundle update schemes are obtained in the HCCO context for the first time and in a unified manner. While two of the PB variants are universal (i.e., their implementations do not require parameters associated with the HCCO instance), the other newly (as far as the authors are aware of) proposed one is not but has the advantage that it generates simple, namely one-cut, bundle models. The paper also presents a universal adaptive PB variant (which is not necessarily an instance of the framework) based on one-cut models and shows that its iteration-complexity is the same as the two aforementioned universal PB variants.

Introduction
Let f, h : R n → R ∪ {+∞} be proper lower semi-continuous convex functions such that dom h ⊆ dom f and h − µ · 2 /2 is convex for some µ ≥ 0, and consider the optimization problem It is said that (1) is a HCCO problem if there exist nonnegative scalars M f and L f and a first-order oracle f ′ : dom h → R n (i.e., f ′ (x) ∈ ∂f (x) for every x ∈ dom h) satisfying the (M f , L f )-hybrid condition, namely: The main goal of this paper is to study the complexity of proximal bundle methods for solving the HCCO problem (1) based on different bundle update schemes. Instead of focusing on a particular proximal bundle method, our unified approach considers a framework of proximal bundle methods based on a generic bundle update scheme (referred to as the GPB framework) and establishes a common iterationcomplexity bound for all variants belonging to it.
Method outline. Like all other proximal bundle methods, an iteration of a GPB variant solves the prox bundle subproblem where λ is the prox stepsize, and x c and Γ are the current prox-center and bundle function, respectively. Moreover, it also performs two types of iterations, i.e., serious and null ones. In a serious iteration, the prox-center is updated to x c ← x and the updated bundle function Γ + is chosen so as to satisfy Γ + ≥ ℓ f (·; x) + h where ℓ f (·; x) = f (x) + f ′ (x), · − x . In a null iteration, the prox-center does not change but Γ is updated according to a certain bundle update scheme (which is usually more restrictive than the ones in the serious iterations).
In order to illustrate the use of the generic bundle update scheme, this paper considers three specific well-known bundle update schemes and shows that they can all be viewed as special cases of the generic one. We now briefly describe the specific ones in the next three itemized paragraphs.
(E1) one-cut scheme: This scheme obtains Γ + as where x is as in (2) and τ ∈ (0, 1) depends on (L f , M f , µ). Clearly, if Γ is the sum of h and an affine function underneath f , then so is Γ + .
(E2) two-cuts scheme: Assume that Γ = max{A f , ℓ f (·; x − )} + h where A f is an affine function satisfying A f ≤ f and x − is the previous iterate. This scheme sets the next bundle function Γ + to one similar to Γ but with (x − , A f ) replaced by (x, A + f ) where A + f = θA f +(1−θ)ℓ f (·; x − ) for some θ ∈ [0, 1] which does not depend on (L f , M f , µ).
This scheme obtains Γ + as Γ + = Γ(·; C + ) where C + is the updated bundle set obtained by possibly removing some points from C and then adding the most recent x to the resulting set.
Throughout out the paper, we refer to the GPB variants based on (E1), (E2) and (E3) as 1C-PB, 2C-PB and MC-PB, respectively. Contribution. Regardless of the parameter triple (L f , M f , µ), it is shown that the iterationcomplexity for any GPB variant to obtain aε-solution of the HCCO problem (1) (i.e., a point x ∈ dom h satisfying φ(x) − φ * ≤ε) is for a large range of prox stepsizes λ. Since 2C-PB and MC-PB methods do not rely on (L f , M f , µ), a sharper iteration-complexity bound can be obtained for them by replacing µ and (M f , L f ) in (5) byμ and (M f ,L f ), respectively, whereμ is the largest µ such that h − µ · 2 /2 is convex and (M f ,L f ) is the unique pair which minimizes M 2 f +εL f over the set of pairs (M f , L f ) satisfying the (M f , L f )-hybrid condition of f ′ . Moreover, even though this sharper complexity bound can not be shown for 1C-PB, Section 5 presents an adaptive version of this variant where τ in (3), instead of being chosen as a function of (L f , M f , µ), is adaptively searched so as to satisfy a key inequality condition. Finally, Section 5 also shows that this adaptive variant has the same iteration-complexity as that of 2C-PB and MC-PB. Related literature. Proximal bundle methods are known to be efficient algorithms for solving nonsmooth convex composite optimization (NCCO) problems, i.e., instances of (1) for which there exists M f ≥ 0 such that the hybrid condition holds with L f = 0. Some preliminary ideas towards the development of the proximal bundle method were first presented in [11,23] and formal presentations of the method were given in [12,15]. Convergence analysis of the proximal bundle method for NCCO problems has been broadly discussed in the literature and can be found for example in the textbooks [19,21]. Different bundle management policies in the context of proximal bundle methods are discussed for example in [6,7,9,18,19,22].
Iteration-complexity bounds have been established for some proximal bundle methods in the context of the NCCO problem with µ = 0 (see for example [1,5,9,14]). Papers [1,9] both consider the NCCO problem where h is the indicator function of a nonempty closed convex set, and [5] considers the NCCO problem where h is identically zero. Moreover, paper [9] obtains the first O(ε −3 ) complexity bound, and [1,5] subsequently also derive an O(ε −3 ) bound. On the other hand, a previous authors' paper [14] proposes a proximal bundle variant using a novel condition to decide whether to perform a serious or null iteration which does not necessarily yield a function value decrease. More importantly, [14] establishes the first O(ε −2 ) complexity bound for a large range of prox stepsizes, and shows that the bound is indeed optimal.
More specialized iteration-complexity bounds in the context of the NCCO problem with µ > 0 have also been established for the proximal bundle methods studied in [9,14]. More specifically, papers [5,6] derive an O(ε −1 ) iteration-complexity bound for the proximal bundle method of [9], and [14] also establishes an O(ε −1 ) iteration-complexity bound for its proximal bundle method which, in contrast to the first one, is optimal with respect to the parameter pair (M f , µ) for a large range of prox stepsizes.
The current paper improves [14] in the following aspects: 1) it deals with the more general HCCO problem; 2) in contrast to [14], it nowhere assumes that h is Lipschitz continuous nor imposes any condition on the parameter µ, and shows that the iteration-complexity bound (5) holds for prox stepsize ranges which are larger than the ones in [14]; 3) while the proximal bundle variant of [14] is based on the bundle update scheme (E3), GPB uses a generic bundle update scheme which potentially includes many other schemes presented in the literature (such as (E1)-(E3)) and the unified analysis presented here for GPB applies to all the different proximal bundle variants contained on it; and 4) as far as the authors are aware of, it presents and analyzes for the first time a one-cut proximal bundle method for both NCCO and HCCO problems and also presents a universal variant of such method.
Another method related, and developed subsequently, to the proximal bundle method is the bundle-level method, which was first proposed in [13] and extended in many ways in [3,8,10]. These methods have been shown to have optimal iteration-complexity in the setting of the NCCO problem with h being the indicator function of a compact convex set. Since their generated subproblems do not have a proximal term, and hence do not use a prox stepsize, they are different from the ones studied in this paper. Finally, paper [4] presents a doubly stabilized bundle method for solving NCCO problems whose prox subproblems combine elements from both proximal bundle and bundlelevel methods and analyzes its asymptotic convergence (but not its iteration-complexity).
Organization of the paper. Subsection 1.1 presents basic definitions and notation used through-out the paper. Section 2 formally describes the assumptions on the HCCO problem (1), reviews the constant stepsize composite subgradient (CS-CS) method and discusses its iteration-complexity. Section 3 presents a generic bundle update scheme, describes the GPB framework and states the main results of the paper, namely, the iteration-complexity of GPB. Section 4 contains three subsections, and they provide the analysis of bounds on the number of the serious, null and total iterates, respectively. Section 5 presents the adaptive variant of 1C-PB and establishes the iterationcomplexity of it. Section 6 presents some concluding remarks and possible extensions. Appendix A provides a few useful technical results. Appendix B presents two recursive formulas and their related results. Appendix C provides the proof of the iteration-complexity for the CS-CS method, and describes an adaptive variant of CS-CS and establishes its iteration-complexity. Finally, Appendix D provides the proofs of properties of bundle update schemes (E2) and (E3).

Problem of interest and a review of the CS-CS method
This section consists of two subsections. The first one describes the main problem and the assumptions imposed on it. The second one reviews the CS-CS method and an adaptive variant of it, and describes their iteration-complexity bounds for obtaining aε-solution of the main problem.

Main problem and assumptions
The problem of interest in this paper is (1) which is assumed to satisfy the following conditions for some triple (L f , M f , µ) ∈ R 3 + : (A1) f, h ∈ Conv (R n ) are such that dom h ⊂ dom f , and a subgradient oracle, i.e., a function f ′ : dom h → R n satisfying f ′ (x) ∈ ∂f (x) for every x ∈ dom h, is available; (A2) the set of optimal solutions X * of problem (1) is nonempty; Throughout this paper, an instance of (1) means a triple (f, f ′ ; h) satisfying conditions (A1)-(A4) for some triple of parameters (L f , M f , µ) ∈ R 3 + . We now add a few remarks about assumptions (A1)-(A4). First, the set Ω ⊂ R 2 + consisting of the pairs (M f , L f ) satisfying (A3) is easily seen to be a (nonempty) closed convex set. Moreover, for a given toleranceε > 0, it is easily seen that there exists a unique pair (M f (ε),L f (ε)) which minimizes M 2 f +εL f over Ω and, without any loss of clarity, we denote this pair simply by (M f ,L f ) and define Tε Second, if there exists a pair (M f , 0) satisfying (A3), then the smallest M f with this property is denoted byM f,0 ; otherwise, if no such pair exists, then we setM f,0 := ∞. Third, it is easily seen thatM f,0 ≥ Tε ≥M f and that any one of these two inequalities can hold strictly. For example, if f = · + · 2 /2 and h ≡ 0, then we can easily see thatM f,0 = ∞,M f = 1, and Tε ∈ (1, ∞) for anyε > 0. Fourth, letting then it is well-known that (A3) implies that for every u, v ∈ dom h, In addition to the above quantities, two other ones which are used to express the complexity bounds obtained in this paper are:μ which denotes the largest quantity µ satisfying (A4), and; the distance of a given initial point x 0 to X * , i.e., Finally, for given initial point x 0 ∈ dom h and toleranceε > 0, it is said that an algorithm for solving an instance (f, f ′ ; h) of (1) hasε-iteration complexity O(T ) if its total number of iterations until it obtains aε-solution is bounded by CT where C > 0 is a universal constant.

Review of the CS-CS method
We start by reviewing the CS-CS method. The CS-CS method with initial point x 0 ∈ dom h and constant prox stepsize λ > 0, denoted by CS-CS(x 0 , λ), recursively computes its iteration sequence {x j } according to For any given universal constant C > 1, pair (M f , L f ) satisfying (A3), and toleranceε > 0, it follows from Proposition C.1 with µ =μ that CS-CS(x 0 , λ) with any stepsize λ such that , hasε-iteration complexity given by with the convention that the second term is equal to the first one whenμ = 0. (It is worth noting that the second term converges to the first one asμ ↓ 0.) In order to obtain theε-iteration complexity (11), the CS-CS method requires the knowledge of (M f , L f ) satisfying (A3) to compute a suitable λ. Subsection C.2 presents an adaptive variant of the CS-CS method which does not require such knowledge. More precisely, this adaptive variant starts with any stepsize λ 0 > 0, employs a backtracking procedure to compute a nonincreasing sequence {λ j } such that each λ j satisfies a key condition, and recursively performs iterations similar to (10). It is shown in Proposition C.3 that, without the prior knowledge of Tε, the adaptive variant of CS-CS hasε-iteration complexity given by It is worth noting that bound (12) is better than the one for the CS-CS method (i.e., (11)) due to the fact that it is expressed in terms of the tighter quantity T 2 ε instead of the estimate M 2 f +εL f .

The GPB Framework
This section contains three subsections. Subsection 3.1 describes a generic bundle update scheme that is used to perform the null iterations of a method in the GPB framework. Subsection 3.2 presents the GPB framework and Subsection 3.3 describes the main complexity results about it.

Bundle update schemes
Bundle methods discussed in the literature rely on different bundle management schemes, i.e., schemes for updating the bundle function Γ in (2) which approximates the objective function of (1). Instead of focusing on a specific bundle update scheme, we describe in this subsection a generic scheme which includes most (if not all) of the ones considered in the literature. This subsection also gives the details of the three concrete examples (E1)-(E3) of the generic bundle update scheme. We start by describing the generic bundle update scheme. For a given quadruple (Γ, where x is as in (2), ℓ f (·; x) is as in (7), andΓ ∈ C µ (φ) is such that For the sake of shortness, we denote the class of functions Γ + satisfying the above conditions as C φ (Γ, x c , λ, τ ). Clearly, the above update scheme does not completely determine Γ + but rather gives minimal conditions on it which are suitable for the complexity analysis of this paper. We now elaborate on schemes (E1)-(E3) which are members of the above class.

The GPB framework
This subsection states the GPB framework based on the generic bundle update scheme presented in Subsection 3.1. It also gives several remarks about GPB and discusses how it relates to the classical proximal point method. We start by stating GPB.
An iteration index j for which the inequality t j ≤ε/2 in step 1 is satisfied is called a serious index in which case x j (resp., y j ) is called a serious iterate (resp., auxiliary serious iterate); otherwise, j is called a null index. Moreover, we assume throughout our presentation that j = 0 is also a serious index.
We make some basic remarks about GPB. First, we refer to it as a framework since it does not completely specify how some algorithmic quantities are generated. The framework rather gives minimal conditions on these quantities which enable us to establish complexity bounds for all algorithms contained on it in a unified manner. Second, two possible ways of choosing the bundle function Γ j+1 in a serious update are: 1) Γ j+1 = ℓ f (·; x j ) + h, and 2) Γ j+1 = max{Γ j , ℓ f (·; x j ) + h}. Third, three possible concrete ways of choosing Γ j+1 in a null update have been discussed in (E1)-(E3). Fourth, y j+1 is the best (in terms of φ λ j+1 value) among the set of points {y ℓ 0 , x ℓ 0 +1 , . . . , x j+1 } where ℓ 0 denotes the largest serious index less than or equal to j + 1. Fifth, although GPB does not specify a termination criterion for the sake of shortness, all iteration-complexity bounds established in this paper are relative to the effort of obtaining aε-solution of (1). Finally, although iterationcomplexity bounds for GPB can also be established for other termination criteria (see for example Section 6 of [14]), we have omitted the details of their derivation for the sake of shortness.
We now discuss the role played by the parameter τ of GPB. First, τ is only used in step 1 for determining the class C φ (Γ j , x c j , λ, τ ) where Γ j+1 is chosen from. Second, τ has to be sufficiently close to one, i.e., τ ∈ [τ , 1) whereτ is as in (19). Third, even though some variants do not depend on the scalar τ as mentioned in the above two remarks, the analysis of GPB does. Fourth, 2C-PB and MC-PB do not depend on τ since the updates (E2) and (E3) do not. (Recall the meaning of 1C-PB, 2C-PB and MC-PC given in the sentence following (E3).) Moreover, both of these variants can be viewed as special cases of GPB with τ =τ but since their implementation do not depend on the choice of τ , they do not need to compute or estimateτ . Fifth, on the other hand, 1C-PB requires knowledge of a scalar τ as mentioned in the first and second remarks since the update (E1) depends on τ (see (3)).
We finally briefly argue that GPB can be viewed as an inexact proximal point method for solving (1). Indeed, it is easy to see that m j ≤ m * j ≤ φ λ j (y j ) where m * j := min{φ λ j (u) : u ∈ R n }, and hence that φ λ j (y j ) − m * j ≤ t j in view of (23). Hence, if j is a serious index, and hence t j ≤ε/2, it follows that y j is a (ε/2)-solution of the proximal subproblem min{φ λ j (u) : u ∈ R n }. The sequence of consecutive null iterations between two serious ones can be regarded as an iterative procedure to compute the aforementioned (ε/2)-solution. More details of such an interpretation can be found in Subsection 3.1 of [14].

Iteration-complexity results for GPB
This subsection presents the main complexity results for GPB.
The first complexity result assumes that, in addition to (f, f ′ ; h) being an instance of (1), a triple (L f , M f , µ) satisfying (A1)-(A4) is also known, and derives aε-iteration complexity bound for GPB variants, with a scalar τ obtained from (L f , M f , µ), for a large range of prox stepsizes λ.
and τ is given by then any variant of GPB with input (x 0 , λ,ε, τ ) obtains aε-solution of the above instance in a number of iterations bounded (up to a logarithmic term) by (5).
The corollary below considers the subclass of GPB methods, referred to as the τ -free GPB subclass, which do not depend on τ (and hence do not need τ as input), and derives an improved iteration-complexity bound for it. Since 2C-PB and MC-PB do not depend on τ , the result below applies to both of them.
Corollary 3.2. Let universal constant C > 0, initial point x 0 ∈ dom h, and toleranceε > 0 be given, and consider an instance (f, f ′ ; h) of (1). Then, any variant of the τ -free GPB subclass with input (x 0 , λ,ε) satisfyingε where Tε is as in (6) obtains aε-solution of the above instance in a number of iterations bounded (up to a logarithmic term) by (12).
Proof: Observe that any variant of the τ -free GPB subclass can be viewed as instance of GPB with input τ =τ and µ =μ since it does not depend on neither τ nor µ. Hence, it follows from (12) and Theorem 3.1 with (L f , M f , µ) replaced by (L f ,M f ,μ) that the conclusion of the corollary holds.
For the sake of comparing the results of this paper with the ones obtained in [14], we now state another consequence of Theorem 3.1 in which an alternativeε-iteration complexity for τ -free GPB variants applied to instances of (1) withM f,0 finite. (Recall the definition ofM f,0 is in the line below (6).) Corollary 3.3. Let universal constant C > 0, initial point x 0 ∈ dom h, and toleranceε > 0 be given, and consider an instance (f, f ′ ; h) of (1) such thatM f,0 is finite. Then, any variant of the τ -free GPB subclass with input (x 0 , λ,ε) satisfyinḡ obtains aε-solution of the above instance in a number of iterations bounded (up to a logarithmic term) by Proof: Observe that any variant of the τ -free GPB subclass can be viewed as instance of GPB with input τ = [1 + (1 + λμ)ε/(8λM 2 f,0 )] −1 and µ =μ since it does not depend on either τ or µ. Since the triple (0,M f,0 ,μ) satisfies conditions (A1)-(A4), it then follows from (12) with Tε replaced bȳ M f,0 and Theorem 3.1 with (L f , M f , µ) replaced by (0,M f,0 ,μ) that the conclusion of the corollary holds.
Before comparing the RPB method of [14] with the τ -free GPB variants of the paper, we first make two remarks about the first one in regards to the latter ones. First, the RPB method of [14] with δ =ε/2 can be viewed as a special case of τ -free GPB since: RPB uses the inequality t j ≤ε/2 to decide whether to perform a serious or null update; and, its serious and null updates, the latter of which are based on (E3), fulfill the requirements of step 1 of GPB (see Lemma D.1). Second, while the RPB method of [14] deals with instances of (1) such thatM f,0 is finite (i.e., the nonsmooth setting), the analysis presented in this paper for τ -free GPB applies to the larger class of instances of (1) such that Tε is finite (i.e., the hybrid or smooth/nonsmooth setting).
We now compare Corollary 3.3 of this paper with Corollary 3.2 of [14]. Indeed, it follows from Corollary 3.2 of [14] with (M f , µ) = (M f,0 ,μ) that RPB hasε-iteration complexity given by (28) as On the other hand, Corollary 3.3 of this paper establishes complexity bound (28) for any λ lying in the larger range (27) without imposing any condition onμ.
We now compare Corollary 3.3 of this paper with Corollary 3.3 of [14]. Indeed, it follows from Corollary 3.3 of [14] with M f =M f,0 that RPB hasε-iteration complexity O 1 ((M f,0 ) 2 d 2 0 /ε 2 ) as long (27) holds and h is (CM f,0 )-Lipschitz continuous. On the other hand, Corollary 3.3 of this paper establishes the (possibly sharper)ε-iteration complexity (28) for any λ in the same range without imposing any condition Lipschitz continuity on h.

Complexity Analysis of GPB
This section consists of three subsections. The first one provides a bound on the number of serious iterates generated by the GPB framework. The second one derives a preliminary complexity bound on the number of possible consecutive null iterates. Finally, the last subsection combines the aforementioned bounds to obtain a complexity bound on the total number of iterations performed by any algorithm in the GPB framework with prox stepsize λ arbitrarily chosen. Moreover, it also provides the proof of Theorem 3.1 as a consequence of this general complexity result.

Bounding the number of serious iterates
We start by introducing some notation and definitions. Let 0 = j 0 < j 1 < j 2 < . . . denote the serious indices of the GPB framework, and definex 0 := x 0 ,ŷ 0 := x 0 and x k := x j k ,ŷ k := y j k ,Γ k := Γ j k ,m k := m j k for every k ≥ 1.
The following result summarizes the basic properties of the above "hat" entities that follow as an immediate consequence of their definitions and the description of the GPB framework. It is worth noting that the complexity results developed in this subsection apply not only to the sequences defined in (29), but also to arbitrary sequences {x k }, {ŷ k } and {Γ k } satisfying the basic properties stated below.
Lemma 4.1. The following statements about GPB hold for every k ≥ 1: is the pair of optimal solution and optimal value of c) there holds φ(ŷ k ) −m k ≤ε/2.

Proof:
We first note that the definition ofx k in (29) and the prox-center update policy in step 2 of GPB imply thatx a) This statement directly follows from the definition ofΓ k in (29) and the fact that Γ j k ∈ C µ (φ). b) It follows from both (20) and the first identity in (23) with j = j k − 1, and relations (29) and (30) that b) holds. c) Since j k is a serious index, we have t j k ≤ε/2. Using this conclusion, (29) and the definitions of t j and φ λ in (23) and (22), respectively, we conclude that and hence that c) holds. It is worth noting that a), b), and c), can be viewed only as properties about the sequences {Γ k } and {ŷ k }, and the initial pointx 0 , since {x k : k ≥ 1} is uniquely determined by {Γ k }.
The next result provides an important recursive formula for the sequences in (29) and derives some important consequences that follow from it. Lemma 4.2. Let u ∈ dom h be given and define Then, the following statements hold: a) for every k ≥ 1, we have Proof: a) It follows from Lemma 4.1(a) and the definition of C µ (φ) thatΓ k is µ-convex, and hence that the objective function in Lemma 4.1(b) is (µ + 1/λ)-strongly convex. Using this observation, Lemma 4.1(b) and Theorem 5.25(b) of [2] with f =Γ k + ·−x k−1 2 /(2λ), x * =x k and σ = µ+1/λ, we have for the given u ∈ dom h and every k ≥ 1, Using the above inequality, Lemma 4.1(c), and the fact that Lemma 4.1(a) and the definition of C µ (φ) imply thatΓ k ≤ φ, we conclude that and hence that a) holds. b)-c) Since (32) satisfies (58) with it follows from Corollary B.2, the fact thatx 0 = x 0 and the definition of λ µ in (19) that b) and c) hold.
We are now ready to present the main result of this subsection which provides a bound on the number of serious iterates generated by GPB until it obtains aε-solution of (1). Proposition 4.3. The number of serious iterations K performed by GPB until it obtains for the first time an auxiliary serious iterateŷ K such that φ(ŷ K ) − φ * ≤ε is bounded by where λ µ is as in (31). Moreover, Proof: Lemma 4.2(b) with u = x * 0 and the definition of d 0 in (9) imply the first conclusion of the proposition, and hence that K − 1 ≤ d 2 0 /(λε). This conclusion, together with Lemma 4.2(c) with u = x * 0 , then implies (34). We note that Proposition 4.3 holds for any µ ∈ [0,μ] and λ > 0.

Bounding the number of consecutive null iterates
We assume throughout this subsection that ℓ 0 denotes an arbitrary serious index (and hence ℓ 0 is possibly equal to zero) and let B(ℓ 0 ) denote the set of all consecutive null indices j ≥ ℓ 0 + 1. Our goal in this subsection is to show that the set B(ℓ 0 ) is finite and bound its cardinality in terms of (M f ,L f ), λ,ε, d 0 and τ ∈ [τ , 1) whereτ is as in (19).
We start by making some simple observations that immediately follow from the description of GPB. For any j ∈ B(ℓ 0 ), it follows from the prox-center update policy of x c j+1 in step 2 of GPB that x c j = x ℓ 0 , and hence that in view of the definitions of Γ λ j and φ λ j in (20) and (22), respectively. We now make a few immediate observations that will be used in the analysis of this subsection. First, since (35) implies that the function φ λ j remains the same whenever j ∈ B(ℓ 0 ) and ℓ 0 remains fixed throughout the analysis of this section, we will simply denote the function φ λ j for j ∈ B(ℓ 0 ) by φ λ , i.e., Moreover, we define ℓ φ (·; x) := ℓ f (·; x) + h where ℓ f (·; x) is as in (7), and Second, in view of the definition of y j in (21) and the above relation, it then follows that Third, ℓ 1 is characterized as the first index j > ℓ 0 satisfying condition (23). The next result presents a few basic properties of the auxiliary bundle functionΓ j which is useful in the analysis.
b) It follows from the fact thatΓ j ∈ C µ (φ) and the definition of C µ (φ) thatΓ j + · −x ℓ 0 2 /(2λ) is λ −1 µ -strongly convex in view of (19). Using (40) and Theorem 5.25(b) of [2] with f =Γ j + · −x ℓ 0 2 /(2λ), x * = x j and σ = λ −1 µ , we have for every u ∈ dom h, The statement now follows from the above inequality and the definition of m j in (23). The following technical result provides an important recursive formula for {m j } which is used in Lemma 4.6 to give a recursive formula for {t j }. It is worth observing that its proof uses for the first time the condition that τ is chosen in the interval [τ , 1) whereτ is as in (19).
Proof: Using (8) with (M f , L f , u, v) = (M f ,L f , x j+1 , x j ), and the definitions of φ λ and ℓ λ φ in (37) and (38), respectively, we have This inequality, together with Lemma 4.5 and the fact that m j = φ λ (y j )−t j (see (23)), then implies where the last inequality is due to (21), (37) and the inequality a 2 −2ab ≥ −b 2 with a = 2M f x j+1 − x j and b =ε/2. The lemma now follows from the above inequality and the definition of t j+1 in (23). The next lemma gives a uniform bound on t ℓ 0 +1 which is used in Proposition 4.8 to derive a uniform bound on the maximum number of consecutive null iterates generated by GPB. Its proof uses Lemma A.3 in Appendix A where a crucial bound on x ℓ 0 − x ℓ 0 +1 is obtained.
Proof: Using both (21) and (23) with j = ℓ 0 , and the facts that φ = f +h and Γ ℓ 0 +1 ≥ ℓ f (·; x ℓ 0 )+h (see the serious update in step 1), we have where the third inequality is due to (8) with , and the last inequality is due to the fact that 2ab ≤ a 2 + b 2 for every a, b ∈ R. The conclusion of the lemma now follows from the above inequality and Lemma A.3 in Appendix A.
We are now ready to present the main result of this subsection where a bound on |B(ℓ 0 )| is obtained in terms of τ ,t andε.
wheret is as in (42) and τ is as in step 0 of GPB.
Proof: Using the inequality τ ≤ e τ −1 , and Lemmas 4.6 and 4.7, we then conclude that for every j ∈ B(ℓ 0 ), Using this observation, and noting that step 1 of GPB and the definition of B(ℓ 0 ) imply that t j >ε/2 for every j ∈ B(ℓ 0 ), it is now easy to see that the conclusion of the proposition follows.

The total iteration-complexity of GPB
This subsection establishes the total iteration-complexity of GPB. We start by providing a more general version of Theorem 3.1 which does not impose any condition on λ. Proposition 4.9. Let input quadruple (x 0 , λ,ε, τ ) ∈ dom h × R ++ × R ++ × [τ , 1] be given. Then, any variant of GPB with input (x 0 , λ,ε, τ ) obtains aε-solution of the above instance in a number of iterations bounded (up to a logarithmic term) by wheret is as in (42). Moreover, if τ is as in (25), then the total iteration-complexity becomes Proof: It follows from Propositions 4.3 and 4.8 that the first conclusion holds. Using bound (43) with τ as in (25), we conclude that the second conclusion holds.
Proposition 4.9 allows us to make one additional remark about Theorem 3.1, namely, in the unusual case where the range of λ (26) is empty, i.e., C 2 (M 2 f +εL f )d 2 0 /ε 2 < 1, it can be easily seen that (44), up to a logarithmic term, reduces to O([κ , which shows that the instances of (1) for which (26) does not hold can be trivially solved by GPB with a proper choice of the prox stepsize.
We are now ready to prove Theorem 3.1. Proof of Theorem 3.1 Defining and using (44), we conclude that O((a + 1)(b + 1)) is aε-iteration complexity bound for GPB up to a logarithmic term. We break the proof into two cases: 1) µ ≤ C(M 2 f +εL f )/ε 2 ; and 2) µ ≥ C(M 2 f +εL f )/ε 2 . First, assume that case 1 holds. Using the definition of λ µ in (19), the fact that µ ≤ C(M 2 f + εL f )/ε 2 , and the first inequality in (24), we have and hence a ≥ 1/(2C). Moreover, it follows from the definition of b in (45) and the second inequality in (24) that Using the fact that log(1 + t) ≥ t/(1 + t) for every t > 0, we easily see that log(1 + t) ≥ t/2 if t ≤ 1 and log(1 + t) ≥ log 2 > 0 if t ≥ 1. This observation with t = λµ/C and the definition of λ µ in (31) then imply that and hence that b ≥ min{1/(2C), log 2}. This inequality and the fact that a ≥ 1/(2C) imply that O((a + 1)(b + 1)) is equal to O(ab + 1). Using this observation, the definitions of a and b in (45), and the fact that λ µ ≤ λ, we then conclude that the bound O((a + 1)(b + 1)) reduces to (5), and hence that the theorem holds for case 1. Assume now that case 2 holds. Then, it follows from the definition of λ µ in (19) and the first inequality in (24) that The first inequality then implies that a ≤ 1/C in view of the first identity in (45), and hence that O((a + 1)(b + 1)) is O(b + 1). We will now derive a bound on b. Indeed, using the definitions of b and λ µ in (45) and (19), respectively, we have where the inequality is due to the second inequality in (48) and the first inequality in (24). Hence, the bound O(b + 1) becomes Finally, it is easy to see that bound (5) becomes the above bound when µ ≥ C(M 2 f +εL f )/ε 2 , and hence that the theorem holds for case 2.
It is worth pointing out how condition (24) on the prox stepsize is used in the proof of Theorem 3.1. Indeed, the first inequality in (24) is used to obtain the inequality in (46), the last inequality in (48), and the inequality in (49), while the second inequality in (24) is used to obtain (47).

A One-Cut Adaptive Proximal Bundle Method
This section presents an adaptive version of the 1C-PB method, referred to as the 1C-APB method which, in contrast to 1C-PB, does not require the availability of a triple (L f , M f , µ) satisfying (A3) and (A4), and which has the sameε-iteration complexity as described in Corollary 3.2 for an arbitrary τ -free GPB variant.
We start by stating the 1C-APB method.
We now make some remarks about the 1C-APB method. First, in contrast to the GPB framework which does not specify how some quantities are generated, 1C-APB is a well-determined method since it specifies Γ j+1 in both the serious and null updates, the latter of which computes Γ j+1 based on the one-cut bundle update scheme (E1). Second, the iteration count j is only increased in step 4 and when that happens the key inequality is satisfied. Before that happens, 1C-APB can loop a few times between steps 2 and 4 and, in the process, computes intermediate quantities which depends on τ and (with some abuse of notation) are all denoted by Γ j+1 , x j+1 , y j+1 , m j+1 and t j+1 . Third, since τ 0 = 0 <τ , it may happen that many τ j 's (possibly even the last one) will also be less thanτ . Hence, 1C-APB can not be viewed as a special case of GPB since the latter one requires its constant τ to be greater than or equal tō τ .
The following lemma summarizes some basic properties of the sequence {τ j } generated by 1C-APB. b) if ℓ 0 is a serious index of the 1C-APB method, then the next serious index ℓ 1 happens and satisfies where λμ := λ/(1 + λμ), and Tε andt are as in (6) and (42), respectively.
Proof: a) It follows from the way τ is updated in step 4 that 1 − τ + = (1 − τ )/2 where τ + is the updated τ . It follows from Lemma 4.6 that if τ j ≥τ then τ ℓ = τ j for every ℓ > j. Using the above two observations, we then easily conclude that the number of times τ changes is bounded by ⌈log (1/(1 −τ ))⌉. The conclusion in b) now follows from the last conclusion and the definition ofτ in (19). b) It follows from Lemma 5.1 that for every j ∈ B(ℓ 0 ), Using the inequality above, the fact that t ℓ 1 ≤ε/2 (see Lemma 5.1(b)) and Proposition 4.8, we conclude that The above inequality, the fact that λμ := λ/(1 + λμ) and the definition ofτ in (19) immediately imply b). We now discuss theε-iteration complexity of 1C-APB.
Proof: First, the same analysis as in Subsection 4.1 shows that the number of serious iterations of 1C-APB is bounded by (33) with µ =μ. Hence, this conclusion and Proposition 5.2(b) imply that theε-iteration complexity for 1C-APB is given by (52). Letting a = λμT 2 ε /ε and b be as in (45), and using (52), we have O((a + 1)(b + 1)) is theε-iteration complexity for 1C-APB up to a logarithmic term. Using the assumption (26) and following a similar argument as in the proof of Theorem 3.1, we conclude that theε-iteration complexity for 1C-APB is (up to a logarithmic term) given by (12).
We end this section by discussing the complexity of 1C-APB in terms of the total number of resolvent evaluations of ∂h, i.e., an evaluation of the point-to-point operator (I + α∂h) −1 (·) for some α > 0. Observe first that the computation of x j+1 in step 3 of 1C-APB requires one resolvent evaluation of ∂h due to (20) and the fact that Γ j+1 has the form (15). Hence, the total number of resolvent evaluations of ∂h is bounded by the sum of the total number of iterations performed by 1C-APB and the total number of times τ is updated. Thus, it follows from Theorem 5.3 and Proposition 5.2(a) that the total number of resolvent evaluations of ∂h is bounded by the sum of (52) and (51). Since (52) is larger than (51), we then conclude that the total number of resolvent evaluations of ∂h is on the order of (52).

Concluding Remarks
We briefly discuss the relationship between GPB variants and other methods. First, it is worth noting that the 1C-PB method has slight similarity with the dual averaging (DA) method of [17] since both methods explore the idea of aggregating cuts into a single one. However, there are essential differences between the two methods: 1) DA uses a fixed prox-center throughout the process, while 1C-PB updates prox-centers during its serious iterations; and 2) DA uses variable prox stepsizes, while GPB uses constant ones. Second, the CS-CS method can be viewed as a special instance of any GPB variant with a relatively small prox stepsize.
We finally discuss some possible extensions of our analysis in this paper. First, throughout the paper, we assume f is convex and h is µ-convex. A natural question is whether, under the weaker assumption that φ is µ-convex, which includes the case where f is µ f -convex, h is µ h -convex and µ = µ f + µ h , the results are still valid for GPB directly applied to the HCCO problem (1). The advantage of this approach, if doable, is that it would not require the knowledge of µ f . Second, theε-iteration complexity of GPB is optimal in the nonsmooth case, however it is not optimal in the hybrid case. It would be interesting to design a variant of GPB which incorporates Nesterov's acceleration scheme and then show that it is optimal for HCCO problems. Third, proximal bundle methods have not been studied in the context of stochastic subgradient oracles, and hence it is interesting to investigate such methods by using the techniques developed in this paper. which in turn, in view of the facts that φ(w ℓ 0 ) ≥ φ * = φ(x * 0 ) and µ ≥ 0, and the inequality (a + b) 1/2 ≤ a 1/2 + b 1/2 for any a, b ≥ 0, yields This inequality and the triangle inequality then imply that where the last inequality is due to (34) and the fact that x ℓ 0 is equal to one of serious iterateŝ x k preceding the last one generated by GPB. On the other hand, since 0 <λ < λ and Γ ℓ 0 +1 ∈ Conv (R n ), it follows from Lemma A.1 with (Γ, x) = (Γ ℓ 0 +1 , x ℓ 0 ) that This inequality together with (56) and the fact that λ/λ = max{1, 2λL f } clearly implies (55).

B Useful recursive formulas
The following two technical results play important roles in the complexity analysis of both GPB and CS-CS. We start by stating the following simple result for general sequences of nonnegative scalars.
Proof: Multiplying (57) by Θ j−1 and summing the resulting inequality from j = 1 to k, we have Hence, the lemma holds. The next result discusses a special case of the previous lemma in which θ j = θ and δ j = δ for every j ≥ 1.
Then, the following statements hold: Proof: a) This statement directly follows from the description of A-CS. b) Using (8) with (M f , L f , u, v) = (M f ,L f , x j+1 , x j ) and the inequality that a 2 + b 2 ≥ 2ab for a, b ∈ R, we have where the last inequality is due to the assumption that λ j ≤ε/(4T 2 ε ). Hence, (61) holds with λ j+1 = λ j . c) This statement clearly follows from steps 2 and 3 of A-CS. d) This statement follows trivially from b) and c), and the way λ is updated in step 2.
Using the same reasoning but with Γ replaced byΓ, we conclude that the above set is also ∂Γ(x), and hence that 1 where the inclusion is due to (2). Now the second identity in (14) immediately follows. As a consequence, we conclude that Γ + ∈ C φ (Γ, x 0 , λ, τ ) in view of its definition in Subsection 3.1.


A Formal Verification Method of Compilation Based on C Safety Subset

With the rapid increase in the number of wireless terminals and the openness of wireless networks, the security of wireless communication is facing serious challenges. The safety and security of computer communication have always been a research hotspot, especially the wireless communication that still has a more complex architecture which leads to more safety problems in the communication system development. In recent years, more and more wireless communication systems are applied in the safety-critical field which tends to need high safety guarantees. A compiler is an important tool for system development, and its safety and reliability have an important impact on the development of safety-critical software. As the strictest method, formal verification methods have been widely paid attention to in compiler verification, but the current formal verification methods have some problems, such as high proof complexity, weak verification ability, and low algorithm efficiency. In this paper, a compiler formal verification method based on safety C subsets is proposed. By abstracting the concept of C grammar units from safety C subsets, the formal verification of the compiler is transformed into the verification of limited C grammar units. In this paper, an axiom system of first-order logic and special axioms are introduced. On this axiom system, the semantic consistency verification of C grammar unit and target code pattern is completed by means of theorem proving, and the formal verification of the compiler is completed.

Introduction
With the rapid development of wireless communication technology, a wireless communication system has been widely used in various fields of national economy and national defense construction. An important part of all kinds of safety-critical systems and software have more and more complex internal structures and open application environments. These factors make people pay more attention to its safety and reliability. Therefore, it is very important to analyze, design, and verify the safety-critical software, especially the onboard software of large passenger aircraft.
At present, the certification standard mainly adopted in the aviation field is DO-178B [1], "Software Requirements in the Certification of Airborne Systems and Equipment", issued by the American Aeronautical Radio Commission (RTCA) in December 1992. DO-178B defines the design and development process for airborne software and describes the target traceability process. According to the impact on aircraft failure state, airborne software is classified into five software grades: A (catastrophic), B (serious), C (heavy), D (light), and E (no impact). The DO-178C was released by RTCA in 2012 [2]. DO-178C complements DO-178B in four aspects: software tool verification, model-based development and verification, object-oriented programming, and formal methods. With the rapid development of new software technologies, these additions and revisions are well adapted to the current process of safety-related software development.
Compiler, as an important tool in software development process, is the bridge between software design and hardware operation. How to ensure the correctness of compiler compilation process is an important problem in software development. The traditional method to detect compilation errors is to conduct a lot of tests, but the tests can only prove that the software is wrong but cannot prove that the software is error-free. In recent years, formal verification methods have received continuous attention in compiler verification. The formal verification method is based on strict mathematical theory, and the software system and properties are regulated by logical methods. Through the formal system composed of axioms and inference rules, the software system is proved in the same way as the theorem proved in mathematics. At present, there are two mainstream methods for formal verification of compilers. One is model detection [3], whose main bottleneck is state explosion, so it is only suitable for analysis of systems with limited and small state space. The other is theorem proving technology [4]. At present, a better way of proving is to use the unified framework of programming and proving, such as PVS, Coq, and Isabelle. Its limitation lies in that it requires tool users to have a high theoretical foundation and technical background, which limits the learning and application of most programmers.
This paper proposes a compiler formal verification method based on secure C subset. By introducing MISRA-C [5], the automotive manufacturing embedded C coding standard, the C language used in safety-critical systems is restricted. The C language defined by this specification is considered to be readable, reliable, portable, and easy to maintain. Combined with the characteristics of MISRA-C and aerospace software, a series of programming criteria of C language software are redefined, and a C safety subset is formed. The C safety subset strictly requires the maturity and stability of the compiler. The compiler must truly reflect the structure and semantics of the source code for comparison and tracking before and after compilation. From the C safety subset, a finite C grammar unit can be obtained, and the source program can be identified by the push-down automata corresponding to the grammar unit. A correct source program must conform to the rules of the grammar unit. Therefore, the proof of the correctness of the compilation process of the source program can be transformed into the proof of the equivalence of the semantics of the grammar unit. This method greatly simplifies the problems of the traditional formal verification methods, such as the high complexity and long time of the proof.

Related Works
The study of theorem proving for programs began in the 1960s with the papers published by Hoare and Floyd [6]. In his paper, Hoare proposed a formal system called Hoare logic. In Hoare logic, there is a set of proof rules called Hoare rules. Hoare logic can be used for machine proof because Hoare rule can be used for formal proof of some correctness assertions.
Separation logic is an extension of Hoare logic, which eliminates the possibility of sharing by providing logical connectives to express separation and corresponding deduction rules, and can describe the properties and related operations of memory in a natural way in the process of calculation, thus simplifying the verification of pointer programs. Separate logic has been proven to be more verifiable, which is a big step forward in program verification and inference technology.
In recent years, the representative one is the work of the COMPCERT project team led by Leroy X [7,8]. For the first time, they have completed the formal verification of the correctness of a complete and practical compilation process. The whole verification process is completely formalized and automatically generated by the machine. To support automatic formal verification, CompCert uses the Coq Assistant, an auxiliary theorem proving tool, to restructure the compilation process. The entire process consists of conversions between eight different intermediate languages, and then, the Coq Assistant is used to prove the correctness of the entire compilation process, i.e., semantic retention. At present, the CompCert compiler can only realize compilation verification for a subset of C language, and it cannot fully cover all C language elements. Moreover, the back-end optimization degree is relatively low, and the project is still under further study [9].
In 2011, Yang et al. [10] tested mainstream C compilers in their research work on CSmith, an automatic test case generation tool, and reported 325 previously unknown bugs to compiler developers, including famous Intel CC, GCC, and LLVM compilers. CompCert performed exceptionally well in all 11 C compilers it compared, not finding any wrong-code errors in its supported C subsets.
The most influential work in recent years is that Comp-Cert puts forward a safe subset Clight in the compiler researched and developed. By adding ultralong types, variable-length parameters, and other features, and adding a safe subset in the front end of the compiler to analyze and trim unnecessary language features in the front end, the compiler complexity of the language is reduced. The range between the standard C (C90), Clight, and MISRA-C safety subsets is shown in Figure 1.
As shown in Figure 1, the C90 covers the latter two, being the first standard C specification to add a true standard library, new preprocessing commands and features, function prototypes that allow for function declarations, and new keywords for specifying parameter types. There is a large intersection between Clight and MISRA-C, but some of them are not covered by each other. This has the very important instructive significance to the future work. Part 1 represents the C language features included in the declaration definition, layout writing, branch control, pointer use, jump control, operational processing, and other parts that are not supported by MISRA-C. Part 2: the intersection of the C language subset supported by Clight and MISRA-C, including C language basic types, syntax, statements, and library functions. Part 3: restricted multiple label declaration, null switch language use, parameter pointer use, pointer nesting, and so on stipulated by MISRA-C are included in it. Part 4: this region is the point not covered by the two subsets, and it is the C language features such as extralong data type, triplet sequence, special type of structure, general representation of floating-point type, special definition of precursor volume, and special arithmetic library function, which are clearly defined in C90 standard.
After the investigation of related researches, it is found that the research content of safety C compilation mainly includes two aspects: the correctness of the design and 2 Wireless Communications and Mobile Computing function of compilation, which ensures the correctness of the compiled object and the correctness of the compilation process itself, and thus guarantees the compilation security to a certain extent obviously; the security of the compiled object is the premise, and the security of the compiler itself is the ultimate goal. Both of them are purposes and motivations of each other, and together constitute the research contents of safety-critical compilation. The conclusions of the objects studied in this paper are shown in Table 1.

Formal Verification Method of Complication
3.1. Safety C Grammar Unit and Semantics. Abstract Syntax Tree Code (ASTC) is a tree representation of the abstract syntax structure of the source code, with each node on the tree representing a syntax structure in the source code. The source program and its corresponding abstract syntax tree are essentially equivalent, and the abstract syntax tree contains all the semantic information of the source program, so the verification of the source program can be transformed into the verification of the abstract syntax tree. From the definition of the tree, we can know that each tree is recursively defined by its subtree, so we can verify the whole grammar tree by verifying the subtree of the grammar separately Under the constraints of the C safety subset, the unsafe syntax specifications in C language, such as Pointers, are removed. Abstract and induction of the abstract syntax tree, we can get some common subsyntax tree structure, these subsyntax tree structures were extracted and restored to the form of C language, and we get the C grammar unit. Compilation verification of the source program is equivalent to verification of each C grammar unit, which can be achieved by verifying whether the semantics of each C grammar unit and the corresponding target code pattern are consistent before and after compilation.
In order to obtain the semantics of each C grammar unit, this paper introduces the concept of context, which can define the semantics of grammar unit according to context. Context represents the environment and context of each proof item in the sequence to be proved, including function local variables, global variables, and context. Table 2 shows some of the C grammar units and their corresponding semantics.
In the table, the sigma symbol σ represents the process of taking a value, and σ(<LOG-EXP>) represents the value of a logical expression that, according to the C safety subset specification, can only be 0 and 1. <STA-LIST> represents a statement block, which can include expression statement and conditional selection statement, and is generally handed over to the push-down automaton that identifies the state-ment block for recursive processing. <ASS-EXP> represents an assignment statement that returns the value of the expression. "{..} * * n" represents the statement inside the braces of the loop execution, which defines the semantics of the loop statement. SKIP means to jump directly to the next statement for execution. Under the 32-bit Power PC instruction set, define SKIP equals σðPC = PC + 4Þ, where PC represents the program counter.
3.2. The Denotational Semantics of Target Language. The denotational semantics is the science of annotating the semantics of a definite formal language with corresponding mathematical objects (such as set and function) using the formal system method. The denotational semantics can also be explained as follows: there are two domains, one is the linguistic domain, in the grammatical domain defines a formal language system. The other is the mathematical domain (or formal system with known semantics). Within the scope of a 32-bit Power PC instruction set, this paper models assembly instruction and obtains corresponding the denotational semantics according to the operational semantics of each instruction given in the official Power PC document. Table 3 gives the denotational semantics of some Power PC assembly instructions.
In the table, the GPR (general-purpose register) represents the Power PC's general-purpose register, mainly used as a stack pointer, the first argument to a function, the return value, etc. CR (Conditional Register) is a condition register, which can reflect the results of some operations (such as CMP instruction) and assist in testing and execution of branch instructions. MEM is a memory space that stores the values of local, global, and other variables. @target represents the relative address, which is generally used in the jump instruction. PC = PC + @target means to jump from the address currently pointed by PC to the address identified by the target. PC = PC + 4 means to directly execute the next instruction.

Target Code Patterns and Propositions.
Target code pattern is a generalized representation of target code sequence obtained by compiling C grammar units in a certain context with GCC compiler and eliminating the influence of context on the target code sequence. Formal verification of compiler should be converted into semantic consistency verification of C grammar unit and target code pattern. Table 4 shows the target code patterns corresponding to some C grammar units under the 32-bit Power PC instruction set.
Formal proof of a program requires a specific system of axioms as the basis. The axiomatic system is to axiomatize a scientific theory and study it with axiomatic methods. Every scientific theory is a system composed of a series of concepts and propositions. Based on the referential semantics of Power PC assembly instruction in 2.2, the proposition mapping algorithm in 3.1 can be used to obtain the proposition of each target code pattern. The propositions of target code patterns about the condition statement (<if-statement>) and loop statement (<while-statement>) are given in Table 5.

Verification and Proof.
The formal verification method proposed in this paper is based on the axiom system of

Wireless Communications and Mobile Computing
first-order logic. Starting from the axioms given in the axiom system in advance (such as the target code pattern proposition), a series of new propositions are deduced according to the inference rules and are added as the premise in the subsequent proof process. Since every item in the proof sequence is a premise, an axiom, or a theorem, and because the axiom system of first-order logic is reliable, every item in the proof sequence must be correct, so that the final inference proves the sequence must be correct.
The MP (Modus Ponens) rule, which is called detached argument or detached rule, is the most basic reasoning rule in the axiom system of first-order logic. The MP rule can be expressed as follows: The implication is as follows: if p is true, then q is true, and then p is true, therefore q is true. The separation rule consists of three statements (or propositions, or statements): the first statement is a conditional statement, i.e., p implicates q; the second statement is p, the premise of the conditional statement is true. The q follows from the first two statements that the conclusion of the conditional statement must also be true logically.
The CI (Conjunction Introduction) rule is called the Conjunction Introduction or combination rule. CI rule can be expressed as follows: A safe subset is proposed, which can reduce the complexity of compilation by adding extralong types, variable-length parameters, and other features in the front end without changing the C semantics.
The coverage range is smaller than that of C90 standard, and MISRA-C standard is not covered, and the accuracy of detection and analysis is not complete.

Correctness of function
From C to ASM It supports automatic formal proof and reconstructs the compilation process in Coq and completes the compilation from a structured functional language Clight to assembly code PowerPC. Finally, it proves the correctness of the whole compilation process by using Coq.
In the process, it has experienced compilation between eight different intermediate languages, and the language changes are complex. The project is still in progress.

Formal verification
Model checking High degree of automation, error detection can be given after the counterexample. State space explosion problem.
Theorem proving Using rigorous mathematical reasoning to prove clear attribute requirements and clear correctness standards, high credibility.
The degree of automation is low, the degree of formalization requirements is high, and the proof process is difficult.
Its meaning is as follows: if p, q is true, then p ∧ q is true. The rule of conjunction is mainly used to convert multiple true propositions into a single one.
In the actual verification process, for the target code mode propositions such as expression grammar unit and conditional choice grammar unit, because they do not contain cyclic structure, it is convenient to complete the reasoning proof of propositions by using MP rule and axiom set and theorem set in the axiom system of first-order logic. However, for cyclic structure, such as <While-Statement> target code pattern proposition, after direct reasoning, the semantics of the target code pattern obtained is quite different from the semantics of the C grammar unit, so it is impossible to directly prove that the semantics of the two are consistent. Therefore, this paper introduces the limited mathematical induction method to prove the target code pattern proposition of cyclic structure.
The logical basis of limited mathematical induction is the axiom of natural numbers, also known as Peano's axiom. General mathematical induction logic expressions for the P ð0Þ⋀ð∀nÞ ðPðnÞ ⟶ PðsðnÞÞ ⟶ ð∀nÞ PðnÞ, limited mathematical induction is on the basis of general mathematical induction, limit n is poor, the program for loop structure, the loop is terminated, and termination conditions are given by the people. Table 6 and Algorithm 1 will give the proofs of the target code pattern propositions of <if-statement> and <while-statement>, respectively.
In Table 6, the final inference of the proof sequence is S12, and the semantics of the target code pattern obtained by the value (σ) operation on S12 are as follows: Combined with the semantics of <if-statement> in Algorithm 1, it can be seen that the semantics of the two are consistent, which is verified.
The inference of <while-statement> proof sequence is the same as that of <if-statement>, the proof sequence is directly derived here, and the proof sequence is proved by finite mathematical induction combining with the semantics of the grammar unit.

Formal Verification Algorithm
4.1. Proposition Mapping Algorithm. The function of the propositional mapping algorithm is to transform the object code pattern into the form of propositions, so as to facilitate subsequent reasoning proof. The algorithm needs to take the referential semantics corresponding to each instruction in the Power PC instruction set as the special axiom input, traverse the input object code pattern one by one, transform each object code into the corresponding form of referential semantics, and finally express the referential semantics of the object code pattern into the form of proposition set  .L1: <STA-LIST> <LOG-EXP> cmpi 7,0,0,0 bne 7,.L1

Wireless Communications and Mobile Computing
<for-statement> .L2: <LOG-EXP> cmpi 7,0,0,0 bne 7,.L1 Wireless Communications and Mobile Computing Proof Inference S1 = GPR 0 ½ = <LOG-EXP > P1 It can be obtained that the semantics of the two are consistent, so it is true when k = 1.
From (1), (2) and (3), it can be seen that the propositions to be verified are valid and have been verified.