\(^\ast \)Department of Mathematics, University of Setif, Algeria, e-mail: h_roumili@yahoo.fr.

\(^\bullet \)Department of Mathematics, University of Setif, Algeria, e-mail: nawelboudjellal2016@gmail.com. The work of these authors has been supported by LMNF Laboratory

1 Introduction

Convex quadratic programs appear in many areas of application. For example, they appear in finance and as sub-problems in sequential Quadratic Programming. Interior point methods (IPMs) are among the most effective methods for solving a wide range of optimization problems. Today, the most popular and robust of them are primal-dual path-following algorithms owing to their numerical efficiency and theoretical polynomial complexity [ 2 ] , [ 3 ] , [ 7 ] – [ 12 ] . Two types of (IPMs) exist, feasible and infeasible IPMs (IIPMs). Feasible IPMs start from a strictly feasible point for the problem at hand, while IIPMs start from an arbitrary positive point. Owing to the difficulty of finding a feasible starting point for various problems, the use of IIPMs is unavoidable. Roos [ 9 ] , proposed the first full-Newton step IIPM for LO. This algorithm starts from strictly feasible iterates on the central path of the intermediate problems produced by suitable perturbations in the LO problem. Then, it uses so-called feasibility steps that serve to generate strictly feasible iterates for the next perturbed problems. After accomplishing a few centring steps for the new perturbed problem, it obtains strictly feasible iterates close enough to the central path of the new perturbed problems. This algorithm has been extensively extended to other optimization problems, e.g., [ 3 ] , [ 8 ] , [ 12 ] – [ 14 ] . Subsequently, some authors have tried to improve Roos’s infeasible algorithm [ 5 ] , [ 6 ] . Some improvements have been done to reduce or remove the centring steps [ 2 ] , [ 7 ] , [ 10 ] . Recently, Mansouri et al. [ 7 ] proposed an IIPM for solving LO problems with a reformulation of the central path. Their algorithm need not perform a centring step to reach the closeness of the iterates to their \(\mu \)-centres. To reach this target, they select a (rather small) fixed default barrier update parameter in their algorithm to return the iterates to the neighbourhood of the central path without doing a centring step. This value seems to be undesirable for practical purposes.

In this paper, we present an IIPM for convex quadratic programs (CQP). The algorithm uses a short-step and a suitable proximity measure for approximately tracing the central path. The rest of the paper is organized as follows. In section \(2\), we introduce the perturbed problems pertaining to the original primal-dual pair. In section \(3 \), the complexity analysis of the algorithm is discussed. In section \(4\), we deal with the numerical implementation of the infeasible interior point algorithm applied to convex quadratic and linear problems. In section \(5\), a conclusion is stated.

2 The perturbed problems

For any \(\mu \) with \(0{\lt}\mu \leq 1\) we consider the perturbed problem \((QP)_{\mu }\) defined by

and its dual problem \((QD)_{\mu }\), which is given by

The solution \((x(\mu ),y(\mu ),s(\mu ))\) of \((QP)_{\mu }\) and \((QD)_{\mu }\) converges to the primal-dual optimal solution of \(\left( QP\right) \) and \(\left( QD\right) \) as \(\mu \rightarrow 0\).

We start with arbitrarily choosing \(x^{0}{\gt}0\) and \(y^{0},s^{0}{\gt}0\) such that \(x^{0}s^{0}=\mu \)e, if \(\mu =\tfrac {( x^{0}) ^{T}s^{0}}{n}=1\) then \(x^{0}=e\) yields a strictly feasible solution of \((QP)_{1 }\) and \(y^{0}=0\), \(s^{0}=e\) yields a strictly feasible solution of \((QD)_{1 }\). We conclude that \((QP)_{\mu }\) and \((QD)_{\mu }\) satisfy the interior point conditions \(IPC\).

Let \(\bar{x}\) be a feasible solution of \((QP)\) and \((\bar{y},\bar{s})\) be a feasible solution of \((QD)\). Then \(A\bar{x}=b\) and \(A^{T}\bar{y}-Q\bar{x}+\bar{s}=c\), with \(\bar{x}\geq 0\) and \(\bar{s}\geq 0\). Now let \(0{\lt}\mu \leq 1\), and consider: \(x=(1-\mu )\bar{x}+\mu x^{0},\) \(y=(1-\mu )\bar{y}+\mu y^{0},\) \(s=(1-\mu )\bar{s}+\mu s^{0}.\)

One has

showing that \(x\) is feasible for \((QP)_{\mu }\).

Similarly,

showing that \(y,s\) are feasible for \((QD)_{\mu }\). Because \(\mu \) \({\gt}0\), \(x\) and \(s\) are positive, thus proving that \((QP)_{\mu }\) and \((QD)_{\mu }\) satisfy the \(IPC\). To prove the inverse implication, suppose that \((QP)_{\mu }\) and \((QD)_{\mu }\) satisfy the \(IPC\) for each \(\mu \) satisfying \(0{\lt}\mu \leq 1\). Letting \(\mu \) go to zero, it follows that \((QP)\) and \((QD)\) are feasible.

Let \((QP)\) and \((QD)\) be feasible and \(0{\lt}\mu \leq 1\). Then Lemma 1 implies that the problems \((QP)_{\mu }\) and \((QD)_{\mu }\) satisfy the \(IPC\), hence their central paths exist. This means that the system

has a unique solution, for every \(\mu {\gt}0.\)

In the sequel, this unique solution is denoted by \((x(\mu ),y(\mu ),s(\mu ))\). These are the \(\mu \)-centres of the perturbed problems \((QP)_{\mu }\) and \((QD)_{\mu }\). Note that because \(x^{0}s^{0}=e\), \(x^{0}\) is the \(\mu \)-center of the perturbed problem \((QP)_{1\text{ }}\) and \((y^{0},s^{0})\) the \(\mu \)-center of \((QD)_{1\text{ }}\).

To get iterates that are feasible for \((QP)_{\mu ^{+}}\) and \((QD)_{\mu ^{+}}\) we need search directions \(\Delta x,\Delta y\) and \(\Delta s\) such that

where \(\mu ^{+}=\left( 1-\theta \right) \mu \) with \(0{\lt}\theta {\lt}1\).

Therefore, the following system is used to define \(\Delta x,\Delta y\) and \(\Delta s:\)

Now, we introduce a norm-based proximity measure as:

to measure the closeness of the points \((x,y,s)\) to the central path. We suppose that the initial point \((x^{0},y^{0},s^{0})\) verified \(\delta (x^{0},y^{0},s^{0}){\lt}1 \) for certain \(\mu \), is known.

3 Complexity analysis

Now the following notations are useful for studying the complexity of the proposed algorithm.

In addition, we obtain:

and

By using these notations the linear system in 5 and the proximity become:

where

and

we have:

By the definition of \(\infty \)-norm i.e., \(\left\Vert d_{x} d_{s}\right\Vert _{\infty } = \max \{ \vert d_{x_{i}} d_{s_{i}}\vert : i=1,2,\) \(\ldots ,n\} \) and from the assumption, we have that \(\left\vert d_{x_{i}} d_{s_{i}}\right\vert {\lt} 1-\theta \) . Equivalently, we have:

which implies that:

Thus, by Lemma 3, \((x^{+},\) \(s^{+})\) are strictly feasible.

Our aim is to find an upper bound for \(\delta (\upsilon ^{+})\) such that the proximity of the new iterates \((x^{+},\) \(s^{+})\) is always less than 1. For each iteration we have:

We have:

by Corollary 1, \((x^{+},\) \(s^{+})\) are strictly feasible.

The following Lemma proved by C. Roos in 2015 [ 10 ] leads us to find an upper bound for \(\delta (\upsilon ^{+}).\)

We have:

Because

is an increasing function.

Then, by Lemma 6 we have the result which is:

By Lemma 6 and Lemma 7

i/

\begin{align*} \Delta x^{T}\Delta s & =( x\upsilon ^{-1}d_{x}) ^{T} ( s\upsilon ^{-1}d_{s}) \\ & =\left( \sqrt{\tfrac {x\mu }{s}}d_{x}\right) ^{T}\left( \sqrt{\tfrac {s\mu }{x}}d_{s}\right) =\mu \left( d_{x}\right) ^{T}d_{s}\leq \mu \delta ^{2}. \end{align*}

ii/

\begin{align*} x^{+}s^{+} & =\left( x+\Delta x\right) \left( s+\Delta s\right) =xs+x\Delta x+s\Delta s+\Delta x\Delta s \\ & =\mu (1-\theta ) e+\Delta x\Delta s \end{align*}

iii/

\begin{align*} (x^{+}) ^{T}s^{+} & =e^{T}( x^{+}s^{+}) =e^{T}( \mu (1-\theta ) e+\Delta x\Delta s) \\ & =\mu (1-\theta ) n+\Delta x^{T}\Delta s =\mu (1-\theta ) n+\mu d_{x}^{T}d_{s} \\ & \leq \mu ( n+\delta ^{2}) \end{align*}

Theorem 10

Let \(\theta =\tfrac {1}{n},\) \(x^{0}=e,y^{0}=0,s^{0}=e\) and \(\mu ^{0}=\tfrac {1}{n}\left( x^{0}\right) ^{T}s^{0}=1\) with \(\delta (\upsilon ^{0})=0{\lt}1\) . Then, the full Newton step IIPM algorithm requires at most \(n\log \tfrac {n}{ \varepsilon }\) iterations to reach the \(\varepsilon \)-solution of \(\left( QP\right) \) and \(\left( QD\right) .\)

Let \(x_{k}\) and \(s_{k}\) be the \(k\)-th iterates of Algorithm 2. Then

Then by taking logarithm of both sides, we have:

4 Numerical implementation

In this section, we deal with the numerical implementation of the infeasible interior point algorithm applied to convex quadratic and linear problems. The feasible starting point is \( (x^{0},y^{0},s^{0}) =(e,0,e)\), the proximity condition \(\delta (x^{0},z^{0},\mu ^{0} )=0\), \(x^{*}\) means the optimal solution of \((QP)\), \((y^{*},s^{*})\) means the optimal solution of \((QD)\), \(f_{PQ}(opt)\) and \(f_{DQ}(opt)\) means the optimal objective values of \((QP)\) and \((QD)\) respectively. ‘Iter’ refers to the number of iterations produced by Algorithm 2. Our accuracy parameter is \(\varepsilon =10^{-4}\). For the update parameter \( \theta \) we have first used the theoretical strategy, followed by a practical strategy with different values.

Linear programming is a special case of convex quadratic programming.

We summarize the number of iterations and the computation time in the following two tables:

The numerical results show that the number of iterations of Algorithm 2 depends on the values of the parameter \( \theta \). It is quite surprising that \( \theta \) = 0.9 gives the lowest iteration and time.

5 Conclusion

In this paper we extended results from [ 8 ] and [ 9 ] to solve the convex quadratic problems \(CQP\). These methods were based on modified search directions such that only one full-Newton step is needed in each main iteration. We can conclude that these methods constitute a valid solution to the algorithm initialization problem. Our numerical results are acceptable, whereas getting a starting feasible centered point for these algorithms is a challenging task. Finally, we point out that the implementation with the update parameter \(\theta \) significantly reduces the number of iterations produced by this algorithm and enables these algorithms to reach their real numerical performance. Future research might extend the algorithm for other optimization problems.