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

Authors: Syaripuddin; Herry Suprajitno; Fatmawati
Journal: Journal of Applied Mathematics
 (2018)

---

## Abstract

Quadratic programming with interval variables is developed from quadratic programming with interval coefficients to obtain optimum solution in interval form, both the optimum point and optimum value. In this paper, a two-level programming approach is used to solve quadratic programming with interval variables. Procedure of two-level programming is transforming the quadratic programming model with interval variables into a pair of classical quadratic programming models, namely, the best optimum and worst optimum problems. The procedure to solve the best and worst optimum problems is also constructed to obtain optimum solution in interval form.


---

## Body

## 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 how to 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. Section2 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 intervalx_=[xI,xS], denoted by x_, is a real interval number which can be defined completely by (1)x_=xI,xS=x∈R∣xI≤x≤xS;xI,xS∈Rwhere xI and xS are called infimum and supremum, respectively.Definition 2.
A real interval numberx_=[xI,xS] is called degenerate, if xI=xS.Definition 3.
Ifx_=[xI,xS] and y_=[yI,yS], the following rules are valid. (1)
x_+y_=[xI+yI,xS+yS] (addition).(2)
x_-y_=[xI,xS]-[yI,yS]=[xI,xS]+[-yS,-yI]=[xI-yS,xS-yI] (subtraction).(3)
x_·y_=[minxIyI,xIyS,xSyI,xSyS, maxxIyI,xIyS,xSyI,xSyS] (multiplication).(4)
x_/y_=x_1/y_=[xI,xS][1/yS,1/yI], 0∉y_ (division).Definition 4.
Given two intervalsx_=[xI,xS] and y_=[yI,yS], the value m(x_)=xI+xS/2 is mid-point and w(x_)=xS-xI/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 intervalsx_=[xI,xS] and y_=[yI,yS], then x_≤y_ if and only if xI+xS≤yI+yS.In order to make the validity of Definition5, the statement x_≤y_ if and only if xI+xS≤yI+yS is valid when one of the following conditions are satisfied.(i)
xS≤yI.(ii)
xI≤yI≤xS≤yS.


## 3. Quadratic Programming with Interval Coefficient

The general form of linear programming with interval coefficients is defined as follows:(2a)Maximizez_=∑j=1ncjI,cjSxj+12∑j=1n∑k=1nqjkI,qjkSxjxk(2b)subjectto∑j=1naijI,aijSxj≤biI,biS,i=1,2,…,m(2c)xj≥0,j=1,2…,nwith xj∈R, [cjI,cjS],[qijI,qijS], [biI,biS], [aijI,aijS]∈I(R), ∑j=1n∑k=1n[qjkI,qjkS]xjxk 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:(3a)Maximizez_=∑j=1ncjI,cjSxjI,xjS+12∑j=1n∑k=1nqjkI,qjkSxjI,xjSxkI,xkS(3b)subjectto∑j=1naijI,aijSxjI,xjS≤biI,biS,i=1,2,…,m(3c)xjI,xjS≥0,j=1,2…,nwith [xjI,xjS], [cjI,cjS], [qijI,qijS], [biI,biS], [aijI,aijS]∈I(R), I(R) are the set of all interval numbers in R, and ∑j=1n∑k=1n[qjkI,qjkS][xjI,xjS][xkI,xkS] is negative semidefinite.Constraint[xjI,xjS]≥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)
Letc_=[cI,cS] be interval coefficient and let x_j=[xI,xS], xI>0, be positive interval variable (xI>0), then there are three possible equations that relate to the value of the coefficient:
(i)
ifcI>0, then c_x_=[cI,cS][xI,xS]=[cIxI,cSxS],(ii)
ifcS<0, then c_x_=[cI,cS][xI,xS]=[cIxS,cSxI],(iii)
ifcI<0<cS, then c_x_=[cI,cS][xI,xS]=[cIxS,cSxS].Thus, ifxI>0, then (4)cI,cSxI,xS=min⁡cIxI,cIxS,max⁡cSxI,cSxS(2)
Letq_=[qI,qS] be interval coefficient and let x_j=[xjI,xjS], x_k=[xkI,xkS] with xjI>0, xkI>0 be two positive interval variables, then there are three possible equations that relate to the coefficient value:
(i)
ifqI>0, then q_x_jx_k=[qI,qS][xjI,xjS][xkI,xkS]=[qIxjIxkI,qSxjSxkS],(ii)
ifqS<0, then q_x_jx_k=[qI,qS][xjI,xjS][xkI,xkS]=[qIxjSxkS,qSxjIxjI],(iii)
ifqI<0<qS, then q_x_jx_k=[qI,qS][xjI,xjS][xkI,xkS]=[qIxjSxkS,qSxjSxkS].Thus, ifxjI>0, xkI>0, then (5)qI,qSxjI,xjSxkI,xkS=min⁡qIxjIxkI,qIxjSxkS,max⁡qSxjIxkI,qSxjSxkSIn (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 ofx_j 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 x_∗∈Q is an optimal point solution if z(x_∗)≥z(x_) for all x_∈Q, and z(x_∗) 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 (≤) can be seen in the following theorem.Theorem 7.
If interval inequality of the constraints∑j=1n[ajI,ajS][xjI,xjS]≤[bI,bS] with [xjI,xjS]≥0, then ∑j=1nminajIxjI,ajIxjS≤bS is the maximum feasible area and ∑j=1nmaxajSxjI,ajSxjS≤bI is the minimum feasible area.Proof.
Let∑j=1najxj≤b be any inequality of the interval inequality ∑j=1n[ajI,ajS][xjI,xjS]≤[bI,bS] with aj∈[ajI,ajS], bj∈[bI,bS], xj∈[xjI,xjS]. Based on (4), for any particular solution xj≥0, xj∈[xjI,xjS], we have(6)∑j=1najxj≤∑j=1najSxj≤∑j=1nmaksajSxjI,ajSxjSTherefore if ∑j=1nmaxajSxjI,ajSxjS≤bI at an interval vector x_=(x_1,x_2,⋯,x_n)T, then we have (7)∑j=1najxj≤∑j=1najSxj≤∑j=1nmaxajSxjI,ajSxjS≤bI≤bSSo x_ must satisfy all possible versions of the interval inequalities simultaneously. Thus,(8)∑j=1nmaxajSxjI,ajSxjS≤bIis  the  minimum  feasible  area.Furthermore, based on (4), for any particular solution xj≥0, xj∈[xjI,xjS], we also have(9)∑j=1nmin⁡ajIxjI,ajIxjS≤∑j=1najIxj≤∑j=1najxj≤b≤bSTherefore, any particular solution which satisfies interval inequality will also satisfy (10)∑j=1nmin⁡ajIxjI,ajIxjS≤bSThus, (11)∑j=1nminajIxjI,ajIxjS≤bSis  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.
Ifz=∑j=1ncjI,cjSxjI,xjS+1/2∑j=1n∑k=1n[qjkI,qjkS][xjI,xjS][xkI,xkS] is the objective function with [xjI,xjS]≥0, then ∑j=1nmincjIxjI,cjIxjS+1/2∑j=1n∑k=1nmin{qjkIxjIxkI, qjkIxjSxkS}≤∑j=1nmaxcjSxjI, cjSxjS+1/2∑j=1n∑k=1nmaxqjkSxjIxkI,qjkSxjSxkS.Proof.
We have[xjI,xjS]≥0 and [xkI,xkS]≥0,j,k=1,2,…,n. Based on (4) and (5), we get (12)∑j=1ncjI,cjSxjI,xjS=∑j=1nmin⁡cjIxjI,cjIxjS,max⁡cjSxjI,cjSxjSand (13)12∑j=1n∑k=1nqjkI,qjkSxjI,xjSxkI,xkS=12∑j=1n∑k=1nminqjkIxjIxkI,qjkIxjSxkS,∑k=1nmaxqjkSxjIxkI,qjkIxjSxkS=12∑j=1n∑k=1nminqjkIxjIxkI,qjkIxjSxkS,∑j=1n∑k=1nmaxqjkSxjIxkI,qjkIxjSxkSClearly we obtain the following expression:(14)∑j=1nmincjIxjI,cjIxjS+12∑i=1n∑j=1nminqijIxiIxjI,qijIxiSxjS≤∑j=1nmaxcjSxjI,cjSxjS+12∑i=1n∑j=1nmaxqijSxiIxjI,qijSxiSxjSBased on Theorems7 and 8, we obtain a pair of one-level classical quadratic programming model with special characteristics, as follows.(a)
The best optimum:(15a)
M
a
x
i
m
i
z
e
z
S
=
∑
j
=
1
n
m
a
x
c
j
S
x
j
I
,
c
j
S
x
j
S
+
1
2
∑
j
=
1
n
∑
k
=
1
n
m
a
x
q
j
k
S
x
j
I
x
k
I
,
q
j
k
S
x
j
S
x
k
S
(15b)
s
u
b
j
e
c
t
t
o
∑
j
=
1
n
m
i
n
a
i
j
I
x
j
I
,
a
i
j
I
x
j
S
≤
b
i
S
,
i
=
1,2
,
…
,
m
(15c)
x
j
S
-
x
j
I
≥
0
,
j
=
1,2
,
…
,
n(b)
The worst optimum:(16a)
M
a
x
i
m
i
z
e
z
I
=
∑
j
=
1
n
m
i
n
c
j
I
x
j
I
,
c
j
I
x
j
S
+
1
2
∑
j
=
1
n
∑
k
=
1
n
m
i
n
q
j
k
I
x
j
I
x
k
I
,
q
j
k
I
x
j
S
x
k
S
(16b)
s
u
b
j
e
c
t
t
o
∑
j
=
1
n
m
a
x
a
i
j
S
x
j
I
,
a
i
j
S
x
j
S
≤
b
i
I
,
i
=
1,2
,
…
,
m
(16c)
x
j
S
-
x
j
I
≥
0
,
j
=
1,2
,
…
,
nThe 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 functionConstraint: the maximum feasible areaModel-2: The worst optimum problem
Objective function: the worst version of the objective functionConstraint: the minimum feasible regionStep 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 modelStep 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 problemIf 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]. (17a)Minimizez_=-10,-6x1+2,3x2+-1,1x1x2+4,10x12+10,20x22(17b)subjectto1,2x1+3x2≤1,10(17c)-2,8x1+4,6x2≤4,6(17d)x1,x2≥0According to [3], the optimum value solution of the model on (17a)-(17d) is z_=zI,zS=[-6.25,-0.9] with the best optimum problem being zS=-0.9, x1=0.3, x2=0 and the worst optimum problem being zI=-6.25, x1=1,25, x2=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_1=0.5, x_2=0 and optimum value is z_=[-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. (18a)Maximizez_=6,10x_1+-3,-2x_2+-1,1x_1x_2+-10,-4x_12+-20,-10x_22(18b)subjectto1,2x_1+3x_2≤1,10(18c)-2,8x_1+4,6x_2≤4,6(18d)x_1,x_2≥0Based 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 (19) M a x i m i z e  z S = 10 x 1 S - 2 x 2 I - 4 x 1 I 2 + x 1 S x 2 S - 10 x 2 I 2 s u b j e c t   t o  x 1 I + 3 x 2 I ≤ 10 - 2 x 1 S + 4 x 2 I ≤ 6 x 1 S - x 1 I ≥ 0 x 2 S - x 2 I ≥ 0 x 1 I , x 1 S , x 2 I , x 2 S ≥ 0
The Worst Optimum Problem
Model-2 (20) M a x i m i z e  z I = 6 x 1 I - 3 x 2 S - 10 x 1 S 2 - x 1 S x 2 S - 20 x 2 S 2 s u b j e c t   t o  2 x 1 S + 3 x 2 S ≤ 1 8 x 1 S + 6 x 2 S ≤ 4 x 1 S - x 1 I ≥ 0 x 2 S - x 2 I ≥ 0 x 1 I , x 1 S , x 2 I , x 2 S ≥ 0Step 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 (21) M a x i m i z e  z S = 10 x 1 S - 2 x 2 I - 4 x 1 I 2 + x 1 S x 2 S - 10 x 2 I 2 S u b j e c t   t o  x 1 I + 3 x 2 I ≤ 10 - 2 x 1 S + 4 x 2 I ≤ 6 2 x 1 S + 3 x 2 S ≤ 1 8 x 1 S + 6 x 2 S ≤ 4 x 1 S - x 1 I ≥ 0 x 2 S - x 2 I ≥ 0 x 1 I , x 1 S , x 2 I , x 2 S ≥ 0
The Worst Optimum Problem
Model-2 (22) M a x i m i z e  z I = 6 x 1 I - 3 x 2 S - 10 x 1 S 2 - x 1 S x 2 S - 20 x 2 S 2 S u b j e c t   t o  2 x 1 S + 3 x 2 S ≤ 1 8 x 1 S + 6 x 2 S ≤ 4 x 1 S - x 1 I ≥ 0 x 2 S - x 2 I ≥ 0 x 1 I , x 1 S , x 2 I , x 2 S ≥ 0Solution of the new Model-1 is [x1I,x1S]=[0,0.5], [x2I,x2S]=[0,0] and solution of Model-2 is [x1I,x1S]=[0.3,0.3][x2I,x2S]=[0,0].Step 4.
The interval solution is obtained by setting the supremum and infimum values of the previous solution, which are(i)
x1S=0.5, x2S=0,(ii)
x1I=0.3, x2I=0.
From (i) and (ii) we get the solution of quadratic programming with interval variables as follows:(i)
The optimum points arex_1=[0.3,0.5] and x_2=[0,0] which satisfy Definition 5.(ii)
The optimum value isz_=[-0.7,4.67] or equivalent to -z_=[-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 Algorithm9. 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.



---

*Source: 5204375-2018-07-30.xml*