Microsoft Word - ETASR_V13_N1_pp10073-10077 Engineering, Technology & Applied Science Research Vol. 13, No. 1, 2023, 10073-10077 10073 www.etasr.com Leulmi: A Comparative Numerical Study between Minorant Functions and Line Search Methods in … A Comparative Numerical Study between Minorant Functions and Line Search Methods in Penalty Methods for Linear Optimization Assma Leulmi Department of Mathematics, Ferhat Abbas University Setif-1, Algeria as_smaleulmi@yahoo.fr (corresponding author) Received: 16 November 2022 | Revised: 27 November 2022 | Accepted: 2 December 2022 ABSTRACT The aim of this paper is to present a comparative numerical study between the minorant functions and line search methods in computing the step size in the penalty method for linear optimization. The minorant functions were confirmed by many interesting numerical experimentations to be more beneficial than the classical line search methods. Keywords-linear optimization; penalty methods; line search; minorant function I. INTRODUCTION Optimization is an especially interesting topic in data science. Linear Optimization (LO) or Linear Programming (LP) problems form an important class of optimization problems, aiming to find the feasible region and optimize the solution in order to have the highest or lowest value of a function. It is now well established as an important and very active branch of applied mathematics. The wide applicability of LO models and its richness as a mathematical theory that underlines these models and the methods developed to solve them have been the driving forces behind the rapid and continuing evolution of the subject. The template is general enough to express many different problems in engineering, industry, commerce, economics, business administration, physical sciences, and mathematics, or in any other area where decisions (in a board sense) must be taken in some complex (or conflicting) situation that can be represented by a mathematical model. There are two classes of methods for the resolution of LO problems, simplex method and interior point methods. In this study, we are interested in interior point methods. These are efficient methods developed to solve LO and NP problems. Several algorithms have been proposed to solve LO problems. Some fundamental classes of interior point methods are the affine method, the projective method with the potential reduction of Karmarkar and its alternatives [5, 9], central trajectory methods, and penalty/barrier methods [6, 13]. Our work is based on the latter type of interior point methods for solving LO problems. In this paper, we propose a logarithmic barrier interior- point method for solving LO problems. In fact, the main difficulty to be anticipated in establishing iterations in such a method will come from the determination and computation of the step-size. The aim of this paper is to present a comparative numerical study between the line search methods and the minorant function to compute the step-size along the direction in barrier logarithmic methods. II. PROBLEM FORMULATION We consider the following LO problem � min� �� � � � ≥ �, � ∈ �� . (1) where ∈ ��×� , such that ���� = � < �, � ∈ �� and � ∈ �� . The problem (1) is the dual of the following linear program: � max � � ! � ! = �! ∈ �� , ! ≥ 0. (2) The problem (1) can be written in the following standard form: $ min� �� � � � − � = & � ∈ �� , & ∈ �� , & ≥ 0. (3) One of the advantages of problem (1) with respect to its dual problem (2) is that the variable of the objective function is a vector instead of a matrix. Furthermore, under certain convenient hypothesis, the resolution of problem (1) is equivalent to (2) in the sense that the optimal solution of one of the two problems can be reduced directly from the other through the application of the theorem of the sladeness complementary [15]. In the rest of the paper, the following are denoted: Engineering, Technology & Applied Science Research Vol. 13, No. 1, 2023, 10073-10077 10074 www.etasr.com Leulmi: A Comparative Numerical Study between Minorant Functions and Line Search Methods in …  ' = {� ∈ �� ∶ � � − � ≥ 0}, the set of feasible solutions of (1).  '+ = {� ∈ �� ∶ � � − � > 0} , the set of strictly feasible solutions of (1).  - = {! ∈ �� ∶ ! = �, ! ≥ 0}, the set of feasible solutions of (2).  -+ = {! ∈ �� ∶ ! = �, ! > 0}, the set of strictly feasible solutions of (2). Let ., / ∈ �� . 0heir scalar product is defined by: 〈., /〉 = .� / = ∑ .4 /4�456 We suppose that the sets '+ and -+ are not empty. A. The Perturbed Problem of (1) Problem (1) is approximated by the following perturbed problem: �min� 78 (�)� ∈ �� . (4) where 9 > 0 is the the penalty parameter and 78 is the barrier function defined by: 78 (�) = ��� � + �9 ln9 − 9ln ∑ 〈<4 , � � − �〉�456 if � � − � > 0+∞ if not where (<6, 0, the set '8 (7) = {� ∈ �� ∶ 7(�) ≤ 9} is compact, which comes in particular to say that its cone of recession is reduced to zero. To prove that (4) has an optimal solution, we show that 78 is inf-compact. For that, it is enough to prove that the cone of recession '+ PQ78 RST = UI ∈ �� ∶ Q78 RS(I) ≤ 0V, is reduced to the origin, i.e. PQ78 RS(I) ≤ 0T ⇒ (d = 0), where Q78 RS is defined by: Q78 RS(I) = limK→GS 7Y(� + HI) − 7Y(�)H = �� I. This needs the following proposition: Proposition: I = 0 whenever �� I ≤ 0 and � I ∈ '+. Then, the problem (4) has an optimal solution. We know that the Hessian matrix Z = ∇A7Y(�) is positive definite, then the problem (4) is strictly convex, and if it has an optimal solution, then it is unique. We have: 78 (�) = �� � + �9 ln9 − 9ln \〈<4 , � � − �〉 � 456 Then: ]78 (�) = � − 9 ∑ ^_`〈_`,^a�bc〉�456 and: ]A78 (�) = 9 ∑ ^_`(^_`)a〈_`,^a�bc〉d�456 As 78 is inf-compact and strictly convex, therefore the problem (4) admits a unique optimal solution. We denote by �(9) or �8 the unique optimal solution of (4). C. Convergence of the Perturbed Problem to the Initial Problem For � ∈ '+, let's introduce the symmetrical definite positive matrix e4 of rank �, f = 1, … , � and the lower triangular matrix g, such that e4 = <4 ( <4 )� = gg� , which implies that Z is a positive definite matrix. In what follows, we will be interested in the behavior of the optimal value and the optimal solution �(9) of problem (4). Proposition: For 9 > 0, let �8 an optimal solution of the problem (4) then there is an optimal solution of (1) � ∈ ', such that, lim8→D �8 = �. Remark: We know that if one of the problems (1) and (2) has an optimal solution, and the values of their objective functions are equal and finite, the other problem has an optimal solution. Engineering, Technology & Applied Science Research Vol. 13, No. 1, 2023, 10073-10077 10075 www.etasr.com Leulmi: A Comparative Numerical Study between Minorant Functions and Line Search Methods in … III. RESOLUTION OF THE PERTURBED PROBLEM In this part, we are interested in the numerical solution of problem (4). We use a logarithmic barrier interior point method. This method types are based on the optimality conditions which are necessary and sufficient, and consist of constructing a sequence of iterate �FG6 = �F + HF IF , where �8 is an optimal solution of (4) if it satisfies the following condition: ∇78 Q�8 R = 0 (5) To solve (5) we use the Newton's approach which means to find in each iteration a vector �8F + IF checking the following linear system: ZF IF = −]78 Q�8F R. (6) As ZF = ] A78 Q�8F R is a symmetric positive definite matrix, the Cholesky methods and the conjugate gradient methods are the best convenient for solving (6). To ensure the convergence of the algorithm towards an optimal solution � ∗ of (4), it should be made sure that all the iterations �8F + IF remain strictly feasible. For that, we introduce a step-size HF checking the condition: � Q�8F + HF IF R − � > 0 A. Effectual Computation of the Step Size There are two main techniques used for computing the displacement step HF. 1) Line Search These methods try out a sequence of candidate values of HF, stopping to accept one of these values when some conditions are satisfied. An ideal choice of the step-size is the global minimization of the one-dimensional function J(∙) defined by: J(HF ) = minKLD 7(� + HI) The most used line search methods are Wolfe, Goldstein— Armijo, Fibonacci, etc. Unfortunately, these methods have big computational cost. 2) Principle of Approximate Function A minorant function ij must be close to: i(H) = 68 k78 (� + HI) − 78 (�)l which must give the minK ij (H) in m0, Hno by a simple and easy manner, which permits the computation of the step-size at each iteration in a relatively short time and with a smaller number of instructions in contrast to line search technique. Authors in [12] gave a simple form for the function, which is presented in the following proposition: Proposition [12]: Let Hn = &.p{H: 1 + r4 H} with r4 = 〈_`,^as〉〈_`,^a�bc〉 , ∀f = 1, … , �. For all H ∈ m0, Hno, the following function i(H) is well defined: i(H) = �(∑ r4�456 )H − ‖r‖AH − ∑ ln(1 + r4 H)�456 such that, i(H)verifies the following properties: ‖r‖A = �(r̅A + wxA) = iyy(0) = −iy(0), i(0) = 0 B. Minorant Function Authors in [10] proposed 3 minorant functions in 2019. In this paper, we are interested in their best minorant function defined as: ij6(H) = zH − (� − 1) ln(1 + {H) − ln(1 + |H) with: z = �r̅ − ‖r‖A { = r̅ − }~√�b6| = r̅ + wx √� − 1. In addition, they proved that the minorant function ij6 is defined and convex on m0, Hno, i(H) > ij6(H) ( ij6 minorant function on m0, Hno ), and the function ij6 verifies the following properties: ‖r‖A = �(r̅A + wxA) = ij yy(0) = −ij y(0), ij (0) = 0 The minimum of ij6 is obtained in H�4 = H��� , such that, ij6y(0) = 0. We are then coming back to solve the second order following equation: H A − 2�H + � = 0, with: � = 6A P�� − 6� − 6�T and � = b‖x‖d��� The roots of this equation are of the type H� = � ± √�A − �. Let's take one root of the two that belong to m0, Hnm. Thus, the H� is explicitly computed, then, we consider it belongs to the interval (0, Hn − �) and i′ (H) < 0, with � > 0 being a fixed precision. Remark: The calculation of H� is performed by a dichotomous procedure, in the cases where H�4 ∉ (0, Hn − �), and iy(H) > 0, as follows: Put H = 0 and � = Hn − � while |� − �| > 10b� . If i P�G�A T < 0 , then � = �G�A . Else � = �G�A , so H� = �. This calculation guarantees a better approximation of the minimizer of ij ′ (H) while remaining in the domain of i. Proposition [10]: Let �FG6 and �F be two strictly feasible solutions of (4) obtained respectively at the � + 1 and � iterations, so we have 78 (�FG6) < 78 (�F ). IV. ALGORITHM DESCRIPTION AND NUMERICAL RESULTS In this section, we present the algorithm of our approach to obtain an optimal solution �̅ to problem (1) and some numerical tests. A. The Αlgorithm In this section, we present the algorithm of our approach to obtain an optimal solution �̅ to the problem (1). For simplicity, we consider �F instead of �8F and � instead of �8 . Engineering, Technology & Applied Science Research Vol. 13, No. 1, 2023, 10073-10077 10076 www.etasr.com Leulmi: A Comparative Numerical Study between Minorant Functions and Line Search Methods in … Begin algorithm Initialization �D is a strictly feasible solution of (1), ID ∈ �� and � > 0 is a given precision. Iteration While |�� IF | > � do Solve the system ZF IF = −]78 Q�8F R. Compute the step-size using the strategy of minorant function or line search method. Take the new iterate �FG6 = �F + HF IF . Take � = � + 1. End while End algorithm This approach tries to reduce the number of iterations and the time of calculation. Some examples are presented below. B. Numerical Results To measure the numerical performance of the proposed methods, we present a numerical comparison of the results obtained by the proposed algorithm using the minorant function given in [10] to compute the step-size and those obtained by using the line search Wolfe's method. We use examples with fixed and variable sizes to carry out the numerical tests. The following examples are taken from the literature [1, 4, 8] and were implemented in MATLAB. We took � = 1.0< − 006. In the result table:  (size) represents the size of the example.  (itrat) represents the number of iterations necessary to obtain an optimal solution.  (time) represents the time of computation in seconds (s).  (mf st) represents the strategy that uses minorant function.  (lr st) represents the strategy that uses Wolfe's line search. Recall that the considered problem (1) is: � min� ��� � � ≥ �, � ∈ �� We note that the matrices used in the numerical tests are full matrices. 1) Examples with Fixed Size Example 01: = �2 3 1 23 0 −2 1� , � = �20� and � = m4 1 2 0o�  The initial strictly feasible point is � D = m1 1.5 1 1o� .  The optimal solution is � D = m0 0.67 0 0o� . Example 02: = �2 1 0 −1 0 00 0 1 0 1 −11 1 1 1 1 1 � , � = � 001� and � = m3 −1 1 0 0 0o�  The initial strictly feasible point is � D = m1 1 2o� .  The optimal solution is � ∗ = m0.5 0.0713 0.5o�. Example 03: = �1 −1 1 1 0 01 1 0 0 1 02 2 1 0 0 1� , � = � 624� and � = m4 −2 −2 0 0 0o�  The initial strictly feasible point is � D = m0.5 1 1o� .  The optimal solution is � D = m0 0 0o� . Example 04: , 100000541232 010000221112 001000512010 000100143354 000010310135 000001113401                           A � = m1 4 4 5 7 5o� � = m−4 −5 −1 −3 5 −8 0 0 0 0 0 0o�  The initial strictly feasible point is: � D = m−2 4 1 1 1 1o�  The optimal solution is � ∗ = m0.5 1.5 0 0 1.5 0o� Example 05: �4 = 10�, f = 1, … ,5, � = m1 1 1 1 1 1 1 1 1 1 0 0 0 0 0o�  The initial strictly feasible point is � D = m1 1 1 1 1o�  The optimal solution is � D = m0 0 0.0888 0 0.0078o� The results of the last examples are given in Table I. TABLE I. EXAMPLES WITH FIXED SIZE Size mf st ls st itrat time itrat time 2 × 4 5 0.032 13 0.130 3 × 6 6 0.044 33 0.128 3 × 6 7 0.051 34 0.132 6 × 12 9 0.055 34 0.306 5 × 15 8 0.048 22 0.170 A  1 2 3 4 5 5 4 3 2 1 1 0 0 0 0 6 7 8 9 10 5 2 8 3 1 0 1 0 0 0 11 12 13 14 15 6 7 80 90 10 0 0 1 0 0 1 10 20 30 40 50 60 80 90 10 0 0 0 1 0 3 9 27 60 45 60 75 8 9 46 0 0 0 0 1 = Engineering, Technology & Applied Science Research Vol. 13, No. 1, 2023, 10073-10077 10077 www.etasr.com Leulmi: A Comparative Numerical Study between Minorant Functions and Line Search Methods in … 2) Example with Variable Size � = 2�, For f, � = 1, … , �, mf, �o = 0 if f ≠ � or (f + 1) ≠ � mf, �o = mf, f + �o = 1, �mfo = 2.  The initial strictly feasible point is � D = m1 1 … 1o� .  The optimal solution is � ∗ = m0 0 … 0o� . Table II resumes the obtained results. TABLE II. EXAMPLES WITH FIXED SIZE Size mf st ls st itrat time itrat time 50 × 100 1 0.031 49 8.5512 100 × 200 1 0.053 50 32.6145 200 × 400 2 0.088 51 91.6524 400 × 800 3 0.096 52 161.4374 500 × 1000 3 0.12 52 411.8901 V. CONCLUSION The conducted numerical study clearly shows that the strategy of the minorant function seems to be more efficient than that of the line search in time and number of iterations. Our future work will consider further improving the computational time of the logarithmic barrier algorithm by proposing another, better, approximate function. But the extensions would be envisaged to the nonlinear, and not necessarily relevant to the LO problem. REFERENCES [1] M. Achache, "A polynomial-time weighted path-following interior-point algorithm for linear optimization," Asian-European Journal of Mathematics, vol. 13, no. 2, Mar. 2020, Art. no. 2050038, https://doi.org/10.1142/S1793557120500382. [2] P. Armaos, "A Study of Joint Cost Inclusion in Linear Programming Optimization," Engineering, Technology & Applied Science Research, vol. 3, no. 4, pp. 473–478, Aug. 2013, https://doi.org/10.48084/etasr. 327. [3] B. Badri-Koohi, R. Tavakkoli-Moghaddam, and M. Asghari, "Optimizing Number and Locations of Alternative-Fuel Stations Using a Multi-Criteria Approach," Engineering, Technology & Applied Science Research, vol. 9, no. 1, pp. 3715–3720, Feb. 2019, https://doi.org/ 10.48084/etasr.2474. [4] M. Bouafia, D. Benterki, and A. Yassine, "A new efficient short-step projective interior point method for linear programming," Operations Research Letters, vol. 46, no. 3, pp. 291–294, May 2018, https://doi.org/ 10.1016/j.orl.2018.02.004. [5] J.-P. Crouzeix and B. Merikhi, "A logarithm barrier method for semi- definite programming," RAIRO - Operations Research, vol. 42, no. 2, pp. 123–139, Apr. 2008, https://doi.org/10.1051/ro:2008005. [6] J.-P. Chehab and M. Raydan, "Geometrical properties of the Frobenius condition number for positive definite matrices," Linear Algebra and its Applications, vol. 429, no. 8, pp. 2089–2097, Oct. 2008, https://doi.org/ 10.1016/j.laa.2008.06.006. [7] R. M. Freund and S. Mizuno, "Interior Point Methods: Current Status and Future Directions," in High Performance Optimization, H. Frenk, K. Roos, T. Terlaky, and S. Zhang, Eds. Boston, MA, USA: Springer US, 2000, pp. 441–466, https://doi.org/10.1007/978-1-4757-3216-0_18. [8] N. Karmarkar, "A new polynomial-time algorithm for linear programming," in Proceedings of the sixteenth annual ACM symposium on Theory of computing, New York, NY, USA, Sep. 1984, pp. 302–311, https://doi.org/10.1145/800057.808695. [9] A. Leulmi and S. Leulmi, "Logarithmic Barrier Method Via Minorant Function for Linear Programming | Journal of Siberian Federal University," Journal of Siberian Federal University. Mathematics & Physics, vol. 12, no. 2, pp. 191–201, 2019, https://doi.org/10.17516/ 1997-1397-2019-12-2-191-201. [10] A. Leulmi, B. Merikhi, and D. Benterki, "Study of a Logarithmic Barrier Approach for Linear Semidefinite Programming," Journal of Siberian Federal University. Mathematics & Physics, vol. 11, no. 3, pp. 1–13, 2018, https://doi.org/10.17516/1997-1397-2018-11-3-300-312. [11] N. Karmarkar, "A new polynomial-time algorithm for linear programming," in Proceedings of the sixteenth annual ACM symposium on Theory of computing, New York, NY, USA, Sep. 1984, pp. 302–311, https://doi.org/10.1145/800057.808695. [12] H. Mansouri and M. Zangiabadi, "An adaptive infeasible interior-point algorithm with full-Newton step for linear optimization," Optimization, vol. 62, no. 2, pp. 285–297, Feb. 2013, https://doi.org/10.1080/ 02331934.2011.611881. [13] M. R. Rezoug, M. Benaouadj, D. Taibi, and R. Chenni, "A New Optimization Approach for a Solar Tracker Based on an Inertial Measurement Unit," Engineering, Technology & Applied Science Research, vol. 11, no. 5, pp. 7542–7550, Oct. 2021, https://doi.org/ 10.48084/etasr.4330. [14] H. Wolkowicz and G. P. H. Styan, "Bounds for eigenvalues using traces," Linear Algebra and its Applications, vol. 29, pp. 471–506, Feb. 1980, https://doi.org/10.1016/0024-3795(80)90258-X. [15] J. F. Bonnans, J. C. Gilbert, C. Lemaréchal, and C. A. Sagastizábal, Numerical Optimization: Theoretical and Practical Aspects (Universitext). Berlin, Heidelberg, Germany: Springer-Verlag, 2006. [16] R. T. Rockafellar, Convex Analysis: (PMS-28), vol. 30. Princeton, NJ, USA: Princeton University Press, 1970.