Olivier Julien
email: ojulien@recherche.enac.fr

Lakshmi Priya

Jean-Luc Issler
email: jean-luc.issler@cnes.fr

Laurent Lestarquit
email: laurent.lestarquit@cnes.fr

Estimating the Ionospheric Delay Using GPS/Galileo Signals in the E5 Band

Keywords: GNSS, Ionosphere estimation, Galileo, GPS I

The estimation of the ionospheric delay by a GNSS receiver is quite simple when the receiver has access to signals located at different frequencies. However, when these two frequencies are very close, this estimation process becomes very noisy. The paper presents a technique to overcome this problem in the case of the reception of Galileo signals in the E5 band only. This technique is based on a local ionosphere model and the use of carrier phase dual frequency measurements. This paper also widen this investigation to the case of the reception of two GNSS constellations, GPS and Galileo, broadcasting in the same E5 band. The performance of the estimation process are shown to be very good in Europe with a standard deviation of the estimation error at L1 that is below 30cm for the worst case ionosphere conditions.

INTRODUCTION Future Galileo and GPS open signals in Aeronautical

RadioNavigation Service (ARNS) bands -E5a, E5b, E1 OS for Galileo and GPS L5, L1C -were designed so that they can bring significant improvements to most of the users compared to the current GPS L1 C/A signal performances. Receivers will thus be able to track the different signals with a lower tracking noise and a lower multipath susceptibility, and an increased resistance to interferers, consequently providing cleaner code and phase pseudorange measurements. This enhancement was obtained thanks to, among others, the use of higher code chipping rates (10.23 MHz for Galileo E5a/E5b and GPS L5), innovative modulations (ALTBOC, MBOC) and the use of a pilot channel in parallel with the traditional data channel.

The use of these open signals together can bring further obvious improvements such as (1) a more accurate and robust ionospheric delay estimation, (2) improved ambiguity resolution performances (in terms of success rate and time to fix), (3) potential tropospheric delay estimation, and (4) frequency diversity against potential intentional or unintentional jammers. These different points were backed up by many different investigations and papers from different user community needing high precision and reliable positioning, showing a great interest in a triple-frequency Galileo/GPS receiver.

Based on this triple frequency baseline, it is however important when it comes to sensitive applications, to consider degraded modes since it might impact the expected behavior of the receiver. A typical example is the loss of one frequency and it is thus important for a triple-frequency receiver to consider the loss of any of the E5a, E5b and E1 signal and its consequence on required performances. This article specifically focuses on the event of the loss of the L1/E1 band. This situation is of particular interest because it means that the receiver is left with measurements coming exclusively from Galileo E5a/E5b and GPS L5 signals. This represents for Galileo two spectrally very close signals, and for GPS a mono-frequency case, which are not ideal cases for precise positioning. Many different figures of merit are to be investigated in this degraded mode scheme to fully assess how the receiver can cope without significantly losing any of its performance. However, this article will only focus on the ionospheric delay estimation using the available GPS/Galileo signals.

The motivation behind this investigation is to show that for a triple frequency Galileo/GPS receiver, whatever the jammed band, it is always possible to estimate accurately the ionospheric delay affecting pseudorange measurements and thus keep an interesting accuracy positioning for the receiver. Moreover, an extension of this conclusion is the potential use of the E5 band alone for precise positioning applications.

The authors have already presented initial results in 2009 [START_REF] Julien | Ionospheric Delay Estimation Strategies Using Galileo E5 Signals Only[END_REF] and 2012 [START_REF] Julien | Ionospheric Delay Estimation Using Galileo E5 Signals Only[END_REF], both using Galileo E5 signals only. These articles investigated the use of an ionospheric delay estimation process based on a Kalman Filter (KF) which was used code and carrier phase geometry free combinations, jointly with a simplified linear local model of the Vertical Total Electron Content (VTEC) to represent the ionospheric delay of any visible satellites. The initial results, based on simulations, were promising since the ionospheric delay estimation error standard deviation was at the decimeter-level for high level of solar activity assuming that the true ionosphere was perfectly modeled by the NeQuick model. This paper goes further by providing the following: [START_REF]European Union, European GNSS (Galileo) Open Service Signal-in-Space Interface Control Document[END_REF]. It is also an ARNS band, thus protected by ITU, but with no exclusivity to RNSS. This means that any system broadcasting within this band will have to cope with the existing non-RNSS services already present in this band. In particular, systems using strong pulsed signals, such as Distance Measuring Equipments (DME), TACtical Air Navigation (TACAN), Joint Tactical Information Distribution Systems(JTIDS)/ Multifunctional Information Distribution Systems (MIDS) are deployed in this band [4; 5].

The Galileo E5 signal has 2 components:  The E5a signal is transmitted in the frequency band [1164 MHz -1191.795 MHz] and centered on =1176.45 MHz. It will fully support the Galileo Open Service (OS) and will support the Safety of Life (SoL) service through its ranging function. It is composed of a data and pilot channel with equal power. The data channel broadcasts the F/NAV message with a symbol rate of 50 sps. Since the useful data is encoded using a convolutional code with a constraint ½, the actual data bit rate is 25 bps. Galileo E5a is Quadra-Phase Shift Keying (QPSK)-modulated and uses a 10230chip long spreading code with a chipping rate of 10.23 Mcps. This means that it is a wide-band signal that will exhibit excellent resistance towards thermal, multipath and narrow-band interference compared to the currently available GPS C/A signal. It is also worth noting that the Galileo E5a signal will overlap the GPS L5 signal, which has similar signal characteristics. It means that it will likely be part of GPS/Galileo receivers using the E5a/L5 frequency band.

 The E5b signal is transmitted in the frequency band [1191.795 MHz -1215 MHz], centered on =1207.14 MHz. The Galileo E5b signal will support the OS, the SoL full service (ranging and integrity functions) and the Commercial Service (CS). It is composed of data and a pilot channels with equal power. The data channel broadcasts the I/NAV message (corresponding to the SoL service) with a symbol rate of 250 sps This means a useful data bit rate of 125 bps due to the convolutional encoding with a constraint 1/2. Galileo E5b uses a 10230-chip long spreading code with a chipping rate of 10.23 MHz. Although the Galileo E5b does not coincide spectrally with any planned GPS signal, it has the same frequency and modulation as the future COMPASS B2 signal, which might be interoperable with Galileo E5b, and is very close to the future GLONASS L3 signal.

It can be seen that Galileo E5a and Galileo E5b are present in adjacent bands. In order to take advantage of that, the 2 signals are transmitted coherently using an ALTBOC [START_REF] Sahmoudi | U-SBAS: A Universal multi-SBAS Standard to ensure Compatibility, Interoperability and Interchangeability[END_REF][START_REF] Komjathy | Global ionospheric Total Electron Content mapping using the Global Positioning System[END_REF] multiplexing [START_REF] Lestarquit | ALTBOC for Dummies or Everything you Always wanted to Know about ALTBOC[END_REF]. The whole Galileo E5 signal is thus an extra wide-band signal (more than 50 MHz wide) that can be received:

 as a whole: this means that the user can process an extrawide band signal for positioning, thus enjoying pseudorange measurements that are the most resistant GNSS signals towards thermal noise, multipath and narrow-band interference [START_REF] Simski | Performance Assessment of Galileo Ranging Signals Transmitted by GSTB-V2 Satellites[END_REF].  separately: in this case, the user does not require a receiver with an extra-wide bandwidth, thus reducing the complexity of the receiver. Note that a dual frequency E5a/E5b receiver can process in parallel both signals, thus obtaining measurements from 2 wide-band signals that were generated based on the same satellite payload module (same filter with excellent stability over the E5 band, same HPA) at 2 different frequencies.

Compared to the Galileo E1 OS, and to a larger extend GPS L1 C/A, the Galileo E5a and E5b signals will provide enhanced tracking capabilities, and thus are very promising for precise positioning applications. Moreover, [START_REF]European Union, European GNSS (Galileo) Open Service Signal-in-Space Interface Control Document[END_REF] specifies that both Galileo E5a and E5b signals should be received with a minimum power 2 dB above the Galileo E1 OS. This also means a better performance in case of signal obstruction.

The Galileo E5 signal performances were presented in [START_REF] Julien | Ionospheric Delay Estimation Strategies Using Galileo E5 Signals Only[END_REF] and will not be detailed in here. It is still worth mentioning that:

 the coherent code tracking performance (against thermal noise, multipath and interference) of the Galileo E5 signal is extremely good compared to any other GNSS signals due to its very wide bandwidth  the coherent code tracking of the Galileo E5a and E5b is equivalent to that of a BPSK(10) signal.

2) GPS L5 Signal

The GPS L5 signal is transmitted in centered on = =1176.45 MHz. It is composed of a data and a pilot component. It is a QPSK-modulated signal and uses 10230-chip long spreading codes with a chipping rate of 10.23 Mcps. As a consequence, it is very similar to Galileo E5a signal and exhibits very similar performance.

B. Observable Model

Let us denote and the code and carrier phase pseudorange measurements from satellite at frequency . Their usual model is provided by:

= + ( - + + + , + , + , ) (1)
= + ( -

+ - + , + , + , + ) (2)
where In order to gather the elements of ( 1) and ( 2) that are common to the different frequencies and observables of satellite , they can be re-written as:


= + + , + , + , (3) = - + , + , + , + (4)
where

= + ( - +
It is well-known that the ionospheric term can be approximated, at the first order, by:

= . •
where  is the signal's carrier frequency, and  is the Slant Total Electron Content (TEC), which represents the TEC along the signal propagation path.

III. PRESENTATION OF THE IONOSPHERE ESTIMATION TECHNIQUES

The reference ionosphere delay estimation technique is fully presented in [START_REF] Julien | Ionospheric Delay Estimation Using Galileo E5 Signals Only[END_REF] and is only briefly described here.

A. Dual Frequency Measurements

The ionosphere delay for each visible satellite can be estimated from two signal at two frequencies using dual-frequency code geometry-free combinations as follows:

, -

with , = -

In the case of an E5a and E5b combination, the coefficient , is equal to 19.9 when estimating the ionospheric delay at E5a. This means that all the tracking errors (due to multipath, noise, interference) and hardware biases are multiplied by 19.9 when estimating the ionospheric delay at E5a. It is quite clear that this is very detrimental to the accuracy of the ionospheric delay estimation. It is then interesting to use dual frequency geometry-free carrier-phase combinations instead:

, - = ( - + , ( , -, + , -, + , -, + - ) ) (6)
In this case, the multiplication factor is not as problematic as the carrier phase tracking errors are only at the mm/cm level. However, in this case, a float ambiguity term (coming from the carrier phase ambiguities) ---has to be estimated as well. It is thus necessary to estimate the ambiguity terms together with the ionosphere term. As a consequence, the system has more unknowns than measurements.

B. Single Frequency Measurements

If only one frequency is available, the ionospheric delay of each satellite can then be estimated using the Code-Minus-Carrier (CMC) combinations as follows:

- ≈ ( + ( , + , + , -, - ) ) (7)
The above equation takes into account the fact that code tracking errors are two degrees of magnitude greater than the carrier phase tracking errors. As it can be seen, the CMC combination also integrates the carrier phase ambiguities and thus these ambiguities have to be jointly estimated with the ionosphere delay.

C. Local Ionospheric Model

To reduce the number of unknowns in the dual-frequency and single-frequency systems shown above, it is possible to try to use a simple local ionospheric delay model. This creates another advantage which is to link the ionospheric delay terms associated with each visible satellite with a set of parameters to estimate. Modeling the local variations of the vertical ionospheric delay around the user to facilitate the estimation of the ionospheric slant delay has been used for single-frequency (GPS L1 C/A) ionospheric estimation in [8; 9] and has also been used for dual frequency GPS L1/L2 measurements in [START_REF] Komjathy | Global ionospheric Total Electron Content mapping using the Global Positioning System[END_REF] in the context of Precise Point Positioning (PPP) using a network of reference stations. These models assume that the ionospheric delays can be modeled using:

 A single layer ionospheric model that is such that each point of the ionosphere layer equals the VTEC  A local VTEC model that is such that the VTEC at any ionospheric pierce point (intersection between the assumed single-layer ionosphere and the signal propagation path) can be modeled as a function of: o the VTEC at a specific reference point, and o a VTEC gradient according to the difference in latitude and longitude between the pierce point location and the reference position.  A mapping function that maps the VTEC at the ionosphere pierce point into the STEC. A typical mapping function to transform the VTEC into an STEC is [Lestarquit et al, 1999]:

= √ - ( + ℎ (8)
where


is the Earth radius (6378.1363 km),  is the satellite elevation (in rad), and  ℎ is the height of the maximum TEC, which is also the height of the ionosphere layer modeled as a single-layer.

Nine simple local VTEC models derived from the above general model were tested in [START_REF] Julien | Ionospheric Delay Estimation Using Galileo E5 Signals Only[END_REF] in the case of a Galileo E5a/E5b receiver. The elected one was based on the the expression of the VTEC at the ionosphere pierce point as a function of 5 parameters:

 The VTEC at the zenith of the user , and  4 VTEC gradients in the North , East , South , West directions  The considered latitude of the ionosphere pierce point and the user location is the geomagnetic latitude.

This local VTEC model can be represented as:

̂ = ( + ( -, • + ( -, • + ( - , • + ( - , • ) (9)
where  are the user and pierce point latitudes, and  are the user and pierce point longitudes.

Using the fact that the ionospheric delay at frequency for satellite can be modeled as:

̂ = . • ̂ It follows that: ̂ = ( + max(∆ , , • + min(∆ , , • + max(∆ , , • + min(∆ , , • ) (10)
where

 = . •  ∆ , = -  ∆ , = -

D. Ionosphere Estimation using Galileo E5 Only

The ionospheric delay estimation described in [START_REF] Julien | Ionospheric Delay Estimation Using Galileo E5 Signals Only[END_REF] is based on a Kalman filter that uses (1) the dual frequency code and carrier phase measurements as measurements and ( 2) the local VTEC model parameters and the ambiguity terms as state parameters.

The state matrix is thus:

[ ∆ , ∆ , … ∆ , ∆ , ∆ , … ∆ , ] = [ , , … , ] + [ , , , , … , , , , , , … , , ]
with where

 ∆P E ,E Y = P E Y -P E Y  ∆φ E ,E Y = φ E Y -φ E Y  A E ,E = λ E A E Y -λ E A E Y  N P,E
 K ̿ E k = [ K k K k … K n k ] ,  ∆lat ̿̿̿̿̿ k = [ max ∆lat , k , max ∆lat , k , … max ∆lat , n k , min ∆lat , k , min ∆lat , k , … min ∆lat , n k , ]
,

 ∆long ̿̿̿̿̿̿̿̿ k = [ max ∆long , k , max ∆long , k , … max ∆long , n k , min ∆long , k , min ∆long , k , … min ∆long , n k , ]
,

 ̿ n is a n-by-n zero matrix  I ̿ n is a n-by-n identity matrix It is interesting to note that this system has the advantage to separate the inter-frequency bias from the ionospheric delay terms since the inter-frequency bias will be absorbed by the (float) ambiguity state once the filter has converged.

The transition matrix is based on the following assumptions:

 The ionosphere-related terms are modeled as first-order Gauss-Markov processes.  The ambiguity terms are modeled as first-order Gauss-Markov processes since these states will absorb the potential variation of the hardware biases as well as the ionosphere modeling error  The Earth rotation is taken into account to update the vertical ionospheric delay between 2 consecutive time updates.

The transition matrix associated to the reference local ionosphere model is thus:

[ VTEC u k + g N k + g k + g E k + g k + A E ,E k + A E ,E k + … A E ,E n k + ] = F [ VTEC u k g N k g k g E k g k A E ,E k A E ,E k … A E ,E n k ] + [ σ EC • n EC σ G N • n G σ G S • n G S σ G E • n G E σ G W • n G W σ A • n A S … σ A • n A S ] with F = [ … … … W e … … … … … … … ]
where

 σ EC , σ G N , σ G S , σ G E , σ G W
, are the standard deviations associated with the variation of the local ionosphere parameters,  σ A corresponds to the standard deviation associated with the variation of the ambiguity term (mostly due to the ionosphere modeling error variation).

 n EC , n G N , n G S , n G E , n G W , n A S , … , n A S Y are independent
Gaussian noise with a unit variance, and  W e is the Earth rotation rate (rad/s)

E. Ionosphere Estimation for Galileo E5/GPS L5

When using Galileo E5 and GPS L5, the estimation process has to be amended since Galileo will provide dual-frequency measurements, while GPS will only provide measurements on L5. Using CMC measurements for GPS L5, the system to solve is now:

[ ∆ , ∆ , … ∆ , ∆ , ∆ , … ∆ , ′ ′ … ′ ] = [ , , … , ′ ′ … ′ ] + [ , , , , … , , , , , , … , , , ′ ,
′ … , ′ ]
As it is easy to have the expression of the matricx from this system from what was presented in the Galileo E5 only case, this will not be detailed here. The same deduction can be done regarding the transition matrix .

F. Ionosphere Estimation for Dual Constellation / Dual Frequency

For references, a third test case was investigated. This test case aimed at assessing the performance of the estimation process in the case of Galileo E5 together with another constellation that would have two available signals in the E5 band. This case is interesting as it would allow using dual frequency carrier phase measurements instead of CMC, which are much noisier. As a consequence, a 'fictitious' GPS constellation was used that assumed that GPS satellites were able to transmit an ALTBOC(15,10) on the same frequency as Galileo E5. By doing so, the idea was to test the estimation process using dual constellation dual frequency carrier phase measurements.

As in the case of Galileo E5/GPS L5, the Kalman filter equations can be deduced from what was presented in the Galileo E5 only case as the local VTEC model is assumed the same.

G. Local VTEC Model based on 3 Gradients

In [START_REF] Julien | Ionospheric Delay Estimation Using Galileo E5 Signals Only[END_REF], the true VTEC variations from obtained from the NeQuick model were analyzed. It was observed that there could be some potential strong variations of the gradients in the North/South directions over Europe. This is why it was decided in the first place to have separate North and South gradients.

However, the variation in the East/West direction appeared more linear. As a consequence, in the frame of this paper, another local VTEC model will be tested based on only 3 gradients: North, South and East/West. The will to test this model is to see how a model with less parameters would behave, in particular taking advantage of a greater observability of each parameter.

IV. PRESENTATION OF THE SIMULATION TOOL AND FILTER SETTINGS

A. Simulation Tool

The simulation tool is exactly the same as the one used in [START_REF] Julien | Ionospheric Delay Estimation Using Galileo E5 Signals Only[END_REF].

There are however two differences:

 the true ionosphere is now modeled using the NeQuick2 model, an evolution of the NeQuick model freely available on the ITU website and used in [12; 13; 14]. For visualization purposes, the C/N0 for the considered Galileo E5 signals's component at the user antenna output is shown in Figure 1Erreur ! Source du renvoi introuvable.. The difference between NeQuick1 and NeQuick2 is mainly that the variation of the VTEC are not as sharp in NeQuick2 as it is in NeQuick1 due to modifications in the modeling of the high altitude ionosphere layers.  GPS satellites are assumed to follow the GPS constellation defined in [START_REF]Assessment of Radio Frequency Interference Relevant to the GNSS L5/E5a Frequency Band[END_REF]. The link budget associated with the GPS satellites takes into account the power output difference between GPS and Galileo signals.  Multipath are generated assuming single reflector (the Earth surface) and the user antenna located on a pole 2 meters above the ground.

B. Kalman Filter Settings

The observation noise variance was chosen to the product of a C/N0-dependent term and an elevation-dependent term. The C/N0-dependent term is the usual theoretical tracking noise variance [START_REF] Van Dierendonck | GPS Receivers in Global Positioning System: Theory and Practice[END_REF]. The elevation-dependent variance represents the impact of multipath and was chosen to be equal to

+ sin E S Y k .
The chosen covariance matrix for the process noise was set empirically to allow for a variation of 0.1 cm/s for the vertical ionosphere component, 0.5 cm/rad/s for the gradients, and 0.01cm/s for the ambiguity terms.

C. Simulation Parameters

The receiver mask was chosen equal to 10°.

Five locations were selected to represent a diversity in terms of latitudes and longitudes:

 Sevilla, which is supposed to be close to the VTEC peak and should thus have higher VTEC gradients  Toulouse, which is in the middle of Europe (in terms of latitude) and should have average VTEC gradients, and  Stockholm, which is in the upper part of Europe (in terms of latitude) and should have low VTEC gradients  Beijing, which sees an ionosphere activity that should be similar to Sevilla (see Figure 2)  Shanghai, which is very close to the VTEC peak and can be considered as a worst case scenario (see Figure 2).

Figure 2 -Representation of the VTEC with the VTEC Peak Located over Southern Asia

Also, four time periods were used to represent the TEC during a plurality of ionosphere activities. These periods were selected thanks to the table of the monthly R12 indexes over the period 1931-2001 provided by ITU (its cumulative distribution is shown in Figure 3) [START_REF] Itu-R | Reference ionosphere characteristics[END_REF]. The four periods selected were:



V. SIMULATION RESULTS

A. Analysis of Results in Europe

The simulations were then run for the 5 locations, for the 4 time slots, and for all the configurations (Galileo E5 only, Galileo E5/GPS L5, Galileo E5/'fictitious GPS dual frequency').

Four output of the simulations are analyzed:

 the max ionosphere estimation error at L1,  the 68th percentile of the ionosphere estimation error at L1  the 95th percentile of the ionosphere estimation error at L1  the 99th percentile of the ionosphere estimation error at L1

The ionosphere estimation errors are given at L1 since this is the usual reference frequency at the moment. In the following, the statistics are computed considering only the ionosphere estimation error of:

 all Galileo satellites above the receiver mask (10°) and  all Galileo satellites above 30°, still considering that all satellites above 10° are use.

The results for the European cities of the simulations are provided in Table 1 for satellites above 10°, and in Table 2 for the satellites above 30° (Table 2 also only presents the results for the 4-gradient local VTEC model). In these tables, the lowest values for a given day and location are in bold.

It appears generally that the best results are obtained when using dual constellation with dual-frequency. The main advantage of this configuration over the Galileo E5 only configuration is to limit the occurrence of large errors as seen with the maximum and 99 th percentile of the ionosphere estimation error. This is true mostly in the difficult cases (very high ionosphere activity). This means that the use of the dual constellation dual frequency case allows a better assessment of the rising and setting satellites' ionosphere delay, probably due to the fact that twice as many satellites are used and that the ionosphere sounding is thus more distributed around the user. However, for a quieter ionosphere, the results between the dual constellation dual frequency and single constellation dual frequency are quite comparable. The main reason is that the main source of error of the proposed ionosphere estimation process in a quieter situation is the chosen model itself: the local VTEC model itself as well as the mapping function.

The dual constellation dual frequency configuration allows having worst case ionosphere estimation error below 2 meters and a standard deviation of the ionosphere estimation error below 30 cm in the 3 European cities. When looking only at satellites above 30° (see Table 2), these worst case results show a maximum error below 1 m and a standard deviation of the estimation error below 20 cm in the 3 European cities. This is an excellent result considering that these results include the top 1% of the strongest ionosphere activity.

Finally, the Galileo E5/GPS L5 configuration appears to provide the worst results. This is even quite significant for simulations in Toulouse and Sevilla where the ionosphere is more active. The main reason that the GPS L5 CMC measurements are much more affected by multipath than Galileo E5a/E5b dual frequency carrier-phase measurements. This can create local errors that leak into the ionosphere parameters resulting in large estimation errors, particular for low elevation satellites

From Table 1, it can also be seen that the choice of 3 or 4 gradients does not make much of a difference in the estimation process. Thus validating that the VTEC is almost linear in the East/West direction.

B. Detailed Analysis of Results for Toulouse in May 1980

In order to understand the estimation process, a specific analysis of a test case is interesting. The test case chosen here is the case of Toulouse in May 1980. The number of visible Galileo and GPS satellites over a day is shown in Figure 4. In the dual constellation dual frequency configuration, Figure 5 and Figure 6 show the output of the estimation process (vertical ionosphere and gradients respectively). The observation of the estimated gradient show that while the estimated North and South gradients can differ quite significantly, thus justifying the use of 2 different parameters, this is not the case of the East and West gradients that tend to remain with the same value. This explains that the cases of 3 and 4 gradients in the estimation process do not lead to significantly different results. Figure 8 and Figure 9 show the ionosphere delay error as a function of the ionosphere pierce point longitude and geomagnetic latitude with respect to the user location (respectively). It can be seen that the highest uncertainty seem to come on the latitude (North/South) since the plots create a wide area. On the other hand, in the East/West direction (longitude), a trend seem to appear as a second order function in which the ionosphere error seems to grow when the difference between the longitude of the pierce point and of the user increases. This could mean that a more optimal local VTEC could be found.

Other local VTEC were tested to take into account this observation, in particular by adding a second order coefficient for the gradients. However, no improvement was noticeable in other tested configurations. It is believed that the use of a more optimal local VTEC model might only bring marginal improvement since there is also an uncertainty on the actual accuracy of the mapping function when the ionosphere is very active.

VI. CONCLUSIONS

This paper has shown further results to the ionosphere delay estimation process that was presented in [START_REF] Julien | Ionospheric Delay Estimation Strategies Using Galileo E5 Signals Only[END_REF], [START_REF] Sahmoudi | U-SBAS: A Universal multi-SBAS Standard to ensure Compatibility, Interoperability and Interchangeability[END_REF] and [START_REF] Julien | Ionospheric Delay Estimation Using Galileo E5 Signals Only[END_REF]. In particular, it is based on a more representative ionosphere condition due to the use of the latest NeQuick model for the simulations. It also proposed the use of a new local VTEC model and of new receiver configurations.

The simulation results show that the proposed ionosphere estimation process, when having access only to the E5 band and to two constellations with two frequencies in the band, can be quite interesting in Europe even in case of a very active ionosphere. Indeed, it was shown that in one of the worst case situations (top 1% of the greatest ionosphere activity), the standard deviation of the ionosphere estimation error at L1 was below 30 cm for satellites above 10° and below 20cm for satellites above 30°. It also showed that the maximum error was around 2m (and below 1m 99% of the time).

It was also shown that it was very interesting even if only one dual frequency constellation (Galileo) was available in the E5 band as a significant performance degradation with respect to the dual constellation configuration was only seen for extremely active ionosphere conditions.

Finally, the use of a second constellation with only one signal in the E5 band was shown not to be very interesting as it increased the estimation error due to the use of CMC measurements.

The limitation of the model was also highlighted when the user location becomes too close to the VTEC peak location as the simple linear local model then cannot accommodate large and steep VTEC variations in several directions.

  the superscript refers to the satellite ,  represents the true satellite-receiver range,  represents the satellite clock bias,  represents the receiver clock bias,  represents the tropospheric delay,  represents the ionospheric delay at freq. ,  and represent the errors due to multipath on the code and phase pseudoranges,  and represent the error due to thermal noise on the code and phase pseudoranges,  , and , represent the satellite+receiver code and phase biases at frequency .  represents the carrier phase ambiguity at frequency ,  represents the wavelength of the carrier .

  ,E and N φ,E ,E are the observation noise assumed Gaussian.

Figure 1 -

 1 Figure 1 -C/N0 of Galileo E5a Signals at the Antenna Output

Figure 3 -

 3 Figure 3 -Cumulative Distribution of Monthly R12 indexes

Figure 4 -

 4 Figure 4 -Number of Visible Satellites (above 10°) in Toulouse in the Considered Scenario

Figure 5 -Figure 6 -Figure 7

 567 Figure 5 -Estimated Vertical Ionosphere based on Two Dual Frequency (in E5) Constellations in Toulouse in May 1980

Figure 7 -

 7 Figure 7 -Ionosphere Estimation Error (at L1) based on Two Dual Frequency (in E5) Constellations in Toulouse in May 1980 conditions

Figure 8 -Figure 9 -

 89 Figure 8 -Ionosphere Estimation Error (at L1) as a Function of the Pierce Point Longitude based on Two Dual Frequency (in E5) Constellations in Toulouse in May 1980 conditions



  Use of signals from two constellations in the E5 bands.

	 More extensive results in Europe based on more simulations (previous results were obtained in Sevilla,
	Toulouse and Stockholm during two 24h time periods
	representing high solar activity).
	II. DESCRIPTION OF GALILEO E5 AND GPS L5 SIGNALS
	AND ASSOCIATED OBSERVABLE MODELS
	A. Presentation of the Galileo E5 and GPS L5 Signals
	1) Galileo E5 Signals
	The Galileo E5 signals are part of the E5 band ([1164-1215
	MHz] that is the largest RadioNavigation Satellite System
	(RNSS) band
	 Use of the updated NeQuick model to represent the true ionosphere, thus providing more representative
	results

Table 3 and

 3 Table 4 show the results for Beijing and Shanghai only for the dual frequency cases and only for the 4-gradient local VTEC model. It can be seen that the results in Beijing are similar to the ones in Europe, which is not surprising as it has a similar geomagnetic latitude. However, Shanghai shows very large estimation errors with worst case situations reaching almost 5m (above 60cm standard deviation). This is due to the difficulty for the proposed linear VTEC model to accommodate the vicinity of the VTEC peak that creates large non-linear variations. Still the results can be seen as reasonable given the conditions.

Table 1 -

 1 Performance Analysis of the Ionospheric Delay Estimation Process in European Cities using the 6 Test Cases (Galileo Only, Galileo/GPS, Galileo/Fictitious GPS in the case of 3 and 4 gradients for the local VTEC model)

	Stockholm	Toulouse	Seville
	1958 1980 2002

1998 1958 1980 2002 1998 1958 1980 2002 1998

	Galileo E5 Only 4 Grad.	68 th perc. 95 th perc. 99 th perc. Max	0.25 0.68 1.01 2.57	0.24 0.18 0.12 0.25 0.26 0.16 0.11 0.33 0.31 0.64 0.57 0.37 0.69 0.70 0.44 0.32 0.82 0.81 0.93 1.10 0.74 0.97 1.18 0.76 0.58 1.31 1.08 1.47 2.41 1.21 1.82 1.71 1.23 1.33 2.53 2.52	0.21 0.59 0.89 2.18	0.14 0.43 0.66 1.17
	Galileo E5 Only 3 Grad.	68 th perc. 95 th perc. 99 th perc. Max	0.26 0.70 1.02 2.28	0.24 0.18 0.12 0.27 0.27 0.17 0.12 0.36 0.35 0.65 0.57 0.37 0.77 0.81 0.43 0.3 1.00 1.01 0.94 0.98 0.63 1.02 1.14 0.69 0.53 1.49 1.39 1.55 2.10 1.19 1.68 1.54 1.12 1.23 2.84 2.84	0.20 0.66 1.03 1.65	0.14 0.48 0.66 1.15
	Galileo E5 / GPS	68 th perc. 95 th perc.	0.21 0.59	0.27 0.19 0.09 0.53 0.53 0.23 0.17 0.67 0.66 0.77 0.49 0.34 1.69 1.68 0.73 0.54 1.79 1.80	0.22 0.95	0.26 0.82
	L5	99 th perc.	0.89	1.32 0.74 0.54 2.58 2.55 1.28 1.03 2.83 2.96	2.26	1.44
	4 Grad.	Max	2.18 2.34	1.19 0.93 3.42 3.42 3.03 1.74 4.67 4.55	3.62	2.37
	Galileo E5 / GPS	68 th perc. 95 th perc.	0.20 0.66	0.28 0.18 0.11 0.58 0.59 0.26 0.16 0.79 0.76 0.64 0.53 0.30 1.84 1.88 0.74 0.55 1.93 1.91	0.24 0.86	0.28 0.93
	L5	99 th perc.	1.03	1.14 0.77 0.45 2.80 2.89 1.20 1.09 2.68 3.14	1.84	1.40
	3 Grad.	Max	1.65	1.69 1.46 0.70 3.67 4.21 2.81 1.76 5.67 5.90	3.75	2.76
	Galileo E5 / GPS	68 th perc. 95 th perc.	0.25 0.62	0.24 0.17 0.10 0.26 0.27 0.14 0.11 0.31 0.32 0.56 0.47 0.28 0.72 0.70 0.41 0.29 0.78 0.78	0.19 0.51	0.13 0.38
	«Bi-Freq»	99 th perc.	0.89	0.77 0.78 0.48 0.96 1.04 0.65 0.54 1.18 1.11	0.77	0.55
	4 Grad.	Max	1.45	1.29 1.25 0.73 1.55 1.47 1.15 1.19 1.90 1.93	1.48	1.16
	Galileo	68 th perc.	0.26	0.24 0.17 0.10 0.29 0.30 0.15 0.11 0.32 0.34	0.17	0.13
	E5 / GPS «Bi-Freq» 3 Grad.	95 th perc. 99 th perc. Max	0.65 0.89 1.42	0.58 0.50 0.29 0.77 0.76 0.42 0.29 0.93 0.92 0.81 0.76 0.44 1.14 1.21 0.61 0.52 1.28 1.27 1.21 1.18 0.63 1.63 1.70 1.08 1.14 1.82 1.78	0.59 0.79 1.34	0.38 0.56 1.09

Table 2 -Performance Analysis of the Ionospheric Delay Estimation Process in European Cities using the 3 Test Cases (Galileo Only, Galileo/GPS, Galileo/Fictitious GPS in the case of 4 gradients for the local VTEC model) Stockholm Toulouse Seville 1958 1980 2002 1998 1958 1980 2002 1998 1958 1980 2002 1998 Galileo E5 Only 4 Grad.

 2

		68 th perc.	0.14	0.14 0.10 0.07 0.15 0.15 0.10 0.08 0.19 0.19	0.12	0.09
		95 th perc.	0.36	0.33 0.24 0.18 0.38 0.37 0.23 0.18 0.48 0.49	0.30	0.22
		99 th perc.	0.50	0.47 0.33 0.26 0.50 0.51 0.32 0.28 0.70 0.68	0.43	0.30
		Max	0.73	0.70 0.57 0.39 0.68 0.67 0.39 0.48 0.80 0.84	0.61	0.43
	Galileo E5 / GPS	68 th perc. 95 th perc.	0.18 0.40	0.20 0.14 0.04 0.34 0.34 0.16 0.11 0.48 0.46 0.42 0.33 0.13 0.90 0.90 0.37 0.28 1.01 0.96	0.17 0.47	0.20 0.40
	L5	99 th perc.	0.57	0.57 0.51 0.21 1.40 1.39 0.50 0.43 1.45 1.42	0.70	0.59
	4 Grad.	Max	0.75 0.75	0.58 0.33 1.66 1.63 0.99 0.63 2.22 2.16	1.54	0.94
	Galileo E5 / GPS	68 th perc. 95 th perc.	0.14 0.37	0.13 0.10 0.07 0.17 0.18 0.10 0.07 0.21 0.21 0.35 0.24 0.15 0.39 0.40 0.20 0.16 0.50 0.51	0.10 0.27	0.08 0.21
	«Bi-Freq»	99 th perc.	0.54	0.50 0.33 0.21 0.54 0.53 0.30 0.27 0.71 0.67	0.38	0.30
	4 Grad.	Max	0.73	0.70 0.57 0.28 0.71 0.66 0.40 0.43 1.03 0.98	0.49	0.46


Roland Hildebrand
email: roland.hildebrand@imag.fr

A lower bound on the barrier parameter of barriers on convex cones

Let K ⊂ R n be a regular convex cone, let e1, . . . , en ∈ ∂K be linearly independent points on the boundary of a compact affine section of the cone, and let x * ∈ K o be a point in the relative interior of this section. For k = 1, . . . , n, let l k be the line through the points e k and x * , let y k be the intersection point of l k with ∂K opposite to e k , and let z k be the intersection point of l k with the linear subspace spanned by all points e l , l = 1, . . . , n except e k . We give a lower bound on the barrier parameter ν of logarithmically homogeneous self-concordant barriers F : K o → R on K in terms of the projective cross-ratios q k = (e k , x * ; y k , z k ). Previously known lower bounds by Nesterov and Nemirovski can be obtained from our result as a special case. As an application, we construct an optimal barrier for the epigraph of the || • ||∞-norm in R n and compute lower bounds on the barrier parameter for the power cone and the epigraph of the || • ||p-norm in R 2 .

Introduction

In modern convex optimization, interior point methods are the primary tool to solve conic programs. A central role in solution algorithms for conic programs over some regular (with nonempty interior, containing no lines) convex cone K is assigned to a smooth real-valued convex function F : K o → R on the interior of the cone, the barrier. In order to be useful for optimization, the barrier has to satisfy certain properties [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF]Section 2.3]. The second and third derivative have to satisfy the self-concordance relation

F ′′′ (x)[h, h, h] ≤ 2(F ′′ (x)[h, h]) 3/2 ∀ x ∈ K o , h ∈ T x K o , (1)
with h running through the tangent space at x. The function F has to tend to infinity as its argument tends to the boundary of the cone, lim

x→∂K F (x) = +∞, (2)
and it has to satisfy the logarithmic homogeneity condition

F (αx) = -ν log α + F (x) ∀ α > 0, x ∈ K o . (3)
A smooth function F : K o → R satisfying conditions (1,2,3) is called a logarithmically homogeneous self-concordant barrier for the cone K. The real constant ν is called the barrier parameter of the barrier F .

The lower the barrier parameter of a barrier, the faster are the interior point algorithms based on this barrier. For conic optimization problems over a cone K, it is therefore desirable to have barriers on K with a barrier parameter as small as possible. We call a logarithmically homogeneous self-concordant barrier on K optimal if it has the lowest possible barrier parameter.

Optimality of a barrier F is proven by verifying properties [START_REF] Chares | Cones and Interior-Point Algorithms for Structured Convex Optimization involving Powers and Exponentials[END_REF][START_REF] Güler | Characterization of the barrier parameter of homogeneous convex cones[END_REF][START_REF] Nesterov | Towards nonsymmetric conic optimization[END_REF] and showing that the barrier parameter ν of F is equal to a lower bound ν * on this parameter for the given cone. For general cones, all lower bounds on the barrier parameter which are available today are based on a result of Nesterov and Nemirovski [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF]Sect. 2.3.4]. Namely, if for some boundary point z ∈ ∂K of the cone there exists a neighbourhood U of z and affine half-spaces A 1 , . . . , A k ⊂ R n with z ∈ ∂A j , j = 1, . . . , k, such that the normals to the half-spaces at z are linearly independent and the intersection U ∩ K equals the intersection

U ∩ A 1 ∩ • • • ∩ A k 1
, then a lower bound on the barrier parameter of any self-concordant barrier on K is given by ν * = k. Based on this result, Güler and Tunçel proved that the minimum over the Carathéodory numbers of all points in the interior of K also is a lower bound on the barrier parameter [START_REF] Güler | Characterization of the barrier parameter of homogeneous convex cones[END_REF]Prop. 4.1]. In this way, the standard barriers for the symmetric cones used in linear, conic quadratic, and semi-definite programming are shown to be optimal. Optimal barriers can be constructed also for general homogeneous cones, with the barrier parameter equal to the rank of the cone [START_REF] Güler | Characterization of the barrier parameter of homogeneous convex cones[END_REF]Theorem 4.1].

In this contribution, we provide a new lower bound on the barrier parameter of barriers on a general cone (Theorems 4.4, 5.4). For n-dimensional cones, this lower bound is contained in the interval [2, n] (Corollary 3.2 and Theorem 5.7). From our result, a slightly stronger bound than that in [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF]Sect. 2.3.4] follows as special case (Theorem 6.1). In contrast to the previously known bounds, our results are non-trivial also for "round" cones, i.e., cones with a smooth boundary. The bound is a function of the projective cross-ratio of geometric objects that are constructed from n boundary points of the cone in general position and an interior point. As an application, we compute lower bounds on the barrier parameter for the epigraph of the || • || ∞ -norm (Corollary 6.2), the power cone (Corollary 7.1), and the epigraph of the

|| • || p -norm in R 2 (Corollary 7.2).
The remainder of the paper is structured as follows. In the next section we introduce the projective cross-ratio and consider some of its elementary properties. In Section 3 we prove an auxiliary result, which essentially applies to 2-dimensional cones. In Section 4 we deduce the lower bound on the barrier parameter of barriers on general cones and in the subsequent section we investigate its properties. In Section 6 we deduce the bounds in [4, Sect. 2.3.4] from our result, and in the last section we apply our results to the power cone and the epigraph of the || • || p -norm. Finally, in the appendix we construct an optimal barrier for the epigraph of the || • || ∞ -norm.

The projective cross-ratio

Let x 1 , x 2 , x 3 , x 4 ∈ R ∪ {∞} be four distinct points in the 1-point compactification of the real line. The projective cross-ratio of the quadruple (x 1 , x 2 , x 3 , x 4 ) is defined as the number

(x 1 , x 2 ; x 3 , x 4 ) = (x 1 -x 3 )(x 2 -x 4 ) (x 1 -x 4 )(x 2 -x 3 ) ∈ R,
where the differences containing the value ∞ are cancelled in the event that one of the points in the quadruple is ∞. This function can be extended continuously to a (R ∪ {∞})-valued function on the set of quadruples of points in R ∪ {∞} of which no three coincide. The projective cross-ratio is invariant under projective transformations of R ∪ {∞}, and can hence also be considered as a (R ∪ {∞})-valued function on quadruples of points on the real projective line RP1 . Alternatively, it can be considered as a (R∪{∞})-valued function on quadruples of 1-dimensional linear subspaces of R 2 , as the set of such subspaces is isomorphic to RP 1 .

As can be easily checked, the projective cross-ratio possesses the symmetry

(x 1 , x 2 ; x 3 , x 4 ) = 1 (x 2 , x 1 ; x 3 , x 4 ) , (4)
with the values 0 and ∞ being considered as reciprocal.

In the next two sections we consider the projective cross-ratio as defined on quadruples of coplanar lines through the origin, while in the example sections it will be more convenient to consider projective cross-ratios of quadruples of collinear points.

2-dimensional linear sections

In this section we prove an auxiliary result which essentially provides a construction of the optimal barrier on a 2-dimensional convex cone under the condition that the direction of the gradient of the barrier at some interior point of the cone is fixed to some value.

Let K ⊂ R n , n ≥ 2, be a regular convex cone, x * ∈ K o a point in the interior of K, l a line containing x * and intersecting the boundary ∂K of the cone in the points e, y. Denote by L the 2dimensional linear hull of l and by l x * , l e , l y the 1-dimensional linear subspaces spanned by the vectors x * , e, y, respectively. Let F : K o → R be a logarithmically homogeneous self-concordant barrier on K with barrier parameter ν, and define p * = -F ′ (x * ). Note that p * is a linear functional on R n , located in the interior of the dual cone K * . The kernel of p * is an n -1-dimensional linear subspace L p * ⊂ R n , which intersects K in the origin. Denote the 1-dimensional intersection of L p * with the 2-dimensional subspace L by l p * . Then l x * , l e , l y , l p * are four mutually distinct coplanar lines, and we can define their projective cross-ratio r = (l e , l y ; l x * , l p * ). The arrangement of the lines implies that -∞ < r < 0. Proof. Let K L = K ∩ L and let F L be the restriction of F on the interior K o L of K L . Then F L is a selfconcordant barrier for the 2-dimensional cone K L with the same barrier parameter ν as K. Moreover, the linear functional p * L = -F ′ L (x * ) is the restriction of the linear functional p * on L, and hence its kernel coincides with l p * . The assertion of the lemma for the cone K thus reduces to the assertion for the cone K L .

In order to avoid unnecessary notations, we shall assume without restriction of generality that n = 2

and hence K = K L . Let γ * = ν * -2 √ ν * -1 = |r+1| √ -r and let λ * ± = -γ * 2 ± γ 2 *
4 + 1 be the roots of the quadratic equation λ 2 + γ * λ -1 = 0. Then -rγ 2 * = (r + 1) 2 and hence r = -

γ 2 * +2 2 ± γ * γ 2 * 4 + 1 = -(λ * ∓ ) 2 . Since γ * ≥ 0, we have λ * -≤ -1 and 0 < λ * + ≤ 1. Therefore r = -(λ * -) 2 if r ≤ -1 and r = -(λ * + ) 2 if r ≥ -1.
Note that in the former case we have (l y , l e ; l x * , l p * ) = r -1 = -(λ * + ) 2 by (4). Let us now introduce a coordinate system in R 2 such that the lines l x * , l p * are parallel to the basis vectors (1, 0) T , (0, 1) T , respectively. Let further the lines l e , l y be parallel to the vectors (1, λ * ± ) T , respectively, if r ≥ -1, and to the vectors (1, λ * ∓ ) T , respectively, if r < -1. This is always possible because

(λ * + , λ * -; 0, ∞) = (λ * + -0)(λ * --∞) (λ * --0)(λ * + -∞) = λ * + λ * - = -(λ * + ) 2 = (l y , l e ; l x * , l p * ), r < -1; (l e , l y ; l x * , l p * ), r ≥ -1,
and the projective cross-ratio of a quadruple of distinct lines through the origin of a plane is the only invariant of the quadruple with respect to the general linear group of this plane. Let us further scale the coordinates by a homothety such that x * = (1, 0) T . In this coordinate system the cone K is given by the set {x = (

x 1 , x 2 ) T | x 1 ≥ 0, λ * -x 1 ≤ x 2 ≤ λ * + x 1 }, and p * = -F ′ (x * ) = (ν, 0) T due to the identity p * , x * = ν [4, eq. (2.3.13)].
Consider the 1-dimensional Lie group A(t) = exp(t • a) = 1 0 t 1 generated by the Lie algebra element a = 0 0 1 0 . Let x(t) = A(t)x * = (1, t) T and consider the scalar f (t) = ν -1 F (x(t)). We shall now establish a differential inequality which is satisfied by the function f (t). Formulas [4, eq.

(2.3.12-14)] and its derivatives yield the relations

F ′ (x)[x] = -ν, F ′′ (x)[x, •] = -F ′ (x), F ′′′ (x)[x, •, •] = -2F ′′ (x). At x(t) = A(t)
x * we thus have

F ′ = νA T (-t) -1 α , F ′′ = νA T (-t) 1 -α -α β A(-t), F ′′′ [A(t)h, •, •] = -2νA T (-t) 1 -α -α β h 1 + -α β β µ h 2 A(-t) (5)
for some α, β, µ ∈ R. Here β > α 2 , because F ′′ ≻ 0, and h = (h 1 , h 2 ) T ∈ R 2 is an arbitrary vector. Condition (1), applied to the vector A(t)h, then yields

-h 3 1 + 3αh 2 1 h 2 -3βh 1 h 2 2 -µh 3 2 ≤ √ ν(h 2 1 -2αh 1 h 2 + βh 2 2 ) 3/2 .
Setting h = (α -β-α 2 ν-1 , 1) T , we obtain after some calculations

-(α 3 + 3α(β -α 2 ) + µ) ≤ γ(β -α 2 ) 3/2 , (6)
where

γ = ν-2 √ ν-1 .
Let us compute the derivatives of f (t). By (5) and using the fact that ẋ = (0, 1) T is constant, we have

ḟ = ν -1 F ′ (x)[ax] = α, f = ν -1 F ′′ (x)[ax, ax] = β, f (3) = ν -1 F ′′′ (x)[ax, ax, ax] = -2µ.
Inserting this into (6), we get

4 ḟ 3 -6 ḟ f + f (3) ≤ 2γ( f -ḟ 2 ) 3/2 . ( 7
)
We would like to bound the function f (t) by the solution of the differential equation which is obtained when one assumes equality in (7). This is accomplished by introducing the variables

q ± = - √ f -ḟ 2 λ∓ -ḟ , where λ ± = -γ 2 ± γ 2
4 + 1 are the roots of the quadratic equation λ 2 + γλ -1 = 0. These variables satisfy the relation q + > q -and ḟ , f can be recovered from them by the formula

ḟ = - λ + λ + -λ - q -+ λ - λ + -λ - q + , f = λ + λ + -λ - q 2 -- λ - λ + -λ - q 2 + . (8)
We have fḟ 2 = (q+-q-) 2 γ 2 +4 , and hence ( f

-ḟ 2 ) 3/2 = (q+-q-) 3 (γ 2 +4) 3/2 . A simple calculus then shows that 2γ( f -ḟ 2 ) 3/2 -4 ḟ 3 + 6 ḟ f = -2λ+ λ+-λ-q 3 -+ 2λ- λ+-λ-q 3
+ and hence by ( 7)

f (3) ≤ - 2λ + λ + -λ - q 3 -+ 2λ - λ + -λ - q 3 + . (9)
Recall that p * = (ν, 0) T and hence ḟ (0) = 0. Hence by (8) we have

λ + q -(0) = λ -q + (0). ( 10
)
Differentiating the first relation in (8) with respect to t and expressing f by the second relation, we obtain

λ + λ + -λ - (q 2 -+ q-) - λ - λ + -λ - (q 2 + + q+ ) = 0. ( 11
)
Differentiating the second relation in ( 8) and inserting into (9) yields the inequality

λ + λ + -λ - q -(q 2 -+ q-) - λ - λ + -λ - q + (q 2 + + q+ ) ≤ 0. ( 12
)
Combining ( 11) with (12) yields

λ + λ + -λ - (q --q + )(q 2 -+ q-) ≤ 0, λ - λ + -λ - (q --q + )(q 2 + + q+ ) ≤ 0,
which by the relation q + > q -gives q 2 -+ q-≥ 0,

q 2 + + q+ ≤ 0. ( 13
)
The solution of the differential equation q 2 + q = 0 is given by q(t) = 1 t+q -1 (0) . The differential inequalities (13) then yield the bounds

q -(t) ≥ 1 t + q -1 -(0) , t ≥ 0; q + (t) ≥ 1 t + q -1 + (0) , t ≤ 0. ( 14
)
By (10) and the condition q + > q -we have q -(0) < 0 and q + (0) > 0. Note that lim t→λ * + f (t) = +∞, hence by convexity of f we have lim t→λ * + ḟ (t) = +∞ and lim t→λ * + q -(t) = -∞. The right-hand side in the first relation in ( 14) tends to -∞ for t → -q -1 -(0), and hence λ * + ≥ -q -1 -(0). Likewise, lim t→λ * -f (t) = +∞, hence lim t→λ * -ḟ (t) = -∞ and lim t→λ * -q + (t) = +∞. The right-hand side in the second relation in ( 14) tends to +∞ for t → -q -1 + (0), and hence λ * -≥ -q -1 + (0). We thus get

λ * + λ+ ≥ -1 λ+q-(0) , - λ * - λ-≥ 1 λ-q+(0)
. Combining with (10), this yields

λ * + λ+ ≥ λ * - λ-. Finally, inserting the values λ -= - √ ν -1, λ + = 1 √ ν-1 , λ * -= - √ ν * -1, λ * + = 1 √ ν * -1
, we arrive at the desired conclusion.

Corollary 3.2. Let K ⊂ R n , n ≥ 2, be a regular convex cone, and F : K o → R a logarithmically homogeneous self-concordant barrier on K with barrier parameter ν. Then ν ≥ 2.

If n = 2 and the bound on the barrier parameter given by Lemma 3.1 is saturated, then λ * + = λ + = -q -1 -(0) and λ * -= λ -= -q -1 + (0). Inequalities ( 14) must be saturated too and ḟ (t) = -λ+ λ+-λ- This group acts transitively on the set of rays constituting the interior of the cone K, and hence the expression ν * in Lemma 3.1 is independent of the choice of the interior point x * in this case.

1 t-λ+ + λ- λ+-λ- 1 t-λ-. This can be integrated, yielding f (t) = -λ+ λ+-λ-log(t -λ + ) + λ- λ+-λ-log(t -λ -) + const,

Main result

In this section a lower bound on the barrier parameter ν for a logarithmically homogeneous selfconcordant barrier F : K o → R on a given regular convex cone K ⊂ R n is obtained from Lemma 3.1 by the following consideration. Let x * ∈ K o be an interior point of K, denote p * = -F ′ (x * ), and let L 1 , . . . , L m be 2-dimensional linear subspaces containing x * . For fixed p * and for each i = 1, . . . , m, application of Lemma 3.1 to the intersection K Li = L i ∩ K gives rise to a lower bound ν * i (p * ) on ν, and hence ν ≥ max i=1,...,m ν * i (p * ). If m is smaller than the dimension n of the cone K, then for subspaces L 1 , . . . , L m in general position p * can be chosen such that max i=1,...,m ν * i (p * ) = 2, and no information is gained with respect to Corollary 3.2. If, however, m ≥ n, then min p * max i=1,...,m ν * i (p * ) > 2 in general, except in the case that K is the Lorentz cone. The goal of this section is to solve the minimax problem min p * max i=1,...,m ν * i (p * ) for the case m = n. We will work under the following assumption.

Assumption 4.1. Let K ⊂ R n be a regular convex cone, let x * = (x * 1 , . . . , x * n ) T ∈ K o , and let L 1 , . . . , L n ⊂ R n be 2-dimensional linear subspaces containing x * . Assume that there exist linearly independent vectors e i ∈ L i ∩ ∂K, i = 1, . . . , n, and let y i ∈ L i ∩ ∂K be such that L i = span{e i , y i }, i = 1, . . . , n. Let l k be the line through the points e k and y k , and let z k be the intersection point of l k with the (n -1)-dimensional linear subspace Lk spanned by all points e l , l = 1, . . . , n except e k . Let l e k , l y k , l z k , and l x * be the linear hulls of e k , y k , z k , and x * , respectively. Then for each k = 1, . . . , n the 4 lines l e k , l y k , l z k , l x * are in L k and hence coplanar, and no three of them are identical. Let q k = [l e k , l x * ; l y k , l z k ] be their projective cross-ratio. Now let F : K o → R be a logarithmically homogeneous self-concordant barrier with parameter ν, set p * = -F ′ (x * ), and let l p * k be the 1-dimensional intersection of the plane L k with the kernel of the linear functional p * . We shall express the projective cross-ratio r k = [l e k , l y k ; l x * , l p * k ], which determines the bound ν * k (p * ) from Lemma 3.1, in terms of the projective cross-ratios q k and the linear functional p * . Introduce a coordinate system in R n with basis vectors equal to e k . Let p * k be the elements of p * in these coordinates. Note that p * is in the interior of the dual cone K * , and hence p * , e k = p * k > 0 for all k = 1, . . . , n.

In each of the planes L k , consider the affine line lk through x * which is parallel to l e k . Introduce a real parameter λ on lk , putting the number λ in correspondence with the point x * + λe k . Then the intersection point of lk with l e k is the infinitely remote point and can be assigned the parameter λ = +∞. The intersection point of lk with l x * has parameter value λ = 0. The coordinate vector of the intersection point of lk with l z k has a zero at its k-th entry and thus has parameter value λ = -x * k . Let λ k be the parameter value corresponding to the intersection point of lk with l y k . Since the segment of lk corresponding to the parameter values λ ∈ [0, ∞) lies in the interior of K, we have λ k < 0. Finally, the intersection point of lk with l p * k is given by the equation p * , x * + λe k = 0, which yields the value λk = -p * ,x * p * k for the parameter of this intersection point. Note that λk < λ k , because p * has to be positive on y k . We then obtain the projective cross-ratios

q k = [l e k , l x * ; l y k , l z k ] = (∞ -λ k )(0 -(-x * k )) (∞ -(-x * k ))(0 -λ k ) = - x * k λ k , (15)
r k = [l e k , l y k ; l x * , l p * k ] = (∞ -0)(λ k -λk ) (∞ -λk )(λ k -0) = 1 - λk λ k = 1 + p * , x * p * k λ k , (16)
from which we get

r k + 1 r k -1 = 1 + 2p * k λ k p * , x * . ( 17
)
Lemma 4.2. The relation k : q k >0 q k > 1 holds.

Proof. Let I + = {k | q k > 0} and Q + = k∈I+ q k . If I + = ∅, then x * is in the nonpositive orthant by (15). Thus -x * is also in K as a linear combination of the basis vectors e k with nonnegative coefficients. This contradicts the regularity of K.

Hence I + = ∅. For every k, x * + λ k e k is a positive multiple of y k and hence equals a nonzero vector in ∂K. Consider the point s

= k∈I+ q k (x * + λ k e k ) = (Q + -1)x * + x * -k∈I+ x * k e k
, where the second relation comes from (15). As a linear combination of nonzero elements in K, with positive coefficients, the point s is also a nonzero vector in K. The vector x * -k∈I+ x * k e k has only nonpositive components and is hence in -K. It follows that (Q + -1)x * = sx * -k∈I+ x * k e k is a nonzero vector in K, which implies Q + > 1 and proves the lemma. By Lemma 3.1, the barrier parameter ν of the barrier F is bounded from below by the expression max k=1,...,n

2 1- r k +1 r k -1
. This bound still depends on the negative gradient p * of F at x * . A lower bound on the barrier parameter of an arbitrary logarithmically homogeneous self-concordant barrier on K is then given by

ν * = min p * max k 2 1 -r k +1 r k -1 = 2 1 -min p * max k r k +1 r k -1 , (18)
where p * is subject to the constraints p * , e k > 0, p * , y k > 0 for all k = 1, . . . , n. By (17) this transforms into

ν * = 2 1 -min p * max k 1 + 2p * k λ k p * ,x * , ( 19
)
where the components of p * have to satisfy the requirements p * k > 0 and

-p * ,x * p * k = λk < λ k . Equiva- lently, 0 < p * k p * ,x * < -1 λ k . Introduce variables α k = 1 + 2p * k λ k p * ,x * ∈ (-1, 1
). These variables have to satisfy the additional requirement

n k=1 α k -1 2λ k x * k = 1, which by (15) is equivalent to n k=1 1-α k 2 q k = 1.
We shall now solve the minimax problem min max

k |α k | α k ∈ (-1, 1), n k=1 1 -α k 2 q k = 1 . ( 20
)
Lemma 4.3. The value of problem (20) is given by

| k q k -2| k |q k | < 1.
Proof. First note that k |q k | ≥ k q k and hence k q k -2 < k |q k |. On the other hand, by Lemma ). It is easily checked that this value is attained by the solution α k = α * k = l q l -2 l |q l | sgn q k ∈ (-1, 1). On the other hand, every feasible vector α = (α 1 , . . . , α n ) T has to satisfy the constraint Inserting the optimal value of (20) into (19), we obtain the following theorem.

we have

k (q k + |q k |) > 2 and hence 2 -k q k < k |q k |. It follows that | k q k -2| k |q k | ∈ [0, 1
k α k q k = k q k -2. It follows that (max k |α k |) k |q k | ≥ k |α k ||q k | ≥ | k q k -2|, which yields max k |α k | ≥ | k q k -2|
Theorem 4.4. Under Assumption 4.1, the barrier parameter ν of any logarithmically homogeneous self-concordant barrier F on the cone K is bounded from below by the quantity

ν * = 2 1 - | k q k -2| k |q k |
.

Properties of the lower bound

In this section we will consider the bound given by Theorem 4.4 in more detail. Proof. The exchange of y k and e k leaves the subspace L k and the line l p * k invariant and hence by (4) leads to the transformation r k → r -1 k in (16). This in turn leads to the transformation r k +1 r k -1 → -r k +1 r k -1 . The set of constraints p * , e k > 0, p * , y k > 0 is also left invariant, and hence by (18) the value of ν * is left unchanged.

Remark 5.2. The assertion of Lemma 5.1 cannot be easily inferred directly from the explicit expression of the bound ν * in Theorem 4.4, because the exchange of e k and y k for one index k changes the lines l z l for all l = k and hence all projective cross-ratios q l in (15) are changed.

Lemma 5.3. Assume the conditions of Assumption 4.1. There exists a subset I ⊂ {1, . . . , n} of indices with complement Ī such that the set {e k | k ∈ Ī} ∪ {y k | k ∈ I} is linearly independent, and x * is a linear combination of the vectors in this set with nonnegative coefficients.

Proof. The assertion of the lemma will follow from the statement that we can render all entries of x * nonnegative by exchanging the vectors e k and y k for a number of indices k and adapting the coordinate system accordingly. Let us prove this statement.

Suppose there exists an index k such that x * k < 0. Recall that z k is the unique point on l k situated in the linear subspace Lk spanned by all e l except e k . Therefore, linear dependence of the vectors e 1 , . . . , e k-1 , y k , e k+1 , . . . , e n is equivalent to the relation z k = y k . Since x * k < 0, the line l x * intersects l k in a point opposite to e k with respect to z k . But y k is opposite to e k with respect to l x * in L k , hence z k = y k . This proves that we can exchange the roles of e k and y k without violating the condition of linear independence of the points e l .

Assume without restriction of generality that x * is situated on the line segment between e k and y k . This is equivalent to multiplication of x * by a positive constant and does not change the signs of the entries x * k . We have the explicit expression

z k = x * -x * k e k 1-x * k
, deriving from the condition that z k is the affine combination of e k and x * whose k-th entry vanishes. On the other hand, we have

y k = x * +λ k e k
1+λ k , deriving from the condition that y k is the affine combination of e k and x * which is a multiple of x * + λ k e k . It follows that

x * = x * k (1 + λ k ) λ k + x * k y k + λ k (1 -x * k ) λ k + x * k z k = x * k (1 + λ k ) λ k + x * k y k + λ k λ k + x * k (x * -x * k e k ). (21)
Note that x *x * k e k is a linear combination of the points e 1 , . . . , e k-1 , e k+1 , . . . , e n , with coefficients being equal to the corresponding entries of x * . From (21) it then follows that the coefficients x * l of x * , when expressed as a linear combination of the vectors e 1 , . . . , e k-1 , y k , e k+1 , . . . , e n , are given by

x * k = x * k (1 + λ k ) λ k + x * k , x * l = λ k λ k + x * k x * l , l = k.
Since x * is situated between y k and z k on the line l k and is different from these points, we have by ( 21) that

x * k (1+λ k ) λ k +x * k > 0, λ k (1-x * k ) λ k +x * k > 0,
ν * = k q k k q k -1 , k q k ≤ 2; k q k , k q k ≥ 2. ( 22
)
Proof. Choose a coordinate system in R n with basis vectors e k , k = 1, . . . , n. Then by assumption of the theorem all entries of x * are nonnegative, and by (15) all projective cross-ratios q k are nonnegative. Then the bound in Theorem 4.4 simplifies to (22).

We now consider the situation when q k = 0 for some k. In this case x * = z k is contained in the (n -1)-dimensional linear subspace Lk ⊂ R n spanned by all e l except e k . For every l = k, since both e l , x * are in Lk , we also have y l ∈ Lk . We can then apply the construction of the previous section to the n -1 2-dimensional subspaces L 1 , . . . , L k-1 , L k+1 , . . . , L n of the n -1-dimensional cone K = K ∩ Lk . Since all q l , l = k, retain their values in the lower-dimensional space, and n l=1 q l = l =k q l , n l=1 |q l | = l =k |q l | by q k = 0, Theorem 4.4 will yield the same bound ν * for the cone K as it has for the cone K. In other words, in the case q k = 0 the bound given by Theorem 4.4 for the cone K is essentially a consequence of a similar bound for the cone K, which is a linear section of K with codimension 1.

Lemma 5.5. Assume the conditions of Theorem 5.4. Then for all k = 1, . . . , n we have q k ≤ 1, and for all index sets I ⊂ {1, . . . , n} of cardinality n -1 we have k∈I q k ≥ 1.

Proof. Assume the notations of the previous section. Since the simplicial cone K S generated by the vectors e k is contained in K, the interval I S = l k ∩ K S is contained in the interval I K = l k ∩ K for every k = 1, . . . , n. Note that y k is the endpoint of I K opposite to e k , while z k is the endpoint of I S opposite to e k . Hence y k is situated on l k opposite to e k with respect to z k (but it may coincide with z k ). Recall that the parameter of the intersection point of l e k with lk was λ = +∞, the intersection point of l z k with lk had parameter λ = -x * k , and the intersection point of l y k with lk had parameter λ = λ k . Therefore λ k ≤ -x * k , which by (15) yields q k ≤ 1. Let us prove the second part by contradiction. Suppose there exists a subset I ⊂ {1, . . . , n} of n -1 indices such that k∈I q k < 1. For l ∈ I, define a l = q l 1-k∈I q k ≥ 0. We then have

x * + l∈I a l (1 + λ l )y l = x * + l∈I q l 1 -k∈I q k (x * + λ l e l ) = 1 1 -k∈I q k x * - l∈I x * l e l ,
where for the second equality we used (15). The leftmost side is the sum of an interior point of K and boundary points of K and is hence also an interior point of K. On the other hand, the rightmost side is proportional to e k, where k is the index missing in I, and is hence a boundary point of K. This leads to a contradiction, thus proving the lemma.

Corollary 5.6. Assume the conditions of Theorem 5.4. Then the bound given in Theorem 4.4 satisfies ν * ≤ n. The equality ν * = n holds if and only if K is either a simplicial cone with generators e 1 , . . . , e n , or a simplicial cone with generators y 1 , . . . , y n .

Proof. By (22) the first assertion of the corollary is equivalent to the inequalities

n n -1 ≤ k q k ≤ n.
These can be obtained by summing the inequalities q k ≤ 1, k∈I q k ≥ 1 from Lemma 5.5 over all indices k or all index sets I of cardinality n -1, respectively. Assume now that ν * = n. By (22) we then have either k q k = n n-1 or k q k = n. Let us consider the first case. By Lemma 5.5 we have q k = 1 n-1 for all k, and hence

λ k = -(n-1)x * k . Note that y k is a positive multiple of the point x * + λ k e k , hence y k = β k (x * -(n -1)x * k e k ), β k > 0 for all k. Let k ∈ {1, . . . , n} and I = {1, . . . , n} \ { k}. Then we have k∈I β -1 k y k = k∈I (x * -(n -1)x * k e k ) = (n -1)x * ke k,
and e k is contained in the relative interior of the convex cone generated by the set {y k | k ∈ I}. But e k ∈ ∂K, which implies that this cone is entirely contained in ∂K. Repeating this argument for all k, we see that the boundary of the simplicial cone generated by the y k is contained in ∂K. On the other hand,

n k=1 β -1 k y k = n k=1 (x * -(n -1)x * k e k ) = x * ∈ K o ,
which implies that the points y k are linearly independent and that K equals the cone generated by the y k .

We now pass to the case k q k = n. By Lemma 5.5 we have q k = 1 for all k. This is equivalent to the relations y k = z k , and y k is contained in the cone generated by the set {e l | l = k} for all k. Moreover, it follows that z k ∈ ∂K and hence z k = x * , which implies x * k > 0 for all k. By λ k = -x * k we then have that y k is a positive multiple of x *x * k e k = l =k x * l e l , and y k is in the relative interior of the cone generated by the set {e l | l = k}. As in the previous paragraph, this whole cone must then be in ∂K for all k, and ∂K contains the boundary of the simplicial cone generated by the e k . Thus K equals this simplicial cone. This proves one direction of the equivalence asserted in the second part of the corollary.

Let us prove the opposite direction. Assume that K is a simplicial cone generated by either the vectors e k or the vectors y k . By possibly exchanging the roles of e k and y k for all k, we by virtue of Lemma 5.1 can assume that K is generated by the e k . The line l k intersects ∂K in e k and in the face opposite to e k , which implies that the second intersection point y k coincides with z k . But then λ k = -x * k and q k = 1 for all k, which by (22) yields the assertion to be proven. Theorem 5.7. Assume the conditions of Assumption 4.1. The lower bound ν * given in Theorem 4.4 cannot exceed the dimension n of the cone K. The equality ν * = n holds if and only if K is a simplicial cone with generators ẽ1 , . . . , ẽn such that ẽk ∈ {e k , y k } for every k = 1, . . . , n.

Proof. The theorem is a consequence of Lemmas 5.1, 5.3, and Corollary 5.6.

Relation with Nesterovs and Nemirovskis bound

In this section we deduce the lower bound of Nesterov and Nemirovski, applied to convex cones, from our result. Proposition 2.3.6 in [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF] states that if C ⊂ R n is a convex polytope and e n ∈ ∂C is a boundary point belonging to exactly k (n -1)-dimensional faces of C, such that the normal vectors to these faces are linearly independent, then k is a lower bound on the barrier parameter of any selfconcordant barrier on C. We are interested in the situation when C is a cone and prove the following slightly stronger result for this case. Theorem 6.1. Let K ⊂ R n , n ≥ 3, be a regular polyhedral convex cone, let e k+1 ∈ ∂K be a nonzero boundary point belonging to exactly k (n -1)-dimensional faces of K, 2 ≤ k ≤ n -1, such that the normals to these faces are linearly independent. Then ν * = k + 1 is a lower bound on the barrier parameter of any logarithmically homogeneous self-concordant barrier on K.

Proof. By an appropriate choice of coordinates, we can assume that e k+1 = (1, 0, . . . , 0) T , the set {x = (x 0 , . . . , x n-1 ) T ∈ K | x 0 = 1} is a compact section of K, and there exists a neighbourhood U of e k+1 such that x ∈ U ∩ K if and only if x ∈ U and x j ≤ 0, j = 1, . . . , k. Let us further assume without restriction of generality that k = n -1, otherwise we replace the cone K by the (k + 1)-dimensional intersection K ∩L, where L ⊂ R n is the (k+1)-dimensional linear subspace determined by the equations

x k+1 = • • • = x n-1 = 0.
Set x * = (1, -ε, . . . , -ε) T , e j = (1, -ε, . . . , -ε, 0, -ε, . . . , -ε) T , j = 1, . . . , n -1, where the zero is located at position j. For small enough ε > 0 we then have x * ∈ K o , e j ∈ ∂K, j = 1, . . . , n. Let further l j be the line through x * and e j and let y j be the intersection point of l j with ∂K opposite to e j , j = 1, . . . , n. We then have y j = (1, -ε, . . . , -ε, -α j , -ε, . . . , -ε) T for j = 1, . . . , n -1, y n = (1, -α n , . . . , -α n ) T , and lim ε→0 α j > 0 for all j = 1, . . . , n. For i ∈ {1, . . . , n}, denote by Li ⊂ R n the (n -1)-dimensional linear subspace spanned by all e j except e i , and let z i be the intersection point of Li with the line l i . It is not hard to check that z

i = (1, -ε, . . . , -ε, -β i , -ε, . . . , -ε) T , i = 1, . . . , n-1, z n = (1, -β n , . . . , -β n ) T with β i = ε n-2 n-3 , i = 1, . . . , n -1, and β n = ε n-2 n-1 .
For n = 3 the line l i does not intersect L i , i = 1, 2, and we set β 1 = β 2 = ∞ in this case.

The projective cross-ratios (15) are then given by

q j = [0, -ε; -α j , -ε n -2 n -3 ] = α j (n -2)(α j -ε) , j = 1, . . . , n -1; q n = [0, -ε; -α n , -ε n -2 n -1 ] = -α n (n -2)(α n -ε) .
Theorem 4.4 then yields the lower bound

ν * = 2 1 - |( n-1 j=1 α j α j -ε )-αn αn -ε -2(n-2)| n j=1 α j α j -ε
on the barrier parameter of any logarithmically homogeneous self-concordant barrier on K. The relation lim ε→0 ν * = n completes the proof.

Corollary 6.2. Let n ≥ 3. The epigraph of the || • || ∞ -norm in R n-1 , K n,∞ = {(x 0 , . . . , x n-1 ) T | x 0 ≥ |x k | ∀ k = 1, . . . , n -1} ⊂ R n , (23)
cannot have a logarithmically homogeneous self-concordant barrier with barrier parameter less than ν * = n. An optimal barrier for the cone K n,∞ is given by

F (x 0 , . . . , x n-1 ) = - n-1 k=1 log(x 2 0 -x 2 k ) + (n -2) log x 0 . (24)
For a proof see the appendix. Note that since every convex quadrangle is projectively equivalent to a square, the barrier (24) for n = 3 yields an optimal barrier also for an arbitrary regular polyhedral cone K ⊂ R 3 which is generated by 4 extreme rays.

7 Further examples

Power cone

The power cone is a 3-dimensional regular convex cone defined by

K p = {(u, v, w) T | u ≥ 0, v ≥ 0, u 1/p v 1/q ≥ |w|}, (25)
where p ∈ (2, ∞) is a parameter and 1 p + 1 q = 1. In [START_REF] Nesterov | Towards nonsymmetric conic optimization[END_REF] Nesterov proposed a logarithmically homogeneous self-concordant barrier with barrier parameter ν = 4 for this cone. In [START_REF] Chares | Cones and Interior-Point Algorithms for Structured Convex Optimization involving Powers and Exponentials[END_REF] a logarithmically homogeneous For p = 2, K 3,p is the 3-dimensional Lorentz cone, whose optimal barrier parameter is 2. For p = 1 and p = ∞ K 3,p is a polyhedral cone with 4 extreme rays. This case was considered in the previous section, where it was established that the optimal barrier parameter equals 3.

Let us consider the case 2 < p < ∞. Let γ ∈ (0, 1) be the unique solution of the equation (1 -2 p )γ 1-1/p + (1 -1 p )γ 1-2/p -1 p = 0. Note that this definition coincides with (26). For δ ∈ (0, 1), set

ρ 2 = 1 -δ, ρ 3 = 1 -γδ, w 2 = (1 -ρ p 2 ) 1/p , w 3 = (1 -ρ p 3 ) 1/p . (31)
Consider the compact section D = {(ρ, w) T | (1, ρ, w) T ∈ K 3,p } of the cone K 3,p and let e 1 , e 2 , e 3 ∈ ∂D, x * ∈ D o be as in the previous subsection. Then the projective cross-ratios q k will be given by the same formulas (27), and

q 1 + q 2 + q 3 = 2 + w 2 2 (1 -ρ 2 3 ) -w 2 3 (1 -ρ 2 2 ) w 3 (1 -ρ 2 )(w 3 (1 + ρ 2 ) + w 2 (1 + ρ 3 )) . ( 32
)
Now note that 1-x 2 (1-x p ) 2/p is a strictly monotonely decreasing function for x ∈ (0, 1), hence and q 1 + q 2 + q 3 < 2. By (22) we then get the lower bound ν * = q 1 + q 2 + q 3 q 1 + q 2 + q 3 -1 = 2 + w

and therefore lim δ→0 ν * = 2 + γ 2/pγ γ 1/p + γ = 2 + γ 1/pγ 1-1/p 1 + γ 1-1/p , which, remarkably, coincides with (29).

Let us now consider the case 1 < p < 2. Let γ ∈ (0, 1) be the unique solution of the equation ( 2p -1)γ 1/p + 1 p γ 2/p-1 -(1 -1 p ) = 0. For δ ∈ (0, 1), define ρ 2 , ρ 3 , w 2 , w 3 by (31) and let e 1 , e 2 , e 3 ∈ ∂D, x * ∈ D o be again as in the previous subsection. Then we again obtain (32), but 1-x 2

(1-x p ) 2/p is now a strictly monotonely increasing function for x ∈ (0, 1). Hence and q 1 + q 2 + q 3 > 2. By (22) we then get the lower bound ν * = q 1 + q 2 + q 3 = 2 + (w 2 /w 3 ) 2 (2γδ)γ -(2δ) (2δ) + w 2 /w 3 (2γδ) .

As in (33) we get lim δ→0 w2 w3 = γ -1/p , which yields lim δ→0 ν * = 2 + γ 1-2/p -1 1 + γ -1/p = 2 + γ 1-1/pγ 1/p 1 + γ 1/p .

Note that this again coincides with (29), but with p and q interchanged. Combining these results, we get the following lower bound. ) ∈ [0, 1 2 ] and let γ ∈ [0, 1) be a solution of the equation (1 -2c)γ 1-c + (1c)γ 1-2cc = 0. If F is a logarithmically homogeneous self-concordant barrier on K 3,p , then its barrier parameter satisfies the inequality ν ≥ 1 + 1+γ c 1+γ 1-c . As already noted, as functions of p the lower bounds given in Corollaries 7.1 and 7.2 coincide.

Remark 7.3. The choices of the points e k and x * in Subsections 7.1 and 7.2 are optimal, i.e., the bounds in Corollaries 7.1 and 7.2 are the best possible which can be obtained with our method.

Lemma 3 . 1 .

 31 Assume above notations. Then ν is bounded from below by ν * = r, -r -1 ).

  thus determining the barrier F up to an additive constant. It is not hard to check that F is invariant under the action of the Lie group exp(t • a) generated by the Lie algebra element a = 0 1 1 -γ .

k

  |q k | and thus proves optimality of the solution α k = α * k .

Lemma 5. 1 .

 1 Assume the conditions of Assumption 4.1. Let I ⊂ {1, . . . , n} be such that the vectors in the set {y k | k ∈ I} ∪ {e k | k ∈ I} are linearly independent. Then the bound in Theorem 4.4 is invariant under an interchange of the points e k and y k for all k ∈ I.

  and hence also λ k λ k +x * k > 0. Therefore the sign of x * l equals that of x * l for l = k, while x * k is positive. As a consequence, exchanging e k and y k has lead to a decrease in the number of negative entries of x * by one. Repeating this process, we can eliminate all negative entries of x * .Theorem 5.4. In addition to Assumption 4.1, suppose that x * is contained in the simplicial cone generated by the vectors e k . Then the lower bound in Theorem 4.4 is given by

Figure 1 :

 1 Figure 1: Barrier parameters of barriers for the power cone and lower bound

2 3 ( 1 -ρ 2 2 ) -w 2 2 ( 1 -ρ 2 3 ) 1 -

 3122131 w 2 (1 + ρ 3 )[w 3 (1ρ 2 ) + w 2 (1ρ 3 )] = 2 + (w 3 /w 2 ) 2 (2δ)γ(2γδ) (2γδ)(w 3 /w 2 + γ) . (1γδ) p 1 -(1δ) p 1/p = lim δ→0 γ(1γδ) p-1 (1δ) p-1 1/p = γ 1/p ,

Corollary 7. 2 .

 2 Let K 3,p ⊂ R 3 be the epigraph of the || • || p -norm given by (30) with parameter p ∈ [1, ∞]. Set c = min( 1 p , 1 -1 p

Actually, in[START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF] Prop.

2.3.6] it is required that K is polyhedral, but this is not used in the proof.

As noted by an anonymous referee, expression (29) can be rewritten as 2 + (1 -q/p)γ 1/p .

self-concordant barrier with barrier parameter ν = 3 was proposed and a logarithmically homogeneous function with homogeneity parameter ν = 3 -2 p was conjectured to be self-concordant. We shall now give a lower bound on the barrier parameter of any logarithmically homogeneous self-concordant barrier on K p .

Consider the compact section D = {(u, v, w)

, we can parameterize D by (ρ, w) T . Inserting the relations u = 1+ρ 2 , v = 1-ρ 2 into the inequality defining the cone K p , we see that D is given by the set {(ρ, w)

Let now γ > 0 be the unique positive root of the transcendent equation

Choose ρ 2 , ρ 3 ∈ (-1, 1) such that ρ 2 < ρ 3 and γ = (1-ρ3)(1+ρ2) (1+ρ3)(1-ρ2) . Then ρ 3 can be expressed as a function of ρ 2 by ρ 3 = 1+ρ2-γ (1-ρ2) 1+ρ2+γ(1-ρ2) . Define further

All these 6 points are located on the boundary of D, and the lines l k through e k , y k , k = 1, 2, 3, intersect in the common point x * = ( ρ2w3+ρ3w2 w2+w3 , 0) T , which lies in the interior of the triangle formed by the e k . The line l 1 intersects the line through e 2 , e 3 in the point z 1 = (ρ 2 , 0) T , while l 3 intersects the line through e 1 , e 2 in the point

) .

From this we readily compute the projective cross-ratios

and hence

By (22) we then obtain

Corollary 7.1. Let K p ⊂ R 3 be the power cone given by (25) with parameter p ≥ (2, +∞). If F is a logarithmically homogeneous self-concordant barrier on K p , then its barrier parameter satisfies the inequality ν ≥ 1 + 1+γ 1/p 1+γ 1/q , where γ is given by (26) and 1 p + 1 q = 1. In Fig. 1 the lower bound ν * as a function of p is depicted along with the barrier parameters of the barriers proposed in [START_REF] Nesterov | Towards nonsymmetric conic optimization[END_REF] and [1] 2 .

Epigraph of the || • || p norm

Next we consider the epigraph of the || • || p -norm in R 2 for 1 ≤ p ≤ ∞, i.e., the 3-dimensional cone

In [START_REF] Nesterov | Towards nonsymmetric conic optimization[END_REF] Nesterov proposed a method to construct a logarithmically homogeneous self-concordant barrier with barrier parameter ν = 2ν for this cone if a logarithmically homogeneous self-concordant barrier for the corresponding power cone K p is available which has barrier parameter ν. In [START_REF] Chares | Cones and Interior-Point Algorithms for Structured Convex Optimization involving Powers and Exponentials[END_REF] the universal barrier [4, Sect. 2.5] for K 3,p was computed and a barrier parameter ν = 3p p+1 (p ≥ 2) for this barrier

A Self-concordance of function (24)

In this section it is proven that the function F given by ( 24) is a self-concordant barrier for the cone K n,∞ defined in (23). The proof is due to an anonymous reviewer. It replaces the much more complicated proof from the first version of the paper.

Consider the positive orthant R n-1 + with its optimal barrier F R n-1 + (y) = -n-1 k=1 log y k . As a homogeneous cone, it has rank n -1. From this cone we construct [START_REF] Güler | Characterization of the barrier parameter of homogeneous convex cones[END_REF]Sect. 3] (see also [4, pp. 165-166]) a homogeneous cone of rank n and dimension 2n -1,

where B : R n-1 → R n-1 + is a symmetric vector-valued bilinear form given by B(x) = (x 2 1 , . . . , x 2 n-1 ) T . An optimal barrier for the cone SC(R n-1 + , B) with barrier parameter n is given by [2, Theorem 4.1]

Now the intersection of the cone SC(R n-1 + , B) with the linear subspace given by x 0 = y 1 = • • • = y n-1 is isomorphic to the cone K n,∞ , and the restriction of the barrier F SC(R n-1 + ,B) to this intersection induces the function F on K n,∞ . This proves that F is actually a self-concordant barrier.