Return to Article Details An infeasible interior point methods for convex quadratic problems

An infeasible interior point method
for convex quadratic problems

Hayet Roumili $^{*}$ Nawel Boudjellal $^{∙}$

January 25, 2018. Accepted: June 12, 2018. Published online: February 7, 2019.

$^{*}$ Department of Mathematics, University of Setif, Algeria, e-mail: h_roumili@yahoo.fr.

$^{∙}$ Department of Mathematics, University of Setif, Algeria, e-mail: nawelboudjellal2016@gmail.com. The work of these authors has been supported by LMNF Laboratory

In this paper, we deal with the study and implementation of an infeasible interior point method for convex quadratic problems $(C Q P)$ . The algorithm uses a Newton step and suitable proximity measure for approximately tracing the central path and guarantees that after one feasibility step, the new iterate is feasible and sufficiently close to the central path. For its complexity analysis, we reconsider the analysis used by the authors for linear optimization $(L O)$ and linear complementarity problems $(L C P)$ . We show that the algorithm has the best known iteration bound, namely $n \log \frac{(n + 1)}{ϵ} .$ Finally, to measure the numerical performance of this algorithm, it was tested on convex quadratic and linear problems.

MSC. 90C05. 90C51.

Keywords. Convex quadratic programs, Infeasible interior-point method, Newton step.

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 $μ$ -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 $μ$ with $0 < μ \leq 1$ we consider the perturbed problem $(Q P)_{μ}$ defined by

(Q P)_{μ} {\begin{cases} min {(c - μ (c - A^{T} y^{0} + Q x^{0} - s^{0}))}^{T} x + \frac{1}{2} x^{T} Q x \\ A x = b - μ (b - A x^{0}) \\ x \geq 0 \end{cases}

and its dual problem $(Q D)_{μ}$ , which is given by

(Q D)_{μ} {\begin{cases} max {(b - μ (b - A x^{0}))}^{T} y - \frac{1}{2} x^{T} Q x \\ A^{T} y + s - Q x = c - μ (c - A^{T} y^{0} + Q x^{0} - s^{0}) \\ s \geq 0, y \in R^{m} \end{cases}

The solution $(x (μ), y (μ), s (μ))$ of $(Q P)_{μ}$ and $(Q D)_{μ}$ converges to the primal-dual optimal solution of $(Q P)$ and $(Q D)$ as $μ \to 0$ .

We start with arbitrarily choosing $x^{0} > 0$ and $y^{0}, s^{0} > 0$ such that $x^{0} s^{0} = μ$ e, if $μ = \frac{(x^{0})^{T} s^{0}}{n} = 1$ then $x^{0} = e$ yields a strictly feasible solution of $(Q P)_{1}$ and $y^{0} = 0$ , $s^{0} = e$ yields a strictly feasible solution of $(Q D)_{1}$ . We conclude that $(Q P)_{μ}$ and $(Q D)_{μ}$ satisfy the interior point conditions $I P C$ .

Lemma 1

The original problems $(Q P)$ and $(Q D)$ are feasible if and only if for each $μ$ satisfying $0 < μ \leq 1$ the perturbed problems $(Q P)_{μ}$ and $(Q D)_{μ}$ satisfy the $I P C$ .

Proof â–¼

Let

\bar{x}

be a feasible solution of

(Q P)

and

(\bar{y}, \bar{s})

be a feasible solution of

(Q D)

. 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 < μ \leq 1

, and consider:

x = (1 - μ) \bar{x} + μ x^{0},

y = (1 - μ) \bar{y} + μ y^{0},

s = (1 - μ) \bar{s} + μ s^{0} .

One has

\begin{aligned} A x & = A ((1 - μ) \bar{x} + μ x^{0}) = (1 - μ) A \bar{x} + μ A x^{0} \\ = (1 - μ) b + μ A x^{0} = b - μ (b - A x^{0}) = b - μ r_{b}^{0} \end{aligned}

showing that $x$ is feasible for $(Q P)_{μ}$ .

Similarly,

\begin{aligned} A^{T} y - Q x + s & = (1 - μ) (A^{T} \bar{y} - Q \bar{x} + \bar{s}) + μ (A^{T} y^{0} - Q x^{0} + s^{0}) \\ = (1 - μ) c + μ (A^{T} y^{0} - Q x^{0} + s^{0}) \\ = c - μ (c - A^{T} y^{0} + Q x^{0} - s^{0}) = c - μ r_{c}^{0} \end{aligned}

showing that $y, s$ are feasible for $(Q D)_{μ}$ . Because $μ$ $> 0$ , $x$ and $s$ are positive, thus proving that $(Q P)_{μ}$ and $(Q D)_{μ}$ satisfy the $I P C$ . To prove the inverse implication, suppose that $(Q P)_{μ}$ and $(Q D)_{μ}$ satisfy the $I P C$ for each $μ$ satisfying $0 < μ \leq 1$ . Letting $μ$ go to zero, it follows that $(Q P)$ and $(Q D)$ are feasible.

Proof â–¼

Let $(Q P)$ and $(Q D)$ be feasible and $0 < μ \leq 1$ . Then Lemma 1 implies that the problems $(Q P)_{μ}$ and $(Q D)_{μ}$ satisfy the $I P C$ , hence their central paths exist. This means that the system

{\begin{matrix} b - A x = μ r_{b}^{0} \\ c - A^{T} y + Q x - s = μ r_{c}^{0} \\ x s = μ e, \  \  \  \  \  \ x > 0, s > 0 \end{matrix}

has a unique solution, for every $μ > 0.$

In the sequel, this unique solution is denoted by $(x (μ), y (μ), s (μ))$ . These are the $μ$ -centres of the perturbed problems $(Q P)_{μ}$ and $(Q D)_{μ}$ . Note that because $x^{0} s^{0} = e$ , $x^{0}$ is the $μ$ -center of the perturbed problem $(Q P)_{1}$ and $(y^{0}, s^{0})$ the $μ$ -center of $(Q D)_{1}$ .

To get iterates that are feasible for $(Q P)_{μ^{+}}$ and $(Q D)_{μ^{+}}$ we need search directions $Δ x, Δ y$ and $Δ s$ such that

{\begin{cases} A (x + Δ x) = b - μ^{+} r_{b}^{0} \\ A^{T} (y + Δ y) - Q (x + Δ x) + (s + Δ s) = c - μ^{+} r_{c}^{0} \end{cases}

where $μ^{+} = (1 - θ) μ$ with $0 < θ < 1$ .

Therefore, the following system is used to define $Δ x, Δ y$ and $Δ s :$

{\begin{cases} A Δ x = θ μ r_{b}^{0} \\ A^{T} Δ y - Q Δ x + Δ s = θ μ r_{c}^{0} \\ s Δ x + x Δ s = (1 - θ) μ e - x s \end{cases}

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

δ (x, z, μ) = \frac{1}{2} ‖ μ e - x s ‖

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 $δ (x^{0}, y^{0}, s^{0}) < 1$ for certain $μ$ , is known.

Algorithm 2

Primal-dual Infeasible IPM algorithm

Input

- An accuracy parameter $ε > 0$ .

- barrier update parameter $0 < θ < 1$ .

- a strictly feasible point $(x^{0}, y^{0}, s^{0}) = (e, 0, e)$ and $μ^{0} = 1$

such that $δ (x^{0}, y^{0}, s^{0}) = 0 < 1 .$

begin

$x = x^{0}, y = y^{0}, s = s^{0}, μ = μ^{0} .$

while $‖ r_{b} ‖ + ‖ r_{c} ‖ + x^{T} s > ε$ do

$(r_{b} = A x - b, r_{c} = c - A^{T} y + Q x - s)$

solve the system $(5)$ to obtain: $(Δ x, Δ y, Δ s) .$

update $x := x + Δ x, y := y + Δ y, z := z + Δ z,$

update $μ := (1 - θ) μ .$

end

3 Complexity analysis

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

υ = \sqrt{\frac{x s}{μ}}, d_{x} = \frac{υ Δ x}{x}, d_{s} = \frac{υ Δ s}{s}, d = \sqrt{\frac{x}{s}}

In addition, we obtain:

s Δ x + x Δ s = μ υ (d_{x} + d_{s})

and

Δ x Δ s = μ d_{x} d_{s}

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

{\begin{cases} \bar{A} d_{x} = μ^{- \frac{1}{2}} θ μ r_{b}^{0} = μ^{\frac{1}{2}} θ r_{b}^{0} \\ {\bar{A}}^{T} d_{y} - \bar{Q} d_{x} + d_{s} = μ^{- \frac{1}{2}} θ μ D r_{c}^{0} = μ^{\frac{1}{2}} θ D r_{c}^{0} \\ d_{x} + d_{s} = (1 - θ) υ^{- 1} - υ \end{cases}

where

D = diag (d_{i}), \bar{A} = A D, \bar{Q} = D Q D, d_{y} =, μ^{- \frac{1}{2}} Δ y

and

δ (υ) = \frac{1}{2} ‖ υ^{- 1} - υ ‖

we have:

\begin{aligned} x^{+} s^{+} & = x s + (s Δ x + x Δ s) + Δ x Δ s = (1 - θ) μ e + Δ x Δ s \\ = (1 - θ) μ e + \frac{x s}{υ^{2}} = μ ((1 - θ) e + d_{x} d_{s}) . \end{aligned}

Lemma 3

The iterates $(x^{+},$ $s^{+})$ are strictly feasible if and only if:

(1 - θ) e + d_{x} d_{s} > 0.

Corollary 4

The iterates $(x^{+},$ $s^{+})$ are strictly feasible if $‖ d_{x} d_{s} ‖_{\infty} < 1 - θ .$

Proof â–¼

By the definition of

\infty

-norm i.e.,

{‖ d_{x} d_{s} ‖}_{\infty} = max {| d_{x_{i}} d_{s_{i}} | : i = 1, 2,

\dots, n}

and from the assumption, we have that

| d_{x_{i}} d_{s_{i}} | < 1 - θ

. Equivalently, we have:

- (1 - θ) < d_{x_{i}} d_{s_{i}} < 1 - θ

which implies that:

d_{x} d_{s} + (1 - θ) e > 0

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

Proof â–¼

Our aim is to find an upper bound for

δ (υ^{+})

such that the proximity of the new iterates

(x^{+},

s^{+})

is always less than 1. For each iteration we have:

‖ d_{x} d_{s} ‖_{\infty} \leq ‖ d_{x} d_{s} ‖ \leq ‖ d_{x} ‖ ‖ d_{s} ‖ \leq \frac{1}{2} (‖ d_{x} ‖^{2} + ‖ d_{s} ‖^{2}) = w (υ) .

Corollary 5

if $w (υ) < 1 - θ$ then $(x^{+},$ $s^{+})$ are strictly feasible $.$

Proof â–¼

We have:

‖ d_{x} d_{s} ‖_{\infty} \leq w (υ) < 1 - θ .

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

Proof â–¼

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

Lemma 6

Let a,b $\in R^{n}, r \in (0, 1]$ and $f (a, b) = \sum_{i = 1}^{n}$ $ζ (a_{i} b_{i}) .$ If

{‖ a ‖}^{2} + {‖ b ‖}^{2} \leq 2 r^{2},

then

f (a, b) \leq (n - 1) ζ (0) + max {ζ (r^{2}), ζ (- r^{2})}

where

ζ (t) = \frac{1 + t}{1 - θ} + \frac{1 - θ}{1 + t} - 2 = \frac{{(θ + t)}^{2}}{(1 - θ) (1 + t)} \geq 0, \forall t > - 1, 0 < θ < 1.

Lemma 7

If $w (υ) < 1 - θ,$ then

4 δ (υ^{+})^{2} \leq (n - 1) ζ (0) + max {ζ (w (υ)), ζ (- w (υ)} .

Proof â–¼

We have:

υ^{+^{2}} = \frac{x^{+} s^{+}}{μ^{+}} = \frac{μ ((1 - θ) e + d_{x} d_{s})}{(1 - θ) μ} = e + \frac{d_{x} d_{s}}{1 - θ}

Because

\begin{aligned} 4 δ (υ^{+})^{2} & = ‖ (υ^{+})^{- 1} - υ^{+} ‖^{2} = \sum_{i = 1}^{n} (\frac{1}{υ_{i}^{+}} - υ_{i}^{+})^{2} \\ = \sum_{i = 1}^{n} (\frac{1}{{(υ_{i}^{+})}^{2}} + {(υ_{i}^{+})}^{2} - 2) \\ = \sum_{i = 1}^{n} [\frac{(1 - θ)}{(1 - θ) + d_{x_{i}} d_{s_{i}}} + \frac{(1 - θ) + d_{x_{i}} d_{s_{i}}}{(1 - θ)} - 2] \\ = \sum_{i = 1}^{n} ζ (d_{x_{i}} d_{s_{i}} - θ) \leq \sum_{i = 1}^{n} ζ (d_{x_{i}} d_{s_{i}}), ζ (t) \end{aligned}

is an increasing function.

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

4 δ (υ^{+})^{2} \leq (n - 1) ζ (0) + max {ζ (w (υ)), ζ (- w (υ)}

Corollary 8

If $θ = \frac{1}{n}$ then:

4 δ (υ^{+})^{2} < 4 \Rightarrow δ (υ^{+}) < 1

Proof â–¼

By Lemma 6 and Lemma 7

Proof â–¼

Lemma 9

The following equation and inequalities hold:
i/ $Δ x^{T} Δ s \leq μ δ^{2}$
ii/ $x^{+} s^{+} = μ (1 - θ) e + Δ x Δ s$
iii/ ${(x^{+})}^{T} s^{+} \leq μ (n + δ^{2})$

Proof â–¼

\begin{aligned} Δ x^{T} Δ s & = (x υ^{- 1} d_{x})^{T} (s υ^{- 1} d_{s}) \\ = {(\sqrt{\frac{x μ}{s}} d_{x})}^{T} (\sqrt{\frac{s μ}{x}} d_{s}) = μ {(d_{x})}^{T} d_{s} \leq μ δ^{2} . \end{aligned}

ii/

\begin{aligned} x^{+} s^{+} & = (x + Δ x) (s + Δ s) = x s + x Δ x + s Δ s + Δ x Δ s \\ = μ (1 - θ) e + Δ x Δ s \end{aligned}

iii/

\begin{aligned} (x^{+})^{T} s^{+} & = e^{T} (x^{+} s^{+}) = e^{T} (μ (1 - θ) e + Δ x Δ s) \\ = μ (1 - θ) n + Δ x^{T} Δ s = μ (1 - θ) n + μ d_{x}^{T} d_{s} \\ \leq μ (n + δ^{2}) \end{aligned}

Theorem 10

Let $θ = \frac{1}{n},$ $x^{0} = e, y^{0} = 0, s^{0} = e$ and $μ^{0} = \frac{1}{n} {(x^{0})}^{T} s^{0} = 1$ with $δ (υ^{0}) = 0 < 1$ . Then, the full Newton step IIPM algorithm requires at most $n \log \frac{n}{ε}$ iterations to reach the $ε$ -solution of $(Q P)$ and $(Q D) .$

Proof â–¼

Let

x_{k}

and

s_{k}

be the

k

-th iterates of Algorithm 2. Then

\begin{array}{r} (x^{+})^{T} s^{+} \leq μ_{k} (n + δ^{2}) \leq μ_{k} (n + 1) = {(1 - θ)}^{k} μ_{0} (n + 1) < ε \end{array}

Then by taking logarithm of both sides, we have:

\begin{aligned} \log ((n + 1) {(1 - θ)}^{k}) & < \log ε \\ \log (n + 1) + \log {(1 - θ)}^{k} & < \log ε \\ k \log (1 - θ) & < \log ε - \log (n + 1) = \log \frac{ε}{(n + 1)} \\ - k θ & < \log \frac{ε}{(n + 1)} \\ k & > \frac{1}{θ} \log \frac{(n + 1)}{ε} = n \log \frac{(n + 1)}{ε} \  \  \ (because θ = \frac{1}{n}) . \end{aligned}

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 $δ (x^{0}, z^{0}, μ^{0}) = 0$ , $x^{*}$ means the optimal solution of $(Q P)$ , $(y^{*}, s^{*})$ means the optimal solution of $(Q D)$ , $f_{P Q} (o p t)$ and $f_{D Q} (o p t)$ means the optimal objective values of $(Q P)$ and $(Q D)$ respectively. ‘Iter’ refers to the number of iterations produced by Algorithm 2. Our accuracy parameter is $ε = 10^{- 4}$ . For the update parameter $θ$ we have first used the theoretical strategy, followed by a practical strategy with different values.

Example 11

Let

A = (\begin{array}{ccc} - 1 & 1 & 0 \\ 1 & 1 & 0 \end{array}), Q = (\begin{array}{ccc} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 0 \end{array}), c = (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}), b = (\begin{matrix} 1 \\ 2 \end{matrix})

$x^{*} = {(0.5, 1.5, 0)}^{T}$ , $y^{*} = {(0, - 0.9999)}^{T}$ , $z^{*} = {(0, 0, 0)}^{T}$ , $f_{P Q} (o p t) = - 4.5$ , $f_{D Q} (o p t) = - 4.4999$ . â–¡

Example 12

Let

A = (\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 1 & 5 & 0 & 1 \end{array}), Q = (\begin{array}{cccc} 4 & - 2 & 0 & 0 \\ - 2 & 4 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}), c = (\begin{matrix} - 4 \\ - 6 \\ 0 \\ 0 \end{matrix}),

$b = (\begin{matrix} 4 \\ 8 \end{matrix})$ , $x^{*} = {(0.9999, 2.9999, 0, 0)}^{T}, y^{*} = {(- 0.9999, - 0.9999)}^{T}$ ,
$z^{*} = {(0, 0, 0.9996, 0.9998)}^{T}$ , $f_{P Q} (o p t) = - 22.9995$ , $f_{D Q} (o p t) = - 22.9988$ . â–¡

Example 13

Let

A = (\begin{array}{cccccccccc} 1.5 & 1 & 1 & 0.5 & 0.5 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 & - 0.5 & - 0.5 & 1 & - 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array}), b = (\begin{matrix} 5.5 \\ 2 \\ 10 \\ 15 \end{matrix}),

$c = 0 \in R^{10},$ $Q = 2 I \in R^{10}$ ( $I$ the identity matrix), $x^{*} =$
$(0.1868, 1.5938, 1.2060, 2.6132, 2.2254, 3.1898, 3.3555, 3.7433, 3.0233, 3.8540)^{T} y^{*} = {(- 4.0776, - 0.4430, 6.4888, 7.2646)}^{T}, z^{*} = {(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)}^{T} f_{P Q} (o p t) = 75.25, f_{D Q} (o p t) = 75.29$ . â–¡

Linear programming is a special case of convex quadratic programming.

Example 14

Consider the linear problem where:

\begin{aligned} A [i, j] = & {\begin{array}{c} 1, if j = i + m or i = j \\ 0, if j \neq i + m or i \neq j \end{array} \\ b [i] = & 2, i = 1, . . ., m, \\ c [i] = & - 1, i = 1, . . ., n . \end{aligned}

4-1) $m = 5, n = 10$

$x^{*} =$ $1, \forall i = 1 : 10$ , $y^{*} = 0.9999, \forall i = 1 : 5$ , $z^{*} = 0, \forall i = 1 : 10$ ,

$f_{P Q} (o p t) = - 10$ , $f_{D Q} (o p t) = - 9.9998 .$

4-2) $m = 10, n = 20$

$x^{*} = 1$ $, \forall i = 1 : 20$ , $y^{*} = 0.9999, \forall i = 1 : 10$ , $z^{*} = 0, \forall i = 1 : 20$

$f_{P Q} (o p t) = - 20$ , $f_{D Q} (o p t) = - 19.9998$

4-3) $m = 20, n = 40$

$x^{*} = 1$ , $\forall i = 1 : 40$ , $y^{*} = 0.9999, \forall i = 1 : 20$ , $z^{*} = 0, \forall i = 1 : 40$ ,

$f_{P Q} (o p t) = - 40$ , $f_{D Q} (o p t) = - 39.9998$

4-4) $m = 50, n = 100$

$x^{*} = 1$ , $\forall i = 1 : 100$ , $y^{*} = 0.9999, \forall i = 1 : 50$ , $z^{*} = 0, \forall i = 1 : 100$ ,

$f_{P Q} (o p t) = - 100$ , $f_{D Q} (o p t) = - 99.9998$

4-5) $m = 250, n = 500$

$x^{*} = 1$ , $\forall i = 1 : 500$ , $y^{*} = 0.9999, \forall i = 1 : 250$ , $z^{*} = 0, \forall i = 1 : 500$

$f_{P Q} (o p t) = - 500$ , $f_{D Q} (o p t) = - 499.9998$

4-6) $m = 500, n = 1000$

$x^{*} = 1$ , $\forall i = 1 : 1000$ , $y^{*} = 0.9999, \forall i = 1 : 500$ , $z^{*} = 0, \forall i = 1 : 1000$ ,

$f_{P Q} (o p t) = - 1000$ , $f_{D Q} (o p t) = - 999.9998$ . â–¡

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

example	size	$θ = 1 / n$	$θ = 0.5$	$θ = 0.9$
1	(2,3)	22	14	6
2	(2,4)	31	14	6
3	(4,10)	70	16	7
4-1	(5,10)	77	13	7
4-2	(10,20)	105	14	10
4-3	(20,40)	193	16	11
4-4	(50,100)	281	17	11
4-5	(250,500)	691	24	13
4-6	(500,1000)	8765	30	13

Table 1 Number of iterations

example	$θ = 1 / n$	$θ = 0.5$	$θ = 0.9$
1	0.000000	0.000000	0.000000
2	0.000000	0.000000	0.000000
3	0.049826	0.000000	0.000000
4-1	0.000000	0.000000	0.000000
4-2	0.091239	0.000000	0.000000
4-3	0.89966	0.031780	0.028232
4-4	4.814184	0.149128	0.065752
4-5	1857.001255	16.50277	3.889985
4-6	15176.701324	86.074864	27.313875

Table 2 Computation time (s)

The numerical results show that the number of iterations of Algorithm 2 depends on the values of the parameter $θ$ . It is quite surprising that $θ$ = 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 $C Q P$ . 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 $θ$ 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.