Monotonicity Characterization of Interval Quadratic Programming
Takayuki Ishizaki1,2 , Masakazu Koike1,2 , Nacim Ramdani3 , Jun-ichi Imura1,2

Abstract— In this paper, we characterize a monotonicity ofthe solution of interval quadratic programming that involves
an interval-valued parameter in the objective function andlinear constraints. To give a characterization of monotonicity,
we first analyze the derivative of a solution candidate forquadratic programming, on the basis of the Karush-KuhnTucker condition. Then, deriving a condition for the objectivefunction to assure the monotonicity, we propose a method toexactly find the upper and lower limits of optimal solutions
by a finite number of operations. Finally, we provide anillustrative example of power supply scheduling to demonstrate
the efficiency of our solution method.

I. I NTRODUCTION
The recent development of computing technology enables
us to efficiently solve optimization problems in a numericalmanner. In this trend, a wide variety of solution algorithms
for linear and nonlinear programming have been investigated.
In particular, for the past several decades, optimization
problems involving interval-valued parameters have beengathering attention to deal with more realistic issues in whichavailable data include uncertainty due to observation andprediction errors. In such optimization problems, interval
analysis techniques are often utilized for, e.g., computing
the enclosures of feasible solution space; see [1], [2] foran overview of interval analysis theory, and see [3], [4],[5] for the application of linear and nonlinear programming
involving interval-valued parameters.
In this paper, we consider a quadratic programming
problem that involves an interval-valued parameter, which
we call interval quadratic programming. It is well known
that quadratic programming is one of major optimization
techniques in engineering and operations research, and it
involves various kinds of important applications to engineering design [6], [7], economics [8] and so forth. Owing to thepotential for wide applications, a number of efficient solution
algorithms, such as interior-point methods [9], [10], havebeen developed for the standard quadratic programming.
However, a solution to interval quadratic programming is notnecessarily easy to find. This is because, to investigate therange of the optimal solution varying with an interval-valued
parameter, we need to solve the quadratic programming for
all possible (i.e., infinite many) parameters in general.
1 Department of Mechanical and Environmental Informatics, Graduate
School of Information Science and Engineering, Tokyo Institute of Technology; 2-12-1, Meguro, Tokyo, Japan:{ishizaki, koike, imura}@cyb.mei.titech.ac.jp
2 CREST, Japan Science and Technology Agency; 4-1-8, Honcho,
Kawaguchi, Saitama, 332-0012, Japan.
3 Universite d’Orleans, PRISME; 63 av. de Lattre de Tassigny, 18020
Bourges, France: Nacim.Ramdani@univ-orleans.fr

As one approach to overcome this difficulty, giving acharacterization of the solution of interval quadratic programming, we propose a method to calculate the upperand lower limits of optimal solutions. It is turned out thatthe proposed method has the advantage to exactly find theupper and lower limits by a finite number of operations.
Furthermore, to demonstrate its efficiency, we provide anillustrative example of power supply scheduling, in which theuncertainty of demand prediction is modeled as an intervalvalued parameter.
Note that most of studies on interval analysis focuses
mainly on finding the global extremum of a multivariable
function, or on covering a feasible solution set complying
with equality and inequality constraints. To this end, aconstraint propagation technique [1], [2] is mostly applied.
In fact, the straightforward application of interval arithmetics
gives a solution to interval quadratic programming. However,it requires considerable computation cost to directly handle
interval-valued parameters. Moreover, the resultant solution
often becomes conservative due to an overestimation. To
the best of authors’ knowledge, there is no general method
based on the interval analysis for solving interval quadratic
programming in a computationally reasonable manner.
The reminder of this paper is structured as follows: In
Section II, we first formulate an interval quadratic programming problem to find the lower and upper limits of optimal
solutions. In Section III, we carry out a monotonicity analysisof the interval quadratic programming problem based on arepresentation of the solution candidate derived from the
Karush-Kuhn-Tucker condition. By this analysis, we derivea characterization to guarantee the monotonicity of the
optimal solution with respect to an interval-valued parameter.
Then, in Section IV, we provide an illustrative example ofpower supply scheduling to demonstrate the efficiency of the
proposed solution method. Finally, concluding remarks areprovided in Section V.
Notation. The following notation is used in this paper:R
set of real numbers
R≥0
set of nonnegative real numbers
R>0
set of positive real numbers
Inn-dimensional unit matrix
eni
ith column of In
1nn-dimensional all-ones vector|I|
cardinality of a set I
P(I)power set of a set I
im(M )
image of a matrix M
ker(M )
kernel of a matrix M
rank(M )rank of a matrix M

For a natural number n, let N[n] := {1, . . . , n}, and wedenote the block-diagonal matrix having M1 , . . . , Mn on its
block-diagonal by diag(Mi )i∈N[n] . Furthermore, we denotea matrix composed of column vectors of In corresponding
to the indices I ⊆ N[n] by enI ∈ Rn×|I| . In particular, if notconfusing, we omit the superscript of n.
We define the sets of matrices
Zn := {A ∈ Rn×n : ai,j ≤ 0, ∀i, j ∈ N[n], i ̸= j}Z+n := {A ∈ Zn : ai,i ≥ 0, ∀i ∈ N[n]}where ai,j denotes the (i, j)-element of A. Furthermore, we
define−1∈ Rn×n≥0 }Mn := {A ∈ Zn : A
M†n := {A ∈ Zn : eT
I AeI ∈ M|I| , ∀I ∈ P(N[n])\{∅, N[n]}}andT−1
Rn := {A ∈ Rn×n
∈ Z+n , ∀I ∈ P(N[n])\∅}.
≥0 : (eI AeI )II. P ROBLEM F ORMULATION

where
Aeq ∈ Rr×n ,andJ(x) :=bin ∈ Rm ,1 T
x Qx − pT x2

beq ∈ Rr

X ∗ := {x∗ (d) : d ∈ [d, d]}

(2)
n×n

(3)

for an interval quadratic programming problem in (1). Then,findx∗ = {x∗i } ∈ Rn , x∗ = {x∗i } ∈ Rn
(4)
where x∗iand x∗ix∗i = x∗i (d ),x∗i = x∗i (d(i) )

(6)

(i)

where the jth elements of d ∈ Rn and d(i) ∈ Rn are
defined as
{ (i)
{
}
dj := σi,j max σi,j dj , σi,j dj
(7)
{
}
(i)
dj := σi,j min σi,j dj , σi,j dj .
Note, however, that a mathematical characterization of themonotonicity is not trivial in general.

with a positive definite matrix Q = Q ∈ R
and a vectorp ∈ Rn . Suppose that the constraints and objective functionin (1) and (2) depend on an interval-valued parameter d ∈[d, d] ⊆ Rν . In this situation, the optimal solution x∗
should be a function of the parameter d. For such quadratic
programming, which called interval quadratic programming[11], [12], we formulate a problem to find the upper andlower limits of x∗ as follows:
Problem 1: Given [d, d] ⊆ Rν , defineTwhere fi and di denote the ith elements of f and d,respectively. Furthermore, an interval quadratic programming
problem in (1) is said to be monotone with respect to d ifx∗ is monotone with respect to d.
If an interval quadratic programming problem in (1) ismonotone with respect to d, then the solution of Problem 1
is obtained by(i)

In this paper, we deal with a quadratic programming
problem given by{
Ain x ≤ binx∗ = arg minn J(x) s.t.
(1)
Aeq x = beqx∈R
Ain ∈ Rm×n ,overestimation. Moreover, it generally requires considerable
computation cost.
In view of this, as a key notion to efficiently solve
Problem 1, we introduce the monotonicity of x∗ as follows:
Definition 1: Let [d, d] ⊆ Rν be given. A function f :νR 7→ Rn is said to be monotone with respect to d if, for anyi ∈ N[ν] and j ∈ N[ν], there exists a constant σi,j ∈ {−1, 1}
such that∂fj (d)≥ 0, ∀d ∈ [d, d] ⊆ Rν
σi,j
(5)
∂di

denote the maximum and minimum ithelements among all x∗ ∈ X ∗ .
In general, the solution of Problem 1 is not necessarily
easy to obtain. This is because, to examine the upper andlower limits of x∗ , we need to solve the interval quadratic
programming for all possible parameters, i.e., infinite many
parameters. In other words, solutions for a finite number ofd ∈ [d, d] do not give the exact bounds of x∗ .
From a theoretical point of view, straightforward application of interval arithmetics can be used for computing thebounds of x∗ . However, in practice, the resultant solution isoften conservative since the interval arithmetics forces us anIII. M ONOTONICITY C HARACTERIZATION OF I NTERVALQ UADRATIC P ROGRAMMING
A. Interval Quadratic Programming without Equality Constraint
First of all, we consider the case where the inequality
constraint in (1) is solely imposed on the interval quadratic
programming. A generalization to handle the equality constraint will be provided in Section III-B.
For the quadratic programming in (1), the Karush-KuhnTucker condition assures that there exists a nonnegative λ ∈Rm≥0 such that
 Qx∗ − p + AT
in λ = 0
λT (Ain x∗ − bin ) = 0(8)

Ain x∗ − bin ≤ 0.
The following proposition gives a representation of x∗ basedon the Karush-Kuhn-Tucker condition:
Proposition 1: Consider an interval quadratic programming problem in (1). Let I ∈ P(N[m]) such thatrank(AI ) = |I||I|×n
where AI := eT, and define
I Ain ∈ R
[
]−1 [
]
[
] Q ATpc
II0x (I) :=
n
bI
AI 0

(9)

(10)

|I|
where bI := eTI bin ∈ R . Then, it follows thatxc (I ∗ ) = x∗ ,I ∗ := {i ∈ N[m] : λi > 0}

(11)

where λi denotes the ith element of λ ∈ Rm
≥0 in (8).
Proof: Using the property of partitioned matrix inverse,
we rewrite (10) by
xc (I) = PI bI + GI p

(12)

where
−1 T −1
PI := Q−1 AT
AI ) ∈ Rn×|I| ,I (AI Q
−1
−1
GI := Q − PI AI Q ∈ Rn×n .

Note thateI eT
I λ = λ,(13)

AI x∗ = bI

if I = I ∗ . Thusx∗ = Q−1 p − Q−1 AT
Iξ

(14)

for ξ := eT
I λ. Multiplying it by AI from the left side, wehavebI = AI Q−1 p − AI Q−1 ATI ξ,
where AI Q−1 AT
I is nonsingular owing to (9). By solving
this equation with respect to ξ and substituting it into (14),
we obtainx∗ = PI bI + GI p,
which implies that xc (I ∗ ) = x∗ for (12). Hence, the claim
follows.
Proposition 1 gives a representation of the solution candidate xc that is parametrized by the index set I. It should
be noted that the monotonicity of x∗ is guaranteed if xc
is monotone for any I ∈ P(N[m]) satisfying (9). In what
follows, for simplicity of arguments, we assume that theinequality constraint is given by
[
]
[ + ]
In
b
Ain =
, bin =
(15)
−In
−b−
and the dependence on the parameter d ∈ [d, d] ⊆ Rν isrepresented as∂b+ (d)∂b− (d)∂p(d)== δ1 enN[ν] ,= δ2 enN[ν] (16)∂d∂d∂dfor δ1 ≥ 0 and δ2 ≥ 0. In this setting, we derive a tractable
representation of the derivative of xc as follows:
Lemma 1: Consider an interval quadratic programming
problem in (1) with (15), and suppose that (16) holds.
Furthermore, suppose that no equality condition is imposedon (1). Let I ∈ P(N[2n]) such that (9), and define−

K := K ∪ K ∈ P(N[n])
+

where

{

Proof:
verify that

(18)

−1 T
Π(K; A) := AeK (eTeK ∈ Rn×n
K AeK )
Γ(K; A) := A − Π(K; A)A ∈ Rn×n .

(19)

0

]

eK −

for (17). By defining
[
]
In
0
J1 :=
,
0 −In

−

∈ R2n×(|K |+|K |)+[J˜1 :=

I|K+ |
0

0],−I|K− |

˜ T
we have eT
I J1 = J1 eI . Furthermore, we have
[
]
In
T
T
T
eI J2 = [eK+ , eK− ] = eK , J2 :=.
In
Thus, it follows thatT ˜
˜ TAI = eTI Ain = eI J1 J2 = J1 eK .

(20)

In addition, owing to (16), we have
∂bI
∂bin
n
˜
˜ T n
= eT
= δ 1 eTI
I J1 J2 eN[ν] = δ1 J1 eK eN[ν] .
∂d∂dThus, by (12), we obtain
)
(
∂xc
n
= δ1 PI J˜1 eT
K + δ2 GI eN[ν] .
∂dFinally, substituting (20) into PI and GI yields−1
PI J˜1 eT),
K = Π(K; Q

GI = Γ(K; Q−1 ).

Hence, the claim follows.
Lemma 1 shows that the derivative of xc defined as in(10) can be represented as a function of Π and Γ in (19).
The sign pattern of the matrix functions Π and Γ can beanalyzed as follows:
Lemma 2: Let A ∈ Rn×n be nonsingular. Then, for any
K ∈ P(N[n]), Π and Γ in (19) satisfy
Π(K; A) ∈ Z+
n,
{

and
Γ(K; A) ∈A ∈ MnZ+
A−1 ∈ Rnn,n×n
R≥0 , A−1 ∈ Mn .

Proof: First, from the structure of Π, it follows thateT
K ΠeK = I|K| ,T
eK
ΠeK = 0,eT
K ΠeK = 0(21)

where K := N[n]\K. Note that, if A ∈ Mn , it follows that
|K|×|K|

AeK ∈ R≥0
−eT
K
Thus

Then, xc in (10) satisfies{}∂xc= δ1 Π(K; Q−1 ) + δ2 Γ(K; Q−1 ) enN[ν]
∂d
where

K+ ∩ K− = ∅,which implies that
[
eK +
eI =
0

(17)

K+ := {i ∈ N[n] : i ∈ I}
K− := {i ∈ N[n] : (i + n) ∈ I}.

Owing to I ∈ P(N[2n]) satisfying (9), we,|K|×|K|

−1
(eT
∈ R≥0
K AeK ).

−1
Π(K; A)eK = eT
AeK (eTeT
K AeK )KK

is constructed by the product of nonpositive and nonnegative
matrices. This implies that all elements of the submatrix
ΠeK are nonpositive. Hence, in conjunction with (21),eTKΠ ∈ Z+
n is proven for any K ∈ P(N[n]).
On the other hand, applying Lemma 6 in Appendix to Π,
we haveA−1 eK )−1 eT.
Γ(K; A) = eK (eTKKThus, the submatrices of Γ satisfyeT
K ΓeK = 0,
By noting that

Then, we haveeT
K ΓeK = 0,eTΓeK = 0.
K Z+ ,

A−1 ∈ RneTΓ(K; A)eK ∈
K


|K|

|K|×|K|
R≥0
,

A

−1

∈ Mn ,

Hence, the claim follows.
Theorem 1 shows that the interval quadratic programmingin (1) possesses the monotonicity if the matrix Q, whichcorresponds to the quadratic part of the objective functionin (2), belongs to the class of matrices specified by (22). As
one of meaningful matrices satisfying (22), we introduce thefollowing class of matrices:Lemma 3: Given α ∈ (−∞, 1] and w ∈ Rn>0 , define
wwT∈ Rn×n .
wT w

(23)


 Rn , α ∈ (−∞, 0]
Mn , α ∈ [0, 1)
Hn (α, w) ∈M†n , α = 1(24)Then, it follows thatHn−1 (α, w) ∈{Mn , α ∈ (−∞, 0]
Rn , α ∈ [0, 1).

(25)

Proof: From direct calculation, we can verify that
)
(
α
,w .
Hn−1 (α, w) = Hn(26)
α−1First, if α ∈ [0, 1), Hn ∈ Mn follows from Hn ∈ Zn
−1
and Hn−1 ∈ Rn×n
≥0 . Similarly, if α ∈ (−∞, 0], Hn ∈ Mn
follows from (26).
Next, if α = 1, the principal submatrix of the singularHn ∈ Zn can be represented byeT
K Hn (1, w)eK ,K ∈ P(N[n])\{∅, N[n]}.

wK := eT
K w.

T
wK
wK
< 1, ∀K ∈ P(N[n])\{∅, N[n]}wT w
since all entries of w are nonzero. Thus, for any principal†
submatrix of Hn , eT
K Hn eK ∈ M|K| holds. Hence, Hn ∈ Mn
follows.
Finally, if α ∈ (−∞, 0], the inverse of the principal
submatrices of Hn ∈ Rn×n
≥0 satisfies

0<then the quadratic programming problem is monotone withrespect to d.
Proof: If (22), it follows from Lemma 2 thatn×n
 (Γ ∈ Z+n ) ∨ (Γ ∈ R≥0 ), δ1 = 0+
Π ∈ Zn ,δ2 = 0+(Π ∈ Z+
)
∧
(Γ
∈
Z
),
δ
1 , δ2 ̸= 0.
n
n

and

)
T
wK
wK
, wK ,
wT w

Note that

we verify the claim.
Lemma 2 shows that the sign pattern of Π and Γ isinvariant with respect to any K ∈ P(N[n]) if the argument Aof Π and Γ belongs to a particular class of matrices. Basedon this fact, we can prove the following theorem:
Theorem 1: Consider an interval quadratic programming
problem in (1) with (15), and suppose that (16) holds.
Furthermore, suppose that no equality condition is imposed.
Ifδ1 = 0 (Q ∈ Rn ) ∨ (Q ∈ Mn ),Q−1 ∈ Mn ,
δ2 = 0(22)(Q ∈ Rn ) ∧ (Q−1 ∈ Mn ), δ1 , δ2 ̸= 0,

Hn (α, w) := In − α(eTK Hn (1, w)eK = H|K|

−1
−1
(eT
= H|K|(α̃, wK ) ∈ M|K| ⊂ Z|K|K Hn (α, w)eK )

where

T
wK
wK
∈ (−∞, 0].
Tw w
This implies that Hn ∈ Rn holds for any K. Similarly, if
α ∈ [0, 1), Hn−1 ∈ Rn is proven by (26).

α̃ := αBased on Lemma 3, the following result is straightforwardly obtained:
Corollary 1: Consider an interval quadratic programming
problem in (1) with (15), and suppose that (16) holds.
Furthermore, suppose that no equality condition is imposed.
For a natural number l, let{
αi ∈ (−∞, 1)
Q = diag (Hni (αi , wi ))i∈N[l] ,(27)iwi ∈ Rn>0∑lwhere i=1 ni = n and Hni is defined as in (23). If{
αi ∈ (−∞, 1), ∀i ∈ N[l], δ1 = 0(28)
αi ∈ (−∞, 0], ∀i ∈ N[l], δ1 ̸= 0,
then the quadratic programming problem is monotone withrespect to d.
Proof: If (28) holds, then (22) follows from Lemma 3.
Hence, the claim follows.
From Corollary 1 with Lemma 3, we can see that, if αi ∈(−∞, 0] for all i ∈ N[l], both Π and Γ belong to the class∗of Z+
n . This implies that xi is a monotonically increasing
function of di and a monotonically decreasing function of
dj for j ̸= i.
B. Interval Quadratic Programming with Equality Constraint
In this subsection, based on an orthogonal projection of thesolution space, we convert a quadratic programing problem
with an equality constraint to that without the equality
constraint. We show that the monotonicity of an interval
quadratic programing problem with equality constraints canbe analyzed by the procedure same as in Section III-A.
Let η ∈ Rn be a vector such that Aeq η = beq for (1).
Then, by replacing x − η by x as a new variable, we canrewrite the equality constraint as
Aeq x = 0.

(29)

It should be noted that this change of variables does notaffect the monotonicity of solutions as long as η is constant.
Therefore, we can assume (29) without loss of generality.
Based on this fact, we obtain the following lemma:
Lemma 4: Consider an interval quadratic programming
problem in (1), and suppose that beq = 0. Define V ∈ Rn×n̂
such that
im(V ) = ker(Aeq ),V T V = In̂(30)

where n̂ := n − r. Then, x∗ is given byx∗ = V x̂∗ ,ˆx̂∗ := arg min J(x̂)
s.t. Ain V x̂ ≤ binx̂∈Rn̂

(31)
where
1
ˆ
J(x̂)
:= x̂T Q̂x̂ − p̂T x̂,2{Q̂ := V T QV
p̂ := V T p.

Proof: We notice that V V T is the orthogonal projection
matrix onto ker(Aeq ) by the definition of (30). Thus
T −1
A := V V T = In − ATAeqeq (Aeq Aeq )(32)

holds. Furthermore, x ∈ ker(Aeq ) for x̂ = V T x, or
equivalently, (29) holds if and only if
x = Ax = V x̂.
Hence, the claim follows from rewriting (1) by using x̂ as
the variable of the quadratic programing in (31).
As shown in Lemma 4, we can equivalently rewrite aquadratic programming problem with an equality constraint
by that without the equality constraint. Based on this fact,
similarly to (18), we obtain the following representation of
the derivative of xc in (10):Lemma 5: Consider an interval quadratic programming
problem in (1) with (15), and suppose that (16) holds. Let
I ∈ P(N[2n]) such that (9), and define K as in (17). Then,xc in (10) satisfies∂xc= {δ1 Π(K; QV ) + δ2 Γ(K; QV )} enN[ν]∂dwhere Π and Γ are defined as in (19) andQV := V (V T QV )−1 V T ∈ Rn×n

(33)

(34)

with V satisfying (30).
Proof: To show the claim by a manner similar to theproof of Lemma 1, we replace the symbols in Lemma 1 as
xc → x̂c ,Ain → Ain V,

Q → Q̂,p → p̂.

Then, from (12), we have
)
(
∂ x̂c
T
enN[ν]= δ1 P̂I J˜1 eT
K + δ2 ĜI V∂dwhere P̂I and ĜI are defined by replacing the symbols in(13) asQ → Q̂ = V T QV,

AI → ÂI = J˜1 eT
K V.

Noting that V x̂c = xc , we obtain
V P̂I J˜1 eT
K = Π(K; QV ),V ĜI V T = Γ(K; QV ).

Hence, the claim follows.
As shown in Lemma 5, the derivative of xc can be
represented by the functions of Π and Γ, similarly to thecase where the inequality constraint is not imposed on thequadratic programming. It should be noted that Q−1 in (18)is replaced with QV in (33), which is defined through theorthogonal projection. Based on this fact, we can prove thefollowing theorem:
Theorem 2: Consider an interval quadratic programming
problem in (1) with (15), and suppose that (16) holds. Let
I ∈ P(N[2n]) such that (9), and define K as in (17). If
Q = In andi
Aeq = diag(wiT )i∈N[r] ∈ Rr×n
wi ∈ Rn>0
(35)
≥0 ,
∑r
where i=1 ni = n, then the quadratic programming problem is monotone with respect to d.
Proof: Note that if Q = In , then QV = A for A
defined as in (32). Furthermore, by the definition of A andLemma 3, we verify thatA = diag (Hni (1, wi ))i∈N[r] ∈ M†n(36)

for Aeq in (35). Thus, in a manner similar to the proof of
Lemma 2, we can prove that, for any K in (17) constructedby I ∈ P(N[2n]) satisfying (9), Π(K; A) ∈ Z+
n holds.
On the other hand, substituting (32) into Γ yields()
eT
Γ(K; A) = eK diag Hni (1, eT
w
)
∈ Z+
i
n
Ki
K
i∈N[r]

where
K := N[n]\K,

eK = [eK1 , . . . , eKr ].

Hence, the claim follows.
By comparing Theorem 2 with Corollary 1, we cansee that, from the viewpoint of monotonicity, the interval
quadratic programming with Q = In subject to the equality
constraint in (36) is equivalent to that with Q given as in (27)for αi ∈ (−∞, 0] subject to no equality constraint. It should
be noted that, if we get rid of the assumption of Q = In , QV
in (34) does not coincide with A in (36), and thus it isdifficult to systematically characterize the monotonicity of
the interval quadratic programming.
IV. A PPLICATION TO P OWER S UPPLY S CHEDULING
A. Monotonicity Analysis
In this subsection, we formulate a power supply schedulingproblem as an interval quadratic programming problem. In
this problem, taking into account the uncertainty of demandprediction, we aim to minimize an objective function reflecting the fuel cost of generators and the degradation cost of
storage batteries.
Dividing a day into n moments, we denote the temporalsequence of uncertain predicted demand by d ∈ Rn . We
suppose that d varies within a fixed interval [d, d] ⊆ Rn ,

which can be regarded as a confidence interval of demandprediction [13], [14]. For this demand prediction, we consider
keeping a supply-demand balance by the power of generatorsand the charge and discharge power of storage batteries. We
denote the temporal sequence of the total generator power byx ∈ Rn , and the total charge and discharge power of storage
batteries by ∆y ∈ Rn . In this notation, the supply-demandbalance can be represented by∆y = x − d.

(37)

We impose the inequality constraint described as∆ymin 1n ≤ ∆y ≤ ∆ymax 1n(38)where ∆ymin ∈ R and ∆ymax ∈ R are the constants
representing the bounds of ∆y. Furthermore, we denote thetotal energy of the batteries by
y := [y1 , . . . , yn ]T ∈ Rn

(39)

where the ith element is defined by
yi := y0 +

i
∑

∆yj

j=1

with the initial value of y0 ∈ R. The equality constraint is
imposed on (39) as
yn = y0 + yD

(40)

where yn ∈ R denotes the total energy at the termination
time, and yD ∈ R denotes a desired energy to be charged in
the day of interest. Moreover, taking into account the fuelcost of generators and the degradation cost of batteries, wedefine the objective function byTTf (x, ∆y) := α1 xT x + α2 1T
n x + α3 ∆y ∆y + α4 1n ∆y (41)where α1 , . . . α4 ∈ R are nonnegative coefficients.
By substituting (37), the optimal power generation planthat minimizes the objective function in (41) is given byf (x, x − d)x∗ (d) = arg min
n
x∈R

(42)

where the inequality constraint in (38) can be rewritten as
[
]
[
]
In
∆ymin 1n + d
Cin (x; d) :
x≤
(43)
−In
−(∆ymax 1n + d)
and the equality constraint in (40) asT
Ceq (x; d) : 1Tn x = 1n d + yD .

(44)

In addition, as being compatible with (37), the optimalbattery charge cycles is given by∆y ∗ (d) := x∗ (d) − d.

(45)

For this interval quadratic programming, we can prove thefollowing fact:
Corollary 2: Let d ∈ [d, d] be given, and consider theinterval quadratic programming in (42) subject toCin (x; d),Ceq (x; d0 )(46)

where Cin and Ceq are defined as in (43) and (44), respectively, and
d+d
d0 :=
∈ Rn .
(47)
2
Define ∆y ∗ as in (45). Then, both x∗ and ∆y ∗ are monotonewith respect to d.
Proof: Note that the objective function in (42) without
the constant term can be rewritten by J in (2) with
Q = 2(α1 + α3 )In ,p = 2α3 d − α2 1n .

Thus, by using Theorem 2, the monotonicity of x∗ is proven.
Next, we prove the monotonicity of ∆y ∗ . To this end, it
suffices to show that∆y c (I; d) := xc (I; d) − d
is monotone for any I ∈ P(N[2n]) such that (9), where xc
is defined as in (10). By direct calculation, we obtain
∂∆y c
1
T
T
= − (1 − δ) eK eT−
e 1 1Tn (eK eK + δeK eK )K
∂d
|K| K |K|
where K is defined as in (17), K := N[n]\K and
α3 α1
δ :=
.
α2 + α3 α1Since δ ∈ [0, 1], all elements of ∂∆y c /∂d are nonpositive
for any K ∈ P(N[n]). Hence, the claim follows.
Corollary 2 shows that the interval quadratic programming
problem in (42) is monotone as long as the equality constraint does not depend on the parameter d. Moreover, in
this power supply scheduling problem, not only the optimal
power generation plan x∗ but also the optimal battery charge
cycles ∆y ∗ possess the monotonicity with respect to d.
B. Numerical Example
In this subsection, through a numerical example, we show
the efficiency of our method to find the lower and upper limits of optimal solutions. As a confidence interval of demandprediction, we use the temporal sequence of intervals shownin Fig. 1, which is based on the data provided by Tokyo
Electric Power Company managing 19 million demanders.
In this figure, the solid line with circles represents d0 in(47), and the thick solid lines represent d and d.
We fix the bounds of ∆y in (38) as ∆ymax = 6 × 106 kW
and ∆ymin = −6×106 kW, the initial and termination valuesof total energy as y0 = yD = 0, and the coefficients of thefuel cost function in (41) as α1 = 0.38×10−12 JPY/W2 h and
α2 = 5000×10−6 JPY/Wh. In this setting, varying the coefficients of the degradation cost of storage batteries as shownin Table I, we solve the interval quadratic programming
problem in (42). The result is shown in Fig. 2, whose first to
third figure corresponds to Case 1 to Case 3, respectively.
In these figures, the lines with circles denote the optimal
solutions for d0 in (47), and the thick solid lines denote thevalues of the upper and lower limits. From these figures, we
see that the difference between the upper and lower limits ofpower generation plan, which corresponds to the regulating
capacity of generators, increases as we use more expensive,i.e., higher degradation cost, storage batteries.

7

7

x 10

2.5

x 10

Case 1

2.5

2

2

1.5

1.5

1

1

0.5

0.5

0

Gneneration Power00

5Fig. 1.

10
15Time [h]Charge/Discharge Power

−0.5

20
Generation Power and Charge/Discharge Power [kW]PV/Demand Prediction [kW]3

Model of Uncertain Demand Prediction.

V. C ONCLUSION
In this paper, we have characterized a monotonicity of thesolution of interval quadratic programming that involves aninterval-valued parameter in the objective function and linear
constraints. Based on the monotonicity characterization, we
have proposed a method to find the lower and upper limitsof the solutions for the interval quadratic programming by
a finite number of operations. Moreover, we have provided
an illustrative example of power supply scheduling and wehave shown that the optimal solution of power generation as
well as battery charge cycles possess the monotonicity. An
enhancement to handle more general form of inequality andequality constraints is currently under investigation.

−1
0

5

10

15

20

7

2.5

x 10

Case 22

Gneneration Power

1.5
1
0.5

Charge/Discharge Power

0
−0.5
−1
0

5

10

15

20

7

2.5

x 10

Gneneration Power

Case 32
1.5
1

A PPENDIX

0.5
Charge/Discharge Power

Lemma 6: Let A ∈ Rn×n be a nonsingular matrix, andP ∈ Rn×k and P ∈ Rn×(n−k) such that

0
−0.5

T

T

P P + P P = In .

−1
0

5

T

Suppose that P T AP and P A−1 P are nonsingular. Then
T

10
15Time [h]20T

AP (P T AP )−1 P T = In − P (P A−1 P )−1 P A−1

Fig. 2.

Power Generation Plan and Battery Charge Cycles.

holds.
T

T

Proof: Using Ξ := P (P A−1 P )−1 P , we defineT

Thus, we haveÂ := P T A−1 P − P T A−1 ΞA−1 P= P T XA−1 P + P T XA−1 ΞA−1 P= P T XA−1 Y P,

T

Y := In − ΞA−1 = In − P (P A−1 P )−1 P A−1 .
Furthermore, by defining X := In − A−1 Ξ, it follows from
(A−1 Ξ)2 = A−1 Ξ that
XA

−1

where the last equality comes from X 2 = X andΞ = 0.

XA−1 Y = X 2 A−1 = XA−1 .
In addition, from the facts that

TABLE ITP P T X = (In − P P )X = X

C OEFFICIENTS OF D EGRADATION C OST F UNCTION OF S TORAGE
BATTERIES .

and
α3 JPY/W2 h
α4 JPY/Wh

Case 11.80 × 10−14−2.17 × 10−7

Case 21.80 × 10−13−2.17 × 10−6

Case 31.80 × 10−12−2.17 × 10−5

TY P P T = Y (In − P P ) = Y,
we obtain

P ÂP T = XA−1 Y = A−1 Y

by XA−1 = A−1 Y and Y 2 = Y . Note that Â = (P T AP )−1
holds as shown in [15], and thus it follows thatY = AP (P T AP )−1 P T .
Hence the claim follows.
R EFERENCES[1] L. Jaulin, Applied interval analysis: with examples in parameter andstate estimation, robust control and robotics. Springer, 2001.
[2] E. Hansen and G. W. Walster, Global optimization using interval
analysis: revised and expanded. CRC Press, 2003, vol. 264.
[3] Q. Lin and G. Huang, “IPEM: an interval-parameter energy systems
planning model,” Energy Sources, Part A, vol. 30, no. 14-15, pp. 1382–
1399, 2008.
[4] Y. Zhu, Y. Li, and G. Huang, “Planning municipal-scale energy
systems under functional interval uncertainties,” Renewable Energy,
vol. 39, no. 1, pp. 71–84, 2012.
[5] L. He, G. H. Huang, G. Zeng, and H. Lu, “An interval mixedinteger semi-infinite programming method for municipal solid waste
management,” Journal of the Air & Waste Management Association,
vol. 59, no. 2, pp. 236–246, 2009.
[6] J. A. Petersen and M. Bodson, “Constrained quadratic programming
techniques for control allocation,” Control Systems Technology, IEEE
Transactions on, vol. 14, no. 1, pp. 91–98, 2006.
[7] T. Dwyer, Y. Koren, and K. Marriott, “Drawing directed graphs using
quadratic programming,” Visualization and Computer Graphics, IEEE
Transactions on, vol. 12, no. 4, pp. 536–548, 2006.
[8] G. F. Reid and L. Hasdorff, “Economic dispatch using quadratic
programming,” Power Apparatus and Systems, IEEE Transactions on,
no. 6, pp. 2015–2023, 1973.
[9] Y. Nesterov, A. S. Nemirovskii, and Y. Ye, Interior-point polynomialalgorithms in convex programming. SIAM, 1994, vol. 13.
[10] R. Cottle, J. Pang, and R. Stone, “The linear complementarity problem.
1992,” AP, New York.
[11] 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.
[12] 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.
[13] B. Petiau, “Confidence interval estimation for short-term load forecasting,” in PowerTech, 2009 IEEE Bucharest. IEEE, 2009, pp. 1–6.
[14] A. Seppälä, Load research and load estimation in electricity distribution. Technical Research Centre of Finland, 1996.
[15] T. Ishizaki, H. Sandberg, K. H. Johansson, K. Kashima, J.-i. Imura,and K. Aihara, “Structured model reduction of interconnected linear
systems based on singular perturbation,” in American Control Conference (ACC), 2013. IEEE, 2013, pp. 5544–5549.