1 Introduction

The nonlinear programming \((\textit{NLP})\) is a model which traduces many real applications. It can be found in control theory, combinatory optimization. In term of research, it is one of subject treated with fervour, in particular the problem of initialization in problem of optimization [1–8].

Choice of starting primal and dual point is an important practical issue with a significant effect on the robustness of the algorithm. A poor choice \( (x^{0},y^{0},s^{0})\) satisfying only the minimal conditions \(x^{0}>0\) , \( s^{0}>0.\) In interior point methods, the successive iterates should be strictly feasible. In consequence, a major concern is to find an initial primal feasible solution \(x^{0}\) [7, 9]. The object of this paper is the dual problem \((y^{0},s^{0})\).

A nonlinear program in its standard form is of type:

$$\begin{aligned} (\textit{CNLP})~\ \left\{ \begin{array}{c} \min \ f(x) \\ s.t \\ Ax=b,~x\ge 0 \end{array} \right. \end{aligned}$$

where \(f(x)\) is a reel nonlinear function, \(A\in \mathbb {R}^{m\times n}\) with \(rg(A)=m<n,\ c,\ x\ \in \mathbb {R}^{n}\) and \(\ y,~b\in \mathbb {R}^{m},\) and its dual problem

$$\begin{aligned} (\textit{CNLD})~\left\{ \begin{array}{l} \max L(x,y,s) \\ s.t \\ A^{t}y+s=\nabla f(x),~s\ge 0,~y\in \mathfrak {R}^{m}. \end{array} \right. \end{aligned}$$

where \(L(x,y,s)\) is a lagrangian function, \(s\in \mathbb {R}^{n},\) \(y\in \mathbb {R}^{m}\) are the vectors.

Some notations are used throughout the paper and they are as follows. \(\mathfrak {R}^{n~}\), \(\mathfrak {R}_{+}^{n~}\) and \(\mathfrak {R}_{++}^{n~}\) denote the set of vectors with \( n\) components, the set of nonnegative vectors and the set of positive vectors, respectively. \(\mathfrak {R}^{n~\times ~n}\) denotes the set of \(n\times n\) real matrices.\(\left\| \text {.}\right\| _{2}\) denote the Euclidean norm, \(e=(1,\ldots ,1)^{t}\) is the vector of ones in \(\mathfrak {R}^{n}.\)

2 Presentation of the problem

The strict dual feasibility problem associated to the problem \((\textit{CNLD})\) is to find a vector \((y,s)\) such that:

$$\begin{aligned} \begin{array}{ccc} \left[ (y,s)\in \mathfrak {R}^{m+n}:A^{t}y+s=\nabla f(x),~s>0\right]&(\textit{DF}) \end{array} \end{aligned}$$

We poses \(y=y^{+}-y^{-},\) where \(y^{+}>0,~y^{-}>0\).

The problem \((DF)\) is equivalent to the following problem

$$\begin{aligned} \begin{array}{ccc} \left[ (y,s)\in \mathfrak {R}^{m+n}:A^{t}y^{+}-A^{t}y^{-}+s=\nabla f(x),~y^{+}>0,y^{-}>0,~s>0\right]&(\textit{DF}) \end{array} \end{aligned}$$

One way to solve a strictly dual feasible problem consists in introducing an additional variable \(\xi \) as follows:

$$\begin{aligned} (P_{\xi })~\left\{ \begin{array}{c} \min \xi \\ s.t \\ Dd+\xi (\nabla f(x)-Da)=\nabla f(x) \\ d>0,~\xi >0 \end{array} \right. \end{aligned}$$

where \(D\) is the \((n)\times (n+2m)\) matrix defined by \(D=(A^{t},~-A^{t},~I)\), \(a\in \mathfrak {R}_{++}^{n+2m}\) is arbitrary and \(d=(y^{+},~y^{-},~s)\in \mathfrak {R}_{++}^{n+2m}\)

The problem \((P_{\xi })\) can be written as a following linear program:

$$\begin{aligned} (LP_{\xi })~\left\{ \begin{array}{c} \min c{{^{\prime \prime }}t}l \\ s.t \\ D{^{\prime }}l=\nabla f(x) \\ l>0\end{array} \right. \end{aligned}$$

where \(c{^{\prime \prime }}\) \(\in \mathfrak {R}^{n+2m+1}\) is the vector defined by:

$$\begin{aligned} c{^{\prime \prime }}[i]=\left\{ \begin{array}{l} 1,~\text {if}\; i=n+2m+1 \\ 0,\; \text {otherwise} \end{array} \right. \end{aligned}$$

\(D{^{\prime }}\) is the \((n)\times (n+2m+1)\) matrix defined by \(D{^{\prime }}=\left( D,~\nabla f(x)-Da\right) \) and \(l\) \(\in \mathfrak {R}^{n+2m+1}\) is vector such that \(l=\left( d,~\xi \right) .\)

For solving the problem \((LP_{\xi })\), we use the Ye Lustig variant of projective interior point method [5].

Lemma 1

 [5] \(x^{*}\) is a solution of problem \((PF)\) if and only if \((d^{*},~\xi )\) is an optimal solution of problem \((LP_{\xi })\)with \(d\in \mathfrak {R}_{++}^{n+2m}\) and \(\xi \) sufficiently small.

To compute the optimal solution of problem (\(LP_{\xi }\)) , we use only the second phase of the projective interior point method. The corresponding algorithm is:

3 Algorithm for solving (\(LP_{_{\xi }}\))

Description of the algorithm

(a) Initialization: \(\varepsilon >0\) is fixed, \(d^{0}=e,~\xi _{0}\) \( =1\) and \(k=0\)

If \(\left\| Dd-\nabla f(x)\right\| _{2}<\varepsilon \), Stop: \( d^{k}\) is an \(\varepsilon \)-approximate solution of \((DF)\).

If not go to (b).

(b) If \(\xi _{k}<\varepsilon \), Stop: \(d^{k}\) is an \(\varepsilon \) -approximate solution of \((DF)\).

If not go to (c).

(c) Step k

Determinate:

  • \(G_{k}=diag(l^{k}),D=\left[ D,~\nabla f(x)-Da\right] ,r=\frac{1}{\sqrt{(n+2m+1)(n+2m+2)}},\)

  • \(C_{k}=\left[ D^{^{\prime }}G_{k},~-\nabla f(x)\right] \)

  • \(P_{k}=\left[ I-C_{k}^{t}(C_{k}C_{k}^{t})^{-1}C_{k}\right] \left[ G_{k}c{^{\prime \prime }t},~-c{{^{\prime \prime }}t}l^{k}\right] ^{t}\)

Compute:

  • \(z^{k+1}=\frac{e_{n+2m+2}}{n+2m+2}-\alpha _{k}r\frac{P_{k}}{\left\| P_{k}\right\| _{2}}\)

  • \(l^{k+1}=\frac{1}{z^{k+1}\left[ n+2m+2\right] }G_{k}z^{k+1}\left[ n+2m+1 \right] \)

Take:

  • \(\xi _{k}=l^{k+1}\left[ n+2m\right] ,\) and go to (b)

4 Modified algorithm

At iteration \(k\), the original algorithm gives a strictly feasible solution \((d^{k},\xi ^{k})\). To find the next iteration \((d^{k+1},\xi ^{k+1})\), we search a vector \(w^{k}\) such that the vector \(d^{k}+w^{k}\) is a solution of problem \((FD)\), i.e

$$\begin{aligned} D(d^{k}+w^{k})=\nabla f(x) \end{aligned}$$
(1)

and

$$\begin{aligned} d^{k}+w^{k}>0 \end{aligned}$$
(2)

\((1)\) is equivalent to \(Dd^{k}=\nabla f(x)-\xi _{k}q,\) where

$$\begin{aligned} Dw^{k}=\xi _{k}q \end{aligned}$$
(3)

\((3)\) is equivalent to the following convex quadratic optimization problem

$$\begin{aligned} (\textit{COP})~\ \left\{ \begin{array}{c} \min \left\| w^{k}\right\| ^{2} \\ s.t \\ Dw^{k}=\xi _{k}q \end{array} \right. \end{aligned}$$

By optimality condition, we obtain the follwing system

we obtain

\(\theta =-(DD^{t})^{-1}\xi _{k}q\)

deduce

\(w^{k}=-D^{t}\theta =D^{t}(DD^{t})^{-1}\xi _{k}q\).

The calculation of \(w^{k}\) requires the calculation of the inverse of the matrix \((DD^{t})\), which is undesirable in practice, to correct, we proceed as follows, let

$$\begin{aligned} u^{k}=(DD^{t})^{-1}\xi _{k}q \end{aligned}$$

equivalent to the follwing linear symetric definite positive system

$$\begin{aligned} DD^{t}u^{k}=\xi _{k}q \end{aligned}$$

Proposition 1

For all \((d^{k},\xi _{k})\) is a strict feasible solution of \((P_{\xi })\),

if \( \max \left| v_{i}^{k}\right| <1\) then:

$$\begin{aligned} d^{k}+w^{k}>0 \hbox { and } D(d^{k}+w^{k})=\nabla f(x) \end{aligned}$$

where

$$\begin{aligned} v^{k}=-diag\Big (\frac{1}{d^{k}}\Big )D^{t}u^{k} \hbox { and } w^{k} \hbox { is a solution of } (\textit{COP}) \end{aligned}$$

Proof

1. \(\ D(d^{k}+w^{k})=\nabla f(x)\)

let, \(w^{k}\) is a solution of \((\textit{COP}),\) we have

\(w^{k}=D^{t}u^{k}\) and \(u^{k}=\xi _{k}u^{0}\)

$$\begin{aligned} D(d^{k}+w^{k})&= D(d^{k}+D^{t}u^{k}) \\&= Dd^{k}+DD^{t}u^{k} \\&= \nabla f(x)-\xi _{k}\big (\nabla f(x)-Da\big )+\xi _{k}DD^{k}u^{0} \\&= \nabla f(x)-\xi _{k}\big (\nabla f(x)-Da\big )+\xi _{k}\xi _{0}\big (\nabla f(x)-Da\big ) \\&= \nabla f(x). \end{aligned}$$

2. \(d^{k}+w^{k}>0\)

we have

$$\begin{aligned} D(d^{k}+w^{k})=\nabla f(x) \end{aligned}$$

so, \(D(\textit{diag}(d^{k})e_{n+2m}+w^{k})=\nabla f(x)\)

then,

$$\begin{aligned} \textit{Ddiag}(d^{k})\Big (e_{n+2m}+\textit{diag}\big [ (d^{k})\big ] ^{-1}w^{k}\Big )=\nabla f(x) \end{aligned}$$

as \(d^{k}>0\) then,

$$\begin{aligned} e_{n+2m}+\textit{diag}\big [ (d^{k})\big ] ^{-1}w^{k}>0 \end{aligned}$$

for \(d^{k}+w^{k}>0,\)

let:

$$\begin{aligned} v^{k}=-\textit{diag}\Big (\frac{1}{d^{k}}\Big )w^{k}=-\textit{diag}\Big (\frac{1}{d^{k}}\Big )D^{t}u^{k} \end{aligned}$$

we have, \(e_{n+2m}+\textit{diag}\big [ (d^{k})\big ] ^{-1}w^{k}>0\) then

\(e_{n+2m}-v^{k}>0,\) giving:

\(\max \left| v_{i}^{k}\right| <1\)

therefore, we have: \(d^{k}+w^{k}>0.\) \(\square \)

4.1 The modified algorithm

Description of the algorithm

(a \({^{\prime }}\) ) Initialization: \(\varepsilon >0\) is fixed, \(d^{0}=e,~\xi _{0}\) \(=1\) and \(k=0\)

If \(\left\| Dd^{0}-\nabla f(x)\right\| _{2}<\varepsilon \), Stop: \(d^{k}\) is an \(\varepsilon \)-approximate solution of \((DF)\).

else

calculated \(u^{0}\) solution of the linear system

$$\begin{aligned} DD^{t}u^{0}=\xi _{0}(\nabla f(x)-Da). \end{aligned}$$

(b \({^{\prime }}\) )

If \(\xi _{k}<\varepsilon \)

Stop: \(d^{k}\)  is an \(\varepsilon \)-approximate solution of \((DF)\).

else

Compute

$$\begin{aligned}&u^{k}=\xi _{k}u^{0}\\&v^{k}=-diag\big (\frac{1}{d^{k}}\big )D^{t}u^{k} \end{aligned}$$

If \(\max \left| v_{i}^{k}\right| <1,\) stop: \( d^{k}+D^{t}u^{k}\) is an \(\varepsilon \)-approximate solution of \((DF)\).

else

go to (c \({^{\prime }})\)

(c \({^{\prime }}\) ) is identical to (c) of the algorithm original.

(d \({^{\prime }}\) ) take \(k=k+1\) and go to (b \({^{\prime }}\) ).

5 Numerical tests

The algorithm has been tested on some benchmark problems issued from the paper [7, 9].The implementation is manipulated in DEV C++, We have taken \(\varepsilon =10^{-8}\).

Example 1 [9]

$$\begin{aligned} \left\{ \begin{array}{l} \min ~\frac{1}{2}x^{t}Qx+c^{t}x \\ s.t \\ Ax=b,~x\ge 0 \end{array} \right. \end{aligned}$$

where

$$\begin{aligned} A=\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 1 &{} 1.2 &{} 1 &{} 1.8 &{} 0 \\ 3 &{} -1 &{} 1.5 &{} -2 &{} 1 \\ -1 &{} 2 &{} -3 &{} 4 &{} 2 \end{array}\right) ,\quad c=\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 1&-1.5&2&1.5&3 \end{array} \right) ^{t},\quad b=\left( \begin{array}{c} 9.31 \\ 5.45 \\ 6.60 \end{array} \right) \end{aligned}$$
$$\begin{aligned} Q=\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 20 &{} 1.2 &{} 0.5 &{} 0.5 &{} -1 \\ 1.2 &{} 32 &{} 1 &{} 1 &{} 1 \\ 0.5 &{} 1 &{} 14 &{} 1 &{} 1 \\ 0.5 &{} 1 &{} 1 &{} 15 &{} 1 \\ -1 &{} 1 &{} 1 &{} 1 &{} 16 \end{array}\right) \end{aligned}$$

In this example, we find the dual initial point \((s^{0},y^{0})\)

\(s^{0}=\left( 29.824284~\ 10.732446~\ 0.544773~\ 1.013929~\ 0.488309\right) ^{t}\)

\(y^{0}=\left( 20.822601~\ 5.717161~\ 3.343051\right) \)

The experiment results see Table 1.

Table 1 Numerical results
Full size table

Example 2 [7]

$$\begin{aligned} \left\{ \begin{array}{l} \min ~x_{1}^{2}+0.5x_{2}^{2}+x_{3}^{2}+0.5x_{4}^{2}-x_{1}x_{3}+x_{3}x_{4}-x_{1}-3x_{2}+x_{3}-x_{4} \\ s.t \\ x_{1}+2x_{2}+x_{3}+x_{4}+x_{5}=5 \\ 3x_{1}+x_{2}+2x_{3}-x_{4}+x_{6}=4 \\ -x_{1}-x_{4}+x_{7}=-1.5 \\ -x_{1}+x_{8}=0 \\ -x_{2}+x_{9}=0 \\ -x_{3}+x_{10}=0 \\ x_{4}+x_{11}=0 \end{array} \right. \end{aligned}$$

In this example, we find the dual initial point \((s^{0},y^{0})\)

$$\begin{aligned} s^{0}&= \left( \begin{array}{l} 1.364487~\ 0.047156~\ 0.332105~\ 0.068909~\ 0.888686~\ 0.021166 \\ 0.209226~\ 0.250756~\ 0.044618~\ 0.069522~\ 0.201388 \end{array} \right) ^{t}\\ y^{0}&= \left( \begin{array}{c} -0.888686~\ -0.021166~\ -0.209226~\ -0.250756~\ -0.044618~ \\ \ -0.069522~\ -0.201388 \end{array} \right) \end{aligned}$$

The experiment results see Table 2.

Table 2 Numerical results
Full size table

Example 3 [9]

$$\begin{aligned}\left\{ \begin{array}{l} \min ~\frac{1}{2}x^{t}Qx+c^{t}x \\ s.t \\ Ax=b,~x\ge 0 \end{array} \right. \end{aligned}$$

where

$$\begin{aligned} A=\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 1 &{} -1 &{} 1.9 &{} 1.25 &{} 1.2 &{} 0.4 &{} -0.7 &{} 1.06 &{} 1.5 &{} 1.05 \\ 1.3 &{} 1.2 &{} 0.15 &{} 2.15 &{} 1.25 &{} 1.5 &{} 0.4 &{} 1.52 &{} 1.3 &{} 1 \\ 1.5 &{} -1.1 &{} 3.5 &{} 1.25 &{} 1.8 &{} 2 &{} 1.95 &{} 1.2 &{} 1 &{} -1 \end{array} \right) , \end{aligned}$$
$$\begin{aligned} b=\left( \begin{array}{c} 11.651 \\ 16.672 \\ 21.295 \end{array} \right) , \quad c=\left( \begin{array}{cccccccccc} -0.5&-1&0&0&-0.5&0&0&-1&-0.5&-1 \end{array} \right) ^{t} \end{aligned}$$
$$\begin{aligned} Q=\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 30 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 \\ 1 &{} 21 &{} 0 &{} 1 &{} -1 &{} 1 &{} 0 &{} 1 &{} 0.5 &{} 1 \\ 1 &{} 0 &{} 15 &{} -0.5 &{} -2 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 \\ 1 &{} 1 &{} -0.5 &{} 30 &{} 3 &{} -1 &{} 1 &{} -1 &{} 0.5 &{} 1 \\ 1 &{} -1 &{} -2 &{} 3 &{} 27 &{} 1 &{} 0.5 &{} 1 &{} 1 &{} 1 \\ 1 &{} 1 &{} 1 &{} -1 &{} 1 &{} 16 &{} -0.5 &{} 0.5 &{} 0 &{} 1 \\ 1 &{} 0 &{} 0 &{} 1 &{} 0.5 &{} -0.5 &{} 8 &{} 1 &{} 1 &{} 1 \\ 1 &{} 1 &{} 1 &{} -1 &{} 1 &{} 0.5 &{} 1 &{} 24 &{} 1 &{} 1 \\ 1 &{} 0.5 &{} 1 &{} 0.5 &{} 1 &{} 0 &{} 1 &{} 1 &{} 39 &{} 1 \\ 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 11 \end{array} \right) \end{aligned}$$

In this example, we find the dual initial point \((s^{0},y^{0})\)

$$\begin{aligned} s^{0}&= \left( \begin{array}{c} 20.514528~\ 7.457094~\ 1.792312~\ 10.121809~\ 14.555866 \\ 0.601053~\ 3.827566~\ 2.716075~\ 18.527227~\ 0.800151 \end{array} \right) ^{t}\\ y^{0}&= \left( 3.9721091~\ 8.084740~\ 4.420401\right) \end{aligned}$$

The experiment results see Table 3.

Table 3 Numerical results
Full size table

Example 4 (Erikson’s problem 1980)

We consider the following convex problem

$$\begin{aligned} \left\{ \begin{array}{c} \min f(x)=\sum _{i=1}^{n}x_{i}\ln \frac{x_{i}}{a_{i}} \\ s.t \\ x_{i}+x_{i+m}=b_{i},~i=1,\ldots ,m,~\ n=2m \\ x\ge 0 \end{array}\right. \end{aligned}$$

where \(a_{i}\in \mathfrak {R}_{++}\) and \(b_{i}\in \mathfrak {R}\) are fixed. We have tested this example for different value of \(n,a_{i}\) and \(b_{i}.\)

Algorithm

Number of iteration

Time (s)

\(a_{i}=1~,b_{i}=6\)

\(\quad n=10~~\)

      Ye-Lustig variant algorithm

\(32\)

\(0.03\)

      Modified algorithm

\(23\)

\(0.02\)

\(\quad n=100~~\)

      Ye-Lustig variant algorithm

\(29\)

\(0.02\)

      Modified algorithm

\(21\)

\(0.02\)

\(\quad n=300~~\)

      Ye-Lustig variant algorithm

\(27\)

\(0.02\)

      Modified algorithm

\(20\)

\(0.01\)

\(\quad n=500~~\)

      Ye-Lustig variant algorithm

\(26\)

\(0.01\)

      Modified algorithm

\(17\)

\(0.01\)

\(a_{i}=2~,b_{i}=4\)

\(\quad n=10~~\)

      Ye-Lustig variant algorithm

28

0.03

      Modified algorithm

17

0.02

\(\quad n=100~~\)

      Ye-Lustig variant algorithm

25

0.03

      Modified algorithm

15

0.01

\(\quad n=300~~\)

      Ye-Lustig variant algorithm

23

0.02

      Modified algorithm

13

0.01

\(\quad n=500~~\)

      Ye-Lustig variant algorithm

21

0.02

      Modified algorithm

11

0.01

\(a_{i}=10~,b_{i}=1\)

\(\quad n=10~~\)

      Ye-Lustig variant algorithm

\(32\)

\(0.04\)

      Modified algorithm

\(25\)

\(0.02\)

\(\quad n=100~~\)

      Ye-Lustig variant algorithm

\(31\)

\(0.03\)

      Modified algorithm

\(23\)

\(0.01\)

\(\quad n=300~~\)

      Ye-Lustig variant algorithm

\(31\)

\(0.03\)

      Modified algorithm

\(23\)

\(0.01\)

\(\quad n=500~~\)

      Ye-Lustig variant algorithm

\(28\)

\(0.02\)

      Modified algorithm

\(16\)

\(0.01\)

6 Conclusion

Our modification, we have improved the numerical behavior of the algorithm, reducing the number of iterations corresponding to the search of an initial strictly feasible dual solution of the problem \((\textit{CNLP})\). It is also possible to applied this idea to the search of an optimal solution of the \( (\textit{CNLP})\) problem.