Aris Daniilidis

Tr Mounir Haddou

Olivier Ley

Solving Nonlinear Absolute Value Equations

Keywords: Nonlinear Absolute Value Equality, Complementarity problem, P 0 -map, Numerical methods AMS Classification: Primary: 90C33, 65K10 ; Secondary: 15B48, 65K15, 90C59

In this work we show that several problems naturally modeled as Nonlinear Absolute Value Equations (NAVE), can be restated as Nonlinear Complementarity Problems (NCP) and solved efficiently using smoothing regularizing techniques under mild assumptions. Applications include ridge optimization and resolution of nonlinear ordinary differential equations.

Introduction

The last two decades, absolute value equation problems (in short, AVE problems) have been extensively studied in the literature. This interest is justified by the fact that this class of problems already covers a wide spectrum of applications: indeed, numerous problems stemming from real-life applications, as for instance all mixed integer linear programming problems, can be reformulated as AVE problems. It is also well-known, see [START_REF] Mangasarian | Linear complementarity as absolute value equation solution[END_REF][START_REF] Prokopyev | On equivalent reformulations for absolute value equations[END_REF] e.g., that AVE problems admit an equivalent description as Linear Complementarity problems (in short, LCP). The exact definitions of an AVE problem and a LCP are recalled below. Dealing efficiently with these problems is thus paramount.

The literature on this subject contains several theoretical results for existence as well as conditions guaranteeing uniqueness of the solution [START_REF] Lotfi | A note on unique solvability of the absolute value equation[END_REF][START_REF] Mangasarian | Absolute value equations[END_REF][START_REF] Rohn | On unique solvability of the absolute value equation[END_REF][START_REF] Rohn | An iterative method for solving absolute value equations and sufficient conditions for unique solvability[END_REF]. Concurrently, there are also various numerical approaches to solve an AVE problem. Generally speaking, these methods can be divided into at least three categories [START_REF] Alcantara | Method of alternating projections for the general absolute value equation[END_REF] : iterative linear algebra based methods (also known as projective methods), semi-smooth Newton-like methods and smoothing methods. The aforementioned methods generally require some assumption on the matrix involved in the AVE problem. In particular, the classes of P 0 -matrices and P -matrices (recalled below) turn out to be particularly relevant in this study [START_REF] Abdallah | Solving absolute value equation using complementarity and smoothing functions[END_REF].

In this work, we consider a natural generalization of (linear) AVE problems to nonlinear ones, known as Nonlinear Absolute Value Equations (in short, NAVE). This more general framework encompasses new applications including ridge regression models, bounded constrained nonlinear systems of equations, and stiff Ordinary Differential Equations (in short, stiff ODE). This approach to deal with the aforementioned problems, based on NAVE, is to the best of our knowledge, completely new in the literature.

Our main contribution is the following: we first show that similarly to the way that an AVE problem is linked to a LCP, nonlinear absolute value equations can also be associated to nonlinear complementarity problems (in short, NCP). Indeed, any NCP can be reformulated as NAVE. The converse is also true, but the association is generally given in an implicit way. Then, taking profit from the huge literature concerning existence, uniqueness and numerical resolution of NCP (see [START_REF] Hu | A note on absolute value equations[END_REF][START_REF] Mangasarian | Absolute value equations[END_REF][START_REF] Rohn | An iterative method for solving absolute value equations and sufficient conditions for unique solvability[END_REF][START_REF] Wu | A note on unique solvability of the absolute value equation[END_REF] e.g.), we propose a new method to solve a NAVE problem, based on the smoothing technique 1 proposed in [START_REF] Haddou | Smoothing methods for nonlinear complementarity problems[END_REF] and further developments in the follow-up work [START_REF] Osmani | A new smoothing method for nonlinear complementarity problems involving P 0 -function[END_REF]. The proposed approach is explained in Section 2, while in Section 3 we discuss applications.

To ease the reading we start with some definitions and settings. The Absolute Value Equality problem (in short, AVE) is defined as follows:

find x ∈ R d : Ax -|x| = b, (AVE)
where

A is a (d × d)-matrix and b ∈ R d . Throughout this work, given x = (x 1 , . . . , x d ) T ∈ R d , we use the notation |x| := (|x 1 |, . . . , |x d |) T componentwise to denote a vector in R d + .
Denoting by I the identity matrix of R d and assuming that either A -I or A + I is invertible, the (AVE) problem can be transformed to a Linear Complementarity Problem (in short, LCP). Indeed, setting (coordinate by coordinate)

y = x + = max { x, 0} z = x -= max {-x, 0} (1.1)
and performing the transformation x = y -z and |x| = y + z we obtain:

(A -I) y -(A + I) z = b.
Therefore for

M := (A + I) -1 (A -I) q := (A + I) -1 (-b) or respectively M := (A -I) -1 (A + I) q := (A -I) -1 b (1.2) we obtain z = M y + q 0 ≤ y ⊥ z ≥ 0 or respectively y = M z + q 0 ≤ y ⊥ z ≥ 0 (LCP)
The above problem can be solved provided M (respectively M ) is a P -matrix (see below for details).

It is important to notice that this property can be traced back to the matrix A; in particular, the property is ensured whenever the singular values of A are all greater than 1. Notice that this condition guarantees invertibility of both A -I and A + I.

Solving (LCP) under the assumption that M (respectively M ) is a P -matrix has been treated in several works (see [START_REF] Gharbia | Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix[END_REF]). In this case, it can be shown that the problem has a unique solution (ȳ, z) yielding that x := ȳ -z is the (unique) solution of (AVE). Moreover, this solution can be obtained numerically, via smoothing regularization techniques (see [START_REF] Abdallah | Solving absolute value equation using complementarity and smoothing functions[END_REF][START_REF] Haddou | Smoothing methods for nonlinear complementarity problems[END_REF][START_REF] Osmani | A new smoothing method for nonlinear complementarity problems involving P 0 -function[END_REF] and Section 2.3 below).

In this work, we propose a new method of solving a nonlinear generalization of (AVE), namely the following Nonlinear Absolute Value Equality problem (in short, NAVE)

Find x ∈ R d : F (x) -|x| = 0 (coordinatewise), (NAVE)
where F : R d → R d is a (nonlinear) mapping. By introducing new variables y = x + and z = x - (cf. (1.1)) so that x = y -z and |x| = y + z, (NAVE) becomes

F (y -z) -(y + z) = 0.
By setting z = H(y) (which is possible under regularity assumptions on F , see Lemma 2.5), we can transform (NAVE) to a Nonlinear Complementarity Problem (NCP):

H(y) = F (y -H(y)) -y 0 ≤ y ⊥ H(y) ≥ 0. (1.3)
As we shall see in Section 2.3, even though the function H is only defined implicitly, it is still possible to solve (1.3) numerically provided we are able to guarantee that H is a P 0 -map (see Definition 2.2), a notion which generalizes P 0 -matrices (c.f. Lemma 2.7).

2 Setting of the problem and description of the method

I ⊂ {1, 2, • • • , d}, det(A II ) ≥ 0 (respectively det(A II ) > 0); (ii) for every x = (x 1 , • • • , x d ) T ∈ R d , x ̸ = 0, max 1≤j≤d
(Ax) j x j ≥ 0 respectively max 1≤j≤d (Ax) j x j > 0 ;

(iii) for every I ⊂ {1, We refer the reader to [START_REF] Fiedler | On matrices with nonpositive off-digagonal elements and positive principal minors[END_REF][START_REF] Moré | On P -and S-functions and related classes of n-dimensional nonlinear mappings[END_REF] for further results about P 0 -and P -matrices and maps. We finish this section with the following useful lemma.

Lemma 2.4 (A characterization of P 0 -matrices). Let A be a (d × d) matrix. Then A is a P 0 -matrix if and only if, for every diagonal matrix ∆ 1 with strictly positive entries and for every nonnegative diagonal matrix ∆ 2 , the matrix ∆ 1 + ∆ 2 A is invertible.

Proof. Let A be a P 0 -matrix. Then for every diagonal matrix ∆ 2 with nonnegative entries, the matrix ∆ 2 A is also P 0 , while for every diagonal matrix ∆ 1 with strictly positive entries, the matrix ∆ 1 + ∆ 2 A is a P -matrix, therefore, in particular, it is invertible. Conversely, let us assume that A is not a P 0 -matrix. Then there exists v ∈ R d , v ̸ = 0 such that (Av) i v i < 0, for every i ∈ {1, • • • , d}.

(2.1)

Let ∆ 1 = diag(δ 1 1 , • • • , δ d 1 ) and ∆ 2 = diag(1, • • • , 1). Then (∆ 1 + ∆ 2 A)v = (δ 1 1 v 1 + (Av) 1 , • • • , δ d 1 v d + (Av) d ) T ,
and by setting, for every i, δ i 1 := -(Av) i /v i (which is well-defined and strictly positive thanks to (2.1)) we deduce that (∆ 1 + ∆ 2 A)v = 0 and therefore ∆ 1 + ∆ 2 A is not invertible. 2

Transforming a (NAVE) problem to a (NCP) problem

Given a nonlinear mapping F : R d → R d , we consider the (NAVE) problem

Find x ∈ R d : F (x) -|x| = 0.
By introducing new variables y = x + and z = x -so that x = y -z, |x| = y + z, y ⊥ z, the (NAVE) problem becomes

F (y -z) -(y + z) = 0. ( 2.2)
The following lemma gives conditions under which (2.2) may be written as a (NCP) problem by setting y = H(z) or z = H(y) for some suitable maps H or H. Lemma 2.5. Assume that the mapping F is C 1 in a neighborhood of the point x * = y * -z * ∈ R d which is assumed to be solution of (2.2). Then it holds:

(i). If F -I is a P 0 -map, then there exists a C 1 map H : R d → R d defined in a neighborhood of y *
such that z * = H(y * ) and y * is a solution to the following (NCP) problem:

H(y) = F (y -H(y)) -y 0 ≤ y ⊥ H(y) ≥ 0. (2.3) (ii). If -(F + I) is a P 0 -map, then there exists a C 1 map H : R d → R d defined in a neighborhood of z * such that y * = H(z *
) and z * is a solution to the following (NCP) problem:

H(z) = F ( H(z) -z) -z 0 ≤ z ⊥ H(z) ≥ 0. (2.4)
Proof. We consider the C 1 map F : R 2d → R defined by

F(y, z) = F (y -z) -(y + z).
We are going to apply the implicit function theorem at the point (y * , z * ) ∈ R 2d . Notice that

(∇ y F(y * , z * ), ∇ z F(y * , z * )) = (∇F (y * -z * ) -I, -∇F (y * -z * ) -I).
If F -I is a P 0 -map, then ∇F (x * ) -I is a P 0 -matrix by Lemma 2.3. Applying Lemma 2.4, we obtain that 2I + ∇F (x * ) -I = ∇F (x * ) + I is invertible. Therefore ∇ z F(y * , z * ) is invertible and, by the implicit function theorem, we obtain a map H such that (i) holds. Similarly, if

-(F + I) is a P 0 -map, then 2I -(∇F (z * ) + I) = I -∇F (z * ) = -∇ y F(y * , z *
) is invertible and we obtain a map H such that (ii) holds. 2

Remark 2.6. (i) The condition F -I (respectively, -(F + I)) being a P 0 -map is actually quite natural since it is exactly the requested assumptions to solve the (NCP) problem, see Section 2.3.

(ii) (NAVE vs AVE). At this stage, the reader may have already noticed an analogy with the (LCP) reformulation of (AVE). Indeed, if F (x) = Ax -b, then (NAVE) coincides with (AVE), and if either A -I or -(A + I) is a P 0 -matrix (which is automatically satisfied if, e.g., the singular values of the matrix A are greater than 1), then the functions H and H are explicitly given by the formulae

H(y) = M y + q and H(y) = M z + q,
where M, M , q and q appear in (1.2). Consequently, in this case it is possible to solve (AVE) as explained in the introduction.

Smoothing techniques to solve (NCP)

As already mentioned, even though the functions H and H are only implicitly defined, we can still solve (2.3)-(2.4) numerically (we shall do so below), whenever it is guaranteed that H, H are P 0 -maps. This is the aim of the following lemma, yielding a criterium based on F .

Lemma 2.7 (Guaranteeing P 0 -property for H, H).

(i).

If F -I is a P 0 -map, then so is H.

(ii). If -(F + I) is a P 0 -map, then so is H.
Proof. We now focus on the case of (2.3), the case of (2.4) can be adapted accordingly. Let

y 1 , y 2 ∈ R d , with y 1 ̸ = y 2 . We infer from (2.3) that 2H(y k ) = F (y k -H(y k )) -(y k -H(y k )) , k ∈ {1, 2}.
Setting

t k := y k -H(y k ), it follows 2H(y k ) = (F -I)(t k ).
Using the fact that F -I is a P 0 -map, we deduce that for some coordinate j = j(t 1 , t 2 ) ∈ {1, . . . , d}, we have 2 H(y 1 ) j -H(y 2 ) j (t j 1 -t j 2 ) ≥ 0, from which we infer

H(y 1 ) j -H(y 2 ) j (y j 1 -y j 2 ) -(H(y 1 ) j -H(y 2 ) j ) ≥ 0, yielding H(y 1 ) j -H(y 2 ) j (y j 1 -y j 2 ) ≥ H(y 1 ) j -H(y 2 ) j 2 ≥ 0.
This is the desired property for the map H.

2

To solve (2.3), we will apply the smoothing approach proposed in [START_REF] Haddou | Smoothing methods for nonlinear complementarity problems[END_REF] and more precisely the non-parametric technique introduced in [START_REF] Osmani | A new smoothing method for nonlinear complementarity problems involving P 0 -function[END_REF]. The overall approach of [START_REF] Haddou | Smoothing methods for nonlinear complementarity problems[END_REF] is based on functions θ satisfying the following properties:

• the function θ : R → (-∞, 1) is concave, continuous and nondecreasing;

• θ(t) < 0, for all t ∈ (-∞, 0), θ(0) = 0 and lim t→+∞ θ(t) = 1.

These functions are used as certificate of positivity, that is, they "detect" whether t = 0 or t > 0 holds in a "continuous way", in the sense of the following characterization:

t > 0 ⇐⇒ lim r→0 θ t r = 1.
The authors in [START_REF] Haddou | Smoothing methods for nonlinear complementarity problems[END_REF] used these functions to regularize the (nonsmooth) (NCP)

0 ≤ x ⊥ H(x) ≥ 0, (2.5)
by means of a sequence of smoothing systems (indexed by r > 0) of the form

G r (x, H(x)) = G r (x, H(x)) 1 , • • • , G r (x, H(x)) d T = (0, • • • , 0) T , (2.6)
where

G r (x, H(x)) i := rψ -1 ψ( x i r ) + ψ( H(x) i r ) with ψ := 1 -θ.
Then they eventually take the limit as r tends to 0.

Several convergence results have been established under the assumption that the problem has at least one solution and H is a P 0 -map. Although this approach is efficient numerically, it suffers from two drawbacks:

• There is no clear or optimal strategy to drive the parameter r to 0.

• The following ad hoc technical assumption on the function ψ has been used without rigorous explanation:

there exist a ∈ (0, 1) and R a > 0 such that:

ψ(t) 2 ≥ ψ 1 a t , for all t ∈ (R a , +∞). (2.7)
The first drawback has been addressed in [START_REF] Osmani | A new smoothing method for nonlinear complementarity problems involving P 0 -function[END_REF] by considering a larger system of equations

G r (x, H(x)) = (0, • • • , 0) T , 1 2 ∥x -∥ 2 + 1 2 ∥H(x) -∥ 2 + r 2 + εr = 0, (2.8)
where ε > 0 is some positive parameter. The second drawback will be the subject of the following result which proves that this technical assumption (2.7) corresponds to a well-known property.

Theorem 2.8 (asymptotic behavior). Let ψ : (0, ∞) → (0, ∞) be a convex decreasing function satisfying lim

x→∞ ψ(x) = inf ψ = 0.
The following assertions are equivalent:

(i). ( Lojasiewicz inequality at infinity) There exists c > 0 such that

lim inf x→∞ x|ψ ′ (x)| ψ(x) > c > 0.
(ii). There exist m, n > 1 and R > 0 such that:

ψ(x) m ≥ ψ(nx), for all x ∈ (R, +∞) (2.9)
(iii). For every m > 1 there exist n > 1 and R > 0 such that:

ψ(x) m ≥ ψ(nx), for all x ∈ (R, +∞)
Notice that the technical assumption (2.7) corresponds to (ii). Therefore, the above result shows that it is equivalent to assume that ψ satisfies the Lojasiewicz inequality at infinity. This latter condition is always satisfied if the function ψ is semialgebraic: Indeed, in this case, the corresponding Hardy field (that is, the field of germs of real semialgebraic functions at infinity) has rank one, and consequently, for any non-ultimately zero semi-algebraic function ψ in the single variable x, the function x → xψ ′ (x)/ψ(x) has a non-zero limit as x goes to infinity (see [7, Remark 2.9]). The same argument applies also for the more general case of functions ψ that are definable in some polynomially bounded o-minimal structure (we refer to [START_REF] Coste | An Introduction to o-minimal Geometry[END_REF] for the corresponding definitions).

Proof. (i)⇒(ii). Let us assume that (ii) fails. We define inductively a sequence

{y n } n ⊂ [1, +∞) such that lim n→∞ y n = +∞ and lim n→∞ y n |ψ ′ (y n )| ψ(y n ) = 0.
To this end, we set x 1 = y 1 = 1. From the contradiction argument, for every n ≥ 2, taking m = 1+ 1 n and R = y n-1 we obtain the existence of some x n > R such that for y n := nx n it holds

ψ(x n ) m < ψ(y n ) yielding ψ(x n ) ψ(y n ) -1 < m -1 = 1 n . ( 2

.10)

Using convexity we also deduce that

ψ ′ (y n ) ≤ ψ(x n ) -ψ(y n ) y n -x n = n n -1 ψ(x n ) -ψ(y n ) y n , whence, from (2.10), 0 ≤ y n |ψ ′ (y n )| ψ(y n ) ≤ n n -1 ψ(x n ) ψ(y n ) -1 < 1 n -1 .
Taking the limit as n → ∞ we conclude that (i) also fails to hold, which establishes the desired implication.

(ii)⇒(iii). Assume that (2.9) holds for some m 0 > 1, n 0 and R 0 > 1, that is, for all x > R 0 we have ψ(x) ≥ m 0 ψ(n 0 x). Then since n 0 x > x > R we also have:

ψ(n 0 x) ≥ m 0 ψ(n 2 0 x) yielding ψ(x) ≥ m 2 0 ψ(n 2 0 x).
We conclude that (2.9) also holds for m 1 = m 2 0 (under the choice of n 1 = n 2 0 and R 1 = R 0 ). Repeating this argument we deduce that (2.9) holds for all

m k = m k 0 , k ≥ 1 (taking n k = n k 0 and R k = R 0 ). Since m k → ∞,
in order to establish (iii) it is sufficient to observe that if (2.9) holds for some m > 1 (together with some n > 1 and R > 0) then it also holds for all m ∈ (1, m], since

ψ(x) m ≥ ψ(x) m .
(iii)⇒(i). Fix m > 1, n > 1 and R > 0 such that (2.9) holds and set

c := m -1 m 1 n -1 > 0.
Using convexity of ψ and (2.9), we deduce that for all x > R we have:

ψ ′ (x) ≥ ψ(x) -ψ(nx) nx -x =⇒ x|ψ ′ (x)| ψ(x) ≥ 1 n -1 1 - ψ(nx) ψ(x) ≥ c.
This establishes (i) and finishes the proof. 2

Remark 2.9. As already mentioned, assertion (i) ( Lojasiewicz inequality at infinity) holds true whenever the function ψ is semialgebraic (or more generally, definable in a polynomially bounded o-minimal structure). This already provides a broad assembly of examples of functions satisfying (i), together with straightforward criteria to detect easily whether the property holds, based on certificates of semialgebricity or o-minimality (see [6, Theorem 1.13] e.g.).

This being said, let us draw reader's attention to the fact that besides what is asserted in [7, Proposition 2.7], the assumption of polynomial boundedness is essential for the validity of (i). Indeed, as shown in [21, Remark 8], the convex function ψ(x) = (log(1 + x)) -1 is definable in the log-exp o-minimal structure but fails to satisfy (i).

Algorithm and numerical results

To solve the system of equation (2.8), we will apply the Newton-like method proposed in [START_REF] Osmani | A new smoothing method for nonlinear complementarity problems involving P 0 -function[END_REF]. However, since H is defined implicitly, we first need to reformulate the problem as follows:

       z -F (y -z) + y = 0 rψ -1 ψ( y i r ) + ψ( z i r ) = 0 i = 1 . . . d, 1 2 ∥y -∥ 2 + 1 2 ∥z -∥ 2 + r 2 + εr = 0, (2.11)
where the variable z plays the role of H(y).

Remark 2.10. In this new system of equations we assume that case (i) of Lemma 2.5 holds. (One can proceed in a similar way if (ii) holds.)

In the definition of the following algorithm, we set X := (y, z, r) T and

H(X) :=      z -F (y -z) + y rψ -1 ψ( y i r ) + ψ( z i r ) i = 1 . . . d, 1 2 ∥y -∥ 2 + 1 2 ∥z -∥ 2 + r 2 + εr (2.12)
so that (2.11) is reduced to H(X) = 0. This algorithm corresponds to a Newton method under a standard Armijo line search.

Algorithm

1. Chose X 0 = (X 0 , r 0 ), X 0 ∈ Ξ, r 0 = ⟨y 0 , z 0 ⟩/n, τ ∈ (0, 1/2), ϱ ∈ (0, 1). Set k = 0. 2. If H(X k ) = 0, stop. 3. Find a direction d k ∈ R 2n+1 such that H(X k ) + ∇ X H(X k )d k = 0. 4. Choose ζ k = ϱ j k ∈ (0, 1), where j k ∈ N is the smallest integer such that Θ(X k + ϱ j k d k ) -Θ(X k ) ≤ τ ϱ j k ∇Θ(X k ) T d k . 5. Set X k+1 = X k + ζ k d k and k ← k + 1. Go to step 2.
The merit function used in the line search corresponds to the square of the global error:

Θ(X) = 1 2 ∥H(X)∥ 2 .
To get a well defined algorithm, the initial point (y 0 , z 0 ) T must be an interior point, and the initial value for r must be positive r 0 > 0.

Applications

In this section we show that several problems, which can be naturally restated as (NAVE) and can be solved efficiently thanks to the above transformation. We present in this section numerical experiments, in which the smoothing functions are restricted to two specific cases

θ 1 (t) :=    t t + 1 , t ≥ 0 t, t < 0 and θ 2 (t) := 1 -e -t .
The numerical experiments are conducted in an ordinary computer. All program codes are written and executed in MATLAB R2023a. In Subsection 3.1 and 3.3, we employ a similar stopping criterion for every numerical method, by using a tolerance T ol = 1e -10 and fixing the maximum number of iterations to N max = 2000. Since the NAVE problems may have multiple solutions, in the following, the error will be computed by Error = ∥F (x approximate ) -|x approximate |∥ in Subsection 3.1 and respectively by Error = ∥F (x approximate ) -|x approximate | -b∥) in Subsection 3.3).

Ridge Regression

Ridge regression adds to the loss function L(x), x ∈ R d a penalty term in order to avoid overfitting: historical development and the applications in data science of ridge regression can be found e.g. in [START_REF] Hastie | Ridge regularization: An essential concept in data science[END_REF][START_REF] Hoerl | Ridge regression: A historical context[END_REF]. This penalty term usually consists of adding the squared magnitude of the coefficients (traditionally denoted by w).

We hereby consider an asymmetric ridge regression of the form:

min x∈R d    L(x) + d j=1 λ j max{x j , 0} 2 + µ j max{-x j , 0} 2    , (3.1)
where the penalization parameters λ j and µ j satisfy λ j -µ j ̸ = 0 for all j ∈ {1, • • • , d}. The case λ j = µ j = λ for every j corresponds to the classical ridge regression, which will not be considered here. On the other hand, the case λ j = 0 for all j and µ j > 0, corresponds to a penalization of the negativity of the coefficients, promoting solutions with positive coefficients. The necessary condition for optimality reads as follows:

∇L(x) + 2λ max{x, 0} -2µ max{-x, 0} = 0, where the two vectors λ max{x, 0} and µ max{-x, 0} are to be understood componentwise. Noticing that 2 max{x, 0} = |x|+x and 2 max{-x, 0} = |x|-x, we end up with the following (NAVE) problem

F (x) -|x| = 0 with F (x) = 1 µ -λ ∇L(x) + µ + λ µ -λ x (coordinatewise)
Therefore, one can solve the previous problem if either

F -I or -(F + I) is a P 0 -map, that is either (µ -λ) -1 (∇L + 2λI) or -(µ -λ) -1 (∇L + 2µI) is a P 0 -map.
To illustrate for asymmetric ridge regression, we consider the loss function

L(x) = 1 2 ∥Ax -b∥ 2 , where A ∈ R m×d and b ∈ R d . (3.2)
We performed numerical experiments, fixing λ j = λ and µ j = μ for every j ∈ {1, • • • , d}. These parameters, matrix A ∈ R m×d and vector b ∈ R d were randomly generated with values in [-5, 5].

As shown in Table 1, considering the average number of iterations with similar tolerance, using the function θ 2 is better, while in an exceptional case m = 20 > d = 10 and ( λ, μ) = (0, 100), θ 2 -smoothing performs worse. On the other hand, while the parameters λ and μ become greater, which can be compared to the ascent of the (classical) ridge parameter, θ 2 -smoothing performs within a better tolerance in a small number of iterations. To end this part, we give a heuristic observation on a sparse optimization problem (see e.g. [START_REF] Hastie | The elements of statistical learning. Data mining, inference and prediction[END_REF][START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF]). Let us consider the following problem min

x∈R d L(x) + λ∥x∥ 1 . (3.3)
The first order optimality condition for (3.3) has the form

0 ∈ ∇L(x) + λ ∂∥ • ∥ 1 (x), (3.4)
where the subdifferential of ℓ 1 norm can be written explicitly as

q ∈ ∂∥ • ∥ 1 (x) if and only if q i = sign(x i ), if x i ̸ = 0, |q i | ≤ 1, if x i = 0.
Using the fact that α sign(α) = |α| for every α ∈ R, the inclusion (3.4) can be transformed into x∇L(x) + λ|x| = 0 (coordinatewise).

The above equation just provides a necessary condition for optimal solution. In the following, we give a short numerical observation to guarantee its potential utility in sparse optimization. In order to apply results from previous sections, it is necessary to ensure that one of the following maps is a P 0 -map

- 1 λ x ∇L(x) -I and 1 λ x ∇L(x) -I.
In the following figures, we use the same quadratic loss function (3.2), where matrix A and vector b are randomly generated ranging from -1 to 1 and -0, 05 to 0, respectively. Figure 1 shows the behavior of each coefficient while increasing the tuning parameter λ > 0.

Nonlinear ordinary differential equations

A NAVE problem also naturally arises when we deal with a discretization of a nonlinear ordinary differential equation (ODE, for short) involving rough velocity, for example γ(t) = |γ(t)| as well as an ODE of the form Φ(X (2k) , X (2k-1) , . . . , Ẋ) = |X|

In this subsection we provide two examples (one being a stiff ODE) to illustrate the effectiveness of smoothing techniques when using finite difference schemes for ODEs.

Example 3.1. We consider a stiff ODE with initial value as follows ẍ + 1001 ẋ -1000|x| = 0, t > 0

x(0) = x 0 < 0, ẋ(0) = 0, (3.5)
whose exact solution is

x exact (t) = x 0 -1 999 e -1000t + 1000 999 e -t ≈ x 0 e -t .

Let us consider problem (3.5) in time domain I = [0, T ]. We use a uniform mesh t t t = (t i ), where t i = ih for i ∈ {0, • • • , N } and h = T /N , and the approximation solution will be x x x = (x i ) where x i ≈ x(t i ). For the first and the second derivative, we use the 2nd-order approximation

ẍ(t i ) ≈ x i-2 -2x i-1 + x i h 2 and ẋ(t i ) ≈ x i+1 -x i-1 2h .
Remarkably, at the final time, the first derivative ẋ(t N ) will be computed via the 2nd-order backward formula ẋ(t N ) ≈ (x N -2 -4x N -1 + 3x N )/2h. Since the initial velocity is zero, using 1st-order backward approximation, we note that x -1 = x 0 . The discretization of (3.5) can be written as Let us now make some comments on the utility of NAVE for boundary value problems: we consider a boundary value problem related to (3.5) ẍ + 1001 ẋ -1000|x| = 0, t ∈ (0, T ),

A A A = 1 h 2           1 0 0 • • • 0 0 0 -2 1 0 • • • 0 0 0 1 -2 1 • • • 0 0 0 • • • • • • • • • • • • • • • • • • • • • 0 0 0 • • • 1 0 0 0 0 0 • • • -2 1 0 0 0 0 • • • 1 -2 1           and B B B = 1 2h           0 1 0 • • • 0 0 0 -1 0 1 • • • 0 0 0 0 -1 0 • • • 0 0 0 • • • • • • • • • • • • • • • • • • • • • 0 0 0 • • • 0 1 0 0 0 0 • • • -1 0 1 0 0 0 • • • 1 -4 3           (
x(0) = x 0 < 0, x(T ) = y 0 ∈ R. (3.7)
In order to illustrate this case, we consider the time interval I = [0, 2] and exact solution is determined by x exact . Using similar time mesh as above, the first and second derivatives are approximate as follows

ẍ(t i ) ≈ x i-1 -2x i + x i+1 h 2 and ẋ(t i ) ≈ x i -x i-1 h .
Figure 3 shows the convergence rate for the boundary value problem (3.7). The smoothing technique used in this problem presents a better accuracy compared to the above initial value problem, which seems to be natural because of the stiffness of the problem (3.5). It is noteworthy that Figure 3 also depicts an expected convergence rate since we have used a first order approximation for ẋ.

i = f (t i ) for i ≥ 2 and b 1 = f (t 1 ) + x 0 h 2 and b 2 = f (t 2 ) - x 0 h 2 .
To illustrate for this example, we consider problem (3.8) with source term

f (t) = arctan(cos(πt)) -| cos(πt)| -π 2 cos(πt),
whose exact solution is x exact (t) = cos(πt).

Comparison of methods for NAVE

Instead of smoothing procedure considered in Section 2, one can solve a NCP via other numerical methods. In this subsection we give examples to compare the efficiency of four methods

• Newton-like method with smoothing functions θ 1 and θ 2 ;

• approximating by Soft-Max function, in which the main idea is to approximate the complementarity condition via the limit max i∈{1,••• ,d}

x i = lim r↘0 r log d i=1 e x i /r .
which have been widely used in many optimization problems, for example [START_REF] Rockafellar | Variational analysis[END_REF]Example 1.30], [START_REF] Li | An entropy-based aggregate method for minimax optimization[END_REF][START_REF] Li | A log-exponential smoothing method for mathematical programs with complementarity constraints[END_REF][START_REF] Nesterov | Smooth minimization of nonsmooth functions[END_REF];

• using interior point method, for example, one can find the use of interior point method for complementarity problems in [START_REF] Haddou | A generalized direction in interior point method for monotone linear complementarity problems[END_REF][START_REF] Iusem | An interior point method for the nonlinear complementarity problem[END_REF][START_REF] Kojima | A unified approach to interior point algorithms for linear complementarity problems[END_REF][START_REF] Potra | Interior-point methods for nonlinear complementarity problems[END_REF]. Now, in the following examples, we solve the system F (x) -|x| = b, especially, Example 3.4 and 3.5 can be found in [START_REF] Alcantara | A new class of neural networks for NCPs using smooth perturbations of the natural residual function[END_REF][START_REF] Kojimam | Extension of Newton and quasi-Newton methods to systems of PC 1 equations[END_REF].

Example 3.3. We consider F (x) = Ax, where T . We observe that the smoothing method (especially with θ 2 -smoothing function) is the most robust among the considered methods. In connection with convergence speed, the interior point method performs much less competitively than the others, while it only reaches 1e -2 after N = 2000 iterations. Another point that can be recognized from Table 2 is that the Soft Max method could only solve problems with small size, for example for problems in dimension N = 50 and N = 200 the singularities appear after less than 100 iterations.

A = tridiag(-1, 4, -1) ∈ R d×d , x * ∈ R d , b = Ax * -|x * |. (3.10) Example 3.4. F : R 3 → R 3 is defined by F (x) :=    2x 1 -2 2x 2 + x 3 2 -x 3 + 3 x 2 + 2x 3 + 2x

(a) θ 1

 1 -smoothing (b) θ 2 -smoothing.

Figure 1 :

 1 Figure 1: Problem in dimension m = 20 and d = 40.

  x x + 1001 1000 B B Bx x x -|x x x| = b b b, where A A A, B B B ∈ R N ×N is determined by

  3.6) Here, vector b b b = (b i ) ∈ R N is defined by b i = 0 for i ≥ 2, b 1 = x 0 (1/(1000h 2 ) + 1001/(2000h)) and b 2 = -x 0 /(1000h 2 ). In Figure 2.(a), we approximate the solution of equation (3.5) with initial condition x 0 = -1 and time interval I = [0, 5]. The finite difference scheme was computed with mesh size h = 0.05 and the error is 9.22e -4 when applying θ 1 and θ 2 smoothing funtions. To get convergence rate in Figure 2.(b), we apply difference mesh sizes in the same time interval I = [0, 1] and intial condition x 0 = -2.

  (a) Approximate solutions. (b) Convergence rate O(h 1/2 ).

Figure 2 :

 2 Figure 2: Solving equation 3.5

Figure 3 :

 3 Figure 3: Convergence rate O(h) for a boundary value problem

Figure 4 .

 4 (a) shows the approximate solution on the time interval I = [0, 1] with mesh size h = 0.0125. The error between θ 1 (resp. θ 2 ) approximation and exact solution is 0.06 (resp. 0.0725). Besides, Figure4.(b) displays convergence rate of the combination of finite difference scheme and the θ-smoothing applying for the associated NAVE problem. (a) Approximate solutions. (b) Convergence rate O(h).

Figure 4 :

 4 Figure 4: Solving equation 3.8.

  ) and Interior Point (denoted IP) method on the NAVE problem associated to Example 3.3-3.5. In the first example, the vector b is randomly generated with values in [-5, 5] and the problem is considered in dimensions d = 10, 50, 200. In Example 3.4 and 3.5, we respectively consider b 1 = (-1, -5, 10) T , b 2 = (9, -100, 10) T , b 3 = (200, 0, 900) T , b * 1 = (10, 10, -12, 0) T , b * 2 = (20, -100, -12, 1) T and b * 3 = (200, 10, -5, -5)

Figure 5 (

 5 Figure 5(a) and 5(b) display the performance time between different methods for Example 3.3 with the size n = 20 and Example 3.4, respectively. We did the observation with 50 samples and the vector b is randomly generated with values in[-10, 10]. At a first sight, the interior point method appears to be the slowest one in comparison with the other three methods. As shown in Figure5(a), the θ 1 -smoothing performs the best choice among all the methods. If we look carefully, in lower dimension as Example 3.4, the Soft Max and θ 2 -smoothing performs slightly better than θ 1 -smoothing method.

Figure 5 :

 5 Figure 5: Performance time.

  II the submatrix made up of the rows and columns of I.

	Definition 2.1 (P 0 -matrix and P -matrix). A matrix A is called a P 0 -matrix (respectively, P -
	matrix) if one of the following equivalent properties holds
	(i) for every

2.1 Definitions and preliminaries

Given a (d × d) matrix A and I ⊂ {1, 2, • • • , d}, we denote by A

Table 1 :

 1 Comparing (asymmetric) ridge regression with different smoothing functions

			Error	Iterations Running time(×e -2(s))
	( λ, μ)	(m, d)	θ 1	θ 2	θ 1	θ 2	θ 1	θ 2
	(0, 100)	(3, 10)	1.9e -11 7.3e -15 18	21	4.81	2.96
		(5, 10)	5.8e -11 1.3e -16 17	71	4.78	6.26
		(10, 10) 5.4e -11 1.9e -16 18	24	5.78	3.45
		(20, 10) 3.8e -11	3.5e -3 17 2000 4.94	819
	(200, 1000) (3, 10)	8.9e -11 1.4e -17 18	23	5.62	2.99
		(5, 10)	2.7e -11 3.6e -18 19	22	5.12	2.9
		(10, 10)	6e -11	2.7e -17 18	33	4.93	3.87
		(20, 10) 4.18e -11 1.2e -10 18	40	5.41	4.17

Table 2

 2 Example 3.5. F : R 4 → R 4 is defined by compares the four methods: smoothing method with θ 1 and θ 2 , Soft Max (denoted SM

	
	3 -3 3   .

Table 2 :

 2 Several methods to solve NAVE

	Error	Iterations

Acknowledgement. This work was initiated during a research stay of Aris Daniilidis and Trí Minh Lê to INSA Rennes (February 2023). These authors thank their hosts for hospitality. The first author acknowledges support from the Austrian Science Fund (FWF, P-36344-N).


Evelyne Benoit
email: evelyne.benoit@cea.frsciencesconf.org

Denis Servent

Jordi Molgó

Jordi Molgó The

The voltage-dependent

come

The voltage-dependent sodium channel : A well-known molecular target of saxitoxins (cyanotoxins), ciguatoxins and brevetoxins (phycotoxins)

Résumé

Because of its highly selectivity to Na ions, and activation and inactivation gating properties, the voltage-dependent sodium channel plays a fundamental role in generating and conducting action potentials. The channel alpha-subunit is a transmembrane protein composed of 4 domains (DI-DIV), each of them consisting in 6 segments (S1-S6). The segment S4 is responsible for the channel activation and the P loop, connecting S5 and S6, is involved in the channel selectivity. Receptor-sites for toxins have been identified on this alpha-subunit. Indeed, aquatic neurotoxins interacting specifically with this channel are widely distributed among the various organisms responsible for intoxications or envenomations. In particular, saxitoxins, gonyautoxins and derivates, a family of divalent and tricyclic cations produced by some dinoflagellates and cyanobacteria and responsible for Paralytic Shellfish Poisoning, interact with the receptor-site 1 of sodium channels, leading to pore blockade and thus to current and action potential inhibition. This is exemplified by an electrophysiological study of oyster cerebro-visceral nerve sensitivity to saxitoxin which decreases during recent exposure of bivalve mollusks to contaminated dinoflagellates in natural and, in a more subtle way, experimental environments, providing better understanding of the mechanisms associated with the contamination of bivalve mollusks and, therefore, of the means of detecting and counterbalancing this contamination (1). Ciguatoxins and brevetoxins, two families of cyclic polyethers produced by some dinoflagellates and responsible for Ciguatera Fish Poisoning and Neurologic Shellfish Poisoning, respectively, interact with the receptor-site 5 of sodium channels, leading to partly blockade of inactivation and thus to spontaneous and/or repetitive action potentials. Consequently, toxin-induced cell swelling occurs. This is exemplified by electrophysiological and confocal-imaging studies of toxin effects on vertebrate myelinated nerve fibers (2,3). ( 1 et al., J. Neurosci. Res., 1999, 55(6):666-673. (3) Mattei et al., Neuropharmacology, 2014, 85:417-426. Mots-Clés: Sodium channels, Biophysic properties, Action potential, Saxitoxins, Ciguatoxins, Brevetoxins, Cell swelling

  ) Boullot et al., Mar. Drugs, 2021, 19(7):380. (2) Mattei

  Evelyne Benoit * †1 , Denis Servent 1 , and Jordi Molgo 1 1 Université Paris-Saclay -CEA -Institut des sciences du vivant Frédéric Joliot, Département Médicaments et Technologies pour la Santé (DMTS), Service d'Ingénierie Moléculaire pour la Santé (SIMoS), EMR CNRS/CEA 9004, 91191 Gif-sur-Yvette, France


Nicolas Lamassiaude

Evelyne Benoit

Rómulo Aráoz

Armen Zakarian

Denis Servent

Jordi Molgó

Phycotox

The block of

The block of skeletal muscle nicotinic acetylcholine receptors caused by cyclic imine toxins can be antagonized by 3,4-diaminopyridine at isolated mouse neuromuscular preparation

Résumé

Cyclic imine toxins (CiTXs) are a worldwide-distributed family of marine macrocyclic phycotoxins comprising different groups of lipophilic compounds: gymnodimines (GYMs), spirolides, pinnatoxins (PnTXs), pteriatoxins (PteTXs), portimines, prorocentrolides and spiroprorocentrimine. CiTXs and acyl derivative products of shellfish metabolism contaminate and bioaccumulate in filter-feeding bivalves, edible mollusks and other marine invertebrates and, thus, represent a risk for shellfish consumers and a menace for wildlife conservation. All CiTXs interact and block, with different affinities, mature (α12βeδ) and embryonic (α12βγδ) nicotinic acetylcholine receptors (nAChRs) expressed in skeletal muscles. 3,4-Diaminopyridine (3,4-DAP) is a well-known K+-channel blocker that prolongs the presynaptic action potential and indirectly enhances Ca2+ entry into nerve terminals and, thereby, increases quantal ACh release from the neuromuscular junction. 3,4-DAP has been used effectively to treat muscular weakness in various human myasthenic syndromes. The aim of this work was to determine whether 3,4-DAP, which increases quantal ACh release, was able to reverse the action of CiTXs on skeletal muscle expressing α12βeδ nAChRs. The use of isolated mouse phrenic-nerve hemi-diaphragm muscle preparations allowed monitoring nerve-evoked isometric muscle contraction in the presence of GYM-A, PnTX-A, PnTX-G and PteTX-A and, afterwards, the action of 3,4-DAP (10-100 µM) in the continuous presence of the respective CiTXs. The results show that 3,4-DAP improves neuromuscular function in a time-and concentration-dependent manner and completely reverses the neuromuscular block caused by the CiTX studied. These results support the view that GYM-A, PnTX-A, PnTX-G and PteTX-A are competitive and reversible inhibitors of muscle-type α12βeδ nAChRs. In fact, CiTXs can be characterized as competing with the binding of ACh (the natural ligand) to the nAChR. The ability of 3,4-DAP to antagonize the action of CiTXs is related to the increased release of ACh that is able to displace the CiTXs from their respective nAChR binding sites.

  Nicolas Lamassiaude 1 , Evelyne Benoit 1 , Romulo Aráoz 1 , Armen Zakarian 2 , Denis Servent 1 , and Jordi Molgo * 1

	1 CEA -CNRS : ERL9004 -CEA, Université Paris-Saclay, Département Médicaments et Technologies
	pour la Santé, Service d'Ingénierie Moléculaire pour la Santé (SIMoS), Equipe Mixte de Recherche
	CNRS (EMR n°9004), F-91191 Gif sur Yvette, France
	2 University of California Santa Barbara -Department of Chemistry and Biochemistry, Santa Barbara,
	CA 93106, États-Unis


Gwenola Bertoluci
email: gwenola.bertoluci@ecp.fr

Bernard Yannou
email: bernard.yannou@ecp.fr

Danielle Attias
email: danielle.attias@ecp.fr

Emilie Vallet
email: emilie.vallet@logica.com

Bertoluci

Yannou

Attias

Vallet

A categorization of innovation funnels of companies as a way to better make conscious agility and permeability of innovation processes

Keywords: Innovation funnel, development funnel, product development, design process, innovation management

It is common in the Management Science and Design Engineering communities to represent the processes contributing to innovation in companies as a funnel or similar variants. It is assumed it is possible to represent an analogy to the stages of planning and idea generation (the so-called fuzzy frontend), conception generation, as well as idea and concept selection to end up with the very few emerging developed and launched products and services on the market. First, this analogy may feature different innovation process layers, each of them independently as well as the entire set of these innovation process layers. After a review of literature on this funnel representation, we show that this analogy may be meaningful to globally represent and discuss about some properties of the innovation capability of a company at different locations: the R&D process as well as a given NPD process. We further describe a survey carried out within 28 large European technological companies through 48 detailed face-to-face interviews. Our questionnaire has allowed us to observe some characteristic patterns in the innovation funnels. We finally propose a model of five innovation funnels varying by their shape, permeability of emerging ideas and agility in terms of innovation management. We also hypothesize that these 5 funnels evolve in a sequential and cyclic way and that our cyclic model may be used as a questioning tool for the continuous improvement of the innovation management.

Introduction to funnel representations

Looking for ideas for an individual or group to document the resolution of a problem implements a cognitive process [START_REF] Brabandere | Le plaisir des idées. Libérer, gérer entrainer la créativité au sein des organisations[END_REF] of divergence and convergence. This is in this divergence part of ideation that creativity tools are solicited. This second convergence part is often represented as a synthesis funnel (see [START_REF] Deschamps | Product juggernauts -How companies mobilize to generate a stream of market winners[END_REF] and Figure 1) in which ideas are selected, recombined or eliminated to result in the very few selected ideas that merit to be further detailed.

Figure 1. Idea Funnel [2]

Design exploration process is an important part of design creativity and novelty [START_REF] Gero | An exploration based evolutionary model of a generative design process[END_REF]. The design activities in conceptual design are contained in two kinds of steps: divergent and convergent [START_REF] Cross | Engineering Design Methods -Strategies for product design[END_REF][START_REF] Pugh | Total Design: Integrated methods for successful product engineers[END_REF][START_REF] Roozenburg | Product Design: Fundamentals and Methods[END_REF]. Cross [START_REF] Cross | Engineering Design Methods -Strategies for product design[END_REF] thought of the conceptual design process as mostly being convergent with the necessity to contain a deliberate divergence in the search for novel ideas (see Figure 2).

Figure 2. The conceptual design process defined by Cross [4]

Pugh's model [START_REF] Pugh | Total Design: Integrated methods for successful product engineers[END_REF] for conceptual design and the definition of the convergence and divergence activities can be represented as on Figure 3. Pugh mentioned that it is essential to carry out concept generation and evaluation in a progressive and disciplined manner so as to generate better designs. This progressive and disciplined manner is illustrated as an iterative, repeated divergent and convergent process with the number of solutions gradually decreased (see [START_REF] Liu | Towards and 'ideal' approach for concept generation[END_REF]).

Figure 3. Pugh's conceptual design process [5]

This representation of the progressive reduction of the possible design space has been extended by various authors [8; 9] to take into account the development of new technologies whenever a new technology is a key lever of innovation. Wheelwright et al. note that the companies that supply these funnels by R & D (Figure 4a) on technologies, processes and products also extend the scope of the funnel to bottom-up uses (Figure 4b) to identify and filter out new ideas from a strategic market analysis. The two situations of convergent part of an ideation process (innovative process) and technology push or market pull representations (strategic innovation management) are very different. Whether one refers to very general models such as the Chain Linked of Kline and Rosenberg [START_REF] Kline | An overview on innovation, in the positive sum strategy[END_REF] and the Stage and Gates of Cooper [START_REF] Cooper | Stage-gate system: A new tool for managing new products[END_REF], or more detailed and structuring processes proposed in design engineering [12-15; 9], this analogy of forward selection and progressive shrinking of the design space appears to be a highly interpretative task. However, it is very well illustrated by Wheelwright and Clark [START_REF] Wheelwright | Revolutionizing Product Development[END_REF] who clearly associate it with the product planning stage preceding that of product development (Figure 5). These representations in funnels do not aim to facilitate the structuring of a process of innovation but to illustrate how an organization has the means to open and close its creative space and thus its products space. In this sense, to interrogate the businesses associated with the innovation process on how they actually process opens or closes to integration of new ideas and new opportunities, throughout a development process, is a way to identify how this funnel is actually generated. It is a question asked on the innovative organization behind that could lead to a continuous improvement of the innovation management. The objective of this paper is to propose a tool for the continuous improvement of the innovation management in companies based on a funnel categorization obtained after an innovation survey in 28 large companies.

Bertoluci, Yannou, Attias, Vallet

Survey on innovation in large companies and lessons learned

In a recent survey of 28 large European companies in the industry, we investigated the state of practice in innovation and innovative organizational models in large companies. This survey has provided qualitative and quantitative results which have been reported in a book [START_REF] Cuisinier | Un nouveau regard sur l'innovation -Un état des pratiques et des modèles organisationnels dans les grandes entreprises[END_REF]. We interviewed 48 R & D or innovation directors by asking them to self-diagnose their business practices according to the five management areas that contribute to value creation: strategy and business intelligence, organization of R & D, management of innovation processes, innovation culture and management of human resources and R & D, measurement of innovation performance. Our learning are numerous and sometimes surprising. We report hereafter just a few of them to contribute to this paper.

Two thirds of respondents reported having profoundly transformed or reorganized their R & D over the past three years. For reasons to support the international expansion, pooling and centralization of research upstream, location in the business unit of applied research and development or reorganization of the development process and resource allocation of R & D. These reorganizations are made in trial and error mode (no apparent method) and reflect a search for greater innovation performance. Indeed, companies face a real difficulty in measuring performance and the benefits of innovation, investment in research that results often lately by the market launch of innovative products and services. Management indicators of innovation or value creation are often of "rear-view mirror" type like the number of patents rather than of "looking ahead" type (able to monitor the value increasing).

Finally, the companies say that the upstream processes of ideas management are poorly organized. Indeed, 47% of companies do not use a methodology for generating ideas. The methods used are the idea boxes and idea contests without, in most cases, budget for the exploitation of good ideas that emerge. Also appalling, the only methods of generating ideas and driving innovation that are sometimes referred by high-level managers are TRIZ and Design to Cost and Objectives.

The companies surveyed acknowledge the fact that the so-called "innovation process" of a company is actually a series of strata or four processes (see Figure 6 which is our own representation) with interconnections but acting at different times, with specific strategies, roadmaps and different but interdependent budgets. These four processes are:

1. The process of ideas generating on products, technologies, processes or organization, 2. That of research or technology management 3. That of product lines or programs management or planning 4. The very activity of project management of New Product Development (NPD), which supplies the market with new offers and contributes largely to the creation of business value.

Figure 6. Modeling innovation or value creation processes in companies

It may be noted that a number of business support processes such as marketing, customer relations, after sales service, purchasing and competitive intelligence also Bertoluci, Yannou, Attias, Vallet contribute more indirectly to the increased degree of effective innovation of the company's products. Note also that according to the ideas (nature, size, maturity), process #1 of Ideas Management can feed processes #2, #3 and #4. All this must necessarily be organized within the company with the collection process of ideas and transfer of ideas within mature roadmap that invest and plan their development and their deployment in research, product lines or project development. However, these transfer processes are currently poorly organized and coordinated so that the process of generating and collecting ideas as we have seen. But there are organized and standardized processes within the company such as product development. These are step by step processes with intermediate outcomes expected, so-called "stage and gate". It turns out that these processes are as well necessary to ensure a minimum quality and coordinate development activity on a complex project, as sometimes too rigid and not very permeable to new ideas and opportunities that would upset too much a strategic positioning or that would appear during the project.

In our book [START_REF] Cuisinier | Un nouveau regard sur l'innovation -Un état des pratiques et des modèles organisationnels dans les grandes entreprises[END_REF] we have thus classified the 28 surveyed companies into 5 categories of innovation funnels (there are 6 companies per category in average), considering the characteristics of the whole 4-layer innovation process of Figure 6 after the three general properties of shape, permeability to emerging ideas along the process and process agility. This classification has been made by us, the 10 researchers having contributed to interview the company managers.

We have baptized them: the funnel "standard, but infertile", the funnel "standardized with high attrition", the "heroes' mode" funnel, the funnel "mixed (or dual device)", the funnel "agile and permeable". We have also graphically represented them in simple and expressive pictorials with small circles for ideas and contours for the shape (see Figure 7). "standard, but infertile" "standardized with high attrition" "heroes' mode"

"mixed (or dual device)" "agile and permeable"

The "standard, but infertile" funnel

For this funnel, few ideas and innovative proposals are selected upstream. The process R & D is classical and relatively heavy. It usually results in a limited number of development projects that generally go until the completion; it is not very selective. This model is found in sectors such as aeronautics, submitted to severe constraints of technical reliability in operation and intense capital investments. It can also be found in the energy sector, a sector where a R & D Director said: "Today the results will kill creativity; R & D is today is a super design department".

The main characteristic of firms adopting this funnel is to have a limited number of ideas in the sequence generation / collection. However, the steps of selection / maturation and launch / development are standardized and instrumented (Stage & Gate, TRL-Technology Readiness Levels -project mode...). Despite a cumbersome process, the dropout rate of development projects is low, once the concept validated and the decision to develop the product made.

These companies are mainly technology companies where the product renewal period is long (more than 10 years) and where the type of innovation is "product" dominant. However, some companies doing predominantly "product" innovation may refer to other funnel models.

The competitive intensity corresponds to relatively oligopolistic markets which, even if they evolve with new entrants, do not change they belong to the exclusive club of leaders in their field.

The "standardized with high attrition" funnel

Here, the process Research and Development (TRL, Stage & Gate) is unique, classic and relatively heavy, with progressive selection and strong attrition of the proposals. In this model, it is difficult to stop the projects launched once they have passed the stagegate -of product development. This funnel is found in sectors such as pharmacy or mass retailing where the selection of ideas for innovation is strong before starting the process of development itself.

In this model, many ideas are killed as they pass upstream phase (vision / selection / feasibility of innovation concepts), sometimes despite an abundance of leads and ideas for innovation in this phase. For the transition phase in product development phase, the company takes the minimum possible risk and projects that pass this stage are then under control. But as explained by a Director of Research, Technology and Innovation, "Risk reduction is the anti-innovation. The goal is not to reduce risks, but to manage them. The difficulty comes from people who want to reduce the risks".

However, the development projects initiated are not arrested or very little even when they no longer meet the original expectations: "I have a project in mind. When I arrived ten years ago, people said "It's been ten years since we talk of it", it's still there! ".

These companies face a double problem. First, how to reduce the number of tracks to explore and to evaluate in upstream stage -which has a cost -to focus on the most promising? Then, how to accept anyway to take risks, knowing that establishing sales forecasts of innovation on the market is both a delicate task and a choke point? In other words, how not to "sterilize" automatically waiving any idea if its business case is not solid in terms of apparent ROI, given that the expected revenue is often not accurate?

The "heroes' mode" funnel

The "heroes' mode" funnel makes coexisting a standardized funnel with a heroic mode. It is a R & D process (Stage & Gate) classic that can turn out to be cumbersome with a progressive selection of ideas and difficulty to kill the projects once they started. It is Bertoluci, Yannou, Attias, Vallet characterized by a weak support to potential innovations proposed by the field and which have failed to take the step of selecting initial ideas. The innovations are defended by tenacious individuals with strong personalities that sometimes succeed to make their ideas acknowledged by others and to put them into an official project portfolio.

Companies in this scheme feed well the funnel in ideas in the upstream phase. But there may be two reasons for not ensuring a good transfer from upstream phase to downstream phase: 1) A R & D process too cumbersome, judged too bureaucratic and procedural or 2) conversely, a lack of a real ideas selection process.

Innovations that pass this barrier are supported for some literally "overreach" by the holders of ideas, which we called the "heroes" and who, with tenacity and by using their internal network, particularly among the bosses of business units, manage to insert their idea into the mainstream product development.

The "mixed (or dual device)" funnel

As its name suggests, this funnel combines two processes. On the one hand, a conventional process of Research and Development (TRL type, stage & gate...) works, but it can be cumbersome. It is often keyed to the yearly budget. Once the candidate ideas issued, it works more in "top down" mode. Its main features are a progressive selection and difficulty to kill projects launched. On the other hand, the process is light, but institutionalized, organized and resourced to capture the ideas and proposals. It is "bottom up", which gives real resources to support potential innovations, giving the possibility to impact the official portfolio of research and development projects.

This funnel consists in putting another competing device in parallel of the standard R & D process (standardized funnel). This parallel process encourages the expression and development of ideas, if possible "out of the box". It is light, rather "bottom up", but well processed and sequenced. It is generally funded fairly "light".

Conditions to help ideas holders are implemented effectively, albeit on a modest scale in comparison with the official process. They can take different forms: a department dedicated to breakthrough projects and exploration of new growth territories, small committees with financial resources which support the evolution and development of the idea, fund dedicated to disruptive innovation... In the best case, an idea supported and emerging from this parallel device may reinstate the traditional process, or even take the place of a program or development project already in the portfolio.

These models are very new in the organizations we met. Some have produced tangible results, that is to say that ideas have been supported and reintegrated into the process of a traditional project. However, none has yet succeeded in bringing an innovation project standalone, ready to integrate the portfolio of projects issued from the official planning.

The "agile and permeable" funnel

Here, the innovation process is instrumented and institutionalized to generate and capture ideas constantly. The whole organization -not only the functions dedicated to Research and Development -and its culture are adapted to support the ideas and give them means. The permeability of the funnel acts both for "input" and "output": stopping of the project, outsourcing of a part of the cycle, selling the idea and the first results obtained for continuing the development by a third party, etc.. The engagement process of the projects is disconnected from the annual budget process for more flexibility while roughly maintaining the budgets allocated to them.

This funnel that one can qualify of "ideal" is pretty close to the previous. When the "dual device" opens a new avenue for innovation, this funnel seeks to open innovation to all disciplines (research, engineering, marketing, design, sociology, risk management, regulatory watch...) and to external partners, from the upstream stage of the process (exploration of innovation fields).

Let us hypothesize an evolution law in a 5-funnel cycle

An evolution law of companies in a 5-funnel cycle

We have also observed that these different forms of funnel tend to be on a sequential series which is even cyclic. Indeed, the surveyed companies described their 3 to 5 years past and were entitled too to describe their idealized future in terms of innovation management. Therefore, we experimentally hypothesize that there is a natural law of evolution like it exists in TRIZ theory for technical systems [18; 19].

We define these five stages of evolution of a company in terms of innovation management maturity as:

• The start-up, spontaneously permeable and agile • The growing company that tends to standardize processes • The healthy reaction to the normalization: the heroes that defend innovations • The awareness of the need to establish mechanisms that promote innovation "out of the box" • The organization of agility In more details, the 5 stages are: 1. Stage 1: At the beginning of a company, at the stage of start-up, the involvement of the founders, the small size of teams and the low volume of activities make that an oral culture is adequate. The whole company is spontaneously committed, led by leaders heavily involved at the operational level, to ensure the output of innovations. The funnel is naturally agile and permeable (or "ideal") without the need for formal processes.

Stage 2:

The growing company creates specialized functions and provide them with dedicated resources. The implementation of processes, operating rules, management tools is needed to control the volume of activity and resource use. The company becomes "technocratic" and sometimes "bureaucratic". A standardized funnel is then implemented. Depending on the types of innovation practiced and sectors concerned, the standardized funnel can be "infertile" (number of ideas for innovation low, often linked to highly technical products and processes and to their renewal duration) or, on the contrary, can be of "high attrition".

Stage 3:

To fight against the negative effects of this form of selection, heroes appear, which personally defend innovative ideas that have failed to pass the formal selection process and eventually turn into real success stories. 4. Stage 4: Companies capitalizing on these successes and eventually recognizing the value of one or more parallel channels to the formal and standardized

Bertoluci, Yannou, Attias, Vallet selection process, finally put in place a dual system by putting them in competition and, at best, in making them cooperate and exploiting synergies. 5. Stage 5: At the ultimate stage, companies are able to merge all the channels of innovation in addressing innovation transversely to functions, approaching it from a multidisciplinary perspective, identifying and exploiting at best external sources of innovation or the value of their Research and Development. They manage to implement, on an industrial scale, an ideal, organized and equipped, agile and permeable funnel, returning to the virtues of roots. In practice, companies in our study [START_REF] Cuisinier | Un nouveau regard sur l'innovation -Un état des pratiques et des modèles organisationnels dans les grandes entreprises[END_REF] are almost all in stages 1 to 4; only a few have some characteristics of the ultimate stage 5. This clearly reveals how much progress still to implement a process for ideas and projects management that is not too rigid while being sufficiently organized. The challenge, in our opinion, for the company that wants to be fully innovative is to get to stage 5, at least for innovations that are not strictly incremental. To be truly innovative as it grows, the company must recover the dynamics and virtues of its beginning as illustrated by Figure 8 of the evolutionary cycle of the five funnels.

How to find the agility and creativity of the origins?

It is not mandatory at all to evolve towards the next stage of innovation funnel for a company. But one believes that, like the TRIZ evolution laws of technical systems [18; 19], making people conscious of the innovation funnel their company is likely to be close to is already fruitful for them to visualize their company process and start discussions about what today contributes to the funnel shape, permeability and agility. Each people can also try to imagine how to personally interpret this innovation funnel.

In the case where the company is not satisfied with innovation management and performance, we propose to use the previous evolution law as a tool for continuous improvement. A creative workshop can be organized as follows:

A categorization of innovation funnels -Gather a short-list of some players representing the ideas and projects management processes in the company (generation, selection, development, managers).

-Make them positioning their business on the 5-funnel cycle. Make them express the reasons to be at a given location and try to result in a consensus for the whole company.

-Then, lead a brainstorming session on how to move from the present company funnel to the next stage.

-Work to a strategic and operational

Conclusion

It is common in the Management Science and Design Engineering communities to represent the processes contributing to innovation in companies as a funnel pictorial. We noticed that it could be used in several situations: representing the ideation process, as well as more strategic innovation processes. We propose to use the funnel representation as a holistic representation of the 4-layer processes that well model innovation or value creation processes in companies (see Figure 6).

Our survey on innovation practices in 28 large companies [START_REF] Cuisinier | Un nouveau regard sur l'innovation -Un état des pratiques et des modèles organisationnels dans les grandes entreprises[END_REF] has led to the observation that the innovation funnels of these companies can be categorized into 5 funnel types differentiated by their shape, permeability to ideas and process agility, and that they could be easily sketched as meaningful pictorials (see Figure 7). Our surveyed companies also learnt us that the past or the expected future of the companies let us think that the 5 funnel types follow a sequential and cyclic evolution law, as in TRIZ theory.

We finally propose to use the 5-funnel model as an inspiring tool for making people conscious of the innovation processes of their company and discussing of it. In addition, they can use it in a creativity workshop to imagine a strategic and operational roadmap for making their company evolving from one funnel stage to the next. These tools are being tested in companies and they truly appear insightful.

  (a) Funnel of technology push (b) Funnel of market bottom up Figure 4. Funnel representations of Wheelwright [9]

Figure 5 .

 5 Figure 5. The funnel development process of Motte et al. [16], adapted from Wheelwright and Clark [9]These representations in funnels do not aim to facilitate the structuring of a process of innovation but to illustrate how an organization has the means to open and close its creative space and thus its products space. In this sense, to interrogate the businesses associated with the innovation process on how they actually process opens or closes to integration of new ideas and new opportunities, throughout a development process, is a way to identify how this funnel is actually generated. It is a question asked on the innovative organization behind that could lead to a continuous improvement of the innovation management. The objective of this paper is to propose a tool for the continuous improvement of the innovation management in companies based on a funnel categorization obtained after an innovation survey in 28 large companies.

Figure 7 .

 7 Our model of five innovation funnels 3 Definition of 5-funnel model and correlations with company features

Figure 8 .

 8 Figure 8. The evolutionary cycle of the five funnels


Olivier Cots

Rémy Dutto
email: remy.dutto@orange.fr.

Sophie Jan

Serge Laporte

Geometric preconditioner for indirect shooting and application to hybrid vehicle

Keywords: Pontryagin's maximum principle, Indirect shooting, Geometric preconditioner, Mathieu transformation, Costate interpretation, Hybrid electric vehicle

In this article, we are interested in the hybrid electric vehicle torque split and gear shift problem, which can be formulated as a classical Lagrange optimal control problem with fixed initial condition. The Pontryagin's maximum principle gives necessary optimality conditions adjoining to the state a covector called costate. Thus, the optimal state trajectory has to be found among the projections of the lifted trajectories, called Pontryagin extremals, given by the maximum principle. The indirect simple shooting method aims to compute Pontryagin extremals reducing the resolution to the research of the initial costate. Classically, a Newtonlike solver is used to compute zeros of the so-called shooting equations. The main drawback of this method is its sensitivity to the initial guess. Therefore, a good initial guess need to be given to make the Newton solver converge, which is not an easy task in practice. We propose a preconditioning method of the shooting function based on a geometrical interpretation of the costate, in relation with the reachable set of the extended system and the underlying symplectic structure. We numerically show that this method reduces the number of iterations of our solver. Remarkably, in our experiments, it is better to use the preconditioner than to provide an approximation of the costate solution.

Introduction

In this article, we consider the Hybrid Electric Vehicle (HEV) torque split and gear shift problem, where the goal is to determine the optimal torque split between the Internal Combustion Engine (ICE) and the Electric Motor (EM) which minimizes the fuel consumption, the initial and final State Of Charge (SOC) of the battery being fixed. The industrial model is given by Vitesco Technologies. This model requires data as the requested torque at each time: for the experiments, we consider the Worldwide harmonized Light vehicles Test Cycle (WLTC), which is one of the most used cycle for fuel consumption and pollutant emission evaluations. Motivated by a new method based on a bilevel decomposition of the optimal control problem and presented in [START_REF] Cots | A bilevel optimal control method and application to the hybrid electric vehicle[END_REF], we consider only the first 100 seconds of the cycle.

This problem can be formulated as a classical Lagrange optimal control problem with simple limit conditions. The Pontryagin Maximum Principle (PMP) gives necessary optimality conditions lifting the optimal trajectory to the cotangent space and leads (under some hypotheses) to the resolution of a Two-Point Boundary Value Problem (TPBVP). The most classical method to solve a boundary value problem is the indirect simple shooting, whose goal is to find a zero of the simple shooting function, the variable of the shooting function being the initial costate of the lifted trajectory. This resolution can be done with a Newton-like solver. We present in Figure 1 a state-control trajectory obtained by shooting for the problem we consider. A drawback of the indirect simple shooting method is that a good initial guess needs to be provided to make the solver converge. This is not trivial in practice. To overcome this sensitivity issue, some methods have been developed such as indirect multiple shooting for instance (see [START_REF] Bock | A Multiple Shooting Algorithm for Direct Solution of Optimal Control Problems[END_REF]).

In this article, we propose a new method to reduce the sensitivity, and so to improve the convergence of the Newton-like solver. This method is a geometric preconditioner of the shooting function, and it is constructed using the Mathieu transformation applied to a change of variable of the extended state. This change of variable is constructed based on a geometrical interpretation of the costate and corresponds in our case to the affine transformation of an ellipse to a circle.

The article is organized as follows. The optimal control problem is formulated in Section 2. The Pontryagin Maximum Principle and the indirect simple shooting are recalled in Section 3. The construction of the proposed geometrical preconditioner of the shooting function is presented in Section 4, and the results are shown in Section 5. Section 6 concludes the article.

Optimal control problem

We consider the HEV torque split and gear shift problem described in details in [START_REF] Cots | A bilevel optimal control method and application to the hybrid electric vehicle[END_REF]. This problem can be written into the following Lagrange Optimal Control Problem:

(OCP)                min x,u t f t0 f 0 t, x(t), u(t) dt, s.t. ẋ(t) = f t, x(t), u(t) t ∈ [t 0 , t f ] a.e., u(t) ∈ U(t), t ∈ [t 0 , t f ], x(t 0 ) = x 0 , x(t f ) = x f ,
where the goal is to find the optimal (absolutely continuous) SOC trajectory x ∈ AC([t 0 , t f ], R) and the optimal (essentially bounded) control u ∈ L ∞ ([t 0 , t f ], R 2 ). The control is composed of the gear and the torque split between ICE and the EM. The two functions f 0 and f , which respectively correspond to the instantaneous fuel consumption of the ICE and the SOC deviation, are supposed to be of class C 1 . The control domain U(t) ⊂ R m is a non-empty set for all t ∈ [t 0 , t f ] and corresponds to the physic limitations (discrete gear, ICE and EM rotation speed. . . ). The initial x 0 and final x f states are fixed, as well as the initial t 0 and final t f times. This optimal control problem is non-autonomous (due to the time dependency of the functions f 0 and f ) because the requested wheel torque and rotation speed are obtained with the cycle (and some information of our HEV).

To transform the problem from Lagrange to Mayer form, we define the extended state x = (x 0 , x) where x 0 corresponds to the cost trajectory:

ẋ(t) = f t, x(t), u(t) ,
with f (t, x, u) = f 0 (t, x, u), f (t, x, u) the extended system. The initial extended state is set to x0 = (0, x 0 ). In order to recover the cost x 0 and the state x from an extended state x = (x 0 , x), we define the canonical x-space projection π x (x) = x and x 0 -space projection π x 0 (x) = x 0 . The final state condition becomes π x x(t f ) -x f = 0. From now on, we drop the ˜on variables to simplify the notations, keeping in mind that x(t) ∈ R 2 stands for x 0 (t), x(t) ∈ R 2 and f for (f 0 , f ).

For any control law u, we define the mapping u → x(u) as the solution at time t f of the Cauchy problem

ẋ(t) = f (t, x(t), u(t) , t ∈ [t 0 , t f ] a.e., x(t 0 ) = x 0 .
This permits us to define the admissible control set U as the set of commands

u ∈ L ∞ ([t 0 , t f ], R 2 ) such that for all t ∈ [t 0 , t f ], u(t) ∈ U(t)
, and such that x(u) is well defined. The reachable set is then given by A = x(U).

Figure 2 shows the reachable set A associated to (OCP). It is a non-empty closed convex set and we assume that x f ∈ π x (A). In this frame, there exists a solution for Problem (OCP) and a necessary optimality condition for a pair (x, u) is that x(t f ) ∈ ∂A, the boundary of A. 3 Necessary optimality conditions

Pontryagin Maximum Principle

According to the Pontryagin Maximum Principle (see [START_REF] Cesari | Statement of the Necessary Condition for Mayer Problems of Optimal Control[END_REF][START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF]), if the pair (x, u) is a solution of (OCP), then there exists a nontrivial costate trajectory p ∈ AC([t 0 , t f ], R 2 ), π p 0 p(t 0 ) ≤ 0, such that the pair (x, p) with the control u, for almost every t ∈ [t 0 , t f ], follow the pseudo-Hamiltonian dynamics:

ẋ(t) = ∇ p h t, x(t), p(t), u(t) , ṗ(t) = -∇ x h t, x(t), p(t), u(t) , (1)
and satisfy the maximization condition:

h t, x(t), p(t), u(t) = max w∈U(t) h t, x(t), p(t), w , (2)
where h(t, x, p, u) = p f (t, x, u) is the pseudo-Hamiltonian and where for all p = (p 0 , p) ∈ R 2 , π p 0 (p) = p 0 represents the p 0 -space projection and π p (p) = p represents the p-space projection. We remark that the costate associated to the cost is constant since f does not depend on the cost. Hence, we can define π p 0 (p) = π p 0 (p(t 0 )) for such a costate. An extremal is defined as a couple (z, u), with z = (x, p), such that the state

x ∈ AC([t 0 , t f ], R 2 ), the costate p ∈ AC([t 0 , t f ], R 2 ) is not trivial and π p 0 (p) ≤ 0, the command u ∈ L ∞ ([t 0 , t f ], R 2 )
satisfies the constraint u(t) ∈ U(t) and such that (x, p, u) satisfies ( 1) and ( 2). A BC-extremal is an extremal that satisfies the boundary conditions x(t 0 ) = x 0 and π x x(t f ) = x f . Finally, an extremal is said to be normal if π p 0 (p) < 0 and abnormal if π p 0 (p) = 0.

For the sake of simplicity, we consider that for any extremal (z, ū) the maximized pseudo-Hamiltonian provides a true Hamiltonian

H t (z) = max w∈U(t) h(t, x, p, w)
well defined and smooth (which means at least C 1 ), for almost all t ∈ [t 0 , t f ] and for all z in a neighborhood of z(t). Under this assumption, the point (z, u) is an extremal of (OCP) if and only if p ̸ = 0, π p 0 (p) ≤ 0 and for almost every t

∈ [t 0 , t f ] ż(t) = #» H t, z(t) ,
where H(t, z) = H t (z) and #» H(t, z) = ∇ p H(t, z), -∇ x H(t, z) is the Hamiltonian vector field.

Numerical methods

Under the previous assumption, that is in the Hamiltonian frame, the necessary optimality conditions given by the Pontryagin Maximum Principle lead to the resolution of the following Two-Point Boundary Value Problem:

(TPBVP) ż(t) = #» H t, z(t) , t ∈ [t 0 , t f ] a.e., x(t 0 ) = x 0 , π x (x(t f )) = x f .
The classical numerical method to solve (TPBVP) is the indirect shooting method. The goal is to find a point where the shooting function S : R -× R → R defined by

S(p) = π x exp #» H (x 0 , p) , is equal to x f ,
where we define π x (x, p) = π x (x) and where exp #» H (z 0 ) corresponds to the solution at time t f of the following Cauchy problem:

ż(t) = #» H t, z(t) , t ∈ [t 0 , t f ] a.e. z(t 0 ) = z 0 .
Let us remark that the extremals are homogeneous in p: it can easily be shown that for all k > 0, if (x, p, u) is a BC-extremal of (OCP) then (x, kp, u) is also a BC-extremal of (OCP). Numerically, it is better to get rid of this homogeneity. There exist two main normalizations for this purpose:

• in the first normalization, the extremals associated to a solution of (OCP) are supposed to be normal (p 0 < 0). Under this assumption, we can fix π p 0 (p) = -1. The associated shooting function S p : R → R is thus defined by S p (p) = S(-1, p).

• the second choice is to fix ||p|| 2 = 1. In this case, if we denote by α the angle of p, the associated shooting function S α : [-π, 0] → R is therefore defined by

S α (α) = S sin(α), cos(α) .
The two corresponding shooting functions are shown in Figure 3. For both normalizations, a zero of S(•) -x f may be found using a classical Newton-like solver, which needs a good initial guess. Therefore, the bounds of the interesting part (the green one) of these shooting functions need to be determined. From Figure 3, we can notice that the range of interesting values (the green part) for S α is extremely small.

Geometrical preconditioner of the shooting function

Paraphrasing Y. Saad, see [8, Chapter 9], preconditioning is simply a means of transforming the original system (not linear in our case) into one that is likely to be easier to solve with an iterative solver. Preconditioning aims to improve both efficiency and robustness of iterative techniques. The main goal of this article is thus to present a preconditioner that allows to reduce the sensitivity of the shooting function and permits to reduce the number of iterations of the Newton-like solver. This preconditioner is based on a geometric interpretation of the costate and the Mathieu transformation.

Geometric interpretation of the costate

The proof of the Pontryagin Maximum Principle is constructive, see [START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF] for instance. It is based upon the so-called needle variations introduced by Boltyanskii which generate a cone K x , that can be seen as a local convex approximation of the set A at the point x. The extremals are then constructed by a backward integration of the Hamiltonian flow from (x, p), where p is taken in the non-empty polar cone K •

x of K x . By construction, the cone K x is included in the Bouligand tangent cone to A at x denoted T (A, x). Consequently, the normal cone to A at x, which is by definition the polar cone of T (A, x), is included in the cone K •

x , that is N (A, x) ⊂ K • x . Hence, by construction, to any non-zero covector of N (A, x(t f )) is associated a BC-extremal. Let remark that since A is a non-empty close convex set, the normal cone N (A, x(t f )) is not reduced to {0}.

In Figure 4, the orientations of the final costates p(t f ) are represented by the blue cones, anchored at the black, red and green points. It is easier now to understand the shape of the shooting function S α (•). Indeed, the normal cones associated to the corner points (in black) represent 99.84% of the angles while the interesting angles (associated to the green part) correspond only to 0.066%. In Figure 5 we give a neat representation of the relations between the angle of the covector and respectively the state and the cost at t f .

Symplectic manifold and Mathieu transformation

Let see R 2 = M as a smooth manifold. The cotangent bundle T * M ≃ R 2 × R 2 and the canonical symplectic form ω make a symplectic manifold (T * M, ω). A Hamiltonian H is a smooth function defined on T * M . If we denote by (x, p) the canonical Darboux coordinates on T * M , the closed nondegenerate differential 2-form ω is obtained from the Liouville 1-form λ = p dx by ω = -dλ = dx∧dp.

In other words, for all

u, v ∈ T z (T * M ) ≃ R 2 × R 2 , we have ω(u, v) = u Jv , where J = 0 I R 2 -I R 2 0 6
is the classical symplectic matrix. The Hamiltonian vector field

#» H is defined by ω( #» H, •) = dH,

which leads to the Hamiltonian dynamics

#» H = J∇H. We are now interested in transformations that preserve the symplectic form, and hence also the Hamiltonian dynamics. These transformations are called symplectomorphisms and correspond to the set of diffeomorphisms Φ : T * M → T * M such that Φ * ω = ω. In particular, a diffeomorphism ϕ : M → M is lifted into a symplectomorphism by the so-called Mathieu transformation

Φ(x, p) = ϕ(x), J -⊤ ϕ (x) p , (3)
where J ϕ (x) is the Jacobian matrix of ϕ at x and J -⊤ ϕ (x) denotes the transpose of its inverse. For more details about symplectic manifolds and the Mathieu transformation, we refer to [START_REF] Agrachev | Control Theory from the Geometric Viewpoint[END_REF] or [START_REF] Lesfari | Géométrie symplectique, calcul des variations et dynamique hamiltonienne[END_REF].

Preconditioner construction

Let us consider a diffeomorphism ϕ : R 2 → R 2 . The associated symplectomorphism Φ defined by (3) transforms z = (x, p) into w = (y, q):

z = x p Φ ----→ ←---- Φ -1 y q = w.
The relations between these variables is thus:

y = ϕ(x), q = J -⊤ ϕ (x) p, x = ϕ -1 (y), p = J ⊤ ϕ (x) q.
The main idea is to create the shooting function S : R 2 → R that takes the new system of coordinates q as input and returns the state in the original one: S(q) = S J ⊤ ϕ (x)q . In the same way as presented in Section 3.2, the homogeneity is removed by considering the two following shooting functions S q : R → R and S β : [-π, 0] × R defined by S q (q) = S(-1, q) and S β (β) = S (sin(β), cos(β)) .

It remains now to define the diffeomorphism ϕ. For that purpose, we propose to construct an ellipse E that best fits ∂A and a diffeomorphism ϕ that transforms this ellipse into the unit circle. This transformation is affine and can therefore be written as follows:

ϕ(x) = Ax + b.
We denote by B = ϕ(A) the reachable set in the new coordinate system. The proposed transformation is shown in Figure 6.

Since ϕ is an affine transformation, the associated costate transformation is linear (and does not depend on x): p = A ⊤ q.

Moreover, thanks to the preservation of the Hamiltonian dynamics by the Mathieu transformation, the geometric interpretation of the costate described in Section 4.1 remains true in the new coordinates.

The shooting function, the reachable set and its polar representation in the new coordinate system are presented in Figures 7, 8 and9, to be compared to Figures 3, 4 and5 respectively. As we can see on Figures 8 and9, the normal cones at the corner points are smaller in the new coordinates. They represent only 15.89% (compare to 99.84% for the original coordinate system) of the angles while the interesting angles (associated to the green part) now represent 42.34% after transformation (compare to 0.066%). Hence, the part of the interesting input set of the shooting function S β is much bigger than the one for S α . This is visible on Figure 7.

Results

The goal is now to compare the convergence of the solver with and without preconditioning, for different initial states x 0 and final targets x f . The convergence of S p and S β are compared in two different cases.

In the first case, we suppose that we have no relevant information on what could be a good initial guess, and hence it is arbitrarily fixed to p = 500 for S p and to β = -π/2 for S β for all the experiments.

The second case is based on [START_REF] Cots | A bilevel optimal control method and application to the hybrid electric vehicle[END_REF]. We assume that we have a differentiable approximation C(x 0 , x f ) of the value function V (x 0 , x f ). This value function corresponds to the optimal cost for Problem (OCP) with the initial x 0 and final x f state of charge. A method to create such an approximation of the value function is described in [START_REF]Generation of value function data for bilevel optimal control method[END_REF]. In this context, it has been shown that is a good initial guess for S p , and reduces the number of iterations of the solver.

p init (x 0 , x f ) = ∇ x0 C(x 0 , x f )
The initial costate -1, p init (x 0 , x f ) is then transported into the q-space and converted in an angle β init by

β init (x 0 , x f ) = atan2 A -⊤ -1 ∇ x0 C(x 0 , x f ) . (4)
Figure 10 shows the evolution of the average error with respect to the number of iterations of the solver. The remarkable fact is that the convergence for the function S β without the good initial guess (plain orange curve) is faster than the one for the function S p with the good initial guess (dashed blue curve). Obviously, the best result is clearly obtained when both preconditioner and good initial guess are used orange curve).

Conclusion

In this paper, we propose a new preconditioning method of the shooting function associated to the HEV's torque split and gear shift optimal control problem. This method is based on two main considerations: the geometric interpretation of the costate and the Mathieu transformation. We propose a simple affine application, that transforms an ellipse to the unit circle, and we show that the associated preconditioned shooting function S β converges faster than the classical one S p . Moreover, the best result is obtained when a good initial guess (Equation 4) is provided to S β , thanks to [START_REF] Cots | A bilevel optimal control method and application to the hybrid electric vehicle[END_REF].

In a future work, it could be interesting to search for other transformations, possibly non-linear, to reduce even more the number of iterations of the solver. As mentioned previously, the considered cycle is the WLTC on the first 100 seconds. This transformation may be extended to other cycles. It could also be really interesting to study this transformation on general optimal control problems (maybe in higher dimension), and identify which of their properties make it possible to use (or not) this preconditioner.

Figure 1 :

 1 Figure 1: Optimal control (Gear and ICE torque) and state trajectory (SOC), with the initial and final state of charge fixed at 50%.

Figure 2 :

 2 Figure 2:Reachable set A at time t f , with x 0 = (0, 0.5). The three black points correspond to corner points. The red (resp. green) line corresponds to ∂A when the cost is maximal (resp. minimal).

Figure 3 :

 3 Figure 3: Shooting functions S p and S α . More precisely, in the upper figure, the green (with the bottom black) curve corresponds to the shooting function S p and the red (with the upper black) one to the shooting function S(1, p) (for which the goal would be to maximize the fuel consumption). In the same way, in the bottom figure, the shooting function corresponds to the restriction to the interval [-π, 0].

Figure 4 :Figure 5 :

 45 Figure 4: Similar to Figure 2. The blue cones correspond to the computed final costates orientations. Numerically, they happen to be the normal cones N (A, x(t f )) for different final states.Notice that the axes do not share the same scale and this explains why orthogonality is not obvious at first sight.

Figure 6 :

 6 Figure 6: Transformation of the boundary ∂A of the reachable set in the original coordinate system (6a) into ∂B in the new one (6b). The fitted ellipse E (dashed blue line on the upper plot) is transformed into the unit circle (dashed blue line on the lower plot).

Figure 7 :

 7 Figure 7: Shooting functions S q and S β . To be compared to Figure 3.

Figure 8 :

 8 Figure 8: Reachable set in the new coordinate system, where y = (y 0 , y 1 ). To be compared to Figure 4. Notice that the axes now share the same scale.

Figure 9 :

 9 Figure9: Polar representation in the new coordinate system, where y = (y 0 , y 1 ). To be compared to Figure5. The black dashed lines correspond to the bounds of the normal cones anchored at the corner points.

Figure 10 :

 10 Figure 10: Evolution of the error |S(•) -x f | with respect to the number of iterations of the solver.The blue curves correspond to the shooting function S = S p and the orange one to S = S β . The plain lines correspond to a fixed initialization (p = 500 and β = -π/2), and the dashed ones to the improved initialization (p = p init (x 0 , x f ) and β = β init (x 0 , x f )). The dotted black line corresponds to the industrial tolerance (10 -3 ).

Acknowledgments

This research was partially supported by Vitesco Technologies. In particular, we want to thank Olivier Flebus, artificial intelligence and optimization group leader at Vitesco Technologies and Mariano Sans, optimal control senior expert at Vitesco Technologies, for their supervision, valuable insights and suggestions.