Modelling of Gauss Elimination Technique for Quadratic Optimization

Page:

31-34

DOI:

https://doi.org/10.18280/ama_a.562-401

OPEN ACCESS

Abstract:

Mathematical modelling aims to describe the different aspects of the real world problems, their interaction and their dynamics through mathematics and optimization. The purpose of this paper is to give a brief taxonomy of an important group of non-linear programming problems (specially Quadratic Programming Problem) which occur in certain branches of applied Mathematics. There exists a variety of decision problems in the field of Mathematical Programming in which objective function contains the product of two linear factors, such problems are known as Quadratic Programming Problems. A new technique has been developed to find the solution of Quadratic Programming Problem (QPP) by modelling of Gauss Elimination Technique of inequalities. The method is quite useful because the calculations are simple and takes least time then earlier existing methods. The technique has been illustrated by a numerical example also.

Keywords:

*gauss elimination technique, quadratic programming problem, inequalities, non-linear objective function, constraints *

1. Introduction

Mathematical modelling aims to describe the different aspects of the real world problems, their interaction and their dynamics through Mathematics and Optimization. It constitutes the third pillar of science and engineering, achieving the fulfilment of the traditional disciplines having theoretical analysis and experimentation. Nowadays, mathematical modelling has also a key role in the fields such as the environment and industry, while its potential contribution in many other areas is becoming more and more evident like nature inspired algorithms. One of the reasons for this growing success is definitely due to the impetuous progress of scientific computation; this discipline allows the translation of a mathematical model—which can be explicitly solved only occasionally—into algorithms that can be treated and solved by ever more powerful computers. Since 1960 Numerical Analysis—the discipline that allows mathematical equations to be solved through elimination algorithms—had a leading role in solving problems linked to mathematical modelling derived from engineering and applied sciences.

Decision making is an innovative and interesting field and solving its related problems is still a challenge for researchers. In recent years a number of interesting algorithms have been proposed. Some of these have been computationally tested. Each algorithm / method have some advantages as well as disadvantages. In the context of each application, some algorithm/method seems more appropriate than others. However, the issue of choosing a proper method in a given context is still a subject of active research.

Many researchers have proposed algorithms for solving mathematical programming problem, for example: Charnes et al. [2], Martos [16], Wolf [19] and others. Elimination techniques for linear programming problems are studied by Kohler [15], Williams [18], Kanniappan [14], Bhargava & Sharma [1], Jain & Mangal [6]. After that Jain and his research team developed and extended Gauss and Modified Fourier elimination techniques for fractional programming problem [9-10], Gauss and Modified Fourier elimination techniques for multi-objective programming problem [4-6,12] and Gauss and Modified Fourier elimination techniques for Separable programming problem [3,11].

Quadratic Programming Problem (QPP) is one of the simplest forms of Non-Linear Programming and used to solve the problems of optimizing a quadratic objective function of the form (CX+α)(C’X+β). The objective function of QPP can contain bilinear terms and the constraints are linear and can be both equations and inequations. Quadratic Programming is used widely in Signal and image processing, to perform the Least – squares approximations and estimations, to optimize financial portfolios and to control scheduling etc.

Gauss elimination technique is the most effective and widely used method in the field of Numerical Analysis. In the following section, we describe in brief how Gauss elimination technique is applied on inequalities. In the proposed method, first we convert objective function of product form into separate constraints. Using updated form of Gauss elimination technique to solve these systems of inequalities of QPP and finally to find solution, we use concept of bounds. This has been verified by a numerical example and concluding remarks are given at the end.

2. Gauss Elimination Technique for Inequalities

In Numerical Analysis, the system of simultaneous linear equation is solved by Gauss elimination technique with the help of elimination of variables one by one and finally reduce to upper triangular system of equations, which can be solved by back substitution. Equation gives only one solution while inequality gives possibility of many solutions in bounded / region form, out of which we select maximum or minimum value according to the problem. This is the main theme to apply Gauss elimination technique for inequalities in place of equations. It ca;n easily verify that max. / min. value of linear variables gives, max. / min. value of objective function of $\sum C_{i} X_{i}$ form where all *C*_{i} are positive. If some *C*_{i} are not positive, then we take mini. /max. value of corresponding linear variables so it gives max. / min. value of objective function.

Here we apply Gauss elimination technique for a system of inequalities of the same sign i.e., either less than equal to ( __<__ ) or greater than equal to ( __>__ ) in nature. Here variables are eliminated by combining inequalities in such a way that the inequalities and variables reduced one by one in every iteration i.e., one variable and one inequality reduced in one iteration so at last there remains only one inequality with one variable remains. This last inequality gives value of last variable in bounded form and finally taking the value of last variable maximum or minimum according to objective function of QPP. Finally, we get value of other variables by back substitution of value of the last variable.

For the sake of clarity and simplicity we consider the system of inequalities of n variable and m inequalities:

$a_{11} x_{1}+\ldots+a_{1 n} x_{n} \leq b_{1}$

$a_{21} x_{1}+\ldots+a_{2 n} x_{n} \leq b_{2}$

………………

………………

$a_{m 1} x_{1}+\ldots+a_{m n} x_{n} \leq b_{m}$

First of all to eliminate the first variable say multiply the first row by $a_{21} / a_{11},{a_{31}} / a_{11}, \cdots,{a_{m 1}} / a_{11}$ respectively and then subtract them from second, third and so on up to the m^{th} row respectively. In this stage, we have assumed that a_{11} ≠ 0. The first equation is called pivotal equation and a_{11} ≠ 0 is called the first pivot.

Then we get first iteration, which is

$a_{22}^{(2)} x_{2}+\cdots+a_{2 n}^{(2)} x_{n} \leq b_{2}^{(2)}$

$a_{32}^{(2)} x_{2}+\dots+a_{3 n}^{(2)} x_{n} \leq b_{3}^{(2)}$

……………………

……………………

$a_{m 2}^{(2)} x_{2}+\cdots+a_{m n}^{(2)} x_{n} \leq b_{m}^{(2)}$

where,

$a_{m n}^{(2)}=a_{m n}-^{a_{m 1} a_{1 n}} / a_{11}$

And

$b_{k}^{(2)}=b_{k}-b_{1}^{a_{k 1}} / a_{11}$

Now after first iteration, we get *(n-1)* variable and *(m-1)* inequalities. Repeating this process or after *(n-1)* iterations we have only one variable remains. Finally, we get value of other variables by back substitution of the value of last variable. There may be some redundant constraints present in the system.

3. Problem Formulation for Gauss Elimination Algorithm

Here we consider the Quadratic programming problem which can be written as the product of two linear functions:

$\begin{align} & Max\,Z=\,\left( {{a}_{1}}x\,+\,{{\alpha }_{1}} \right)\times \left( {{a}_{2}}x\,+\,{{\alpha }_{2}} \right) \\ & Subject\,\,to,\,\,A\,x\,\le \,b \\ & and\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,x\,\ge \,0 \\ \end{align}$ (1)

where it is assumed that $\left(a_{1} x+a_{1}\right),\left(a_{2} x+a_{2}\right)$ are positive for all feasible solutions and set of feasible solutions is bounded closed convex polyhedron.

To apply Gauss elimination technique, we formulate this QPP by taking objective function as constraints and all constraints of the same sign of inequality. So reduced form of QPP for Gauss elimination technique is as follows:

$\begin{align} & Max\,Z=\,\left( {{a}_{1}}x\,+\,{{\alpha }_{1}} \right)\times \left( {{a}_{2}}x\,+\,{{\alpha }_{2}} \right)=\,Max\,{{z}_{1}}\,.\,Max\,{{z}_{2}} \\ & \,\left( {{a}_{1}}x\,+\,{{\alpha }_{1}} \right)\,-\,{{z}_{1}}\le \,0 \\ & \,\left( {{a}_{2}}x\,+\,{{\alpha }_{2}} \right)\,-\,{{z}_{2}}\le \,0 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,A\,x\,\le \,b \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-x\,\le \,0 \\ \end{align}$ (2)

Now combining inequalities in such a way such that the inequalities and variables are reduced one by one in each iteration eliminates the variables. If at any stage we get an absurd inequality like 0 __<__ d where d is a negative number then we conclude that the given QPP has infeasible solution otherwise QPP has feasible solution.

To explain the whole procedure, we consider a numerical example of QPP in the next section.

4. Numerical Example

Consider the following Quadratic Programming Problem:

Maximize

z = (2*x*_{1}+3*x*_{2}+2) (*x*_{2}-5)

Subject to

*x*_{1}+*x*_{2} ≤1

4*x*_{1}+*x*_{2} ≥2

and

*x*_{1}, *x*_{2} ≥ 0

Here, we assume both the linear functions involved in objective function as a constraint, say z_{1} and z_{2}.

Making standard form by treating objective function as constraints and all the inequalities of same sign for Gauss Elimination Technique, we have

Max z = z_{1}z_{2}

2*x*_{1}+3*x*_{2 }-z_{1} ≤ -2 (3)

0*x*_{1}+*x*_{2}- z_{2 } ≤ 5 (4)

*x*_{1}+*x*_{2} ≤ 1 (5)

-4*x*_{1}-*x*_{2} ≤ -2 (6)

-*x*_{1} ≤ 0 (7)

-*x*_{2} ≤ 0 (8)

After first stage of elimination, we have

Max z = z_{1}z_{2}

*x*_{2} – z_{2} ≤ 5 (9)

-*x*_{2} + z_{1} ≤ 4 (10)

5 *x*_{2} – 2z_{1} ≤ -6 (11)

3*x*_{2} – z_{1} ≤ -2 (12)

-*x*_{2}≤ 0 (13)

After second stage of elimination, we have

-2z_{1} + 5z_{2} ≤ -31 (14)

-z_{1} + 3z_{2} ≤ 29 (15)

z_{2} ≥ -5 (16)

z_{1} ≥ 3 (17)

We have some values of z_{1} and z_{2 }but our object is to maximize z_{1} and z_{2}.

Values of z_{1} and z_{2} from the above inequalities, we have

z_{1} = 3 and z_{2} = -5

Now putting z_{1} = 3 and z_{2} = -5 in the inequalities (4.7) to (4.11), we get different bounded values for variable *x*_{2}. Out of this, *x*_{2} = 0 is the only value that satisfies all the inequalities (4.7) to (4.11) simultaneously. Therefore *x*_{2} = 0.

Now putting z_{1} = 3, z_{2} = -5 and *x*_{2}=0 in the inequalities (4.1) to (4.6), we get different bounded values for variable *x*_{1. }Out of this *x*_{1} = ½ is the only value that satisfies all the inequalities (4.1) to (4.6) simultaneously. Therefore *x*_{1} = ½ .

Hence, the solution of above Quadratic programming Problem is as follows :

*x*_{1} = ½ , *x*_{2} = 0, z_{1} = 3, z_{2} = -5 and z = -15.

5. Discussion

The method discussed in this paper provides an interactive approach in which the decision maker can search for an acceptable solution of the quadratic optimization problem. If one linear factor becomes one for some values of *a*_{i} and *α*_{i }then proposed QPP gets reduced to Linear Programming Problem which had been studied earlier by Bhargava, S. and Sharma, K.C. The proposed method to solve Quadratic Programming Problem is much better than many existing methods because in this method the concept of bound is used at each iteration. The existing methods to solve Quadratic Programming Problems are much calculative as compared to this method. The proposed method is based upon the solution of inequalities while more calculations are required to solve Quadratic Programming Problem by simplex method or by any existing method.

6. Conclusion

The proposed method in this paper indicates that the final result converges quickly as compared to other existing methods. This method does not depend on the simplex type method which searches along the boundary from one feasible vertex to an adjacent vertex until an optimal solution is reached. In some certain problems, the number of vertices is quite large, hence the simplex method would be prohibitively expensive in computer time.

References

[1] Bhargava, S., Sharma, K.C. (2002). Extended Modified Fourier Method to Solve Integer Programming Problem. Pure and Applied Mathematika Sciences LVI, 56(1/2): 31-37.

[2] Charnes, A., Cooper, W.W. (1962). Programming with Linear Fractional Functionals. Naval Research Log. Quart, 9: 181-186. https://doi.org/10.1002/nav.3800090303

[3] Jain, S. (2012). Modeling of Gauss elimination technique for multi-objective linear programming problem. J Nov App Sci, 1(1): 25-29.

[4] Jain, S. (2012). Modeling of Gauss elimination technique for Separable Non-linear programming problem. Int. J. industrial Mathematics, 4(3): 163-170.

[5] Jain, S. (2014). Modeling of Gauss elimination technique for Multiobjective fractional programming problem. South Asian Journal of Mathematics, 4(3): 148-153.

[6] Jain, S., Arya, N. (2013). On inverse quadratic programming problem. Journal of Association for the Advancement of Modeling & Simulation Techniques in Enterprises, Series-A, 50(2): 55-71.

[7] Jain, S., Mangal, A. (2008). Extended Gauss Elimination Technique For Integer Solution of Linear Fractional Programming. Journal of the Indian Mathematical Society, 75(1-4): 37-46.

[8] Jain, S., Mangal, A. (2008). Extended Modified Fourier Elimination Technique For Integer Solution of Fractional Programming Problem. Varahmihir Journal of Mathematical Sciences, 8(1): 179-186.

[9] Jain, S., Mangal, A. (2008). Gauss Elimination Technique For Fractional Programming Problem. J. Indian Soc. Stat. Opers. Res, 29(1-4): 35-40.

[10] Jain, S., Mangal, A. (2004). Modified Fourier Elimination Technique For Fractional Programming Problem. Acharya Nagarjuna International Journal of Mathematics & Information Technology, 1(2): 121-131.

[11] Jain, S., Singh, K. (2018). Modeling of Modified Fourier Technique for Solving Separable Non-Linear Programming Problem. Advanced Modeling and Optimization, 20(1): 265-270.

[12] Jain, S. (2009). Modeling of Fourier elimination technique for multiobjective linear programming problem. Journal of Association for the Advancement of Modeling & Simulation Techniques in Enterprises, Series-A, 46(2): 70-78.

[13] Jain, S. (2013). Modeling of Fourier Elimination Technique for Multiobjective Fractional Programming Problem. Int J of Development Res. & Quantitative Techniques, 03: 30-36.

[14] Kanniappan, P., Thangvel, K. (1998). Modified Fourier’s Method of Solving LPP. OPSEARCH, 35: 45-56.

[15] Kohler, D.A. (1973). Translation of a report by J. B. Fourier on his work on linear inequalities (Oeuvres de Fourier, Tome II, pp. 325–328, Gauthier-Villars, Paris, 1890). Opsearch 10 (1973), 1: 38–42.

[16] Martos, B. (1975). Nonlinear Programming : Theory and Methods. North- Holland Publishing Company, Amsterdam. https://doi.org/10.1057/jors.1977.183

[17] Sharma, K.C., Bhargava, S. (2003). Gauss Method to Solve Linear Programming Problem. Applied Science Periodical, 5(1): 45-49.

[18] Williams, H.P. (1986). Fourier’s Method of Linear Programming and its Dual. American Mathematical Monthly, 93: 681-695. https://doi.org/10.2307/2322281

[19] Wolf, H. (1985). A parametric method for solving the linear fractional programming problems. Operations Research, 33: 835-841.