Matthieu Boutier

Gabriel Kerneis

Generating events with style

Keywords: Concurrency, program transformations, event-driven style

Threads and events are two common abstractions for writing concurrent programs. Because threads are often more convenient, but events more efficient, it is natural to want to translate the former into the latter. However, whereas there are many different event-driven styles, existing translators often apply ad-hoc rules which do not reflect this diversity. We analyse various control-flow and data-flow encodings in real-world event-driven code, and we observe that it is possible to generate any of these styles automatically from threaded code, by applying certain carefully chosen classical program transformations. In particular, we implement two of these transformations, lambda lifting and environments, in CPC, an extension of the C language for writing concurrent systems. Finally, we find out that, although rarely used in real-world programs because it is tedious to perform manually, lambda lifting yields better performance than environments in most of our benchmarks.

Introduction

Most computer programs are concurrent programs, which need to perform several tasks at the same time. For example, a network server needs to serve multiple clients at a time; a GUI needs to handle multiple keyboard and mouse inputs; and a network program with a graphical interface (e.g. a web browser) needs to do both simultaneously.

Translating threads into events There are many different techniques to implement concurrent programs. A very common abstraction is provided by threads, or lightweight processes. In a threaded program, concurrent tasks are executed by a number of independent threads which communicate through a shared memory heap. An alternative to threads is event-driven programming. An event-driven program interacts with its environment by reacting to a set of stimuli called events. At any given point in time, to every event is associated a piece of code known as the handler for this event. A global scheduler, known as the event loop, repeatedly waits for an event to occur and invokes the associated handler. Performing a complex task requires to coordinate several event handlers by exchanging appropriate events. Unlike threads, event handlers do not have an associated stack; event-driven programs are therefore more lightweight and often faster than their threaded counterparts. However, because it splits the flow of control into multiple tiny event handlers, event-driven programming is generally deemed more difficult and error-prone. Additionally, event-driven programming alone is often not powerful enough, in particular when accessing blocking APIs or using multiple processor cores; it is then necessary to write hybrid code, that uses both preemptivelyscheduled threads and cooperatively-scheduled event handlers, which is even more difficult.

Since event-driven programming is more difficult but more efficient than threaded programming, it is natural to want to at least partially automate it. Continuation-Passing C (CPC [START_REF] Kerneis | Continuation-passing C, compiling threads to events through continuations[END_REF]) is an extension of the C programming language for writing concurrent systems. The CPC programmer manipulates very lightweight threads, choosing whether they should be cooperatively or preemptively scheduled at any given point. The CPC program is then processed by the CPC translator, which produces highly efficient sequentialised event-loop code, and uses native threads to execute the preemptive parts. The translation from threads into events is performed by a series of classical source-to-source program transformations: splitting of the control flow into mutually recursive inner functions, lambda lifting of these functions created by the splitting pass, and CPS conversion of the resulting code. This approach retains the best of both worlds: the relative convenience of programming with threads, and the low memory usage of event-loop code.

The many styles of events Not all event-driven programs look the same: several styles and implementations exist, depending on the programmer's taste. Since event-driven programming consists in manually handling the control flow and data flow of each task, a tedious and error-prone activity, the programmer often choses a style based on some trade-off between (his intuition of) efficiency and code-readability, and then sticks with it in the whole program. Even if the representation of control or data turns out to be suboptimal, changing it would generally require a complete refactoring of the program, not likely to be undertaken for an uncertain performance gain. In large event-driven programs, written by several people or over a long timespan, it is even possible to find a mix of several styles making the code even harder to decipher.

For example, the transformations performed by the CPC translator yield event-driven code where control flow is encoded as long, intricate chains of callbacks, and where local state is stored in tiny data structures, repeatedly copied from one event-handler to the next. We can afford these techniques because we generate the code automatically. Hand-written programs often use less tedious approaches, such as state machines to encode control flow and coarse long-lived data structures to store local state; these are easier to understand and debug but might be less efficient. Since the transformations performed by the CPC translator are completely automated, it offers an ideal opportunity to generate several event-driven variants of the same threaded program, and compare their efficiency.

Contributions

We first review existing translators from threads to events (Section 2), and analyse several examples of event-driven styles found in realworld programs (Section 3). We identify two typical kinds of control-flow and data-flow encodings: callbacks or state machines for the control flow, and coarsegrained or minimal data structures for the data flow.

We then propose a set of automatic program transformations to produce each of these four variants (Section 4). Control flow is translated by splitting and CPS conversion to produce callbacks; adding a pass of defunctionalisation yields state machines. Data flow is translated either by lambda lifting, to produce minimal, short-lived data structures, or using shared environments for coarse-grained ones.

Finally, we implement eCPC, a variant of CPC using shared environments instead of lambda lifting to handle the data flow in the generated programs (Section 5). We find out that, although rarely used in real-world event-driven programs because it is tedious to perform manually, lambda lifting yields faster code than environments in most of our benchmarks. To the best of our knowledge, CPC is currently the only threads-to-events translator using lambda lifting.

Related work

The translation of threads into events has been rediscovered many times [5,[START_REF] Key | Weave: translated threaded source (with annotations) to fibers with context passing (ca 1995-2000[END_REF][START_REF] Krohn | Events can make sense[END_REF]. In this section, we review existing solutions, and observe that each of them generates only one particular kind of event-driven style. As we shall see in Section 4, we believe that these implementations are in fact a few classical transformation techniques, studied extensively in the context of functional languages, and adapted to imperative languages, sometimes unknowingly, by programmers trying to solve the issue of writing events in a threaded style.

The first example known to us is Weave, an unpublished tool used at IBM in the late 1990's to write firmware and drivers for SSA-SCSI RAID storage adapters [START_REF] Key | Weave: translated threaded source (with annotations) to fibers with context passing (ca 1995-2000[END_REF]. It translates annotated Woven-C code, written in threaded style, into C code hooked into the underlying event-driven kernel.

Adya et al. [START_REF] Adya | Cooperative task management without manual stack management[END_REF] provide a detailed analysis of control flow in threads and events programs, and implement adaptors between event-driven and threaded code to write hybrid programs mixing both styles.

Duff introduces a technique, known as Duff 's device [START_REF] Duff | Protothreads: simplifying eventdriven programming of memory-constrained embedded systems[END_REF], to express general loop unrolling directly in C, using the switch statement. Much later, this technique has been employed multiple times to express state machines and event-driven programs in a threaded style: protothreads [5], FairThreads' automata [START_REF] Boussinot | FairThreads: mixing cooperative and preemptive threads in C[END_REF]. These libraries help keep a clearer flow of control but they provide no automatic handling of data flow: the programmer is expected to save local variables manually in his own data structures, just like in event-driven style.

Tame [START_REF] Krohn | Events can make sense[END_REF] is a C++ language extension and library which exposes events to the programmer but does not impose event-driven style: it generates state machines to avoid the stack ripping issue and retain a thread-like feeling. Similarly to Weave, the programmer needs to annotate local variables that must be saved across context switches.

TaskJava [START_REF] Fischer | Tasks: language support for event-driven programming[END_REF] implements the same idea as Tame, in Java, but preserves local variables automatically, storing them in a state record. Kilim [START_REF] Srinivasan | Kilim: Isolation-typed actors for java[END_REF] is a messagepassing framework for Java providing actor-based, lightweight threads. It is also implemented by a partial CPS conversion performed on annotated functions, but contrary to TaskJava, it works at the JVM bytecode level.

MapJAX [START_REF] Myers | Mapjax: Data structure abstractions for asynchronous web applications[END_REF] is a conservative extension of Javascript for writing asynchronous RPC, compiled to plain Javascript using some kind of ad-hoc splitting and CPS conversion. Interestingly enough, the authors note that, in spite of Javascript's support for nested functions, they need to perform "function denesting" for performance reasons; they store free variables in environments ("closure objects") rather than using lambda lifting.

AC [START_REF] Harris | AC: composable asynchronous IO for native languages[END_REF] is a set of language constructs for composable asynchronous I/O in C and C++. Harris et al. introduce do..finish and async operators to write asynchronous requests in a synchronous style, and give an operational semantics. The language constructs are somewhat similar to those of Tame but the implementation is very different, using LLVM code blocks or macros based on GCC's nested functions rather than source-to-source transformations.

Control flow and data flow in event-driven code

Because event-driven programs do not use the native call stack to store return addresses and local variables, they must encode the control flow and data flow in data structures, the bookkeeping of which is the programmer's responsibility. This yields a diversity of styles among event-driven programs, depending on the programmer's taste, creativity, and his perception of efficiency. In this section, we analyse how control flow and data flow are encoded in several examples of real-world event-driven programs, and compare them to equivalent threaded-style programs.

Control flow

Two main techniques are used to represent the control flow in event-driven programming: callbacks and state machines.

Callbacks Most of the time, control flow is implemented with callbacks. Instead of performing a blocking function call, the programmer calls a non-blocking equivalent that cooperates with the event loop, providing a function pointer to be called back once the non-blocking call is done. This callback function is actually the continuation of the blocking operation.

Developing large programs raises the issue of composing event handlers. Whereas threaded code has return addresses stored on the stack and a standard calling sequence to coordinate the caller and the callee, event-driven code needs to define its own strategy to layer callbacks, storing the callback to the next layer in some data structure associated with the event handler. The "continuation stack" of callbacks is often split in various places of the code, each callback encoding its chunk of the stack in an ad-hoc manner.

Consider for instance the accept loop of an HTTP server that accepts clients and starts two tasks for each of them: a client handler, and a timeout to disconnect idle clients. With cooperative threads, this would be implemented as a mere infinite loop with a cooperation point. The following code is an example of such an accept loop written with CPC. The programmer calls cpc spawn accept loop(fd) to create a new thread that runs the accept loop; the function accept loop then waits for incoming connections with the cooperating primitive cpc io wait, and creates two new threads for each client (httpTimeout and httpClientHandler), which kill each other upon completion. Note that cooperative functions are annotated with the cps keyword; such cps functions are to be converted into event-driven style by the CPC translator.

Figure 1 shows the (very simplified) code of the accepting loop in Polipo, a caching web-proxy written by Chroboczek. 3 This code is equivalent to the threaded version above, and uses several levels of callbacks.

In Polipo, the accept loop is started by a call to schedule accept(fd, http-Accept, NULL). This function stores the pointer to the (second-level) callback httpAccept in the handler field of the request data structure (Section 3.1), and registers a (first-level) callback to do scheduled accept, through register-FdEvent. Each time the file descriptor fd becomes ready (not shown), the event loop calls the (first-level) callback do scheduled accept, which performs the actual accept system call (Section 3.1) and finally invokes the (second-level) callback httpAccept stored in request->handler (Section 3.1).

This callback schedules two new event handlers, httpTimeout and http-ClientHandler. The former is a timeout handler, registered by scheduleTime-Event (Section 3.1); the latter reacts I/O events to read requests from the client, and is registered by do stream buf (Section 3.1). Note that those helper functions that register callbacks with the event loop use other intermediary callbacks themselves, just like schedule accept uses do schedule accept. In the original Polipo code, things are even more complex since schedule accept is called from httpAcceptAgain, yet another callback that is registered by httpAccept itself in some error cases. The control flow becomes very hard to follow, in particular when errors are triggered: each callback must be prepared to cope with error codes, or to follow-up the unexpected value to the next layer. In some parts of the code, this style looks a lot like an error monad manually interleaved with a continuation monad. Without a strict discipline and well-defined conventions about composition, the flexibility of callbacks easily traps the programmer in a control-flow and storage-allocation maze.

State machines When the multiplication of callbacks becomes unbearable, the event-loop programmer might refactor his code to use a state machine. Instead of splitting a computation into as many callbacks as it has atomic steps, the programmer registers a single callback that will be called over and over until the computation is done. This callback implements a state machine: it stores the current state of the computation into an ad-hoc data structure, just like threaded code would store the program counter, and uses it upon resuming to jump to the appropriate location.

Figure 2 shows how the initial handshake of a BitTorrent connection is handled in Transmission,4 a popular and efficient BitTorrent client written in (mostly) event-driven style. Until the handshake is over, all data arriving from a peer is handed over by the event loop to the canRead callback. This function implements a state machine, whose state is stored in the state field of a handshake data structure. This field is initialised to AWAITING HANDSHAKE when the connection is established (not shown) and updated by the functions responsible for each step of the handshake.

The first part of the handshake is dispatched by canRead to the readHandshake function (Section 3.1). It receives the buffer inbuf containing the bytes received so far; if not enough data has yet been received to carry on the handshake, it returns READ LATER to canRead (Section 3.1), which forwards it to the event loop to be called back when more data is available (Section 3.1). Otherwise, it checks the BitTorrent header (Section 3.1), parses the first part of the handshake, registers a callback to send a reply handshake (not shown), and finally updates the state (Section 3.1) and returns READ NOW to indicate that the rest of the handshake should be processed immediately (Section 3.

1).

Note what happens when the BitTorrent header is wrong (Section 3.1): the function tr handshakeDone is called with false as its second parameter, indicating that some error occurred. This function (not shown) is responsible for invoking the callback handshake->doneCB and then deallocating the handshake structure. This is another example of the multiple layers of callbacks mentioned above.

If the first part of the handshake completes without error, canRead then dispatches the buffer to readPeerId which completes the handshake (Section 3.1). Just like readHandshake, it returns READ LATER if the second part of the handshake has not arrived yet (Section 3.1) and finally calls tr handshakeDone with true to indicate that the handshake has been successfully completed (Section 3.1).

In the original code, ten additional states are used to deal with the various steps of negotiating encryption keys. The last of these steps finally rolls back the state to AWAITING HANDSHAKE and the keys are used by the function tr peerIoReadBytes to decrypt the rest of the exchange transparently. The state machine approach makes the code slightly more readable than using pure callbacks.

Data flow

Since each callback function performs only a small part of the whole computation, the event-loop programmer needs to store temporary data required to carry on the computation in heap-allocated data structures, whereas stack-allocated variables would sometimes seem more natural in threaded style. The content of these data structures depends heavily on the program being developed but we can characterise some common patterns.

Event loops generally provide some means to specify a void* pointer when registering an event handler. When the expected event triggers, the pointer is passed as a parameter to the callback function, along with information about the event itself. This allows the programmer to store partial results in a structure of his choice, and recover it through the pointer without bothering to maintain the association between event handlers and data himself.

Coarse-grained, long lived data structures These data structures are usually large and coarse-grained. Each of them correponds to some meaningful object in the context of the program, and is passed from callback to callback through a pointer. For instance, the connection structure used in Polipo (Figure 1) is allocated by httpMakeConnection when a connection starts (Section 3.1) and passed to the callbacks httpTimeoutHandler and httpClientHandler through the registering functions scheduleTimeEvent (Section 3.1) and do stream buf (Section 3.1). It lives as long as the HTTP connection it describes and contains no less than 22 fields: fd, timeout, buf, pipelined, etc. The tr handshake structure passed to canRead in Transmission is similarly large, with 18 fields. Some of these fields need to live for the whole connection (eg. fd which stores the file descriptor of the socket) but others are used only transiently (eg. buf which is filled only when sending a reply), or even not at all in some cases (eg. the structure HTTPConnectionPtr is used for both client and server connections, but the pipelined field is never used in the client case). Even if it wastes memory in some cases, it would be too much of a hassle for the programmer to track every possible data flow in the program and create ad-hoc data structures for each of them.

Minimal, short-lived data structures In some simple cases, however, the event-loop programmer is able to allocate very small and short-lived data structures. These minimal data structures are allocated directly within an event handler and are deallocated when the associated callback returns. They might even be allocated on the stack by the programmer and copied inside the event-loop internals by the helper function registering the event handler. The overhead is therefore kept as low as possible.

For instance, the function schedule accept passes a tiny, stack-allocated structure request to the helper function registerFdEvent (Fig. 1, Section 3.1). This structure is of type AcceptRequestRec (not shown), which contains only three fields: an integer fd and two pointers handler and data. It is copied by registerFdEvent in the event-loop data structure associated with the event, and freed automatically after the callback do scheduled accept has returned; it is as short-lived and (almost) as compact as possible.

As it turns out, creating truly minimal structures is hard: AcceptRequestRec could in fact be optimised to get rid off the fields data, which is always NULL in practice in Polipo, and fd, which is also present in the encapsulating event data structure. Finding every such redundancy in the data flow of a large event-driven program would be a daunting task, hence the spurious and redundant fields used to lighten the programmer's burden.

Generating various event-driven styles

In this section, we first demonstrate the effect of CPC transformation passes on a small example; we show that code produced by the CPC translator is very close to event-driven code using callbacks for control flow, and minimal data structures for data flow (Section 4.1). We then show how two other classical translation passes produce different event-driven styles: defunctionalising inner function yields state machines (Section 4.2), and encapsulating local variables in shared environments yields larger, long-lived data structures with full context (Section 4.3).

The CPC compilation technique

Consider the following function, which counts seconds down from an initial value x to zero.

cps void countdown ( int x ) { while ( x > 0) { printf ( " % d \ n " , x --); cpc_sleep (1); } printf ( " time is over !\ n " ); }
This function is annotated with the cps keyword to indicate that it yields to the CPC scheduler. This is necessary because it calls the CPC primitive cpc sleep, which also yields to the scheduler.

The CPC translator is structured in a series of proven source-to-source transformations [START_REF] Kerneis | Continuation-passing C, compiling threads to events through continuations[END_REF], which turn a threaded-style CPC program into an equivalent event-driven C program. Boxing first encapsulates a small number of variables in environments. Splitting then splits the flow of control of each cps function into a set of inner functions. Lambda lifting removes free local variables introduced by the splitting step; it copies them from one inner function to the next, yielding closed inner functions. Finally, the program is in a form simple enough to perform a one-pass partial CPS conversion. The resulting continuations are used at runtime to schedule threads.

In the rest of this section, we show how splitting, lambda lifting and CPS conversion transform the function countdown. The boxing pass has no effect on this example because it only applies to extruded variables, the address of which is retained by the "address of" operator (&).

Splitting The first transformation performed by the CPC translator is splitting. Splitting has been first described by van Wijngaarden for Algol 60 [START_REF] Van Wijngaarden | Recursive definition of syntax and semantics[END_REF], and later adapted by Thielecke to C, albeit in a restrictive way [START_REF] Thielecke | Continuations, functions and jumps[END_REF]. It translates control structures into mutually recursive functions.

Splitting is done in two steps. The first step consists in replacing every controlflow structure, such as for and while loops, by its equivalent in terms of if and goto.

cps void countdown ( int x ) { loop : if ( x <= 0) goto timeout ; printf ( " % d \ n " , x --); cpc_sleep (1); goto loop ; timeout :

printf ( " time is over !\ n " ); }

The second step uses the fact that goto are equivalent to tail calls [START_REF] Steele | Lambda, the ultimate imperative[END_REF]. It translates every labelled block into an inner function, and every jump to that label into a tail call (followed by a return) to that function. Splitting yields a program where each cps function is split in several mutually recursive, atomic functions, very similar to event handlers. Additionally, the tail positions of these inner functions are always either:

a return statement (for instance, on Section 4.1 in the previous example), a tail call to another cps function (Section 4.1), a call to an external cps function followed by a call to an inner cps function (Section 4.1).

We recognise the typical patterns of an event-driven program that we studied in Section 3: respectively returning a value to the upper layer (Fig. 1 (4)), calling a function to carry on the current computation (Fig. 2 (1)), or calling a function with a callback to resume the computation once it has returned (Fig. 1 (2)).

Another effect of splitting is the introduction of free variables, which are bound to the original encapsulating function rather than the new inner ones. For instance, the variable x is free in the function loop above. Because inner functions and free variables are not allowed in C, we perform a pass of lambda lifting to eliminate them. correct in the case of CPC, for reasons similar to the correctness of lambda lifting [START_REF] Kerneis | Continuation-passing C, compiling threads to events through continuations[END_REF].

Defunctionalising inner functions

Defunctionalisation is a compilation technique introduced by Reynolds to translate higher-order programs into first-order ones [START_REF] Reynolds | Definitional interpreters for higher-order programming languages[END_REF]. It maps every first-class function to a first-order structure that contains both an index representing the function, and the values of its free variables. These data structures are usually a constructor, whose parameters store the free variables. Function calls are then performed by a dedicated function that dispatches on the constructor, restores the content of the free variables and executes the code of the relevant function.

The dispatch function introduced by defunctionalisation is very close to a state automaton. It is therefore not surprising that defunctionalising inner functions in CPC yields an event-driven style similar to state machines (Section 3.1).

Defunctionalisation of CPC programs

Usually, defunctionalisation contains an implicit lambda-lifting pass, to make free variables explicit and store them in constructors. For example, a function fn x => x + y would be replaced by an instance of LAMBDA of int, with the free variable y copied in the constructor LAMBDA. The dispatch function would then have a case: dispatch (LAMBDA y, x) = x + y.

In this discussion, we wish to decouple this data-flow transformation from the translation of the control flow into a state machine. Therefore, we define the dispatch function as an inner function which merges the content of the other inner functions but still contains free variables. This is possible because the splitting pass does not create any closure: it introduces inner functions with free variables, but these are always called directly, not stored as first-class values whose free variables must be captured. Consider again our countdown example after the splitting pass (Fig. 3). Once defunctionalised, it contains a single inner function dispatch that dispatches on an enumeration representing the former inner function loop and timeout. As an optimisation, the recursive call to dispatch on Section 4.2 can be replaced by a goto statement. However, we cannot replace the call that follows the cps function cpc sleep(1) on Section 4.2, since we will need to provide dispatch as a callback to cpc sleep during CPS conversion, to avoid blocking.

We must then eliminate free variables and inner functions, with a lambdalifting pass. It is still correct because defunctionnalisation does not break the required invariants on tail calls. We finally reach code that is similar in style to the state-machine shown in Fig. 2.

cps void dispatch ( enum state s , int x ) { switch ( s ) { case LOOP : if ( x <= 0) goto timeout_label ; printf ( " % d \ n " , x --); cpc_sleep (1)
; dispatch ( LOOP , x ); return ; case TIMEOUT : timeout_label : printf ( " time is over !\ n " ); return ; } } cps void countdown ( int x ) { dispatch ( LOOP , x ); return ; } In this example, we have also replaced the first occurrence of dispatch with goto timeout label, as discussed above, which avoids the final function call when the counter reaches zero.

If we ignore the switch -which serves mainly as an entry point to the dispatch function, à la Duff's device [START_REF] Duff | Protothreads: simplifying eventdriven programming of memory-constrained embedded systems[END_REF] -we recognise the intermediate code generated during the first step of splitting, as having an explicit control flow using gotos but without inner functions. In retrospect, the second step of splitting, which translates gotos to inner functions, can be considered as a form a refunctionalisation, the left-inverse of defunctionalisation [START_REF] Danvy | Defunctionalization at work[END_REF].

Benefits

The translation presented here is in fact a partial defunctionalisation: each cps function in the original program gets its own dispatch function, and only inner functions are defunctionalised. A global defunctionalisation would imply a whole program analysis, would break modular compilation, and would probably not be very efficient because C compilers are optimised to compile hand-written, reasonably-sized functions rather than a giant state automaton with hundreds of states. On the other hand, since it is only partial, this translation does not eliminate the need for a subsequent CPS conversion step to translate calls to external cps functions into operations on continuations.

Despite adding a new translation step while keeping the final CPS conversion, this approach has several advantages over the CPS conversion of many smaller, mutually recursive functions performed by the current CPC translator. First, we do not pay the cost of a CPS call for inner functions. This might bring significant speed-ups in the case of tight loops or complex control flows. Moreover, it leaves with much more optimisation opportunities for the C compiler, for instance to store certain variables in registers, and reduces the number of operations on the continuations. It also makes debugging easier, avoiding numerous hops through ancillary cps functions.

Shared environments

The two main compilation techniques to handle free variables are lambda lifting, illustrated in Section 4.1 and discussed extensively in a previous article [START_REF] Kerneis | Continuation-passing C, compiling threads to events through continuations[END_REF], and environments. An environment is a data structure used to capture every free variable of a first-class function when it is defined; when the function is later applied, it accesses its variables through the environment. Environments add a layer of indirection, but contrary to lambda lifting they do not require free variables to be copied on every function call.

In most functional languages, each environment represents the free variables of a single function; a pair of a function pointer and its environment is called a closure. However, nothing prevents in principle an environment from being shared between several functions, provided they have the same free variables. We use this technique to allocate a single environment shared by inner functions, containing all local variables and function parameters.

An example of shared environments Consider once again our countdown example after splitting (Fig. 3). We introduce an environment to contain the local variables of countdown (here, there is only x). The environment is allocated (Section 4.3) and initialised (Section 4.3) when the function countdown is entered. The inner functions access x through the environment, either to read (Section 4.3) or to write it (Section 4.3). A pointer to the environment is passed from function to function (Section 4.3); hence all inner functions share the same environment. Finally, the environment is deallocated just before the last inner function exits (Section 4.3).

The resulting code is similar in style to hand-written event-driven code, with a single, heap-allocated data structure sharing the local state between a set of callbacks. Note that inner functions have no remaining free variable and can therefore be lambda-lifted trivially.

Benefits Encapsulating local variables in environments avoids having to copy them back and forth between the continuation and the native call stack. However, it does not necessarily mean that the generated programs are faster; in fact, lambda-lifted programs are often more efficient (Section 5). Another advantage of environments is that they make programs easier to debug, because the local state is always fully available, whereas in a lambda-lifted program "useless" variables are discarded as soon as possible, even though they might be useful to understand what went wrong before the program crashed.

Evaluation

In this section, we describe the implementation of eCPC, a CPC variant using shared environments instead of lambda lifting to encapsulate the local state of cps functions. We then compare the efficiency of programs generated with eCPC and CPC, and show that the latter is more efficient in most cases. This demonstrates the benefits of generating events automatically: most real-world event-driven programs are based on environments, because they are much easier to use, although systematic lambda lifting would probably yield faster code.

Implementation

The implementation of eCPC is designed to reuse as much of the existing CPC infrastructure as possible. The eCPC translator introduces two new passes: preparation and generation of environments. The former replaces the boxing pass; the latter replaces lambda lifting.

Environment preparation Environments must be introduced before the splitting pass for two reasons. First, it is easier to identify the exit points of cps functions, where the environments must be deallocated, before they are split into multiple, mutually recursive, inner functions. Furthermore, these environment deallocations occur in tail position, and have therefore an impact on the splitting pass itself.

Although deallocation points are introduced before splitting, neither allocation nor initialisation or indirect memory accesses are performed at this stage. Environments introduced during this preparatory pass are empty shells, of type void*, that merely serve to mark the deallocation points. This is necessary because not all temporary variables have been introduced at this stage (the splitting pass will generate more of them). Deciding which variables will be stored in environments is delayed to a later pass.

This preparatory pass also needs to modify how return values are handled. In the original CPC, return values are written directly in the continuation when the returning function invokes its continuation. This is made possible by the convention that the return value of a cps function is the last parameter of its continuation, hence at a fixed position on the continuation stack. Such is not the case in eCPC, where function parameters are kept in the environment rather than copied on the continuation.

In eCPC, the caller function passes a pointer to the callee, indicating the address where the callee must write its return value. 5 The preparatory pass transforms every cps function returning a type T (different from void) into a function returning void with an additional parameter of type T * ; call and return points are modified accordingly. The implementation of CPC primitives in the CPC runtime is also modified to reflect this change.

Environment generation After the splitting pass, the eCPC translator allocates and initialises environments, and replaces variables by their counterpart in the environment.

First, it collects local variables (except the environment pointer itself) and function parameters and generates the layout of the associated environment. Then, it allocates the environment and initialises the fields corresponding to the function parameters. Because this initialisation is done at the very beginning of the translated function, it does not affect the tails, thus preserving the correctness of CPS conversion. Finally, every use of variables is replaced by its counterpart in the environment, local variables are discarded, and inner functions are modified to receive the environment as a parameter instead.

The CPS conversion is kept unchanged: the issue of return values is dealt with completely in the preparatory pass and every cps function returns void at this stage.

Benchmark results

We previously designed a set of benchmarks to compare CPC to other thread libraries, and have shown that CPC is as fast as the fastest thread libraries available to us while providing at least an order of magnitude more threads [START_REF] Kerneis | Continuation-passing C, compiling threads to events through continuations[END_REF]. We reuse these benchmarks here to compare the speed of CPC and eCPC; our experimental setup is unchanged, and detailed in our previous work.

Primitive operations

We first measure the time of individual CPC primitives. Table 1 shows the relative speed of eCPC compared with CPC for each of our micro-benchmarks: t eCPC /t CPC . A value greater than 1 indicates that eCPC is slower than CPC. The slowest primitive operation in CPC is a cps function call (cps-call ), mostly because of the multiple layers of indirection introduced by continuations. This overhead is even larger in the case of eCPC: performing a cps function call is 2 to 3 times slower than with CPC. This difference of cost for cps function calls probably has an impact on the other benchmarks, making them more difficult to interpret. Context switches (switch) are around 50 % slower on every architecture, which is surprisingly high since they involve almost no manipulation of environments. Thread creation (spawn) varies a lot across architectures: more than 3 times slower on the Pentium M, but only 59 % slower on a MIPS embedded processor. Finally, condition we believe that the larger number of registers helps to limit the number of memory accesses, but we were not able to quantify this effect precisely. These benchmarks of CPC primitives show that the allocation of environments slows down eCPC in most cases, and confirms our intuition that avoiding boxing as much as possible in favour of lambda lifting is very important in CPC.

Tic-tac-toe generator Unfortunately, benchmarking individual CPC primitives gives little information on the performance of a whole program, because their cost might be negligible compared to other operations. To get a better understanding of the performance behaviour of eCPC, we wrote a trivial but highly concurrent program with intensive memory operations: a tic-tac-toe generator that explores the space of grids. It creates three threads at each step, each one receiving a copy of the current grid, hence 3 9 = 19 683 threads and as many copies of the grid.

We implemented two variants of the code, to test different schemes of memory usage. The former is a manual scheme that allocates copies of the grids with malloc before creating the associated threads, and frees each of them in one of the "leaf" threads, once the grid is completed. The latter is an automatic scheme that declares the grids as local variables and synchronises their deallocation with barriers; the grids are then automatically encapsulated, either by the boxing pass (for CPC) or in the environment (for eCPC).

Our experiment consists in launching an increasing number of generator tasks simultaneously, each one generating the 19 683 grids and threads mentioned above. We run up to 100 tasks simultaneously, ie. almost 2 000 000 CPC threads in total, and the slowest benchmark takes around 3 seconds to complete on an Intel Centrino 1,87 Ghz, downclocked to 800 MHz.

Finally, we compute the mean time per tic-tac-toe task. This ratio turns out to be independent of the number of simultaneous tasks: both CPC and eCPC scale linearly in this benchmark. We measured that eCPC is 20 % slower than CPC in the case of manual allocation (13.2 vs. 11.0 ms per task), and 18 % slower in the automatic case (31.3 vs. 26.5 ms per task). This benchmark confirms that environments add a significant overhead in programs performing a lot a memory accesses, although it is not as important as in benchmarks of CPC primitives.

Web servers To evaluate the impact of environments on more realistic programs, we reuse our web server benchmark [START_REF] Kerneis | Are events fast? Tech. rep[END_REF]. We measure the mean response time of a small web server under the load of an increasing number of simultaneous clients. The server is deliberately kept minimal, and uses one CPC thread per client. The results are shown in Fig. 4. In this benchmark, the web server compiled with eCPC is 12 % slower than the server compiled with CPC. Even on programs that spend most of their time performing network I/O, the overhead of environments remains measurable.

Conclusions

Through the analyse of real-world programs, we have identified several typical styles of control-flow and data-flow encodings in event-driven programs: callbacks or state machines for the control flow, and coarse-grained or minimal data structures for the data flow. We have then shown how these various styles can be generated from a common threaded description, by a set of automatic program transformations. Finally, we have implemented eCPC, a variant of the CPC translator using shared environments instead of lambda lifting. We have found out that, although rarely used in real-world programs because it is tedious to perform manually, lambda lifting yields better performance than environments in most of our benchmarks.

An interesting extension of our work would be to try and reverse our program transformations, in order to reconstruct threaded code from event-driven programs. This could help analysing and debugging event-driven code, or migrating legacy, hard-to-maintain event-driven programs like Polipo towards CPC or other cooperative threads implementations.

Fig. 1 .

 1 Fig. 1. Accept loop callbacks in Polipo (simplified)

1Fig. 3 .

 3 Fig. 3. CPC code after splitting

1 9 cpc_sleep ( 1 )

 91 struct env_countdown { int x }; cps void countdown ( int x ) { 3 struct env_countdown * e = malloc ( sizeof ( struct env_countdown )); 5 e -> x = x ; cps void loop ( struct env_countdown * e ) { 7 if (e -> x <= 0) { timeout (); return ; } printf ( " % d \ n " , e ->x --); ; loop ( e ); return ; } cps void timeout ( struct env_countdown * e ) { printf ( " time is over !\ n " ); free ( e ); return ; } loop ( e ); return ; }

Fig. 4 .

 4 Fig. 4. Web server benchmark

Table 1 .

 1 Ratio of speeds of eCPC to CPC

	Architecture	cps-call switch condvar spawn
	Core 2 Duo (x86-64)	2.45 1.67	1.13 2.18
	Pentium M (x86)	2.35 1.75	1.08 3.12
	MIPS-32 4KEc	2.92 1.43	0.91 1.59
	variables (condvar ) are even more surprising: not much slower on x86 and x86-64,
	and even 9 % faster on MIPS. It is unclear which combination of factors leads
	eCPC to outperform CPC on this particular benchmark only:

http://www.pps.univ-paris-diderot.fr/ ~jch/software/polipo/.

http://www.transmissionbt.com/.

Note that a similar device would be necessary to implement defunctionalisation, because the dispatch function is a generic callback which might receive many different types of return values.

Acknowledgments The authors would like to thank Andy Key, who has inspired this work, Juliusz Chroboczek for his continuous support, Peter Sewell, Chloé Azencott and Alan Mycroft for their valuable comments.

Lambda lifting

The CPC translator then makes the data flow explicit with a lambda-lifting pass. Lambda lifting, also called closure conversion, is a standard technique to remove free variables introduced by Johnsson [START_REF] Johnsson | Lambda lifting: Transforming programs to recursive equations[END_REF]. It is also performed in two steps: parameter lifting and block floating.

Parameter lifting binds every free variable to the inner function where it appears (for instance x to loop on Section 4.1 below). The variable is also added as a parameter at every call point of the function (Sections 4.1 and 4.1). Note that because C is a call-by-value language, lifted parameters are duplicated rather than shared and this step is not correct in general. It is however sound in the case of CPC because lifted functions are called in tail position: they never return, which guarantees that at most one copy of each parameter is reachable at any given time [START_REF] Kerneis | Continuation-passing C, compiling threads to events through continuations[END_REF]. Block floating is then a trivial extraction of closed, inner functions at top-level.

Lambda lifting yields a program where the data is copied from function to function, each copy living as long as the associated handler. If some piece of data is no longer needed during the computation, it will not be copied in the subsequent handlers; for instance, the variable x is not passed to the function timeout. Hence, lambda lifting produces short-lived, almost minimal data structures.

CPS conversion

Finally, the control flow is made explicit with a CPS conversion [START_REF] Plotkin | Call-by-name, call-by-value and the lambda-calculus[END_REF][START_REF] Reynolds | The discoveries of continuations[END_REF]. The continuations store callbacks and their parameters in a regular stack-like structure cont with two primitive operations: push to add a function on the continuation, and invoke to call the first function of the continuation. cps void loop ( int x , cont * k ) { if ( x <= 0) { timeout ( k ); return ; } printf ( " % d \ n " , x --); cpc_sleep (1 , push ( loop , x , k )); return ; } cps void timeout ( cont * k ) { printf ( " time is over !\ n " ); invoke ( k ); return ; } cps void countdown ( int x , cont * k ) { loop (x , k ); return ; } CPS conversion turns out to be an efficient and systematic implementation of the layered callback scheme described in Section 3.1. Note that, just like lambda lifting, CPS conversion is not correct in general in an imperative call-by-value language, because of duplicated variables on the continuation. It is however


Jean B Lasserre
email: lasserre@laas.fr

A Lagrangian relaxation view of linear and semidefinite hierarchies

Keywords: Global and 0/1 optimization, approximation algorithms, linear and semidefinite relaxations, Lagrangian relaxations

We consider the general polynomial optimization problem P : f * = min{f (x) : x ∈ K} where K is a compact basic semi-algebraic set. We first show that the standard Lagrangian relaxation yields a lower bound as close as desired to the global optimum f * , provided that it is applied to a problem P equivalent to P, in which sufficiently many redundant constraints (products of the initial ones) are added to the initial description of P. Next we show that the standard hierarchy of LP-relaxations of P (in the spirit of Sherali-Adams' RLT) can be interpreted as a brute force simplification of the above Lagrangian relaxation in which a nonnegative polynomial (with coefficients to be determined) is replaced with a constant polynomial equal to zero. Inspired by this interpretation, we provide a systematic improvement of the LP-hierarchy by doing a much less brutal simplification which results into a parametrized hierarchy of semidefinite programs (and not linear programs any more). For each semidefinite program in the parametrized hierarchy, the semidefinite constraint has a fixed size O(n k ), independently of the rank in the hierarchy, in contrast with the standard hierarchy of semidefinite relaxations. The parameter k is to be decided by the user. When applied to a non trivial class of convex problems, the first relaxation of the parametrized hierarchy is exact, in contrast with the LP-hierarchy where convergence cannot be finite. When applied to 0/1 programs it is at least as good as the first one in the hierarchy of semidefinite relaxations. However obstructions to exactness still exist and are briefly analyzed. Finally, the standard semidefinite hierarchy can also be viewed as a simplification of an extended Lagrangian relaxation, but different in spirit as sums of squares (and not scalars) multipliers are allowed.

Introduction

Recent years have seen the development of (global) semi-algebraic optimization and in particular LP-or semidefinite relaxations for the polynomial optimization problem:

P : f * = min x {f (x) : x ∈ K } (1.1)
where f ∈ R[x] is a polynomial and K ⊂ R n is the basic semi-algebraic set

K = { x ∈ R n : g j (x) ≥ 0, j = 1, . . . , m}, (1.2)
for some polynomials g j ∈ R[x], j = 1, . . . , m.

In particular, associated with P are two hierarchies of convex relaxations:

-Semidefinite relaxations based on Putinar's certificate of positivity on K [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF], where the d-th convex relaxation of the hierarchy is a semidefinite program which solves the optimization problem

γ d = max t,σ j { t : f -t = σ 0 + n j=1 σ j g j }.
(

The unknowns σ j are sums of squares polynomials with the degree bound constraint degree σ j g j ≤ 2d, j = 0, . . . , m, and the expression in (1.3) is a certificate of positivity on K for the polynomial x → f (x)t.

-LP-relaxations based on Krivine-Stengle's certificate of positivity on K [START_REF] Krivine | [END_REF][START_REF] Stengle | A Nullstellensatz and a Positivstellensatz in semialgebraic geometry[END_REF], where the d-th convex relaxation of the hierarchy is a linear program which solves the optimization problem

θ d = max λ≥0,t {t : f -t = (α,β)∈N 2m d λ αβ   m j=1 g α j j   ×   m j=1 (1 -g j ) β j      , (1.4)
where N 2m d = {(α, β) ∈ N 2m : j α j + β j ≤ d}. The unknown are t and the nonnegative scalars λ = (λ αβ ), and it is assumed that 0 ≤ g j ≤ 1 on K (possibly after scaling) and the family {g i , 1g i } generates the algebra R[x] of polynomials. Problem (1.4) is an LP because stating that the two polynomials in both sides of "=" are equal yields linear constraints on the λ αβ 's. For instance, the LP-hierarchy from Sherali-Adams' RLT [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF] and their variants [START_REF] Sherali | A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems[END_REF] are of this form. See more details in §3. [START_REF] Benabbas | Extending SDP integrality gaps to Sherali-Adams with applications to Quadratic Programming and MaxCut-Gain[END_REF].

In both cases, (γ d ) and (θ d ), d ∈ N, provide two monotone nondecreasing sequences of lower bounds on f * and if K is compact then both converge to f * as one let d increase. For more details as well as a comparison of such relaxations the interested reader is referred to e.g. Lasserre [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF][START_REF] Lasserre | Semidefinite programming vs. LP relaxations for polynomial programming[END_REF] and Laurent [START_REF] Laurent | A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming[END_REF], as well as Chlamtac and Tulsiani [START_REF] Chlamtac | Convex relaxations and integrality gaps[END_REF] for the impact of LP-and SDP-hierarchies on approximation algorithms in combinatorial optimization.

Of course, in principle, one would much prefer to solve LP-relaxations rather than semidefinite relaxations (i.e. compute θ d rather than γ d ) because present LP-software packages can solve problems with millions of variables and constraints, which is far from being the case for semidefinite solvers. And so the hierarchy (1.3) applies to problems of modest size only unless some sparsity or symmetry is taken into account in which case specialized variants can handle problems of much larger size. However, on the other hand, the LP-relaxations (1.4) suffer from several serious theoretical and practical drawbacks. For instance, it has been shown in [START_REF] Lasserre | Semidefinite programming vs. LP relaxations for polynomial programming[END_REF][START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF] that the LPrelaxations cannot be exact for most convex problems, i.e., the sequence of the associated optimal values converges to the global optimum only asymptotically and not in finitely many steps. Moreover, the LPs of the hierarchy are numerically ill-conditioned. This is in contrast with the semidefinite relaxations (1.3) for which finite convergence takes place for convex problems where ∇ 2 f (x * ) is positive definite at every minimizer x * ∈ K (see de Klerk and Laurent [START_REF] De Klerk | On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems[END_REF]Corollary 3.3]) and occurs at the first relaxation for SOS-convex1 problems [START_REF] Lasserre | Convexity in semi-algebraic geometry and polynomial optimization[END_REF]Theorem 3.3]. In fact, as demonstrated in recent works of Marshall [START_REF] Marshall | Representation of non-negative polynomials, degree bounds and applications to optimization[END_REF] and Nie [START_REF] Nie | Optimality Conditions and Finite Convergence of Lasserre's Hierarchy[END_REF], finite convergence is generic (even for non convex problems).

So would it be possible to define a hierarchy of convex relaxations in between (1.3) and (1.4), i.e., with some of the nice features of the semidefinite relaxations but with a much less demanding computational effort (hence closer to the LP-relaxations)? This paper is a contribution in this direction.

Contribution. This paper consists of two contributions: In the first contribution which is of theoretical nature, we describe a new hierarchy of convex relaxations for P with the following feature. Each relaxation in the hierarchy is a finite-dimensional convex optimization problem of the form:

ρ d = max λ { G d (λ) : λ ≥ 0}, (1.5)
where G d (•) is the concave function defined by: (b) For convex problems P, i.e., when f, -g j are convex, j = 1, . . . , m, and Slater's condition holds, the convergence is finite and occurs at the first relaxation, i.e., ρ 1 = f * , in contrast with the LP-relaxations (1.4) where convergence cannot be finite (and is very slow on simple trivial examples). In fact computing ρ 1 is just applying the standard dual method of multipliers (or Lagrangian relaxation) to the convex problem P.

G d (λ) := min x {f (x) - (α,β)∈N 2m d λ αβ   m j=1 g α j j (x)   ×   m j=1 (1 -g j (x)) β j      . ( 1
(c) For 0/1 optimization, i.e., when K ⊆ {0, 1} n , finite convergence takes place and the optimal value ρ d provides a better lower bound than the one obtained with Sherali-Adams' RLT hierarchy [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF]. In fact, the latter is solving (1.4) with only a subset of the products that appear in (1.4).

(d) Finally, (1.5) has a nice interpretation in terms of the dual method of Non Linear Programming (or Lagrangian relaxation). To see this, consider the optimization problem Pd defined by: min

x {f (x) : g j (x) α j (1 -g j (x)) β j ≥ 0, (α, β) ∈ N 2m d } (1.7)
which has same value f * as P because Pd is just P with additional redundant constraints; and notice that P1 = P. Then solving (1.5) is just applying the dual method of multipliers in Non Linear Programming to Pd ; see e.g. [START_REF] Bertsekas | Convex Analysis and Optimization[END_REF]Chapter 8]. In general one obtains only a lower bound on the optimal value of Pd when P is not a convex program). And so our result states that the Lagrangian relaxation applied to Pd provides a lower bound as close to f * as desired, provided that d is sufficiently large, i.e., provided that sufficiently many redundant constraints are added to the description of P.

Note in passing that this provides a rigorous rationale for the well-known fact that adding redundant constraints helps for solving P. Indeed, even though the new problems Pd , d ∈ N, are all equivalent to P, their Lagrangian relaxations are not equivalent to that of P.

Practical and computational considerations

Our second contribution has a practical and algorithmic flavor. Even though (1.5) is a convex optimization problem, evaluating G d (λ) at a point λ ≥ 0 requires computing the unconstrained global minimum of the function

x → L d (x, λ) := f (x) - (α,β)∈N 2m d λ αβ   m j=1 g j (x) α j   ×   m j=1 (1 -g j (x)) β j   , (1.8)
an NP-hard problem in general. After all, in principle the goal of Lagrangian relaxation is to end up with a problem which is easier to solve than P, and so, in this respect, the hierarchy (1.5) is not practical. So in this second part of the paper, we first show that the LP-relaxations (1.4) can be interpreted as a way to "restrict" and simplify the hierarchy (1.5) by a simple and brute force trick, so as to make it tractable (but of course less efficient). Namely, a certain nonnegative polynomial (whose coefficients have to be determined) is imposed to be the constant polynomial equal to zero! More precisely, the nonnegative vector λ in (1.5) is restricted to a polytope so as to make the polynomial L d in (1.8) constant! In fact, if one had initially defined the LP-relaxations (1.4) as this brute force (and even brutal) simplification of (1.5), it would have been hard to justify.

Inspired by this interpretation, we propose a systematic way to define improved versions of the LP-hierarchy (1.4) by simplifying (1.5) in a much less brutal manner. We now impose the same nonnegative polynomial L dt to be an SOS polynomial of fixed degree 2k (rather than the zero polynomial in (1.4)). The increase of complexity is completely controlled by the parameter k ∈ N and is chosen by the user. That is, in the new resulting hierarchy (parametrized by k), each LP of the hierarchy (1.4) now becomes a semidefinite program but whose size of the semidefiniteness constraint is fixed and equal to n+k n , independently of the rank d in the hierarchy. (It is known that crucial for solving semidefinite programs is the size of the LMIs involved rather than the number of variables.) The level k = 0 of complexity corresponds to the original LP-relaxations (1.4), the level k = 1 corresponds to a hierarchy of semidefinite programs with an Linear Matrix Inequality (LMI) of size (n + 1), etc. To fix ideas, let us mention that for k = 1, the first relaxation (i.e., d = 1) is even stronger than the first relaxation of the hierarchy (1.3) as it takes into account products of linear constraints; and so for instance, when applied to the celebrated MAXCUT problem, the first relaxation has the Goemans-Williamson's performance guarantee. Moereover, when k = 1 one obtains the so-called "Sherali-Adams + SDP" hierarchy already used for approximating some 0/1 optimization problems. So an important issue is: What do we gain by this increase of complexity?

Of course, from a computational complexity point of view, one way got evaluate the efficiency of those relaxations is to analyze whether they help reduce integrality gaps, e.g. for some 0/1 optimization problems. For the level k = 1 (i.e. the "Adams-Sherali + SDP hierarchy") some negative results in this direction have been provided in Benabbas and Magen [START_REF] Benabbas | SDP gaps from pairwise independence[END_REF], and in Benabbas et al. [START_REF] Benabbas | Extending SDP integrality gaps to Sherali-Adams with applications to Quadratic Programming and MaxCut-Gain[END_REF].

But in a different point of view, we claim that a highly desirable property for a general purpose method (e.g., the hierarchies (1.3) or (1.4)) aiming at solving NP-hard optimization problems, is to behave "efficiently" when applied to a class of problems considered relatively "easy" to solve. Otherwise one might raise reasonable doubts on its efficiency for more difficult problems, not only in a worst-case sense but also in "average". Convex problems P as in (1.1)-(1.2), i.e., when f, -g j are convex, form the most natural class of problems which are considered easy to solve by some standard methods of Non Linear Programming; see e.g. Ben-tal and Nemirovski [START_REF] Ben-Tal | Lectures on Modern Convex Optimization[END_REF]. We have already proved that the hierarchy (1.3) somehow recognizes convexity. For instance, finite convergence takes places as soon as ∇ 2 f (x * ) is positive definite at every global minimizer x * ∈ K (see deKlerk and Laurent [START_REF] De Klerk | On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems[END_REF]); moreover, SOS-convex programs are solved at the first step of the hierarchy as shown in Lasserre [START_REF] Lasserre | Convexity in semi-algebraic geometry and polynomial optimization[END_REF]. On the other hand, the LP-hierarchy (1.4) behaves poorly on such problems as the convergence cannot be finite; see e.g. Lasserre [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF][START_REF] Lasserre | Semidefinite programming vs. LP relaxations for polynomial programming[END_REF].

We prove that the gain by this (controlled) increase of complexity is precisely to permit finite convergence (and at the first step of the hierarchy) for a non trivial class of convex problems. For instance with k = 1 the resulting hierarchy of semidefinite programs solves convex quadratic programs exactly at the first step of the hierarchy. And more generally, for k > 1, the first relaxation is exact for SOS-convex2 problems of degree at most k. On the other hand, we show that for non convex problems, exactness at some relaxation in the hierarchy still implies restrictive conditions.

Main result 2.1 Notation and definitions

Let R[x] be the ring of polynomials in the variables

x = (x 1 , . . . , x n ). Denote by R[x] d ⊂ R[x]
the vector space of polynomials of degree at most d, which forms a vector space of dimension s(d) = n+d d , with e.g., the usual canonical basis (x α ) of monomials. Also, denote by Σ

[x] ⊂ R[x] (resp. Σ[x] d ⊂ R[x] 2d )
the space of sums of squares (s.o.s.) polynomials (resp. s.o.s. polynomials of degree at most 2d).

If f ∈ R[x] d , write f (x) = α∈N n d f α x α in
the canonical basis and denote by f = (f α ) ∈ R s(d) its vector of coefficients. Finally, let S n denote the space of n × n real symmetric matrices, with inner product A, B = trace AB, and where the notation A 0 (resp. A ≻ 0) stands for A is positive semidefinite. With g 0 := 1, the quadratic module Q(g 1 , . . . , g m ) ⊂ R[x] generated by polynomials g 1 , . . . , g m , is defined by

Q(g 1 , . . . , g m ) := { m j=0 σ j g j : σ j ∈ Σ[x]}.
We briefly recall two important theorems by Putinar [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] and Krivine-Stengle [START_REF] Krivine | [END_REF][START_REF] Stengle | A Nullstellensatz and a Positivstellensatz in semialgebraic geometry[END_REF] respectively, on the representation of polynomials positive on K, Theorem 2.1 Let g 0 = 1 and K in (1.2) be compact.

(a) If the quadratic polynomial

x → M -x 2 belongs to Q(g 1 , . . . , g m ) and if f ∈ R[x] is strictly positive on K then f ∈ Q(g 1 , . . . , g m ).
(b) Assume that 0 ≤ g j ≤ 1 on K for every j, and the family {g j , 1 -

g j } generates R[x]. If f is strictly positive on K then f = α,β∈N m c αβ j g α j j ℓ (1 -g ℓ ) β ℓ ,
for some finitely many nonnegative scalars (c αβ ).

Main result

With K as in (1.2) we make the following assumption:

Assumption 1 K is compact and 0 ≤ g j ≤ 1 on K for all j = 1, . . . , m. Moreover, the family of polynomials {g j , 1g j } generates the algebra R[x].

Notice that if K is compact and Assumption 1 does not hold, one may always rescale the variables x i so as to have K ⊂ [0, 1] n , and then add redundant constraints 0 ≤ x i ≤ 1 for all i = 1, . . . , m. Then the family {g j , 1g j } (which includes x j and 1x j for all j) generates the algebra R[x] and Assumption 1 holds. With d ∈ N and 0

≤ λ = (λ αβ ), (α, β) ∈ N 2m d , let λ → G d (λ)
be the function defined in (1.6), with associated problem: Proof. We first prove that ρ d+1 ≥ ρ d for all d, so that the sequence (ρ d ), d ∈ N, is monotone nondecreasing. Let 0 ≤ λ = (λ αβ ) with (α, β) ∈ N 2m d . Then 0 ≤ λ with λαβ = λ αβ whenever (α, β) ∈ N 2m d , and λαβ = 0 whenever |α + β| > d, is such that G d+1 ( λ) = G d (λ) and so ρ d+1 ≥ ρ d . Next, let ǫ > 0 be fixed, arbitrary. The polynomial ff * + ǫ is positive on K and therefore, by [START_REF] Stengle | A Nullstellensatz and a Positivstellensatz in semialgebraic geometry[END_REF], [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF]Theorem 2.23

ρ d = max λ { G d (λ) : λ ≥ 0}. ( 2
], f -(f * -ǫ) = (α,β)∈N 2m d c ǫ αβ   m j=1 g α j j     m j=1 (1 -g j ) β j   ,
for some nonnegative vector of coefficients c ǫ = (c ǫ αβ ). Equivalently,

f - (α,β)∈N 2m d c ǫ αβ   m j=1 g α j j     m j=1 (1 -g j ) β j   = (f * -ǫ).
Letting

d ǫ := max α,β {|α + β| : c ǫ αβ > 0}, we obtain f * ≥ G dǫ (c ǫ ) = f * -ǫ.
And so

f * ≥ max λ {G dǫ (λ) : λ ≥ 0} ≥ f * -ǫ.
As ǫ > 0 was arbitrary, the desired result follows.

Corollary 2.1 Let K be as in (1.2), Assumption (1) hold and let Pd , d ∈ N, be as in (1.7). Then for every ǫ > 0 there exists d ǫ ∈ N such that for every d ≥ d ǫ , the Lagrangian relaxation of Pd , yields a lower bound

f * -ǫ ≤ ρ d ≤ f * .
This follows from Theorem 2.2 and the fact that computing ρ d is just solving the Lagrangian relaxation associated with Pd . So the interpretation of Corollary 2.1 is that the Lagrangian relaxation technique in non convex optimization can provide a lower bound as close as desired to the global optimum f * provided that it is applied to an equivalent formulation of P that contains sufficiently many redundant constraints which are products of the original ones. It also provides a rigorous rationale for the well-known fact that adding redundant constraints helps solve P. Indeed, even though the new problems Pd , d ∈ N, are all equivalent to P, their Lagrangian relaxations are not equivalent to that of P.

Convex programs

In this section, the set K is not assumed to be compact.

Theorem 2.3 Let K be as in (1.2) and assume that f and -g j are convex, j = 1, . . . , m. Moreover, assume that Slater's condition3 holds and f * > -∞.

Then the hierarchy of convex relaxations (1.5) has finite convergence at step d = 1, i.e., ρ 1 = f * , and

ρ 1 = G 1 (λ * ) for some nonnegative λ * ∈ R m .
Proof. This is because the dual method applied to P (i.e. P1 ) converges, i.e.,

f * = max λ≥0    min x {f (x) - m j=1 λ j g j (x)}    = max λ {G 1 (λ) : λ ≥ 0} = ρ 1 .
Next, let λ (n) be a maximizing sequence, i.e., G 1 (λ (n) ) → f * as n → ∞. Since Slater's condition holds (say at some x 0 ∈ K), one has

G 1 (λ (0) ) ≤ G 1 (λ (n) ) ≤ f (x 0 ) - m j=1 λ (n) j g j (x 0 ),
for all n, and so λ

(n) j ≤ (f (x 0 )-G 1 (λ (0)
))/g j (x 0 ) for every j = 1, . . . , m, and all n ≥ 1. So there is a subsequence (n k ), k ∈ N, and

λ * ∈ R m + , such that λ (n k ) → λ * ≥ 0 as k → ∞. Finally, let x ∈ R n be fixed, arbitrary. From G 1 (λ (n k ) ) ≤ f (x) - m j=1 λ (n k ) j g j (x), ∀ k, letting k → ∞ yields f * ≤ f (x) - m j=1
λ * j g j (x).

As x ∈ R n was arbitrary, this proves G 1 (λ * ) ≥ f * , which combined with

G 1 (λ * ) ≤ f * yields the desired result G 1 (λ * ) = f * .
Observe that this does not hold for the LP-relaxations (1.4) where generically θ d < f * for every d ∈ N; see e.g. [START_REF] Lasserre | Semidefinite programming vs. LP relaxations for polynomial programming[END_REF][START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF].

Interpreting the LP-relaxations

Observe that the LP-relaxations (1.4) can be written

θ d = max λ≥0,t { t : L d (x, λ) -t = 0, ∀x ∈ R n } , (3.1)
where L d has been defined in (1.8).

And so the LP-relaxations (1.4) can be interpreted as simplifying (2.1) by restricting the nonnegative orthant {λ : λ ≥ 0} to its subset of λ's that make the polynomial x → L(x, λ)t constant and equal to zero, instead of being only nonnegative. This subset being a polyhedron, solving (3.1) reduces to solving a linear program. At first glance, such an a priori simple and naive brute force simplification might seem unreasonable (to say the least). But of course the LP-relaxations (1.4) where not defined this way. Initially, the Sherali-Adams' RLT hierarchy [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF] was introduced for 0/1 programs and finite convergence was proved by using ad hoc arguments. But in fact, the rationale behind convergence of the more general LP-relaxations (1.4) is the Krivine-Stengle positivity certificate [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF]Theorem 2.23].

However, even though this brute force simplification still preserves the convergence θ d → f * thanks to [12, Theorem 2.23], we have already mentioned that it also implies serious theoretical (and practical) drawbacks for the resulting LP-relaxations (like slow asymptotic convergence for convex problems and numerical ill-conditioning).

A parametrized hierarchy of semidefinite relaxations

However, inspired by this interpretation we propose a systematic way to improve the LP-relaxations (1.4) along the same lines but by doing a much less brutal simplification of (2.1). Indeed, one may now impose on the same nonnegative polynomial x → L(x, λ)t to be a sum of squares (SOS) polynomial σ of degree at most 2k (instead of being constant and equal to zero as in (3.1)), and solve the resulting hierarchy of optimization problems:

q k d = max λ,t,σ t s.t. L d (x, λ) -t = σ, ∀x ∈ R n λ ≥ 0, σ ∈ Σ[x] k , (3.2
x → L d (x, λ) -t := β∈N n s L β (λ, t) x β ,
where s = d max j [deg g j ] and L β (λ, t) is linear in (λ, t) for each β ∈ N n s . Next, for k ∈ N such that 2k ≤ s, let v k (x) be the vector of the monomial basis (x β ), β ∈ N n k , of R[x] k , and write

v k (x) v k (x) T = β∈N n 2k x β B β ,
for some appropriate real symmetric matrices (B β ), β ∈ N n 2k . Then problem (3.2) is the semidefinite program:

q k d = max λ,t,Q t s.t. L β (λ, t) = B β , Q , ∀β ∈ N n 2k L β (λ, t) = 0, ∀β ∈ N n s , |β| > 2k λ ≥ 0; Q = Q T 0, (3.3)
where

Q is a n+k n × n+k n real symmetric matrix. Of course q k d ≥ θ d (= q 0 d
) for all d because with σ = 0 one retrieves (1.4). Moreover in the semidefinite program (3.3), the semidefinite constraint Q 0 is concerned with a real symmetric n+k n × n+k n matrix, independently of the rank d in the hierarchy. For instance if k = 1 then σ is a quadratic SOS and Q has size (n + 1) × (n + 1). In other words, even if the number of variables λ = (λ αβ ) increases fast with d, the LMI constraint Q 0 has fixed size, in contrast with the semidefinite relaxations (1.3) where the size of the LMIs increases with d. And it is a well-known fact that crucial for solving semidefinite program is the size of the LMIs involved rather than the number of variables.

Sherali-Adams' RLT for 0/1 programs

Consider 0/1 programs with f ∈ R[x], and feasible set K = {x : Ax ≤ b} ∩ {0, 1} n , for some real matrix A ∈ R m×n and some vector b ∈ R m . The Sherali-Adams's RLT hierarchy [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF] belongs to the family of LP-relaxations (1.4) but with a more specific form since K ⊂ [0, 1] n . Notice that the family {1,

x 1 , (1 -x 1 ), . . . , x n , (1 -x n )} generates the algebra R[x]. Let g ℓ (x) = (b -Ax) ℓ , ℓ = 1, . . . , m, and g 0 (x) = 1.
Following the definition of the Sherali-Adams' RLT in [START_REF] Sherali | A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems[END_REF], the resulting linear program at step d in the hierarchy reads:

θ d = max λ≥0,t,h t : f (x) -t = n i=1 h i (x) x i (1 -x i ) + m ℓ=0 I,J ⊂{1,...,n} I∩J=∅;|I∪J|≤d λ ℓ IJ g ℓ (x) i∈I x i j∈J (1 -x j ); h i ∈ R[x] d-1 i = 1, . . . , n} , (3.4)
where λ is the nonnegative vector (λ ℓ IJ ). (If there are linear equality constraints g ℓ (x) = 0 the corresponding variables λ ℓ IJ are not required to be nonnegative.) So all products between the g ℓ 's are ignored (see the paragraph before Lemma 1 in [17, p. 414]) even though they might help tighten the relaxations. In the literature the dual LP of (3.4) is described rather than (3.4) itself.

In this context, the problem Pd equivalent to P and defined in (1.7) by adding redundant constraints formed with products of original ones, reads:

(x) : x α x j (1 -x j ) = 0, j = 1, . . . , n; α ∈ N n d-1 ; g ℓ (x) i∈I x j j∈J (1 -x j ) ≥ 0, ℓ = 0, . . . , m, I, J ⊂ {1, . . . , n}; I ∩ J = ∅; |I ∪ J| ≤ d}.
Hence the 0/1 analogue of (3.2) reads

q k d = max λ≥0,t,h t : f (x) -t = σ(x) + n i=1 h i (x) x i (1 -x i ) + m ℓ=0 I,J ⊂{1,...,n} I∩J=∅;|I∪J|≤d λ ℓ IJ g ℓ (x) i∈I x i j∈J (1 -x j ); σ ∈ Σ[x] k ; h i ∈ R[x] d-1 i = 1, . . . , n} . (3.5)
For 0/1 programs with linear or quadratic objective function, and for every k ≥ 1, the first semidefinite relaxation (3.5), i.e., with d = 2, is at least as powerful as that of the standard hierarchy of semidefinite relaxations (1.3). Indeed (3.5) contains products g ℓ (x)x j or g ℓ (x)(1-x k ), for all (ℓ, j, k), which do to not appear in (1.3) with d = 1. And so in particular, the first such relaxation for MAXCUT has the celebrated Goemans-Williamson's performance guarantee while the standard LP-relaxations (1.4) do not. On the other hand, for 0/1 problems and for the parameter value k = 1, the hierarchy (3.5) is what is called the Sherali-Adams + SDP hierarchy (basic SDP-relaxation + RLT hierarchy) in e.g. Benabas and Magen [START_REF] Benabbas | Extending SDP integrality gaps to Sherali-Adams with applications to Quadratic Programming and MaxCut-Gain[END_REF] and Benabbas et al. [START_REF] Benabbas | SDP gaps from pairwise independence[END_REF]; and in [START_REF] Benabbas | Extending SDP integrality gaps to Sherali-Adams with applications to Quadratic Programming and MaxCut-Gain[END_REF][START_REF] Benabbas | SDP gaps from pairwise independence[END_REF] the authors show that any (constant) level d of this hierarchy, viewed as a strengthening of the basic SDP-relaxation, does not make the integrality gap decrease.

In fact, and in view of our previous analysis, the "Sherali-Adams + SDP" hierarchy should be viewed as a (level k = 1)-strengthening of the basic Sherali-Adams' LP-hierarchy (3.4) rather than a strengthening of the basic SDP relaxation.

Comparing with standard LP-relaxations

As asked in introduction: What do we gain by going from the LP hierarchy (1.4) to the semidefinite hierarchy (3.3) parametrized by k? Some answers are provided below.

Convex problems

Recall that a highly desirable property for a general purpose method aiming at solving NP-hard optimization problems, is to behave efficiently when applied to a class of problems considered relatively easy to solve. Otherwise one might raise reasonable doubts on its efficiency for more difficult problems not only in a worst-case sense but also in average. And convex problems P as in (1.1)-(1.2), i.e., when f, -g j are convex, form the most natural class of problems which are considered easy to solve by some standard methods of Non Linear Programming. (a) If max[deg f, deg g j ] ≤ 2k and f, -g j are all SOS-convex, then q k 1 = f * , i.e., the first relaxation of the hierarchy (3.2) parametrized by k, is exact.

Proof. Under the assumptions of Theorem 4.1, P has a minimizer x * ∈ K and the Karush-Kuhn-Tucker optimality conditions hold at (x

* , λ * ) ∈ K × R m + for some λ * ∈ R m + . And so if k = 1, the Lagrangian polynomial L 1 (•, λ * ) -f * is a nonnegative quadratic polynomial and so an SOS σ * ∈ Σ[x] 1 . Therefore as q 1 d ≤ f * for all d, the triplet (λ * , f * , σ *
) is an optimal solution of (3.2) with k = d = 1, which proves (a).

Next, if k > 1 and f, -g j are all SOS-convex then so is the Lagrangian polynomial L 1 (•, λ * )-f * . In addition, as ∇ x L 1 (x * , λ * ) = 0 and L 1 (x * , λ * )-f * = 0, the polynomial L 1 (•, λ * )f * is SOS; see e.g. Helton and Nie [START_REF] Helton | Semidefinite representation of convex sets and convex hulls[END_REF]Lemma 4.2]. Hence L 1 (•, λ * )f * = σ * for some σ * ∈ Σ[x] k , and again, the triplet (λ * , f * , σ * ) is an optimal solution of (3.2) with d = 1, which proves (b).

Hence by simplifying (1.5) in a less brutal manner than in (1.4) one recovers a nice and highly desirable property for the resulting hierarchy. The price to pay is to pass from solving a hierarchy of LPs to solving hierarchy of semidefinite programs; however the increase in complexity is controlled by the parameter k since the size of the LMI in the semidefinite program (3.3) is O(n k ), independently of the rank d in the hierarchy.

Obstructions to Exactness

On the other hand, for non convex problems, exactness at level-d of the hierarchy (3.2), i.e., finite convergence after d rounds, still implies restrictive conditions on the problem: where V ⊂ R n (see (4.2) below) is a variety defined from some products of the polynomials g j 's and (1g j )'s. And if k = 0 then f must be constant on the variety V.

Proof.

If (3.2) is exact at level d ∈ N, then L d (x, λ * ) -f * = σ(x), ∀x ∈ R n ,
for some λ * ≥ 0 and some σ ∈ Σ[x] k . Equivalently,

f (x) -f * = σ(x) + (α,β)∈N 2m d λ * αβ   m j=1 g j (x) α j   ×   m j=1 (1 -g j (x)) β j   .
Then evaluating at x = x * yields σ(x * ) = 0 and

λ * αβ > 0 ⇒ ∃j ∈ I 1 (x * ) s.t. α j > 0, or ∃j ∈ I 2 (x * ) s.t. β j > 0.
So let Ω := {(α, β) ∈ N 2m d : λ * αβ > 0} and for every (α, β) ∈ Ω let

J 1 αβ := {j ∈ I 1 (x * ) : α j > 0}, J 2 αβ := {j ∈ I 2 (x * ) : β j > 0}.
Next, define V ⊂ R n to be the real variety:

{x ∈ R n :    j∈J 1 αβ g j (x)       j∈J 2 αβ (1 -g j (x))    = 0, ∀ (α, β) ∈ Ω } . (4.2)
Then for every x ∈ V, one obtains f (x)f * = σ(x) ≥ 0, which means that f * is the global minimum of f on V. If k = 0 then σ is constant and equal to zero. And so f (x)f * = 0 for all x ∈ V.

Hence Corollary 4.1 shows that exactness at some step d of the hierarchy (3.2) imposes rather restrictive conditions on problem P. Namely, the global optimum f * (resp. the global minimizer x * ∈ K) must also be the global optimum (resp. a global minimizer) of problem (4.1). For instance, suppose that only one constraint, say g k (x) ≥ 0, is active at x * . Then f * (resp. x * ) is also the global minimum (resp. a global minimizer) of f on the variety {x : g k (x) = 0}. And if k = 0 then f must be constant on the variety V! Example 1 If K is the (compact) polytope {x : a T j x ≤ 1, j = 1, . . . , m} for some vectors (a j ) ⊂ R n , then invoking a result by Handelman [START_REF] Handelman | Representing polynomials by positive linear functions on compact convex polyhedra[END_REF], one does not need the polynomials {1g j } in the definition (1.8) of L d . So for instance, suppose that I 1 (x * ) = {ℓ} at a global minimizer x * ∈ K. Then exactness at some step d of the hierarchy (3.2) imposes that f * should also be the global minimum of f on the whole hyperplane V = {x : a T ℓ x = 1}; for non convex functions f , this is a serious restriction. Moreover, if k = 0 then f must be constant on the hyperplane V.

Concerning exactness for 0/1 polynomial optimization: Corollary 4.2 Let K = {x : Ax ≤ b} ∩ {0, 1} n and let x * ∈ K be an optimal solution of f * = min{f (x) : x ∈ K}. Assume that Ax * < b, i.e., no constraint is active at x * .

(a) The Sherali-Adams' RLT relaxation (3.4) is exact at step d in the hierarchy only if f (x) = f (x * ) = f * for all x in the set

V := {x ∈ {0, 1} n : i∈I x i j∈J (1 -x j ) = 0, (I, J) ∈ Q},
where Q is some finite set of couples (I, J) satisfying I∩J = ∅ and |I∪J| ≤ d.

(b) Similarly, the semidefinite relaxation (3.5) is exact at step d only if x * is also a global minimizer of min{f (x) : x ∈ V} for some V as in (a).

Proof. (a) Exactness implies that the polynomial x → f (x)f * has the representation described in (3.4) for some polynomials (h i ) ⊂ R[x] d-2 and some nonnegative scalars (λ ℓ IJ ). Evaluating both sides of (3.4) at x = x * and using g ℓ (x * ) > 0 for all ℓ = 0, . . . , m, yields

λ ℓ IJ > 0 =⇒ i∈I x * i j∈J (1 -x * j ) = 0. ( 4.3)
Let V be as in Corollary 4.2 with Q := {(I, J) : ∃ ℓ s.t. λ ℓ IJ > 0}. Then from the representation of x → f (x)f * in (3.4) we obtain f (x)f * = 0 for all x ∈ V and the result follows. For (b) a similar argument is valid but now using the representation of f (x)f * described in (3.5). And so exactness yields (4.3) as well as σ(x * ) = 0. Next, for every x ∈ V we now obtain f (x)f * = σ(x) ≥ 0 because σ is SOS.

The constraints Ax ≤ b play no explicit role in the definition of the set V. Moreover, if f discriminates all points of the hypercube {0, 1} n then exactness of the Sherali-Adams' RLT implies that V must be the singleton {x * }.

On the hierarchy of semidefinite relaxations

Similarly, the hierarchy of semidefinite relaxations (1.3) also has an interpretation in terms of simplifying an extended Lagrangian relaxation of P. Indeed consider the hierarchy of optimization problems For each d ∈ N, problem (4.4) is an obvious relaxation of P and in fact is an extended Lagrangian relaxation of P where the multipliers are now allowed to be SOS polynomials with a degree bound, instead of constant nonnegative polynomials (i.e., SOS polynomials of degree zero).

If K is compact and the quadratic module 3) simplify (4.4) by imposing on the nonnegative polynomial x → f (x)j σ j (x)g j (x)t to be an SOS polynomial σ 0 ∈ Σ[x] d (rather than just being nonnegative). But the spirit is different from the LP-relaxations as there is no problem Pd obtained from P by adding finitely many redundant constraints and equivalent to P. Instead of adding more and more redundant constraints and doing a standard Lagrangian relaxation to Pd , one applies an extended Lagrangian relaxation to P with SOS multipliers of increasing degree (instead of nonnegative scalars). And in contrast to LP-relaxations, there is no obstruction to exactness (i.e., finite convergence). In fact, it is quite the opposite since as demonstrated recently in Nie [START_REF] Nie | Optimality Conditions and Finite Convergence of Lasserre's Hierarchy[END_REF], finite convergence is generic!

Conclusion

We have shown that the hierarchy of LP-relaxations (1.4) has a rather surprising interpretation in terms of the Lagrangian relaxation applied to a problem P equivalent to P (but with redundant constraints formed with product of polynomials defining the original constraints of P). Indeed it consists of the brute force simplification of imposing on a certain nonnegative polynomial to be the constant polynomial equal to zero, a very restrictive condition.

However, inspired by this interpretation, one has provided a systematic strategy to improve the LP-hierarchy by doing a much less brutal simplification. That is, one now imposes on the same nonnegative polynomial to be an SOS polynomial whose degree k is fixed in advance and parametrizes the whole hierarchy. Each convex relaxation is now a semidefinite program but whose LMI constraint has fixed size O(n k ). Hence, the resulting families of parametrized relaxations achieve a compromise between the hierarchy of semidefinite relaxations (1.3) limited to problems of modest size and the LP-relaxations (1.4) that theoretically can handle problems of larger size but with a poor behavior when applied to convex problems.

. 6 )

 6 Therefore ρ d ≤ f * for all d. And we prove that:(a) ρ d ≥ θ d for all d, and so ρ d → f * as one let d increase.

Theorem 4 . 1

 41 With P as in (1.1)-(1.2) let f, -g j be convex, j = 1, . . . , m, let Slater's condition hold and let f * > -∞. Then:(a) If max[deg f, deg g j ] ≤ 2 then q 1 1 = f * , i.e., the first relaxation of the hierarchy (3.2) parametrized by k = 1, is exact.

Corollary 4 . 1

 41 Let P be as in (1.1)-(1.2) and let Assumption 1 hold. Let x * ∈ K be a global minimizer and let I 1 (x * ) := {j ∈ {1, . . . , m} : g j (x * ) = 0} and I 2 (x * ) := {j ∈ {1, . . . , m} : (1g j (x * )) = 0} be the set of active constraints at x * . Let 0 ≤ k ∈ N be fixed. The level-d semidefinite relaxation (3.2) is exact only if f * (resp. x * ∈ K) is also the global optimum (resp. a global minimizer) for the problem min x {f (x) : x ∈ V}, (4.1)

  ω d := max σ j {H(σ 1 , . . . , σ m ) : deg(σ j g j ) ≤ 2d, σ j ∈ Σ[x] j = 1, . . . , m},(4.4)d ∈ N, where σ → H(σ 1 , . . . , σ m ) is the functionH(σ 1 , . . . , σ m ) := min x {f (x) -m j=1σ j (x) g j (x) }.

σ

  j g j : σ j ∈ Σ[x], j = 0, 1, . . . , m} (where g 0 = 1) is Archimedean, then ω d → f * as d → ∞. But of course, and like for the usual Lagrangian, minimizing the extended Lagrangianx → L(x, σ) := f (x) -m j=1 σ j (x) g j (x),is in general an NP-hard problem. In fact, writing (4.4) asω d = max t,σ {t : f (x) -m j=1 σ j (x) g j (x)t ≥ 0 ∀x ; deg(σ j g j ) ≤ 2d},the semidefinite relaxations (1.

An SOS-convex polynomial is a convex polynomial whose Hessian factors as L(x)L(x) T for some rectangular matrix polynomial L. For instance, separable convex polynomials are SOS-convex.

A SOS-convex polynomial is such that its Hessian matrix is SOS, i.e., factors as L(x)L(x) T for some rectangular matrix polynomial L.

Slater's condition holds for P if there exists x0 ∈ K such that gj(x0) > 0 for every j = 1, . . . , m.