<!DOCTYPE html>
<html lang="en">
<head>
<script>
  MathJax = { 
    tex: {
		    inlineMath: [['\\(','\\)']]
	} }
</script>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js">
</script>
<meta name="generator" content="plasTeX" />
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Comparative numerical study between line search methods and majorant functions in barrier logarithmic methods for linear programming: Comparative numerical study between line search methods and majorant functions in barrier logarithmic methods for linear programming</title>
<link rel="stylesheet" href="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/styles/theme-white.css" />
</head>

<body>

<div class="wrapper">

<div class="content">
<div class="content-wrapper">


<div class="main-text">



<div class="titlepage">
<h1>Comparative numerical study between line search methods and majorant functions in barrier logarithmic methods for linear programming</h1>
<p class="authors">
<span class="author">Soraya Chaghoub\(^\ast \) Djamel Benterki\(^\bullet \)</span>
</p>
<p class="date">October 13, 2019; accepted: April 30, 2020; published online: August 11, 2020.</p>
</div>
<div class="abstract"><p> This paper presents a comparative numerical study between line search methods and majorant functions to compute the displacement step in barrier logarithmic method for linear programming. This study favourite majorant function on line search which is promoted by numerical experiments. </p>
<p><b class="bf">MSC.</b> 90C22, 90C51. </p>
<p><b class="bf">Keywords.</b> Linear programming, Interior point methods, Line search, Majorant function. </p>
</div>
<p>\(^\ast \)School of Mathematical Science \(\& \) Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, China, e-mail: <span class="tt">chaghoubsoraya@yahoo.fr</span>. </p>
<p>\(^\bullet \)Laboratory of Fundamental and Numerical Mathematics, Department of Mathematics, Faculty of Sciences, Setif-1 Ferhat Abbas University, 19000, Algeria, e-mail: <span class="tt">djbenterki@univ-setif.dz</span>. </p>
<h1 id="Introduction">1 Introduction</h1>

<p>The linear programming is one of the most successful topic in operational research, that comes from the modelling power it offers despite the inherent limitation imposed by the linearity of the functions involved, the richness of the theory that it initiated and which allowed the development of extremely efficient algorithms for its resolution, and the stability of available algorithms. There exist two classes of methods for the resolution of linear programming methods, simplex method and interior point methods. In this context, we are interesting in the class of interior point methods. These last methods, have as a principle the construction of a series of interior points of the feasible domain which from a strictly feasible initial point converges towards the optimal solution. We classify them in three categories: affine method <span class="cite">
	[
	<a href="#id" >7</a>
	]
</span>, projective method with potential reduction of Karmarkar <span class="cite">
	[
	<a href="#bn" >1</a>
	, 
	<a href="#bby" >2</a>
	, 
	<a href="#k84" >8</a>
	]
</span> and central trajectory of logarithmic barrier type <span class="cite">
	[
	<a href="#bby1" >3</a>
	, 
	<a href="#bby2" >4</a>
	, 
	<a href="#cm" >5</a>
	, 
	<a href="#bnm" >6</a>
	, 
	<a href="#lmb" >9</a>
	, 
	<a href="#mb07" >10</a>
	]
</span>. In this paper, we are interesting in the last category. </p>
<p>The aim of this paper is to present a comparative numerical study between line search methods and majorant function to compute the step-size along the direction in barrier logarithmic methods for the following linear programming problem:</p>
<div class="displaymath" id="a0000000002">
  \begin{equation*}  (D)\left\{  \begin{array}{l} \min b^{t}y \\ A^{t}y\geqslant c \\ y\in \mathbb {R} ^{m},\end{array}\right. \end{equation*}
</div>
<p>where \(A\in \mathbb {R}^{m\times n},\) such that \(\operatorname {rank}(A)=m{\lt}n\), \(b\in \mathbb {R}^{m},\) \(c\in \mathbb {R}^{n}\). </p>
<p>We denote by \(S_{D}=\{ y\in \mathbb {R}^{m}\, :\, A^{t}y-c\geq 0\} \), the feasible solution set of \((D)\). </p>
<p>\(S_{D}^{0}=\{ y\in \mathbb {R}^{m}\, :\, A^{t}y-c{\gt}0\} \), the strictly feasible solution set of \((D)\). </p>
<p>In the following, we suppose that the set \(S_{D}^{0}\) is not empty. The problem \((D)\) is approximated by a series of perturbed problems without constraints defined by </p>
<div class="displaymath" id="a0000000003">
  \begin{equation*}  (D_{r})\left\{  \begin{array}{l} \min f_{r}(y) \\ y\in \mathbb {R} ^{m},\end{array}\right. \end{equation*}
</div>
<p>where \(r{\gt}0\) is a barrier parameter and \(f_{r}\) is a barrier function defined by </p>
<div class="displaymath" id="a0000000004">
  \begin{equation*}  f_{r}(y)=\left\{  \begin{array}{ll} b^{t}y+nr\ln r-r\sum \limits _{i=1}^{n}\ln \langle e_{i},A^{t}y-c\rangle , &  if \  A^{t}y-c{\gt}0 \\ +\infty , &  otherwise,\end{array}\right. \end{equation*}
</div>
<p>where \(e_{i}\) are the elements of the canonical base in \(\mathbb {R}^{n}\). </p>
<p>The paper is organized as follows. In Section \(2\), we present the results for the existence and the uniqueness of the optimal solution of \((D_{r})\) given by Menniche <i class="it">et al.</i> <span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span>, as well as the convergence of the problem \((D_{r})\) towards the problem \((D)\). In Section \(3\), we describe the logarithmic barrier algorithm based on the Newtons approach, and the majorant function proposed by Menniche <i class="it">et al.</i> in <span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span>. Section \(4\) reports and compares the numerical test results obtained by the proposed algorithm. Finally, a conclusion and perspectives are drawn in Section \(5\). </p>
<h1 id="a0000000005">2 Existence and uniqueness of the solution of the problem \((D_{\lowercase {r}}) \)</h1>
<p> In the following lemma, we give the result of existence and uniqueness of the optimal solution of the problem \((D_{r}) \) <div class="lemma_thmwrapper " id="s">
  <div class="lemma_thmheading">
    <span class="lemma_thmcaption">
    Lemma
    </span>
    <span class="lemma_thmlabel">1</span>
  </div>
  <div class="lemma_thmcontent">
  <p><span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> Let \(f_{r}\) be inf-compact and strictly convex, therefore the problem \((D_{r})\) admits a unique optimal solution. </p>

  </div>
</div> </p>
<p>Menniche <i class="it">et al.</i> <span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> proved that the function \(f_{r}\) is inf-compact and strictly convex, therefore \((D_{r})\) admits a unique optimal solution, and they gave the following Lemma that ensures the convergence of \((D_{r})\) to \((D)\). </p>
<h2 id="a0000000006">2.1 Convergence of \((D_{r})\) to \((D)\)</h2>
<p><div class="lemma_thmwrapper " id="a0000000007">
  <div class="lemma_thmheading">
    <span class="lemma_thmcaption">
    Lemma
    </span>
    <span class="lemma_thmlabel">2</span>
  </div>
  <div class="lemma_thmcontent">
  <p><span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> For \(r{\gt}0\), let \(y_{r}\) an optimal solution of the problem \((D_{r})\), then there exist \(y\in S_{D}\) an optimal solution of \((D)\) such that: \(\lim _{r\rightarrow 0}y_{r}=y\). </p>

  </div>
</div> </p>
<p>As \((D_{r})\) is a strictly convex problem, then the conditions of KKT are necessary and sufficient. Then, solving the problem \((D_{r})\) is equivalent to solve the nonlinear system </p>
<div class="displaymath" id="a0000000008">
  \begin{equation*}  \nabla f_{r}(y_{r})=0 \end{equation*}
</div>
<h1 id="a0000000009">3 Logarithmic barrier method to solve the perturbed problem</h1>
<p>We use a logarithmic barrier interior point method. This type of methods are based on the optimality conditions which are necessary and sufficient, they consist of constructing a sequence of iterate </p>
<div class="displaymath" id="a0000000010">
  \begin{equation*}  y_{k+1}=y_{k}+t_{k}d_{k}, \end{equation*}
</div>
<p> where the descent direction \(d_{k}\) is the solution of the system </p>
<div class="displaymath" id="a0000000011">
  \begin{equation*}  H_{k}d_{k}=-\nabla f_{r}(y_{r}), \end{equation*}
</div>
<p> and \(t_{k}\) is the displacement step chosen in such a way that \(y_{k+1}\) be strictly feasible <i class="it">i.e.</i>, \(y_{k}+t_{k}d_{k}\) satisfying the condition \(A^{t}(y_{k}+t_{k}d_{k})-c{\gt}0.\) </p>
<h2 id="a0000000012">3.1 Prototype algorithm</h2>
<p>In the following, we consider \(y_{k}\) instead of \(y_{rk}\) and \(y\) instead of \(y_{r}\). </p>
<p><b class="bfseries">Begin algorithm</b> </p>
<p><b class="bfseries">Initialization</b>: \(y_{0}\) is a strictly feasible solution of \((D)\), \(d_{0}\in \mathbb {R}^m, \varepsilon \) a given precision, \(k=0.\) </p>
<p><b class="bfseries">While</b> \(|b^{t}d_k|{\gt}\varepsilon \) <b class="bfseries">do</b> </p>
<p>- Resolve the system \(H_{k}d_{k}=-\nabla f_{r}(y_{k}).\) </p>
<p>- Compute the displacement step \(t_{k}\). </p>
<p>- Take \(y_{k+1}=y_{k}+t_{k}d_{k}\) and \(k=k+1\). </p>
<p><b class="bfseries">End While.</b> </p>
<p><b class="bfseries">End algorithm.</b> </p>
<h2 id="a0000000013">3.2 Effective computation of the displacement step</h2>
<p>We propose two strategies to compute the displacement step: </p>
<h3 id="a0000000014">Line search method (LR)</h3>
<p>Such as the method of Goldstein-Armijo, Fibonacci, Wolfe,... etc. They are based on the minimization of the unidimensional function</p>
<div class="displaymath" id="a0000000015">
  \begin{equation*}  \varphi (t)=\underset {t{\gt}0}{\min }f_{r}(y+td). \end{equation*}
</div>
<p>Unfortunately, they are expensive in computational volume. </p>
<h3 id="a0000000016">Principle of majorant function</h3>
<p>A majorant function \(\hat{\theta }\) must be close to</p>
<div class="displaymath" id="a0000000017">
  \begin{equation*}  \theta (t)=\tfrac {1}{r}\left[ f_{r}(y+td)-f_{r}(y)\right], \end{equation*}
</div>
<p> which must give the \(\underset {t}{\min \, }\hat{ \theta }(t)\) in \([0,\hat{t}]\) by a simple and easy manner. </p>
<p>Menniche <i class="it">et al.</i> <span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> gave a simple form for the function \(\theta \), which is presented in the following lemma: </p>
<p><div class="lemma_thmwrapper " id="a0000000018">
  <div class="lemma_thmheading">
    <span class="lemma_thmcaption">
    Lemma
    </span>
    <span class="lemma_thmlabel">3</span>
  </div>
  <div class="lemma_thmcontent">
  <p><span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> Let \(\hat{t}=\sup \{ t,1+tz_{i} \} \) with \(z_{i}=\frac{\langle e_{i},A^{t}d\rangle }{\langle e_{i},A^{t}y-c\rangle },\) \(\forall i=1,...,n\). For all \(t\in \lbrack 0,\hat{t}],\) the function \(\theta (t)\) is well defined and written in the following form:</p>
<div class="displaymath" id="a0000000019">
  \begin{equation*}  \theta (t)=t\left(\sum \limits _{i=1}^{n}z_{i}-\Vert z\Vert ^{2}\right) -\sum \limits _{i=1}^{n}\ln (1+tz_{i}), \qquad t \in [0,\widehat{t}[. \end{equation*}
</div>
<p>Furthermore, \(\theta (t)\) verifies the following properties :</p>
<div class="displaymath" id="a0000000020">
  \begin{equation*}  \theta (0)=0,\Vert z\Vert ^{2}=\theta ^{^{\prime \prime }}(0)=-\theta ^{^{\prime }}(0). \end{equation*}
</div>

  </div>
</div> </p>
<h2 id="a0000000021">3.3 Majorant function</h2>
<p>In 2017, Menniche <i class="it">et al.</i> <span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> proposed three majorant functions. In this paper, we are interested in their best majorant function defined as:</p>
<div class="displaymath" id="a0000000022">
  \begin{equation*}  \hat{\theta _{0}}(t)=t\gamma -(n-1)\ln (1+t\alpha )-\ln (1+t\beta ) \end{equation*}
</div>
<p> such as</p>
<div class="displaymath" id="a0000000023">
  \begin{equation*} \begin{array}{ll} \gamma = &  n\overline{z}-\|  z\|  ^{2} \\ \alpha = &  \overline{z}+\frac{\sigma _{z}}{\sqrt{n-1}} \\ \beta = &  \overline{z}-\sigma _{z}\sqrt{n-1}\end{array}\end{equation*}
</div>
<p>In addition, they proved in <span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> that the majorant function \(\hat{\theta _{0}}\) is defined and convex on \([0,\hat{t}],\) \(\theta (t){\lt}\hat{\theta _{0}}(t)\) (\(\hat{\theta _{0}}\) majorant function of \(\theta \) on \([0,\hat{t}]\)), and the function \(\hat{\theta _{0}}\) verifies the following properties:</p>
<div class="displaymath" id="a0000000024">
  \begin{equation*}  \hat{\theta _{0}}(0)=0,\quad \Vert z\Vert ^{2}=\hat{\theta _{0}}^{{\prime \prime }}(0)=-\hat{\theta _{0}}^{{\prime }}(0). \end{equation*}
</div>
<p>The majorant function \(\hat{\theta _{0}}\) reaches its minimum at the point </p>
<div class="displaymath" id="a0000000025">
  \begin{equation*}  t^{\ast }=b_{0}-\sqrt{b_{0}^{2}-c_{0}} \end{equation*}
</div>
<p>where </p>
<div class="displaymath" id="a0000000026">
  \begin{equation*}  b_{0}=\tfrac {1}{2}(\tfrac {n}{\gamma }-\tfrac {1}{\alpha }-\tfrac {1}{\beta })\quad \text{ and}\quad c_{0}=-\tfrac {\|  z\|  ^{2}}{\gamma \alpha \beta }. \end{equation*}
</div>
<p><div class="lemma_thmwrapper " id="a0000000027">
  <div class="lemma_thmheading">
    <span class="lemma_thmcaption">
    Lemma
    </span>
    <span class="lemma_thmlabel">4</span>
  </div>
  <div class="lemma_thmcontent">
  <p><span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> Let \(y_{k+1}\) and \(y_{k}\) are two strictly feasible solutions of \((D_{r})\), obtained respectively at the iteration \(k+1\) and \(k\), so we have \(f_{r}(y_{k+1})\leq f_{r}(y_{k})\). </p>

  </div>
</div> </p>
<h1 id="a0000000028">4 Numerical tests</h1>
<p>In this part, we present comparative numerical tests to confirm and consolidate the numerical performances of the best majorant function \(\hat{\theta _{0}}\) given in <span class="cite">
	[
	<a href="#mb07" >10</a>
	]
</span> with respect to line search method of Wolfe. We have tested examples of both fixed and variable size. The tested examples are implemented in MATLAB, with a precision \(\varepsilon \in [10^{-6},10^{-2}].\) </p>
<h3 id="a0000000029">Examples with fixed size</h3>
<p><div class="example_thmwrapper " id="a0000000030">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">5</span>
  </div>
  <div class="example_thmcontent">
  <p>\(A=\left( \begin{smallmatrix} 1 &  0 &  0 &  0 \\ 0 &  1 &  0 &  0\end{smallmatrix}\right) ,\) \(b=(\begin{array}{cc} 2, &  2\end{array})^{t},\) \(c=(\begin{array}{cccc} 1, &  1, &  -1, &  -1\end{array})^{t}\). </p>
<p>- The initial strictly feasible solution is \(y_{0}=(\begin{array}{cc} 1.5, &  1.5\end{array})^{t}\) </p>
<p>- The optimal solution found is : \(y^{\ast }=(\begin{array}{cc} 1, &  1\end{array})^{t}\) after : </p>
<p>- \(13\) iterations in \(0.100\) \(s\) using the line search. </p>
<p>- \(17\) iterations in \(0.053\) \(s\) using majorant function. </p>

  </div>
</div> </p>
<p><div class="example_thmwrapper " id="a0000000031">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">6</span>
  </div>
  <div class="example_thmcontent">
  <p>\(A=\left( \begin{smallmatrix} -2 &  -1 &  0 &  1 &  0 &  0 \\ 0 &  0 &  -1 &  0 &  0 &  1 \\ 0 &  -1 &  -1 &  -1 &  -1 &  -1\end{smallmatrix}\right) ,\) </p>
<p>\(b=(\begin{array}{ccc} 0,&  0,&  -1\end{array})^{t},\) \(c=(\begin{array}{cccccc} -3, &  1, &  -1, &  0, &  0, &  0\end{array})^{t}\) </p>
<p>- The initial strictly feasible solution is \(y_{0}=(\begin{array}{ccc} -1, &  -1, &  -2\end{array})^{t}\) </p>
<p>- The optimal solution found is : \(y^{\ast }=(\begin{array}{ccc} -0.5, &  -0.0713, &  -0.5\end{array})^{t}\) after: </p>
<p>- \(33\) iterations in \(0.128\) \(s\) using the line search. </p>
<p>- \(9\) iterations in \(0.063\) \(s\) using majorant function. </p>

  </div>
</div> </p>
<p><div class="example_thmwrapper " id="a0000000032">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">7</span>
  </div>
  <div class="example_thmcontent">
  <p>\(A=\left( \begin{smallmatrix} -1 &  0 &  4 &  -3 &  -1 &  -1 &  -1 &  0 &  0 &  0 &  0 &  0 \\ -5 &  -3 &  -1 &  0 &  1 &  -3 &  0 &  -1 &  0 &  0 &  0 &  0 \\ -4 &  -5 &  3 &  -3 &  4 &  -1 &  0 &  0 &  -1 &  0 &  0 &  0 \\ 0 &  1 &  0 &  -2 &  -1 &  5 &  0 &  0 &  0 &  -1 &  0 &  0 \\ -2 &  -1 &  -1 &  -1 &  -2 &  -2 &  0 &  0 &  0 &  0 &  -1 &  0 \\ -2 &  3 &  -2 &  1 &  -4 &  -5 &  0 &  0 &  0 &  0 &  0 &  -1\end{smallmatrix}\right) \) </p>
<p>\(b=(\begin{array}{cccccc} -1, &  -4, &  -4, &  -5, &  -7, &  -5\end{array})^{t},\) </p>
<p>\(c=(\begin{array}{cccccccccccc} 4, &  5, &  1, &  3, &  -5, &  8, &  0, &  0, &  0, &  0, &  0, &  0\end{array})^{t}\) </p>
<p>- The initial strictly feasible solution is \(y_{0}=(-0.5,\,  -4,\,  -1,\,  -1,\,  -1,\,  -1)^{t}\) </p>
<p>- The optimal solution found is: \(y^{\ast }=(\begin{array}{cccccc} -0.5, &  -1.5, &  0, &  0, &  -1.5, &  0\end{array})^{t}\) after: </p>
<p>- \(34\) iterations in \(0.306\) \(s\) using the line search. </p>
<p>- \(25\) iterations in \(0.009\) \(s\) using majorant function. </p>

  </div>
</div> </p>
<p><div class="example_thmwrapper " id="Tab:one">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">8</span>
  </div>
  <div class="example_thmcontent">
  <p>\(A=\left( \begin{smallmatrix} -1 &  -6 &  -11 &  -1 &  -3 \\ -2 &  -7 &  -12 &  -10 &  -9 \\ -3 &  -8 &  -13 &  -20 &  -27 \\ -4 &  -9 &  -14 &  -30 &  -60 \\ -5 &  -10 &  -15 &  -40 &  -45 \\ -5 &  -5 &  -6 &  -50 &  -60 \\ -4 &  -2 &  -7 &  -60 &  -75 \\ -3 &  -8 &  -80 &  -80 &  -8 \\ -2 &  -3 &  -90 &  -90 &  -9 \\ -1 &  -1 &  -10 &  -10 &  -46 \\ -1 &  0 &  0 &  0 &  0 \\ 0 &  -1 &  0 &  0 &  0 \\ 0 &  0 &  -1 &  0 &  0 \\ 0 &  0 &  0 &  -1 &  0 \\ 0 &  0 &  0 &  0 &  -1\end{smallmatrix}\right) ^{t}\) </p>
<p>\(b_{i}=-10^{4},\) \(i=1,...,5,\) </p>
<p>\(c=(-1,\,  -1, \,  -1, \,  -1,\,  -1, \,  -1, \,  -1, \,  -1, \,  -1, \,  -1, \,  0, \,  0, \,  0, \,  0,\,  0)^{t}\) </p>
<p>- The initial strictly feasible solution is \(y_{0}=(\begin{array}{ccccc} -1, &  -1, &  -1, &  -1, &  -1\end{array})^{t}\) </p>
<p>- The optimal solution found is : \(y^{\ast }=(\begin{array}{ccccc} 0, &  0, &  -0.0888, &  0, &  -0.0078\end{array})^{t}\) after: </p>
<p>- \(22\) iterations in \(0.170\) \(s\) using the line search. </p>
<p>- \(42\) iterations in \(0.009\) \(s\) using majorant function. </p>
<p>We note by: </p>
<p>- \(LR\) : the strategy that uses line search of Wolfe. </p>
<p>- \(MF\) : the strategy that uses majorant function. </p>
<p>- \(Itr\) : the number of iterations needed to find an optimal solution. </p>
<p>- \(time\): run time in seconds. </p>

  </div>
</div> </p>
<p>The following table summarizes the obtained results. </p>
<div class="table"  id="a0000000033">
   <div class="centered"><small class="footnotesize"><table class="tabular">
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(method\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(LR\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(method\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(MF\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:center" 
        rowspan=""
        colspan="">
      <p> \(ex\left( m,n\right) \) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(Itr\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="1">
      <p> \(time\left( s\right) \) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(Itr\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="1">
      <p> \(time\left( s\right) \) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p>\(ex5\left( 2,4\right) \) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(13\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="1">
      <p> \(0.100\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(17\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="1">
      <p> \(0.053\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p>\(ex6\left( 3,6\right) \) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(33\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="1">
      <p> \(0.128\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(9\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="1">
      <p> \(0.063\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p>\(ex7\left( 6,12\right) \) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(34\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="1">
      <p> \(0.306\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center" 
        rowspan=""
        colspan="">
      <p> \(25\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="1">
      <p> \(0.009\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p>\(ex8\left( 5,15\right) \) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(22\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="1">
      <p> \(0.170\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(42\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="1">
      <p> \(0.009\) </p>

    </td>
  </tr>
</table></small><figcaption>
  <span class="caption_title">Table</span> 
  <span class="caption_ref">1</span> 
  <span class="caption_text">Numerical results for the fixed size examples.</span> 
</figcaption></div>
</div>
<h3 id="a0000000034">Example with variable size</h3>
<p><div class="example_thmwrapper " id="Tab:two">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">9</span>
  </div>
  <div class="example_thmcontent">
  <div class="displaymath" id="a0000000035">
  \begin{equation*}  (D)\left\{  \begin{array}{l} \min \sum \limits _{i=1}^{m}2y_{i} \\ y_{i}-1\geq 0,i=1,...,m,n=2m.\end{array}\right. \end{equation*}
</div>
<p>\(y_{0}=(\begin{array}{cccc} 1.5, &  1.5, &  ..., &  1.5\end{array})^{t}\in \mathbb {R} ^{m}\) is strictly feasible. </p>
<p>The optimal solution is \(y^{\ast }=(\begin{array}{cccc} 1, &  1, &  ..., &  1\end{array})^{t}\in \mathbb {R} ^{m}\). </p>

  </div>
</div> </p>
<p>The following table summarizes the results obtained for the different sizes. </p>
<div class="table"  id="a0000000036">
   <div class="centered"><small class="footnotesize"><table class="tabular">
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(size(m,n)\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(method\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(LR\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(method\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(MF\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left" 
        rowspan=""
        colspan="">
      <p> \((m,n)\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(Itr\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(time\left( s\right) \) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(Itr\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(time\left( s\right) \) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p>\((100,200)\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(90\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(14.426\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(22\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(0.406\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p>\((200,400)\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(89\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(120.047\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(23\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(34.562\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p>\((300,600)\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(72\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(671.713\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(23\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left" 
        rowspan=""
        colspan="">
      <p> \(132.719\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p>\((400,800)\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(83\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(1312.761\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(24\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(305.578\) </p>

    </td>
  </tr>
</table></small><figcaption>
  <span class="caption_title">Table</span> 
  <span class="caption_ref">2</span> 
  <span class="caption_text">Numerical results for the variable size example.</span> 
</figcaption></div>
</div>
<h1 id="a0000000037">5 Conclusion and perspectives</h1>
<p>According to the numerical study that we have done, we conclude that the strategy of the majorant function seems more effective in time and number of iterations than that of the line search, these results encourage us to look for another better approximate functions to further improve the behaviour of interior point algorithms, and extend this study to other optimization problems that are not necessarily linear. </p>
<p><div class="acknowledgement_thmwrapper " id="a0000000038">
  <div class="acknowledgement_thmheading">
    <span class="acknowledgement_thmcaption">
    Acknowledgements
    </span>
  </div>
  <div class="acknowledgement_thmcontent">
  <p>The authors would like to thank the anonymous referee and the editor for their suggestions, which lead to significant improvement of the manuscript. </p>

  </div>
</div> </p>
<p><small class="footnotesize">  </small></p>
<div class="bibliography">
<h1>Bibliography</h1>
<dl class="bibliography">
  <dt><a name="bn">1</a></dt>
  <dd><p><a href ="https://doi.org/10.1051/ro:2007006"> <i class="sc">D. Benterki</i>, <i class="sc">J.P. Crouzeix</i>, <i class="sc">B. Merikhi</i>, <i class="it">A numerical feasible interior point method for linear semidefinite programs</i>, RAIRO-Operation research, <b class="bf">41</b>, (2007), pp.&#160;49–59. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="bby">2</a></dt>
  <dd><p><a href ="https://doi.org/10.1016/j.orl.2018.02.004"> <i class="sc">M. Bouafia</i>, <i class="sc">D. Benterki</i>, <i class="sc">A. Yassine</i>, <i class="it">A new efficient short-step projective interior point method for linear programming</i>, Operations Research Letters <b class="bf">46</b>, (2018), pp.&#160;291–294. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="bby1">3</a></dt>
  <dd><p><a href ="https://doi.org/10.1007/s11590-017-1170-5"> <i class="sc">M. Bouafia</i>, <i class="sc">D. Benterki</i>, <i class="sc">A. Yassine</i>, <i class="it">An efficient parameterized logarithmic kernel function for linear optimization</i>, Optim. Lett, <b class="bf">12</b>, (2018), pp.&#160;1079–1097. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="bby2">4</a></dt>
  <dd><p><a href ="https://doi.org/10.1007/s11081-019-09467-w"> <i class="sc">M. Bouafia</i>, <i class="sc">A. Yassine</i>, <i class="it">An efficient twice parameterized trigonometric kernel function for linear optimization</i>, Optimization and Engineering, (2019). <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="cm">5</a></dt>
  <dd><p><a href ="https://doi.org/10.1051/ro/2018061"> <i class="sc">L.B. Cherif</i>, <i class="sc">B. Meikhi</i>, <i class="it">A penalty method for nonlinear programming</i>, RAIRO-Oper. Res. <b class="bf">53</b>, (2019) pp.&#160;29–38. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="bnm">6</a></dt>
  <dd><p><a href ="https://doi.org/10.1051/ro:2008005"> <i class="sc">J.P. Crouzeix</i>, <i class="sc">B. Merikhi</i>, <i class="it">Algorithm barrier method for semidefinite programming</i>, RAIRO-Operations Research, <b class="bf">42</b>, (2008) pp.&#160;123–139. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="id">7</a></dt>
  <dd><p><i class="sc">I.I. Dikin</i>, <i class="it">Iterative solution of problems of linear and quadratic programming</i>, Doklady Akademiia Nauk SSSR, <b class="bf">174</b> (1967) pp.&#160;747–748. </p>
</dd>
  <dt><a name="k84">8</a></dt>
  <dd><p><a href ="https://doi.org/10.1145/800057.808695"> <i class="sc">N.K. Karmarkar</i>, <i class="it">A new polynomial-time algorithm for linear programming</i>, Proc. of the 16\(^{{th}}\) Annual ACM Symposium on Theory of Computing, <b class="bf">4</b>, (1984), pp.&#160;373–395. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="lmb">9</a></dt>
  <dd><p><a href ="https://doi.10.17516/1997-1397-2018-11-3-300-312"> <i class="sc">A. Leulmi</i>, <i class="sc">B. Meikhi</i>, <i class="sc">D. Benterki</i>, <i class="it">Study of a logarithmic barrier approach for linear semidefinite programming</i>, Journal of Siberian Federal University. Mathematics and Physics, <b class="bf">11</b>, (2018), pp.&#160;300–312. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="mb07">10</a></dt>
  <dd><p><a href ="https://doi.org/10.1016/j.cam.2016.05.025"> <i class="sc">L. Menniche</i>, <i class="sc">D. Benterki</i>, <i class="it">A logarithmic barrier approach for linear programming</i>, J. Comput. Appl. Math., <b class="bf">312</b>, (2017), pp.&#160;267–275. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
</dl>


</div>
</div> <!--main-text -->
</div> <!-- content-wrapper -->
</div> <!-- content -->
</div> <!-- wrapper -->

<nav class="prev_up_next">
</nav>

<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/jquery.min.js"></script>
<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/plastex.js"></script>
<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/svgxuse.js"></script>
</body>
</html>