Comparative numerical study between line search methods and majorant functions in barrier logarithmic methods for linear programming

Soraya Chaghoub$^\ast $ Djamel Benterki$^\bullet $

October 13, 2019; accepted: April 30, 2020; published online: August 11, 2020.

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.

MSC. 90C22, 90C51.

Keywords. Linear programming, Interior point methods, Line search, Majorant function.

$^\ast $School of Mathematical Science $\& $ Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, China, e-mail: chaghoubsoraya@yahoo.fr.

$^\bullet $Laboratory of Fundamental and Numerical Mathematics, Department of Mathematics, Faculty of Sciences, Setif-1 Ferhat Abbas University, 19000, Algeria, e-mail: djbenterki@univ-setif.dz.

1 Introduction

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 [ 7 ] , projective method with potential reduction of Karmarkar [ 1 , 2 , 8 ] and central trajectory of logarithmic barrier type [ 3 , 4 , 5 , 6 , 9 , 10 ] . In this paper, we are interesting in the last category.

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:

\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*}

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}$.

We denote by $S_{D}=\{ y\in \mathbb {R}^{m}\, :\, A^{t}y-c\geq 0\} $, the feasible solution set of $(D)$.

$S_{D}^{0}=\{ y\in \mathbb {R}^{m}\, :\, A^{t}y-c{\gt}0\} $, the strictly feasible solution set of $(D)$.

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

\begin{equation*} (D_{r})\left\{ \begin{array}{l} \min f_{r}(y) \\ y\in \mathbb {R} ^{m},\end{array}\right. \end{equation*}

where $r{\gt}0$ is a barrier parameter and $f_{r}$ is a barrier function defined by

\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*}

where $e_{i}$ are the elements of the canonical base in $\mathbb {R}^{n}$.

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 et al. [ 10 ] , 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 et al. in [ 10 ] . Section $4$ reports and compares the numerical test results obtained by the proposed algorithm. Finally, a conclusion and perspectives are drawn in Section $5$.

2 Existence and uniqueness of the solution of the problem $(D_{\lowercase {r}}) $

In the following lemma, we give the result of existence and uniqueness of the optimal solution of the problem $(D_{r}) $

Lemma 1

[ 10 ] Let $f_{r}$ be inf-compact and strictly convex, therefore the problem $(D_{r})$ admits a unique optimal solution.

Menniche et al. [ 10 ] 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)$.

2.1 Convergence of $(D_{r})$ to $(D)$

Lemma 2

[ 10 ] 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$.

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

\begin{equation*} \nabla f_{r}(y_{r})=0 \end{equation*}

3 Logarithmic barrier method to solve the perturbed problem

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

\begin{equation*} y_{k+1}=y_{k}+t_{k}d_{k}, \end{equation*}

where the descent direction $d_{k}$ is the solution of the system

\begin{equation*} H_{k}d_{k}=-\nabla f_{r}(y_{r}), \end{equation*}

and $t_{k}$ is the displacement step chosen in such a way that $y_{k+1}$ be strictly feasible i.e., $y_{k}+t_{k}d_{k}$ satisfying the condition $A^{t}(y_{k}+t_{k}d_{k})-c{\gt}0.$

3.1 Prototype algorithm

In the following, we consider $y_{k}$ instead of $y_{rk}$ and $y$ instead of $y_{r}$.

Begin algorithm

Initialization: $y_{0}$ is a strictly feasible solution of $(D)$, $d_{0}\in \mathbb {R}^m, \varepsilon $ a given precision, $k=0.$

While $|b^{t}d_k|{\gt}\varepsilon $ do

- Resolve the system $H_{k}d_{k}=-\nabla f_{r}(y_{k}).$

- Compute the displacement step $t_{k}$.

- Take $y_{k+1}=y_{k}+t_{k}d_{k}$ and $k=k+1$.

End While.

End algorithm.

3.2 Effective computation of the displacement step

We propose two strategies to compute the displacement step:

Line search method (LR)

Such as the method of Goldstein-Armijo, Fibonacci, Wolfe,... etc. They are based on the minimization of the unidimensional function

\begin{equation*} \varphi (t)=\underset {t{\gt}0}{\min }f_{r}(y+td). \end{equation*}

Unfortunately, they are expensive in computational volume.

Principle of majorant function

A majorant function $\hat{\theta }$ must be close to

\begin{equation*} \theta (t)=\tfrac {1}{r}\left[ f_{r}(y+td)-f_{r}(y)\right], \end{equation*}

which must give the $\underset {t}{\min \, }\hat{ \theta }(t)$ in $[0,\hat{t}]$ by a simple and easy manner.

Menniche et al. [ 10 ] gave a simple form for the function $\theta $, which is presented in the following lemma:

Lemma 3

[ 10 ] 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:

\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*}

Furthermore, $\theta (t)$ verifies the following properties :

\begin{equation*} \theta (0)=0,\Vert z\Vert ^{2}=\theta ^{^{\prime \prime }}(0)=-\theta ^{^{\prime }}(0). \end{equation*}

3.3 Majorant function

In 2017, Menniche et al. [ 10 ] proposed three majorant functions. In this paper, we are interested in their best majorant function defined as:

\begin{equation*} \hat{\theta _{0}}(t)=t\gamma -(n-1)\ln (1+t\alpha )-\ln (1+t\beta ) \end{equation*}

such as

\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*}

In addition, they proved in [ 10 ] 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:

\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*}

The majorant function $\hat{\theta _{0}}$ reaches its minimum at the point

\begin{equation*} t^{\ast }=b_{0}-\sqrt{b_{0}^{2}-c_{0}} \end{equation*}

where

\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*}

Lemma 4

[ 10 ] 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})$.

4 Numerical tests

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 [ 10 ] 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}].$

Examples with fixed size

Example 5

$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}$.

- The initial strictly feasible solution is $y_{0}=(\begin{array}{cc} 1.5, & 1.5\end{array})^{t}$

- The optimal solution found is : $y^{\ast }=(\begin{array}{cc} 1, & 1\end{array})^{t}$ after :

- $13$ iterations in $0.100$ $s$ using the line search.

- $17$ iterations in $0.053$ $s$ using majorant function.

Example 6

$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) ,$

$b=(\begin{array}{ccc} 0,& 0,& -1\end{array})^{t},$ $c=(\begin{array}{cccccc} -3, & 1, & -1, & 0, & 0, & 0\end{array})^{t}$

- The initial strictly feasible solution is $y_{0}=(\begin{array}{ccc} -1, & -1, & -2\end{array})^{t}$

- The optimal solution found is : $y^{\ast }=(\begin{array}{ccc} -0.5, & -0.0713, & -0.5\end{array})^{t}$ after:

- $33$ iterations in $0.128$ $s$ using the line search.

- $9$ iterations in $0.063$ $s$ using majorant function.

Example 7

$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) $

$b=(\begin{array}{cccccc} -1, & -4, & -4, & -5, & -7, & -5\end{array})^{t},$

$c=(\begin{array}{cccccccccccc} 4, & 5, & 1, & 3, & -5, & 8, & 0, & 0, & 0, & 0, & 0, & 0\end{array})^{t}$

- The initial strictly feasible solution is $y_{0}=(-0.5,\, -4,\, -1,\, -1,\, -1,\, -1)^{t}$

- The optimal solution found is: $y^{\ast }=(\begin{array}{cccccc} -0.5, & -1.5, & 0, & 0, & -1.5, & 0\end{array})^{t}$ after:

- $34$ iterations in $0.306$ $s$ using the line search.

- $25$ iterations in $0.009$ $s$ using majorant function.

Example 8

$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}$

$b_{i}=-10^{4},$ $i=1,...,5,$

$c=(-1,\, -1, \, -1, \, -1,\, -1, \, -1, \, -1, \, -1, \, -1, \, -1, \, 0, \, 0, \, 0, \, 0,\, 0)^{t}$

- The initial strictly feasible solution is $y_{0}=(\begin{array}{ccccc} -1, & -1, & -1, & -1, & -1\end{array})^{t}$

- The optimal solution found is : $y^{\ast }=(\begin{array}{ccccc} 0, & 0, & -0.0888, & 0, & -0.0078\end{array})^{t}$ after:

- $22$ iterations in $0.170$ $s$ using the line search.

- $42$ iterations in $0.009$ $s$ using majorant function.

We note by:

- $LR$ : the strategy that uses line search of Wolfe.

- $MF$ : the strategy that uses majorant function.

- $Itr$ : the number of iterations needed to find an optimal solution.

- $time$: run time in seconds.

The following table summarizes the obtained results.

	$method$	$LR$	$method$	$MF$
$ex\left( m,n\right) $	$Itr$	$time\left( s\right) $	$Itr$	$time\left( s\right) $
$ex5\left( 2,4\right) $	$13$	$0.100$	$17$	$0.053$
$ex6\left( 3,6\right) $	$33$	$0.128$	$9$	$0.063$
$ex7\left( 6,12\right) $	$34$	$0.306$	$25$	$0.009$
$ex8\left( 5,15\right) $	$22$	$0.170$	$42$	$0.009$

Table 1 Numerical results for the fixed size examples.

Example with variable size

Example 9

\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*}

$y_{0}=(\begin{array}{cccc} 1.5, & 1.5, & ..., & 1.5\end{array})^{t}\in \mathbb {R} ^{m}$ is strictly feasible.

The optimal solution is $y^{\ast }=(\begin{array}{cccc} 1, & 1, & ..., & 1\end{array})^{t}\in \mathbb {R} ^{m}$.

The following table summarizes the results obtained for the different sizes.

$size(m,n)$	$method$	$LR$	$method$	$MF$
$(m,n)$	$Itr$	$time\left( s\right) $	$Itr$	$time\left( s\right) $
$(100,200)$	$90$	$14.426$	$22$	$0.406$
$(200,400)$	$89$	$120.047$	$23$	$34.562$
$(300,600)$	$72$	$671.713$	$23$	$132.719$
$(400,800)$	$83$	$1312.761$	$24$	$305.578$

Table 2 Numerical results for the variable size example.

5 Conclusion and perspectives

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.

Acknowledgements

The authors would like to thank the anonymous referee and the editor for their suggestions, which lead to significant improvement of the manuscript.

Bibliography

1: D. Benterki, J.P. Crouzeix, B. Merikhi, A numerical feasible interior point method for linear semidefinite programs, RAIRO-Operation research, 41, (2007), pp. 49–59. $\includegraphics[scale=0.1]{ext-link.png}$
2: M. Bouafia, D. Benterki, A. Yassine, A new efficient short-step projective interior point method for linear programming, Operations Research Letters 46, (2018), pp. 291–294. $\includegraphics[scale=0.1]{ext-link.png}$
3: M. Bouafia, D. Benterki, A. Yassine, An efficient parameterized logarithmic kernel function for linear optimization, Optim. Lett, 12, (2018), pp. 1079–1097. $\includegraphics[scale=0.1]{ext-link.png}$
4: M. Bouafia, A. Yassine, An efficient twice parameterized trigonometric kernel function for linear optimization, Optimization and Engineering, (2019). $\includegraphics[scale=0.1]{ext-link.png}$
5: L.B. Cherif, B. Meikhi, A penalty method for nonlinear programming, RAIRO-Oper. Res. 53, (2019) pp. 29–38. $\includegraphics[scale=0.1]{ext-link.png}$
6: J.P. Crouzeix, B. Merikhi, Algorithm barrier method for semidefinite programming, RAIRO-Operations Research, 42, (2008) pp. 123–139. $\includegraphics[scale=0.1]{ext-link.png}$
7: I.I. Dikin, Iterative solution of problems of linear and quadratic programming, Doklady Akademiia Nauk SSSR, 174 (1967) pp. 747–748.
8: N.K. Karmarkar, A new polynomial-time algorithm for linear programming, Proc. of the 16$^{{th}}$ Annual ACM Symposium on Theory of Computing, 4, (1984), pp. 373–395. $\includegraphics[scale=0.1]{ext-link.png}$
9: A. Leulmi, B. Meikhi, D. Benterki, Study of a logarithmic barrier approach for linear semidefinite programming, Journal of Siberian Federal University. Mathematics and Physics, 11, (2018), pp. 300–312. $\includegraphics[scale=0.1]{ext-link.png}$
10: L. Menniche, D. Benterki, A logarithmic barrier approach for linear programming, J. Comput. Appl. Math., 312, (2017), pp. 267–275. $\includegraphics[scale=0.1]{ext-link.png}$

	\(method\)	\(LR\)	\(method\)	\(MF\)
\(ex\left( m,n\right) \)	\(Itr\)	\(time\left( s\right) \)	\(Itr\)	\(time\left( s\right) \)
\(ex5\left( 2,4\right) \)	\(13\)	\(0.100\)	\(17\)	\(0.053\)
\(ex6\left( 3,6\right) \)	\(33\)	\(0.128\)	\(9\)	\(0.063\)
\(ex7\left( 6,12\right) \)	\(34\)	\(0.306\)	\(25\)	\(0.009\)
\(ex8\left( 5,15\right) \)	\(22\)	\(0.170\)	\(42\)	\(0.009\)

\(size(m,n)\)	\(method\)	\(LR\)	\(method\)	\(MF\)
\((m,n)\)	\(Itr\)	\(time\left( s\right) \)	\(Itr\)	\(time\left( s\right) \)
\((100,200)\)	\(90\)	\(14.426\)	\(22\)	\(0.406\)
\((200,400)\)	\(89\)	\(120.047\)	\(23\)	\(34.562\)
\((300,600)\)	\(72\)	\(671.713\)	\(23\)	\(132.719\)
\((400,800)\)	\(83\)	\(1312.761\)	\(24\)	\(305.578\)