Reşat Oguz

Sinan Sipahi

Tuna Mermer

Aslihan Candevir Demirdal

Pierre Ulu

Selin Bardak Fillâtre

Şafak Ozcem

Alper Kaya

Cemal Şener

Recep Bulut

Tekin

Sipahi

Sinan Mermer

Tuna Demirdal

Aslıhan Candevir Ulu

Pierre Fillatre

Selin Bardak Ozcem

Şafak Kaya

Alper Şener

Cemal Bulut

Recep Tekin

Hasip Kahraman
email: hasipkahraman@gmail.com

Erkin Özgiray

Taşkın Yurtseven

Hilal Sipahi

Bilgin Arda

Hüsnü Pullukçu

Meltem Taşbakan

Tansu Yamazhan

Sohret Aydemir

Sercan Ulusoy

Tigecycline in the treatment of multidrug-resistant Acinetobacter baumannii meningitis Results of the Ege study

Keywords: Acinetobacter baumannii, meningitis, glycylcycline, multidrug resistant bacteria, carbapenemresistant

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

strains were carbapenem-resistant and susceptible to tigecycline. Six cases received tigecycline monotherapy while 17 received tigecycline including combination therapy (10 with colistin, 4 with netilmicin, 3 with amikacin, 4 with meropenem). Seven of 23 cases (30%) died during the tigecycline including therapy (1 in monotherapy, 4 in colistin, 2 in netilmicin, 1 amikacin, one case received tigecycline+netilmicin followed by tigecycline+colistin). Hence, overall end of treatment (EOT) success was 70%. However, since further 27% died due to additional nosocomial infections, overall clinical success (relieved symptoms at the EOT and one-month post-therapy survival without any relapse or reinfection) decreased to 43%.

A C C E P T E D M

A N U S C R I P T

Introduction

In spite of developments in neurosurgery, antimicrobial agents, medicine and intensive care, meningitis, as well as nosocomial or healthcare-associated meningitis (HCAM), are still associated with significant mortality and morbidity [START_REF] Bardak-Ozcem | An updated approach to healthcare-associated meningitis[END_REF][START_REF] Van De Beek | Nosocomial bacterial meningitis[END_REF][START_REF] Sipahi | Pooled analysis of 899 nosocomial meningitis episodes from Turkey[END_REF][START_REF] Sipahi | Economics of antibiotic resistance[END_REF][START_REF] Tasbakan | Is tigecycline a good choice in the treatment of multidrug-resistant Acinetobacter baumannii pneumonia?[END_REF][START_REF] Wadi | Multidrug resistant Acinetobacter nosocomial meningitis treated successfully with parenteral tigecycline[END_REF][START_REF] Tutuncu | Tigecycline use in two cases with multidrug-resistant Acinetobacter baumannii meningitis[END_REF][START_REF] Kim | Comparable Efficacy of Tigecycline versus Colistin Therapy for Multidrug-Resistant and Extensively Drug-Resistant Acinetobacter baumannii Pneumonia in Critically Ill Patients[END_REF][START_REF] Chuang | Effectiveness of tigecycline-based versus colistin-based therapy for treatment of pneumonia caused by multidrug-resistant Acinetobacter baumannii in a critical setting: a matched cohort analysis[END_REF][START_REF] Sipahi | Tigecycline in the management of post-neurosurgical spondylodiscitis: a review of eight cases[END_REF][START_REF] Sipahi | Linezolid in the treatment of methicillin-resistant staphylococcal postneurosurgical meningitis: a series of 17 cases[END_REF]. Multidrug-resistant (MDR) as well as carbapenem-resistant Acinetobacter baumannii (CRAB) is an important global problem in any kind of nosocomial infection [START_REF] Sipahi | Economics of antibiotic resistance[END_REF][12][START_REF] Kim | Update on the Epidemiology, Treatment, and Outcomes of Carbapenem-resistant Acinetobacter infections[END_REF][START_REF] Buke | High dose of intrathecal netilmicin in the treatment of nosocomial Acinetobacter baumannii meningitis[END_REF][START_REF] Kim | Management of meningitis due to antibiotic-resistant Acinetobacter species[END_REF][START_REF] Kooli | Successful treatment of postoperative multidrug-resistant Acinetobacter baumannii meningitis by tigecycline[END_REF]. . Acinetobacter spp is also one of the most common bacterial agents in the etiology of HCAM and the most common one in Turkey [START_REF] Bardak-Ozcem | An updated approach to healthcare-associated meningitis[END_REF][START_REF] Sipahi | Pooled analysis of 899 nosocomial meningitis episodes from Turkey[END_REF].

Treatment options are limited and depend on the susceptibility pattern of the infecting isolate [START_REF] Bardak-Ozcem | An updated approach to healthcare-associated meningitis[END_REF]. Tigecycline is a glycylcycline antimicrobial agent, active in vitro against a variety of Gram-positive and Gram-negative organisms including CRAB [START_REF] Bardak-Ozcem | An updated approach to healthcare-associated meningitis[END_REF][START_REF] Sipahi | Economics of antibiotic resistance[END_REF][START_REF] Fang | Comparative efficacy of GAR-936, a novel glycylcycline, alone and in combination with vancomycin against highly penicillin-resistant Streptococcus pneumoniae experimental meningitis in rabbits[END_REF][START_REF] Yahav | Efficacy and safety of tigecycline: a systematic review and meta-analysis[END_REF][START_REF] Mcgovern | All-cause mortality imbalance in the tigecycline phase 3 and 4 clinical trials[END_REF]. The United States Food and Drug Administration (FDA) approved tigecycline for the treatment of complicated intra-abdominal infections, complicated skin and skin structure infections and community-acquired pneumonia. However, its off-label use in other CRAB infections such as nosocomial pneumonia, bacteremia or meningitis is common due to its pharmacological profile and bacterial spectrum [START_REF] Tasbakan | Is tigecycline a good choice in the treatment of multidrug-resistant Acinetobacter baumannii pneumonia?[END_REF][START_REF] Wadi | Multidrug resistant Acinetobacter nosocomial meningitis treated successfully with parenteral tigecycline[END_REF][START_REF] Tutuncu | Tigecycline use in two cases with multidrug-resistant Acinetobacter baumannii meningitis[END_REF][START_REF] Kim | Comparable Efficacy of Tigecycline versus Colistin Therapy for Multidrug-Resistant and Extensively Drug-Resistant Acinetobacter baumannii Pneumonia in Critically Ill Patients[END_REF][START_REF] Chuang | Effectiveness of tigecycline-based versus colistin-based therapy for treatment of pneumonia caused by multidrug-resistant Acinetobacter baumannii in a critical setting: a matched cohort analysis[END_REF][START_REF] Sipahi | Tigecycline in the management of post-neurosurgical spondylodiscitis: a review of eight cases[END_REF]. In this multicenter study, we retrospectively reviewed A. baumannii meningitis cases treated with tigecycline including regimens and evaluated the efficacy of tigecycline in the therapy.

The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

Materials and methods

This study was performed in seven tertiary-care educational hospitals from five cities of Turkey (Izmir, Ankara, Adana, Çanakkale, Diyarbakir) and one hospital from Rennes-France. We extracted data and outcomes of all adult (aged>18) patients with culture-proven A. baumannii meningitis treated with tigecycline including therapy between January 2007-April 2016. Demographic, clinical and laboratory findings, predisposing factors, as well as information on response to treatment and outcome were obtained retrospectively by the study site authors. Ege University Institutional Review Board approved the study.

A definite diagnosis of meningitis was based on the isolation of A. baumannii in at least one CSF culture.

Typical CSF findings included a leukocytosis with a predominance of polymorphonuclear cells (≥250 leukocytes/ml), and classical clinical manifestations of meningitis. Nosocomial meningitis was defined as bacterial infection not present when the patient was admitted to the hospital or clinical evidence of infection within a short period of time after discharge from the hospital where the patient had received an invasive procedure. Patients developing meningitis after neurosurgical procedures were defined as having postneurosurgical infection [START_REF] Sipahi | Linezolid in the treatment of methicillin-resistant staphylococcal postneurosurgical meningitis: a series of 17 cases[END_REF][START_REF] Garner | CDC definitions for nosocomial infections[END_REF]. Accordingly, all cases had nosocomial post neurosurgical meningitis. CSF samples were obtained by lumbar puncture or percutaneous aspiration of shunt reservoir or puncture of extra ventricular drainage tubing. Samples were routinely centrifuged and the pellet was Gram stained. Identification of A.baumannii and determination of antimicrobial susceptibility were performed using the VITEK 2 automated system (BioMerieux Inc, Mercy L'etoil, France) and conventional methods. For tigecycline susceptibility, the FDA clinical minimum inhibitory concentration (MIC) breakpoints for Enterobacteriaceae (2 mg/l-sensitive) were used. Other antibacterial susceptibility tests were evaluated according to Clinical Laboratory Standards Institute (CLSI) criteria until 2014 and EUCAST in 2015 and 2016 [START_REF]Performance Standards for Antimicrobial Susceptibility Testing: Twenty-third Informational Supplement M100-S23[END_REF][START_REF]European Committee on Antimicrobial Susceptibility Testing Breakpoint tables for interpretation of MICs and zone diameters. Version 6.0[END_REF].

Microbiological success was defined as clearance of A. baumannii in repeated CSF cultures on day 3-5 and/or at the end of tigecycline including treatment (EOT). EOT success was defined as relieved symptoms (which were present at the beginning) at the end of treatment accompanied by microbiological success. Overall success was defined as EOT success and one-month post-therapy survival without any relapse or reinfection.

Fisher exact test was used for comparison of major treatment groups.

A C C E P T E D

M A N U S C R I P T

Results

A total of 23 patients (15 male and eight female) fulfilled our inclusion criteria. All cases were in intensive care units at the beginning of the tigecycline including therapy. Gender, age, underlying diseases and other characteristics of the cases, are shown in table 1 and2.

Clinical presentation and diagnosis

Five cases had shunt infection (2/6 in tigecycline monotherapy group vs 3/17 in others, p:0.57), 12 were on lumbar drainage (6/6 in tigecycline monotherapy group vs 6/17 in others, p:0.013) whereas seven were on external ventricular drainage on the day of CRAB meningitis (0/6 in tigecycline monotherapy group vs 7/17 in others-p:0.12-lumbar drainage or external ventricular drainage 6/6 vs 13/17 p:0.53).

Twenty-one cases had disturbances in the level of consciousness (6/6 in tigecycline monotherapy group vs 15/17 in others, p:1) and 11 had neck stiffness (6/6 in tigecycline monotherapy group vs 5/17 in others, p:0.0048).

Nineteen cases had a fever (5/6 in tigecycline monotherapy group vs 14/17 in others, p:1). Six cases had convulsions (2/6 in tigecycline monotherapy group vs 4/17 in others, p:0.63) and twelve had nausea and vomiting (5/6 in tigecycline monotherapy group vs 7/17 in others, p:0.155) (Table 1).

Twenty patients had leukocytosis (>10.000/mm 3 ). Three cases did not have leukocytosis but had polymorphonuclear leukocyte predominance (Table 1). Glasgow coma scale results of all cases at the start of tigecycline including therapy are in table 2.

All cases had CSF pleocytosis (median 500/mm 3 , range 280-3450/mm 3, Table 1). Mean CSF protein level was 299 mg/dl (range 38-2055 mg/dl, table 1), Mean CSF glucose level was 41 mg/dl (range 1-60 mg/dl, table 1). All cases had culture-proven A. baumannii meningitis. Case 12 had mixed infection with E. faecium. All A. baumannii strains were carbapenem-resistant (only two intermediately-resistant). All strains were susceptible to tigecycline. Seventeen strains were susceptible to colistin while colistin susceptibility was unknown in six strains. Nine and three strains were susceptible to netilmicin and amikacin, respectively. Tigecycline MIC was available in two cases and was 0.5 mg/L in both.

Previous antibacterial treatment

When we evaluated the antibiotic therapy history of the cases during the one-month time period before the A. baumannii meningitis episode, all but five received at least one antibiotic (2/6 in tigecycline monotherapy group vs 16/17 in others, p:0.15). The most commonly used antibiotic was vancomycin (8 cases). Seven cases received

Tigecycline Including CRAB Meningitis treatment

Data related to the duration of treatment regimens are summarized in table 1. Tigecycline dosage was 50 mg q12h in all cases. Six cases received tigecycline monotherapy (Case 1-6), while 17 received tigecycline including combination therapy (10 with colistin, 4 with netilmicin, 3 with amikacin, 4 with meropenem-Table 2), Tigecycline level in cerebrospinal fluid or sera was not measured in any case.

Ten cases received tigecycline+colistin (Case 7-16). Of these ten, three received concomitant intrathecal colistin (case 9-13 and 15). In case 16 tigecycline and netilmicin (3 days intrathecal and 6 days intravenous) combination was started. Afterwards, netilmicin was switched to colistin due to microbiological failure. In case 11 colistin was switched to meropenem after nephrotoxicity on day 5. Case 14 received additional rifampin as third antibacterial agent. Case 12 received additional vancomycin also for E. faecium meningitis.

Four cases were given tigecycline and netilmicin combination (Case [START_REF] Kooli | Successful treatment of postoperative multidrug-resistant Acinetobacter baumannii meningitis by tigecycline[END_REF][START_REF] Fang | Comparative efficacy of GAR-936, a novel glycylcycline, alone and in combination with vancomycin against highly penicillin-resistant Streptococcus pneumoniae experimental meningitis in rabbits[END_REF][START_REF] Yahav | Efficacy and safety of tigecycline: a systematic review and meta-analysis[END_REF][START_REF] Mcgovern | All-cause mortality imbalance in the tigecycline phase 3 and 4 clinical trials[END_REF]. In case 16 tigecycline and netilmicin (3 days intrathecal and 6 days intravenous) combination was started. Afterwards, netilmicin was switched to colistin due to microbiological failure. In case 17 linezolid was also added to antibiotic therapy empirically. In case 18 tigecycline and netilmicin were started after failure with cefoperazone/sulbactam and meropenem. Case 19 received netilmicin for three days intrathecally and five days intravenously.

Three cases received tigecycline and amikacin including therapy (Case 20-21-22). Case 22 received amikacin only intrathecally in combination with meropenem and case 21 received additional rifampin as third antibacterial agent.

Finally, four cases (Case 11, 12, 22 and 23) were given tigecycline and meropenem including therapy. Case 11 received meropenem after colistin nephrotoxicity. Case 12 received additional colistin while case 22 received additional intrathecal amikacin. In case 11 and 22 the infecting srains were intermediately resistant to meropenem.Case 12 and 23 received meropenem despite the infecting strain was resistant to it.

Microbiological response on day 3-5

Repeated CSF culture on day 3-5 was available for 18 cases and overall efficacy was 72% (13/18, table 1). Among these 18 cases, microbiological efficacy on day 3-5 was evident in 5 of 5 cases in monotherapy group, 4

A C C E P T E D M A N U S C R I P T

End of therapy microbiological response

EOT microbiological efficacy data were available in 17 cases and overall efficacy was 88% (15/17).

Microbiological efficacy at the end of the treatment was evident in 5 of 5 in monotherapy group, 6 of 7 tigecyclin+colistin group, 1 of 3 tigecycline+netilmicin group, 2 of 3 tigecycline+amikacin group and 2/2 of cases who received tigecycline+meropenem combination.

Clinical success and mortality

Seven of 23 cases (30%) died during the tigecycline including therapy (1 in monotherapy, 4 in colistin, 2 in netilmicin, 1 amikacin, case 16 received tigecycline+netilmicin followed by tigecycline+colistin). Hence, EOT clinical success was 70%.

Among the remaining 16 cases, one had relapsing A. baumannii meningitis, one case had reinfection with P.aeruginosa, one case had reinfection with MRSA and three cases died due to nosocomial pneumonia during one-month follow-up. Hence. overall clinical success (relieved symptoms at the end of treatment and one-month post-therapy survival without any relapse or reinfection). was 43% (10/23). There was no difference in terms of EOT clinical success (5/6 vs 11/17, p: 0.62) and clinical success at the end of one-month follow-up (2/6 vs 8/17, p:1) in monotherapy vs any combination group. Glasgow coma scale at the EOT was 15 in two cases, 14 in four and 13 in one case. Others' EOT Glasgow coma score was 12 or less (table 2). When tigecycline monotherapy was compared with tigecycine+aminoglycoside combination or tigecycline+colistin there was no significant difference (p>0.05).

Tigecycline monotherapy (Case 1-6): The five cases with bacterial clearance in CSF had EOT clinical success.

However, three of them died due to nosocomial pneumonia during follow-up. The only case without EOT clinical success had died on day 5 of tigecycline possibly due to meningitis. Microbiological response, as well as clinical response at the end of therapy and after one-month follow-up, are summarized in table 2.

Adverse events

There was increase in creatinine levels in two cases who received tigecycline-colistin combination in one of whom colistin was switched to meropenem. Two cases had mild hepatotoxicity (x2 AST-ALT) levels which also did not result in change in antibiotic therapy. There was no severe hematological, nephrological or hepatological toxicity during the tigecycline treatment of other cases.

Discussion

Nosocomial Acinetobacter infections including meningitis are becoming an increasingly common problem in intensive care units. In a recent systematic review regarding HCAM in Turkey [START_REF] Sipahi | Pooled analysis of 899 nosocomial meningitis episodes from Turkey[END_REF], Acinetobacter spp. caused . Carbapenem resistance rate in Acinetobacter is reported to be over >50% in several countries including Italy, England, Saudi Arabia, China, India, Brazil and Argentina and United States [START_REF] Kim | Update on the Epidemiology, Treatment, and Outcomes of Carbapenem-resistant Acinetobacter infections[END_REF].

There are several options in the treatment of CRAB meningitis cases according to susceptibility pattern of the relevant strain such as colistin, sulbactam, aminoglycosides and tigecycline [START_REF] Bardak-Ozcem | An updated approach to healthcare-associated meningitis[END_REF][START_REF] Van De Beek | Nosocomial bacterial meningitis[END_REF][START_REF] Sipahi | Pooled analysis of 899 nosocomial meningitis episodes from Turkey[END_REF][START_REF] Buke | High dose of intrathecal netilmicin in the treatment of nosocomial Acinetobacter baumannii meningitis[END_REF][START_REF] Kim | Management of meningitis due to antibiotic-resistant Acinetobacter species[END_REF]. In the presented study all strains were susceptible to tigecycline. Data regarding tigecycline in meningitis or A. baumannii meningitis is rare [START_REF] Wadi | Multidrug resistant Acinetobacter nosocomial meningitis treated successfully with parenteral tigecycline[END_REF][START_REF] Tutuncu | Tigecycline use in two cases with multidrug-resistant Acinetobacter baumannii meningitis[END_REF][START_REF] Kooli | Successful treatment of postoperative multidrug-resistant Acinetobacter baumannii meningitis by tigecycline[END_REF][START_REF] Ray | Cerebral spinal fluid penetration of tigecycline in a patient with Acinetobacter baumannii cerebritis[END_REF][START_REF] Pallotto | Cerebrospinal fluid penetration of tigecycline[END_REF][START_REF] Lengerke | Low tigecycline concentrations in the cerebrospinal fluid of a neutropenicpatient with inflamed meninges[END_REF][START_REF] Lauretti | First reported case of intraventricular tigecycline for meningitis from extremely drug-resistant Acinetobacter baumanni[END_REF][START_REF] Wu | Intraventricular administration of tigecycline for the treatment of multidrug-resistant bacterial meningitis after craniotomy: a case report[END_REF][START_REF] Fang | A case report of intraventricular tigecycline therapy for intracranial infection with extremely drug resistant Acinetobacter baumannii[END_REF]. To our knowledge, there are a few reports in which tigecycline is used to treat A. baumannii meningitis. Wadi et al [START_REF] Wadi | Multidrug resistant Acinetobacter nosocomial meningitis treated successfully with parenteral tigecycline[END_REF] treated a case of A. baumannii meningitis with tigecycline monotherapy successfully. Tutuncu et al [START_REF] Tutuncu | Tigecycline use in two cases with multidrug-resistant Acinetobacter baumannii meningitis[END_REF] reported two cases of A. baumannii meningitis treated with tigecycline+netilmicin. Kooli et al reported successful treatment of an A. baumannii meningitis case with tigecycline and colistin combination [START_REF] Kooli | Successful treatment of postoperative multidrug-resistant Acinetobacter baumannii meningitis by tigecycline[END_REF]. Recently there have been cases reported to be treated with intrathecal tigecycline regimens [START_REF] Lauretti | First reported case of intraventricular tigecycline for meningitis from extremely drug-resistant Acinetobacter baumanni[END_REF][START_REF] Wu | Intraventricular administration of tigecycline for the treatment of multidrug-resistant bacterial meningitis after craniotomy: a case report[END_REF][START_REF] Fang | A case report of intraventricular tigecycline therapy for intracranial infection with extremely drug resistant Acinetobacter baumannii[END_REF]. Data related to animal models are also scarce about tigecycline. Wang et al compared tigecycline with tigecycline+vancomycin in Streptococcus pneumoniae meningitis of rabbits and reported that combination therapy was associated with greater clearance. However, the significance of the results obtained with the combination is limited by the absence of statistical analysis comparing the different arms [START_REF] Chuang | Effectiveness of tigecycline-based versus colistin-based therapy for treatment of pneumonia caused by multidrug-resistant Acinetobacter baumannii in a critical setting: a matched cohort analysis[END_REF][START_REF] Sipahi | Tigecycline in the management of post-neurosurgical spondylodiscitis: a review of eight cases[END_REF]. Fang et al [START_REF] Fang | Comparative efficacy of GAR-936, a novel glycylcycline, alone and in combination with vancomycin against highly penicillin-resistant Streptococcus pneumoniae experimental meningitis in rabbits[END_REF] analyzed the effects of tigecycline at different doses with or without vancomycin on penicillin-resistant S. pneumoniae induced meningitis model. In their study, when used at a concentration above 20 mg/kg, tigecycline was reported to be bactericidal and was at concentration above 1 mg/ml in CSF after three h of treatment. In case of A. baumannii meningitis, to our knowledge there is no animal study comparing tigecycline with any antibacterial agent.

Herein we presented 23 CRAB meningitis cases treated with tigecycline including regimens. Six cases received monotherapy. Several meta-analysis regarding tigecycline in randomized-controlled studies concluded excess mortality in tigecycline arm [START_REF] Yahav | Efficacy and safety of tigecycline: a systematic review and meta-analysis[END_REF][START_REF] Mcgovern | All-cause mortality imbalance in the tigecycline phase 3 and 4 clinical trials[END_REF]. Colistin entered Turkish market in 2011. Most cases but not all received Data regarding penetration of tigecycline into CSF is rare. Ray et al [START_REF] Ray | Cerebral spinal fluid penetration of tigecycline in a patient with Acinetobacter baumannii cerebritis[END_REF] reported a serial, steady-state, serum and CSF concentrations of tigecycline when administered in the Food and Drug Administration-approved dose of 50 mg every 12 hours. CSF concentrations remained relatively stable, suggesting that tigecycline did not accumulate in the CSF. Tigecycline concentrations in the CSF were between 0.035 and 0.048 mg/L, while corresponding serum concentrations were 0.097-0.566 mg/L. The calculated tigecycline penetration ratio in this patient ranged from 0% to 52%, depending on the calculation methodology utilized. In another case with shunt infection regarding penetration of tigecycline [START_REF] Pallotto | Cerebrospinal fluid penetration of tigecycline[END_REF], the deep concentration of tigecycline (before the following expected administration, t0) was 49 ng/ml in serum and 5.2 ng/ml in the CSF at steady-state. At 1 h after the end of the infusion, the drug serum concentration was 203 ng/ml and the CSF concentration was 13.4 ng/ml. The average ratio of CSF-to-serum concentration was 0.079 (0.059-0.106 interval). Lengerke et al [START_REF] Lengerke | Low tigecycline concentrations in the cerebrospinal fluid of a neutropenicpatient with inflamed meninges[END_REF] reported higher tigecycline level in inflamed CSF vs non-inflamed CSF and suggested that higher tigecycline levels may cause higher CSF levels. Interestingly, in recently published three case reports [START_REF] Lauretti | First reported case of intraventricular tigecycline for meningitis from extremely drug-resistant Acinetobacter baumanni[END_REF][START_REF] Wu | Intraventricular administration of tigecycline for the treatment of multidrug-resistant bacterial meningitis after craniotomy: a case report[END_REF][START_REF] Fang | A case report of intraventricular tigecycline therapy for intracranial infection with extremely drug resistant Acinetobacter baumannii[END_REF] tigecycline was administered by intraventricular route possibly because of the severity of these infections (2 A. baumannii and 1 K. pneumoniae meningtis/ventriculitis) and the limited treatments available. Wu et al also analysed the pharmacokinetics of tigecycline and measured tigecycline concentrations by liquid chromatography-mass spectrometry/mass spectrometry. The trough concentrations of tigecycline in CSF for the three different dosages of tigecycline IV-intra ventricular (ICV) combined administration were 0.313, 1.290 and 2.886 mg/L for 40mgIV/10mgICV, 45 mgIV/5 mg ICV and 50 mg IV /1 mg ICV tigecycline, respectively. In terms of outcome, in the case reported by Wu et al, [START_REF] Wu | Intraventricular administration of tigecycline for the treatment of multidrug-resistant bacterial meningitis after craniotomy: a case report[END_REF] clinical success but microbiological success is not mentioned, while Lauretti et al. [START_REF] Lauretti | First reported case of intraventricular tigecycline for meningitis from extremely drug-resistant Acinetobacter baumanni[END_REF] and Fang et al [START_REF] Fang | A case report of intraventricular tigecycline therapy for intracranial infection with extremely drug resistant Acinetobacter baumannii[END_REF] reported both clinical and microbiological success. In our series none of the cases received intrathecal or intravenous high dose tigecycline probably due to the fact that all strains were susceptible to tigecycline and/or reimbursement problems. Additionally since the presented study was on retrospective design, tigecycline levels could not be measured in any case.

Seven of 23 cases (30%) died during the tigecycline including therapy. Hence, overall EOT success was 70%.

However, since further 27% died due to other nosocomial infections, overall clinical success (relieved symptoms

A C C E P T E D M A N U S C R I P T
at the EOT and one-month post-therapy survival without any relapse or reinfection) decreased to 43%. Mortality was the least in monotherapy arm (17%) whereas it was 40% in cases who received tigecycline+colistin (p>0.05) and only three received intrathecal colistin (one of these three cases survived after one-month follow-up). In the systematic review by Falagas et al, [START_REF] Falagas | Intraventricular or intrathecal use of polymyxins in patients with Gram-negative meningitis: a systematic review of the available evidence[END_REF] which comprised 11 A. baumannii meningitis cases, treated with intrathecal colistin including therapy, intrathecal colistin was found to be successful in 10 cases. The difference between the outcomes of the studies may be due to the differences in the time lap between the A. baumannii oriented therapies or relatively low number of cases receiving intrathecal colistin which is reported to be associated with a better clinical response in some series [START_REF] Fotakopoulos | Outcomes in meningitis/ventriculitis treated with intravenous or intraventricular plus intravenous colistin[END_REF][START_REF] Khawcharoenporn | Intrathecal colistin for drug-resistant Acinetobacter baumannii central nervous system infection: a case series and systematic review[END_REF]. Another speculative reason may be the antibacterial effect of the antibiotic combination on the infecting strain. Combination therapy for CRAB infections is mostly recommended to cause synergy. However, the results of synergy tests are rarely known at the start of therapy. In fact, as in the presented study, it is usually not performed. In the real life scenario, a combination may be synergic in one strain whereas antagonistic in other [START_REF] March | A meta-analysis of in vitro antibiotic synergy against Acinetobacter baumannii[END_REF]. In the previously mentioned systematic review regarding nosocomial meningitis in Turkey, pathogen-specific mortality was reported to be 55.5% (30/54) for A. baumannii [START_REF] Sipahi | Pooled analysis of 899 nosocomial meningitis episodes from Turkey[END_REF]. Finally, overall one-month survival was 46% in another paper regarding tigecycline therapy in 72 Acinetobacter nosocomial pneumonia cases [START_REF] Tasbakan | Is tigecycline a good choice in the treatment of multidrug-resistant Acinetobacter baumannii pneumonia?[END_REF]. Hence, although EOT clinical success of 70% is comparable, one month survival without reinfection or relapse was a bit less than general A. baumannii meningitis outcomes (55.5%) and comparable to MDR A. baumannii pneumonia results in our setting.

Our study has several limitations. It was not a formal therapeutic trial but rather a retrospective review of cases treated with tigecycline including regimens. Besides, we did not make a sample size analysis for detecting the power of therapeutic efficacy comparison. We did not perform multiple logistic regression analysis for mortality since total number of cases was low and we did not have 10-20 events per covariate [START_REF] Stoltzfus | Logistic regression: a brief primer[END_REF]. The relatively low number of cases probably resulted in not to achieve statistical significance in other comparisons, too. There was no pharmacokinetic and pharmacodynamic data, as CSF/blood levels of tigecycline were not measured in any case. Besides, molecular genetic analysis of the infecting strains could not be performed since strains were not available. In addition, since autopsy could not be performed, definite reasons for mortality could not be delineated. Only six cases were treated with monotherapy. Some of the cases received additional intrathecal therapy. Hence, success or failure in 17 cases was not due to tigecycline alone but also the effects of combination and/or intrathecal therapy. However, as mentioned before, tigecycline was reported to be associated with excess

A C C E P T E D M A N U S C R I P T
mortality suggesting not to use it as monotherapy [START_REF] Yahav | Efficacy and safety of tigecycline: a systematic review and meta-analysis[END_REF][START_REF] Mcgovern | All-cause mortality imbalance in the tigecycline phase 3 and 4 clinical trials[END_REF]. Nevertheless, any study which would evaluate the efficacy of tigecycline in combination therapy regimens will have the same major disadvantage. The facts that most of the cases were from Turkey and there were mortality, relapse and reinfection after the end of successful CRAB meningitis therapy, suggest problems in infection control. Despite the above-mentioned limitations, to our knowledge, this is the largest series and dataset evaluating the microbiological and clinical efficacy of tigecycline in CRAB meningitis and comparing tigecycline monotherapy with combination therapy.

Conclusion

Our experience with tigecycline including therapy modalities resulted in an EOT success of 70% but since further 27% died due to other nosocomial infections, overall clinical success (relieved symptoms at the end of treatment and one-month post-therapy survival without any relapse or reinfection) decreased to 43%. These data suggest that similar to colistin [START_REF] Ceylan | Variables Determining Mortality in Patients With Acinetobacter baumannii Meningitis/Ventriculitis Treated With Intrathecal Colistin[END_REF], tigecycline can be an alternative in the salvage therapy of nosocomial CRAB meningitis. The medical community should seek easily implementable-very fastly resulting synergy testing methods in the contemporary age of antibiotic therapy, which includes only a few alternatives for CRAB.

In addition, the Turkish medical community should seek effective infection control measures regarding CRAB meningitis and other nosocomial infections. We recommend physicians treating any patient with tigecycline to determine actual CSF levels of the drug (whereever the measurement of tigecycline is abailable), along with CSF data which could allow them to correlate CSF levels with penetration across an inflamed blood-brain barrier and maintenance of levels as therapy progresses.

A C C E P T E D

M A N U S C R I P T A C C E P T E D M A N U S C R I P T A C C E P T E D M A N U S C R I P T Figures and table A C C E P T E D M A N U S C R I P T

  meropenem while five cases received cefazoline. Others are detailed in table 2. Eleven cases had received empirical (Case 10-13-14-15-16-17-18-19-20-21-22; 0/6 in tigecycline monotherapy group vs 11/17 in others, p:0.07) meningitis therapy before tigecycline including regimens.

of 8

 8 in tigecycline+colistin group, 1 of 3 in tigecycline+netilmicin group, 2 of 2 tigecycline+amikacin group and in 2/2 in cases received tigecycline+meropenem combination. There was no significant difference between the monotherapy vs any combination therapy (p:0.128).Tigecycline monotherapy (Case 1-6): Microbiological response data on day 3-5 were available for five cases all of whom had CSF clearance at both time points. Case 5 did not have repeated CSF culture and died on day 5 possibly due to meningitis. Tigecycline and colistin including therapy (Case 7-16): Eight of 10 cases had repeated CSF culture on day 3-5 and four had bacteriological eradication (Case 9, 10, 12, 14). Two cases (Case 7 and 11) did not have repeated CSF culture. However, case 7 had clinical response at the end of therapy and had one-month survival without any relapse. Case 11 died during therapy. Tigecycline and netilmicin including therapy (Case 16-19): Three of four cases had repeated CSF culture on day 3-5 and two (Case 17 and 18) had bacteriological eradication. Case 16 had bacteriologic failure with tigecycline and netilmicin combination and netilmicin was switched to colistin. Case 19 did not have repeated CSF culture but had clinical response at the end of therapy and had one-month survival without any relapse. Tigecycline and amikacin including therapy (Case 20-22): Two of three cases had repeated CSF culture on day 3-5 and one (Case 22) had bacteriological eradication. Case 21 did not have repeated CSF culture on day 3-5. Tigecycline and meropenem including therapy (Case 11, 12, 22 and 23): Case 11 did not have repeated CSF culture on day 3-5. Other cases had bacterial eradication on day 3-5.

  Tigecycline monotherapy (Case 1-6): Microbiological response data at the EOT were available for five cases all of whom had CSF clearance. The only case who had not microbiological response data died on day 5 of tigecycline monotherapy. Tigecycline and colistin including therapy (Case 7-16): Seven cases had EOT CSF culture and six had bacteriological eradication (Case 9, 10, 13, 14, 15, 16). The case with bacteriological failure (case 8) died.

  Among three cases without EOT CSF culture data one (Case 11) died during therapy whereas two had EOT as well as one-month survival without any relapse (Case 7 and 12). Tigecycline and netilmicin including therapy (Case 16-19): Only one case (Case 18) had EOT CSF culture and had bacteriological eradication. Case 17 had bacteriological cure on day 3-5 but died during treatment. Case 19 did not have EOT CSF culture but had EOT clinical response as well as one-month survival without any relapse. In case 16 was netilmicin was switched to colistin after failure. Tigecycline and amikacin including therapy (Case 20-22): Three cases had EOT CSF culture. Two (Case 20 and 22) had bacteriologic cure whereas one (Case 21) had developed P. aeruginosa meningitis during the tigecycline including therapy. Tigecycline and meropenem including therapy (Case 11, 12, 22 and 23): Case 22 and 23 had EOT CSF culture data and both had bacterial cure. Case 11 died during therapy whereas case 12 had EOT as well as one-month survival without any relapse or reinfection.

  Tigecycline and colistin including therapy (Case 7-16): Five cases had EOT clinical success and did not have relapse/reinfection during one-month follow-up (Case 7, 10, 12, 13, 14). In contrast, four cases died (two died possibly due to CRAB meningitis episode (Case 9 and 11), one nosocomial Providencia stuartii sepsis (Case 16) and one nosocomial meningitis and/or central catheter infection (Case 8). One case (Case 15) had EOT clinical response but had relapse on day 22 after treatment was retreated with tigecycline and colistin combination successfully and had no relapse during follow-up. Tigecycline and netilmicin including therapy (Case 16-19): Two cases (Case 18 and 19) had EOT clinical response. Case 19 had no relapse/reinfection during one-month follow-up. However, case 18 had reinfection with MRSA meningitis. Case 16 who was switched to tigecycline+colistin, died possibly due to P. stuartii sepsis (Case 16) and case 17 died secondary to meningitis episode. Tigecycline and amikacin including therapy (Case 20-22): Case 20 had EOT clinical success and no relapse/reinfection during one-month follow-up. Case 22 who received tigecycline, amikacin and meropenem combination during treatment died on day 26 possibly due to meningitis episode. Case 21 who received tigecycline, amikacin and rifampin combination had clearance of A. baumannii but developed P. aeruginosa meningitis on follow-up. Tigecycline and meropenem including therapy (Case 11, 12, 22 and 23): Case 12 and 23 had EOT clinical response and no relapse/reinfection during one-month follow-up. Although case 22 had bacterial clearance in CSF culture, he died probably due to nosocomial sepsis and possibly meningitis. Case 11 died during the treatment possibly due to meningitis.

  of cerebrospinal fluid culture positive 899 nosocomial meningitis episodes. Pooled carbapenem resistance rate was 37.5%. CRAB is endemic in many Turkish hospitals. According to pooled national nosocomial infection surveillance data, 50 percentile of the carbapenem-resistance rate of A. baumannii in tertiary-care university hospitals was 93.66% in 2014[12]

  colistin including combination. Hence, some of the cases were combined with non-colistin options whereas some others were treated with monotherapy.

Table 3 :

 3 Summary of microbiological rsponse as well as clinical response at the end of therapy and one month follow up data.

Table 1 :

 1 Clinical and laboratory findings at the start of tigecycline including therapy.

	Case N 1 2 3 4 5	Gender/Age F/39 M/48 M/74 F/53 M/79	Fever/Disturbences in level of consciousness/convulsions +/+/-+/+/-+/+/--/+/-+/+/+ M A N Nausea-vomiting/ neck stiffness +/+ +/+ +/+ -/+ +/+ U S C R I P CSF leukocyte/mm 3 300 500 280 280 460	CSF protein (mg/dl) 135 132 143 148 123	CSF glucose (mg/dl) 40 47 51 54 42	Blood leukocyte/mm 3 (Blood PNL%) 16100 (68%) 14700 (69%) 10300 (66%) 20700 (70%) 17000 (85%)
	6 7 8 9 10 11 12 13 14 C C E P T E D F/60 +/+/+ M/75 +/+/+ M/43 +/+/-M/26 +/+/+ F/ 21 -/-/-M/55 +/+/-M/23 +/+/-F/58 -/+/-F/46 -/+/-	+/+ -/--/-+/+ -/--/+ -/--/-+/-	450 >1000 3450 350 >1000 >1000 280 >1000 >1000	103 201 2055 110 167 104 397 382 38	35 50 32 1 43 58 24 29 60	13200 (75%) 9140 (82%) 24100 (94%) 10600 (83%) 20800 (85.4%) 11800 (91.2%) 32000 (94.1%) 15530 (86%) 16250(79%)
	15 A	M/43	+/+/-	-/-	>1000	82	38	13670 (76%)
	16	F/70	+/+/+	+/+	>1000	517	58	10990 (86%)
	17	M/68	+/+/-	+/+	500	289	27	10800 (74%)
	18	M/?	+/+/-	-/-	>1000	308	55	19600 (88%)
	19	F/48	+/-/-	+/-	>1000	317	59	8400 (82%)
	20	M/25	+/+/-	-/-	300	281	23	11900 (75%)

Table 2

 2 Susceptibility data of infecting strains, tunderlying diseases, reatment details and outcome data of the A. baumannii meningitis cases

Acknowledgments: Authors thank European Study Group for Infections of Brain (Esgib). This research did not receive any specific grant from any party.


Heinz H Bauschke
email: heinz.bauschke@ubc.ca.

Minh N Dao
email: minhdn@hnue.edu.vn

Dominikus Noll
email: noll@mip.ups-tlse.fr.

Hung M Phan
email: hungphan@uml.edu.

Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study

Keywords: 2010 Mathematics Subject Classification: Primary 65K05; Secondary 65K10, 90C25 alternating projections, convex feasibility problem, convex set, Douglas-Rachford algorithm, projection, proximal mapping, proximal point algorithm, proximity operator

Many iterative methods for solving optimization or feasibility problems have been invented, and often convergence of the iterates to some solution is proven. Under favourable conditions, one might have additional bounds on the distance of the iterate to the solution leading thus to worst case estimates, i.e., how fast the algorithm must converge.

Exact convergence estimates are typically hard to come by. In this paper, we consider the complementary problem of finding best case estimates, i.e., how slow the algorithm has to converge, and we also study exact asymptotic rates of convergence. Our investigation focuses on convex feasibility in the Euclidean plane, where one set is the real axis while the other is the epigraph of a convex function. This case study allows us to obtain various convergence rate results. We focus on the popular method of alternating projections and the Douglas-Rachford algorithm. These methods are connected to the proximal point algorithm which is also discussed. Our findings suggest that the Douglas-Rachford algorithm outperforms the method of alternating projections in the absence of constraint qualifications. Various examples illustrate the theory.

Introduction

Three algorithms

Let X be a Euclidean space, with inner product •, • and induced norm • , and let f : X → ]-∞, +∞] be convex, lower semicontinuous, and proper. A classical method for finding a minimizer of f is the proximal point algorithm (PPA). It requires using the proximal point mapping (or proximity operator) which was pioneered by Moreau [13]: Fact 1.1 (proximal mapping) For every x ∈ X, there exists a unique point p = P f (x) ∈ X such that min y∈X f (y) + 1 2 xy 2 = f (p) +1 2 xp 2 . The induced operator P f : X → X is firmly nonexpansive 1 , i.e., (∀x ∈ X)(∀y ∈ X) P f (x) -P f (y) 2 + (Id -P f )x -(Id -P f )y 2 ≤

xy 2 .

The proximal point algorithm was proposed by Martinet [START_REF] Martinet | Régularisation d'inéquations variationnelles par approximations successives[END_REF] and further studied by Rockafellar [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF]. Nowadays numerous extensions exist; however, here we focus only on the most basic instance of PPA: Fact 1.2 (proximal point algorithm (PPA)) Let f : X → ]-∞, +∞] be convex, lower semicontinuous, and proper. Suppose that Z, the set of minimizers of f , is nonempty, and let x 0 ∈ X. Then the sequence generated by [START_REF] Alber | An iterative method for solving a class of nonlinear operator equations in Banach spaces[END_REF] (∀n ∈ N) x n+1 = P f (x n )

converges to a point in Z and it satisfies

(2) (∀z ∈ Z)(∀n ∈ N)

x n+1 -z 2 + x n -x n+1 2 ≤ x n -z 2 .
An ostensibly quite different type of optimization problem is, for two given closed convex nonempty subsets A and B of X, to find a point in A ∩ B = ∅. Let us present two fundamental algorithms for solving this convex feasibility problem. The first method was proposed by Bregman [START_REF] Bregman | The method of successive projection for finding a common point of convex sets[END_REF].

Fact 1.3 (method of alternating projections (MAP))

Let a 0 ∈ A and set [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] (∀n ∈ N) a n+1 = P A P B (a n ).

Then (a n ) n∈N converges to a point a ∞ ∈ C = A ∩ B. Moreover,

(4) (∀c ∈ C)(∀n ∈ N) a n+1 -c 2 + a n+1 -P B a n 2 + P B a n -a n 2 ≤ a n -c 2 .
The second method is the celebrated Douglas-Rachford algorithm. The next result can be deduced by combining [START_REF] Lions | Splitting algorithms for the sum of two nonlinear operators[END_REF] and [START_REF] Bauschke | Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization[END_REF]. Fact 1.4 (Douglas-Rachford algorithm (DRA)) Set T = Id -P A + P B R A , let z 0 ∈ X, and set [START_REF] Bauschke | Restricted normal cones and the method of alternating projections: applications[END_REF] (∀n ∈ N) a n = P A z n and z n+1 = Tz n .

Then 2 (z n ) n∈N converges to some point z ∞ ∈ Fix T = (A ∩ B) + N A-B (0), and (a n ) n∈N converges to P A z ∞ ∈ A ∩ B.

Again, there are numerous refinements and adaptations of MAP and DRA; however, it is here not our goal to survey the most general results possible 3 but rather to focus on the speed of convergence. We will make this precise in the next subsection.

Goal and contributions

Most rate-of-convergence results for PPA, MAP, and DRA take the following form: If some additional condition is satisfied, then the convergence of the sequence is at least as good as some form of "fast" convergence (linear, superlinear, quadratic etc.). This can be interpreted as a worst case analysis. In the generality considered here 4 , we are not aware of results that approach this problem from the other side, i.e., that address the question: Under which conditions is the convergence no better than some form of "slow" convergence? This concerns the best case analysis. Ideally, one would like an exact asymptotic rate of convergence in the sense of (14) below.

While we do not completely answer these questions, we do set out to tackle them by providing a case study when X = R2 is the Euclidean plane, the set A = R × {0} is the real axis, and the set B is the epigraph of a proper lower semicontinuous convex function f . We will see that in this case MAP and DRA have connections to the PPA applied to f . We focus in particular on the case not covered by conditions guaranteeing linear convergence of MAP or DRA 5 . We originally expected the behaviour of MAP and DRA in cases of "bad geometry" to be similar 6 . It came to us as surprise that this appears not to be the case. In fact, the examples we provide below suggest that DRA performs significantly better than MAP. Concretely, suppose that B is the epigraph of the function f (x) = (1/p)|x| p , where 1 < p < +∞. Since A = R × {0}, we have that A ∩ B = {(0, 0)} and since f (0) = 0, the "angle" between A and B at the intersection is 0. As expected MAP converges sublinearly (even logarithmically) to 0. However, DRA converges faster in all cases: superlinearly (when 1 < p < 2), linearly (when p = 2) or logarithmically (when 2 < p < +∞). This example is deduced by general results we obtain on exact rates of convergence for PPA, MAP and DRA.

Organization

The paper is organized as follows. In Section 2, we provide various auxiliary results on the convergence of real sequences. These will make the subsequent analysis of PPA, MAP, and DRA more structured. Section 3 focuses on the PPA. After reviewing results on finite, superlinear, and linear convergence, we exhibit a case where the asymptotic rate is only logarithmic. We then turn to MAP in Section 4 and provide results on the asymptotic convergence. We also draw the connection between MAP and PPA and point out that a result of G üler is sharp. In Section 5, we deal with DRA, draw again a connection to PPA and present asymptotic convergence. The notation we employ is fairly standard and follows, e.g., [START_REF] Rockafellar | Convex Analysis[END_REF] and [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF].

Auxiliary results

In this section we collect various results that facilitate the subsequent analysis of PPA, MAP and DRA. We begin with the following useful result which appears to be part of the folklore 7 .

Fact 2.1 (generalized Stolz-Cesàro theorem) Let (a n ) n∈N and (b n ) n∈N be sequences in R such that (b n ) n∈N is unbounded and either strictly monotone increasing or strictly monotone decreasing. Then [START_REF] Bauschke | Linear and strong convergence of algorithms involving averaged nonexpansive operators[END_REF] lim

n→∞ a n+1 -a n b n+1 -b n ≤ lim n→∞ a n b n ≤ lim n→∞ a n b n ≤ lim n→∞ a n+1 -a n b n+1 -b n ,
where the limits may lie in [-∞, +∞].

Setting (b n ) n∈N = (n) n∈N in Fact 2.1, we obtain the following:

Corollary 2.2
The following inequalities hold for an arbitrary sequence (x n ) n∈N in R:

(7) lim n→∞ (x n+1 -x n ) ≤ lim n→∞ x n n ≤ lim n→∞ x n n ≤ lim n→∞ (x n+1 -x n ). Set R ++ = x ∈ R x > 0 .
For the remainder of this section, we assume that (8) g : R ++ → R ++ is increasing and H is an antiderivative of -1/g.

Example 2.3 (x q ) Let g(x) = x q on R ++ , where 1 ≤ q < ∞. If q > 1, then -1/g(x) = -x -q and we can choose H(x) = x 1-q /(q -1) which has the inverse H -1 (x) = 1/((q -1)x) 1/(q-1) . If q = 1, then we can choose H(x) =ln(x) which has the inverse H -1 (x) = exp(-x).

Proposition 2.4 Let (β n ) n∈N and (δ n ) n∈N be sequences in R ++ , and suppose that

(9) (∀n ∈ N) β n+1 = β n -δ n g(β n ).
Then the following hold: 7 Since we were able to locate only an online reference, we include a proof in Appendix A.

(i) (∀n

∈ N) δ n ≤ H(β n+1 ) -H(β n ) ≤ δ n+1 β n -β n+1 β n+1 -β n+2 = δ n g(β n ) g(β n+1
) .

(ii) lim

n→∞ δ n ≤ lim n→∞ H(β n ) n ≤ lim n→∞ H(β n ) n ≤ lim n→∞ δ n g(β n ) g(β n+1 ) . (iii) If (δ n ) n∈N is convergent, say δ n → δ ∞ , and g(β n ) g(β n+1 ) → 1, then H(β n ) n → δ ∞ .
Proof. For every n ∈ N, we have

δ n = β n -β n+1 g(β n ) ≤ β n β n+1 dx g(x) = H(β n+1 ) -H(β n ) (10a) ≤ β n -β n+1 g(β n+1 ) = δ n+1 β n -β n+1 β n+1 -β n+2 = δ n g(β n ) g(β n+1 ) . (10b)
Hence (i) holds. Combining with [START_REF] Borwein | Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets[END_REF], we obtain (ii). Finally, (iii) follows from (ii).

Corollary 2.5 Let (x n ) n∈N and (δ n ) n∈N be sequences in R ++ such that [START_REF] Lions | Splitting algorithms for the sum of two nonlinear operators[END_REF] (∀n ∈ N)

x n = x n+1 + δ n g(x n+1
).

Then the following hold:

(i) (∀n ∈ N) δ n g(x n+1 ) g(x n ) ≤ H(x n+1 ) -H(x n ) ≤ δ n . (ii) lim n→∞ δ n g(x n+1 ) g(x n ) ≤ lim n→∞ H(x n ) n ≤ lim n→∞ H(x n ) n ≤ lim n→∞ δ n . (iii) If (δ n ) n∈N is convergent, say δ n → δ ∞ , and g(x n+1 ) g(x n ) → 1, then H(x n ) n → δ ∞ . Proof. Indeed, set (∀n ∈ N) ε n = δ n g(x n+1 ) g(x n
) and rewrite the update (12)

x n+1 = x n -δ n g(x n+1 ) g(x n ) g(x n ) = x n -ε n g(x n ).
Now apply Proposition 2.4.

Definition 2.6 (types of convergence)

Let (α n ) n∈N be a sequence in R ++ such that α n → 0, and suppose there exists 1 ≤ q < +∞ such that

(13) α n+1 α q n → c ∈ R + .
Then the convergence of (α n ) n∈N to 0 is:

(i) with order q if q > 1 and c > 0;

(ii) superlinear if q = 1 and c = 0;

(iii) linear if q = 1 and 0 < c < 1;

(iv) sublinear if q = 1 and c = 1;

(v) logarithmic if it is sublinear and |α n+1 -

α n+2 |/|α n -α n+1 | → 1. If (β n ) n∈N is also a sequence in R ++ , it is convenient to define (14) α n ∼ β n ⇔ lim n→∞ α n β n ∈ R ++ .
The following example exhibits a case where we obtain a simple exact asymptotic rate of convergence.

Example 2.7 Let (x n ) n∈N and (δ n ) n∈N be sequences in R ++ , and let 1 < q < ∞. Suppose that

(15) δ n → δ ∞ ∈ R ++ , x n x n+1 → 1, and (∀n ∈ N) x n = x n+1 + δ n x q n+1 .
Then

x n → 0 logarithmically, (16)
x n

1 n 1/(q-1) → 1 ((q -1)δ ∞ ) 1/(q-1) and x n ∼ 1 n 1/(q-1)
.

Proof. Suppose that g(x) = x q and note that g(x n+1 )/g(x n ) = (x n+1 /x n ) q → 1 q = 1. This implies that x n → 0 logarithmically. Finally, [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF] follows from Example 2.3, Corollary 2.5, and [START_REF] Phan | Linear convergence of the Douglas-Rachford method for two closed sets[END_REF].

We conclude this section with some one-sided versions which are useful for obtaining information about how fast or slow a sequence must converge.

Corollary 2.8 Let (β n ) n∈N and (ρ n ) n∈N be sequences in R ++ , and suppose that

(17) (∀n ∈ N) β n+1 ≤ β n -ρ n g(β n ) and ρ = lim n→∞ ρ n ∈ R ++ . Then (18) ∀ε ∈ ]0, ρ[ (∃ m ∈ N)(∀n ≥ m) β n ≤ H -1 n(ρ -ε) . Proof. Observe that (19) (∀n ∈ N) β n+1 = β n -δ n g(β n ), where δ n = β n -β n+1 g(β n ) ≥ ρ n . Hence, by Proposition 2.4, ρ ≤ lim n→∞ H(β n )/n. Let ε ∈]0, ρ[. Then there exists m ∈ N such that (∀n ≥ m) ρ -ε ≤ H(β n )/n ⇔ H -1 (n(ρ -ε)) ≥ β n .
Example 2.9 Let (β n ) n∈N and (ρ n ) n∈N be sequences in R ++ , let 1 ≤ q < ∞, and suppose that

(20) (∀n ∈ N) β n+1 ≤ β n -ρ n β q n and ρ = lim n→∞ ρ n ∈ R ++ .
Let 0 < ε < ρ. Then there exists m ∈ N such that the following hold:

(i) If q > 1, then (∀n ≥ m) β n ≤ 1 (q -1)n(ρ -ε) 1/(q-1) = O 1/n 1/(q-1) . (ii) If q = 1, then (∀n ≥ m) β n ≤ γ n , where γ = exp(ε -ρ) ∈ ]0, 1[.
Consequently, the convergence of (β n ) n∈N to 0 is at least sublinear if q > 1 and at least linear if q = 1.

Proof. Combine Example 2.3 with Corollary 2.8.

Remark 2.10 Example 2.9(i) can also be deduced from [7, Lemma 4.1]; see also [START_REF] Alber | An iterative method for solving a class of nonlinear operator equations in Banach spaces[END_REF].

Corollary 2.11 Let (β n ) n∈N and (ρ n ) n∈N be sequences in R ++ , and suppose that

(21) (∀n ∈ N) β n ≥ β n+1 ≥ β n -ρ n g(β n ) and ρ = lim n→∞ ρ n g(β n ) g(β n+1 ) ∈ R + . Then (22) (∀ε ∈ R ++ )(∃ m ∈ N)(∀n ≥ m) β n ≥ H -1 n(ρ + ε) . Proof. Observe that (23) (∀n ∈ N) β n+1 = β n -δ n g(β n ), where δ n = β n -β n+1 g(β n ) ≤ ρ n . Hence, by Proposition 2.4, lim n→∞ H(β n )/n ≤ ρ. Let ε ∈ R ++ . Then there exists m ∈ N such that (∀n ≥ m) ρ + ε ≥ H(β n )/n ⇔ H -1 (n(ρ + ε)) ≤ β n .
Example 2.12 Let (β n ) n∈N and (ρ n ) n∈N be sequences in R ++ , let 1 ≤ q < ∞, and suppose that

(24) (∀n ∈ N) β n ≥ β n+1 ≥ β n -ρ n β q n and ρ = lim n→∞ ρ n β q n β q n+1 ∈ R + . Let ε ∈ R ++ .
Then there exists m ∈ N such that the following hold:

(i) If q > 1, then (∀n ≥ m) β n ≥ 1 (q -1)n(ρ + ε) 1/(q-1) . (ii) If q = 1, then (∀n ≥ m) β n ≥ γ n , where γ = exp(-ρ -ε) ∈ ]0, 1[.
Consequently, the convergence of (β n ) n∈N to 0 is at best sublinear if q > 1 and at best linear if q = 1.

Proof. Combine Example 2.3 with Corollary 2.11.

Proximal point algorithm (PPA)

This section focuses on the proximal point algorithm. We assume that (25) f : R → ]-∞, +∞] is convex, lower semicontinuous, proper, with (26) f (0) = 0 and f (x) > 0 when x = 0.

Given x 0 ∈ R, we will study the basic proximal point iteration

(27) (∀n ∈ N) x n+1 = P f (x n ). Note that if x > 0 and y < 0, then f (y) + 1 2 |x -y| 2 > f (0) + 1 2 |x -0| 2 ≥ f (P f x) + 1 2 |x -P f x| 2 .
Hence the behaviour of f | R --is irrelevant for the determination of P f | R ++ (and an analogous statement holds for the determination of P f | R --)! For this reason, we restrict our attention to the case when (28)

x 0 ∈ R ++ is the starting point of the proximal point algorithm. The general theory (Fact 1.2) then yields (29)

x 0 ≥ x 1 ≥ • • • ≥ x n ↓ 0.
In this section, it will be convenient to additionally assume that (30) f is an even function;

although, as mentioned, the behaviour of f | R --is actually irrelevant because x 0 ∈ R ++ .

Combining the assumption that 0 is the unique minimizer of f with [15, Theorem 24.1], we learn that

(31) 0 ∈ ∂ f (0) = [ f -(0), f + (0)] ∩ R = [-f + (0), f + (0)] ∩ R.
We start our exploration by discussing convergence in finitely many steps.

Proposition 3.1 (finite convergence)

We have x n → 0 in finitely many steps, regardless of the starting point x 0 ∈ R ++ , if and only if

(32) 0 < f + (0), in which case P f x n = 0 ⇔ x n ≤ f + (0). Proof. Let x > 0. Then P f x = 0 ⇔ x ∈ 0 + ∂ f (0) ⇔ x ≤ f + (0) by (31).
Suppose first that f + (0) > 0. Then, by (31), 0 ∈ int ∂ f (0) and, using (29), there exists n ∈ N such that x n ≤ f + (0). It follows that x n+1 = x n+2 = • • • = 0. (Alternatively, this follows from a much more general result of Rockafellar; see [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF]Theorem 3] and also Remark 3.4 below.) Now assume that there exists n ∈ N such that P f x n = 0 and x n > 0. By the above, x n ≤ f + (0) and thus f + (0) > 0.

An extreme case occurs when f + (0) = +∞ in Proposition 3.1: Example 3.2 (ι {0} and the projector) Suppose that f = ι {0} . Then P f = P {0} and (∀n ≥ 1)

x n = 0.

P f : x → x -x |x| , if |x| > 1; 0, otherwise,
Consequently, x n = 0 if and only if n ≥ x 0 .

Remark 3.4

In [16, Theorem 3], Rockafellar provided a very general sufficient condition for finite convergence of the PPA (which works actually for finding zeros of a maximally monotone operator defined on a Hilbert space). In our present setting, his condition is

(34) 0 ∈ int ∂ f (0).
By Proposition 3.1, this is also a condition that is necessary for finite convergence.

Thus, we assume from now on that f + (0) = 0, or equivalently (since f is even and by (31)), that

(35) f (0) = 0.
in which case finite convergence fails and thus (36)

x 0 > x 1 > • • • > x n ↓ 0.
We now have the following sufficient condition for linear convergence. The proof is a refinement of the ideas of Rockafellar in [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF]. Proposition 3.5 (sufficient condition for linear convergence) Suppose that

(37) λ = lim x↓0 f (x) x 2 ∈ ]0, +∞] .
Then the following hold:

(i) If λ < +∞, then there exists α 0 ∈ 1 2λ , 1 λ such that (38) (∀ε > 0)(∃ m ∈ N)(∀n ≥ m) |x n+1 | ≤ α 0 1 + α 2 0 (1 + 2λ -2ε) |x n |. (ii) If λ = +∞, then (39) (∀α > 0)(∀ε > 0)(∃ m ∈ N)(∀n ≥ m) |x n+1 | ≤ α 1 + α 2 (1 + 2λ -ε) |x n |.
Proof. By [16, Remark 4 and Proposition 7], there exists α 0 ∈ 1 2λ , 1 λ such that (∂ f ) -1 is Lipschitz continuous at 0 with every modulus α > α 0 . Let α > α 0 . Then there exists τ > 0 such that

(40) (∀|x| < τ)(∀z ∈ (∂ f ) -1 (x)) |z| ≤ α|x|. Since x n → 0 by [16, Theorem 2] (or (36)), there exists m ∈ N such that (∀n ≥ m) |x n - x n+1 | ≤ τ. Let n ≥ m. Noticing that x n ∈ (Id +∂ f )(x n+1 ), we have (41) x n+1 ∈ (∂ f ) -1 (x n -x n+1 ).
It follows by ( 40) that

(42) |x n+1 | ≤ α|x n -x n+1 |. Since x n -x n+1 ∈ ∂ f (x n+1 ), we have (43) x n -x n+1 , x n+1 = x n -x n+1 , x n+1 -0 ≥ f (x n+1 ) -f (0) = f (x n+1 ).
Now for every ε > 0, employing (37) and increasing m if necessary, we can and do assume that

(44) (∀n ≥ m) x n -x n+1 , x n+1 ≥ λ - ε 2 |x n+1 | 2 .
Let n ≥ m. Combining (42) and (44), we obtain

|x n | 2 = |x n+1 | 2 + |x n -x n+1 | 2 + 2 x n -x n+1 , x n+1 (45a) ≥ |x n+1 | 2 + 1 α 2 |x n+1 | 2 + (2λ -ε)|x n+1 | 2 (45b) = 1 + α 2 (1 + 2λ -ε) α 2 |x n+1 | 2 . (45c) This gives (46) |x n+1 | ≤ α 1 + α 2 (1 + 2λ -ε) |x n |
and hence (39) holds. Now assume that λ < +∞ so that

α 0 > 0. Since α → α √ 1+α 2 (1+2λ-ε) = 1 1 α 2 +(1+2λ-ε)
is strictly increasing on R + , we note that the choice α = α 0 / 1εα 2 0 > α 0 yields (38).

Remark 3.6

Assume that f is differentiable on U = ]0, δ[, where δ ∈ R ++ . Then f (x) > 0 on U. Note that lim x↓0 f (x)

x = f + (0). Therefore, L'H ôpital's rule shows that if f + (0) exists in [0, +∞], then (47) λ = 1 2 f + (0) in (37). A sufficient condition for λ to exist is to assume that the function f (x)/x 2 is monotone on U which in turn happens when 2 f (x)x f (x) is either nonnegative or nonpositive on U by using the quotient rule.

Although we won't need it in the remainder of this paper, we point out that the proof of Proposition 3.5 still works in a more general setting leading to the following result: Corollary 3.7 Let H be a real Hilbert space, and let f : H → ]-∞, +∞] be convex, lower semicontinuous and proper such that 0 is the unique minimizer of f . Assume also that

(48) λ = lim 0 =x→0 f (x) x 2 ∈ ]0, +∞] .
Then there exists α 0 ∈ 1 2λ , 1 λ such that

(49) (∀α > α 0 )(∀ε > 0)(∃ m ∈ N)(∀n ≥ m) x n+1 ≤ α 1 + α 2 (1 + 2λ -ε) x n .
If λ < +∞, then eventually

(50) x n+1 ≤ α 0 √ 1 + α 0 2 x n ,
a result which can also be deduced from [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF]Theorem 2].

We now discuss powers of the absolute value function.

Example 3.8 (|x| 2 and linear convergence) Suppose that f (x) = x 2 . Then x + f (x) = 3x and hence P f = 1 3 Id. We see that the actual linear rate of convergence of the PPA is (51) 1 3 .

Now consider Proposition 3.5 and Corollary 3.7. Then clearly λ = 1 in (37) and hence α 0 ∈ 1 2 , 1 . In fact, since ∂ f = 2 Id and so (∂ f ) -1 = 1 2 Id, we know that the tightest choice for α 0 is

α 0 = 1 2 .
The linear rate obtained by ( 50) is

(1/2)/ 1 + (1/2) 2 , i.e., (52) 1 √ 5 .
Let us compare to the linear rate provided by Proposition 3.5, where, for every ε > 0, we obtain

(1/2)/ 1 + (1/2) 2 (1 + 2 -2ε) = 1/ √ 7 -2ε.
From the proof of Proposition 3.5, we see that we can here actually set ε = 0; thus, the rate provided is

(53) 1 √ 7 .
In summary, 1/ √ 7, the rate from Proposition 3.5, is better than 1/ √ 5, which comes from (50); however, even the former does not capture the true rate 1/3. Example 3.9 (|x| q , where 1 < q < 2, and superlinear convergence) Suppose that f (x) = |x| q , where 1 < q < 2. Note that λ = +∞ and thus α 0 = 0 in (38). In passing, we point out that we cannot use α 0 itself in (38) because it would imply finite convergence which does not occur by (36). Set φ(x) = x + qx q-1 and note that (∀n ∈ N)

x n = φ(x n+1 ). Now set also ψ(x) = qx q-1 , and assume that a sequence (ρ n ) n∈N satisfies (∀n ∈ N) ρ n = ψ(ρ n+1 ). The sequence (ρ n ) n∈N can be thought of as an approximation of (x n ) n∈N . It has the advantage that the implicit recursion is invertible and solvable; indeed one may verify by induction that (54) (∀n ∈ N) ρ n = ρ 1/(q-1) n 0

(1/q) (1/(q-1) n -1)/(2-q) ; Assume furthermore that ρ 0 = x 0 is sufficiently close to 0. Since φ and ψ are increasing and φ > ψ > 0 on R ++ , we deduce that (∀n ≥ 1)

x n < ρ n . Therefore, ( 55
) (∀n ∈ N) x n ρ n = φ(x n+1 ) ψ(x n+1 ) x n+1 ρ n+1 q-1 > x n+1 ρ n+1 q-1 , which implies that (56) 0 < x n ρ n < x 1 ρ 1 1/(q-1) n-1
→ 0 because 1/(q -1) > 1. Let n ∈ N. It follows from x n = x n+1 + qx q-1 n+1 > x n+1 and 1 < q < 2 that x n+1 x q-1 n < x n x q-1 n+1 , and so (57)

x n x n-1 = x n+1 + qx q-1 n+1

x n + qx q-1 n < x q-1 n+1

x q-1 n . This gives x 1/(q-1)

n x 1/(q-1) n-1 < x n+1 x n ; hence, (58) x n
x 1/(q-1) n-1

< x n+1
x 1/(q-1) n .

On the other hand,

x n = x n+1 + qx q-1 n+1 > qx q-1
n+1 , which yields ( x n q ) 1/(q-1) > x n+1 and hence

x n+1

x 1/(q-1) n < q 1/(1-q) . The sequence (x n+1 /(x 1/(q-1) n

)) n∈N is thus increasing and bounded above, and so it converges to some µ > 0. We obtain that x n → 0 superlinearly with order 1/(q -1).

Example 3.10 (|x| q , where 2 < q, and logarithmic convergence) Suppose that f (x) = |x| q , where 2 < q < +∞. Because (∀n ∈ N) x n = x n+1 + qx q-1 n+1 , we have x n /x n+1 = 1 + qx q-2 n+1 → 1. It thus follows from Example 2.7 that x n → 0 logarithmically and (59)

x n

1 n 1/(q-2) → 1 ((q -2)q) 1/(q-2) .
Let us summarize what we found out in the previous three examples about the behaviour of the PPA applied to |x| q : q PPA convergence of x n → 0 for f (x) = |x| q 1 < q < 2 superlinear with order 1/(q -1) q = 2 linear with rate 1/3 2 < q < +∞ logarithmic

Method of Alternating Projections (MAP)

We now turn to the method of alternating projections. As in Section 3, we assume without loss of generality that (60a) f : R → ]-∞, +∞] is convex, lower semicontinuous, and proper, with (60b) f even, f (0) = 0, f > 0 otherwise, and f (0) = 0.

Furthermore, we set

(60c) A = R × {0} and B = epi f .
The projection onto A is very simple:

(61) P A : R 2 → R 2 : (x, r) → (x, 0).

We now turn to P B .

∈ dom f ) (z -y)(x -y) ≤ ( f (z) -f (y))( f (y) -r).
Corollary 4.2 Suppose that f is differentiable at 0, let (x, r) ∈ (dom f × R) B, and set (y, f (y)) = P B (x, r). Then y = 0 if x = 0, and y lies strictly between x and 0 otherwise. Furthermore,

x 2 + r 2 ≥ y 2 + f (y) 2 + (x -y) 2 + (r -f (y)) 2 .
Proof. We use Fact 4.1. Observe that r < f (y) and hence that f (y)r > 0. Choosing z = 0 gives -y(xy) ≤f (y)( f (y)r) ≤ 0. If x = 0, this implies y 2 ≤ 0, and so y = 0. Assume that x = 0. Then y = 0 since y = 0 implies x = 0 + ( f (0)r) f (0) = 0. We obtainf (y)( f (y)r) < 0, and then -y(xy) < 0, i.e., y(xy) > 0. It follows that y ∈ ]0, x[ if x > 0, and y ∈ ]x, 0[ if x < 0. Finally, since P B is firmly nonexpansive (see, e.g., [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 4.8]) and P B (0, 0) = (0, 0), we obtain

(62) (x, r) -(0, 0) 2 ≥ (y, f (y)) -(0, 0) 2 + (x, r) -(y, f (y)) 2 ,
which completes the proof.

We now turn to the sequence generated by the method of alternating projections. We assume without loss of generality that (63a)

x 0 ∈ R ++ ∩ dom f , a 0 = (x 0 , 0) ∈ A, and (63b) (∀n ∈ N) a n+1 = P A P B (a n ) = (x n+1 , 0).

Combining Fact 1.3, ( 60) and ( 63), we learn that (64)

x 0 > x 1 > • • • > x n ↓ 0.
We are ready for our first result on the lack of linear convergence for MAP.

Theorem 4.3

The following hold:

(65) (∀n ∈ N) x n+1 (x n+1 -x n ) + f 2 (x n+1 ) ≤ 0, ( 66
) (∀n ∈ N) x n = x n+1 + f (x n+1 )x * n+1 , where x * n+1 ∈ ∂ f (x n+1 ),
and x n → 0 sublinearly, i.e., (67)

x n+1 x n → 1.
If f is differentiable on some interval [0, δ], where δ ∈ R ++ , and there exists q ∈ R such that

(68) lim x↓0 f (x) f (x) x q = c q ∈ R ++ , then x n → 0 logarithmically, i.e., (69)
x n+1 -x n+2 x n -x n+1 → 1.
Proof. Corollary 4.2 implies (65). Using Fact 4.1, we have (66), which yields (70) [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 17.32]. This gives (67). Now suppose that f is differentiable on [0, δ] and (68) holds. Hence, using also (66), (71)

x n x n+1 = 1 + f (x n+1 ) -f (0) x n+1 x * n+1 → 1 + f (0) f (0) = 1 because of f (0) = 0 and
x n+1 -x n+2 x n -x n+1 = f (x n+2 ) f (x n+2 ) x q n+2 f (x n+1 ) f (x n+1 ) x q n+1 x n+2 x n+1 q → c q c q • 1 q = 1,
as claimed.

Remark 4.4

The function f satisfies (68) with q = 2a -1 and c q = aϕ 2 (0) whenever f (x) = x a ϕ(x), where a ∈ R {0}, δ ∈ R ++ , ϕ is differentiable on [0, δ], ϕ is continuous at 0, and ϕ(0) = 0.

Proposition 4.5 Suppose that f is differentiable on [0, δ], where δ ∈ R ++ . Set

(72) ∀q ∈ [1, +∞[ c q = lim x↓0 f (x) f (x) x q ,
where c q is either undefined if the limit does not exist or in [0, +∞]. Let q ∈ [1, +∞[. Then the following hold:

(i) c 1 = 0. If c q = 0, then c q = 0 for 1 ≤ q < q. If c q > 0, then c q = +∞ for q > q.

(ii) If c q = 0, then

x n x n+1 -1

x q-1 n+1 → 0 and (74) (∀ε ∈ R ++ )(∃ m ∈ N)(∀n ≥ m) x n ≥          exp(-ε) n , when q = 1;
1 (q -1)nε 1/(q-1) , when q > 1.

(iii) If c q > 0, then q > 1 and x n 1 n 1/(q-1) → 1 (q -1)c q 1/(q-1) .

Proof. (i): Using L'H ôpital's rule, we have lim x↓0 f (x)

x = lim x↓0 f (x) 1 = f (0) = 0 and hence c 1 = lim x↓0 f (x) f (x) x = 0.
The remaining statements follow now readily.

(ii): It follows from (66) that (75)

x n x n+1 -1 x q-1 n+1 = f (x n+1 ) f (x n+1 ) x q n+1
→ c q = 0; thus, (73) holds. Now write (76)

x n+1 = x n - f (x n+1 ) f (x n+1 ) x q n+1 x n+1 x n q x q n = x n -ρ n x q n ,
and note that ρ n → 0 because x n+1 /x n → 1 and c q = 0. Thus, (74) holds due to Example 2.12.

(iii): We must have q > 1 since otherwise c q = c 1 = 0 by (i), which is absurd. From (66), we have (77)

x n x n+1 = 1 + f (x n+1 ) f (x n+1 ) x n+1 → 1
and also, for every n ∈ N, (78)

x n = x n+1 + f (x n+1 ) f (x n+1 ) = x n+1 + f (x n+1 ) f (x n+1 ) x q n+1 x q n+1 .
The conclusion therefore follows from Example 2.7.

Example 4.6 ( 1 p |x| p , where p > 1) Suppose that f (x) = 1 p |x| p , where 1 < p < +∞. Let x ∈ R ++ . Then f (x) = 1 p x p and f (x) = x p-1 . Setting q = 2p -1 > 1, we have c q = 1 p > 0, and so x n → 0 logarithmically, using Theorem 4.3. Moreover, by Proposition 4.5(iii), (79)

x n

1 n 1/(2p-2) → 1 2p-2 p 1/(2p-2) .
For a couple of cases, one can actually invert (66) and simplify (79):

(80) p = 3 2 ⇒ x n 1/n → 3 2 and x n+1 = √ 9 + 24x n - 3 4 ; and (81)
p = 2 ⇒ x n 1/ √ n → 1 and x n+1 = 1 3 27 x n + 3 81 x 2 n + 24 2/3 -6 3 27 x n + 3 81 x 2 n + 24 . Example 4.7 (R - √ R 2 -x 2 ) Suppose that R ∈ R ++ and that f (x) = R - √ R 2 -x 2 on its domain [-R, R]. Let n ∈ N. Then f (x) = x √ R 2 -x 2 ,
and by (66), (82)

x n = x n+1 + R -R 2 -x 2 n+1 x n+1 R 2 -x 2 n+1 = Rx n+1 R 2 -x 2 n+1 . It follows that (83) x n+1 = Rx n x 2 n + R 2
, and also R 2

x 2 n+1 = 1 + R 2 x 2 n . Hence, R 2 x 2 n = n + R 2 x 2 0
, which yields the explicit formula (84)

x n = Rx 0 nx 2 0 + R 2 = R n + (R/x 0 ) 2 ∼ R √ n , which shows that x n → 0 logarithmically. Example 4.8 Suppose that f (x) = exp(|x|) -|x| -1. Then f (x) f (x) = 1 2 x 3 + 5 12
x 4 + 5 24 x 5 + O(x 6 ) on R ++ . Thus, Proposition 4.5(iii) with q = 3 and c q = 1 2 yields

x n /(1/ √ n) → 1.
Example 4.9 Suppose that f = cosh. Then f (x) f (x) = 1 2 x 3 + 1 8 x 5 + O(x 7 ) and hence again by Proposition 4.5(iii) with q = 3 and c q = 1 2 yields

x n /(1/ √ n) → 1.

Example 4.10 (extremely slow convergence

) Suppose that f (x) = exp(-x -2 ) with domain [- √ 2/3, √ 2/3].
Then c q = 0 in Proposition 4.5(ii) and hence, according to (73),

x n

x n+1 -1 x q-1 n+1

→ 0 for every q > 1.

Furthermore, the convergence (x n ) n∈N to 0 is extremely slow in the sense that (86) 1

x n ≤ O(n 1/p ) for every p > 0.

Remark 4.11 (MAP sequence is essentially a PPA sequence) Note that, by (66),

(87) (∀n ∈ N) x n ∈ (Id + f • ∂ f )(x n+1 ) = Id +∂ 1 2 f 2 (x n+1 ) and so (88) (∀n ∈ N) x n+1 = P1 2 f 2 (x n ). Since f 2 is
convex (by, e.g., [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 8.19]), we see that the sequence (a n ) n∈N = (x n , 0) n∈N generated by MAP is essentially the same as the sequence generated by PPA for the function 1 2 f 2 ! This useful connection will be further discussed after we recall a special case of a result due to G üler. ) Let H be a real Hilbert space, let f : H → ]-∞, +∞] be convex, lower semicontinuous, and suppose that the sequence (x n ) n∈N generated by the PPA converges (strongly) to some minimizer z of f . Then f

(x n ) -f (z) = o(1/n), i.e., n( f (x n ) - f (z)) → 0.
Combining Remark 4.11 with Fact 4.12 results in the following: Corollary 4. [START_REF] Moreau | Proximité et dualité dans un espace hilbertien[END_REF] The MAP sequence (a n ) n∈N = (x n , 0) n∈N satisfies .

(89) n f 2 (x n ) → 0.
Then (89) becomes

(91) n f 2 (x n ) ∼ nx 2p n ∼ 1 n 1/(p-1) → 0.
Note that this also shows that this consequence of Fact 4.12 is sharp in the sense that it cannot be improved to n 1+ε f 2 (x n ) → 0, where ε > 0. (Indeed, if n 1+ε f 2 (x n ) → 0, then we obtain a contradiction for sufficiently large p.)

Douglas-Rachford algorithm (DRA)

Finally, we investigate the Douglas-Rachford algorithm. As in Section 4, we assume that that (92a) f : R → ]-∞, +∞] is convex, lower semicontinuous, and proper, with (92b) f even, f (0) = 0, f > 0 otherwise, and f (0) = 0, and that (92c) A = R × {0} and B = epi f .

We now turn to the sequence generated by the Douglas-Rachford algorithm. We assume that (93a) x n → 0 and r n → r ∞ ∈ R + .

x 0 ∈ R ++ ∩ dom f , r 0 = 0, z 0 = (x 0 , 0) ∈ A,
Let us now investigate the effect of carrying out one DRA step:

Corollary 5.1 (one DRA step) Let (x, r) ∈ R 2 , set (x + , r + ) = T(x, r), and suppose that 0 < x ∈ dom f and 0 ≤ r < f (x). Then there exists x * + ∈ R such that

(96a) 0 < x + = x -r + x * + < x, x * + ∈ ∂ f (x + ) and r + = r + f (x + ) > r and (96b) x 2 + r 2 ≥ x 2 + + (r + -r) 2 + (x -x + ) 2 + r 2 + .
Proof. First, we note that R A (x, r) = (x, -r). Set (y, s) = P B (x, -r).

x n = 1 1 + r n+1 x * n+1 x n+1 → 1 1 + r ∞ f + (0)
and exactly one of the following holds:

(i) f + (0) = +∞ and x n → 0 superlinearly. (ii) f + (0) ∈ R ++ and x n → 0 linearly. (iii) f + (0) = 0 and x n → 0 sublinearly. If there exists q ∈ R such that (103) lim x↓0 f (x) x q = c ∈ R ++ , then x n → 0 logarithmically; moreover, if additionally q > 1, then (104)
x n 1 n 1/(q-1) → 1 ((q -1)r ∞ c) 1/(q-1) .

Proof. (101) follows from Corollary 5.1. Divide (101b) by x n+1 , solve for x n /x n+1 , then take reciprocals to obtain (105)

x n+1 x n = 1 1 + r n+1 x * n+1 x n+1
. Now assume that f + (0) exists; it belongs to [0, +∞] because x > 0 ⇒ f (x) > 0. Since x n ↓ 0, we see that

(106) x * n+1 x n+1 = f (x n+1 ) x n+1 = f (x n+1 ) -f (0) x n+1 -0 → f + (0).
Altogether, we get (102). Items (i) and (ii) are now clear, so let us focus on (iii). Obviously

x n → 0 sublinearly if and only if f + (0) = 0 which we henceforth assume, along with (103). It follows from (101b) that (107)

x n+1 -x n+2 x n -x n+1 = r n+2 f (x n+2 ) r n+1 f (x n+1 ) = r n+2 r n+1 f (x n+2 ) x q n+2 f (x n+1 ) x q n+1 x n+2 x n+1 q → r ∞ r ∞ • c c • 1 q = 1;
hence, x n → 0 logarithmically. Finally assume that q > 1. Writing (see (101b))

(108)

x n = x n+1 + r n+1 f (x n+1 ) x q n+1 x q n+1 = x n+1 + δ n x q n+1 ,
where δ n → r ∞ c > 0, we obtain (104) through Example 2.7. (ii) p = 2 and x n → 0 linearly with rate 1/(1 + r ∞ ).

(iii) 2 < p < +∞, x n → 0 logarithmically, and

x n 1 n 1/(p-2) → 1 ((p -2)r ∞ ) 1/(p-2) .
Proof. (i): From (101b), we obtain

(109) (∀n ∈ N) x n = x n+1 + r n+1 x p-1 n+1 . Since x n ↓ 0 and p < 2, we have (110) (∀ε > 0)(∃ m ∈ N)(∀n ≥ m) 0 < x n+1 < εx p-1 n+1 . Combining yields r n+1 x p-1 n+1 < x n < (r n+1 + ε)x p-1 n+1 . In turn, x n x p-1 n+1
→ r ∞ > 0 and the conclusion follows.

(ii): Clear from (102).

(iii): Apply Theorem 5.3(iii) with q = p -1 > 1 and c = 1. We conclude that in all cases, the DRA sequence converges to 0 faster than the MAP sequence 8 . To illustrate this, set x 0 = 1. Letting the parameter p range from 1 to 3, we show in Figure 1 the first 100 terms of the MAP sequence (x n ) n∈N and of the DRA sequence (x n ) n∈N . Although both sequences converge to 0, the solution, the stark contrast in their speed of convergence is shown in Figure 2 where we plot the quotient sequence of the MAP sequence divided by the DRA sequence. As predicted by the theory, the terms tend to +∞ when 1 < p < 2 illustrating the much faster convergence of the DRA sequence. x n ∼ R √ n .

Remark 5.5 (comparison MAP vs DRA when

f (x) = 1 p |x| p ) Suppose f (x) = 1 p |x| p ,
We now turn to the DRA sequence (x n ) n∈N . By (101b), we have for every n ∈ N (113)

x n = x n+1 + r n + R -R 2 -x 2 n+1 x n+1 R 2 -x 2 n+1 = (r n + R) x n+1 R 2 -x 2 n+1
; consequently, (114)

x n+1 = Rx n (r n + R) 2 + x 2 n .
Since f (x) = R 2 /(R 2x 2 ) 3/2 , we have f (0) = 1/R ∈ R ++ and therefore, by (102), the DRA sequence (115)

x n → 0 linearly with rate 1/(1 + r ∞ /R). Once again, the DRA sequence converges much faster than the MAP sequence! Let us conclude. The results in this paper suggest that, for the convex feasibility problem, DRA outperforms MAP in cases of "bad geometry" (such as the absence of constraint qualifications or a "zero angle" between the constraints at the intersection). Since our proof techniques do not naturally generalize, it would be interesting to study these questions in higher-dimensional space and other classes of convex sets.

Hence, for every z ∈ Z, f (z)f (p) ≥ p * , zp = p * , zx + p * , xp (119a) ≥p * zx + p * 2 ≥p * zx . (119b) Since f (p) ≥ f (z), we learn that (120) p * ≥ f (p)f (z)

xz ≥ 0.

Setting y = x in (118), we have

(121) f (x) -f (p) ≥ p * , x -p = p * 2 .
Therefore,

f (x) -f (z) -f (p) -f (z) = f (x) -f (p) ≥ p * 2 ≥ f (p) -f (z) x -z 2 . ( 122
) It follows that (123) f (x) -f (z) ≥ f (p) -f (z) 1 + f (p) -f (z) x -z 2 ;
equivalently,

(124) 1 f (x) -f (z) ≤ 1 f (p) -f (z) 1 + f (p) -f (z) x -z 2 -1
.

On the other hand, the definition of the proximal mapping yields (125) f (p) ≤ f (p) + 1 2 xp 2 ≤ f (z) + 1 2 xz 2 , which implies (126) f (p)f (z)

xz 2 ≤ 1 2 .

Consider the function α(t) = 1 1+t with domain ]-1, +∞[. Clearly, α is convex, α(0) = 1 and α( 12 ) = 2 3 . The line described by t → 1 -2 3 t goes through the same points and lies between these points above the graph of α(•) (by convexity). Hence (127)

∀0 ≤ t ≤ 1 2 1 1 + t ≤ 1 - 2 3 t.
Altogether, we deduce that

ϕ(x) = 1 f (x) -f (z) (128a) ≤ 1 f (p) -f (z) 1 - 2 3 • f (p) -f (z) x -z 2 (128b) = ϕ(p) - 2 3 x -z 2 . (128c)
Now assume that z ← x n+1 = P f x n . Then ϕ(x n+1 )ϕ(x n ) ≥ 2 3 x nz -2 → +∞. By Corollary 2.2, lim ϕ(x n ) n = +∞. Now take reciprocals.

Example 3 . 3 (

 33 |x| 1 and the thresholder) Suppose that f = | • | in which case ∂ f (0) = [-1, 1] and f + (0) = 1. Proposition 3.1 guarantees finite convergence of the PPA. Indeed, either a direct argument or [3, Example 14.5] yields (33)

Fact 4 . 1 (

 41 See[START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] Proposition 9.18 and Proposition 28.28]) Let (x, r) ∈ (dom f × R) B. Then P B (x, r) = (y, f (y)), where y satisfies x ∈ y + ( f (y)r)∂ f (y). Moreover, r < f (y) and (∀z

Fact 4 .

 4 12 (G üler) (See [10, Theorem 3.1].

Example 4 . 14 ( 1 p

 4141 |x| p revisited) Suppose that f (x) = 1 p |x| p , where 1 < p. By Example 4

  (∀n ∈ N) z n+1 = Tz n = (x n+1 , r n+1 ),where (93c) T = Id -P A + P B R A . Since N A-B (0, 0) = R + (0, 1), we have (94) A ∩ B = {(0, 0)} and Fix T = R + (0, 1), Hence we deduce from Fact 1.4, (92) and (93) that (95)

Example 5 . 4 ( 1 p

 541 |x| p , where 1 < p < +∞) Suppose that f (x) = 1 p |x| p , where 1 < p < +∞. Then exactly one of the following holds:(i) 1 < p < 2

  (a) MAP sequence (x n ) n∈N (b) DRA sequence (x n ) n∈N

Figure 1 :

 1 Figure 1: The distance of the first 100 terms to the solution for p ∈ [1, 3]

Figure 2 :

 2 Figure 2: The MAP sequence divided by the DRA sequence

  By Fact 4.1, (97) y = x -(r + f (y))x * + for some x * + ∈ ∂ f (y) and s = f (y). , r + ) = (Id -P A )(x, r)+ P B R A (x, r) = (x, r) -(x, 0) + (y, s) = (y, r + s). P r f + 1 2 f 2 (x) and r + = r + f (x + ),which reveals a connection between the DRA step and the PPA step for r f+ 1 2 f 2 . ↓ 0 and r n ↑ r ∞ ∈ R ++ ,and for every n ∈ N, there exits x * n+1 ∈ ∂ f (x n+1 ) such that (101b) 0 < x n+1 = x nr n+1 x * n+1 < x n and r n+1 = r n + f (x n+1 ).

	Now, (93c) gives
	(98) (x + Thus x + = y,
	(99)	x + = x -(r + f (x + ))x * + and r + = r + f (x + ),
	as claimed. The rest follows from Corollary 4.2.
	Remark 5.2 (DRA step is related to a PPA step) Consider Corollary 5.1. Then
	(100) x + = Theorem 5.3 (DRA sequence) The DRA sequence satisfies
	(101a) x n Now suppose that furthermore that f + (0) exists in [0, +∞]. Then
	(102)	x n+1

  where 1 < p < +∞. According to Example 4.6, the MAP sequence (x n ) n∈N exhibits logarithmic convergence to 0 and

	(111)	x n ∼	1 n	1/(2p-2)	.
	On the other hand, Example 5.4 yields the following for the DRA sequence (x n ) n∈N :
		p convergence of the DRA sequence (x n ) n∈N to 0
		1 < p < 2 superlinear with order	1 p -1
		p = 2 linear with rate	1 1 + r ∞	1	1/(p-2)
					n

2 < p < +∞ logarithmic and x n ∼

Note that if f = ι C is the indicator function of a nonempty closed convex subset of X, then P f = P C , where the P C is the nearest point mapping or projector of C; the corresponding reflector is R C =

2P C -Id.

Here Fix T = x ∈ X x = Tx is the set of fixed points of T, and N A-B (0) stands for the normal cone of the set A -B = ab a ∈ A, b ∈ B at 0.

See, e.g.,[START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] for various more general variants of PPA, MAP, and DRA.

Some results are known for MAP when the sets are linear subspaces; however, the slow (sublinear) convergence can only be observed in infinite-dimensional Hilbert space; see[START_REF] Deutsch | Arbitrarily slow convergence sequences of linear operators: a survey[END_REF] and references therein.

Indeed, the most common sufficient condition for linear convergence in either case is ri(A) ∩ ri(B) = ∅; see[START_REF] Bauschke | Restricted normal cones and the method of alternating projections: applications[END_REF] Theorem 3.21] for MAP and[START_REF] Phan | Linear convergence of the Douglas-Rachford method for two closed sets[END_REF] or [6, Theorem 8.5(i)] for DRA.

This expectation was founded in the similar behaviour of MAP and DRA for two subspaces; see[START_REF] Bauschke | The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle[END_REF].

It is interesting to note that DRA performs better than MAP when A and B are two subspaces with a small Friedrichs angle (see[START_REF] Bauschke | The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle[END_REF] Section 8]).

Acknowledgments

HHB was partially supported by the Natural Sciences and Engineering Research Council of Canada and by the Canada Research Chair Program. He also acknowledges the hospitality and the support of Université de Toulouse, France during the preparation of an early draft of this paper. MND was partially supported by an NSERC accelerator grant of HHB. HMP was partially supported by an internal grant of University of Massachusetts Lowell.

Appendix A

Proof of Fact 2.1. (This proof is taken from http://www.imomath.com/index.php?options= 686 and included here for completeness as we were not able to locate a book or journal reference.) The second inequality is obvious. We only prove the right inequality since the proof of the left inequality is similar. Without loss of generality, we assume that b n → +∞ and that λ = lim n→∞

Now let γ ↓ λ to complete the proof.

Appendix B

Proof of Fact 4.12. (This proof is a special case taken from [START_REF] Üler | On the convergence of the proximal point algorithm for convex minimization[END_REF] and included here for completeness.) Denote the minimizers of f by Z. Let x ∈ H, set p = P f x, p * = xp ∈ ∂ f (p), and assume that p / ∈ Z. We have (118) (∀y ∈ H) f (y)f (p) ≥ p * , yp .