Christophe Finot
email: christophe.finot@u-bourgogne.fr

Frequency-swept high-repetition rate optical source

Keywords: Electro-optic modulators, optical pulses, microwave photonics, phase modulation, pulse width modulation

We propose and numerically validate an all-optical scheme to generate optical pulse trains with varying temporal pulse-to-pulse delay and pulse duration.

Applying a temporal sinusoidal phase modulation followed by a shaping of the spectral phase enables us to maintain high-quality Gaussian temporal profiles.

Introduction

The modulation of the temporal optical phase by a sinusoidal waveform is a simple but very efficient method to all-optically process the properties of a signal at very high-repetition rates. Various examples have indeed been demonstrated in the context of fiber ultrafast optics such as optical time lens [START_REF] Torres-Company | Chapter 1 -Space-Time Analogies in Optics[END_REF], mitigation of self-phase modulation [START_REF] Audo | Nonlinear spectrum broadening cancellation by sinusoidal phase modulation[END_REF], improvement of nonlinear spectral compression process [START_REF] Boscolo | Enhanced nonlinear spectral compression in fibre by external sinusoidal phase modulation[END_REF], enhancement of the extinction ratio [START_REF] Audo | Extinction ratio enhancement by sinusoidal phase modulation and nonlinear spectral focusing[END_REF], to cite a few … Another field of application that has stimulated strong interest is the photonic generation of optical pulse trains at repetition rates of several tens of GHz. Indeed, applying a sinusoidal temporal phase modulation on a continuous wave followed by a spectral phase shaping has been found to be a promising approach that can overcome the bandwidth limitations of the usual optoelectronics modulation schemes. Initial developments were based on a quadratic spectral phase to convert the temporal phase modulation into a modulation of the intensity profile [START_REF] Kobayashi | Optical pulse compression using high-frequency electrooptic phase modulation[END_REF][START_REF] Komukai | Optical pulse generator using phase modulator and linearly chirped fiber Bragg gratings[END_REF]. However, this scheme suffers from a detrimental residual background that impairs the picosecond pulse train quality [START_REF] Torres-Company | Unified approach to describe optical pulse generation by propagation of periodically phasemodulated CW laser light[END_REF]. The method has been recently improved by imprinting a triangular spectral phase profile or equivalently, a series of equally spaced /2 phase shifts. High-quality pulse trains made of Fourier transform-limited Gaussian pulses have been experimentally demonstrated [START_REF] Andral | Triangular spectral phase tailoring for the generation of high-quality picosecond pulse trains[END_REF]. This architecture can compete with alternate cavity-free approaches based on Kerr nonlinear elements [START_REF] Inoue | Pulse compression techniques using highly nonlinear fibers[END_REF][START_REF] Pitois | Generation of 20-Ghz picosecond pulse trains in the normal and anomalous dispersion regimes of optical fibers[END_REF] and has the advantage to sustain multi-wavelength operation [START_REF] Andral | Multiwavelength high-repetition rate source[END_REF]. It has also been shown that starting from a two-tone sinusoidal modulation enables the generation of a pulse train with controllable levels of fluctuations of the peak power and temporal duration [START_REF] Andral | High-repetition-rate source delivering optical pulse trains with a controllable level of amplitude and temporal jitters[END_REF].

In this contribution, we further extend this approach by investigating the possibility of delivering pulse trains with a continuously varying pulse-to-pulse delay. By sweeping the frequency of the sinusoidal modulation, we numerically show that we can tune the properties of the pulses while maintaining an excellent pulse quality, both in terms of duty cycle, extinction ratio and waveform. The scheme that is chosen to process the spectral phase is crucial and very different behaviors can be observed.

We first introduce the principle of our approach and the different configurations we have studied and compared. Results of numerical simulations are then discussed.

Principle of operation

Our method is based on the principle detailed in [START_REF] Andral | Triangular spectral phase tailoring for the generation of high-quality picosecond pulse trains[END_REF]. A continuous optical wave with an amplitude 0 and a carrier frequency fc is temporally phase modulated by a sinusoidal waveform Am cos(2 fm(t) t) with Am being the amplitude of the phase modulation (chosen as Am = 1.1 rad following the guidelines of [START_REF] Andral | Triangular spectral phase tailoring for the generation of high-quality picosecond pulse trains[END_REF]) and fm(t) its non-constant frequency. In the present work, we consider a linear temporal sweep of the frequency of the RF signal driving the modulator between fm1 and fm2 so that fm(t) = fm1 + (fm2 -fm1) t / Ts, 2 Ts being the time of the frequency sweep. In order to illustrate our discussion with numerical simulations based on realistic parameters, we have chosen the boundaries fm1 and fm2 being 30 and 35 GHz respectively. Ts is fixed by the RF generator and does not impact the results under discussion. The optical spectrum obtained after the temporal phase modulation is plotted in Fig. 1(a) and is symmetric.

Compared to the frequency-constant case modulation where the spectrum is made of equally-spaced spectral lines with an amplitude provided by Bessel functions of the first kind [START_REF] Finot | Impact of a temporal sinusoidal phase modulation on the optical spectrum[END_REF][START_REF] Hammani | Applications of sinusoidal phase modulation in temporal optics to highlight some properties of the Fourier transform[END_REF], the energy of the spectral components is here spread on spectral bands of constant amplitude. A first band appears between 30 and 40 GHz with a span given by twice the chirp range. It is followed by a second band between 60 and 80 GHz. The third spectral band merges with the fourth one. Using an optical bandpass filter with sharp edges and with a full spectral width of 170 GHz (mixed grey line in Fig. 1(a)), we isolate the central component and the two first pairs of sidebands. The processing of the spectral phase is here achieved by a few /2 phase shifts that replace the continuous triangular phase profile initially used in [START_REF] Andral | Triangular spectral phase tailoring for the generation of high-quality picosecond pulse trains[END_REF][START_REF] Andral | Multiwavelength high-repetition rate source[END_REF]. Only four phase-shifts are inserted (at 25 and 55 GHz, Fig. 1(b), solid black line). Experimentally, it can be achieved using programmable liquid-crystal modulators [START_REF] Andral | Triangular spectral phase tailoring for the generation of high-quality picosecond pulse trains[END_REF][START_REF] Andral | Multiwavelength high-repetition rate source[END_REF][START_REF] Jiang | Optical processing based on spectral line-by-line pulse shaping on a phase-modulated CW laser[END_REF] or fiber Bragg gratings [START_REF] Berger | Reshaping periodic light pulses using cascaded uniform fiber Bragg gratings[END_REF]. We will compare the temporal properties of the pulse train with the results achieved when a quadratic spectral phase typical of a dispersive element is inserted. Different levels of cumulated dispersion D are tested: 24, 32 and 44 ps 2 (solid, dotted and dashed grey lines in Fig. 1(b)), corresponding to the optimum level of quadratic phase that has to be imprinted to observe the best compression for modulation at a constant frequency of 40, 35 and 30 GHz respectively. Finally, we have also tested the results obtained in the presence of some possible bandwidth limitations of the optoelectronic devices. For the sake of simplicity and for the qualitative discussion, we have considered here that the various limitations that affect Am can be taken into account as a first-order lowpass filter, with a cutoff frequency of 40 GHz.

Results and discussion

Examples of the intensity profiles obtained after processing under different conditions are summarized for different instants of the frequency scan in Fig. 2.

We can first note that the various schemes lead to intensity profiles with very different levels of background. The insertion of /2 phase shits leads to waveforms of high quality, with a close-to-Gaussian profile, a duty cycle (here defined as the ratio of the full-width at half maximum duration and the pulse-topulse delay) and a peak power that remain constant when the optoelectronic bandwidth limitations are ignored. Note that processing a restricted limited number of spectral sidebands does not impair the temporal profile compared to the ideal case where the full spectrum is processed [START_REF] Andral | Triangular spectral phase tailoring for the generation of high-quality picosecond pulse trains[END_REF]. This strongly contrasts with the quadratic spectral phase that only partly compensates for the initial sinusoidal phase and that consequently induces much higher and detrimental background. Moreover, the pulse shape may vary according to the pulse-topulse delay. Whereas a cumulated dispersion of 44 ps 2 induces an optimal compression for the highest pulse-to-pulse delay (obtained at t = -TS), it is a value of D = 24 ps 2 that leads to the best profile for the shortest pulse-to-pulse delay (achieved at t = TS). A more quantitative study of the impact of the frequency linear chirp of the modulation on the main pulse properties is reported in Fig. 3 and4. As can be seen in Fig. 3, in the ideal case (/2 phase shifts, no optoelectronic bandwidth limitation, solid black line), the temporal duration may vary between -13% and +16% with respect to its average value, i.e. between 6.2 and 8.2 ps with remarkably no change of the peak power. Additional simulations (in the ideal conditions, results not shown here) have stressed that we can achieve for higher frequency span, modulation of the duration between -16% and +23% with respect to the average value. When limits of the modulation are taken into account (mixed black line), slight variations of the peak power ( 5%) become visible and the range of variations of the fwhm duration is compressed. The results are significantly changed when a quadratic spectral phase modulation is involved. In that case, we can first note that the variations of the peak power are more pronounced and can reach as much as  20 % in the case of D = 44 ps 2 . The level of cumulated dispersion will also influence the range of variation of the fwhm duration that can be tuned from less than 10 % of the average value to more than 25 %. The link between the peak power and duration can remain monotonic (such as in the case of D = 24 or 44 ps 2 ) or become more complex as in the case of D = 32 ps 2 .

Finally, we report in Fig. 4 the influence of the pulse-to-pulse delay on three parameters of the waveform. We can first note that the kurtosis excess that assesses the pulse shape [START_REF] Decarlo | On the meaning and use of kurtosis[END_REF] remains close to zero for the processing by /2 phase shifts. That confirms that the waveform remains close to a Gaussian pulse, even in the presence of optoelectronics bandwidth limitations. On the contrary, when quadratic phase modulation is involved, the shape may significantly change as stressed by the large excursion of the kurtosis excess.

Regarding the extinction ratio (defined here as the ratio of the peak power by the power at T/2 ), we note once again the poor performance achieved in the case of a quadratic spectral phase. With an extinction ratio always above 27 dB, the other scheme is by far much more promising. Finally, the duty cycle is found to be nearly constant to 0.25 in many configurations. However, when a quadratic spectral phase with a cumulated dispersion of 44 ps 2 , is applied, we can observe that the duty-cycle can be nearly doubled.

Conclusions

In order to conclude, we have extended the approach initially proposed in [START_REF] Andral | Triangular spectral phase tailoring for the generation of high-quality picosecond pulse trains[END_REF] and we have demonstrated that this scheme was also suitable with sweeping of the modulation frequency. Compared to the solutions based on an additional quadratic spectral phase, the insertion of a few discrete /2 phase shifts enables a clear improvement of both the stability and the overall performances.

Numerical simulations have revealed that the same Gaussian temporal shape can be maintained. However, in the presence of optoelectronic bandwidth limitations, some additional fluctuations of the peak power may appear.

The proposed architecture may find application in test and measurements where pulse trains with different pulse-to-pulse can be interesting and where testing different pulse durations can be wanted. With the progress of phase modulators [START_REF] Wang | Integrated lithium niobate electro-optic modulators operating at CMOS-compatible voltages[END_REF], operation at extremely high frequencies up to 100 GHz can be foreseen, the optical spectral processing being not a limitation of the scheme.

As the scheme is purely linear and does not require high-power, high signal to noise ratio can be expected.

Figure captions:

Fig. 1

 1 Fig. 1 Optical spectrum. (a) Intensity profile of the phase modulated signal (black) and optical filter under use (grey dashed line). (b) Spectral phase profile applied to convert the phase modulation into temporal intensity modulation. Quadratic phase profiles corresponding to a cumulated dispersion D of 24, 32 and 44 ps 2 are plotted with solid, dotted and dashed grey lines respectively whereas the spectral phase profile made of phase shifts of /2 is shown with solid black line.

Fig. 2

 2 Fig. 2 Examples of the temporal intensity profiles obtained for different pulseto-pulse delays T of -Ts, 0 and Ts ps are plotted in panels a, b and c respectively. The results obtained for a quadratic spectral phase profile (cumulated dispersion D of 24, 32 and 44 ps 2 are plotted with solid, dotted and dashed grey lines, respectively) are compared with the results achieved using spectral phase shifts of /2 without or with bandwidth limitation of the optical modulator included (solid and dashed black lines).

Fig. 3

 3 Fig. 3 Evolution of the peak power of the pulse as a function of the temporal fwhm duration of the pulses. The results obtained for a quadratic spectral phase profile (cumulated dispersion D of 24, 32 and 44 ps 2 are plotted with solid, dotted and dashed grey lines, respectively) are compared with the results achieved using spectral phase shifts of /2 without or with bandwidth limitation of the optical modulator included (solid and dashed black lines).

Fig. 4

 4 Fig. 4 Evolution of the excess kurtosis, extinction ratio and duty cycle (panels a, b and c, respectively) according to the pulse-to-pulse delay T. The results obtained for a quadratic spectral phase profile (cumulated dispersion D of 24, 32 and 44 ps 2 are plotted with solid, dotted and dashed grey lines, respectively) are compared with the results achieved using spectral phase shifts of /2

Figure 1 Figure 2 Figure 3

 123 Figure 1

Figure 4

 4 Figure 4

Acknowledgements:

We acknowledge the support of the Institut Universitaire de France (IUF). We thank Ugo Andral, Julien Fatome, Alexandre Parriaux and Bertrand Kibler for fruitful discussions.


Joël Colloc
email: joel.colloc@univ-lehavre.fr

Perspectives and Ethics of the Autonomous Artificial Thinking Systems

Keywords: artificial thinking, holism, Ethics, autonomous systems, artificial consciousness Behavior and actions

The feasibility of autonomous artificial thinking systems needs to compare the way the human beings acquire their information and develops the thought with the current capacities of the autonomous information systems. Our model uses four hierarchies: the hierarchy of information systems, the cognitive hierarchy, the linguistic hierarchy and the digital informative hierarchy that combines artificial intelligence, the power of computers models, methods and tools to develop autonomous information systems. The question of the capability of autonomous system to provide a form of artificial thought arises with the ethical consequences on the social life and the perspective of transhumanism.

Introduction

The recent progress of the cognitive sciences, neurosciences, computing and robotics boosts the project of autonomous artificial being capable of thinking. The feasibility of autonomous artificial thinking systems needs to compare the way the human beings acquire their information and develops the thought with the current capacities of the autonomous information systems. Our model is based on four hierarchies: the hierarchy of information systems, stemming from the systemic theory, supplies indicators of complexity and autonomy; the cognitive hierarchy describes the sub-symbolic acquisition and the emergence of our personal experience, our knowledge, whereas the linguistic hierarchy builds the speech describing the knowledge acquired in terms of concrete and abstract objects on the environment and on oneself. The digital informative hierarchy relies on the necessary concepts, models, methods and tools to build autonomous information systems. At last, we discuss the nature of artificial thinking.

Caption:

Level 6: Operating, Information Decision system Level 7: The system coordonates its actions of different agents Level 8: The system imagines and elaborates new means of decision Level 9: The system finalizes Acronyms: SCS: Selection and Coordination System DS: Decision System FS: Finalization System IS: Information System SID: System of Imagination and Design OS: Operating System Figure 1: The levels 6 to 9 of the model of complex system (J-L. Le [START_REF] Moigne | La modélisation des systèmes complexes[END_REF])

OS! DS! IS!

The hierarchy of information systems

Jean-Louis Le Moigne describes the evolution of information systems. Like epigenesis, the following level adds features to the previous one. By conciseness, the levels 6 to 9 are presented figure 1. On level 6, the system becomes is able to memorize his decision O.I.D (Operating system (O), Information system (I), System of Decision (D)). On level 7, the system coordinates numerous decisions of actions at all the time t, concerning its internal activity and regulation and the external information from and to the environment. On level 8, the system is endowed with a sub-system of imagination and design (SIC). On level 9, the system is able to decide on its decision and to determine the positive and negative aspects of its actions. This finalization of a complex system is closed to the human thought (SF) which confers him an autonomy of decision allowing him to set his own goals. They correspond to the autonomous multi-agents systems.

Integration of the sensory ways and motricity: emergence of objects

The neurophysiology of the sensory ways is described with details in [START_REF] Arbib | Vision, brain and coopérative computation[END_REF]Hanson 1988),(Gazzaniga et al., 2001) and [START_REF] Purves | [END_REF].For all the sensory ways (vision, hearing, smell, taste, touch, ...) we find globally an ascending similar organization: peripheral sensors, transduction in electric signal, the transmission (+/-long) by nerves in the brainstem or by pairs of cranial nerves (V, VII, IX, X), the relay in a specific thalamic area, a projection in a specialized cortical zone and associative areas common to several sensory modalities. In every level, numerous recurring neurons constitute the feedback loops of the cerebral cortex that are essential to do the predictions of the future expected perceptions as coherent with those recently memorized at each level details: from short-lived elements of perception called "percepts" up to durably memorized objects (figure 2 and3). The motricity works similarly by downward ways is strongly entangled with the sensory ways and also have feedback loops. The cerebral cortex functioning is rather uniform on its whole surface [START_REF] Mountcastle | The Mindful brain: Cortical Organization and the group-s élective theory of higher brain, chapter An Organizing Principle for Cérébral Function: The Unit Model and the Distributed System[END_REF]. Seeing an apple actives the smell of the fruit, its shape, consistency (in connection with the motricity) and the word « apple » to speak about it. Smelling (blindly) the odor of apple activates a stereotypical image of apple which we would expect to see. All these predictions is possible because we memorized a global unified perception of the object apple bound with the other various sensory, linguistic modalities which correspond to it [START_REF] Hawkins | Intelligence[END_REF], [START_REF] Minsky | La, société de l'esprit éd. InterEditions. InterEditions[END_REF].

Emergence%of%objects%

Percepts"and"Feelings"

Shapes"and""Pieces"

Pa3erns"

Concrete"Objects" Charactéris:cs" Symbols"

Names" "Verbs"

Abstract"objects" SubA symbolic" Percep:on" Level"

Symbolic" Level"

Cogni:ve"pyramid"" "Sensory"Cortex"and"Thalamus"" "Emo:on:"hypothalamus"

Sentences" " Life" Experiences" "

Ontologies"" Knowledge" Linguis:c"pyramid" Cor:cal"areas"of"the"language," Thalamus" Informa:on" Flow"

Texts"

Informa:ons" R" Signs" R" R" R" R" R" L" R" L" L" L" Oc" ∈" Speech/WriPng" Listening/Reading" OL" Se" Sy" ∈" SIGNIFIED% SIGNIFIER%(Saussure)%
The figure 2 shows the various cortical layers V1, V2, V4 that integrate the sensory modalities and associative zones in the inféro-temporal cortex (IT) and that are activated when an apple is recognized in any manner. This activation is then transmitted in a downward way in the other sensory or linguistic areas which are going to predict patterns corresponding to levels of details more and more fine to confirm or counter that they are corresponding in each of the other senses.

We can so know if we are feeling a real apple or only a partial representation as in the famous Magritte's painting entitled « Ceci n'est pas une pomme » (this is not an apple). To this anatomophysiological organization corresponds a hierarchy of the sensory information passed on and integrated into the cortical level figure 3. The hippocampus is the zone situated at the top of the mnesic pyramid. This cerebral structure is at the origin of the matching and the interconnection of the various sensory modalities and the memorization of the characteristics of the new unknown objects [START_REF] Hawkins | Intelligence[END_REF]. The figure 3 describes an abstract model of the human information system [START_REF] Colloc | L'éthique des systèmes d'information autonomes vers une pensée artificielle in Enjeux du big data et identifications des données médicales, Les Cahiers du Numérique[END_REF]. In his left part we find the sensory and cognitive pyramid leading to the emergence of concrete objects and to the memorization of knowledge and experiences on the objects of the world. At every level recognition operators (R) confirm or counter the coherence in the flow of the perceptions. Percepts is primary elements perceived by the organs of the senses. For the vision, it is points, of directed segments (vertical, oblique, horizontal ...) which establish in the field of vision of the forms elementary as those described in the theory of "geons" proposed by Hummel and Biederman in 1987 [START_REF] Biederman | Recognition by components: a theory of human image understanding[END_REF], [START_REF] Boucart | La reconnaissance des objets[END_REF] and the hypothalamic emotional aspects concerning them [START_REF] Damasio | L'erreur de Descartes la raison des émotions[END_REF]. The neurohormones, secreted mainly by the hypothalamus and the amygdalae, influence the interpretation of the sensory information. The hypothalamus regulates the set of the balances of the body (hunger and thirst/satisfaction, pleasure/pain, ...) [START_REF] Vincent | La Chair et le diable Odile Jacob[END_REF], [START_REF] Vincent | La Chair et le diable Odile Jacob[END_REF]. The amygdalae intervene in the circuits of the reward and the motivation. For Alain Prochiantz, there is no organ of the thought, " there n is no thought without body, nor of body without thought" [START_REF] Prochiantz | Machine-Esprit[END_REF], he so joins Francisco Varela [START_REF] Varela | L'inscription corporelle de l'esprit[END_REF]. The cognitive operators ⊕ composition and (R) Recognition establish signs which base the experience of patterns and behavior of the concrete objects at successive levels of compositions (part left of the figure 3).

The operator of synthesis ⊗ Predicted the characteristics or the behavior of the similar objects and exploit the following operators: the operator of generalization (G) groups together similar objects in a category. The operator of deduction (Dd) predicts the characteristics and the behavior of objects to be looked for from the shapes and already observed patterns. The induction operator (In) search for predictable properties in unknown objects because of their resemblance with already known objects. The operator of abduction (Ab) detects missing or abnormal properties in usually known objects. The operator of subsumption (Sb) connects an object type more specialized in a more general already known object type. The analogy operator detects similarity between the structures, the characteristics or the behavior of known and memorized objects.

The linguistic hierarchy: The concrete objects do not need to be put into words to be recognized, the language appears later with the maturation of the nervous system. Jean Piaget underlines that the language is gradually set up from the 12th to the 18th months of the life of the child [START_REF] Piaget | Biologie et Connaissance -Essai sur les relations entre les régulations organiques et les processus cognitifs Delachaux et Niestlé[END_REF]. The sign language being older than the spoken language, it is earlier set up in the encephalon and precedes the language in the verbal flow (Jacquet-Andrieu and [START_REF] Jacquet-Andrieu | On how to Define Anticipation in the Verbal Flow[END_REF]. The perception, the emergence, the recognition of the concrete objects and the thought are previous to the implementation of the language, they are thus considered as subsymbolic, they result from the memorization of the experiences of perception. The Haeckel's theory :"The ontogeny recapitulates the philogenesis" finds a new lighting by the discovery of the genes of the development (Hox) [START_REF] Prochiantz | Machine-Esprit[END_REF]. In particular, the development of the sensory ways takes place during the embryogenesis and continues after the birth in the presence of the stimulations of the environment. The absence of visual stimulation of kittens in the birth prevents the maturation of the vision and causes a partial or total agenesis of the visual ways [START_REF] Shatz | La maturation du cerveau[END_REF]. Also, the other intellectual functions would be organized according to an intellectual protomap (similar to that proposed by Brodman) which determines the migration of neurons and the maturation of the sensory and motor ways. The linguistic pyramid (part right of figure 3) establishes the symbols, characteristics, the names of objects abstracted from the concrete objects or the other pre-existent abstract objects. It determines semantics, the syntax of the sentences allowing to establish input flows (reading / listening) and output (speaking / writing) of texts and flows of information (verbal and nonverbal). The linguistic operators (Ol) are: the lexical operator (L) in charge of naming and associating a word with the concrete and abstract objects and with their characteristics or behavior. The operator of membership (∈) (has a) establishes that a characteristic or a behavior belongs to a concrete or abstract object. The semantic operator defines himself the meaning of a word (name, verb, adverb) that is with which concrete or abstract object is the meant according to (de Saussure, 1916). The syntactic operator (Sy) determines in a given language the possible syntaxes of the sentences. The objects of the world are meaningful by their name, the actions by verbs and their characteristics by adjectives, the quite ordered by the syntax rules of a grammar and operators like generalization (is-a), causality (caused by), composition (is-part-of), temporality (succeeds, precedes)... They allow to create new abstract objects memorized in their turn and then combined with others in an incremental way. Our model is always incomplete and reducing but it shows the interactions between the perception, the cognition, the language and the feelings. It tries to reconcile the structuralist approach of the linguistics initialized by Ferdinand de Saussure with the current neurophysiological and neuro-psychological approaches (de Saussure, 1916).

The digital information hierarchy

Information relies on the triptych: data, information and knowledge [START_REF] Abiteboul | Sciences des données : de la logique du premier ordre à la toile[END_REF]. Many knowledge bases were developed like MYCIN (Buchanan and Shortliffe, 1984) and SIAMED (Colloc, 1985). Logic is used to classify objects as initially shown by [START_REF] Carroll | Symbolic Logic, Part I Elementary[END_REF] and languages like LISP (McCarthy,1960) or PROLOG [START_REF] Colmerauer | The birth of Prolog[END_REF]. Semantic models (object oriented and agents) allows to build knowledge and ontologies more efficiently (Shen et Object"" Internal"or"private"part" External"or"public""Interface" Data% EnGGes% % Processing%:% Func:ons" Procedures" Queries" Logical"operators" ∈" ∈" CogniGve%/%ReacGve%%Agents%% /%Actors% MulGOAgent%Systems%MAS% Autonomous% %MulGOagent%Systems%% AMAS%

InformaGon%Systems%IS"" Databases%DB" SemanGc%Systems%:" A"Object"Oriented"Model" A"En:tyARela:onship"Model"

Knowledge%Based%

Systems%KBS" Distributed%ArGficial% Intelligence%DAI% Finalized% Autonomous%Systems% Lev"5" Lev"6" Lev"7" Lev"7A8" Lev"9" Le"Moigne's" Levels" al.,2015). The semantic Web allow to access a considerable quantity of knowledge and data on the world and the people (level 6-7). Multi-agent systems (MAS) are used to build simulations: A community of numerous agents ants solve problems of search for paths in complex graphs thanks to their stigmergic behavior (level 7). MAS allows to to coordinate mutiple ontologies and knowledge agents to support clinical decision in medicine [START_REF] Shen | Emerging Medical Informatics with Case-Based Reasoning for Aiding Clinical Decision in Multi-Agent System[END_REF]. Alain Cardon proposes a psychic system that relies on knowledge in psychology and capable of generating flows of thoughts that take place in the temporality under the shape of organized groups of processes to build the artificial psychic system and its interactions [START_REF] Cardon | Un modèle constructible de Système Psychique[END_REF]. This conscious autonomous multi-agent system (CAMAS) is able to choose its objectives and set its goals to achieve them (level 9).

Conclusion Can computers think ?

Computers could think in a very different way than human, as a plane flights differently but faster than a bird [START_REF] Pitrat | Métaconnaissance Futur de l'intelligence artificielle[END_REF]. The Zen is a total holism, the world cannot be absolutely divided into parts. The dilemma is that for every object of the world, according to master Zen Mummon: "we cannot express him with words and we cannot express him without the words". According to the Buddhism : to trust the words to reach the truth is equivalent of trusting an always incomplete formal system [START_REF] Hofstadter | Gödel Escher Bach, Les Brins d'une Guirlande Eternelle[END_REF]. For Jiddu Khrishnamurti, our consciousness is common to all the humanity: All the human beings think that contribute to build it. He considers the individualism, the ego as an obstacle to understand the consciousness with rare moments of clarity ("insight"). "The thought is a movement in the time and the space. The thought is memory, memory of the past things. The thought is the activity of the knowledge, the knowledge which was gathered through millions of years and stored in the form of memory in the brain." (Krishnamurty, 2005). There are two forms of thinking: -The first is a reaction of the memory which contains the knowledge, the result of the experience from the beginning of humanity (phylogenesis) and since our birth (epigenesis) in a loop: experience, knowledge, memory, thought, action, experience... necessarily limited by the time, it is used every day, rational, individualistic, power-hungry and of progress submissive to the knowledge which accumulates, in the words which divide and this division is responsible for all the suffering, for all the troubles of the world. -The alternative thinking: the action-perception where in rare occasions, we pay simply our attention to the world, without interpreting it, without naming anything, virgin of any prejudice, knowledge and especially spontaneously, by living this moment without thinking of it and without the will. For example: the direct perception of a wonderful landscape of mountain one morning with all our senses uses our complete attention where we forget ourselves and banish the use of the words (Krishnamurty, 2005). Such a full perception requests only the left lower part: the sub-symbolic cognitive pyramid (figure 3) and not the linguistic pyramid. The first way of thinking is a fatal vicious circle implemented soon in computers that will think better than human beings! And there nothing prevents that a computer invents a new religion at the origin of new sufferings for the humanity. The language during the evolution would have made lose to the man his spontaneity in the immediate perception of the world such as it is. The digital technology, which strengthens the symbolic nature of our relation to the world, is doubtless going to establish the peak of our ignorance. The realization of CAMAS able to think is now possible. These systems have access to Internet and will quickly become more powerful than the human beings with disturbing consequences for the future of the humanity. In conclusion, we have shown that computers can think in the first way only. The main characteristic of humanity is to still be able to think also in the alternative way but how long before losing our essential faculty ?

Figure 2 :

 2 Figure2: Sensory emergence of known objects[START_REF] Hawkins | Intelligence[END_REF]

Caption 5 .

 5 Objects encapsulate (∈) data or attributes, and procedures to make necessary arithmetics or logic calculations and deductions from the data values. 6. Semantic systems implements entities and then objects 7-8. Distributed Knowledge bases implement cognitive agents and ontologies cooperation. 9. Conscious autonomous multi-agent systems (CAMAS) has an internal memory to store facts of consciousness. It is able to choose its objectives and then schedule its goals and actions.

Figure 4 :

 4 Figure 4 : Digital information hierarchy[START_REF] Colloc | L'éthique des systèmes d'information autonomes vers une pensée artificielle in Enjeux du big data et identifications des données médicales, Les Cahiers du Numérique[END_REF]


Simone Naldi
email: simone.naldi@tu-dortmund.de

Daniel Plaumann
email: daniel.plaumann@tu-dortmund.de

SYMBOLIC COMPUTATION IN HYPERBOLIC PROGRAMMING

Hyperbolic programming is the problem of computing the infimum of a linear function when restricted to the hyperbolicity cone of a hyperbolic polynomial, a generalization of semidefinite programming. We propose an approach based on symbolic computation, relying on the multiplicity structure of the algebraic boundary of the cone, without the assumption of determinantal representability. This allows us to design exact algorithms able to certify the multiplicity of the solution and the optimal value of the linear function.

Introduction

Semidefinite programming (SDP) constitutes a popular class of convex optimization problems for which approximate solutions can be computed through a variety of numerical algorithms, the most efficient of which are based on primal-dual interior point methods. On the other hand, exact algorithms for general semidefinite programs have been developed only much more recently in the work of Henrion, Safey El Din and the first author in [START_REF] Henrion | Exact algorithms for linear matrix inequalities[END_REF]. The optimizer in an SDP problem corresponds to a positive semidefinite real symmetric matrix. While symbolic algorithms obviously have a much higher complexity than numerical ones, finding exact solutions has many benefits, especially regarding certification of the solution. For instance, the rank of the optimizer, which is often a meaningful quantity, can be determined exactly by the algorithm in [START_REF] Henrion | Exact algorithms for linear matrix inequalities[END_REF], and one can even optimize over all feasible points of bounded rank, which is a non-convex optimization problem [START_REF] Naldi | Solving rank-constrained semidefinite programs in exact arithmetic[END_REF].

In this paper, we consider analogous algorithmic questions in the more general framework of hyperbolic programming. We briefly summarize the underlying notions. A real homogeneous polynomial f in several variables x = (x 1 , . . . , x n ) is called hyperbolic with respect to a point e ∈ R n if f (e) = 0 and the polynomial f (te -a) ∈ R[t] has only real zeros for every a ∈ R n . The general determinant of symmetric matrices has this property with respect to the unit matrix e = I d , since det(tI d -A) is the classical characteristic polynomial of the real symmetric matrix A. Hyperbolic polynomials can therefore be seen as generalized characteristic polynomials. If f is hyperbolic with respect to e, the hypersurface defined by f bounds a convex cone containing e, the hyperbolicity cone, generalizing the cone of positive semidefinite matrices in case of the determinant. The zeros of f (te -a) can be regarded as generalized eigenvalues of a ∈ R n , and the multiplicity of the root t = 0 of f (te -a) as the corank of a.

Date: February 6, 2018. 2010 Mathematics Subject Classification. 14Q20, 68W30, 90C22, 90C25.

A hyperbolic program is the convex optimization problem of minimizing a linear function over the hyperbolicity cone of a hyperbolic polynomial. Such cones have nonempty interior by construction (the interior will indeed contain the point e). Denote now by S d (R) the set of d × d real symmetric matrices. Regular semidefinite programs (in which the feasible set has non-empty interior) correspond to the case in which f is the restriction of the determinant map det : S d (R) → R to a linear subspace V ⊂ S d (R) containing a positive definite matrix. More precisely, for such V , the polynomial f = det V is hyperbolic, and its hyperbolicity cone is the spectrahedron

V ∩ S + d (R) = {M ∈ V : M
0}. If V does not contain positive definite matrices,

V ∩ S + d (R
) is still a spectrahedron, but f = det V is not hyperbolic. Moreover, not every hyperbolic polynomial can be represented in this way (in fact, the set of representable polynomials is, in general, of strictly smaller dimension) which motivates the development of techniques that are independent of the determinantal representability of f . Hyperbolic programming can be solved numerically with interior point methods much like SDP [START_REF] Klerk | Aspects of Semidefinite Programming[END_REF][START_REF] Güler | Hyperbolic polynomials and interior point methods for convex programming[END_REF][START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF]. One of the major challenges in hyperbolic programming, when Figure 1. An affine section of a hyperbolic quartic surface with four nodes compared to SDP, is the lack of an explicit duality theory, while SDP duality is always heavily exploited. The methods in [START_REF] Henrion | Exact algorithms for linear matrix inequalities[END_REF] rely on the good properties of determinantal varieties, which provide an explicit non-singular lifting of the variety of symmetric matrices of bounded rank in a given subspace. The same is not available for hyperbolic programming. However, hyperbolicity of a real polynomial still imposes some strong conditions on the structure of the real part of the singular locus of the hypersurface.

Let us give an overview of our main results. Given a polynomial f , hyperbolic with respect to e ∈ R n , let Λ + be the hyperbolicity cone of f (Section 1) and let Γ m ⊂ R n denote the set of points of multiplicity at least m (see Section 2). Furthermore, let L e = {x ∈ R n : e T x = 1} be the affine space orthogonal to the direction e (containing e e 2 ) and write Λ + = Λ + ∩L e and Γ m = Γ m ∩L e . We show that if m equals the maximal multiplicity on Λ + , then Λ + contains one of the real connected components of Γ m , proving that Γ m ∩ Λ + is the union of some components of Γ m (Proposition 6). Thus a point of maximal multiplicity (analogous to the minimal rank in SDP) can be found by sampling the connected components of Γ m . Since this is an algebraic set (rather than just semialgebraic), this reduces to a standard problem in computational real algebraic geometry. Furthermore, we show that the more general convex hyperbolic programming problem over Λ + is equivalent to computing local minimizers over the sets Γ m of the same linear function (Theorem 10). This can be carried out in practice using Lagrange multipliers, provided that the corresponding set of critical points has complex dimension 0. We use these results to design an exact algorithm for hyperbolic programming. Applying this to explicit examples yields interesting results that are discussed in the final part.

The structure of this paper is as follows. In Section 1, we summarize standard definitions and results about hyperbolicity cones. In Section 2, we describe the multiplicity structure of the algebraic boundary of Λ + and prove our main result on the maximal multiplicity. This is used to certify feasible multiplicities in the case where Λ + is the d-elliptope. In Section 3, we formalize the relationship between solutions to hyperbolic programming problems and the multiplicity loci Γ m . Our algorithm solving hyperbolic programming in exact arithmetic is implemented in Maple; we finally discuss the results of our tests.

Preliminaries

The following notation is used throughout. The ring of real polynomials in

x = (x 1 , . . . , x n ) is denoted by R[x], with its natural grading R[x] = d R[x] d . The complex algebraic set defined by polynomials f = (f 1 , . . . , f s ) ∈ R[x] s is denoted by Z(f ) = {x ∈ C n : ∀ i f i (x) = 0}, and its subset of real points by Z R (f ) = Z(f ) ∩ R n .
The closure of a set S ⊂ R n in the Euclidean topology (resp. Zariski topology) of R n is S (resp. Zar(S)). Its Euclidean boundary is ∂S.

Recall from the introduction that a homogeneous polynomial f ∈ R[x] of degree d is called hyperbolic with respect to a point e ∈ R n if f (e) = 0 and f (te -a) ∈ R[t] has only real roots for every a ∈ R n . Up to rescaling f , we may suppose that f (e) = 1, and we often say that f is just hyperbolic, without specifying the direction e.

The polynomial t → ch a (t; f, e) = f (te -a)

is called the characteristic polynomial of a ∈ R n (with respect to f and e). This will be denoted simply by ch a (t) when f, e are understood from the context. For a ∈ R n , the ordered roots λ 1 (a) ≤ λ 2 (a) ≤ • • • ≤ λ d (a) of ch a are called the eigenvalues of a. The set

Λ ++ (f, e) = {a ∈ R n : λ 1 (a) > 0}
is called the open hyperbolicity cone of f with respect to e. This is an open, convex cone containing e [START_REF] Gårding | An inequality for hyperbolic polynomials[END_REF]. Note that there may exist several hyperbolicity cones associated to a given hyperbolic polynomial, and bounds on the number of such cones have been recently computed in [START_REF] Jörgens | Hyperbolicity cones and imaginary projections[END_REF]; however, when f is irreducible, there is only one hyperbolicity cone, up to changing e with -e (see [START_REF] Kummer | On the connectivity of the hyperbolicity region of irreducible polynomials[END_REF]). We will simply denote Λ ++ (f, e) by Λ ++ when f, e are fixed. It is independent of the choice of e within Λ ++ , by the following basic result.

Theorem 1 (Gårding [START_REF] Gårding | An inequality for hyperbolic polynomials[END_REF], Renegar [START_REF] Renegar | Hyperbolic programs, and their derivative relaxations[END_REF]).

Λ + = Λ ++ = {x ∈ R n : λ 1 (x) ≥ 0}.
As mentioned in the introduction, we work over the affine section

Λ + = Λ + ∩ L e ,
where L e = {x ∈ R n : e T x = 1}.

Note that the relative interior of Λ + in L e is not empty, since, for instance, it contains e e 2 . We call the affine section Λ + the standard section since it preserves the multiplicity structure of the cone Λ + (see Remark 5).

Since linear (LP) and semidefinite programming (SDP) are special instances of hyperbolic programming, we recall the description of their feasible cones in this setting. For LP, the polynomial splits into real linear factors, that is

f = 1 • • • d , with i ∈ R[x] 1 .
For all e ∈ R n with i (e) > 0, i = 1, . . . , d, one has that

Λ + (f, e) = {x ∈ R n : ∀ i i (x) ≥ 0}
is a polyhedron. For SDP, the hyperbolicity cone of f = det(

x 1 A 1 + • • • + x n A n )
in direction e, with A i real symmetric, and e 1 A 1 + • • • + e n A n 0, equals the cone of positive semidefinite matrices in the subspace spanned by A 1 , . . . , A n , that is, a spectrahedral cone.

Multiplicities

Let a ∈ R n , and f ∈ R[x] a hyperbolic polynomial (with respect to a fixed point e ∈ R n ) of degree d. The multiplicity of a is the multiplicity of t = 0 as an eigenvalue of a, hence as a root of the characteristic polynomial ch a (t) = f (te -a), and is denoted by mult(a). We consider the semialgebraic sets [START_REF] Renegar | Hyperbolic programs, and their derivative relaxations[END_REF]. By [START_REF] Renegar | Hyperbolic programs, and their derivative relaxations[END_REF]Prop.22], the function a → mult(a) is independent of the hyperbolic direction e chosen within Λ + (f, e). The following lemmas give basic results on the multiplicity structure of the boundary of Λ + and on its algebraic closure. These will allow us to define explicit equations for algebraic relaxations of Λ + .

∂ m Λ + = {a ∈ Λ + : mult(a) = m}, ∂ ≥m Λ + = ∂ m Λ + ∪ ∂ m+1 Λ + ∪ • • • ∪ ∂ d Λ + , for 0 ≤ m ≤ d, first considered in
Lemma 2. For 0 ≤ m ≤ d, the set ∂ ≥m Λ + is closed and ∂ m Λ + ⊂ ∂ ≥m Λ + .
Proof. The inclusion ∂ m Λ + ⊂ ∂ ≥m Λ + holds by definition. Hence we have to show that ∂ ≥m Λ + is closed, which comes simply from the continuity of eigenvalues a → λ i (a).

Indeed, if (a ) >0 ⊂ ∂ ≥m Λ + , then for all > 0 λ 1 (a ) = • • • = λ m (a ) = 0 ≤ λ m+1 (a ) ≤ • • • ≤ λ d (a ). Thus if a →0 + ---→ a, then λ 1 (a) = • • • λ m (a) = 0 ≤ λ m+1 (a) ≤ • • • ≤ λ d (a), hence mult(a) ≥ m as claimed.
Note that, typically, neither ∂ m Λ + nor ∂ ≥m Λ + are Zariski closed sets, since they are semialgebraic rather than algebraic. Often, in order to develop algebraic techniques, it is desirable to work with real algebraic sets. We therefore define the following:

Γ m = {a ∈ R n : mult(a) ≥ m} , 0 ≤ m ≤ d. The sets Γ m define a nested collection in R n : Γ d ⊂ Γ d-1 ⊂ • • • ⊂ Γ 1 = {a ∈ R n : f (a) = 0} = Z R (f ) ⊂ Γ 0 = R n .
By Lemma 2, we have

∂ m Λ + ⊂ Γ m ∩ Λ + (indeed, Γ m ∩ Λ + = ∂ ≥m Λ + ).
Lemma 3. For any 0 ≤ m ≤ d, the set Γ m is real algebraic and satisfies

Zar(∂ m Λ + ) = Zar(∂ m Λ + ) ⊂ Γ m .
Proof. The equality Zar(S) = Zar(S) always holds, since the Zariski topology is coarser than the Euclidean topology. The inclusion

Zar(∂ m Λ + ) ⊂ Zar(Γ m ) follows from ∂ m Λ + ⊂ Γ m ∩ Λ + , proved in Lemma 2.
Hence we only need to prove that Γ m is real algebraic. Writing

ch x (t) = t d + g 1 (x)t d-1 + • • • + g d-1 (x)t + g d (x),
we deduce that a point a ∈ R n lies in Γ m if and only if t m divides ch a (t). This is the case if and only if all coefficients

g d = f (-x), g d-1 , . . . , g d-m+1 ∈ R[x] vanish at a.
The defining equations for Γ m obtained in the proof can be made more explicit. Let us consider the modified characteristic polynomial ch -a = f (te + a) at a point a ∈ R n , with respect to f and e. Denote by σ i (y 1 , . . . , y

d ) = j 1 <•••<j i y j 1 • • • y j i the i-th elementary symmetric polynomial on variables y 1 , . . . , y d , then ch -a = t d + σ 1 (λ(a))t d-1 + • • • + σ d-1 (λ(a))t + f (a)
where λ(a) = (λ 1 (a), . . . , λ d (a)) are the eigenvalues of a. Note that f

(x) = σ d (λ(x)) = λ 1 (x) • • • λ d (x), since f (e) = 1. Corollary 4. For 0 ≤ m ≤ d, we have Γ m = Z R (f, σ d-1 (λ), . . . , σ d-m+1 (λ)).
Proof. Indeed, in the proof of Lemma 3 we have shown that Γ m equals the real algebraic set Z R (g d , g d-1 , . . . , g d-m+1 ), with g d := f (-x) and g i (x) is the coefficient of t d-i in ch x (t). Therefore, g i (-x) = σ i (λ(x)) for i = 1, . . . , d and hence

Γ m = Z R (f (-x), σ d-1 λ(-x) , . . . , σ d-m+1 λ(-x) ).
The claim follows from the homogeneity of f, σ d-1 (λ), . . . , σ d-m+1 (λ).

Remark 5. Suppose that a ∈ Λ + with e T a = 0. Then x = a e T a ∈ Λ + and mult(x) = mult(a). We deduce that if Λ + ∩ {x ∈ R n : e T x = 0} = {0}, the standard section of a hyperbolicity cone is a base for Λ + (as a convex cone; see [START_REF] Barvinok | A course in convexity[END_REF]Def. 8.3]) and has the same multiplicity structure as Λ + \ {0}.

We are particularly interested in computing the maximum multiplicity on the standard section of the cone Λ + . For a hyperbolic polynomial f ∈ R[x] d , we define the integer max

a∈Λ + mult(a) = max 0≤t≤d {t : Γ t ∩ Λ + = ∅}.
This is well defined since Λ + = ∅ and 0 ≤ mult(a) ≤ d for all a ∈ R n . We now show the maximum multiplicity m is attained on an entire real connected component of Γ m . Proposition 6. Let f ∈ R[x] d be hyperbolic with respect to e ∈ R n , and let m = max a∈Λ + mult(a). For every (real

) connected component C of Γ m , with C ∩ Λ + = ∅, we have (1) C ⊂ Λ + (2) C ∩ Γ m+1 = ∅.
Proof. First, note that (1) implies ( 2), because, by definition, m is the maximal multiplicity of points in Λ + .

To prove (1), let C be a connected component of Γ m intersecting Λ + , and let a ∈ C ∩ Λ + . Note that mult(a) = m by maximality of m. Suppose that there is b ∈ C \ Λ + ; hence mult(b) ≥ m and λ 1 (b) < 0. Since C is connected, there is a continuous path ϕ : [0, 1] → C with ϕ(0) = a and ϕ(1) = b. For all t ∈ [0, 1], mult(ϕ(t)) ≥ m, and there exists

t 0 ∈ [0, 1] such that (a) ϕ([0, t 0 ]) ⊂ Λ + and (b) ∃ δ > 0 such that, ∀ 0 < < δ, ϕ(t 0 + ) / ∈ Λ + .
Define a 0 = ϕ(t 0 ) and a = ϕ(t 0 + ), for 0 < < δ, so that a →0 + ---→ a 0 . Since a / ∈ Λ + , then λ 1 (a ) < 0 for all 0 < < δ. More precisely, since mult(a ) ≥ m, then for all > 0 there exists i( ) ∈ {1, . . . , d} such that

λ 1 (a ) ≤ • • • ≤ λ i( ) (a ) < 0 λ i( )+1 (a ) = • • • = λ i( )+m (a ) = 0 0 ≤ λ i( )+m+1 (a ) ≤ • • • ≤ λ d (a ).
Passing to the limit for → 0 + , by the continuity of the eigenvalues and since a 0 ∈ Λ + , we find that λ 1 (a 0 ) = • • • = λ m+1 (a 0 ) = 0, that is mult(a 0 ) ≥ m + 1, which contradicts the fact that m is the maximum multiplicity.

Proposition 6 provides us with a way of computing the largest multiplicity on the standard section Λ + of the hyperbolicity cone Λ + , and of representing one point where this maximum value is attained. More precisely, consider the non-convex optimization problem (1)

max mult(x) s.t. x ∈ Λ + (f, e)
By the hyperbolicity of f , the interior of the feasible set Λ + is Λ ++ = ∅ (for instance, e ∈ Λ ++ ), hence this problem is feasible (and with non-empty interior). Hence there always exists a * ∈ Λ + such that mult(a * ) = m := max a∈Λ + mult(a). By Proposition 6, the whole connected component C * of Γ m containing a * , is included in Λ + . First, by Remark 5, under the assumption that Λ + intersects {x ∈ R n : e T x = 0} only in 0, we conclude that a solution of Problem (1) yields the maximum multiplicity over Λ + \ {0}. We also conclude by applying Proposition 6, that Problem (1) can be solved by computing at least one point per connected component of the real algebraic sets Γ m , m = 1, . . . , d-1. This is a central routine in computational algebraic geometry, for which exact algorithms have been designed, see e.g. [START_REF] Basu | On the combinatorial and algebraic complexity of quantifier elimination[END_REF][START_REF] Renegar | On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals[END_REF] or the monograph [START_REF] Basu | A new algorithm to find a point in every cell defined by a family of polynomials[END_REF] with its references. By exact representation, we mean via a rational univariate representation [START_REF] Rouillier | Solving zero-dimensional systems through the Rational Univariate Representation[END_REF]: this is a vector (q, q 0 , q 1 , . . . , q n ) ∈ Q[t] n+2 such that the set [START_REF] Basu | On the combinatorial and algebraic complexity of quantifier elimination[END_REF] q 1 (t) q 0 (t) , . . . , q n (t) q 0 (t) : q(t) = 0 intersects every connected component of the given algebraic set. In (2), q and q 0 are coprime, therefore the set is well defined and finite. Its cardinality is bounded above by deg q.

The best arithmetic complexity bounds for computing representations as in (2) are essentially polynomial in the number of equations defining the algebraic set (which for Γ m is at most m+1, by Corollary 4) and in the maximum of their degree (bounded above by d) and singly exponential in the number of variables. These come out of the so-called critical points method [START_REF] Basu | A new algorithm to find a point in every cell defined by a family of polynomials[END_REF]Ch. 16], or the effective theory of polar varieties [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF][START_REF] El Din | Properness defects of projections and computation of at least one point in each connected component of a real algebraic set[END_REF].

In this paper we are not focusing on complexity results for hyperbolic programming, but our efforts are especially devoted to the design of algebraic methods for this problem. However, Proposition 6 and the mentioned results, according to the previous complexity analysis, give a singly exponential algorithm to represent a solution to Problem 1 in exact arithmetic, which is worth being highlighted.

We conclude this section with an example and comment on computational issues of Problem 1 for the case of the elliptope. This is the feasible set of the SDP-relaxation of the MAX-CUT combinatorial optimization problem [START_REF] Goemans | Improved approximation algorithms for maximum cuts and satisfiability problems using semidefinite programming[END_REF].

Example 7 (Elliptope). Let d ∈ N and n = d 2 , and let E d be the d-elliptope. This is the spectrahedral cone of dimension n + 1 defined by the linear matrix inequality A(x) 0 with

A(x) =       x 0 x 1,2 • • • x 1,d x 1,2 x 0 . . . . . . . . . . . . . . . x d-1,d x 1,d • • • x d-1,d x 0      
.

That is We propose two distinct tests on Example 7. The results that we present have been obtained on a desktop PC, with CPU architecture with the following characteristics: Intel(R) Xeon(R) CPU E5-4620 0 @ 2.20GHz. For the sake of reproducibility, the corresponding Maple scripts are made available on the webpage of the first author1 .

E d = {x = (x 0 , x 1,2 , . . . , x d-1,d ) ∈ R n+1 : A(x) 0}. It
Test 8. Since we work in the affine space L e defined in Example 7, we put x 0 = 1/d. We recall that det A is hyperbolic with respect to e = (1, 0, . . . , 0). The authors of [START_REF] Laurent | On a positive semidefinite relaxation of the cut polytope[END_REF] proved that the vertices of E d (defined as those boundary points whose normal cone is full-dimensional) are characterized as all the rank one matrices in A(x) with entries in ±1. These are exactly the connected components (in this case, isolated real points) of Γ d-1 , that is Γ d-1 ⊂ E d , and each rank one matrix in Γ d-1 maximizes the multiplicity on E d \ {0}: indeed, 0 is the unique positive semidefinite matrix of trace 0, hence the assumption in Remark 5 is satisfied. If M is one of these rank one matrices, then (1/d)M ∈ E d ∩ L e maximizes the multiplicity on E d ∩ L e .

These points can be computed efficiently in practice. We make use of the Maple library spectra [START_REF] Henrion | Spectra: a Maple library for solving linear matrix inequalities in exact arithmetic[END_REF], which is targeted to computing low rank solutions of linear matrix inequalities. As explained in [START_REF] Henrion | Spectra: a Maple library for solving linear matrix inequalities in exact arithmetic[END_REF], the command SolveLMI(A,{all}, [START_REF] Barvinok | A course in convexity[END_REF]) (when called in a Maple worksheet where spectra has been previously loaded, and where the variable A is instantiated to A(x), with x 0 = 1/d) computes all components with highest multiplicity, namely isolated matrices of rank 1.

To give an idea of performances, we are able to solve our problem for d ≤ 5 in less than half second, or for d = 8 (corresponding to an elliptope of dimension 21, and computing 2 7 = 128 solutions) in around 2.5 minutes.

A second test is performed for the elliptope, without exploiting the spectrahedrality of E d , but just relying on the hyperbolicity of det A.

Test 9. We generate the sets Γ m , m = 1, . . . , d, as the zero locus of the polynomials defined in Corollary 4. For every m, we sample the real connected components of Γ m and check how many of the solutions lie in E d , using the Maple library raglib [START_REF] Din | Raglib (Real Algebraic Geometry library[END_REF]. The function PointsPerComponents allows us to sample the real connected components of the sets Γ m , m = 1, . . . , d, computing rational parametrizations as in [START_REF] Basu | On the combinatorial and algebraic complexity of quantifier elimination[END_REF]. The goal is to sample many points on the boundary of E d , possibly with different multiplicities. Note that, a priori, Proposition 6 guarantees that this method yields at least one feasible point for the maximum multiplicity in

E d ∩ L e .
The results are summarized in Table 1. For a fixed d and for a given multiplicity We also note that one computes points with multiplicity which can be larger than the expected one (that is, matrices whose rank is smaller than expected). For example, for d = 3 and m = 1, the four points on Γ 1 ∩ E d actually belong to Γ 2 ⊂ Γ 1 , and correspond to those solutions computed in the subsequent step m = 2. Moreover, in contrast with spectra in Test 8, one can even sample multiplicities smaller than the maximal one, as for the case of the 4-elliptope. Already for the 5-elliptope, however, the computation becomes quite prohibitive, which is coherent with the exponential arithmetic complexity of the algorithms implemented in raglib.

d m # samples # feasible mult = m CPU time 2
In these tests, we have seen that points of maximum multiplicity can be computed efficiently in practice using LMI exact solvers in the case of hyperbolic polynomials with determinantal representation. On the other hand, larger multiplicities can be computed on general hyperbolicity cones Λ + (f, e) by sampling the loci Γ m , but with clear limitations in terms of the degree of f .

Hyperbolic programming

Hyperbolic programming is a convex optimization problem specified as follows. We are given a homogeneous polynomial f ∈ R[x] of degree d, with x = (x 1 , . . . , x n ), hyperbolic with respect to e ∈ R n , and a linear map : R n → R.

The hyperbolic program associated to data (f, e, ) is

(3) * = inf (x) s.t. x ∈ Λ + (f, e)
Assumption. We assume, without loss of generality, that in Problem (3) (x) and e T x are independent linear forms. Indeed, if (x) = λe T x for some λ ∈ R and for all x ∈ R n , then (x) is constant and equal to λ over the feasible set Λ + (f, e), and the hyperbolic program is trivial.

Since the objective function of Problem ( 3) is linear and the feasible set is convex, when the infimum is attained at x * , then x * ∈ ∂(Λ + )⊂∂Λ + . The boundary ∂Λ + is defined, locally, by the coefficients of the modified characteristic polynomial ch -x (t), as in Corollary 4. We now formalize this relationship between solutions to Problem (3) and multiplicity loci. k→∞ ---→ x * . We deduce that λ 1 (x(k)) < 0 holds for all k, and hence λ m * +1 (x(k)) ≤ 0 (because at least m * eigenvalues of x(k) must vanish). Passing to the limit, we find λ m * +1 (x * ) = 0; since x * ∈ Λ + , we get λ j (x * ) = 0 for j = 1, . . . , m * + 1, which implies mult(x * ) ≥ m * + 1, which is a contradiction. Now, two cases remain to be analyzed:

Case A : C * ⊂ Λ + . Thus (x * ) ≤ (x) for all x ∈ C * , that is x * is a (global) minimizer of on C * , hence a local minimizer of on Γ m * . Case B : There is an open set W ⊂ R n with x * ∈ W and W ∩ (Z R (f ) \ Λ + )∩L e = ∅.
In other words, W meets Z R (f ) only at feasible points. Hence x * minimizes on W ∩ Γ m * , hence it is a local minimizer of on Γ m * .

We now give a formal description of an algorithm for Problem [START_REF] Basu | A new algorithm to find a point in every cell defined by a family of polynomials[END_REF]. The idea is to represent local minimizers of the map on the set Γ m via first-order conditions involving additional Lagrange multipliers. Let f 1 , . . . , f m be the polynomials defining Γ m (see Corollary 4). A local minimizer x * of on Γ m is encoded by the following system of equations:

(4)

f 1 = 0, . . . , f m = 0, e T x = 1 z 1 ∇f 1 + • • • + z m ∇f m +z m+1 e = ∇
which means that there exists z * ∈ R m+1 such that (x * , z * ) satisfies system (4). When the number of singular points of the complex set {x ∈ C n :

∀ i = 1, f i (x) = 0, e T x = 1}
is finite, which turns out to be often satisfied, the solutions of system (4) consist of these singular points and the smooth minimizers of . Note that if (x) and e T x are dependent linear forms, then e and ∇ are multiples, and hence system (4) has infinitely many solutions (all feasible points are critical). Our assumption that , e T x are independent excludes this pathological situation.

We suppose now that we are given a routine RP that, when given as input a zerodimensional ideal I ⊂ R[x, z], returns the rational parametrization (2) for the finite set Z(I ∩ R[x]) ⊂ C n . Algorithms to compute such parametrizations have appeared e.g. in [START_REF] Rouillier | Solving zero-dimensional systems through the Rational Univariate Representation[END_REF][START_REF] Giusti | A Gröbner-free alternative for polynomial system solving[END_REF][START_REF] Jeronimo | Deformation techniques for sparse systems[END_REF]. The routine LAG is supposed to build the system (4) from data f, e, , m. The formal description of our algorithm is as follows:

Algorithm 1 SolveHP

1: procedure SolveHP(f, e, ) 2:
L ← { } 3:

for m = 1, . . . , d -1 do 4: L ← L ∪ RP(LAG(f, e, , m)) 5:
return L

The output of SolveHP is a set of rational parametrizations. The union of their solutions contains the solution to Problem (3), according to Theorem 10.

3.1.

Examples. We have implemented Algorithm 1 in Maple and used it to recover exact information on examples from the literature.

Example 11 (Quartic symmetroids). We consider the list of nodal quartic symmetroids given in [START_REF] Ottem | Quartic spectrahedra[END_REF]. The authors of [START_REF] Ottem | Quartic spectrahedra[END_REF] associate to every transversal quartic spectrahedron

S = {x = (x 0 , x 1 , x 2 , x 3 ) ∈ R 4 : A(x) 0}, where A(x) = x 0 A 0 + x 1 A 1 + x 2 A 2 + x 3 A 3 , for some A i ∈ S 4 (R), a couple (ρ, σ) of
nonnegative integers, where ρ corresponds to the number of nodes (quadratic singularities) of the real projective hypersurface {x ∈ P 3 (R) : det A(x)= 0}, and σ ≤ ρ is the number of nodes lying on ∂S . We denote the quartic of type (ρ, σ) in the list in [START_REF] Ottem | Quartic spectrahedra[END_REF] by S ρ,σ .

The goal is to perform a random analysis on the solutions of SDP instances over these sets. While this is similar to [START_REF] Nie | The algebraic degree of semidefinite programming[END_REF]Table 2], our exact viewpoint can certify the multiplicity at a given solution; indeed, once the representation ( 2) is computed, isolating the real roots of q allows to compute the signs of the coefficients of the characteristic polynomial det(tI -A(x)) exactly, hence to decide feasibility and multiplicity. The same is not possible with standard SDP solvers. We draw random linear forms

S ρ,σ m * = 1 m * = 2 S ρ,σ m * = 1 m * = 2 S 2
Q[x 0 , x 1 , x 2 , x 3 ] 1 with coefficients uniformely distributed in Z ∩ [-100
, 100], and we compute the solution in (3) with f = det A and e = I 4 . Note that in this case the standard section of the hyperbolicity cone is given by 1 = I 4 , A = Trace(A), hence we restrict the homogeneous pencil A(x) to the affine space of matrices with trace 1.

The multiplicity of a solution x * ∈ S ρ,σ in this case corresponds to the corank of A(x * ). In Table 2 we report on the percentage for the multiplicity at a minimizer on 1000 tries. There are only two possible multiplicities, that is 1 and 2. Feasible points with multiplicity 2 correspond to the singularities of the determinant lying on S ρ,σ .

We finally generated other representatives of the classes. We observe that percentages can change; indeed these depend not only on the topology of the symmetroid, but also on how the singularities on ∂S ρ,σ are exposed. We believe that this approach can be useful to solve similar classification problems of larger size. Algorithm 1 still works without the assumption that f has a determinantal representation. We test our algorithm on one such example.

Example 12. Let A(x) be a 5 × 5 homogeneous symmetric linear matrix in 4 variables x 0 , x 1 , x 2 , x 3 , with A(e) 0 for some e ∈ R 4 . Let f = det A. Then the directional derivative of f in direction e, that is the polynomial D (1) e (f ) = n i=0 e i ∂f ∂x i , is hyperbolic with respect to e (hence the same is true for the k-th derivative D

e (f ), 1 ≤ k ≤ 5, by induction), but in general does not admit a determinantal representation. For example, let

A(x) =      x 0 + x 3 2x 1 + 2x 3 x 1 + 3x 3 x 2 x 2 + 3x 3 2x 1 + 2x 3 x 0 + 4x 1 + 3x 3 x 1 -x 2 + 6x 3 x 1 + x 2 -2x 3 x 1 + x 2 + 4x 3 x 1 + 3x 3 x 1 -x 2 + 6x 3 x 0 + x 1 + 8x 3 -x 1 -x 2 -3x 3 -x 1 -x 2 + 6x 3 x 2 x 1 + x 2 -2x 3 -x 1 -x 2 -3x 3 x 0 + x 2 + x 3 x 1 + 2x 2 -x 3 x 2 + 3x 3 x 1 + x 2 + 4x 3 -x 1 -x 2 + 6x 3 x 1 + 2x 2 -x 3 x 0 + x 2 + 4x 3     
.

Then f = det A is hyperbolic with respect to e = (1, 0, 0, 0) (corresponding to the identity matrix I 5 ), and the quintic real hypersurface {x ∈ R 4 : f (x) = 0} has four singularities. As in the previous example, we cut the hyperbolicity cone with the condition Trace(A(x)) = 1 defining the affine space L e . The derivative D

e (f ) defines a singular quartic, still with four nodes and hyperbolic with respect to e (see Figure 1), which is not representable as a determinant of a symmetric pencil. Let Λ + (D

e (f ), e) be its hyperbolicity cone.

Optimizing generic linear functions over Λ + (D

e (f ), e) yields solutions of multiplicity one (smooth boundary points) for 64% of the time, and solutions corresponding to singular points (of multiplicity 2) for 36% of the time, on average. An example of multiplicity two is any multiple of the vector with coordinates

x 0 = 1 2 x 1 = 0 x 2 = 1 2 x 3 = 0
which in this case are rational numbers. A smooth point on the boundary of Λ + (D

e (f ), e) (multiplicity one), whose coordinates are given as elements of certified rational intervals, with 10 significant decimal digits, is:

x 0 ∈ [ 1697352983372573029285 1180591620717411303424 , 212169122921574321063 147573952589676412928 ] ≈ 1.437713900 x 1 ∈ [-29707767148026666593 147573952589676412928 , -29707767148024593931 147573952589676412928 ] ≈ -0.2013076605 x 2 ∈ [-18765770300641154993 73786976294838206464 , -18765770300640685591 73786976294838206464 ] ≈ -0.2543236116 x 3 ∈ [ 21153099339285995043 1180591620717411303424 , 661034354352767111
36893488147419103232 ] ≈ 0.01791737208.

In our last example, we show how our algorithm can certify lower bounds of Renegar's method, which uses derivative cones for hyperbolic programming.

Example 13 (Nie, Parrilo, Sturmfels [START_REF] Nie | Semidefinite Representation of the k-Ellipse[END_REF]; Saunderson, Parrilo [START_REF] Saunderson | Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones[END_REF]). We consider the semidefinite representation of the 3-ellipse, as computed in [START_REF] Nie | Semidefinite Representation of the k-Ellipse[END_REF]. Given n points p 1 , . . . , p n in R 2 , and a nonnegative real number D, the n-ellipse is the plane compact curve consisting of those points the sum of whose distances to p 1 , . . . , p n is D (which is called the radius of the ellipse). This set is the boundary of a spectrahedral hyperbolicity cone E n , for every D. Moreover, one has the stronger property that the algebraic boundary of E n is a determinantal hypersurface [START_REF] Nie | Semidefinite Representation of the k-Ellipse[END_REF]. However, it may be advantageous not to compute such a determinantal representation and work with the hyperbolic polynomial directly, which in the case of the 3-ellipse E 3 with foci (0, 0), (3, 0) and (0, 4) and radius 8, is the degree-8-polynomial

f = 9x 8 -72x 7 z + 36x 6 y 2 -96x 6 yz -1564x 6 z 2 -216x 5 y 2 z + 960x 5 yz 2 + 9912x 5 z 3 + + 54x 4 y 4 -288x 4 y 3 z -4748x 4 y 2 z 2 + 12256x 4 yz 3 + 70782x 4 z 4 -216x 3 y 4 z+ + 1920x 3 y 3 z 2 + 17424x 3 y 2 z 3 -71040x 3 yz 4 -262296x 3 z 5 + 36x 2 y 6 -288x 2 y 5 z- -4804x 2 y 4 z 2 + 27712x 2 y 3 z 3 + 137228x 2 y 2 z 4 -564384x 2 yz 5 -616140x 2 z 6 -
-72xy 6 z + 960xy 5 z 2 + 7512xy 4 z 3 -76416xy 3 z 4 -389688xy 2 z 5 + 1372608xyz 6 + + 1610280xz 7 + 9y 8 -96y 7 z -1620y 6 z 2 + 15456y 5 z 3 + 58014y 4 z 4 -349728y 3 z 5 --457380y 2 z 6 + 1723680yz 7 + 893025z 8 .

restricted to the plane z = 1. Let A = A(x, y, z) be the linear matrix representation of E 3 given in [26, Example 1], and hence f = det A. The corresponding 3-ellipse E 3 has the semidefinite representation {(x, y) ∈ R 2 : A(x, y, 1) 0}. The boundary ∂E n could contain one or more singularity, and if this happens, these coincide with some of the base points p 1 , . . . , p k . This is the case for the 3-ellipse we consider, which contains the point (3, 0). The polynomial f is hyperbolic with respect to e = (1, 1, 1), hence L e is given by the equation x + y + z = 1.

Our exact algorithm for hyperbolic programs, as we have already remarked, is able to certify rational intevals containing the coordinates of a solution, its multiplicity, and also the optimal value of the linear function on the solution. In order to measure the error when considering Renegar relaxations for solving hyperbolicity programs, we consider the relaxations of E 3 , namely the hyperbolicity cones of the derivatives of f in the direction e = (1, 1, 1). The infimum of the linear function (x, y, z) = x+2y+3z +4 on E 3 ∩L e is attained at the unique point of multiplicity 2, that is at (3/4, 0, 1/4) (projectively equivalent to (3, 0, 1)). We optimize the same linear function over the derivative relaxations and look at the sequence of optimal values.

In Table 3, k denotes the order of derivation of f , and x * , m * , f (x * ) denote the minimizer, its multiplicity, and the optimal value of on the given derivative cone Λ + (D e (f ) denotes the k-th derivative of f in direction e). Moreover, we report in the fifth and sixth column, the degree of the polynomial q(t) in the rational representation which is computed by our algorithm (cf. (2)) and the degree of the coordinates of x * (as algebraic numbers over Q). We first remark that the value in the fifth column decreases when considering derivative relaxations, which implies the following fact: the higher the derivative relaxation order is, the faster the exact representation, and hence the lower bound, can be computed. We Table 3. Derivative relaxations of the 3-ellipse also remark that for k = 0, 1, 2 the value in the sixth column is lower. This is because the polynomial q is reducible, and for k = 0 (resp k = 1, 2) has a linear (resp. degree 30, degree 26) factor which corresponds to the minimum polynomial of the extensions Q[x * i ] over Q. Indeed, in these cases the variety of critical points factors over Q.

  is the linear section of codimension d -1 of the cone of d × d real symmetric positive semidefinite matrices whose main diagonal is constant. Every matrix in E d is also called a correlation matrix (see[START_REF] Laurent | On a positive semidefinite relaxation of the cut polytope[END_REF] and references therein). Note that e = (1, 0, . . . , 0) (corresponding to the identity matrix A(e) = I d ) is in the interior of E d and that L e = {x ∈ R n+1 : x 0 = 1/d}.

A

  local minimizer of a continuous function : R n → R on a set S ⊂ R n is a point x * ∈ S such that there exists an open set U ⊂ R n with x * ∈ U and (x * ) ≤ (x) for all x ∈ U ∩ S. We can reduce Problem (3) to the computation of local minimizers on the multiplicity loci Γ m as follows. Theorem 10. Let f, e, be the data defining Problem (3). Let x * ∈ Λ + (f, e) with (x * ) = * , and let m * = mult(x * ). Then x * is a local minimizer of f on Γ m * . Proof. Since we are minimizing a linear function over a non-empty convex set, the minimizer (if it exists) belongs to the boundary of the feasible set, hence m * > 0. Next, we denote by C * the connected component of Γ m * containing x * . First, we suppose that C * ⊂ Λ + and that W ∩L e ∩ (Z R (f ) \ Λ + ) = ∅ holds for every open set W ⊂ R n containing x * . We show that this situation cannot occur. Indeed, since C * ⊂ Λ + , we easily deduce W ∩ (Γ m * \ Λ + ) = ∅ for all W as above. Let B k be the open ball with center x * and radius 1/k, for k ∈ N \ {0}. For all such k, we can choose x(k) ∈ B k ∩ (Γ m * \ Λ + ), yielding a sequence x(k)

k

  ≈ x * m * (x * )Degree of q(t) Alg. deg. of x * 0 (0.750, 0.000, 0.250)

  The cone Λ ++ is convex, open and coincides with the connected component of R n \ Z R (f ) containing e. Moreover, f is hyperbolic with respect to e for all e ∈ Λ ++ (f, e), and Λ ++ (f, e) = Λ ++ (f, e ). closure of Λ ++ in the Euclidean topology is called the hyperbolicity cone. It is denoted by Λ + and equals

	The

Table 1 .

 1 Sample

	1	2	2	2	0.07 s
	3 1	10	4	0	0.7 s
	3 2	4	4	4	5.1 s
	4 1	36	10	6	26 s
	4 2	36	36	30	24 s
	4 3	8	8	8	34 s

points on the d-elliptope m = 1, . . . , d -1, the number of sample points computed by raglib is given in the third column, those lying on E d ∩L e in the fourth, and those of the expected multiplicity in the fifth column; then, we report on the average time on 1000 tries on our standard desktop PC.

Table 2 .

 2 Multiplicities on random quartic symmetroids ∈

	,2	98 %	2 % S 4,0	100 %	0 %
	S 4,4	62 %	38 % S 6,2	32 %	68 %
	S 6,6	58 %	42 % S 8,4	17 %	83 %
	S 8,8	22 %	78 % S 10,6	7 %	93 %
	S 10,10	75 %	25 % S 6,0	100 %	0 %
	S 2,0	100 %	0 % S 8,2	15 %	85 %
	S 4,2	36 %	64 % S 10,4	14 %	86 %
	S 6,4	46 %	54 % S 8,0	100 %	0 %
	S 8,6	63 %	37 % S 10,2	18 %	82 %
	S 10,8	86 %	14 % S 10,0 100 %	0 %

www.unilim.fr/pages_perso/simone.naldi/software.html

Acknowledgements. Work on this project was partially supported through DFG grant PL 549/3-1 Convexity in Real Algebraic Geometry.