A weighted logarithmic barrier interior-point method for linearly constrained optimization

(1)

DOI: 10.24193/subbmath.2021.4.14

A weighted logarithmic barrier interior-point method for linearly constrained optimization

Selma Lamri, Bachir Merikhi and Mohamed Achache

Abstract. In this paper, a weighted logarithmic barrier interior-point method for solving the linearly convex constrained optimization problems is presented.

Unlike the classical central-path, the barrier parameter associated with the perturbed barrier problems, is not a scalar but is a weighted positive vector. This modification gives a theoretical flexibility on its convergence and its numerical performance. In addition, this method is of a Newton descent direction and the computation of the step-size along this direction is based on a new efficient technique called the tangent method. The practical efficiency of our approach is shown by giving some numerical results.

Mathematics Subject Classification (2010):90C30, 90C25, 90C51.

Keywords:Logarithmic barrier method, linearly constrained convex optimization, interior-point methods.

1. Introduction

In this paper, we consider the linearly convex constrained optimization (LCCO) problem:

¯

p= minf(x) subject tox∈ F, (P)

where the objective function f :Rⁿ →R is twice differentiable and convex over the feasible setF ={x∈Rⁿ:x≥0, Ax=b},Ais a given (m×n) matrix with full rank rowmandb∈R^m.

This problem has many important applications in theory as well in practice. In par- ticular, it includes linear and quadratic optimization. Feasible logarithmic barrier interior-point methods gained much more attention than others. Their derived algorithms enjoy some interesting results such as polynomial complexity and numerical efficiency. However, these algorithms require that the starting point must be strictly feasible and close to the central-path.This is a hard practical task to release and even impossible. On the other hand, at each iteration, they compute a descent direction and

(2)

determine a step-size on this direction. It is known that computing this latter is very expensive while using classical line search methods. In order to overcome these two dif- ficulties, we suggest for the first, a weighted-path (see [1], [2], [3], [8], [10], [12]) where a relaxation parameter associated with perturbed problems is introduced in order to give more flexibility on the numerical aspects. Beside, we propose a new numerical efficient procedure called the tangent method for determining this displacement. Across these two modifications the numerical results obtained by our algorithm are totally improved with respect to the classical logarithmic barrier interior-point approach (see [10], [13]). The paper is organized as follows. In section 2, perturbed relaxation problems based on the weighted barrier penalization are given where the convergence to the original problem is studied. The computation of the direction and of the step-size are stated. Finally, a weighted-path interior-point algorithm is presented. In section 3, some numerical results are given to show the efficiency of our approach. Finally a conclusion and remarks end the section 4.

2. The weighted barrier penalization

Throughout the paper, we assume that the following assumptions hold.

1. There exit a strictly feasible pointx₀>0 such thatAx₀=b.

2. The set of optimal solutions ofP is non empty bounded set.

It follows from the second hypothesis that

{d∈Rⁿ: f_∞(d)≤0, d≥0, Ad= 0}={0},

wheref_∞denote the recession function off. We deduce from the optimality conditions that x^∗ is a solution of P if and only if there exists an y^∗ ∈R^m and z^∗ ∈Rⁿ such that

∇f(x^∗) +A^Ty^∗=z^∗≥0, Ax^∗=b, hz^∗, x^∗i= 0, x^∗≥0. (2.1) 2.1. The weighted perturbed problems

Let us define the functionθ:R×R→(−∞,+∞] by θ(t, w) =







t(logt−logw) if t >0, w >0,

0 if t= 0, w≥0,

+∞ otherwise.

The function θ is convex, lower semi-continuous and proper. We consider now the following function defined onRⁿ₊×Rⁿ₊ by

ϕ(µr, x) =







f(x) +

n

X

i=1

θ(µri, xi) ifx∈ F,

+∞ otherwise,

where µ > 0 is the barrier parameter and r = (r1, r2, . . . , rn)^T ∈ Rⁿ₊, the vector of the weight associated with the barrier function.

Finally, we introduce the functionp^r defined by p^r(µ) = inf

x [ϕ^r_µ(x) =ϕ(µr, x) : x∈Rⁿ]. (P_µ^r)

(3)

The functionp^ris convex sinceϕ^r_µis convex. By construction,P₀^ris only the problem P with ¯p=p^r(0). The functionϕ^r_µ is convex, lower semi-continuous and proper, its recession function is given by

(ϕ^r_µ)∞(d) = lim

α→+∞

ϕ^r_µ(x0+αd)−ϕ^r_µ(x0)

α .

We obtain

(ϕ^r_µ)_∞(d) =

f_∞(d) if d≥0, Ad= 0, +∞ otherwise.

Then

{d∈Rⁿ : (ϕ^r_µ)_∞(d)≤0}={d∈Rⁿ : f_∞(d)≤0, d≥0, Ad= 0}, wheredis the descent direction andαis the step-size.

Since this set is reduced to{0} then the problemP_µ^r admits an optimal solution for eachµ >0. The functionϕ^r_µ is strictly convex for all µ≥0 and r≥0, thenP_µ^r has an unique optimal solution denoted byx^r_µ.

2.2. Convergence of the weighted perturbed solutions to the optimal solution ofP_µ^r The necessary and sufficient optimality conditions of (P_µ^r) imply that there exits y_µ^r =y(µ, r)∈R^m, such that

∇f(x^r_µ)−µX⁻¹r+A^Ty_µ^r = 0, (2.2)

Ax^r_µ = b, (2.3)

whereX =Diag(x^r_µ).

Note thaty^r_µis uniquely defined sinceAis of full rank row. In fact, the couple (x^r_µ, y_µ^r) is the solution of the systemH(x, y) = 0 where

H(x, y) =

∇f(x)−µX⁻¹r+A^Ty Ax−b

.

By the implicit function theorem, the functionsµ7→x(µ, r) =x^r_µ andµ7→y(µ, r) = y_µ^r are differentiable on (0,∞) and we have,

∇²f(x^r_µ) +µRX⁻² A^T

A 0

x⁰(µ, r) y⁰(µ, r)

=

X⁻¹r 0

, (2.4)

where R=Diag(r), it follows that the function p^r is differentiable on (0,∞). Recall that

p^r(µ) =f(x^r_µ) +µ

n

X

i=1

ri(lnµri−ln(xi)^r_µ), and then

(p^r(µ))⁰=

n

X

i=1

ri(1 + lnµri−ln(xi)^r_µ) +h∇f(x^r_µ)−µX⁻¹r, x⁰(µ, r)i.

(4)

In view of (2.2) and (2.4) (p^r(µ))⁰ =

n

X

i=1

r_i(1 + lnµr_i−ln(x_i)^r_µ)− hA^Ty^r_µ, x⁰(µ, r)i,

=

n

X

i=1

ri(1 + lnµri−ln(xi)^r_µ)− hy_µ^r, Ax⁰(µ, r)i,

=

n

X

i=1

ri(1 + lnµri−ln(xi)^r_µ).

Sincex^r_µ∈ F andp^ris convex we obtain:

f(x^r_µ)≥p¯=p^r(0)≥p^r(µ) + (0−µ)(p^r(µ))⁰ =f(x^r_µ)−µkrk1. Consequently, we have

¯

p≤f(x^r_µ)≤p¯+µkrk1. Then if

µ7→0, f(x^r_µ) = ¯p.

Now, we interested to the weighted-path of{x^r_µ}when µ7→0.

i) Case where f is strongly convex with coefficient τ > 0. Hence P has a unique optimal solutionx^∗, and we have

µkrk1≥f(x^r_µ)−f(x^∗)≥ h∇f(x^∗), x^r_µ−x^∗i+τ

2kx^r_µ−x^∗k². In view of (2.1), we deduce

µkrk1≥ hz^∗, x^r_µi+τ

2kx^r_µ−x^∗k²≥ τ

2kx^r_µ−x^∗k², kx^r_µ−x^∗k ≤

r2µkrk1

τ .

ii) For the case wheref is only convex is more complex. Note first that for µ≤1, x^r_µ ∈ {x : x≥0, Ax=b, f(x)≤ krk1+ ¯p}.

This set is closed convex non empty. Its recession cone is {d∈Rⁿ: f_∞(d)≤0, d≥0, Ad= 0}={0}.

By the second assumption the set of optimal solutions ofP is bounded which implies that each adherence value of{x^r_µ} whenµ7→0 is an optimal solution ofP.

Remark 2.1. Ifr=e, whereeis the vector of ones, then the weighted-path coincides with the classical path (see[6]).

(5)

2.3. The description of the method

Letting F⁰ = {x ∈ Rⁿ : x > 0, Ax = b} the set of strictly feasible points.

The principle of the method is as follows: Let (µkr, xk)∈Rⁿ₊×F⁰, the current iterate.

1. We make an approximated minimization of the weighted perturbedP_µ^r_k which gives a new pointx_k+1 such thatϕ(µ_k+1r, x_k+1)< ϕ(µ_kr, x_k).

2. We takeµ_k+1< µ_k.

We iterated until we obtained an approximated optimal solution of the original problem. The weighted perturbed problem is defined by

minx ϕ^r_µ(x) = min

x [f(x) +

n

X

i=1

θ(µri, xi) :x∈ F]. (P_µ^r) 2.4. The Newton descent direction

At x ∈ F⁰, the Newton descent direction d is given by solving the following quadratic convex program:

min

d [h∇ϕ^r_µ(x), di+1

2h∇²ϕ^r_µ(x)d, di:Ad= 0 ].

It suffices to solve the linear system withn+mequations ∇²f(x) +µRX⁻² A^T

A 0

d s

=

µX⁻¹r− ∇f(x) 0

, (2.5)

wheres∈R^m .

It easy to prove that the linear system (2.5) has a unique solution. The descent direction being thus obtained, it is now question of minimizing a function of one real variable to obtain the step-sizeα.

γ^r(α) =ϕ^r_µ(x+αd)−ϕ^r_µ(x) =f(x+αd)−f(x) −µ

n

X

i=1

riln(1 +αti), wheret=X⁻¹d, the functionγ^r is convex.

Next task, we propose a new method to determine the step-size.

2.5. A tangent method for determining the step-size

Our approach is try out a sequence of candidate values for α, when the condition (γ^r(α))⁰ ≤ is satisfied, stopping and accept this value. We can say that this technique is done in two phases.

1. The first phase finds an interval containing the required step-size, the choice of the bounds of the interval is similar to the bisection method, when we restrict the value ofαuntil we find the required value.

2. The second phase computes the optimal step-size within this interval, in this phase we determine the tangentsT1andT2in the bounds of the interval and we select the value corresponding to the intersection of the tangentsT1 andT2.

(6)

The upper bound on the step-sizeαis given by

αmax= min

−x_i di

; i∈Iˆ

,

where

Iˆ={i: di<0}.

Because the convexity of the functionγ^r(α), this technique will be more efficiency in practice, the next figures shows clearly this idea:

Figure 1 Figure 2

Figure 3

(7)

The tangent algorithm for determining the step-size is follows.

Algorithm Input

- An accuracy parameter >0;

- A threshold parameter 0< β <1;

a= 0, b=βαmax,such that (γ^r(αmax))⁰>0;

α= ^b₂;

While|(γ^r(α))⁰|> do if (γ^r(α))⁰ >0 then

b=α;

if not a=α; end if

α= ^−(γ^r^(b))⁰_(γ^b+γ_r_(a))^r^(b)+(γ0−(γ^r^r(b))^(a))⁰⁰^a−γ^r^(a) ; End While

We are now ready to state the generic algorithm for solving LCCO.

The generic algorithm

Threshold parameters >0,µ >¯ 0 andλ∈[0,1],are given;

Start withx0∈ F⁰,µ >µ¯ and a weight vectorr >0;

1) Solve the linear system (2.5) to obtaind;

2) Take t=X⁻¹d;

If ktk ≥

- Determinate ˜α with tangent method ;

- Update xk+1=xk+ ˜αdk, µk+1=λµk and return to 1;

If ktk ≤ Case 1. µk≤µ¯

STOP we have obtained a good approximation of the optimal solution ofP; Case 2.µ_k>µ¯

We have obtained a good approximation of p^r(µ), doµ_k+1=λµ_k and go to 1;

3. Numerical results

In the following section, we apply our algorithm on some different examples of LCCO. A comparative numerical tests with a classical line search are presented, Our implementation is done by the Scilab 5.4.1. We use in the sequel the following notation.

Method 1: the first alternative uses the tangent technique.

Method 2: the second alternative uses the Wolfe method.

(8)

Outer: the number of outer iterations.

Inner: the number of inner iterations.

Objective: the optimal value of the objective function ¯p.

Time: the time measured in seconds. Our tolerance is = 10⁻⁶ in all our testing examples.

The below examples are taken from literature [10], the numerical obtained results with different values of r such as r1 = (0.9, 1, 0.03)^T, r2 = (2, 1, 3, 1, 4)^T , r3= (1, 1, 0.4, 1, 0.4, 1, 0.4, 0.4, 1, 0.96)^T and

r4=

0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1,0.1, 0.1, 0.1 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3

,

are summarized in table 1.

Method 1 Method 2 Example Size (m,n) Inner Outer Inner Outer

1 (2,3) 7 7 162 7

2 (3,5) 24 6 46 8

3 (3,10) 20 7 40 8

4 (10,20) 25 7 83 7

Table 1.

In the following, we compare our approach with the classical path method (non weighted case).

Example with variable size. We consider the following LCCO problem:

¯

p= min[f(x) :x≥0, Ax=b], wheref(x) =

n

X

i=1

x_ilnx_i, b_i= 1 and

A[i, j] =

1 ifi=j or j =i+m), 0 else,

,withn= 2m.

The strictly feasible starting point is:

x⁰= 0.7, . . . , 0.7, 0.3, . . . , 0.3 ^T . The exact solution is:

x^∗= 0.5, 0.5, . . . ,0.5 ^T . The optimal values with different size ofnare:

n 20 400 900

Objective -6.9314718 -138.62944 -311.911623

The obtained numerical results with different size of n and barrier parameterµ are stated in tables 2 and 3.

(9)

Weighted case

The weigh vector isr= (0.011, . . . ,0.011,0.022. . . ,0.022)^T.

n= 20 n= 400 n= 900

µ Outer Time Outer Time Outer Time

0.01 2 0.296×10⁻³ 2 0.17160 2 23.476212

0.25 4 0.316×10⁻³ 4 0.28762 4 32.40515

1 5 0.499×10⁻³ 5 0.355702 5 41.84014

5 6 0.665×10⁻³ 6 0.400961 6 52.96016

Table 2.

Non weighted case

n= 20 n= 400 n= 900

µ Outer Time Outer Time Outer Time

0.01 4 0.325×10⁻³ 4 0. 2915518 4 33.147112

0.25 6 0.482×10⁻³ 6 0.3832547 6 40.40114

1 7 0.591×10⁻³ 7 0.4512415 7 49.88745

5 8 0.835×10⁻³ 8 0.6001489 8 58.91456

Table 3.

4. Conclusion and remarks

In this paper we have introduced a relaxation of the classical path of the perturbed LCCO problem and we have presented a new technique for determining the step-size. These have a great influence on the acceleration of the convergence of the algorithm i.e., the number of iterations and the time produced are reduced signifi- cantly. This analysis may be extended to inducing a general weight vectorw >0 as the barrier parameter instead of the formµrwithr >0.

References

[1] Achache, M.,A weighted-path-following method for the linear complementarity problem, Stud. Univ. Babe¸s-Bolyai Informatica,49(2004), no. 1, 61-73.

[2] Achache, M., A polynomial-time weighted path-following interior-point algorithm for linear optimization, Asian-Eur. J. Math.,13(2020), no. 1, 1-9.

[3] Achache, M., Khebchache, R.,A full-Newton step fessible weighted primal-dual interior point algorithm for monotone LCP, Afr. Mat.,27(2016), no. 3, 591-601.

[4] Achache, M., Khebchache, R.,A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP, Afr. Mat.,27(2016), no. 3, 591-601.

[5] Alzalg, B.,A logarithmic barrier interior-point method based on majorant functions for second-order cone programming, Department of Mathematics, The University of Jordan, Amman 11942, Jordan, (2017).

(10)

[6] Bachir Cherif, B., Merikhi, B.,A penalty method for nonlinear programming, RAIRO Oper. Res.,53(2019), no. 1, 29-38.

[7] Crouzeix, J.-P., Seeger, A.,New bounds for the extreme values of a finite sample of real numbers, J. Math. Anal. Appl.,197(1996), 411-426.

[8] Crouzeix, J.-P., Merikhi, B.,A logarithm barrier method for semi-definite programming, RAIRO Oper. Res.,42(2008), no. 2, 123-139.

[9] Darvay, Zs.,A weighted-path-following method for linear optimization, Stud. Univ. Babe¸s Bolyai Informatica,47(2002), no. 1, 3-12.

[10] Goutali, M.,Complexité et implimentation numérique d’une méthode de points interieurs pour la programmation convexe, Mémoire de Doctorat, Dept. Math. Univ. Sétif, 2018.

[11] Kebbiche, Z., Benterki,D., A weighted-path-following method for linearly constrained convex programming, Rev. Roumaine Math. Pures Appl.,57(2012), no. 3, 245-256.

[12] Kettab, S., Benterki, D.,A relaxed logarithmic barrier method for semidefinite programming, RAIRO Oper. Res.,49(2015), 555-568.

[13] Menniche, L., Benterki, D., Alogarithmic barrier approach for linear programming, J.

Comput. Appl. Math.,312(2017), 267-275.

[14] Zhang, M., Bai, Y., Wang, G., A new primal-dual path-following interior-point algorithm for linearly constrained convex optimization, J. Shanghai Univ.,12(2008), no. 6, 475-480.

Selma Lamri

Laboratoire de Mathématiques Fondamentales et Numériques, Sétif1, Sétif 19000, Algérie

e-mail:[email protected] Bachir Merikhi

e-mail:[email protected] Mohamed Achache

e-mail:achache [email protected]