# Novel Interior Point Algorithms for Solving Nonlinear Convex Optimization Problems

Authors: Sakineh Tahmasebzadeh; Hamidreza Navidi; Alaeddin Malek
Journal: Advances in Operations Research
 (2015)

---

## Abstract

This paper proposes three numerical algorithms based on Karmarkar’s interior point technique for solving
nonlinear convex programming problems subject to linear constraints. The first algorithm uses the Karmarkar
idea and linearization of the objective function. The second and third algorithms are modification of
the first algorithm using the Schrijver and Malek-Naseri approaches, respectively. These three novel schemes
are tested against the algorithm of Kebiche-Keraghel-Yassine (KKY). It is shown that these three novel algorithms
are more efficient and converge to the correct optimal solution, while the KKY algorithm fails in
some cases. Numerical results are given to illustrate the performance of the proposed algorithms.


---

## Body

## 1. Introduction

The simplex method has never had any serious competition until 1984 when Karmarkar proposed a new-polynomial-time algorithm in order to solve linear programming problems, especially for solving large scale problems [1, 2]. Polynomial complexity of Karmarkar’s algorithm has an advantage in comparison with exponential complexity of the simplex algorithm [3–5]. The improvement of the Karmarkar’s algorithm by Schrijver [6, 7] resulted in less number of iterations compared to Karmarkar’s method. In 2004, Malek and Naseri [8] proposed a modified technique based on the interior point algorithm to solve linear programming problems more efficiently.After the appearance of Karmarkar’s algorithm for solving linear programming problems, the researchers developed the algorithm to solve the convex quadratic programming problem (e.g., see [9]). Considering the success of the interior methods for solving linear programming problems [10, 11], the researchers used the linearization methods to solve convex nonlinear programming problems. In 2007, Kebbiche et al. [12] introduced a projective interior point method to solve more general problems with nonlinear convex objective function. The objective of this paper is to propose an optimal step length in each iteration in combination with Karmarkar’s algorithm in order to decrease the nonlinear objective function as fast as possible.In Section2, extension of Karmarkar’s algorithm for nonlinear programming problem is considered. In Section 3, by considering the technique associated with KKY’s algorithm, a modified algorithm is presented. In Section 4, the convergency of modified algorithm in Section 3 is proved. Then this algorithm is combined with Schrijver’s and Malek-Naseri’s algorithms successfully. In Section 5, numerical results are illustrated for KKY algorithm and the three suggested modified algorithms are compared to each other.


## 2. Extension of Karmarkar’s Algorithm for Nonlinear Problems

Consider the following nonlinear optimization problem:(1)minfxs.t.Ax=b,x≥0,where f:Rn→R is a nonlinear, convex, and differentiable function. A is m×n matrix of rank m and b is m×1. The starting point x0>0 is chosen to be feasible. I is the identity matrix with order (n+1) and en+1T is a row vector of n+1 ones.Assumey=(y1,y2,…,yn+1)T=(y[n],yn+1)T, the simplex S={y∈Rn+1∣en+1Ty=1,y≥0}, and the projective transformation of Karmarkar Tk defined by Tk:Rn→S such that Tk(x)=y. Consider g(y)=yn+1[f(Tk+1-1(y))-f(Tk-1(y))], where g:Rn+1→R is a nonlinear, convex, and differentiable function and the optimal value of g is zero. Using the linearization process to the function g in neighborhood of the ball of center y0 as g(y)=g(y0)+∇g(y0)(y-y0) for y∈{y∈Rn+1∣y-y0≤β} along with Karmarkar projective transformation [12], we conclude that Problem (1) is equivalent to (2)min⁡∇gy0Tys.t.Aky=0,en+1Ty=1,y-y0≤β.As a result, the optimal solution of the preceding problem lies along the negative projection of the gradientCp and is given as yk+1=y0-βCp/Cp, where y0=(1/n+1,…,1/n+1)T is the center of the simplex S. Cp is the projected gradient which can be shown to be Cp=[I-PT(PPT)-1P]∇g(y0), where P=Aken+1T, Ak=[ADk,-b], Dk=diag⁡{xk}, and k is the number of iterations. The selection of β as a step length is crucial to enhance the efficiency of the algorithm.The functiong on Y={y∈Rn+1∣Aky=0,y∈S} is convex, since the function f on X={x∈Rn∣Ax=b,x≥0} is convex. The optimal solution of Problem (2) is given by yk+1=y0-βCp/Cp [12].Consider the algorithm of Kebiche-Keraghel-Yassine (KKY) for solving Problem (2).KKY Algorithm. Let ϵ>0 be a given tolerance and let x0>0.Step 1.
Computey0=(1/n+1,…,1/n+1)T and β=n+1/3(n+2). Put k=0.Step 2.
BuildDk=diag⁡{xk},Ak=[ADk,-b] and P=Aken+1T.
ComputeCp=[I-PT(PPT)-1P]∇g(y0), yk+1=y0-βCp/Cp, and xk+1=Dkyk+1[n]/yn+1K.Step 3.
Whilef(xk+1)-f(xk)>ϵ, let k=k+1, and go to Step 2.However, as we can see in the following two examples, the KKY algorithm does not work for every nonlinear problem.Example 1.
Consider the quadratic convex problem:(3)min⁡fx=x12+x22-2x1-4x2s.t.x1+4x2+x3=5,2x1+3x2+x4=6,x1,x2,x3,x4≥0.For toleranceϵ=10-8, after k=161 iterations for KKY algorithm we havex161=[0.00000000, 2.00005934, -3.00008255, -0.00000000]T and f(x161)=-3.9999999964. Since the condition f(x162)-f(x161)=4.47×10-9<10-8 holds, the algorithm stopped, whereas this solution is not feasible.Example 2.
Consider the nonlinear convex problem:(4)min⁡fx=32x12+x22+2x32+x42-ln⁡x1x4-3x1x2+4x3x4-2x1-3x4s.t.x1+14x4-8x5-x6+9x7=0,x2+12x4-12x5-12x6+3x7=0,x3+x6=1,x1,x2,…,x7≥0.
Forϵ=10-8, β=8/27∈[0.27,0.36], and k=1 iteration using KKY algorithm the solution x1=[-5.2199,-1.8871,0.4463,0.3791,-0.0087,0.5536,0.6232]T is calculated. This solution is not feasible.Here, two difficulties arise. First,xk must stay feasible in each iteration. Second, in the moderate time the required tolerance must be satisfied. To overcome these difficulties we modify the KKY algorithm in the next section.


## 3. Modified Algorithm

### 3.1. Modifications

In the KKY [12] algorithm β∈[0.27,0.36]. As it is observed in Examples 1 and 2, for these values of β, the KKY algorithm may produce infeasible solution. In the standard Karmarkar [1, 3, 4] instead of β, αr=(n+1/3(n+2))(1/(n+1)(n+2)) is used. Hence the solution in each iteration remains feasible. In this case, the optimal solution for Problem (2) is given by yk+1=y0-βCp/Cp, where β=αr. Applying KKY algorithm with β=αr to the problem in Example 2, it gives the feasible solution x80=[0.7517262,0.0000174,0.0000056,1.0209196, 0.0008742,0.9999943,0.0000035]T, f(x80)=-1.3692774913, and f(x81)=-1.3692882373. The algorithm stops after k=80 iterations since f(x81)-f(x80)=-1.0746×10-5, while the suitable accuracy ϵ=10-8 is not reached. In each iteration, linear search method is used to find 0<λ≤1 such that f(xk+1)≤f(xk), where the suitable tolerance satisfies. Thus one may write Problem (2) in the following form: (5)min⁡∇gy0Tys.t.Aky=0,en+1Ty=1,y-y0≤λαr.Lemma 3.
The optimal solution for Problem (5) is given by yk+1=y0-λαrCp/Cp.Proof.
We putx=y-y0, and then we have Px=Aken+1T(y-y0)=0 and Problem (5) is equivalent to (6)min⁡∇gy0Txs.t.Px=0,x2≤λ2α2r2.x∗ is a solution of Problem (6) if and only if there exist ω∈Rm+1 and μ≥0 such that (7)∇gy0+PTω+μx∗=0.Multiplying both sides of (7) by P and since Px∗=0, we get P∇g(y0)+PPTω=0. Then ω=-(PPT)-1(P∇g(y0)); by substituting ω in (7) we find (8)x∗=-1μI-PTPPT-1P∇gy0.By assuming CP=[I-PT(PPT)-1P]∇g(y0), we have (9)x∗=1μCP=λαr⟹1μ=λαrCP,⟹x∗=-λαrCPCP.And we have yk+1=y∗=y0+x∗=y0-λαrCP/CP.Note that here we have proposed the algorithm similar to KKY, whereβ=λαr. This modified algorithm has the advantage that can find the feasible approximate solution in the suitable tolerance.


### 3.2. Modified KKY Algorithm (MKKY)

Letϵ>0 be a given tolerance and x0 is a strictly feasible point.Step 1.
Computey0=(1/n+1,…,1/n+1)T, r=1/(n+1)(n+2), and α=n+1/3(n+2). Put λ=1 and k=0.Step 2.
BuildDk=diag⁡{xk},Ak=[ADk,-b], and P=Aken+1T.
ComputeCp=[I-PT(PPT)-1P]∇g(y0), yk+1=y0-λαrCp/Cp, and xk+1=Dkyk+1[n]/yn+1K.Step 3.
Whilef(xk+1)-f(xk)>ϵ, put k=k+1.
BuildDk=diag⁡{xk},Ak=[ADk,-b], and P=Aken+1T.
ComputeCp=[I-PT(PPT)-1P]∇g(y0) and yk+1=y0-λαrCp/Cp.
Thenxk+1=Tk-1(yk+1)=Dkyk+1[n]/yn+1K.
Letk=k+1, and go to Step 3.Step 4.
Whilef(xk+1)>f(xk), compute λ=1/2λ, yk+1=y0-λαrCp/Cp, and xk+1=Dkyk+1[n]/yn+1K.Step 5.
Letk=k+1, and go to Step 3.


## 3.1. Modifications

In the KKY [12] algorithm β∈[0.27,0.36]. As it is observed in Examples 1 and 2, for these values of β, the KKY algorithm may produce infeasible solution. In the standard Karmarkar [1, 3, 4] instead of β, αr=(n+1/3(n+2))(1/(n+1)(n+2)) is used. Hence the solution in each iteration remains feasible. In this case, the optimal solution for Problem (2) is given by yk+1=y0-βCp/Cp, where β=αr. Applying KKY algorithm with β=αr to the problem in Example 2, it gives the feasible solution x80=[0.7517262,0.0000174,0.0000056,1.0209196, 0.0008742,0.9999943,0.0000035]T, f(x80)=-1.3692774913, and f(x81)=-1.3692882373. The algorithm stops after k=80 iterations since f(x81)-f(x80)=-1.0746×10-5, while the suitable accuracy ϵ=10-8 is not reached. In each iteration, linear search method is used to find 0<λ≤1 such that f(xk+1)≤f(xk), where the suitable tolerance satisfies. Thus one may write Problem (2) in the following form: (5)min⁡∇gy0Tys.t.Aky=0,en+1Ty=1,y-y0≤λαr.Lemma 3.
The optimal solution for Problem (5) is given by yk+1=y0-λαrCp/Cp.Proof.
We putx=y-y0, and then we have Px=Aken+1T(y-y0)=0 and Problem (5) is equivalent to (6)min⁡∇gy0Txs.t.Px=0,x2≤λ2α2r2.x∗ is a solution of Problem (6) if and only if there exist ω∈Rm+1 and μ≥0 such that (7)∇gy0+PTω+μx∗=0.Multiplying both sides of (7) by P and since Px∗=0, we get P∇g(y0)+PPTω=0. Then ω=-(PPT)-1(P∇g(y0)); by substituting ω in (7) we find (8)x∗=-1μI-PTPPT-1P∇gy0.By assuming CP=[I-PT(PPT)-1P]∇g(y0), we have (9)x∗=1μCP=λαr⟹1μ=λαrCP,⟹x∗=-λαrCPCP.And we have yk+1=y∗=y0+x∗=y0-λαrCP/CP.Note that here we have proposed the algorithm similar to KKY, whereβ=λαr. This modified algorithm has the advantage that can find the feasible approximate solution in the suitable tolerance.


## 3.2. Modified KKY Algorithm (MKKY)

Letϵ>0 be a given tolerance and x0 is a strictly feasible point.Step 1.
Computey0=(1/n+1,…,1/n+1)T, r=1/(n+1)(n+2), and α=n+1/3(n+2). Put λ=1 and k=0.Step 2.
BuildDk=diag⁡{xk},Ak=[ADk,-b], and P=Aken+1T.
ComputeCp=[I-PT(PPT)-1P]∇g(y0), yk+1=y0-λαrCp/Cp, and xk+1=Dkyk+1[n]/yn+1K.Step 3.
Whilef(xk+1)-f(xk)>ϵ, put k=k+1.
BuildDk=diag⁡{xk},Ak=[ADk,-b], and P=Aken+1T.
ComputeCp=[I-PT(PPT)-1P]∇g(y0) and yk+1=y0-λαrCp/Cp.
Thenxk+1=Tk-1(yk+1)=Dkyk+1[n]/yn+1K.
Letk=k+1, and go to Step 3.Step 4.
Whilef(xk+1)>f(xk), compute λ=1/2λ, yk+1=y0-λαrCp/Cp, and xk+1=Dkyk+1[n]/yn+1K.Step 5.
Letk=k+1, and go to Step 3.


## 4. Convergence for Modified Algorithm (MKKY)

In order to establish the convergence of the modified algorithm, we introduce a potential function associated with Problem (1) defined by (10)ϕx=n+1ln⁡fx-z∗-∑i=1nln⁡xi,where z∗ is the optimal value of the objective function.Lemma 4.
Ifyk+1 is the optimal solution of Problem (5), then g(yk+1)<g(y0).Proof.
Sinceg(yk+1)=g(y0)+∇g(y0)T(yk+1-y0) and yk+1=y0-λαrCP/CP, then (11)gyk+1-gy0=∇gy0T-λαrCPCP=-λαrCP∇gy0CP=-λαrCPCP2=-λαrCP<0.Thus g(yk+1)<g(y0) and a reduction is obtained in each iteration.Lemma 5.
Ifyk+1 is the optimal solution of Problem (5), then(12)gyk+1≤1-λαn+1gy0.Proof.
Letx∗ be the optimal solution of Problem (1); we can write x∗=Tk-1(y∗). B(y0,λαr) is a ball of center y0 with radius λαr. There are two cases:(i)
Ify∗∈Y∩B(y0,λαr), then (13)0≤gyk+1≤gy∗=0<1-λαn+1gy0,and Lemma5 holds.(ii)
Ify∗∉Y∩B(y0,λαr), since Y is convex, intersection point of the boundary of Y∩B(y0,λαr) and the line segment between y0 and y∗ should be feasible for Problem (5). Let y^k+1 be the intersection point; then y^k+1 satisfies y^k+1=θy∗+(1-θ)y0 for θ∈(0,1), and y^k+1-y0=λαr. Thus, (14)y^k+1-y0=θy∗-y0=λαr⟹y∗-y0=λαrθ.Hence,(15)y∗-y02=y∗2+y02-2y0Ty∗,and we have (16)y∗=∑i=1n+1yi∗2≤∑i=1n+1yi∗2=en+1Ty∗2=1,y02=1n+1en+12=1n+1,y0Ty∗=1n+1en+1Ty∗=1n+1.Thus,(17)y∗-y02≤1+1n+1-2n+1=nn+1≤n+1n+2.From (14) we also have y∗-y02=(λαr/θ)2; therefore (18)λαrθ2≤n+1n+2orλαrθ≤n+1n+2.Substituting r=1/(n+1)(n+2) in the above inequality, we have θ≥λα/n+1. Since g is convex and g(y∗)=0, then (19)gy^k+1≤θgy∗+1-θgy0≤1-λαn+1gy0.Furthermore, g(yk+1)≤g(y∗); then g(yk+1)≤(1-λα/n+1)g(y0).Theorem 6.
In every iteration of the algorithm MKKY, potential function is reduced by a constant valueδ such that ϕ(xk+1)≤ϕ(xk)-δ.Proof.
Consider(20)ϕxk+1-ϕxk=n+1ln⁡fxk+1-z∗fxk-z∗-∑i=1nln⁡xik+1xik=n+1ln⁡gyk+1gy0-∑i=1n+1ln⁡yik+1≤n+1ln⁡1-λαn+1-∑i=1n+1ln⁡yik+1≤-λα+λ2α221-λα2.
We used the result demonstrated by Karmarkar [1]: (21)-∑i=1n+1ln⁡yik+1≤λ2α221-λα2.Then ϕ(xk+1)≤ϕ(xk)-δ, where δ=-λα+λ2α2/2(1-λα)2.
Ifα=n+1/3(n+2), then ϕ(xk+1)≤ϕ(xk)-0.2.
Thereforeϕ(xk+1)≤ϕ(x0)-0.2(k+1).Theorem 7.
Ifx0 is the feasible solution of Problem (1) and x∗ is the optimal solution with optimal value z∗, then one has following assumptions:(1)
x0≥2-Len.(2)
x∗≤2Len; for any feasible solution x one has -23L≤z∗≤f(x)≤23L.
The algorithm MKKY finds an optimal solution afterO(nL) iteration. L is the number of bytes.Proof.
Consider(22)fxk-z∗fx0-z∗=γxkexp⁡ϕxk-ϕx0n+1,where(23)γxk=exp⁡∑i=1nln⁡xik-∑i=1nln⁡xi0n+1.By assumptions (1) and (2) we have γ(xk)≤22L in the feasible region; then (24)fxk-z∗≤22lfx0-z∗exp⁡ϕxk-ϕx0n+1.According to Theorem 6, after k iterations, we have ϕ(xk)-ϕ(x0)≤-kδ. Thus, (25)fxk-z∗≤22lfx0-z∗exp⁡-kδn+1≤25Lexp⁡-kδn+1≤2-4L.Therefore, f(xk)-z∗≤2-4L for k≥45L(n+1).In the next section MKKY algorithm is combined with the algorithm of Schrijver [6, 7] and Malek-Naseri’s algorithm [8] to propose novel hybrid algorithms called Sch-MKKY (Schrijver-Modified Kebiche-Keraghel-Yassine) and MN-MKKY (Malek-Naseri-Modified Kebiche-Keraghel-Yassine). These algorithms are different from MKKY in the use of optimal length in each iteration.


### 4.1. Hybrid Algorithms

Let us assume thatr and y0 in the modified algorithm are expressed as follows: r=n+2/n+1 and y0=(1,1,…,1)T. In the Sch-MKKY and MN-MKKY algorithms, choose α=1/1+r and α=1-1/(n+2)4(1+n(n+1)), respectively. It is easy to prove that the theorems in Section 4 satisfy Sch-MKKY and MN-MKKY algorithms. Thus with the recent step length the convergence is guaranteed.


## 4.1. Hybrid Algorithms

Let us assume thatr and y0 in the modified algorithm are expressed as follows: r=n+2/n+1 and y0=(1,1,…,1)T. In the Sch-MKKY and MN-MKKY algorithms, choose α=1/1+r and α=1-1/(n+2)4(1+n(n+1)), respectively. It is easy to prove that the theorems in Section 4 satisfy Sch-MKKY and MN-MKKY algorithms. Thus with the recent step length the convergence is guaranteed.


## 5. Numerical Results

It is observed that the approximate solution from KKY algorithm is not feasible in some instances (see Examples8, 9, and 11 in Table 1). All programs have been written with MATLAB 7.0.4 for ϵ=10-8 as tolerance. The computed solution for KKY, Sch-MKKY, and MN-MKKY is given in Table 1.Table 1
Computed solutions using four different algorithms for Examples8, 9, 10, and 11.
Examples
x
KKY
MKKY
Sch-MKKY
MN-MKKY
Example8
x
1
1.1176285677
0.7993104755
0.7992885091
0.7984677572
x
2
0.8925922545
1.2006283419
1.2006478942
1.2013756245
x
3
−0.0102208222
0.0000611826
0.0000635969
0.0001566183
x
4
1.3324440588
0.3980537916
0.3979927208
0.395765081
Example9
x
1
−5.2199797446
0.7514629509
0.7514297188
0.7514274997
x
2
−1.8871925195
0.0000032699
0.0000065967
0.0000068198
x
3
0.4463304312
0.0000010511
0.0000021234
0.0000022020
x
4
0.3791651531
1.0175937272
1.0172339995
1.0172101531
x
5
−0.0087312913
0.0007335551
0.0007190583
0.0007180983
x
6
0.5536695688
0.9999989489
0.9999978766
0.9999977980
x
7
0.6232230772
0.0000006675
0.0000013472
0.0000013940
Example10
x
1
0.0000000025
0.0000000156
0.0000000055
0.0000000080
x
2
1.9999999829
1.9999999858
1.9999999749
1.9999999586
x
3
0.0000000025
0.0000000156
0.0000000055
0.0000000080
Example11
x
1
0.3124560511
0.7142857707
0.7142857350
0.7142857453
x
2
0.3438507936
0.1428572168
0.1428571684
0.1428571600
x
3
0.0001576431
0.0000002101
0.0000000702
0.0000000498
x
4
−1.4064826279
0.0000001087
0.0000000363
0.0000000258Example 8.
Consider the quadratic convex problem:(26)min⁡fx=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x2+x3=2,-x1+2x2+x4=2,x1,…,x4≥0.As it is shown, the KKY algorithm does not converge to the correct solution, while the computed solution of MKKY and two hybrid algorithms is feasible. Example8 is solved by using Fmincon from MATLAB 7.0.4 and the absolute difference of the objective functions stated as Error. In Table 2 number of iterations, solution norms, optimal values of the objective function, Error, and the elapsed time for each algorithm have been given.Table 2
Comparison between four different algorithms for Examples8, 9, 10, and 11.
Examples
Algorithm
k
‖
x
∗
‖
f
(
x
∗
)
Error
CPU time (sec)
Example8
KKY (infeasible)
—
—
—
—
—
MKKY
549
1.4962795449
−7.1998265727
1.7344
×
1
0
-
4
182.8281
Sch-MKKY
515
1.4962672544
−7.1998196616
1.8034
×
1
0
-
4
153.4063
MN-MKKY
187
1.4958093895
−7.1995511207
4.4888
×
1
0
-
4
83.5313
Example9
KKY (infeasible)
—
—
—
—
—
MKKY
181
1.6125110840
−1.3693639744
1.6216
×
1
0
-
5
213.1250
Sch-MKKY
87
1.6122679375
−1.3693475555
3.2635
×
1
0
-
5
122.4229
MN-MKKY
67
1.6122518087
−1.3693463904
3.3800
×
1
0
-
5
79.1875
Example10
KKY
17
1.9999999829
−3.9999999317
6.8305
×
1
0
-
8
11.4844
MKKY
80
1.9999999858
−3.9999999433
5.6661
×
1
0
-
8
46.5469
Sch-MKKY
37
1.9999999749
−3.9999998994
1.0058
×
1
0
-
7
22.5625
MN-MKKY
15
1.9999999586
−3.9999998343
1.6570
×
1
0
-
7
10.7031
Example11
KKY (infeasible)
—
—
—
—
—
MKKY
61
0.7284314289
−0.2039626101
3.2040
×
1
0
-
8
35.7188
Sch-MKKY
30
0.7284313844
−0.2039626256
8.9867
×
1
0
-
9
18.4531
MN-MKKY
12
0.7284313929
−0.2039626212
1.3372
×
1
0
-
8
9.0781In Table2 we show that MN-MKKY algorithm is more efficient than the other algorithms comparing the number of iterations and elapsed time.In Figure1, for various tolerances, the number of iterations is compared for different algorithms. It is observed that the MN-MKKY algorithm has better performance for each required tolerance.Figure 1
The tolerances against number of iterations are compared for MKKY, Sch-MKKY, and MN-MKKY algorithms for Examples8, 9, 10, and 11.
(a)
Example8
(b)
Example9
(c)
Example10
(d)
Example11Example 9.
Consider Example2. Table 2 shows the computed solution for four different algorithms. From Figure 1, it is obvious that MN-MKKY algorithm is the best for this example.Example 10.
Consider the quadratic convex problem:(27)min⁡fx=x12+x22-8x2+8s.t.x1+2x2+x3=4,x1,x2,x3≥0.Example 11.
Consider the nonlinear convex problem:(28)min⁡fx=x12+2x25-x1s.t.x1+2x2-x3=1,-3x1+x2+x4=-2,x1,x2,x3,x4≥0.


## 6. Conclusion

Having two ideas in our mind, (i) calculation of feasible solution in each iteration and (ii) the fact that the objective function value must decrease in each iteration with the fixed desired tolerance, this paper proposed three hybrid algorithms for solving nonlinear convex programming problem based on the interior point idea using variousβ’s of Karmarkar, Schrijver, and Malek-Naseri techniques. These methods have better performance than the standard Karmarkar algorithm, since in the latter algorithm one may not check the feasibility of solution in each iteration.Our numerical simulation shows that the MN-MKKY algorithm has the best performance among the other algorithms. This algorithm uses less number of iterations to solve the general nonlinear optimization problems with linear constraints, since it uses the step lengthβ of Malek-Naseri type.



---

*Source: 487271-2015-09-16.xml*