2012 International Symposium on Nonlinear Theory and its Applications
NOLTA2012, Palma, Majorca, Spain, October 22-26, 2012

A Modified Multiplicative Update Algorithm for Convex
Quadratic Programming Problems with Nonnegativity Constraints
Jiro Katayama† and Norikazu Takahashi‡†Graduate School of Information Science and Electrical Engineering, Kyushu University‡Faculty of Information Science and Electrical Engineering, Kyushu University
744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan.
Email: jiro.katayama@inf.kyushu-u.ac.jp, norikazu@inf.kyushu-u.ac.jp
Abstract—A multiplicative update for solving convex
quadratic programming problems with nonnegativity constraints, which was proposed by Sha et al., has three advantages: 1) nonnegativity of solutions is automatically satisfied, 2) no parameter tuning is needed, and 3) implementation is easy because of simple update formula. However,
the global convergence of the update is not always guaranteed. In this paper, we propose a modified version of
the multiplicative update and prove its global convergence
without any assumption on the problem. We also show experimentally that our modification aﬀects neither the computation time nor the number of iterations
1. Introduction
Problems of minimizing an objective function under
nonnegativity constraints arise in various fields. For example, Nonnegative Matrix Factorization (NMF) [1, 2],which is to approximate a given large nonnegative matrix by the product of two small nonnegative matrices andhas attracted remarkable attention in the fields of machinelearning, signal processing and so on, is formulated as an
optimization problem with nonnegativity constraints. In
this paper, as an important class of these problems, we consider convex quadratic programming (QP) problems with
nonnegativity constraints.
Sha et al. [3] recently proposed a multiplicative update
for convex QP problems with nonnegativity constraints,
which is based on multiplicative updates for NMF developed by Lee and Seung [1]. The algorithm of Sha et al. has
three main advantages: 1) nonnegativity of variables is automatically satisfied, 2) no parameter tuning is needed, and
3) implementation is easy because of simple update formula. Furthermore, under some assumptions on the QP
problem and the initial solution, Sha et al. proved that any
sequence of solutions generated by their update converges
to the unique optimal solution.
In this paper, we propose a modified version of the multiplicative update of Sha et al. and prove its global convergence without any assumption on the QP problem and theinitial solution. We also construct an multiplicative update
algorithm which always stops within a finite number of iterations after finding an approximate solution. We finallyshow experimentally that our modification aﬀects neither
the computation time nor the number of iterations.
2. Multiplicative Update Proposed by Sha et al.
We consider optimization problems of the form:
minimize F(v) = 12 vT Av + bT v
subject to v ≥ 0(1)

where v = [v1 , v2 , . . . , vn ]T ∈ Rn is a variable vector,
A = [Ai j ] ∈ Rn×n is a positive definite constant matrix, andb = [b1 , b2 , . . . , bn ]T ∈ Rn is a constant vector. Throughout this paper, the inequality between two vectors meanscomponentwise inequality. Based on the idea behind thedevelopment of multiplicative updates for NMF [1], Sha etal. [3] recently proposed a multiplicative update for solving the optimization problem (1). Let vk = [vk1 , vk2 , . . . , vkn ]Tbe the solution after k iterations. Then their update is expressed as follows:√−bi + b2i + 4aki cki
=
vk+1
(2)
vki
i
2aki
where aki = (A+ vk )i , cki = (A− vk )i , A+ = [A+i j ] is defined by{
Ai j , if Ai j > 0
A+i j =
0,otherwise
and A+ = [A−i j ] is defined by{|Ai j |, if Ai j < 0A−i j =
0,otherwise
It is easily seen that the right-hand side of (2) is positiveif vki > 0 and the following assumption is satisfied.
Assumption 1 The i-th row of A has one or more negative
elements whenever bi ≥ 0.
Therefore, if the initial solution v0 is positive and Assumption 1 is valid then any sequence {vk }∞k=0 generated by (2)satisfies vk > 0 for all k.
Sha et al. studied in detail the convergence properties of(2) under Assumption 1 and proved the following theoremby using Zangwill’s global convergence theorem [6, 7].

- 431 -

Theorem 1 ([3]) Suppose that the origin is not the optimal solution of (1) and the initial vector v0 is positive andF(v0 ) < F(0) = 0. Then the sequence {vk }∞k=0 converges tothe optimal solution of (1).
Even if Assumption 1 is satisfied and the initial solution
v0 is positive, the limit of the sequence {vk }∞k=0 may not bea positive vector. Therefore, the update must be definedfor all nonnegative vectors vk in order to apply Zangwill’s
global convergence theorem. However, in the update (2), it
is not clear how the case where aki = 0 is dealt with. As apossible solution, we consider the modified update:√−bi + b2i +4aki cki kvi , if vki > 0
2aki
vk+1
=
(3)
i


 0,
if vki = 0
Let us suppose that oﬀ-diagonal elements in the i-th row
and i-th column of A are all zero. Then Aii must be positive
because A is assumed to be positive definite. Let us further
suppose that bi is negative. In this case, we have√√−bi + b2i + 0−bi + b2i + 4aki cki
vki =
vki
2aki
2Aii vki
−bi
=
>0
Aii

instead of (1). Note that (5) has the unique optimal solution
for any positive constant ϵ and it approaches the optimal
solution of (1) as ϵ goes to zero. As is well known in optimization theory, v ∈ [ϵ, ∞)n is the optimal solution of (5) if
and only if the KKT conditions
Av + b ≥ 0(Av + b)i (−vi + ϵ) = 0, i = 1, 2, . . . , n

(6)
(7)

are satisfied.
One of the main results of this paper is given by the following theorem.
Theorem 2 For any positive constant ϵ and the initial solution v0 ∈ [ϵ, ∞)n , the sequence {vk }∞k=0 generated by themodified multiplicative update (4) has at least one convergent subsequence and they converge to the unique optimal
solution of (5).
Note that this theorem does not require any assumption
on A and b except that A is positive definite. Proof of thistheorem will be given in the next section.
We next develop a multiplicative update algorithm which
always stops within a finite number of iterations. The stopping criterion we employ for the algorithm is given by
Av + b ≥ −δ1 1|(Av + b)i (−vi + ϵ)| < δ2 ,(8)

i = 1, 2, . . . , n(9)for all vki > 0 and hence the update (3) can be rewritten as{−bi /Aii , if vki > 0
=
vk+1
i
0,
if vki = 0

where δ1 and δ2 are positive constants. As is easily seen,
this criterion is a relaxed version of the KKT conditions (6)and (7). The proposed algorithm is described as follows.

This means that the update (3) is not continuous in the region {v ∈ Rn | v ≥ 0, vi = 0}, and hence Zangwill’s global
convergence theorem cannot be applied to (3).

Step 1: Set k = 0 and choose the initial solution v0 suchthat v0 ≥ ϵ1.

3. Modified Multiplicative Update and Its Global Convergence
In order to avoid the problem described in the previous
section, we propose a modified multiplicative update:√ −b + b2 + 4ak ck iii i k
(4)
vk+1= max ϵ,vi 
i


2aki
where ϵ is any positive constant. Note that the same idea isused in Reference [4, 5] in which a modified multiplicative update for NMF is proposed. It is apparent that if
vk > 0 then the right-hand side is well-defined and we havevk+1 ≥ ϵ1 where 1 ∈ Rn is the vector whose elements are
all one. Therefore, if we choose the initial solution v0 suchthat v0 ≥ ϵ1 then the sequence of solutions {vk }∞k=0 generated by (4) satisfies vk ≥ ϵ1 for all k. We thus consider inthe following the optimization problem
minimizesubject toF(v) = 21 vT Av + bT v
v ≥ ϵ1

Algorithm 1

Step 2: Find vk+1 by the modified update (4).
Step 3: If v = vk+1 satisfies the stopping criterion (8) and(9) then stop. Otherwise, add 1 to k and go to Step 2.
From Theorem 1 and the continuity of the stopping criterion, we have the following theorem.
Theorem 3 For any positive constants ϵ, δ1 and δ2 , Algorithm 1 stops within a finite number of iterations.
Proof: Let {vkl }∞l=0 be any convergent subsequence of thesequence {vk }∞k=0 generated by the update (4). By Theorem 1, it converges to the unique optimal solution of (5).
We therefore have)(lim Avkl + b ≥ 0
l→∞
{
}
kl
lim (Av + b)i (−vki l + ϵ) = 0, i = 1, 2, . . . , nl→∞In other words, for any positive constants δ1 and δ2 , there
exists an positive integer L such that
Avkl + b ≥ −δ1 1|(Avkl + b)i (−vki l + ϵ)| ≤ δ2 ,(5)

i = 1, 2, . . . , n

for all l ≥ L. This completes the proof.

- 432 -



4. Proof of Theorem 1
We will prove Theorem 1 by using the same approach as
Sha et al. [3], that is, we apply Zangwill’s global convergence theorem [6, 7] to the update (4). We hereafter express(4) as vk+1 = M(vk ) for notational simplicity, where M isa mapping from [ϵ, ∞)n into itself. In order to prove Theorem 2 by using Zangwill’s global convergence theorem,
it suﬃces for us to show that the mapping M satisfies thefollowing conditions.
(i) For all k ≥ 0, vk belongs to a compact set.
(ii) The mapping M satisfies(a) v , v∗ ⇒ F(M(v)) < F(v)(b) v = v∗ ⇒ F(M(v)) ≤ F(v)(iii) The mapping M is continuous for all vectors v ∈[ϵ, ∞)n except the unique optimal solution of (5).

The objective function Gi (ui ) is strictly convex in [ϵ, ∞)becauseG′′i (ui ) =(A+ v)i (A− v)i vi
+
> 0.
vi
u2i

Thus the optimal solution u∗i of (13) is uniquely determinedby considering the solution of the equation G′i (ui ) = 0, andis given by√ −b + b2 + 4(A+ v) (A− v) 
i
i 
i

i


vi  .
u∗i = max ϵ,2(A+ v)i
This implies that the optimal solution of (10) is given byM(v). Therefore, we have G(M(v), v) < G(v, v) if M(v) ,v. From this inequality and the properties (11) and (12), wehaveF(M(v)) ≤ G(M(v), v) < G(v, v) = F(v)which completes the proof.

Lemma 1 The mapping M is continuous in [ϵ, ∞)n .
Lemma 2 If v ∈ [ϵ, ∞)n is not a fixed point of the mapping
M then F(M(v)) < F(v).
Proof: For given v ∈ [ϵ, ∞)n , we consider the optimization
problemminimize G(u, v)(10)subject to u ≥ ϵ1
whereLemma 3 v ∈ [ϵ, ∞) is a fixed point of the mapping M if
and only if it is the unique optimal solution of (5).
nProof: A vector v ∈ [ϵ, ∞)n is a fixed point of M if andonly if√−bi + b2i + 4(A+ v)i (A− v)i { ≤ v , if v = ϵiivi,= vi , if vi > ϵ2(A+ v)ii = 1, 2, . . . , n

1 ∑ (A+ v)i 2ui
2 i=1 vinG(u, v) =

(
) ∑
n
n
n
ui u j1 ∑∑ −−
Ai j vi v j 1 + log+
bi ui
2 i=1 j=1
vi v ji=1
which is well defined in [ϵ, ∞)n and continuous everywherein [ϵ, ∞)n . The function G(u, v) is an auxiliary function ofF(v), that is, it satisfies
F(u) ≤ G(u, v), ∀u, v ≥ ϵ1
F(v) = G(v, v), ∀v ≥ ϵ1

(11)
(12)

(see Reference [3] for details). Also, since G(u, v) can be
rewritten asG(u, v) =n∑

1
Gi (ui ) − vT A− v
2
i=1

if vi = ϵ,if vi > ϵi = 1, 2, . . . , n

Noting that (A+ v)i +bi −(A− v)i = (Av+b)i , we see that thisis equivalent to (6) and (7). Since v ∈ [ϵ, ∞)n is the optimal
solution of (5) if and only if (6) and (7) are satisfied, we
can conclude that v ∈ [ϵ, ∞)n is a fixed point of M if andonly if v is the unique optimal solution of (5).
From Lemmas 2 and 3, we have the following lemma.
Lemma 4 If v ∈ [ϵ, ∞)n is the optimal solution of (5) thenF(M(v)) = F(v) holds because v is the fixed point of M.
Otherwise, F(M(v)) < F(v) holds.
Lemma 5 For any initial solution v0 ∈ [ϵ, ∞)n , the sequence {vk }∞k=0 generated by (4) belongs to the compact set
S = {v ∈ Rn | v ≥ ϵ1, F(v) ≤ F(v0 )}.

where
1 (A+ v)i 2ui
Gi (ui ) =ui − (A− v)i vi log + bi ui
2 vi
vi
the optimization problem (10) is decomposed into n independent optimization problems of the form:
minimize Gi (ui )subject to ui ≥ ϵwhich can be rewritten as{≥ 0,(A+ v)i + bi − (A− v)i
= 0,

(13)

Proof: It follows from Lemma 4 that F(vk ) ≤ F(v0 ) holds
for all k, that is, vk ∈ S for all k. Since F(v) is continuousand strongly convex, the level set {v ∈ Rn | F(v) ≤ F(v0 )} is
compact. Therefore S is also compact.
Lemmas 1, 4 and 5 mean that all of the three conditions in Zangwill’s global convergence theorem are satisfied. This completes the proof of Theorem 1.

- 433 -

100

Proposed
Sha et al.

1.4

80
number of iterations

1.2
1
time

Proposed
Sha et al.

0.8
0.6

60

40

0.4
20
0.2
0

0
50

100

150

200

250
300
size

350

400

450

500

50

100

150

200

250
300
size

350

400

450

500

Figure 1: Comparison of computation time between theoriginal (green) and modified (red) updates.

Figure 2: Comparison of the number of iterations between
the original (green) and modified (red) updates.

5. Numerical Experiments

the computation time and the number of iterations. A future problem is to extend the proposed update to the casewhere the objective function is not strictly convex.

In order to examine the eﬀect of the modifications of themultiplicative update and the optimization problem on thecomputational cost, we conducted numerical experiments.
We implemented both the original update (2) and the modified one (4) with Scilab 5.3.3 and applied them to convex QP problems with nonnegativity constraints with sizen from 50 to 500 on a Windows PC with Intel Core i5
2.53GHz CPU and 2GB RAM. The eﬀect is evaluated by
the computation time and the number of iterations which
are obtained by computing the averages over 30 randomly
generated problems. In all experiments, the positive constant ϵ was set to 10−4 , and the positive constants δ1 and δ2
are set to 10−5 .
Figure 1 shows the computation time of the original andmodified updates for QP problems with various sizes. Although the modified update requires an additional operation, i.e., the max operation, no significant diﬀerence canbe seen from the results. Moreover, when n is between 350
and 450, the modified update is a little bit faster than theoriginal. Unfortunately, the reason for this is not clear to
the authors. But anyway, we can say that our modification
has little eﬀect on the computation time. Figure 2 shows
the number of iterations of the original and modified updates. For all values of n, there is little diﬀerence between
these two updates. We can say from the results that ourmodification has no eﬀect on the number of iterations.
6. Conclusion
Global convergence of the multiplicative update proposed by Sha et al. [3] for solving strictly convex QP problems with nonnegativity constraints was studied. We havefirst pointed out an error in their global convergence proof.
We have next proposed a modified version of the multiplicative update and proved its global convergence. We
have finally shown that the modification has little eﬀect on

Acknowledgments
This work was supported by KAKENHI 24560076 and23310104.
References[1] D. D. Lee and H. S. Seung, “Algorithms for nonnegative matrix factorization,” in T. K. Leen, T. G. Dietterich and V. Tresp (Eds.), Advances in Neural Information Processing Systems, vol. 13, pp. 556–562,
2001.
[2] A. Cichocki, R. Zdunek, A. H. Phan and S.-I. Amari,Nonnegative Matrix and Tensor Factorizations, John
Wiley & Sons, 2009.
[3] F. Sha, Y. Lin, L. K. Saul, D. D. Lee, “Multiplicative
updates for nonnegative quadratic programming,” Neural Computation, vol. 19, pp. 2004–2031, 2007.
[4] N. Gillis and F. Glineur, “Nonnegative factorizationand the maximum edge biclique problem,” ArXiv,
0810.4225, Oct. 2008.
[5] R. Hibi and N. Takahashi, “A modified multiplicative
update algorithm for Euclidean distance-based nonnegative matrix factorization and its global convergence,” Proc. 18th International Conference on Neural
Information Processing, Part-II，pp. 655–662，2011.
[6] W. I. Zangwill, Nonlinear Programming: A Unified
Approach, Prentice-Hall, 1969.
[7] D. G. Luenberger, Linear and Nonlinear Programming, Second Edition, Addison-Wesley Publishing
Company, 1984.

- 434 -