Eloïse Berthier

Justin Carpentier

Alessandro Rudi

Francis Bach

INFINITE-DIMENSIONAL SUMS-OF-SQUARES FOR OPTIMAL CONTROL

We introduce an approximation method to solve an optimal control problem via the Lagrange dual of its weak formulation. It is based on a sum-of-squares representation of the Hamiltonian, and extends a previous method from polynomial optimization to the generic case of smooth problems. Such a representation is infinite-dimensional and relies on a particular space of functions -a reproducing kernel Hilbert space -chosen to fit the structure of the control problem. After subsampling, it leads to a practical method that amounts to solving a semi-definite program. We illustrate our approach by a numerical application on a simple low-dimensional control problem.

Introduction

The continuous-time optimal control problem (OCP) is a versatile framework modelling a wide variety of nonlinear systems and optimization criteria, with countless industrial applications, including aerospace [START_REF]Optimal control and applications to aerospace: some results and challenges[END_REF] or robotics [START_REF] Murray | A mathematical introduction to robotic manipulation[END_REF]. Developing efficient numerical methods for solving such a general problem is a daunting task, especially for high-dimensional systems. Among current methods, indirect methods exploit optimality criteria derived from Pontryagin's maximum principle and give precise results but need to be initialized properly, while the less accurate direct methods reformulate the problem as a nonlinear program without specific initialization requirements [START_REF] Trélat | Contrôle optimal: Théorie & applications[END_REF]Chapter 9].

In this paper, we focus on a direct method that computes the optimal value function of the problem as the maximal subsolution of the Hamilton-Jacobi-Bellman (HJB) equation. It is described in [START_REF] Hernández-Hernández | The linear programming approach to deterministic optimal control problems[END_REF][START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI-relaxations[END_REF] and is obtained by taking the dual of the weak formulation of the OCP, involving occupation measures [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF]. In [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI-relaxations[END_REF], the numerical resolution of this formulation is based on polynomial optimization [START_REF]An introduction to polynomial and semi-algebraic optimization[END_REF], and hence is restricted to polynomial dynamics and cost functions, with a possibly costly extension to smooth functions, involving a hierachy of semi-definite programs (SDPs).

Our main contribution is to extend the numerical method of [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI-relaxations[END_REF] to non-polynomial and smooth OCPs. To this end, we consider a space of smooth functions, called a reproducing kernel Hilbert space (RKHS) [START_REF] Aronszajn | Theory of reproducing kernels[END_REF], and use representations of non-negative functions in this space [START_REF] Marteau-Ferey | Non-parametric models for non-negative functions[END_REF] with sums-of-squares. This is detailed in Sections 2 and 3. In Section 4, we notably prove that this representation is exact in two particular cases: the time-invariant linear quadratic regulator (LQR) and smooth control-affine systems. This results in a practical numerical method derived in Section 5, that requires to solve an SDP to approximate the optimal value function of the OCP. Finally, in Section 6 we illustrate the practical application of this method to a simple two-dimensional OCP.

Background

First, we introduce the three building blocks that are then combined in Section 3 to design our approximation method.

2.1. Formulation of OCP with Maximal Subsolutions of HJB. Let X and U be compact subsets of R d and R p , for integers d, p ≥ 1, and assume that U is convex. We define the dynamics f : [0, T ] × X × U → R d , the running cost L : [0, T ] × X × U → R, and the terminal cost M : X → R occurring at the fixed terminal time T > 0. In addition, we assume that the state trajectories remain in the compact set X , and that sampling points from X is easy. We do not consider problems with explicit state-constraints which are left as future work.

Assume the existence of a smooth function V * ∈ C 1 (X T ), meaning that V * is smoothly differentiable on X T := [0, T ] × X , that is a solution of the HJB equation:

∀(t, x) ∈ X T , ∂V * ∂t (t, x) + inf u∈U L(t, x, u) + ∇V * (t, x) f (t, x, u) = 0 V * (T, x) = M (x), (HJB)
where ∇V * refers to the gradient of V * w.r.t. x. For t ∈ [0, T ], let U t the set of admissible controls such that ∀s ∈ [t, T ], (x(s), u(s)) ∈ X × U. Then V * is the value function [START_REF] Liberzon | Calculus of variations and optimal control theory: A concise introduction[END_REF] of the following OCP:

∀(t 0 , x 0 ) ∈ X T , V * (t 0 , x 0 ) = inf u∈Ut 0 T t0 L(t, x(t), u(t))dt + M (x(T )) ∀t ∈ [t 0 , T ], ẋ(t) = f (t, x(t), u(t)), x(0) = x 0 . (OCP)
Let µ 0 be a probability measure on X . We are interested in the value of the stochastic initial point problem, where x 0 is drawn according to µ 0 , that is,

E x0∼µ0 [V * (0, x 0 )] = V * (0, x 0 )dµ 0 (x 0 ).
In this paper, instead of directly looking for solutions of the HJB equation, we will focus on the following alternative problem (P), namely, finding a maximal subsolution of HJB:

sup V ∈C 1 (X T ) V (0, x 0 )dµ 0 (x 0 ) ∀(t, x, u), ∂V ∂t (t, x) + L(t, x, u) + ∇V (t, x) f (t, x, u) ≥ 0 ∀x, V (T, x) ≤ M (x). (P)
This is the dual of the weak formulation of the OCP with occupation measures, which is a linear program over the space of measures [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF][START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF][START_REF] Kamoutsi | On infinite linear programming and the moment approach to deterministic infinite horizon discounted optimal control problems[END_REF]. Moreover, subsolutions of HJB also play a key role in the theory of viscosity solutions [START_REF] Michael | Viscosity solutions of Hamilton-Jacobi equations[END_REF] of partial differential equations. The first constraint in (P) is the positivity of a certain Hamiltonian associated to V , namely:

H(t, x, u) := ∂V ∂t (t, x) + L(t, x, u) + ∇V (t, x) f (t, x, u).
If V = V * is the optimal value function, then the optimal controller u = u * (t, x) minimizes the positivity constraint and for all (t, x) ∈ X T , H * (t, x, u * (t, x)) = 0.

Our goal is to find an approximate solution V of (P). Under some additional assumptions, (P) is equivalent to the OCP. Such regularity and convexity assumptions were first studied by [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF] and are detailed in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI-relaxations[END_REF]. In this particular case, the value of problem (P) coincides with the one of the stochastic initial point problem:

sup P = E x0∼µ0 [V * (0, x 0 )] .

Parameterization of the Value Function.

A first difficulty in problem (P) is searching V in the infinite-dimensional set C 1 (X T ). One option is to search V in a finitely-parameterized set F Θ . A common practice, notably in approximate dynamic programming and reinforcement learning [SB18, Chapter 9], is to use a linear approximation of V , with a feature vector ψ(t, x) ∈ R m and a parameter θ in a convex subset Θ of R m , for m ≥ 1.

Since we assumed that V * is a solution of the HJB equation, we can restrict that search space in (P) to functions V such that V (T, .) = M (.). Then we assume that the parameterization is such that ∀θ, V θ (T, .) = M (.), so that we can remove the explicit constraint in (P). Hence our parameterized set is:

F Θ := {(t, x) → V θ (t, x) = θ ψ(t, x) + M (x) | θ ∈ Θ},
with ψ such that ψ(T, .) = 0. To simplify the evaluations of ∇V θ and ∂V θ ∂t , it is convenient (but not necessary) to use a separable feature vector ψ(t, x) = κ(t)ϕ(x), with κ(T ) = 0.

Representing Non-Negative

Functions as Sum-of-Squares. Problem (P) is constrained by a dense set of inequalities indexed by (t, x, u) ∈ [0, T ] × X × U, which cannot be directly handled by numerical algorithms. Hence we look for a finite -possibly approximate -representation of the non-negative function (t, x, u) → H(t, x, u) ≥ 0.

If f , L, M are polynomials, one way is to use sum-of-squares (SoS) polynomials [START_REF]An introduction to polynomial and semi-algebraic optimization[END_REF], i.e., to represent H(t, x, u) as the sum of the squares of polynomials of a given degree. This is a sufficient but not necessary condition for being a non-negative polynomial. This technique has been applied to problem (P) in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI-relaxations[END_REF], although it is presented in its dual version using the method of moments [START_REF] Henrion | Optimization on linear matrix inequalities for polynomial systems control[END_REF]. In any case, this representation is not exact in general and gives a lower approximation of (P). To numerically solve the problem, one needs to build a hierarchy of SDPs obtained by this SoS representation with polynomials of increasing degree r. Under generic conditions, this hierarchy converges to the value of (P), but the speed of convergence is not explicitly controlled [START_REF] Pauwels | Positivity certificates in optimal control[END_REF]. This is a potentially critical issue, since the size of the SDP at rank r is defined by the number of monomials of degree less than r in the dimension of (t, x, u), which is d+p+1+r r , a quantity growing exponentially with r. In this paper, we opt for another option inspired by recently-introduced machine learning techniques [START_REF] Rudi | Finding global minima via kernel approximations[END_REF]: representing a non-negative function as a SoS in a reproducing kernel Hilbert space (RKHS). Hereafter, we briefly define an RKHS and mention its main properties, and refer to [START_REF] Paulsen | An introduction to the theory of reproducing kernel hilbert spaces[END_REF] for a thorough description. Consider a set E, a function k : E × E → R is a positive definite kernel if ∀n ∈ N, y 1 , . . . , y n ∈ E, the matrix K := (k(y i , y j )) n i,j=1 is positive semi-definite. Associated to a positive definite kernel k, there exists a unique RKHS H, a Hilbert space of functions E → R, with an inner product •, • H , such that the following properties hold (the second one is the so-called "reproducing property"):

• ∀y ∈ E, k y := k(y, •) ∈ H; • ∀g ∈ H, ∀y ∈ E, g, k y H = g(y)
. In addition, there exists a feature map Φ : E → H, possibly infinite dimensional, defined by Φ(y) = k y , which maps a point in E to a function in H, and in particular we have k(y, y ) = Φ(y), Φ(y ) H . Conversely, any feature map defines an RKHS associated to the former kernel.

Here we mention two classical kernels from the RKHS literature, which we use later to build our function representations. Assume that E is a subset of R , for ≥ 1. The polynomial kernel of degree r is defined on E ×E by k(y, y ) = (1+y y ) r , and the corresponding embedding Φ(y) is the vector of +r r multivariate monomials of degree less than r. In this case H is finite-dimensional. The exponential kernel is defined by k(y, y ) = exp(-y -y 2 /σ), with σ > 0. If E is bounded and has locally Lipschitz boundary, the corresponding RKHS is the Sobolev space of functions whose weak-derivatives up to order s = /2 + 1/2 are square-integrable [START_REF] Berlinet | Reproducing kernel hilbert spaces in probability and statistics[END_REF].

Functions that are SoS in an RKHS H can be represented using an infinite-dimensional positive semi-definite operator [RMFB20, Corollary 1]. Indeed, assume that a function h ∈ H is written as a sum-of-squares of functions h j ∈ H:

∀y ∈ E, h(y) = q j=1 h j (y) 2 .
For any v, w ∈ H, we have:

w, (v ⊗ v)w = w, vv * w = Tr(w * vv * w) = ( v, w ) 2 ,
where ⊗ denotes the outer product. Because of the reproducing property: ∀j ∈ {1, ..., q}, y ∈ E, h j (y) 2 = ( Φ(y), h j H ) 2 = Φ(y), (h j ⊗ h j )Φ(y) .

And then:

h(y) = Φ(y), AΦ(y) H , with A := q j=1 h j ⊗ h j ∈ S + (H) and A has rank at most q, where S + (H) is the set of bounded self-adjoint positive semi-definite operators on H.

In [START_REF] Marteau-Ferey | Non-parametric models for non-negative functions[END_REF], this SoS representation in an RKHS is used to model non-negative functions, e.g., for signal processing or statistics applications. In some cases, e.g., in Sobolev spaces as we will see hereafter, the representation is exact in the sense that all non-negative functions can be written as a SoS in H, whereas the polynomial SoS representation is tight only for a restricted class of polynomials [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]. Besides, SoS polynomials are a particular case of what has just been described, if k is the polynomial kernel. In the rest of the paper, we will extend the method of [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI-relaxations[END_REF] from polynomials to any RKHS, at the expense of possibly infinite-dimensional representations.

Dense Set of Inequality Constraints

In this section, we start by providing a basic relaxation of problem (P) and a motivation for preferring a SoS representation of the non-negativity constraints in (P). Then we present the resulting problem and its main features.

3.1. Relaxed formulation by subsampling. A straightforward relaxation of (P) is obtained by finitely subsampling the non-negativity constraints. Let us sample values of (t (i) , x (i) , u (i) ) i∈I in [0, T ] × X × U, with I a finite set of cardinality n ≥ 1. For simplicity, assume that µ 0 is the mean of n 0 Diracs at points {x (i) 0 } i∈{1,...,n0} . Besides, let us use a linear parameterization of V as described in Section 2.2, with Θ = R m . We then obtain a linear program, with a possibly unbounded solution in the overparameterized setting (m n). To circumvent this effect, we add a quadratic regularizer on θ with parameter λ θ ≥ 0, and obtain the following problem:

sup θ∈R m 1 n 0 n0 k=1 θ ψ(0, x (k) 0 ) + M (x (k) 0 ) -λ θ θ 2 2 ∀i ∈ I, θ ∂ψ ∂t (t (i) , x (i) ) + L(t (i) , x (i) , u (i) ) (LP) + θ ∇ψ(t (i) , x (i) ) + ∇M (x (i) ) f (t (i) , x (i) , u (i) ) ≥ 0.
Although this is not exactly a linear program if λ θ > 0, it can still can be solved easily by standard solvers, and we will refer to it as the LP problem. A similar finite-dimensional LP formulation has been proposed in [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] for discounted infinite-horizon control problems. It is part of a long series of LP formulations for optimal control (see, e.g., [START_REF] Gaitsgory | Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time[END_REF] and references therein), for dynamic programming and more recently for reinforcement learning [START_REF] Lu | American Control Conference (ACC)[END_REF]. This problem will be used as a baseline in Section 6, to be compared with the SoS formulation below. It is a relaxation that gives an upper-bound on (P), but it is not straightforward to relate the number of samples n and how they are spread to the quality of the approximation. Yet in the example below, this can be evaluated explicitly.

Example 1: Let g : R p → R be a smooth function with a unique minimizer u * . With T = 1, L : (t, x, u) → g(u), f = 0 and M = 0, then V * (t, x) = (1 -t)g(u * ) and solving the OCP is essentially equivalent to finding the global minimizer of g. If V is parameterized by V θ (t, x) = θ(1 -t), the LP formulation with λ θ = 0 writes:

sup θ s.t. ∀i ∈ I, -θ + g(u i ) ≥ 0,
which is readily solved by θ = min{g(u i )} i∈I . In general, this method requires O(ε -p ) samples to approximate g(u * ) with precision ε [START_REF] Novak | Deterministic and stochastic error bounds in numerical analysis[END_REF], and yet when g is smooth, this is not an optimal way to perform zero-th order optimization. Indeed, [RMFB20] use a SoS representation of g -θ to solve this exact problem, and alleviate the curse of dimensionality when g is sufficiently smooth: the number of samples reduces to O(ε -p/s ) for g ∈ C s (R p ). In the rest of this paper, we propose to use the same approach and to generalize it to any OCP. We expect similar benefits when H is smooth.

Strengthened formulation by SoS representation.

Consider an RKHS H of real-valued functions on [0, T ] × X × U, with positive definite kernel k, and Φ : E → H the corresponding embedding. We use a SoS representation in H, or "kernel SoS", for the constraint H ≥ 0 in (P):

sup V ∈C 1 (X T ), A∈S+(H) V (0, x 0 )dµ 0 (x 0 ) ∀(t, x, u), H(t, x, u) = Φ(t, x, u), AΦ(t, x, u) . (KSOS)
This is a strengthening of the constraint in (P), since being SoS is stronger than being nonnegative. So in general, (KSOS) is a lower-approximation of (P). However, in certain cases, (KSOS) can be equivalent to (P), as we will prove in Section 4. A sufficient condition is the existence of A ∈ S + (H) such that, at the optimal V * : ∀(t, x, u), H * (t, x, u) = Φ(t, x, u), AΦ(t, x, u) .

Tight Sum-of-Squares Representations

We study the tightness of problem (KSOS) in two particular cases: the time-invariant LQR and smooth value functions.

4.1. Case 1: Infinite-Horizon Time-Invariant LQR. First we look at a very simple OCP, where every quantity can be computed almost in closed form, and with infinite-horizon so that there is no dependence in t.

Let f (x, u) = A 0 x + B 0 u, for A 0 ∈ R d×d , B 0 ∈ R d×p , with (A 0 , B 0 ) controllable, L(x, u) = x Q 0 x + u R 0 u, Q 0 ∈ S + (R d×d ), R 0 ∈ S + (R p×p ), R 0 0.
The optimal value function is V * (x) = x S 0 x, where S 0 is the unique positive semi-definite solution of the algebraic Riccati equation:

0 = -Q 0 -A 0 S 0 -S 0 A 0 + S 0 B 0 R -1 0 B 0 S 0 . The optimal controller is u * (x) = -R -1 0 B 0 S 0 x =: -K 0 x. H * (x, u) = x Q 0 x + u R 0 u + 2x S 0 (A 0 x + B 0 u) = u R 0 u + x S 0 B 0 u + u B 0 S 0 x + x S 0 B 0 K 0 x.
This is a SoS of degree-one polynomials in (x, u):

H * (x, u) = (u + K 0 x) R 0 (u + K 0 x) = x u K 0 I p R 0 K 0 I p x u = p j=1 [q j (x, u)] 2 , with q j (x, u) := [R 1/2 0 ] j • K 0 I p x u .
Hence, an infinite-horizon, time-invariant LQR with unknown parameters can be equivalently expressed by: sup

V ∈C 1 (X ), N 0 V (x 0 )dµ 0 (x 0 ) ∀(x, u), L(x, u) + ∇V (x) f (x, u) = x u N x u .
In the next section, we prove that similar SoS constructions exist for sufficiently smooth OCPs, possibly with an infinite-dimensional embedding (v.s. a (d + p)-dimensional one here).

Sum-of-Squares

Decomposition with Smooth Functions. We show that, for smooth and control-affine OCPs, H * is a SoS of smooth functions. Let

Ω 2 := Int(U), Ω 1 := Int{(t, x) ∈ X T | argmin u∈U H * (t, x, u) ⊂ Ω 2 }, and Ω := Ω 1 × Ω 2 . Theorem 1. Let s ∈ N, s ≥ 1. Assume that: • f is control-affine: ∀(t, x, u) ∈ [0, T ] × X × U, f (t, x, u) = g(t, x) + B(t, x)u.
• For all (t, x) ∈ Ω 1 , u → L(t, x, u) is twice differentiable on Ω 2 and strongly convex: ∇ 2 u L(t, x, u) ρI for some ρ > 0, and

(t, x, u) → ∇ 2 u L(t, x, u) ∈ C s (Ω). • (t, x, u) → ∇ u L(t, x, u) + B(t, x) ∇ x V * (t, x) ∈ C s (Ω).
Then there exist p functions (w j ) 1≤j≤p ∈ C s (Ω) such that:

∀(t, x, u) ∈ Ω, H * (t, x, u) = p j=1 w j (t, x, u) 2 .
The proof is in the appendix. This result motivates the use of exponential kernels, inducing a Sobolev space RKHS, to represent the non-negativity constraints in (P) for smooth OCPs. When s > d/2 + 1, by applying a technique similar to the one used under Corollary 2 of [START_REF] Rudi | Finding global minima via kernel approximations[END_REF], it is possible to obtain a SoS representation in terms of the exponential kernel. Then (KSOS) is equivalent to (P). 4.3. Stochastic Smoothing of the Optimal Value Function. However in general, V * is not necessarily smooth (e.g. minimal time problems), nor is u * (e.g. bang-bang controllers that are not even continuous). Here, we provide a generic technique to give some regularity to V * . For η > 0, we can define a perturbed version of the control system [START_REF] Fleming | Deterministic and stochastic optimal control[END_REF], where the state is a random variable X t :

dX t = f (t, X t , u t )dt + (2η) 1/2 dB t ,
where B t is a standard Brownian motion independent of X t . We define the optimal value function, with X 0 = x 0 :

V η (t 0 , x 0 ) = inf u∈U E T t0 L(t, X t , u t )dt + M (X T ) . V η is the unique C 1,2 (X T ) (C 1 in t, C 2 in x) solution [FR12] of the following regularized HJB equation: ∀(t, x) ∈ X T , inf u∈U {L(t, x, u) +∇V η (t, x) f (t, x, u)} + ∂V η ∂t (t, x) + η∆V η (t, x) = 0, with V η (T, x) = M (x)
. ∆V η refers to the Laplacian with respect to x. Contrary to HJB, the solutions are at least C 1,2 (X T ) because this is a quasilinear parabolic partial differential equation [START_REF] Gary | Second order parabolic differential equations[END_REF]. The regularization η∆V is a vanishing viscosity term, and the optimal controller is still in argmin u L + ∇V η f . Generically, V η converges to V * as η → 0, following a reasoning similar to the theory of viscosity solutions [START_REF] Michael | Viscosity solutions of Hamilton-Jacobi equations[END_REF].

SDP Formulation and its Numerical Resolution

5.1. Finite-Dimensional Formulation via Subsampling. Similarly to the (LP) formulation that relaxes (P), we will now derive a relaxation of problem (KSOS), which is another relaxation of problem (P) if the SoS representation of H * is tight. Going through (KSOS) as an intermediate step will help to exploit the structure of (P). Using a parameterization of V in F Θ with Θ = R m , and a set of sampled points (t (i) , x (i) , u (i) ) i∈I in [0, T ] × X × U, with |I| = n, we obtain: anda

sup A∈S+(H),θ∈Θ c θ -λ θ θ 2 2 -λ Tr(A) + C such that ∀i ∈ {1, . . . , n}, b i + a i θ = Φ(t (i) , x (i) , u (i) ), AΦ(t (i) , x (i) , u (i) ) , with c := n i=1 µ (i) 0 ψ(0, x (i) ), C := i µ (i) 0 M (x (i) ), b i := L(t (i) , x (i) , u (i) )+∇M (x (i) ) f (t (i) , x (i) , u (i) )+ η∆M (x (i) ),
i := J ψ (t (i) , x (i) )f (t (i) , x (i) , u (i) )+ ∂ψ ∂t (t (i) , x (i) )+η∆ψ(t (i) , x (i) )
, where J ψ denotes the Jacobian matrix of ψ with respect to x only. Note that we integrate the stochastic smoothing process in this formulation, with parameter η that can be eventually set to 0.

The regularization parameter λ > 0 controls the trace of the infinite-dimensional operator A, and allows for subsampling to provably recover the non-subsampled program when n tends to infinity, and λ goes to zero at the proper rate (see [START_REF] Rudi | Finding global minima via kernel approximations[END_REF] for the precise dependence). In the limit λ → 0, we recover the LP formulation where we assume nothing about the SoS representation of H * in H.

Both the operator A and the Φ(t (i) , x (i) , u (i) ) can be infinite dimensional, depending on the RKHS H. Yet, following [START_REF] Rudi | Finding global minima via kernel approximations[END_REF], we can reformulate the problem equivalently in finite dimension. Using the representer theorem in [START_REF] Marteau-Ferey | Non-parametric models for non-negative functions[END_REF], one can prove that A can be sought in the form: for D ∈ R n×n , D 0,

A = n i,j=1 D ij Φ(t (i) , x (i) , u (i) ) ⊗ Φ(t (j) , x (j) , u (j) ).
Simple computations detailed in [START_REF] Rudi | Finding global minima via kernel approximations[END_REF] show that:

∀i, Φ(t (i) , x (i) , u (i) ), AΦ(t (i) , x (i) , u (i) ) = [KDK] ii , Tr(A) = Tr(DK),
where K is the kernel matrix with entry (i, j) equal to k (t (i) , x (i) , u (i) ), (t (j) , x (j) , u (j) ) . Assume that K 0. We denote by K = R R the Cholesky decomposition of K, with R an invertible upper-triangular matrix.

Let B := RDR and for 1 ≤ i ≤ n, Φ i := R • i . Then:

Tr(B) = Tr(DK) = Tr(A), [KDK] ii = R BR ii = Φ i BΦ i .
The problem can now be reformulated as a finite-dimensional SDP over the positive semi-definite matrix B ∈ R n×n :

sup B 0,θ∈R m c θ -λ θ θ 2 2 -λ Tr(B) + C (SDP) such that ∀i ∈ {1, . . . , n}, b i + a i θ = (Φ i ) BΦ i .
An important question is to estimate the number of subsampled inequalities sufficient to ensure that (SDP) ⇔ (KSOS). If nothing is assumed on the structure of H, as in the LP method, this number is infinite. In contrast, the kernel SoS representation can reduce it or make it finite. If H is a polynomial of degree 2r, k is the polynomial kernel of degree r, then n ≥ 2r distinct sampled points are enough to interpolate H, and (SDP) ⇔ (KSOS). Another example is global optimization of smooth functions (see Example 1 ) with the exponential kernel. We refer to [START_REF] Rudi | Finding global minima via kernel approximations[END_REF] for the analysis of the convergence rates, with a lower dependence in the dimension for the kernel SoS when compared to direct inequality subsampling (corresponding to the LP approach).

Interior Point

Method with the Damped Newton Method. Problem (SDP) can be readily solved by any off-the-shelf SDP solver. However, for large n, this quickly becomes too computationally demanding. Here, we propose a numerical scheme based on [RMFB20] that scales better with the number of subsamples n. First, we introduce a slack variable δ ∈ R n allowing the constraints to be slightly violated (e.g. because F Θ is not a perfect model), controlled by a large parameter γ > 0. Second, we introduce a log-barrier term controlled by a small ε > 0, useful to form the dual of the SDP. We obtain the following problem:

sup B 0, θ,δ c θ -λ Tr(B) -λ θ θ 2 2 -γ δ 2 + ε log det B + C such that ∀i ∈ {1, . . . , n}, b i + a i θ = (Φ i ) BΦ i + δ i .
The Lagrange dual of this problem reads:

inf α∈R n n i=1 α i b i + 1 4λ θ m j=1 c j + n i=1 α i a ij 2 -ε log det U (α) + 1 4γ α 2 2 + εn log(ε/e) + C,
where U (α) := λI n + Φ Diag(α)Φ, and Φ := R is the matrix with rows

(Φ i ) 1≤i≤n . Let us call the objective F (α). Since F/ε is self-concordant [BV04] like in [RMFB20]
, we propose to use damped Newton iterations [START_REF] Nemirovski | Interior point polynomial time methods in convex programming[END_REF] on F/ε:

α ← α + 1 1 + λ(α) ∆α,
where ∆(α) := -[F (α)] -1 F (α) is the Newton direction and λ(α) := ∆α F (α)∆α/ε is the Newton decrement. The gradient and Hessian of F are computed by:

∂F ∂α i = b i + 1 2λ θ m j=1 a ij c j + n k=1 a kj α k + 1 2γ α i -ε Φ i U (α) -1 Φ i . ∂ 2 F ∂α i ∂α j = 1 2λ θ n k=1 a ik a jk + ε Φ i U (α) -1 Φ j 2 + 1 i=j 2γ .
At optimum, the value function is recovered by

θ = 1 2λ θ n i=1 α i a i + c ,
and the dual variable α plays a role similar to an occupation measure [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF], although it is not necessarily non-negative. To improve numerical stability in the experiments hereafter, we used an homotopy heuristics that progressively decreases the parameters λ θ and ε. Moreover, parallel implementations are possible because no singular value decomposition is needed, only matrix operations and system inversions.

Numerical Example

In this section, we apply the kernel SoS method along with the basic LP method, on a twodimensional control problem, namely the double integrator with finite horizon. Setting. The problem is an LQR, as in Section 4.1, but with finite-horizon

T = 1, d = 2, p = 1, M (x) = x 2 2 , A 0 = 0 1 0 0 , B 0 = 0 1 , Q 0 = I 2 , R 0 = 0.1 .
The optimal value function and controller are V * (t, x) = x S(t)x, u * (t, x) = -R -1 0 B 0 S(t)x =: -K(t)x, where S(.) is the positive semi-definite solution of S(T ) = I 2 and:

Ṡ(t) = -Q 0 -A 0 S(t) -S(t)A 0 + S(t)B 0 R -1 0 B 0 S(t). Parameterization of V . Let V θ (t, x) = θ ψ(t, x)
, where each entry of ψ is a product of basis functions on X and

[0, T ]. Let ϕ(x) := (1, x 1 , x 2 , x 1 x 2 , x 2 1 , x 2
2 ) , because we know V * is quadratic in x. For κ on [0, T ], we only know that it is a smooth function, so we use an approximate basis of the Sobolev space of functions with squared integrable derivatives: a sequence of sines and cosines with decreasing periods beginning with 2T to avoid constraining V (0, .) = V (T, .), and κ(T ) = 0, ensures that V (T, .) = M (.):

κ(t) := 1 ω sin ωπ 2 t -T T 1≤ω≤mt .
Finally, ψ i+6j (t, x) := ϕ i (x)κ j (t), and θ ∈ R m , m = 6m t . We choose m t = 10, for which the performance of the policy of the projection of V * on F Θ is almost perfect. Evaluation. We give two criteria to evaluate the quality of an approximation V . First, the distance to V * : V -V * 2 , where V is the vector of its values on a regular grid on [0, T ] × [-1, 1] 2 with 10 × 10 × 10 points. Second, the cost of the policy on a 10 × 10 regular grid of initial points. Sampling. The set of samples (t (i) , x (i) , u (i) ) i∈I is built as follows. The x (i) are n x points in [-1, 1] 2 generated by the Sobol sequence [Sob67], the (u (i) ) 1≤i≤nu are on a uniform grid on [-10, 10] and the (t (i) ) 1≤i≤nt on [0, T ]. The sample set is the Cartesian product of the three previous ones, and has n = n t n x n u elements. We also use the same samples as initial points (t

(i) 0 , x (i)
0 ) in the objective function of problem (P). Note that we have replaced it with n i=1 V (t (i) , x (i) )/n, as we found it more efficient in our experiments to optimize over V at intermediate time steps rather than at t 0 only. Indeed, we ultimately evaluate our approximation by the accuracy of V on the whole X T and not only on {t 0 } × X . In a discrete states and actions setting, this effect is analyzed in [START_REF] Pucci | The linear programming approach to approximate dynamic programming[END_REF], where µ 0 is denoted as "state-relevance weights". Methods. We compare three methods: the LP, the guided SoS and the kernel SoS. The LP method is detailed in Section 3.1, and as for the kernel SoS method, we add a slackness parameter on the constraints, with a penalization controlled by γ > 0 (γ → ∞ recovers the original LP).

The guided SoS method is the same as the (SDP) problem, except that the embeddings Φ i of the samples are replaced by vectors Ψ i of fixed dimension, which are computed explicitly, without a kernel. Motivated by the fact that: we choose the embedding vectors as follows:

H * (t, x, u) = (u + K(t)x) R(u + K(t)x),
Ψ i := (u (i) /10, x (i) , (1/ω sin(ωπ/2(t/T -1))x) 1≤ω≤qt ) ,
where the last q t scalar terms (without the vector x) approximately model K(.) as a smooth function of t. For computational efficiency, we choose q t = 5 and we checked that this basis can approximate the entries of K(t) well. Then we solve an SDP of size (p + q t d) × (p + q t d) = 11 × 11 instead of n × n for the kernel version.

The kernel SoS method is as described in the previous sections, with the following kernel:

k((t, x, u), (t , x , u )) = u, u /100 + x, x × exp(-|t -t |).
This kernel is also designed to match the shape of H * , with a smooth term in t modelled by the exponential kernel. The matrix K can be singular, so we replace it by K + 10 -8 I n .

Results. We compare the performance of the three methods to a baseline: the projection of V * on F Θ , which is a proxy for the best performance to expect with a fixed F Θ . We keep the best set of hyper-parameters after a grid search on (λ θ , γ) for the LP method, and on (λ θ , γ, λ) for the two others, with ε = 10 -4 . We keep η = 0 and n t = 20 in all the experiments, and a varying number n x = n u of sample points. For example, with n x = n u = 20, the dual variable α of the largest problem here has dimension n = 8000, and solving the numerical problem written in Python takes a few minutes on a standard laptop.

The results are presented in Figure 1. The guided and kernel SoS methods perform similar, and better than the LP: they better exploit a fixed number of samples than the LP. Note that the kernel SoS tends to the LP when λ tends to 0, hence using a positive λ improves the results. We believe that the design of a kernel adapted to prior knowledge on the problem is crucial to benefit from this effect. Finally, the kernel SoS has the same performance as the guided SoS, but it is computationally more expensive as soon as n > 11. Yet the kernel version extends way beyond such fixed finite-dimensional embeddings, to infinite-dimensional embeddings represented by any positive definite kernel, including the exponential kernel, the polynomial kernel and many others.

Conclusion

The kernel SoS approximation method generalizes the polynomial SoS method for OCPs. Like the simple LP method, it is black-box in the sense that it is based only on function evaluations of the dynamics and loss, without requiring any gradients. Moreover, it enables to exploit prior knowledge on the structure of an OCP, by choosing an appropriate kernel. The problem reduces to an SDP, whose size can be computationally limiting, but parallel implementations are possible. There are several sources of approximation in this method: the parameterization F Θ of V might not be exact, the SoS representation of H * is not exact in general (although we have proved it is in a few particular cases), and we subsample a finite number of constraints (further work is needed to evaluate the effect of this step). In particular, it seems essential to assess in which cases the subsampling step is tight with a finite number of samples, or approximately so, in such a way that the overall process gives a certified lower-bound on the OCP, similarly to [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI-relaxations[END_REF]. For all these reasons, the method will probably not reach high precision solutions, but can be used to initialize direct shooting methods, and returns an approximate solution even with very few samples. Furthermore, we believe it is possible to extend the method to also account for state constraints, similarly to [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI-relaxations[END_REF]. One could also parameterize the value function directly in an RKHS. Another interesting extension is to apply the method to Markov decision processes, where we could deal with states or actions that are more complex objects (graphs, trajectories, DNA sequences...) with appropriate kernels.

Figure 1 .

 1 Figure 1. Comparison of the performances of the value function and the policy of the three methods, as a function of the number of samples n x = n u .

Acknowledgements

This work was supported by the Direction Générale de l'Armement, and by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grants SEQUOIA 724063 and REAL 947908). We thank Didier Henrion for interesting discussions related to this work.

Appendix A. Proof of Theorem 1

Proof. Consider the Hamiltonian with f control-affine: H * (t, x, u) = ∇V * (t, x) g(t, x) + ∂V * ∂t (t, x)

Pontryagin's maximum principle states that:

Since L is strongly convex in u, the minimizer is unique and we call it u * (t, x). By definitions of Ω 1 and Ω 2 , we have a mapping u * : Ω 1 → Ω 2 and it is characterized by:

) is continuous on Ω and invertible, and (t, x, u) → ∇ u H * (t, x, u) ∈ C s (Ω), then the implicit function theorem ensures that u * ∈ C s (Ω 1 ) (see [START_REF] Schwartz | [END_REF], Chapter 8, Theorems 25 & 31).

For (t, x, u) ∈ Ω, we use Taylor's formula around u * (t, x):

Since H * (t, x, u * (t, x)) = 0, ∇ u H * (t, x, u * (t, x)) = 0 (by definition), and

•), we have:

For (t, x, u) ∈ Ω, R(t, x, u) has a positive-definite square root R(t, x, u). Also, ∀τ ∈ [0, 1],

(

ρ 2 I}, then r i,j : (t, x, u) → e i R(t, x, u)e j ∈ C s (Ω), and we have the decomposition:

w i (t, x, u) 2 , with w i (t, x, u) := R(t, x, u) i • (u -u * (t, x)) = p j=1 r i,j (t, x, u) e j (u -u * (t, x)) , and each w i ∈ C s (Ω).


ARTICLE YANNIS HARALAMBOUS

Breaking Arabic: the creative inventiveness of Uyghur script reforms

Abjad or not?

The Arabic writing system is notoriously an . Nevertheless, let us not confuse writing system and script! A script is neither abjad nor abjad per se-it is its use in the frame of a particular language that can be qualified as such (for further discussion see Meletis, 2020, p. 21). In theory, for languages other than Arabic, the Arabic script could be used in manifold ways.

!bj!d 1 not

However, the rule is that most languages that use Arabic script use it as an abjad. The reasons are historical: the Arabic script has been spread as the vehicle of Islam and, consequently, Arabic-script languages contain a substantial amount of Arabic words, in their original Arabic spelling. If Arabic loan words are written and read in abjad mode, then it is not surprising that words in native languages are written and read in the same way.

DES$GN REGRESS$ON

This paper deals with a renowned exception to this: a language that uses the Arabic script in a strictly way. This language takes the liberty of respelling Arabic loan words and names. And furthermore, this language dares to transgress the most sacrosanct rule of Arabic calligraphy/typography by actually breaking words at the end of the line.

phonogr!phic 2

This language is . Uyghur 3

A glance at history

Uyghur is a Turkic language and, as such, it historically faced the same problems as Ottoman, Kirghiz, Kazakh, and other Turkic languages. The abjad approach used for Arabic loan words in their original spelling was extended to native words, even though these languages are morphologically quite different from Arabic.

In Turkey, Kemal Atatürk solved the problem in 1929 by imposing a purely phonographic Latin-script based writing system, and by removing most Arabic and Persian loan words from the language [START_REF] Lewis | [END_REF].

The Xinjiang region (Northwest China), where most of the Uyghurs live, has not been affected by Atatürk's reform-at the time it was politically part of the Republic of China and culturally under the Soviet sphere of influence (Wei, 1993, p. 263). Uyghurs chose a different path: from 1937 to 1983 (and despite short periods of use of the Cyrillic and ) they reformed their writing system [START_REF] Wei | An historical survey of modern Uighur writing since the 1950s in Xinjiang, China[END_REF][START_REF] Reheman | A field research of Chinese Uyghur people's writing reforms and influences in the 20th century[END_REF], and progressively transformed the use of Arabic script in Uyghur from abjad mode to phonographic mode.

the Latin script 4

Here is how they did it.

How to move from abjad to phonography https://designregression.com/article/breaking-arabic

First of all the Uyghurs needed to solve the problem of Arabic loan words that would need to be read in abjad mode. They solved it by respelling the words (in a way similar to the way the Hungarians spell the name of the French capital as "Párizs" An (approximate) Uyghur transcription of "Design Regression", typeset in the typeface Amiri.

Figure 1:

The second most frequent Uyghur vowel phoneme is /a/, which is non-problematic since it is perfectly compatible with the Arabic letter . So let us turn to the third most frequent Uyghur vowel phoneme, namely /ε/. For this, the Ottomans used the letter . The problem is that in the As for the relatively rare phonemes /ø/ and /y/, Uyghurs used diacritics absent from the Arabic writing system: and .

ۆ ۈ

And last but not least, for the semi-vowel /w/, they chose a -also a clever choice since triple dots are exclusively used for consonants in the Arabic and Ottoman writing systems, so that they carry the "consonant" connotation.

tripledotted vowel 7 ۋ

And this is how the Arabic script joined the world of phonography.

Hyphenation of Arabic script

What is common to Semitic languages is the fact that the morphology of a graphemic word is identified by the reader through a specific mental process. This process consists of detecting a combined with a , a potential prefix, and a potential suffix.

The root is a set of three or four consonants carrying semantic To be able to carry out this process, the reader of the Arabic language needs a simultaneous visualization of the complete Arabic . Hyphenation would break this visualization and make it more difficult to identify its parts. Consequently the Arabic language has never been hyphenated. Furthermore, the connected nature of the Arabic script allows the calligrapher (and, to a lesser extent, the typographer) to elongate or shrink words to fit them on lines of equal width, so that there is no need for hyphenation in the first place. graphemic word 8

The choice of not hyphenating Arabic language has been inherited by all other languages using the Arabic script, even though languages such as or Persian could very well benefit from such a method. This would apply especially in printed media, in which columns may be narrow. Furthermore, in typography, lengthening of connecting strokes between Arabic letters in order to compensate for excessive whitespace is not as easy as in calligraphy.

Turkish 9

Once again Uyghur broke the rule. Reformers probably considered hyphenation as a feature inherent in all phonographic writing systems and decided to take the plunge and be the first (and only, for the moment) Arabic-script language in the world adopting it.

Of course this decision was taken at a time when typesetting was mechanical and such an operation was still possible. In digital typography, hyphenation of Arabic script is quite a challenge since it requires redefining the basic contextual behaviour of letters, which is handled at a very low level by the operating system. Systems such as XeTeX can do it in a rather tricky way (cf. Haralambous, 2021) but not (yet) word processing software, at least not automatically. And hyphenation, by its nature, should be automatic. https://designregression.com/article/breaking-arabic

Font design of hyphenated Arabic script

A natural question to ask is: do the features of the Uyghur language affect font design?

In , and the reader can see excerpts from three Uyghur printed documents, covering the period 1979-2021 (documents from the Web site ). between letters have been elongated to compensate for the lack of hyphenation. This is a standard practice in Arabic language but does not comply with Uyghur typographic tradition, as can be seen in Figures 2 and3.

Figure 4: Lutun

Observing these documents, one immediately notices that Uyghur typesetters avoid Arabic aesthetic ligatures (see Haralambous & Dürst, 2019, p. 152) and favour a Maybe the purpose of this communicative strategy is to emphasize the phonographic nature of the writing system, where graphemes are directly matched to phonemes and we have a tendency to perceive the order of phonemes as inherently linear since our speech organs can only emit a single phoneme at a time.

.

f/!t design 10

The preference of non-ligatured text is easy to achieve; it suffices to deactivate aesthetic ligatures in the font. What is more challenging for designers is to cope with hyphenation.

Splitting after a biform letter involves no special design. After all, being the letter is already necessarily in final or isolated form. Thus, the hyphen is simply appended to a final or isolated form, something perfectly natural in all the Arabic-script languages (see ).

biform, 11

Table 1

ﻣﯩﻬﻰ ﻣﯩـ۔ ـﻬﻰ

Hyphenating after biform and quadriform letters in Uyghur. Table 1: The difficulty is to hyphenate quadriform letters, which are connected to the following letter by a calligraphic stroke and hyphenation occurs between forms that are normally meant to be connected.

Indeed, for centuries Arabic type designers have connected shapes in such a way that the connecting curve seems as natural and elegant as possible. The reader is not supposed to notice the junction point between the letters. The illusion of an unbroken natural calligraphic stroke between the two letters is crucial to obtain the fluidity of a high-quality Arabic font. By splitting the connecting stroke between two letters, the entrails of the font are laid bare-compare the fluidity of a Uyghur word and the awkwardness of its individual segments in . Figure 5 An Uyghur word typeset in Decotype Naskh and its individual segments laid bare.

Figure 5:

One way to solve the problems inherent in Uyghur typography would be to design additional contextual forms for letters involved in hyphenation and to develop systems that would use these forms automatically whenever hyphenation of quadriform letters occurred.

Since the Unicode standard has adequately encoded the various uses of the Arabic script, the internationalization of Arabic fonts has been straightforward: the font designer only had to add some additional dots and diacritics and to build ligatures involving these additions. In the light of what we said above, adding special forms for hyphenation may be a real internationalization challenge for designers of Arabic fonts, since they may need to re-invent the very basics of the Arabic script. This is an amazing opportunity for designers to contribute with an elegant and effective solution, and will require the collaboration of programmers and designers.

Conclusion

Uyghurs reformed their writing system to use the Arabic script phonographically rather than as an abjad. Their decision to break with 14/10/2021 08:45 Breaking Arabic: the creative inventiveness of Uyghur script reforms https://designregression.com/article/breaking-arabic tradition was remarkable, but even more remarkable was the way they actually achieved it. Instead of switching to a different script, as did the Turks, they chose to stay as close as possible to their cultural heritage of the Arabic script, but redesigned its use to adhere to strict phonography. Their methods were highly innovative. Today, the decision to hyphenate, contradicting the fluid connections between letters, calls for new letter forms and constitutes the main challenge for programmers and designers. We hope that in the years to come font designers will accept this challenge and produce Arabic font masterpieces rendering equally well Uyghur and all other Arabicscript languages.

Solution to the exercise

Solution to the test of identification of the letter . A script is used in a phonographic mode when graphemes represent all types of phonemes, whether consonant, long vowels, or short vowels.

2

While the venerable and write "Uighur" (with an "i"), Wikipedia and mass media use the "Uyghur" spelling. We kept the latter because it coincides with the official Uyghur Latin-alphabet transcription of the Uyghur word for Uyghur, namely .

3 Oxford English Dictionary Encyclopaedia Britannica

ﺋﯘﻳﻐﯘر

According to Zhou (2003, p. 137-138), Uyghur may return once again to the Latin script since "information technology clearly favors romanized writing systems", an extremely Eurocentric point of view.

4

The tooth form (cf. Smitshuijzen, 2001, p. 181 (Meletis, 2020, §2.5) for the definition of "graphemic word". 8

Turkish is a so-called language where graphemic words may contain entire phrases and therefore can be quite long.

!gg#utin!tive

At least in the Naskh style (see Osborn, 2017, p. 55 and[START_REF] Haralambous | The traditional Arabic typecase extended to the Unicode set of glyphs[END_REF],

  Figures 2 3 4

Figure 2 :

 2 Figure 2:Shinjangning qisqiche tarixi

Figure 3 :

 3 Figure 3:Lale-qurban

  a writing system in which primary graphemes represent only consonants or long vowels. Typical examples are the writing systems of Arabic, Hebrew and Syriac languages.

  1

aesthetic

  Arabic ligatures often correspond to a vertical stacking of shapes. In the absence of aesthetic ligatures, the base line is visually omnipresent and the general impression is one of a flat design. Compare the ligatured (left) and unligatured (right) sequence of the three letters in the following figure: 10 In the Arabic script, letters are not connected to the following letter; letters are connected to the following letter. 11 biform qu!driform

  ـﻴـ two dots underneath. The simple solution would be to use for phoneme /i/, but that would be a tedious solution since Uyghur texts would be flooded with letters, and strongly-opinionated Arabs might have said: "See, this is why we prefer abjad: it allows us to avoid repeating the obvious and to show only pertinent information".

					ـﻴـ
	ـﻴـ
		). For example, the Arabic
	word does not mark the short /u/-becomes (sultan)-that uses a non-Uyghur emphatic letter in Uyghur; has become (of which the medial form is ) and the phoneme /u/ is and represented by grapheme . ﺳﻠﻄﺎن ط ﺳﯘﻟﺘﺎن ط ت Uyghur reformers were definitely not tedious. They cut the Gordian ـﺘـ ۇ knot by changing the rules of the Arabic script: they used a non-
	, namely a tooth without dots or diacritics. Using an undotted /etter
	Next, they cleaned up their consonants. They kept Arabic consonants tooth is both radical and ingenuous-indeed, the most ـﯩـ belonging to their phonology, without changing their grapheme-phoneme correspondence. All other consonants ( , , , , , , , , and the stand-alone ) had to go. And as the Arabic unobtrusive grapheme you can get is the one you wouldn't notice in ث ح ذ ص ض ط ظ ع ة the first place. A non-Uyghur reader of the Arabic script may not ء even detect its presence. As a test, try to locate the four occurrences
	writing system was not sufficient to represent all Uyghur consonantic of the letter in .
	phonemes, they added graphemes	, , , پ چ ژ گ	and	ڭ	, which were
	already used in Ottoman (Buğday, 2009).
	Now comes the difficult part: how to deal with vowels. Disregarding
	vocalic length, Arabic language has only three vowels, while the
	Uyghur phonology requires eight vowels. The principle of strict
	phonography requires all vowels to be denoted by distinct
	graphemes-Uyghurs were keen on applying this principle and, after
	47 years of reforms, they achieved it.
	The main constraint was to do it in a way that is natural to the Arabic
	script, i.e. to use variations of original Arabic graphemes in order to
	obtain new graphemes for Uyghur. Can this be done in a simple and
	straightforward way? Not really, but a smart way to do it is to keep
	frequent graphemes simple and allow more visual complexity in the
	rarer ones.
	Let us therefore consider vowels in decreasing order of frequency, to
	discover the inventiveness of Uyghur reformers.
	The most frequent Uyghur vowel phoneme is /i/; it appears in 42.64%

of Uyghur words. Arabic uses for the long vowel /i/. The medial form of this Arabic letter is , which is with two dots underneath. The simple solution would be to use for

ي ـﻴـ

the standard "tooth" 5 6 ـﯩـ Figure

1

  , for the name) is used in six Arabic-Breaking Arabic: the creative inventiveness of Uyghur script reforms Page 11 sur 14 https://designregression.com/article/breaking-arabic

									14/10/2021 08:45
	6	For the solution, see	. Figure 6
	Indeed, all triple-dotted graphemes represent consonants: /ŋ/, /ʧ/. 7 چ	ث	/θ/,	پ	/p/,	ش	/ʃ/,	ڭ
		See
	5
	language letters, namely	, , , , ـﺒـ ـﺘـ ـﺜـ ـﻨـ ـﻴـ	and , always accompanied by dots or ـﺌـ
	other forms.
	6	For the solution, see	. Figure 6

https://designregression.com/article/breaking-arabic

 Zhou, M. (2003).

. Mouton