# A Method of Two New Augmented Lagrange Multiplier Versions for Solving Constrained Problems

Authors: Hamsa Th. Saeed Chilmeran; Eman T. Hamed; Huda I. Ahmed; Abbas Y. Al-Bayati
Journal: International Journal of Mathematics and Mathematical Sciences
 (2022)

---

## Abstract

One of the more restrictive methods of improvement is the augmented Lagrange method. Two versions are built in the external framework and the internal framework of the proposed method. The first basic version of the proposed algorithm includes a new derivation of Lagrange multiples and different penalty criteria, and the second version is the internal framework in which the unconstrained algorithm known as the conjugate gradient (CG) method was incorporated; also, a new parameter was derived in the search direction. The numerical results are indicative of the stability, efficiency, and speed of the proposed algorithm, based on performance profiles provided by Dolan and More.


---

## Body

## 1. Introduction

All major constraining problem strategies have been categorized into two basic categories: direct and indirect methods. However, indirect methods create subproblem methods that do not contain restrictions. Lagrange function techniques transform a restricted problem into an unconstrained problem. The technique is basically easy and very powerful. Augmented Lagrange algorithms are well-known and successful methods of solving restrictive optimization problems that are commonly used in various engineering and economic fields. In this paper, we present improvement problems that are restricted to equality.(1)minimizex∈Rnf−xξix≥b−,1≤i≤η,where b− is a constant and f and ξ are a map from Rn to R; replacing a constrained optimization problem by a series of unconstrained problems by adding a Barrier term [1–4], there is a general formulation of the augmented Lagrange method defined as follows:(2)Ax,r,λ=f−x−∑i=1mλ−iξi+rk∑i=1mAξixη−13+∈2ξixη−12−ξixη−1+1∈−1−η1−∈.Several authors have studied several formulas for previous years [5–7].


## 2. First Version (Two Multipliers,λ−i1∗λ−i2∗) (Say, NEW1)

This section provides a detailed breakdown of our improved Lagrange method to solve optimization problem (1). It is a catalyst and differs from the standard augmented Lagrange method to obtain a new value. We derive two new formula-modified Lagrange multipliers. We begin with the augmented Lagrange definition. The general formula of Lagrange functions is(3)LAGx,λ−=f−x−∑i=1mλi−ξix+∑i=1mrAξixη−13+∈2ξixη−12−ξixη−1+1∈−1−η1−∈.The gradient of Lagrange function is(4)∇LAGx,λ−=∇f−x−∑i=1mλ−∗+r∑i=1m3Aξixη−12+∈ξixη−1−11η∇ξix.The new modified barrier augmented Lagrange multiplier method is defined by(5)ALMx,r,λi1∗−=f−x−∑i=1mλi1−ξix+r∑i=1mlnAξixη−13+∈2ξixη−12−ξixη−1+1∈−1−η1−∈,∇ALMx,r,λi1∗−=∇f−x−∑i=1mλi1∗−+r∑i=1m3Aξix/η−12+∈ξix/η−12−11/ηAξix/η−13+∈/2ξix/η−12−ξix/η−1+1/∈−1−η1−∈∇ξix.Compare (3) with (4) to obtain the first multiplier as follows:(6)λ∗−=λi1∗−+rAξix/η−13+∈/2ξix/η−12−ξix/η−1+1/∈−1−η1−∈.Now, we will derive the second multiplierλi2∗−:(7)ALMx,r,λ−=f−x+∑i=1mλi−ξix−r∑i=1m−ξix1−∈∈−1,∇ALMx,r,λ−=∇f−x+∑i=1mλi−+∑i=1mrξix−∈∇ξix,ALMx,r,λ−=f−x+∑i=1mλi2−ξix+r∑i=1mln−ξix1−∈∈−1,∇ALMx,r,λ−=∇f−x+∑i=1mλi2−+∑i=1m∈−1ξix−∈−ξix1−∈∇ξix.Compare (6) with (7) to obtain the following:(8)λ∗−=λi2−+r∈−1ξix−∈−ξix1−∈.


## 3. Conjugate Gradient (CG) Method with the Constrained Problem

Now, we turn to the new second part, increasing the efficiency of internal iteration by optimizing the line search to quickly reach the optimum value with the least error by using an effective CG method. This method is very popular among mathematicians who are interested in solving large-scale constrained nonlinear optimization problems:(9)minimizexÎRnfx,where f:Rn⟶R is a smooth function; it creates a series of successive points that take shape as(10)xk+1=xk+μk.The parameterμk is cubic line search direction, and it creates a series of successive dk as(11)dk+1=−∇ALMk+1fork=0,dk+1=−∇ALMk+1+∂kdk,fork≥1,where ∂k∈R is known as the conjugacy coefficient. Different CG modes are adopted by different and multiple choices of ∂k. Scientists have conducted many studies in [8–20], letting gk+1T=∇ALMk+1T. The standard Wolfe conditions are(12)fxk+μkdk−fxk≤δϖϖk∇ALMk+1T.The constants are within the period0<δ<σ<1 [21, 22].(13)∇ALMk+1′Tdk≥∂k∇ALMk+1Tdk.


## 4. Second Version (Scaling Parameter,θk) (Say, New2)

In this version, a new scalar is proposed to improve the CG method. The directiondk+1 is defined by(14)dk+1=−θk+1+1gk+1+∂ksk.And, ∂k is defined by the formula in [13], i.e.,(15)dk+1=−θk+1+1gk+1+ykTgk+1skTyk−skTgkskTyksk.Multiplying both sides of (15) by yk, then we get(16)dk+1Tyk=−θk+1+1gk+1Tyk+ykTgk+1skTyk−skTgkskTykskTyk.We have(17)dk+1Tyk=−tgk+1Tsk.Using (17) in (16) yields(18)−tgk+1Tsk=−θk+1+1gk+1Tyk+ykTgk+1skTyk−skTgkskTykskTyk,tgk+1Tsk−gk+1Tyk−ykTgk+1skTykskTgkskTykskTyk=θk+1gk+1Tyk,θk+1=tgk+1Tskgk+1Tyk−1−skTgkskTyk,dk+1=−tgk+1Tskgk+1Tyk−1−skTgkskTyk+1gk+1T+ykTgk+1skTyk−skTgkskTykskT,dk+1New=−tgk+1Tskgk+1Tyk+skTgkskTykgk+1T+ykTgk+1skTyk−skTgkskTyksk.


## 5. Convergence Analysis of the New Proposed Method

Affinity analysis is performed for new method (20), based on inexact line research given by Wolfe line search. We shall also show that the CG coefficients achieve appropriate ratio conditions and global convergence characteristics. In light of this inexact line research (12) and (13), first, we will seek sufficient conditions.


### 5.1. Sufficient Descent Conditions

For the requirement of sufficient proportions, we present the following theory.Theorem 1.
Letϖk defined in (12) achieve the relations (12) and (13); then, the direction defined by (20) is a descent direction.Proof.
Multiply both sides of (18) by gk+1/gk+12 to obtain(19)dgk+1Tk+1gk+12=−tgk+1Tskgk+1Tyk+skTgkskTykgk+1Tgk+1gk+12+ykTgk+1skTyk−skTgkskTykskTgk+1gk+12,(20)skTgk+1≤skTyk,ykTgk+1≤yk⋅gk+1⟶1−ykTgk+1≤1−yk.gk+1,dk+1Tgk+1gk+12≤−tskTykgk+1yk+skTgkskTyk+gk+1ykskTyk−skTgkskTykskTykgk+12,dk+1Tgk+1gk+12≤−tskTykgk+1yk+skTgkskTyk−ykgk+1−skTgkskTyk,dk+1Tgk+1gk+12≤−tskTykgk+1yk+skTgkskTyk1−ykgk+1.
We have(21)skTgk≤−skTykσ+1.
Using (23) in (22) yields(22)dk+1Tgk+1gk+1≤−tskTykgk+1yk+−skTykσ+1skTyk≤0,dk+1Tgk+1≤0.


### 5.2. Global Convergent Properties

To prove that new method (20) fulfills the convergence conditions, we need some basic convergence hypotheses, the most important of which is the oneness condition of the solution. For additional details, see [23–25].Lemma 1.
With reliance on assumption foundations, the convergence property of (20) and the step length ϖ is achieved with relations (12) and (13). If(23)∑k≥11dk+12=∞,then(24)Limk⟶∞infgk=0.Theorem 2.
Suppose that our assumption is correct, the new direction defined by (18) is descent, and ϖk is computed using (12) and (13); then,(25)Limk⟶∞infgk=0.Proof.
Since∂k is a positive parameter defined between zero and one, i.e., ∂k=max∂kHS,0, then(26)∂k=c1,where 0<c1<1 and(27)θk+1=tgk+1Tskgk+1Tyk−1−skTgkskTyk.
From (11) and (12) and skTgk+1≤skTyk, we obtain(28)θk+1≤tskTykgk+1Tgk+1−gk+1+skTgkskTyk.
Sincedk=−gk, we obtain(29)θk+1≤tskTykgk+1Tgk+1+dk+1+skTgkskTyk.
From Wolfe conditions (12) and (13), we have(30)θk+1≤tskTykgk+1Tgk+1+σgk+1+αgkskTyk.
Let(31)tskTykgk+1Tgk+1+σgk+1+αgkskTyk=ς,whereς>0.
Therefore, from (14), we have(32)dk+1≤θk+1gk+1+∂ksk.
Hence, from (26) and (31), we have(33)dk+1≤ςgk+1+c1sk=D,∑k≥11dk+12≥1D∑k≥11=∞.
That is,Limk⟶∞gk=0, and hence, the proof is complete.


## 5.1. Sufficient Descent Conditions

For the requirement of sufficient proportions, we present the following theory.Theorem 1.
Letϖk defined in (12) achieve the relations (12) and (13); then, the direction defined by (20) is a descent direction.Proof.
Multiply both sides of (18) by gk+1/gk+12 to obtain(19)dgk+1Tk+1gk+12=−tgk+1Tskgk+1Tyk+skTgkskTykgk+1Tgk+1gk+12+ykTgk+1skTyk−skTgkskTykskTgk+1gk+12,(20)skTgk+1≤skTyk,ykTgk+1≤yk⋅gk+1⟶1−ykTgk+1≤1−yk.gk+1,dk+1Tgk+1gk+12≤−tskTykgk+1yk+skTgkskTyk+gk+1ykskTyk−skTgkskTykskTykgk+12,dk+1Tgk+1gk+12≤−tskTykgk+1yk+skTgkskTyk−ykgk+1−skTgkskTyk,dk+1Tgk+1gk+12≤−tskTykgk+1yk+skTgkskTyk1−ykgk+1.
We have(21)skTgk≤−skTykσ+1.
Using (23) in (22) yields(22)dk+1Tgk+1gk+1≤−tskTykgk+1yk+−skTykσ+1skTyk≤0,dk+1Tgk+1≤0.


## 5.2. Global Convergent Properties

To prove that new method (20) fulfills the convergence conditions, we need some basic convergence hypotheses, the most important of which is the oneness condition of the solution. For additional details, see [23–25].Lemma 1.
With reliance on assumption foundations, the convergence property of (20) and the step length ϖ is achieved with relations (12) and (13). If(23)∑k≥11dk+12=∞,then(24)Limk⟶∞infgk=0.Theorem 2.
Suppose that our assumption is correct, the new direction defined by (18) is descent, and ϖk is computed using (12) and (13); then,(25)Limk⟶∞infgk=0.Proof.
Since∂k is a positive parameter defined between zero and one, i.e., ∂k=max∂kHS,0, then(26)∂k=c1,where 0<c1<1 and(27)θk+1=tgk+1Tskgk+1Tyk−1−skTgkskTyk.
From (11) and (12) and skTgk+1≤skTyk, we obtain(28)θk+1≤tskTykgk+1Tgk+1−gk+1+skTgkskTyk.
Sincedk=−gk, we obtain(29)θk+1≤tskTykgk+1Tgk+1+dk+1+skTgkskTyk.
From Wolfe conditions (12) and (13), we have(30)θk+1≤tskTykgk+1Tgk+1+σgk+1+αgkskTyk.
Let(31)tskTykgk+1Tgk+1+σgk+1+αgkskTyk=ς,whereς>0.
Therefore, from (14), we have(32)dk+1≤θk+1gk+1+∂ksk.
Hence, from (26) and (31), we have(33)dk+1≤ςgk+1+c1sk=D,∑k≥11dk+12≥1D∑k≥11=∞.
That is,Limk⟶∞gk=0, and hence, the proof is complete.


## 6. Results and Discussion

To verify the effectiveness of the proposed algorithms, we performed different numerical experiments that could be summarized into three comparison activities. The first is to compare Lagrange’s algorithm using the new derivative Lagrange multiplier with standard algorithms in this field. As for the second efficacy, a comparison of some optimized conjugate gradient algorithms was performed with those known in this field. The final efficacy consists of a combined comparison of Lagrange’s algorithm modification and conjugate gradient optimization developed with a classic algorithm. The new augmented Lagrange methods attempt to minimize the Lagrange multiplier and the penalty parameter in each iteration which means less cost function and time required to implement the method and also the new versions are used for modifying the line search of conjugate gradient use of those multipliers to reduce the errors and avoid the use arbitrary values. All algorithms implement the Wolfe line search conditions withδ = 0.0001 and σ = 0.001. The numerical results are too effective when compared with other established algorithms. To solve the standard constrained problem, we demonstrate the global convergence of the proposed method. The new restrictive CG technology has been tested on more than twenty specific test functions (see Appendix [23] for details of these test issues). We demonstrated results of all experiments using the Dolan and More’ profile [25].The experiments shown in Figures1–3 show the performance of the above methods concerning the number of iterations and the number of job evaluations, and Figure 3 shows the CPU time.Figure 1
The performance of the given methods relative to iterations.Figure 2
The performance of the given methods relative to the number of function evaluations.Figure 3
The performance of the given methods relative to CPU time.


## 7. Conclusions

The results of the current study of the two new versions showed that the newly proposed method developed has the potential to reduce the cost of the job, the time required to reach the solution, and the number of required iterations compared to some well-known CG methods by using the Dolan–More profile.



---

*Source: 3527623-2022-04-23.xml*