Printer Friendly

Solution of Quadratic Programming with Interval Variables Using a Two-Level Programming Approach.

1. Introduction

Classic quadratic programming requires the assumption that the coefficient value is certainly known. But in the real world, coefficient values often cannot be certainly determined. The uncertain coefficient value can be estimated using intervals based on the theory of interval analysis which is developed by Moore [1]. It is also called interval quadratic programming. The special characteristic of the interval quadratic programming is the coefficients and variables of the objective functions and constraints are in interval form. Classical quadratic programming which is developed by transforming the coefficients in objective functions and constraints into interval form is called quadratic programming with interval coefficients. If the coefficients and variables in the objective function and constraints are both of interval form, it is called quadratic programming with interval variables.

Researches on quadratic programming with interval coefficients have been discussed by Liu and Wang [2], Li and Tiang [3], and Syaripuddin et al. [4]. All of the researches were inspired by linear programming with the interval coefficients which have been discussed earlier by Shaocheng [5], Chinneck and Ramadan [6], and Kuchta [7]. The research on quadratic programming with interval variables was inspired by linear programming with interval variables which have been discussed by Suprajitno and Mohd [8]. Research on quadratic programming with interval coefficients has also been extended to the nonlinear interval programming which is discussed by Jiang et al. [9], Wu [10,11], and Bhurjee and Panda [12].

Two-level programming is a mathematical procedure which used to transform the interval programming model into a pair of classic programming models with special characteristics, namely, the best optimum and the worst optimum problems. Reference [6] used two-level programming on the solving of linear programming with the interval coefficients, whereas [2, 3] used two-level programming on the solving of quadratic programming with interval coefficients. References [2, 3, 6] were able to construct the interval solution at the optimum value only, which was done by combining the optimum value from the best optimum with the worst optimum problem so the interval form was obtained. Nevertheless, the optimum point cannot be constructed in interval form. Reference [8] presented procedures to obtain optimum solution in interval form for both optimum point and optimum value. Reference [8] defined the coefficients and variables in the linear programming in the interval form and constructed a solution by using a two-level programming approach with some additional procedures for obtaining an interval solution. Reference [9] suggested a method to solve nonlinear interval programming by transforming the uncertain objective functions and constraints into two deterministic objective functions and constraints. Two deterministic objective functions and constraints are formulated into an optimization problem with a single objective function through a linear combination method and the penalty function method. Based on the solving nonlinear interval programming method and the interval analysis method, Jiang et al. [13] suggested a method to solve uncertain structural programming meanwhile Zhang et al. [14] suggested a method to solve uncertainty modelling and time-dependent reliability analysis for time-dependent structures.

This paper discusses the solution of quadratic programming with interval variables using a two-level programming approach that focuses on howto obtain the optimum solution in interval form, for both optimum point and optimum value. There are three steps to obtain an optimum solution in the interval form. First step is defining the coefficients and variables on interval quadratic programming model as interval form. The second step is transforming a quadratic programming with interval variables model into a pair of classical quadratic programming models. The last step is constructing the procedure of interval solution in the classic quadratic programming model by adding new constraints to the model which has unbounded solution in order to restrict the feasible area. The aim of adding new constraints is to determine whether the model has unbounded solution or bounded solution.

This paper is constructed by seven sections. Section 2 discusses interval arithmetic operations. Section 3 presents the general form of quadratic programming with interval coefficients. Section 4 presents the general form of quadratic programming with interval variables. Section 5 discusses the procedure to transform a quadratic programming model with interval variables into a pair of classical quadratic programming models and also presents the interval solution algorithm of the classical quadratic programming model. Section 6 discusses an example to illustrate how to apply concepts to solved quadratic programming with interval variables and Section 7 presents some conclusions.

2. Interval Arithmetic

The basic definition and properties of interval number and interval arithmetic can be seen at Moore [1], Alefeld and Herzberg [15], and Hansen [16].

Definition 1. A closed real interval [x.bar] = [[x.sub.1], [x.sub.S]], denoted by x, is a real interval number which can be defined completely by

[mathematical expression not reproducible] (1)

where [x.sub.1] and [x.sub.s] are called infimum and supremum, respectively.

Definition 2. A real interval number [x.bar] = [[x.sub.1], [x.sub.S]] is called degenerate, if [X.sub.I] = [x.sub.s].

Definition 3. If [x.bar] = [[x.sub.1], [x.sub.2]] and [x.bar] = [[y.sub.1], [y.sub.2]], the following rules are valid.

(1) [x.bar] + [y.bar] = [[x.sub.I] + [y.sub.I], [x.sub.s] + [y.sub.s]] (addition).

(2) [mathematical expression not reproducible]

(3) [mathematical expression not reproducible]

(4) [mathematical expression not reproducible] (division).

Definition 4. Given two intervals [x.bar] = [[x.sub.1], [x.sub.2]] and [y.bar] = [[y.sub.1], [y.sub.2]], the value m([x.bar]) = ([x.sub.1] + [x.sub.S])/2 is mid-point and w([x.bar]) = ([x.sub.S] - [x.sub.I])/2 is half-width.

Some ideas of comparison of two intervals can be seen in Alefeld and Herzberger [15], Chanas and Kuctha [17], Klatte et al. [18], Sengupta et al. [19], and Kuctha [7]. Here we will only propose one approach, discussed in Maleki et al. [20] as follows.

Definition 5. Given two intervals [x.bar] = [[x.sub.1], [x.sub.2]] and [y.bar] = [[y.sub.1], [y.sub.2]], then [x.bar] if and only if [x.bar] + [x.sub.s] < [y.sup.I] + [y.sup.s].

In order to make the validity of Definition 5, the statement [x.bar] [less than or equal to] [y.bar] if and only if [x.sub.I] + [x.sup.S] [less than or equal to] [y.sup.I] + [y.subs] is valid when one of the following conditions are satisfied.

(i) [x.sub.S] [less than or equal to] [y.sup.I]

(ii) [x.sup.I] [less than or equal to] [y.sup.I] < [[less than or equal to] [x.sub.S] [less than or equal to] [y.sup.S].

3. Quadratic Programming with Interval Coefficient

The general form of linear programming with interval coefficients is defined as follows:

Maximize [z.bar]

[mathematical expression not reproducible] (2.a)

[mathematical expression not reproducible] (2.b)

[x.sub.j] [greater than or equal to] 0, j = 1,2..., n (2c)

with [mathematical expression not reproducible] is negative semidefinite, and I(R) are the set of all interval numbers in R.

The models of (2a)-(2c) were introduced by [3]. The special characteristic of this model is that any coefficient of the objective function and constraints are interval. Reference [3] used two-level programming approach to solve quadratic programming by using the interval coefficients. So we define solution of (2a)-(2c) as follows. The optimal solution in the form of intervals on the solution of the quadratic programming with interval coefficient can only be constructed at the optimum value only, while the optimum point cannot be constructed in the form of intervals.

4. Quadratic Programming with Interval Variable

The general form of linear programming with interval variables is defined as follows:

[mathematical expression not reproducible] (3.a)

[mathematical expression not reproducible] (3.b)

[mathematical expression not reproducible] (3.c)

with [mathematical expression not reproducible] are the set of all interval numbers in R, and [mathematical expression not reproducible] is negative semidefinite.

Constraint [[x.sub.jI], [X.sub.jS]] [greater than or equal to] 0, j = 1,2...,n, in (3c) is called a nonnegative constraint. The properties of the interval multiplication associated with the nonnegative constraint are discussed as follows:

(1) Let [c.bar] = [[c.sub.I], [c.sub.s]] be interval coefficient and let [x.sub.j] =[[x.sub.jI], [X.sub.jS]], [x.sub.I] > 0, be positive interval variable ([x.sub.I] > 0), then there are three possible equations that relate to the value of the coefficient:

(i) if cI > 0, then [mathematical expression not reproducible]

(ii) if [c.sub.S] < 0, then [mathematical expression not reproducible]

(iii) if [mathematical expression not reproducible]

Thus, if [x.sub.I] > 0, then

[mathematical expression not reproducible] (4)

(2) Let [q.bar] = [[q.sub.I], [q.sub.s]] be interval coefficient and let [mathematical expression not reproducible] be two positive interval variables, then there are three possible equations that relate to the coefficient value:

[mathematical expression not reproducible]

In (3a)-(3c), the coefficients and variables of the objective function and constraints in the quadratic programming model are defined as interval form. This model is developed from the models in (2a)-(2c). Quadratic programming model with interval variables is defined to obtain the optimum solution in the interval form, for both optimum value and optimum point. The problems described in (3a)-(3c) are solved by using a two-level programming approach with respect to the properties of the interval multiplication of nonnegative constraints.

The following definition is used to determine the optimal interval solution. The idea of definition is derived from Maleki et al. [20].

Definition 6. Any set of [[x.bar].sub.] which satisfies the set of constraints (3b) is called a feasible solution for the problem in (3a)-(3c). Let Q be the set of all feasible solutions of the problem. We shall say that [[bar.x].sup.*] [member of] Q is an optimal point solution if z([[x.bar].sup.*]) [greater than or equal to] z([x.bar]) for all [x.bar] e=[member of] Q, and z([[x.bar].sup.*]) is an optimal value solution for the problem.

5. Two-Level Programming

Two-level programming is a mathematical procedure which is used to transform a two-level interval programming model into a pair of one-level classic programming model. In this section, we will discuss the theorem which will be used to transform the quadratic programming model with interval variables into a pair of classical quadratic programming models.

In quadratic programming for maximizing with interval variables, the best optimum problem has properties as the best version of the objective function and the maximum feasible area on the constraint function, whereas the worst optimum problem has properties as the worst version of the objective function and the minimum feasible area on the constraint function. The discussion of how to obtain the maximum and minimum feasible area on the constraints of quadratic programming with interval variables which contains inequality less than or equal to ([less than or equal to]) can be seen in the following theorem.

Theorem 7. If interval inequality of the constraints [mathematical expression not reproducible] is the maximum feasible area and [[summation.sup.n.sub.j=1] max([a.sub.jS][x.sub.Ji], [a.sub.Js][x.suub.Js]) [less than or equal to] [b.sub.I] is the minimum feasible area.

Proof. Let [[summation.sup.n.sub.j=1] [a.sub.j][x.sub.j] [less than or equal to] b] be any inequality of the interval inequality [mathematical expression not reproducible]. Based on (4), for any particular solution [x.sub.j] [greater than or equal to] 0, [x.sub.j] [member of] [[x.sub.jL], [x.sub.Js], we have

[mathematical expression not reproducible] (6)

Therefore if [[summation].sup.n.sub.j=1] max([a.sub.jS][x.sub.Ji], [a.sub.jS][x.sub.j]S) [less than or equal to] [b.sub.I] at an interval vector [mathematical expression not reproducible], then we have

[mathematical expression not reproducible] (7)

So [x.bar] must satisfy all possible versions of the interval inequalities simultaneously. Thus,

[n.summation over (j=1)] max ([a.sub.jS] [x.sub.jI],[a.sub.jS] [x.sub.js]) (8)

< [b.sub.I] is the minimum feasible area.

Furthermore, based on (4), for any particular solution [x.sub.j] > 0, [x.sub.j] [member of] [[x.sub.jI], [x.sub.jS], we also have

[mathematical expression not reproducible] (9)

Therefore, any particular solution which satisfies interval inequality will also satisfy

[n.summation over (j=1)] ([a.sub.jl][x.sub.jI], [a.sub.jI][x.sub.jS]) [less than or equal to] [b.sub.S] (10)

Thus,

[mathematical expression not reproducible] (11)

[less than or equal to] [b.sub.s] is the maximum feasible area.

A discussion of how to get the best and worst version of the objectives function at the quadratic programming with interval variables can be seen in the following theorem.

Theorem 8. [mathematical expression not reproducible] is the objective function with

[[mathematical expression not reproducible]

Proof. We have [mathematical expression not reproducible]. Based on (4) and (5), we get

[mathematical expression not reproducible] (12)

[mathematical expression not reproducible] (13)

Clearly we obtain the following expression:

[mathematical expression not reproducible] (14)

Based on Theorems 7 and 8, we obtain a pair of onelevel classical quadratic programming model with special characteristics, as follows.

(a) The best optimum:

[mathematical expression not reproducible] (15a)

[mathematical expression not reproducible] (15b)

[mathematical expression not reproducible] (15c)

(b) The worst optimum:

[mathematical expression not reproducible] (16a)

[mathematical expression not reproducible] (16b)

[mathematical expression not reproducible] (16c)

The optimum solution in the form of intervals is obtained by constructing the interval solution procedure in the classical quadratic programming model. If there is an unbounded solution in one of the classic quadratic programming models or in both models, then we add a new constraint to its pair model in order to restrict the feasible region. The purpose of this procedure is to ascertain whether a solution is unbounded or bounded. The interval solutions procedure is discussed in the following algorithm.

Algorithm 9.

Step 1. Transform quadratic programming with interval variables model into a classical quadratic programming model.

(a) Determine the maximum and minimum feasible area in the constraint function

(b) Determine the best and the worst version of the objective function

(c) Construct two classical quadratic programming models from (a) and (b)

Model-1: The best optimum problem

Objective function: the best version of the objective function

Constraint: the maximum feasible area

Model-2: The worst optimum problem

Objective function: the worst version of the objective function

Constraint: the minimum feasible region

Step 2. Determine the solution for Model-1 and Model-2.

Step 3. Check the solution.

(a) If Model-1 and Model-2 have no feasible region, then stop. The models have no solution

(b) If Model-1 and Model-2 are unbounded, a solution has been reached, continue to Step 4. If they are finite, then choose a model that has an unbounded solution. Next, replace the constraint with the new constraint from the combination of the constraints of Model-1 and Model-2, so we have the new model

Step 4. Create an interval solution.

The optimum solution of quadratic programming with the interval variables is obtained by creating the interval solution as follows.

(a) Set the supremum value from interval solution of the best optimum problem

(b) Set the infimum value from interval solution of the worst optimum problem

If the solution is an interval form, then stop. If it is not an interval form, then give the infimum value to the noninterval solution so that we have interval degenerate.

6. Numerical Example

Consider the following example of quadratic programming with interval coefficients in [3].

[mathematical expression not reproducible] (17a)

[mathematical expression not reproducible] (17b)

[mathematical expression not reproducible] (17c)

[mathematical expression not reproducible] (17d)

According to [3], the optimum value solution of the model on (17a)-(17d) is [bar.z] = [[z.sub.I],[z.sub.s] = [-6.25,-0.9] with the best optimum problem being [z.sub.S] = -0.9, [x.sub.1] = 0.3, [x.sub.2] = 0 and the worst optimum problem being [z.sub.I] = -6.25, [x.sub.1] = 1,25, [x.sub.2] = 0. Furthermore, [12] solves (17a)-(17c) by introducing a new approach. In this approach, the interval programming model is defined into a programming model of parameter function. It was obtained that the optimum point is [[x.bar].sub.1] = 0.5, [[x.bar].sub.2] = 0 and optimum value is [z.bar] = [-4, -0.5].

In this paper, the quadratic programming model with interval variables is only defined for maximization problem, so any minimization problem will be converted into maximization problem. The simple procedure to convert a minimization problem into maximization problem is by multiplying the objective function of the minimization problem by -1, and vice versa.

The model in (17a)-(17d) is assumed to be a quadratic programming with interval variables and converted to maximization problems as presented as follows.

[mathematical expression not reproducible] (18a)

[mathematical expression not reproducible] (18b)

[mathematical expression not reproducible] (18c)

[mathematical expression not reproducible] (18d)

Based on Algorithm 9, we find the solution of (18a)-(18d) as follows.

Step 1. Create two classical quadratic programming models, namely, the best and worst optimum problem.

The Best Optimum Problem

Model-1

[mathematical expression not reproducible] (19)

The Worst Optimum Problem

Model-2

[mathematical expression not reproducible] (20)

Step 2. The solution of Model-1 and Model-2 is as follows.

In this case, it is found that Model-1 has an unbounded solution and Model-2 has a finite solution.

Step 3. Create a new model on the model that has an unbounded solution.

The Best Optimum Problem

New Model-1

[mathematical expression not reproducible] (21)

The Worst Optimum Proble

Model-2

[mathematical expression not reproducible] (22)

Solution of the new Model-1 [mathematical expression not reproducible] .

Step 4. The interval solution is obtained by setting the supremum and infimum values of the previous solution, which are

(i) [x.sub.1s] = 0.5, [x.sub.2S] = 0,

(ii) [x.sub.1I] = 0.3, [x.sub.2I] = 0.

From (i) and (ii) we get the solution of quadratic programming with interval variables as follows:

(i) The optimum points are [[x.bar].sub.1] = [0.3,0.5] and [[x.bar].sub.2] = [0,0] which satisfy Definition 5.

(ii) The optimum value is [z.bar] = [-0.7,4.67] or equivalent to -[z.bar] = [-4.64,0.7] on minimized problem.

The optimum point and optimum value are covering the solution in [12] while optimum value is an intersection solution in [3].

7. Conclusion

This paper presents a two-level programming approach for solving quadratic programming with interval variables. The two-level programming procedure is transforming the quadratic programming model with interval variables into a pair of classical quadratic programming models. Interval solution procedure on a pair of classical quadratic programming models is presented by using Algorithm 9. The definition of coefficients and interval variables in the quadratic programming model has a particular benefit, so its optimum solution is in the interval form for both the optimum point and the optimum value.

Data Availability

No data were used to support this study.

https://doi.org/10.1155/2018/5204375

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

The first author would like to thank the Indonesian Ministry of Research, Technology and Higher Education for providing a financial scholarship and research.

References

[1] R. E. Moore, Interval Analysis, Prentice-Hall, Englewood Cliffs, NJ, USA, 1966.

[2] S.-T. Liu and R.-T. Wang, "A numerical solution method to interval quadratic programming," Applied Mathematics and Computation, vol. 189, no. 2, pp. 1274-1281, 2007

[3] W. Li and X. Tian, "Numerical solution method for general interval quadratic programming," Applied Mathematics and Computation, vol. 202, no. 2, pp. 589-595, 2008.

[4] Syaripuddin, H. Suprajitno, and Fatmawati, "Extension of Wolfe method for solving quadratic programming with interval coefficients," Journal of Applied Mathematics, vol. 2017, Article ID 9037857, 6 pages, 2017.

[5] S. C. Tong, "Interval number and fuzzy number linear programmings," Fuzzy Sets and Systems, vol. 66, no. 3, pp. 301-306,1994.

[6] J. W. Chinneck and K. Ramadan, "Linear programming with interval coefficients," Journal of the Operational Research Society, vol. 51, no. 2, pp. 209-220, 2000.

[7] D. Kuchta, "A modification of a solution concept of the linear programming problem with interval coefficients in the constraints," Central European Journal of Operations Research, vol. 16, no. 3, pp. 307-316, 2008.

[8] H. Suprajitno and I. B. Mohd, "Interval linear programming," in Proceedings of the ICOMS-3, Bogor, Indonesia, 2008.

[9] C. Jiang, X. Han, G. R. Liu, and G. P. Liu, "A nonlinear interval number programming method for uncertain optimization problems," European Journal of Operational Research, vol. 188, no. 1, pp. 1-13, 2008.

[10] H.-C. Wu, "The Karush-KUHn-Tucker optimality conditions in an optimization problem with interval-valued objective function," European Journal of Operational Research, vol. 176, no. 1, pp. 46-59, 2007.

[11] H.-C. Wu, "On interval-valued nonlinear programming problems," Journal of Mathematical Analysis and Applications, vol. 338, no. 1, pp. 299-316, 2008.

[12] A. K. Bhurjee and G. Panda, "Efficient solution of interval optimization problem," Mathematical Methods of Operations Research, vol. 76, no. 3, pp. 273-288, 2012.

[13] C. Jiang, X. Han, F. J. Guan, and Y. H. Li, "An uncertain structural optimization method based on nonlinear interval number programming and interval analysis method," Engineering Structures, vol. 29, no. 11, pp. 3168-3177, 2007

[14] D. Q. Zhang, X. Han, C. Jiang, and X. Y. Long, "The interval PHI2 analysis method for time-dependent reliability, Scientia Sinica Pysica," Scientia Sinica Pysica, Mechanica & Astronomia, vol. 45, no. 5, 2015.

[15] G. Alefeld and J. Herzberger, Introduction to Interval Computations, Academic Press, New York, NY, USA, 1983.

[16] E. Hansen, Global Optimization Using Interval Analysis,vol. 165, Marcel Dekker, Inc., New York, 1992.

[17] S. Chanas and D. Kuchta, "Multiobjective programming in optimization of interval objective functions: a generalized approach," European Journal of Operational Research, vol. 94, no. 3, pp. 594-598, 1996.

[18] R. Klatte, U. Kulisch, M. Neaga, D. Ratz, and Ullrich, Pascal-XSC Laguange Reference with Examples, Springer-Verlag, Berlin, Germany, 1999.

[19] A. Sengupta, T. K. Pal, and D. Chakraborty, "Interpretation of inequality constraints involving interval coefficients and a solution to interval linear programming," Fuzzy Sets and Systems, vol. 119, no. 1, pp. 129-138, 2001.

[20] H. R. Maleki, M. Tata, and M. Mashinchi, "Linear programming with fuzzy variables," Fuzzy Sets and Systems, vol. 109, no. 1, pp. 21-33, 2000.

Syaripuddin [ID], (1) Herry Suprajitno [ID], (2) and Fatmawati [ID] (2)

(1) Department of Mathematics, Faculty of Mathematics and Natural Science, Mulawarman University, Kampus Gunung Kelua, Jl. Borong Tongkok, Samarinda 1068, Indonesia

(2) Department of Mathematics, Faculty of Science and Technology, Airlangga University, Kampus C Unair, Jl. Mulyorejo, Surabaya 60115, Indonesia

Correspondence should be addressed to Herry Suprajitno; herry-s@fst.unair.ac.id

Received 31 January 2018; Revised 30 April 2018; Accepted 20 May 2018; Published 30 July 2018

Academic Editor: Wei-Chiang Hong
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Syaripuddin; Suprajitno, Herry; Fatmawati
Publication:Journal of Applied Mathematics
Article Type:Report
Date:Jan 1, 2018
Words:3839
Previous Article:Modeling the Effects of Spatial Heterogeneity and Seasonality on Guinea Worm Disease Transmission.
Next Article:Some Properties of the Strong Primitivity of Nonnegative Tensors.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters