4 présentations

• 
  10h30 - 10h55

  Complexity of trust-region methods in the presence of unbounded Hessian approximations

  • Mohamed Laghdaf Habiboullah, prés., GERAD - Polytechnique Montréal
  • Youssef Diouane, ISAE-SUPAERO, Université de Toulouse, Toulouse, 31055 Cedex 4, France
  • Dominique Orban, GERAD - Polytechnique Montréal

  We extend traditional complexity analyses of trust-region methods for unconstrained, possibly nonconvex, optimization. Whereas most complexity analyses assume uniform boundedness of the model Hessians, we work with potentially unbounded model Hessians. Boundedness is not guaranteed in practical implementations, in particular ones based on quasi-Newton updates such as PSB, BFGS and SR1. Our analysis is conducted for a family of trust-region methods that includes most known methods as special cases. We examine two regimes of Hessian growth: one bounded by a power of the number of successful iterations, and one bounded by a power of the number of iterations. This allows us to formalize and confirm the profound intuition of Powell [IMA J. Numer. Ana. 30(1):289-301,2010], who studied convergence under a special case of our assumptions, but whose proof contained complexity arguments. Specifically, for \(0 \leq p < 1\), we establish sharp \(O(\epsilon^{-2/(1-p)})\) evaluation complexity to find an \(\epsilon\)-stationary point when model Hessians are \(O(k^p)\), where \(k\) is the iteration counter. For \(p = 1\), which is the case studied by Powell, we establish a sharp \(O(\exp(c\epsilon^{-2}))\) evaluation complexity for a certain constant \(c > 0\). This is as Powell suspected and is far worse than other bounds surmised elsewhere in the literature. We establish similar bounds when model Hessians are \(O(|\mathcal{S}_k|^p)\), where \(|\mathcal{S}_k|\) is the number of iterations where the step was accepted, up to iteration \(k\). To the best of our knowledge, ours is the first work to provide complexity bounds when model Hessians grow linearly with \(|\mathcal{S}_k|\) or at most linearly with \(k\), which covers multiple quasi-Newton approximations.

  Link : https://arxiv.org/abs/2408.06243

• 
  10h55 - 11h20

  New Family of cutting planes for 0-1 polynomials programming problem: RTL-K to RLT-1 cutting planes

  • Ibrahim Dan Dije, prés., UQAM
  • Franklin Djeumou Fomeni, Universite du Quebec a Montreal
  • Leandro C. Coelho, Université Laval

  The reformulation-linearization technique (RLT), due to Sherali and Adams, is a general framework for constructing hierarchies of linear programming (LP) relaxations of various optimization problems. It was first developed for 0-1 polynomial programs, but was soon adapted to continuous polynomial programs, and then extended to mixed 0-1 polynomial programs. Since then, it has been further extended and adapted, to cover a wide range of integer programming and global optimization problems. As one moves up the levels of the RLT hierarchy, the LP relaxations grow stronger, also the number of variables increases exponentially. In practice, therefore, one can hope to solve the relaxations only at very low levels of the hierarchy. In fact, even solving the relaxation at the level two can be challenging.

  In this talk, we present a framework which generalizes quadratic space cutting planes from any given hierarchy level, by weakening the higher-level inequalities to quadratic space ones with a direct jump moving by using set subdivision. The estimators obtained from the weakening represent facets to the convex hull of the high-level multilinear monomials.

  We test the generated cutting planes using instances of the quadratic knapsack problem, then we will present some computational results which show that these cutting planes improved the linear relaxation of the quadratic knapsack problem.

• 
  11h20 - 11h45

  Welfare and environmental impacts of inventory holding in a supply chain under vertical and horizontal competition

  • fouad el ouardighi, prés., ESSEC Business School

  We assess the impact of inventory holding in a supply chain both in terms of social welfare and environmental footprint under vertical and horizontal competition. As key components of the problem, the players’ inventory and the pollution levels are stock variables that change over time and are determined by the players' decisions. Due to the cumulative nature of players’ inventory and pollution, we adopt a differential game of finite duration. The suggested model is shown to have the state-separability property (Dockner et al.,1985), which implies that the second stage of the game admits a unique Markov-perfect equilibrium.

• 
  11h45 - 12h10

  The optimization contribution of revitalization of nature reserve parks in South Africa: A case study of the Bushbuckridge Nature Reserve

  • Franklin Djeumou Fomeni, prés., Universite du Quebec a Montreal
  • Sejeso Matthews, University of the Witwatersrand, Johannesburg, South Africa
  • Simelane Simphiwe, University of Johannesburg, South Africa
  • Shabalala Lombuso Precious, University of South Africa, Pretoria, South Africa

  Tourism is a major contributor to South Africa’s economy. Before the Covid-19 pandemic, it accounted for about 8.6% of national GDP. Nature reserve parks play an essential role in this sector, as South Africa is a global leader in wildlife tourism. Some major actors in the wildlife within the tourism sector (Kruger National Park, Pilanesberg National Park, etc.), some of which are privately owned, have been doing very well over the years. However, the much smaller actors, primarily the nature reserves managed by provincial /local governments (Manyeleti Nature Reserve, Mariepskop Nature Reserve, Bushbuckridge Nature Reserve, etc.,) have been struggling on the opposite to keep up economically while dealing with the local population needs.
  The Bushbuckridge Nature Reserve, located in the Province of Mpumalanga, SA, has recently set itself an objective of becoming a world-class Nature Reserve that maintains the integrity of its biodiversity through conservation while permitting sustainable utilization of its natural resources by neighboring communities. In this work, we present an operations research decision support tool, which can help the management explore and analyze various options for restoring the ecosystem and wildlife in the nature reserve. The tool can also facilitate the exchange between the reserve management and the local population to account for their interest in the revitalization process. More precisely, we propose an optimization model that can be used to better reshape the ecosystem and wildlife of the reserve for maximum animal well-being and tourist attraction, as well as optimal and sustainable utilization of its natural resources by local communities. Some experiments have been conducted; this presentation will show the results.