Jérôme Malick
email: jerome.malick@inria.fr

Welington De Oliveira
email: welington@ime.uerj.br

Sofia Zaourar
email: sofia.zaourar@inria.fr

Uncontrolled inexact information within bundle methods

Keywords: Nonsmooth optimization, bundle methods, inexact oracle, energy optimization, two-stage stochastic problems, chance-constrained problems Mathematics Subject Classification (2000) 65K05, 49J52, 49M27, 90C15, 90C25, 90C27

We consider convex nonsmooth optimization problems where additional information with uncontrolled accuracy is readily available. It is often the case when the objective function is itself the output of an optimization solver, as for large-scale energy optimization problems tackled by decomposition. In this paper, we study how to incorporate the uncontrolled linearizations into (proximal and level) bundle algorithms in view of generating better iterates and possibly accelerating the methods. We provide the convergence analysis of the algorithms using uncontrolled linearizations, and we present numerical illustrations showing they indeed speed up resolution of two stochastic optimization problems coming from energy optimization (two-stage linear problems and chance-constrained problems in reservoir management).

1 Introduction: context, problem, and contributions

Nonsmooth minimization with an (inexact) oracle

We consider nonsmooth optimization problems of the form

f * := inf x∈X f (x) , (1)
with a convex function f : R n → R; and a (nonempty) polyhedral set X ⊂ R n , and we assume that the infimum is finite ( f * > -∞). Typically, the nonsmoothness of f comes after a maximization, i.e. when f itself is the result of an inner optimization problem

f (x) = sup u∈U h(u, x) (2)
where h(u, •) are convex for each u lying in a set U. Such nonsmooth objective functions appear in Lagrangian relaxation (see e.g. [START_REF]Lagrangian relaxation[END_REF]), in stochastic optimization with recourse (see e.g. [START_REF] Shapiro | Lectures on stochastic programming: Modeling and theory[END_REF]), or in Benders decomposition (see e.g. [START_REF] Geoffrion | Generalized Benders decomposition[END_REF]). For a fixed accuracy η ≥ 0, a so-called (lower) η-oracle of f provides, for a point x ∈ X as an input, an approximate value and an approximate linearization

f x ∈ R such that f (x) -η ≤ f x ≤ f (x), g x ∈ R n such that f x + g x (• -x) ≤ f (•).
(3)

If the oracle error is null (η = 0), the oracle returns the exact value f x = f (x) and a subgradient g x ∈ ∂ f (x). For some problems, as in large-scale stochastic optimization or in combinatiorial optimization, computing exact information on f is expensive, or even out-of-reach, whereas computing some inexact information (η > 0) is still possible. For example, when f is given by (2), any ū ∈ U gives an inexact value and an approximate linearization of f at a given x ∈ X. Indeed, the convexity of h(u, •) yields h( ū, x) + g (zx) ≤ h( ū, z) ≤ f (z), for any g ∈ ∂ x h( ū, x).

So we have inexact information on f by taking f x = h( ū, x) and g x = g ∈ ∂ x h( ū, x).

(4)

In this case, an η-oracle maximizes h(•, x) over U up to the tolerance η, i.e., computes ū ∈ U satisfying f (x)η ≤ h( ū, x) ≤ f (x) so that (4) gives the η-information (3). Among the nonsmooth optimization methods to solve problems (1) with f known by an oracle (3), are the bundle-type methods: the Kelley method [START_REF] Kelley | The cutting plane method for solving convex programs[END_REF][START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms[END_REF], proximal bundle methods [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms[END_REF], level bundle methods [START_REF] Lemaréchal | New variants of bundle methods[END_REF], generalized bundle methods [START_REF] Frangioni | Generalized bundle methods[END_REF], and doubly stabilized bundle methods [dS15]. Initially devellopped for exact oracles (η = 0), these methods have been extended to handle inexact oracles (η > 0) and to solve (1) up to an accuracy of η. Complete convergence analysis of these methods exists; roughly speaking, under some assumptions, the iterates x k are an η-minimizing sequence

f * ≤ lim inf f (x k ) ≤ f * + η.
(5)

We refer to [START_REF] Hintermüller | A proximal bundle method based on approximate subgradients[END_REF] and [START_REF] Solodov | On approximations with finite precision in bundle methods for nonsmooth optimization[END_REF] for first articles, [START_REF] Zakeri | Inexact cuts in benders decomposition[END_REF] for an inexact version of the Kelley method, [START_REF] Fábián | Bundle-type methods for inexact data[END_REF] for an inexact level method, [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF] and [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF] for inexact proximal bundle methods, and [START_REF] Oliveira | Level bundle methods for oracles with on-demand accuracy[END_REF] for inexact level methods with vanishing errors.

1.2 Inexact oracle... and more

For some optimization problems as above with an η-oracle, there is in fact additional uncontrolled information on f , which is already available or cheap to get.

A typical example is in combinatorial optimization when f has the form (2), with a discrete set U and with a Lagrangian function h (see e.g. [START_REF]Lagrangian relaxation[END_REF]). In this case, exact or approximate resolution schemes produce "good" feasible points ū ∈ U, that give, in turn, linearizations of f by (4) -but with uncontrolled accuracy, so that this cannot be used for an oracle with fixed accuracy η. For instance, when (2) is solved by a branch-and-bound algorithm, feasible solutions are generated during the exploration of the branch-and-bound tree, but only the final one, the optimal solution, is used by the oracle to generate (3). The (uncontrolled) information (4) produced by the intermediate feasible solutions is not used, whereas it is available for free and possibly fine (since nearly optimal solutions are usually obtained soon in the branch-and-bound process). It is the same situation when we have cheap heuristics computing solutions that are "good" in practice (sometimes with probabilistic guarantees) but without the (deterministic) guarantee required for an η-oracle. We will consider in section 4 an energy optimization problem with such an efficient specific heuristic; other examples include p-median problems [START_REF] Beltran | Solving the p-median problem with a semi-lagrangian relaxation[END_REF] and unit-commitment problems (see e.g. the recent review [START_REF] Tahanan | Large-scale unit commitment under uncertainty[END_REF]).

Another type of example of cheap uncontrolled information appears in two-stage stochastic linear problems (see e.g. [START_REF] Shapiro | Lectures on stochastic programming: Modeling and theory[END_REF], and applications to energy problems in [START_REF] Zakeri | Inexact cuts in benders decomposition[END_REF] and [dOSP + 10]). In this case, the function has a form (2) with separable terms corresponding to linear maximization subproblems

f (x) = c x + N ∑ i=1 π i f i (x) with f i (x) = sup W u ≤q (h i -T x) u, (6)
for given N, π i , h i , T , W and q (details to come in section 4). Computing exact information on f requires to solve the N linear optimization subproblems, which is costly when N is large. Solving only a fraction of these subproblems (say 10%) still gives inexact uncontrolled information on f . Indeed if we compute ūi an optimal solution giving f i (x), then we can also use it to under-approximate other terms f j (x) (since the feasible sets are the same, we have (h j -T x) ūi ≤ f j (x)). Thus, for a given fraction of solved problems, we have an inexact linearization but with an unknown accuracy.

We formalize the situation where we can compute controlled information together with some uncontrolled inexact information by assuming that we have an oracle with accuracy bounded by η ≥ 0, and a "cutting-plane generator" adding linearizations with uncontrolled accuracy.

(7)

This abstract cutting-plane generator should be seen as an external module, having the previous bundle of linearizaions as an input, and adding other linearizations without calling the η-oracle. There is no other requirement on the generator: it can use information already available, call heuristics, or even run optimization algorithms. For example, in our numerical experiments, the cutting-plane generators will add inexact (uncontrolled) linearizations produced during a fixed number of iterations of a standard bundle method using heuristics. Note that the situation (7) does not fit in the context of "on-demand accuracy oracles" of [START_REF] Oliveira | Level bundle methods for oracles with on-demand accuracy[END_REF] where the oracle both requires and provides more information. Note also that the cutting-plane generator is different from the multi-cuts techniques used to accelerate cutting-plane methods in operation research (see e.g. [START_REF] Desrosiers | A primer in column generation[END_REF] in "column generation", [START_REF] Magnanti | Accelerating benders decomposition: Algorithmic enhancement and model selection criteria[END_REF] for the Benders decomposition of mixed-integer programming, and [START_REF] Ruszczyński | Stochastic programming[END_REF] in stochastic programming). Contrary to our cutting-plane generator, these techniques usually add several "controlled" cuts. In this context, our approach can be seen as an uncontrolled multi-cut technique.

In the two situations mentioned in this section (Lagrangian relaxations of combinatorial optimization problems, and decompositions of stochastic optimization problems), obtaining uncontrolled bundle information and calling the cutting-plane generator are often of neglectable computational cost compared to the cost of calling the (controlled) oracle. A wise practitioner can therefore be tempted to use the uncontrolled bundle information inside of his bundle method. The goal of this paper is to serve as an incentive to follow this meaningful practical intuition, as it establishes that incorporating uncontrolled bundle information can help in practice and is also consistent in theory.

Using uncontrolled linearizations in bundle methods

Assume that we are at iteration k of a bundle method solving (1), and that we have a family of linearizations fi (•)

:= f x i + g x i (• -x i ) ≤ f (•) (8)
associated to points {x i } ⊂ X. In this paper, we consider that some of these linearizations (indexed by J η k ) were given by the oracle, (so they are inexact up to the oracle error f

(x i ) -η ≤ f x i ≤ f (x i ) for all i ∈ J η k )
, and that the others (indexed by J u k ) were created by the cutting-plane generator (so we do not known and do not control their inexactness). Bundle methods use available linearizations to create the so-called cutting-plane model of f , which is

fk (•) := max i ∈J η k ∪ J u k fi (•) ( ≤ f (•) ). ( 9
)
This model is used to compute the next iterate x k+1 by solving a convex quadratic programming problem. In proximal bundle algorithms (see e.g. [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms[END_REF]), x k+1 is the proximal point of fk given a "prox-parameter" t k > 0 and the "stability center" xk ;

the quadratic optimization problem is the following:

min x∈X fk (x) + 1 2t k x -xk 2 ⇐⇒    min x,r r + 1 2t k x -xk 2 s.t. fi (x) ≤ r, ∀ i ∈ J η k ∪ J u k x ∈ X, r ∈ R . (10)
In level bundle algorithms (see e.g. [START_REF] Lemaréchal | New variants of bundle methods[END_REF]), x k+1 is the projection of the current stability center xk onto the level set of "level parameter"

f lev k X k := x ∈ X : fk (x) ≤ f lev k = x ∈ X : fi (x) ≤ f lev k for all i ∈ J η k ∪ J u k ; (11)
the quadratic optimization problem is the following:

min x∈X k 1 2 x -xk 2 ⇐⇒    min x 1 2 x -xk 2 s.t. fi (x) ≤ f lev k ∀ i ∈ J η k ∪ J u k x ∈ X. (12)
In both cases, it is clear that using more information gives a more precise model, so would possibly lead to computation of better iterates since the model (9) using all the information (max on both J η k and J u k ) is obviously always above the model of f that would restrict the max to J η k only. Admittedly, in practice using the complete model (9) rather than ignoring uncontrolled information makes quadratic programming problems (10) and (12) larger and then more difficult to solve. This is partly compensated by the ever-growing performance of (specific or even general-purpose) linear-quadratic programming solvers. Anyway, this drawback does not really hold in the case of expensive oracles -which is the situation we consider in this paper. Thus, there is a clear practical interest to consider as much information as possible when solving (1) with bundle methods: richer information can accelerate numerical methods at a neglectable cost, so that the overall computing time is lower than using only the controlled information. This will be illustrated in section 4.

There is nevertheless a theoretical argument against using the uncontrolled information in the model. Up to our understanding, the convergence results of bundle methods do not extend in a straightforward way for handling general models (9). Standard proofs of convergence use indeed that iterates are computed using a cuttingplane model with "controlled" linearizations, produced by an oracle with bounded or vanishing accuracy (η → 0); see e.g. [START_REF] Fábián | Bundle-type methods for inexact data[END_REF], [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF], and [START_REF] Oliveira | Level bundle methods for oracles with on-demand accuracy[END_REF]. In our situation, the call of the cutting-plane generator makes us lose control on the construction of the cutting-plane model and therefore on the next iterate.

The only analysis which is generic enough to cover uncontrolled linearizations is the recent article [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF] on the convergence of various forms of proximal bundle methods. So we start with considering, in section 2, a proximal bundle algorithm using the cutting-plane generator which is a trivial extension of the standard inexact proximal method of [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF] and whose analysis is an instantiation of the generic analysis of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF]. Numerical experiments show that this proximal algorithm does accelerate the convergence with the help of uncontrolled linearizations added by a cheap cutting-plane generator. However this algorithm may not fully capture the uncontrolled information: the prox-parameter t k in (10) ties the next iterate to the stability center xk , so that the step can be small even when the model is reasonably rich due to the added uncontrolled linearizations. This feature is inherent to proximal algorithms.

In contrast, level bundle method would better benefit from additional uncontrolled inexact information: richer cutting-plane models would tend to generate useful lower bounds, and then the level set X k would better approximate the solution set, and the next iterate would better approximate a solution. However, to our knowledge, there is no level bundle method which we could build on to introduce uncontrolled information: the level counterpart of [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF] able to deal with bounded accuracy η-oracle in the general case has not been developed yet, because of the difficulty of setting up a noise attenuation without direct control on the step (operated by t k in proximal methods). In particular, our situation does not fit in the recent analysis of [START_REF] Oliveira | Level bundle methods for oracles with on-demand accuracy[END_REF] that features oracles with varying accuracy but controlling the error (and driving it to zero), nor in [START_REF] Van Ackooij | Level bundle methods for constrained convex optimization with various oracles[END_REF] that assumes the oracle to have uniformly bounded errors on a compact feasible set X.

Contributions, structure, and notation

This paper presents two inexact bundle algorithms (proximal and level) incorporating (already available or cheap to compute) uncontrolled bundle information. We formalize the additional information as produced by an external module (the cutting-plane generator of (7)) producing inexact linearizations without known or bounded accuracy. In section 2, we consider a proximal bundle algorithm using this cutting-plane generator, which is simple (in the sense that is a trivial extension of the standard inexact proximal method of [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF]) and has a simple analysis (in the sense that it is an instantiation of the generic analysis of proximal methods of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF]). We introduce in section 3 a new inexact level bundle algorithm using the cutting-plane generator which is an extension of the limited-memory proximal level algorithm [START_REF] Brannlund | A descent proximal level bundle method for convex nondifferentiable optimization[END_REF] with an implicit noise attenuation step. This is the first level algorithm able to handle inexact oracles without assuming compactness of the feasible set X or a vanishing error; this is the main technical contribution of this paper. Finally, in section 4, we present and discuss computational illustrations on stochastic optimization problems coming from energy optimization: two-stage linear problems (arising in the planning of hydro-electric power generation, see [START_REF] Zakeri | Inexact cuts in benders decomposition[END_REF] and [dOSP + 10]) and joint chanceconstrained optimization problems (arising in cascaded reservoir management, see e.g. [START_REF] Van Ackooij | Level bundle methods for constrained convex optimization with various oracles[END_REF]). For these problems, we show that the methods save computational time in using both controlled and uncontrolled information.

Before moving to these developments, we finish this introduction by recalling some notation and terminology of bundle algorithms.

Aggregate linearizations. We will see that the optimality conditions of the quadratic problems (10) and (12) introduce the "aggregated subgradients" ĝk ∈ ∂ fk (x k+1 ) + N X (x k+1 ), which will have a role in the stopping tests. They define in turn the socalled "aggregate linearizations", denoted with the convenient notation "-k" bor-

rowed from [dOSL14], f-k (•) := fk (x k+1 ) + ĝ k (• -x k+1 ) . (13)
It can be proved (see e.g. [dOS14, Prop.

3.2]) that f-k is indeed a linearization f-k (x) ≤ fk (x) ≤ f (x) for all x ∈ X . ( 14
)
We also define the "aggregate linearization error" by

êk := f xk -f-k ( xk ). ( 15
)
Bundle compression. The linearizations used in fk are possibly numerous and imprecise. It is interesting to be able to work with a limited memory and to somehow extract the useful part from all linearizations. In bundle algorithm terminology, this is called "bundle compression", which is a desirable property in general [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms[END_REF], and thus even more in our context where it would make sense to compress uncontrolled bundle information. In theory we can compress a lot in the algorithms presented in this paper: as usual for bundle methods, the current controlled linearization and the aggregate linearization are sufficient to guarantee convergence.

Descent test. The two bundle methods presented in this paper have a descent step which is the technical point bringing convergence without compactness of X. The stability center xk is updated if the observed decrease is at least a fraction of the predicted decrease

v k = f xk -fk (x k+1 ). (16)
More specifically, we use the following descent test

f x k+1 ≤ f xk -κ f v k , with κ f ∈ (0, 1) . ( 17
)
2 Proximal bundle method using uncontrolled information This section explains how the usual inexact bundle method extends easily to deal with uncontrolled bundle information: Algorithm 1 below is a version of the inexact proximal algorithm of [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF] using the cutting-plane generator to incorporate uncontrolled bundle information. At iteration k of this algorithm, optimality conditions of the quadratic proximal subproblem (10) can be written with the help of the (simplicial) Lagrange multipliers α i associated to the constraints fi (x) ≤ r, as

-x + xk -t k ∑ i∈J η k ∪ J u k α i g i ∈ N X (x).
The unique solution x k+1 can thus be written as a "subgradient step" along ĝk ∈

∂ fk (x k+1 ) + N X (x k+1 ) with specified stepsize t k x k+1 = xk -t k ĝk . ( 18
)
Combined with (13), this yields that the aggregate linearization error êk defined in (15) and the predicted decrease ν k of ( 16) are connected by v k = e k + t k ĝk 2 . Excessive inexactness is handled in a standard way: we employ the "noise attenuation" rule proposed by [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF], consisting in increasing sharply t k whenever êk is overly negative. More precisely, if êk < -κ att t k ĝk 2 , we set t k = 10t k and solve again (10) to obtain another iterate. Otherwise (i.e., êk ≥ -κ att t k ĝk 2 ), the algorithm performs like a classical proximal bundle method. We implement this using an extra binary variable na indicating noise attenuation. After noise attenuation, t k does not decrease until a new descent step is performed (see line 20). Though it deals with the coarse information (J u k = / 0), the convergence of the algorithm still fits into the generic bundle scheme analysis of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF].

Algorithm 1 Usual inexact proximal bundle method using cutting plane generator 1: Choose x 1 ∈ X, and set x1 ← x 1 2: Choose stopping tolerances, tol e ≥ 0 and tol g ≥ 0 3: Select κ f , κ att ∈ (0, 1) and t 1 ≥ t > 0 4: ( f x 1 , g x 1 ) ← η-oracle(x 1 ), set ĝ1 ← g x 1 and ê1 ← 0 5: ( Choose J η k+1 ⊃ {k + 1, -k} bundle compression 23: end for Theorem 1 (Convergence of inexact proximal bundle) Set the tolerances to zero in Algorithm 1. Then the sequences testing optimality { êk + ĝ k xk } and { ĝk } become "nonpositive", in the sense that there exists a subsequence (indexed by I ) such that:

J η 1 ← {1}, J u 0 ← / 0 and na ← 0 6: for k = 1, 2, . . . do 7: J u k ←cutting-plane-generator( xk , J η k , J u k-1 ) introduction of
f x k+1 , g x k+1 ) ← η-oracle(x k+1 ) call η-oracle 17: if f x k+1 ≤ f xk -κ f v k then 18: xk+1 ← x k+1 ,
lim sup k∈I êk + ĝ k xk ≤ 0 and lim k∈I ĝk = 0 .
Furthermore, the iterates { xk } generate an η-minimizing sequence, i.e. (22) holds. Thus Algorithm 1 terminates after finitely many steps with an approximate solution if the tolerances tol g , and tol e are strictly positive.

Proof The algorithm fits into the algorithmic pattern 4.2 of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF], and roughly speaking the convergence comes from the use of the η-oracle at descent steps. More specifically, we apply the generic convergence result of Theorems 6.11 and 4.4 of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF]; let us check their assumptions one by one:

-The oracle error is uniformly bounded by η (for iterates x j with j ∈ J η k ), and thus satisfies (6.8) of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF].

-The cutting-plane model (9) satisfies fk ≤ f , i.e., equation (4.10) in [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF].

-We have (3.8) of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF] by setting k = f xk .

-The prox-parameter updating rule is of the type (6.14) of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF].

-Equation (6.11) in [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF] holds trivially for f xkf x k+1 as effective decrease.

-We have (6.16) of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF] (specifically, with α k = 0 and β k = κ att in there).

Thus Algorithm 1 satisfies all the assumptions (6.15) and (6.16) of [dOSL14, Theorem 6.11]. This opens the way to apply [dOSL14, Theorem 4.4], which in turn states that having a subsequence I such that lim sup k∈I ( êk + ĝ k xk ) ≤ 0 and lim k∈I ĝk = 0 gives the convergence up to η, which is the desired conclusion.

We report numerical illustrations of this algorithm in section 3.2. They show that using uncontrolled linearizations within this algorithm leads to less iterations and lower CPU time than using only controlled linearizations. However we see on (18) that the algorithm may not exploit completely the added uncontrolled linearizations: x k+1 is tied to xk by the explicit prox-parameter t k , which could prevent the algorithm from making big steps in case of rich cutting-plane model. Such behavior would not appear with level bundle method.

Level method using uncontrolled information

This section presents a level bundle algorithm dealing with an η-oracle and a cuttingplane generator introducing uncontrolled linearizations, as in (7). When disregarding the cutting-plane generator, this algorithm turns out to be the first level method able to deal with inexact η-oracles in general; in this way, it can be seen as the level counterpart of the proximal bundle method of [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF]. The algorithm is presented in section 3.1, its convergence is stated in section 3.2 and analyzed in section 3.3. Its numerical behaviour is illustrated in section 4.

An inexact proximal-descent level bundle method

To avoid any compactness assumption, we consider a proximal-descent version of level bundle method, inspired from the one of [START_REF] Brannlund | A descent proximal level bundle method for convex nondifferentiable optimization[END_REF]. At iteration k of this algorithm, optimality conditions of the projection problem (12) can be written, with the help of the Lagrange multipliers α i ≥ 0 associated to the constraints fi (x) ≤ f lev k , as

-x + xk -∑ i∈J η k ∪ J u k α i g i ∈ N X (x).
Introducing the "stepsize"

µ k := ∑ i∈J η k ∪ J u k α i ,
we observe that x k+1 , the unique solution of the above optimality conditions, can be written as the "subgradient step" along a direction ĝk ∈ ∂ fk (x k+1 ) + N X (x k+1 )

x k+1 = xk -µ k ĝk such that µ k ( fk (x k+1 ) -f lev k ) = 0. ( 19
)
The (inexact) upper bound is given by the η-oracle at the stability center ( f up k = f xk ). When µ k > 0, the predicted decrease (16) then corresponds to the level depth

v k = f up k -f lev k ,
and the aggregate linearization error is related to it, as

êk = v k -µ k ĝk 2 . ( 20
)
To see this, notice from (19) that µ k > 0 ensures that fk (x k+1 ) = f lev k and, therefore

êk = f xk -( fk (x k+1 ) + ĝ k ( xk -x k+1 )) = f xk -f lev k -µ k ĝk 2 = v k -µ k ĝk 2 .
We emphasize that we do not control the stepsize µ k in level bundle methods, in contrast with proximal bundle methods where we can choose the prox-parameter t k giving the stepsize. This poses a technical difficulty for handling excessive inexactness within level methods. In Algorithm 1, as in other inexact proximal bundle methods, t k is increased when the noise is excessively large compared to ĝk (see line 13 in Algorithm 1); this can not be done directly in an inexact level method. So we propose in Algorithm 2 an implicit noise attenuation rule, combined with the level attenuation rule. The idea is simple: we do not allow the depth v k to decrease if the noise is excessive (see line 21). We will prove in the key proposition 2 that this simple idea makes µ k to go to infinity in presence of noise, such that either a new descent step is generated, or the algorithm terminates.

In practice, the projection onto X k (problem (12)) is solved by a quadratic programming solver (at line 18 of Algorithm 2). If X k is nonempty, the solver provides x k+1 and µ k , from which we deduce ĝk by (19). If X k is empty, the solver raises a flag of infeasibility and we exploit this information by updating the lower bound for the optimal value f * : observe indeed that when X k is empty, there holds

f lev k < fk (x) ≤ f (x) for all x ∈ X,
f low k ≤ f * ≤ f up k + η. ( 21
)
Algorithm 2 New inexact proximal level method using cutting-plane generator 1: Choose x 1 ∈ X, v 1 > 0, and set x1 ← x 1 2: Choose stopping tolerances tol ∆ ≥ 0, tol e ≥ 0 and tol g ≥ 0 3: Select κ l , κ f , κ att ∈ (0, 1) 4: Choose a threshold µ large > 0 5: ( f x 1 , g x 1 ) ← η-oracle(x 1 ), set ĝ1 ← g x 1 and ê1 ← 0 6: Set Run a quadratic optimization software on problem (12) 14:

f up 1 ← f x 1 , f low 1 ← -∞, ∆ 1 ← +∞, J η 1 ← {1}, J u 0 ← / 0 7: for k = 1, 2, . . . do 8: J u k ←cutting-plane-generator( xk , J η k , J u k-1 ) introduction of uncontrolled linearizations 9: Update f lev k ← f up k -v k and X k ← x ∈ X : fk (x) ≤ f lev k 10: if ∆ k ≤
if X k is empty then 15: (

f low k ← f lev k , ∆ k ← f up k -f low k , v k ← min{ν k , κ l ∆ k }
f x k+1 , g x k+1 ) ← η-oracle(x k+1 ) call η-oracle 25: if f x k+1 ≤ f xk -κ f v k then 26: xk+1 ← x k+1 , f up k+1 ← f xk+1 and f low k+1 ← f low k descent step 27: ∆ k+1 ← f up k+1 -f low k+1 and v k+1 ← min{v k , κ l ∆ k+1 } 28: else 29: xk+1 ← xk , ∆ k+1 ← ∆ k , v k+1 ← v k , f up k+1 ← f up k and f low k+1 ← f low k 30: end if 31:
Choose J η k+1 ⊃ {k + 1, -k} bundle compression 32: end for

Convergence result

We have the following theorem stating the convergence of Algorithm 2, which is of the same vein as Theorem 1 for Algorithm 1.

Theorem 2 (Convergence of inexact proximal level) Set the tolerances to zero in Algorithm 2. Then the sequences testing optimality {∆ k = f up kf low k }, { êk } and { ĝk } become "nonpositive", in the sense that either the sequence {∆ k } tends to be nonpositive: lim ∆ k ≤ 0, or there exists a subsequence (indexed by I ) such that: lim inf k∈I êk ≤ 0 and lim k∈I ĝk = 0.

Furthermore, the iterates { xk } generate an η-minimizing sequence, i.e.

f * ≤ lim inf f ( xk ) ≤ f * + η. ( 22
)
Thus Algorithm 2 terminates after finitely many steps with an approximate solution if the tolerances tol ∆ , tol g , and tol e are strictly positive.

The next section is devoted to the proof of this theorem. We will say that the algorithm converges up to η when (22) holds. Note that there are two ways to stop the algorithm (see line 10): the usual criterion based on the gap

∆ k = f up k -f low k lim ∆ k ≤ 0 =⇒ convergence up to η (23)
and a second one inspired from [START_REF] Brannlund | A descent proximal level bundle method for convex nondifferentiable optimization[END_REF] based on the aggregated error and subgradients to deal with unbounded feasible sets. The next two lemmas explain these two stopping tests and their consistency.

Lemma 1 (Nonpositivity of ∆ k and convergence) If lim ∆ k ≤ 0, then the sequence

{ xk } satisfies f * -η ≤ lim f xk ≤ f * ≤ lim inf f ( xk ) ≤ f * + η . ( 24
)
Furthermore, if at some iteration k we have ∆ k ≤ 0, then we have in fact

f * -η ≤ f xk ≤ f * ≤ f ( xk ) ≤ f * + η . ( 25
)
Proof Note first that the η-oracle properties imply that, for all k,

f * -η ≤ f ( xk ) -η ≤ f xk , (26)
≤ f * . Writing lim ∆ k ≤ 0 as lim f xk -lim f low k ≤ 0 we obtain f * -η ≤ lim f xk ≤ f * . (27)
Now passing to the limit-inf in (26) and adding η, we also have

f * ≤ lim inf f ( xk ) ≤ lim f xk + η ≤ f * + η.

Combining this inequalities with (27) gives the announced inequalities (24).

The argument leading to the second inequality (25) is the same as above. For a fixed k, (26) and ∆ k ≤ 0 give f *η ≤ f xk ≤ f * , and adding η to (26) yields

f * ≤ f ( xk ) ≤ f xk + η ≤ f * + η .

Combining the inequalities gives (25).

Lemma 2 (Vanishing aggregate errors and convergence) For the sequences { xk }, { êk } and { ĝk } generated by Algorithm 2, we have, for all x ∈ X,

f ( xk ) ≤ f (x) + êk + η -ĝ k (x -xk ). ( 28
)
Assume that { xk } is bounded and there exists a subsequence indexed by I such that lim inf k∈I êk ≤ 0 and lim

k∈I ĝk = 0. ( 29
)
Then the algorithm converges up to η.

Proof Fix x ∈ X. The inequality (28) comes from (13) as follows:

f (x) ≥ f-k (x) = fk (x k+1 ) + ĝ k (x -x k+1 ) = fk (x k+1 ) + ĝ k ( xk -x k+1 ) + ĝ k (x -xk ) = f-k ( xk ) + ĝ k (x -xk ) = f xk -( f xk -f-k ( xk )) + ĝ k (x -xk ) = f xk -êk + ĝ k (x -xk ) ≥ f ( xk ) -η -êk + ĝ k (x -xk ).
We also get the upper bound

f * ≤ f ( xk ) ≤ f (x) + êk + η + ĝk x -xk .
Passing to the lim inf, (29) together with the boundedness of { xk } yields

f * ≤ lim inf k∈I f ( xk ) ≤ f (x) + η.
Taking the infimum over x ∈ X gives (22).

Convergence proof

To prove Theorem 2, we adapt the usual rationale of convergence proof of bundle methods, by considering the two cases of infinitely many and finitely many descent steps (line 26). We show that in both cases one of the two stopping tests is active, which guarantees in turn that the algorithm converges up η (by (23) and Lemma 2). The technical challenge is to handle, first, a fixed inexactness in a level method and, second, the uncontrolled cutting-plane model. We note that this proof of convergence differs from the one of [START_REF] Brannlund | A descent proximal level bundle method for convex nondifferentiable optimization[END_REF].

We start with a remark about the level depth v k . Looking at lines 15, 22 and 27, we see that {v k } is nonincreasing, and that if v k ≥ 0 then êk ≥ -µ k ĝk 2 . We also notice that v k can be negative only if so is ∆ k , and then (23) holds. Therefore, we consider that v k ≥ 0 in the remainder of the section.

We will also need the index set A of the iterations requiring a noise attenuation (line 22). The following lemma studies the situation of infinitely many of such attenuations. The following proposition treats the first case of infinitely many descent steps.

Lemma 3 (Infinitely many attenuations) If A contains infinitely many indices, then (29) holds with I = A . If the sequence { xk } is furthermore bounded, then the algorithm converges up to η.

Proof Recall that v k = êk + µ k ĝk 2 by (20). If k ∈ A , then we have

v k = êk + µ k ĝk 2 ≥ (1 -κ att )µ k ĝk 2 ≥ (1 -κ att )µ large ĝk 2 ≥ 0.
If the set A is infinite, then we have v k → 0, and therefore ĝk → 0 by the above inequality. By (20), this yields that êk → 0 and then we have (29) with I = A . As a result, if the sequence { xk } is bounded, we can invoke Lemma 2 and get that { xk } is η-minimizing.

Proposition 1 (Infinitely many descent steps) Suppose there are infinitely many descent steps (line 26). Then the algorithm converges up to η.

Proof Let us index the descent steps by . More precisely k( ) denotes the th descent iteration, and j( ) = k( + 1) -1 the last iteration before the ( + 1) th . Note that xk( ) is the th (different) stability center, and that xk( ) = x j( ) . The descent test (17) gives the inequality

f x k( ) -f x k( +1) ≥ κ f v j( ) ≥ 0 .
Summing over we get

f x k(0) -lim f x k( +1) ≥ κ f ∞ ∑ =0 v j( ) .
Since lim f x k( +1) ≥ f *η > -∞, we get that the series converges and then

lim v j( ) = 0. ( 30
)
By monotonicity of v k , we thus have lim k v k = 0. Let us distinguish now three cases:

(i)A finite (ii)A infinite and { xk } k bounded (iii)A infinite and { xk } k unbounded

In the case (i), for k large enough, we have v k = κ l ∆ k , and then lim k ∆ k = 0. Thus, (23) holds and the proof is over. In the case (ii), we can use Lemma 3 which gives (29) and that { xk } is η-minimizing. So let us focus on the case (iii), and let us prove by contradiction that { xk } is still η-minimizing.

Suppose that there exists ε > 0 such that f ( xk ) > f * +η +ε for all k large enough. This yields that there exists x ∈ X such that f ( xk( ) ) ≥ f ( x) + η + ε/2 for all large . Then (28) applied to k = j( ) gives

ĝ j( ) (x -xk( ) ) ≤ f (x) + η -f ( xk( ) ) + ê j( ) for all x ∈ X , which yields ĝ j( ) ( x -xk( ) ) ≤ ê j( ) -ε/2 .
Using this inequality and (20), we develop

xk( +1) -x 2 = xk( ) -µ j( ) ĝ j( ) -x 2 = xk( ) -x 2 + µ j( ) ĝ j( ) 2 + 2µ j( ) ĝ j( ) ( x -xk( ) ) = xk( ) -x 2 + µ j( ) [µ j( ) ĝ j( ) 2 + 2 ĝ j( ) ( x -xk( ) )] ≤ xk( ) -x 2 + µ j( ) [µ j( ) ĝ j( ) 2 + 2 ê j( ) -ε] ≤ xk( ) -x 2 + 2µ j( ) [v j( ) -ε/2] .
As lim v j( ) = 0 by (30), we have for all large enough v j( ) ≤ ε/2 and then xk( +1)x 2 ≤ xk( )x 2 which contradicts the fact that { xk } is unbounded. Hence, (22) must hold.

We consider now the second case of finitely many descent steps. We start with a lemma stating that null iterates get further away from the last stability center.

Lemma 4 (After a last descent step)

If xk = xk-1 = x, f lev k ≤ f lev k-1 and v k = v k-1 , then we have x k+1 -x 2 ≥ x k -x 2 + (1 -κ f ) 2 g x k 2 v 2 k .
Proof The bundle management of line 31 incorporates two pieces in the model fk : the k-th linearization fk and the aggregate linearization f-k . Both bring some information, as follows. First, since f-(k-1) ≤ fk and f lev k ≤ f lev k-1 , we have that the level set X k is included in the "aggregate level set" X -(k-1) := {x ∈ X : f-(k-1) (x) ≤ f lev k-1 }, and therefore that x k+1 ∈ X -(k-1) . It can be proved (see e.g. [START_REF] Oliveira | Level bundle methods for oracles with on-demand accuracy[END_REF]Prop. 3.2]) that the aggregate level-set produces the same iterate that X k-1 ; in other words, 31) Thus, we have ( xx k ) (x k+1x k ) ≤ 0 and developing x k+1x 2 = x k+1x k + (x kx) 2 , the inequality gives

x k = P X k-1 ( x) = P X -(k-1) ( x) and ( x -x k ) (x -x k ) ≤ 0 for all x ∈ X -(k-1) . (
x k+1 -x 2 ≥ x k -x 2 + x k -x k+1 2 . ( 32
)
Now since fk ≤ fk and x k+1 ∈ X k , we have

f x k + g x k (x k+1 -x k ) ≤ f lev k , which gives f x k -f lev k ≤ g x k x k+1 -x k . ( 33
)
Iteration k is not a descent iteration: the converse of line 25 reads

f x k ≥ f x -κ f v k-1 . Recalling that f lev k = f x -v k and v k = v k-1 , this yields f x k -f lev k ≥ (1 -κ f )v k .
Together with (33), this gives

x k+1 -x k ≥ (1 -κ f ) g x k v k .
which ends the proof with (32).

Proposition 2 (Finitely many descent steps) Suppose that Algorithm 2 generates only finitely many descent steps. Then the algorithm converges up to η.

Proof Let us consider first two easy cases. If lim ∆ k ≤ 0 then (23) holds, and the proof is over. If A has infinitely many indices, we can conclude with Lemma 3 together with the fact that the sequence { xk } is constant for k large enough. Let us focus on the case where there exists ∆ > 0 such that ∆ k ≥ ∆ for all k, and there is eventually no noise attenuation (A has finitely many indices). For k large enough, the stability center is fixed (denoted x) and the depth is also fixed (at v > 0).

We claim that the sequence x k+1x is not bounded. For sake of a contradiction, suppose that it is bounded. Then the η-subgradients are bounded (by a constant Λ ) by [HUL93, Prop. XI.4.1.2]. Apply Lemma 4; since the v k and the f lev k are fixed, the sequence { x k+1x } k increases by a constant factor (1κ f ) 2 v2 /Λ 2 at each iteration. This contradicts the boundedness.

We claim now that µ k → ∞. In view of a contradiction, suppose that {µ k } is bounded: let μ > 0 be such that µ k ≤ μ for all k large enough. Using (20) we have that

µ k v k = µ k êk + µ 2 k ĝk 2 ≥ -µ k η + µ 2 k ĝk 2 ≥ -μη + x k+1 -x 2 .
As {v k } is nonincreasing, we have that μv

0 ≥ µ k v k ≥ -μη + x k+1 -x 2 , contra- dicting that x k+1 -x 2 → ∞. Hence, µ k → ∞.
Since there is eventually no noise attenuation, we have (see line 21) êk < -κ att µ k ĝk 2 < 0 for all k large enough.

By definition of êk in (15), we have that êk

≥ f ( xk ) -η -f-k ( xk ) ≥ -η, from (3)
and ( 14). This yields ĝk 2 ≤ η/(κ att µ k ). Since µ k → ∞, we get that ĝk → 0. Hence, (29) holds with I being all the large indices. Since the sequence { xk } is finite (thus bounded), we can conclude with Lemma 2.

Remark 1 (More sophisticated versions) We emphasize that the important point of the above proofs was to control the linearization error at descent steps. As a consequence, we could add a test in the algorithm to stop the oracle whenever we detect that the descent test will be false. This version of the algorithm would be proved to be convergent with the exact same proof.

We could also cover the case of "upper oracles" in the terminology of [START_REF] Oliveira | Convex proximal bundle methods in depth: a unified analysis for inexact oracles[END_REF]. The algorithm could indeed deal with controllable linearizations overestimating the function by no more than a constant η g > 0. The same convergence proof would result in a convergence to an (η + η g )-solution.

Numerical illustration on energy optimization

We illustrate the efficiency of our approach on two classes of energy optimization problems: two-stage stochastic programming problems (with publicly available data sets) and chance-constrained optimization problems arising from cascaded reservoir management (with real-life data). Each following subsection treats one family of problems for which we consider an exact oracle and a cutting-plane generator incorporating uncontrolled linearizations. Our goal here is not to obtain the best computational results for these problems, but to show that using the uncontrolled bundle information can speed-up computations.

Specifically, we compare Algorithm 1 and Algorithm 2 using cutting-plane generators to their basic versions not using any additional uncontrolled linearizations (J u k = / 0 for all k). We have implemented these algorithms in MATLAB (using the Gurobi solver for LP and QP problems); we name them as follows u-P: Algorithm 1, the proximal bundle using uncontrolled information, -P: Algorithm 1 with J u k = / 0, the standard proximal bundle algorithm, u-L: Algorithm 2, the level bundle using uncontrolled information, -L: Algorithm 2 with J u k = / 0, the (new) level algorithm.

Notice that the comparison between level and proximal bundle algorithms are (surprisingly) rare; an exception is [dS15]. In particular, in section 5.1.4 of [dS15], tests are reported with tuning parameters of proximal and level bundle methods. Here we set the parameters of the algorithms according to these tests: for both algorithms, we take κ f = 0.1 and κ att = 0.99 ; for Algorithm 1, we take t 1 = 10, t = 10 -6 , and the update rule of Section 5.1.2 of [dS15] (with a = 2) for t k ; for Algorithm 2, we take κ l = 0.2 and µ large = 5. Since the controlled oracle is exact (η = 0), the four methods converge to the exact solution. The algorithms are compared by measuring the number of calls to the exact oracle and the total CPU time to reach the stopping test. We use the relative stopping tolerance

tol e = tol ∆ = 10 -5 (1 + f ( xk )) and tol g = 10 -4 (1 + f ( xk )).
These experiments were performed on a computer with Intel(R) Core(TM), i3-3110M CPU 2.40, 4G (RAM), under Windows 8, 64Bits.

We also compare the speed and robustness of the algorithms globally on all the problems by using performance profiles [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF]. For each algorithm, we plot the proportion of problems that it solved within a factor of the time required by the best algorithm. More precisely, if we denote by t A (p) the time spent by algorithm A to solve problem p and t * (p) the best time for solving problem p, then the proportion of problems solved by A within a factor τ is θ A (τ) = number of problems p such that t A (p) ≤ τ t * (p) total number of problems .

Two-stage stochastic linear optimization problems

Problem and instances description. Two-stage stochastic linear problems arise in the planning of hydro-electric power generation; see e.g. [START_REF] Zakeri | Inexact cuts in benders decomposition[END_REF] and [dOSP + 10] for applications to the New Zealand and Brazilian electricity system. The problem can be formulated as (1) with

X = {x ∈ R n + : Ax = b} and f (x) = c x + N ∑ i=1 π i f i (x)
where c ∈ R n , A ∈ R m 1 ×n and b ∈ R m 1 are such that the set X is bounded. Also,

f i (x) := min y∈R n 2 + q y s.t. T x +Wy = h i (34)
is the so-called recourse function associated with the i-th scenario h i ∈ R m 2 (which has a probability π i > 0). In these problems, the vectors h i are the only uncertainty parameters and are normally distributed. The dual linear problem of (34) is

f i (x) = sup W u ≤q (h i -T x) u. (35)
We use the set of two-stage stochastic linear test-problems that have been used by several authors including [START_REF] Shapiro | Lectures on stochastic programming: Modeling and theory[END_REF][START_REF] Deák | Two-stage stochastic problems with correlated normal variables: computational experiences[END_REF][START_REF] Oliveira | Inexact bundle methods for two-stage stochastic programming[END_REF]). The set is available online on the webpage of István Deák1 . The data set consists in 7 families of problems of different sizes; we call them F1 to F7. A family of problems is given by the data (c, A, b, q, T,W ) along with a generator of appropriate scenarios, which takes as an input the number of scenarios N, and returns (π i , h i ) for i = 1, . . . , N. For each family, we have 7 problems corresponding to N ∈ {100, 200, 500, 800, 1000, 1200, 1500}.

Oracles and cutting-plane generator. Computing exact information on f requires solving the N linear optimization subproblems (34)-(35). Solving only a fraction of these subproblems still gives inexact information on f : the optimal solution ūi giving f i (x) can also be used to under-approximate other terms f j (x) (since the dual feasible sets are the same, we have (d j -T i x) ūi ≤ f j (x)). Thus we are in the situation (7) with an exact oracle providing the value f (x) and a subgradient g ∈ ∂ f (x) (η = 0) by solving exactly the N subproblems (35); an uncontrolled oracle by solving 10% of the subproblems (35) and taking a feasible solution of the remaining subproblems. This oracle is about 90% times faster than the fine one, but we do not know its accuracy. a cutting-plane generator consisting in running several iterations of a bundle method using only the uncontrolled oracle (with the same stopping test and a maximum of 100 iterations).

Numerical results. Table 1 presents the performances of the four algorithms on the 49 test-problems. It reports the number of (exact) oracle calls and CPU time (in minutes) required to reach convergence. Each entry is the average over the seven instances of the family, except for the last line which is the grand total over the 49 instances. This table shows that adding uncontrolled linearization does speed up significantly the two algorithms: we observe 25% less oracle calls and 10% less CPU time between L and u-L, and 39.4% and 28.6% between P and u-P. 1 Comparison of the four algorithms with respect to the number of oracle calls and the global CPU time to get convergence. Each entry is the average over the seven instances of the family, except for the last line which is the grand total over the 49 instances.

The decrease of oracle calls is more important than the one of CPU time because of the additional time taken by the calls of the cutting-plane generator and by solving larger quadratic subproblems. We still observe a decrease of CPU time in all our instances, even if the uncontrolled linearizations may have a poor accuracy. We also note that the decrease is more important for proximal algorithm than the level one. This is due to the fact that the level algorithm without uncontrolled information (L) does already well: we see that the CPU times of L are comparable to the ones of u-P. For these problems, the best method in terms of both oracle calls and CPU time is u-L, the level method using the uncontrolled cutting-plane generator. Figure 1 confirms this by showing the performance profile of all solvers with respect to oracle calls (the plot for CPU time is similar). Since its curve is always higher, u-L clearly dominates the other methods in terms of speed and robustness. The value at τ = 1 indicates that u-L is the best to solve around 70% of the 49 problems; it also solves all the problems within a factor τ ≈ 1.5 of the best method.

We finish with a remark about the influence of the accuracy of the uncontrolled oracle. We note indeed that we can adjust the accuracy of the uncontrolled oracle in this situation by changing the percentage of subproblems (35) solved. In the reported experiments, we choose to solve 10% of the subproblems because we found out that it provides a good compromise between performance of the overall algorithm and computational burden of the external module. We mention here that, during preliminary tests, we observed that solving fewer subproblems (e.g. 1% of all subproblems) tends to increase of the total number of exact oracle calls and to give higher CPU times to solve the overall problem. On the other hand, we also observed that solving more subproblems (e.g. 20% of all subproblems) tends to decrease of the number of exact oracle calls, but with higher total CPU costs (since the uncontrollable oracle becomes more expensive). In general, the efficient choice of the percentage of problems solved depends on the problem's data, such as variance of the random vectors and number of considered scenarios.

Chance-constraint optimization problems

Problem and instances description. Joint chance-constrained optimization problems appear in cascaded reservoir management in presence of probabilistic guarantees that volumes in the reservoirs remain within bounds see e.g. [START_REF] Van Ackooij | Level bundle methods for constrained convex optimization with various oracles[END_REF]. With a target probability p ∈ (0, 1), these constraints can be expressed as P[g(y) ≥ ξ ] ≥ p where ξ ∈ R n represents the random vector of water inflows (of associate probability measure P) and g : R m → R n is an affine mapping. The associated optimization problem can be written (see more precisely [vAHMZ14, Eq.( 15)]) as min y∈Y,v∈V q y s.t. g(y) ≥ v ,

where Y is a bounded polyhedron and V the set of points satisfying the probability constraint. When considering finitely many scenarios {ξ 1 , . . . , ξ N } with associated probability {π 1 , . . . , π N } (see e.g. [SDR09, Chap. 4], [DM13, Chap. 6], and [START_REF] Van Ackooij | Probabilistic optimization via approximate p-efficient points and bundle methods[END_REF]), V can be expressed as the following feasibility set

V = v ∈ R n : ∃ z ∈ {0, 1} N , π z ≤ 1 -p, (1 -z i )ξ i ≤ v -b z i , i = 1, . . . , N
where b ∈ R n is defined component-wise by b j := min 1≤i≤N ξ i j . Then the dual problem has the form (1) with

X = R n + and f (x) := -(h(x) + d(x))
where h(x) is the optimal value of a mere linear programming problem (since Y is a polyedron and g is affine)

h(x) := min y∈Y q yx g(y)

and d(x) is the optimal value of a (large-scale) mixed-binary linear problem

d(x) :=      min v∈R m , z∈{0,1} N x v s.t. ξ i (1 -z i ) ≤ v -b z i , i = 1, . . . , N π z ≤ 1 -p . (37)
Here we use the instances described in [START_REF] Van Ackooij | Joint chance constrained programming for hydro reservoir management[END_REF] and [START_REF] Van Ackooij | Level bundle methods for constrained convex optimization with various oracles[END_REF] constructed from real-life data on the French hydro-valley Isère (provided to us by EDF, the French Electricity Board). For N ∈ {50, 100, 150, 200, 250} and p ∈ {80%, 90%}, three different scenario samples are randomly generated, and as a result, we get thirty different associated instances.

Oracles and cutting-plane generator. The bulk of the work of an exact oracle for f is to solve the mixed-binary linear optimization problem (37) to optimality, which is expensive as N grows. On the other hand, we have an easy way to produce feasible solutions, as follows. To any binary point z ∈ {0, 1} N satisfying π z ≤ 1p we associate the vector ṽ ∈ R n such that ṽ j := max i∈{l: z l =0} ξ i j for all j = 1, . . . , N .

Observe then that the pair ( ṽ, z) is feasible for (37). Accordingly, d x := x ṽ is an upper approximation for d(x), which in turn provides a (cheap but imprecise) approximation for f (x)

f x := -(h(x) + d x ) ≤ f (x) .
The recent work [START_REF] Van Ackooij | Probabilistic optimization via approximate p-efficient points and bundle methods[END_REF] proposes a fast heuristic (denoted Heuristic h1 therein) to compute a good candidate z (and therefore ṽ as above) to approximate a solution of problem (37). Thus we are in the situation (7) with an exact oracle providing the value f (x) and a subgradient g ∈ ∂ f (x) (η = 0) by solving exactly the subproblem (37) with Gurobi; an uncontrolled oracle using the heuristic of [START_REF] Van Ackooij | Probabilistic optimization via approximate p-efficient points and bundle methods[END_REF] and (38); a cutting-plane generator consisting in running several iterations of a bundle method using only the uncontrolled oracle (with the same stopping test and a maximum of 100 iterations).

Numerical results. Table 2 Comparison of the four algorithms with respect to oracle calls and global CPU time to get convergence. Each entry is the average over the three instances, except for the last line which is the grand total over the 30 instances.

The figures show that introducing uncontrolled linearizations reduces both the number of oracle calls and the CPU time for both proximal and level algorithms. This improvement is even more significant than for the two-stage problems: the reduction of CPU times is of 47% for u-L and 36% for u-P.

We also see that u-L is more efficient u-P, both in CPU time and number of oracle calls. In fact u-L makes a better use of uncontrolled information added by the cuttingplane generator: L and P are comparable in terms of CPU time whereas u-L is faster than u-P (by more than 20%). The performance profiles of Figure 2 confirm that u-L is the fastest and most robust among the four methods.

Conclusions

This paper analyzes two bundle algorithms (a proximal one and a level one) handling cheap uncontrolled inexact linearizations, incorporated by an abstract cutting-plane generator. Beside the formalisation and the emphasis on uncontrolled bundle information, the main technical contribution of this paper is the challenging convergence analysis of the level algorithm. This algorithm extends [START_REF] Brannlund | A descent proximal level bundle method for convex nondifferentiable optimization[END_REF] to handle inexact η-oracles and to use the general uncontrolled cutting-plane model generator. The key feature of this algorithm is a novel noise attenuation rule, that can be seen as an implicit version of the one of [START_REF] Kiwiel | A proximal bundle method with approximate subgradient linearizations[END_REF]. Numerical experiments on two energy optimization problems show that including cheap uncontrolled information can decrease the CPU time to reach optimality, and that the level algorithm, fully exploiting the additional information, works particularly well on these problems.

To our knowledge, this paper is the first one to consider cheap uncontrolled inexact information within bundle methods and to show the interest to use it. A recent preprint [START_REF] Van Ackooij | Inexact stabilized benders decomposition approaches to chance-constrained problems with finite support[END_REF] builds on this line of research in a context of Benders decomposition. Note finally that we consider here an extreme case of a cutting-plane generator with no control at all on the linearizations. More sophisticated and subtle ways to incorporate cheap information should be possible, as for exemple using "adaptative oracles". Such inexact oracles would interact with the bundle algorithm (though accuracy parameters as in [START_REF] Oliveira | Level bundle methods for oracles with on-demand accuracy[END_REF] but not only) and would be able to choose between several available approximation schemes with increasing accuracy and increasing cost (as for example the three specific heuristics of [START_REF] Beltran | Solving the p-median problem with a semi-lagrangian relaxation[END_REF] for a combinatorial problem). A general study of smart and communicating oracles goes beyond the scope of the paper and deserves special research and developments.

  so that we can set f low k = f lev k (see line 15). At each iteration of Algorithm 2, we thus have a lower bound f low k and an inexact upper bound f up k such that

Fig. 1

 1 Fig. 1 Performance profiles of the four methods over the 49 instances

Fig. 2

 2 Fig.2Performance profiles of the four methods on the 30 instances.

  tol ∆ or ( êk ≤ tol e and ĝk ≤ tol g ) then

	11:	return xk and f xk = f	up k	stopping test
	12:	end if
	13:

  The nonincreasing sequence { f xk } is bounded from below thus converges and lim f xk ≥ f

so that f up k = f xk satisfies (21). We see that { f up k = f xk } is nonincreasing (line 26), { f low k } is

nondecreasing (line 15), and so {∆ k } is nonincreasing (line 27). *η. Similarly the nondecreasing { f low k } is bounded from above by f * , thus it also converges and lim f low k

  Table2reports the number of (exact) oracle calls and CPU time (in minutes) required to reach convergence, for the four algorithms over the 30 testproblems. Each entry is the average over the instances with same N and p, except for the last line which is the grand total over the 30 instances.

				# oracle calls			CPU time (min)
	N	p	L	P	u-L	u-P	L	P	u-L	u-P
	50	0.8	18	32	13	13	0.6	0.9	0.4	0.4
	50	0.9	18	18	11	9	0.4	0.4	0.3	0.2
	100	0.8	19	24	12	15	2.9	3.5	1.7	1.6
	100	0.9	19	19	11	21	1.3	1.1	0.7	1.2
	150	0.8	19	24	11	20	12.8 12.0	6.2	7.9
	150	0.9	18	24	8	18	2.4	3.6	1.2	2.1
	200	0.8	20	19	13	23	24.2 20.2 12.1 12.6
	200	0.9	19	22	10	6	5.6	5.7	3.2	1.4
	250	0.8	18	32	15	15	48.9 45.6 29.9 28.0
	250	0.9	19	36	12	40	17.0 26.1	5.3	20.5
	Total		558 751 346 543 5.8h 6.0h 3.0h 3.8h

http://www.uni-corvinus.hu/index.php?id=26637

Acknowledgment

We thank Antonio Frangioni (Univ. of Pisa, Italy) for insightful discussions on a first version of this article and Wim van Ackooij (EDF, France) for providing us with the real-life data set used in section 4.2. The first author gratefully acknowledges the support of the grant "ANR GeoLMI" and the CNRS Mastodons project "gargantua/titan". The second author gratefully acknowledges the support provided by Severo Ochoa Program SEV-2013-0323 and Basque Government BERC Program 2014-2017.