Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions

Safa Guerdouh; Wided Chikouche; Imene Touil; Adnan Yassine

Displaying similar documents to “Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions”

A novel kernel function bridging iteration bounds in interior-point algorithms for linear programming

Imene Touil, Sajad Fathi-Hafshejani (2025)

Kybernetika

Similarity:

Kernel functions play an important role in designing and analyzing interior-point methods. They are not only used for determining search directions but also for measuring the distance between the given iterate and the $μ$ -center in the algorithms. Currently, interior-point methods based on kernel functions are among the most effective methods for solving different types of optimization problems and are very active research area in mathematical programming. Therefore, in this work, we introduce...

A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound

Benhadid Ayache, Saoudi Khaled (2020)

Communications in Mathematics

Similarity:

In this paper, we propose a large-update primal-dual interior point algorithm for linear optimization. The method is based on a new class of kernel functions which differs from the existing kernel functions in which it has a double barrier term. The investigation according to it yields the best known iteration bound $O (\sqrt{n} log (n) log (\frac{n}{ε}))$ for large-update algorithm with the special choice of its parameter $m$ and thus improves the iteration bound obtained in Bai et al. [] for large-update algorithm. ...

Global solutions to initial value problems in nonlinear hyperbolic thermoelasticity

Jerzy August Gawinecki

Similarity:

CONTENTS1. Introduction..................................................................................................................................... 5 1.1. Main Theorem 1.1................................................................................................................. 8 1.2. Main Theorem 1.2................................................................................................................. 92. Radon transform.......................................................................................................................................

Generic Primal-dual Interior Point Methods Based on a New Kernel Function

M. EL Ghami, C. Roos (2008)

RAIRO - Operations Research

Similarity:

In this paper we present a generic primal-dual interior point methods (IPMs) for linear optimization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. The proposed kernel function does not satisfy all the conditions proposed in [2]. We show that the corresponding large-update algorithm improves the iteration complexity with a factor $n^{\frac{1}{6}}$ when compared with the method based on the use of...

On the Picard problem for hyperbolic differential equations in Banach spaces

Antoni Sadowski (2003)

Discussiones Mathematicae, Differential Inclusions, Control and Optimization

Similarity:

B. Rzepecki in [5] examined the Darboux problem for the hyperbolic equation $z_{x y} = f (x, y, z, z_{x y})$ on the quarter-plane x ≥ 0, y ≥ 0 via a fixed point theorem of B.N. Sadovskii [6]. The aim of this paper is to study the Picard problem for the hyperbolic equation $z_{x y} = f (x, y, z, z_{x}, z_{x y})$ using a method developed by A. Ambrosetti [1], K. Goebel and W. Rzymowski [2] and B. Rzepecki [5].

An $0 (n^{3})$ worst case bounded special $L P$ knapsack $(0 - 1)$ with two constraints

Ruy E. Campello, Nelson Maculan (1988)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Nonuniform center bunching and the genericity of ergodicity among $C^{1}$ partially hyperbolic symplectomorphisms

Artur Avila, Jairo Bochi, Amie Wilkinson (2009)

Annales scientifiques de l'École Normale Supérieure

Similarity:

We introduce the notion of nonuniform center bunching for partially hyperbolic diffeomorphims, and extend previous results by Burns–Wilkinson and Avila–Santamaria–Viana. Combining this new technique with other constructions we prove that $C^{1}$ -generic partially hyperbolic symplectomorphisms are ergodic. We also construct new examples of stably ergodic partially hyperbolic diffeomorphisms.

Sur la classification des hexagones hyperboliques à angles droits en dimension 5

François Delgove, Nicolas Retailleau (2014)

Annales de la faculté des sciences de Toulouse Mathématiques

Similarity:

The aim of this paper is to give a classification of the right-angled hyperbolic hexagons in the real hyperbolic space $ℍ_{ℝ}^{5}$ , by using a quaternionic distance between geodesics in $ℍ_{ℝ}^{5}$ .

An interior-point algorithm for semidefinite least-squares problems

Chafia Daili, Mohamed Achache (2022)

Applications of Mathematics

Similarity:

We propose a feasible primal-dual path-following interior-point algorithm for semidefinite least squares problems (SDLS). At each iteration, the algorithm uses only full Nesterov-Todd steps with the advantage that no line search is required. Under new appropriate choices of the parameter $β$ which defines the size of the neighborhood of the central-path and of the parameter $θ$ which determines the rate of decrease of the barrier parameter, we show that the proposed algorithm is well defined...

A characterization of Fuchsian groups acting on complex hyperbolic spaces

Xi Fu, Liulan Li, Xiantao Wang (2012)

Czechoslovak Mathematical Journal

Similarity:

Let $G \subset 𝐒𝐔 (2, 1)$ be a non-elementary complex hyperbolic Kleinian group. If $G$ preserves a complex line, then $G$ is $ℂ$ -Fuchsian; if $G$ preserves a Lagrangian plane, then $G$ is $ℝ$ -Fuchsian; $G$ is Fuchsian if $G$ is either $ℂ$ -Fuchsian or $ℝ$ -Fuchsian. In this paper, we prove that if the traces of all elements in $G$ are real, then $G$ is Fuchsian. This is an analogous result of Theorem V.G. 18 of B. Maskit, Kleinian Groups, Springer-Verlag, Berlin, 1988, in the setting of complex hyperbolic isometric groups. As an...

Computing the determinantal representations of hyperbolic forms

Mao-Ting Chien, Hiroshi Nakazato (2016)

Czechoslovak Mathematical Journal

Similarity:

The numerical range of an $n \times n$ matrix is determined by an $n$ degree hyperbolic ternary form. Helton-Vinnikov confirmed conversely that an $n$ degree hyperbolic ternary form admits a symmetric determinantal representation. We determine the types of Riemann theta functions appearing in the Helton-Vinnikov formula for the real symmetric determinantal representation of hyperbolic forms for the genus $g = 1$ . We reformulate the Fiedler-Helton-Vinnikov formulae for the genus $g = 0, 1$ , and present an elementary...