uluwtyflvvu "vuwu‘..-"

 

 

 

 

 

 

I‘-'|de\/| l

 

 

.1
MICHIGA

fit") RARY W W 3. NlImp/If'UTl'fiBS’IT’lVLfR'AR‘Ef
Michgan State ”//I@I’ll£l’£lfllfl/MlfllMal/W

University

 

 

This is to certify that the

dissertation entitled

An Algorithm For Non-Negative Least Error
Minimal Norm Solutions

presented by

Panagiotis V. Nikolopoulos

has been accepted towards fulfillment
of the requirements for

Ph-D- degree in Mathematics

Major professor

Date 7/28/89

M5 U i: an Affirmative Action/Equal Opportunity Institution 0- 12771

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or More one due.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

___________J
——ll—_—_l

MSU Is An Affirmdive Action/Emu Opportunity Institution

 

 

AN ALGORITHM FOR NON—NEGATIVE LEAST ERROR
MINIMAL NORM SOLUTIONS

By

Panagiotis Vasilios Nikolopoulos

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements

for the degree of

DOCTOR OF PHILOSOPHY
Department of Mathematics

1989

ABSTRACT

AN ALGORITHM FOR NON-NEGATIVE LEAST ERROR
MINIMAL NORM SOLUTIONS
By
Panagiotis Vasilios Nik010poulos

In this thesis we consider non-negative solutions of a system of m real

linear equations, Ax = b, in n unknowns which minimize the residual

error when Rm is equipped with a strictly convex norm. Out of these

solutions we seek the one which is of least norm when It“ is equipped with

a strictly convex and smooth norm. An implementable iterative algorithm

accomplishing this is given. The algorithm is globally convergent and it does

not require that a non-negative minimal error solution be found first. As a
special case, we test the algorithm for the tp—norms (l < p < 00).

Numerical results are also included.

ACKNOWLEDGMENTS

I would like to express my sincere thanks to Professor V.P. Sreedharan,
without whose direction and encouragement I would not have written this
thesis. I also thank the other members of my committee, Professors C.
Seebeck, C. Wei], D. Dunninger and J. Plotkin. Finally, Special thanks are
reserved for Cathy Sparks for typing the final manuscript.

TABLE OF CONTENTS

CHAPTER 1 .................................. 1
CHAPTER 2 ................................. 25
CHAPTER 3 ................................. 53
REFERENCES ................................ 76

ii

LIST OF TABLES

Table 1 ..................................... 74
Table 2 ..................................... 75

iii

LIST OF TABLES

Table 1 ..................................... 74
Table 2 ..................................... 75

iii

CHAPTER 1

1.1 INTRODUCTION

In this chapter we assume that the system of m real linear equations
in n unknowns Ax = b has a non—negative solution. We give an
implementable iterative algorithm converging to the least norm || o|| solution
of Ax = b, x 2 0 for a strictly convex norm ||-|| on Rn. This
algorithm is modeled after a similar algorithm in [6]. Before we state the
algorithm we formulate some duality theorems, again analogous to these in
[6]. These theorems will be needed to show that the algorithm is convergent

and is properly formulated.

1.2 NOTATION AND SOME PRELIMINARIES

Let ||-|| be a norm on R", n 2 1 and <-,-> denote the standard
Euclidean inner product, with "'"2’ the corresponding Euclidean length. For
x , y c Rn, we write x 2 y iff xj 2 yj, Vj = 1,...,n where
x = (xl,...,xn) and y = (yl,...,yn), xj, yj c R. The definition of 5 is
now clear. In formulating the duality theorems we will need the well known
notion of the dual norm on Rn: Given the norm ||~|| on R“, we define
the dual norm ||-||' by
(1.2.1) “yII' = max {<x , y>|||x|| = 1, x c 3"}.
Given y ,t 0, we define (see [7], [8]) y' a II-ll—dual and y* a
||o||'—dual by the equations
(1-2-2) lly'll = 1, <y2 y> = IMF.
and
(1.2.3) uy*u' = 1. <y*, y> = My".

The norm ||-|| is said to be strictly convex iff the unit sphere

s = {x c Rnlllxll = 1} has no line segments on it. The norm H." is
said to be smooth iff through each point of unit norm in It", there passes
precisely one hyperplane supporting the closed unit ball
B = {x c Rnlllxll S 1}. One easily sees that if the norm ||o|| is strictly
convex (smooth), then |||| (||-||')—duals are unique and
(1.2.4) x*' = x|||x|l (x'* = x|||x||'), v x s 0.
Furthermore, the map x |-v x' (x |-+ x*) of Rn\{0} into the
||-|| (||-||')—unit Sphere is continuous, and positively homogeneous of degree
zero.

A non—empty convex subset K of It” is said to be a convex cone iff

Ach,Vch and VAZO.

1.3 SOME DUALITY THEORY
Let adln. With the primal problem (P)
(P) min{llx-a|l det“, Ax b. x 2 0}

we associate a "dual" problem (P'):
(P') max {<y.b> — <A’y + ca> Ices“, c 2 0, ymmiIATy + éll' s 1}
where AT denotes the transpose of A.

We have the following basic theorems:

1.3.1 THEOREM. Let ||~|| be any norm on R". Assume that
K = {xcRn|Ax = b, x 2 0} is nonempty. Then the problems (P) and
(P') have the same value.

Proof For any x 2 0 such that Ax = b, Mi“, 6 2 0, ycllm with
IIATy + {II' S 1, we have

<y,b> — <ATy + {,a> = <y,Ax> — <Ary + {,a>
= <ATy,x> — <Ary + £,a>
g <ATy + {,x> — <ATy + €,a>
= <ATy+ €,x—a>

_<_ IIATy + {II' llx - all

(1.3.1.1) g ||x — all.

This proves that value of (P') _<_ value of (P).
Now value of (P) = d(a,K)

(1.3.1.2) = inf {||x — all Ich},

where K = {xdlnle = b, x 2 0}.
By the duality theorem of Nirenberg [4], we have

(1.3.1.3) d(a,K) = max (<z,a> - 0(2)),
IIZII'S1

where o is the support function of the polyhedrally convex set K, i.e.

(1.3.1.4) 0(2) = sup{<z,x> Ich}.
So
(1.3.1.5) d(a,K) = max (<z,a> — sup <z,x>).
”z I) '51 ch
Now
(1.3.1.6) — sup{<z,x>lch} = inf{<-z,x>|Ax = b,x Z 0}.

The standard linear program on the right of the above equation is feasible by
hypothesis. So by the well known strong duality theorem of linear
programming [3],
(1.3.1.7) inf{<-z,x>|Ax = b,x 2 0} = max{<y,b>|ATy 5 —z},
with the convention that maximum over the empty set is we. Rewriting
(1.3.1.7) and combining it with (1.3.1.6) yields

—sup{<z,x>|ch} = max {<y,b>lATy + 5 = —z, chm,

wt”. 5 2 0}-

Inserting this in (1.3.1.5) we get

(1.3.1.8) d(a,K):ll Ilrllax (<z,a> + max{<y,b>|ATy + g” = —z,{ 2 0}).
z '51

Given 2, with ||z||' 5 1, if there does not exist chm, (din, 5 2 0 such
that ATy + 6 = -2, then the linear program occuring in (1.3.1.8) has the
value -00. Since 0 5 d(a,K) < 00, we may therefore consider only 2'3 of
the form

(1.3.1.9) z = —ATy - {, yellm, gen“, 5 2 0, ||z|l' s 1.

From (1.3.1.8), we see that there exists 5, Ilill' S 1, such that

(1.3.1.10) d(a,K) = <§,a> + max{<y,b>|ATy + g = —E, g 2 0}.

By remarks above, 3 yellm and 26R”, 2‘ 2 0 such that

(1.3.1.11) E = —A7‘ — Z

and
(1.3.1.12) d(a,K) = <'z',a> + <y,b>
= — of; + Z,a> + <y,b>
g max{<y,b> - <ATy + £,a>|ycllm, gen”, g 2 o,
IIATy + {II' S 1}
(1.3.1.13) = value of (P').

We have now shown that value of (P) _<_ value of (P') and so the theorem

is completely proved.

REMARK. The easy half in the above theorem, viz: value of
(P') 5 value of (P) will be referred to as the weak duality principle.

1.3.2 THEOREM. Let the norm II” on Rn be strictly convex.
Assume also that K = {xcllnle = b, x 2 0} is nonempty and acRn\K.
Then sees“ solves (P) iff ASE = b, i 2 o and 3mm, gen“, 5 2 o

such that

(1.3.2.1) |lATy + {II' = 1, <y,b> — <ATy + {,a> > 0,
and

(1.3.2.2) SE —a = (<y,b> — <ATy + £,a>)(ATy + 0'.
Furthermore,

(1.3.2.3) <§,§> = o.

ProojI "If" part: We have by (1.3.2.1) and (1.3.2.3)
u; - all = <y,b> — <ATy + 4,»,
which by Theorem 1.3.1 shows that "if - all is the value of (P) and so
i solves (P).
"Only if" part: Let ydlm, g 2 o be a solution of (P'), so that by
Theorem 1.3.1
lli — all = <y,b> — <ATy + {,a> = p > 0.
Now
(1.3.2.4) <ATy + g, i - a> s llATy + 5w ()3: — all = p.
On the other hand,
<ATy + 6, it" — a> = <ATy + 53> - <ATy + £,a>
= <ATy,1't'> + <§,3E> — <ATy + £,a>
= <y,Ai> + <§,SE> - <ATy + £,a>
= <y,b> — <ATy + £,a> + <§,SE>
(1.3.2.5) = p + «53> 2 p,
since both the vectors 6 and i are 2 0. From (1.3.2.4) and (1.3.2.5)
we see that
(1.3.2.6) <ATy + 5, i - a> = p,
and that <£JE> = 0, proving (1.3.2.3). Since llATy + {II' = 1 and
"(x — a)/pl| = 1, we see from (1.3.2.6)
<(i - 80/0, Ary + €> = IIATy + {H'-

In view of the strict convexity of the norm ll-ll, we get
(i - a)/p = (ATy + £)', or x - a = p(ATy + 0', which is (1.3.2.2),
completing the proof of the theorem.

1.3.3. If we assume that the norm ll-ll is both smooth and strictly

convex we can get more symmetric results as stated below.

1.3.4 THEOREM. Let the norm ||-|| be both smooth and strictly
convex. Assume that K = {xcRnle = b, x 2 0} is nonempty and
acRn\K. Then its" solves (P) iff A1? = b, i‘ 2 o and ayes“, gen“,
g 2 0 such that
(1.3.4.1) 11* = ATy + 6,
where u = i — a, and
(1.3.4.2) <§,SE> = 0.

Furthermore, (y,§) solves (P').

Proof "Only if" part: By Theorem 1.3.2, there exists x such that
A} = b, i 2 0 and (y,£) satisfying (1.3.2.1), (1.3.2.2) and (1.3.2.3). By
(1.3.2.2), u = llu||(ATy + £)', so that u* = ATy + 6, due to the
smoothness of ||-||.

"If" part: We shall show that x solves (P) and also (y,§) solves
(P'). Observe that by the strict convexity of the norm ll-ll,

(1.3.4.3) u/llull = n*' = (My + ()2
Now
(1.3.4.4) 1 = llu*ll' = "My + {II'

= <(A’y + 0', A’y + €>-
By (1.3.4.4) and (1.3.4.3) we see that
(1.3.4.5) "u" = <u,ATy + {>

01’

lli — all = (SE - a, ATy + {>
(1.3.4.6) = <y,b> - <Ary + £,a>
due to the calculation in (1.3.2.5) and the fact <§,§> = 0. Equation

(1.3.4.6) in view of Theorem 1.3.1 completes the proof.

1.3.5 COROLLARY. Let x solve (P) under the hypotheses of the
theorem. Then
(1.3.5.1) <y,b> = <n*,sz>.
Proof By (1.3.4.6),
<y,b> = llull + <ATy + £,a>
= <ATy + 5, a + 11>, by (1.3.4.5)
= <Ary + 6, §>

*_
=<11,X>.

1.3.6. The Special case of Theorem 1.3.4 with ll-ll = ll-ll2, the

standard Euclidean norm, is important for later applications. So we record it

explicitly.

1.3.7 THEOREM. Assume that the set K = {xcRnle = b, x 2 0}
is nonempty and that adln\K. Then felt" is the solution of (P), with

H = Il-ll2, iff there edst yen”, ten“, 5 2 0 such that
(1.3.7.1) u = ATy + 5,

where

(1.3.7.2) u = 32 - a,

and

(1.3.7.3) llullg = <y,b> - <u,a>.

Proof By Theorem 1.3.5, SE is the solution of (P) iff there exist
yet“, m", z 2 0 such that u’“ = AT; + z and <y,b> = <n*,§>.
Since M = ll-IIZ, u’“ = u/nuu. Setting y = "his, as = llullZ‘, we see that
(1.3.7.1) and (1.3.7.2) hold and conversely. Also,

<y,b> = <llull'y7,b>
= IIUII <y,b>
= llull <u*,§>, by (1.3.5.1)
= <u,x>
= <u,u + a>,

which is (1.3.7.3).

1.3.8. Theorems 1.3.1, 1.3.2, 1.3.4 and 1.3.6 correspond to Theorems 3.2,
3.4, 3.7 and 3.8 of [6] respectively. In [6] a simple geometric proof of
Theorem 3.8 of [6] was sketched. In the same Spirit, it would be worthwhile,
to give a direct geometric proof of Theorem 1.3.6 without relying on results
for general norms. Let us recall a couple of well known facts.
Fact (i). If K is a nonempty closed convex subset of R“ with MR“,
then itK is the unique point nearest to a in K, for the Euclidean norm
iff
(1.3.8.1) <a - i, x - §> 5 0, thK.
Fact (ii). If K is a convex cone in It“, then its negative polar K° is
defined by
(1.3.3.2) K° = {ycllnl <y,x> g 0, chK}.

It will be convenient to state Theorem 1.3.6 in an equivalent form before

proving it.

1.3.9 THEOREM. Assume that the set K = {xcllnle = b, x 2 0}
is nonempty with 3€Rn\K. Then i solves (P) for the tZ-norm ll-ll2
iff A; = b, i 2 o and ayrsm, as“, g 2 0 such that

(1.3.9.1) 35 — a = My + g,
and
(1.3.9.2) <§,1—t> = 0.

Proof i solves (P) iff icK is the point in K nearest to a, for
the Euclidean norm |l-|l2. By Fact (i), this is the case iff
(1.3.9.3) <a - x, x — i> S 0, chK.

Now suppose that x solves (P). Let .1 = {jt[1,n]|§j = 0} and
(1.3.9.4) H = (kerA) n {vclinlvj 2 0, Vij}.

Due to the fact that xj > 0, Vj¢J and ij = O, Vij, one easily sees that
given vcH, 317 > 0 such that x + nch, and so from (1.3.9.3) we see
that <a — x, nv> 5 0; i.e.

(1.3.9.5) <a - x, v> S 0, chH.

By Fact (ii), this means a — icHo. Again, one easily sees that

(1.3.9.6) H° = (KerA)* + {vcllnlvj = 0, via, yj s o, erJ}.

Since (lterA)l = 1m(AT), it follows that 3chm, cell", 5 2 o, {j = o, Vj¢J
such that

(1.3.9.7) i — a = My + g,

which is (1.3.9.1). Since {j = 0, Vj¢J, (1.3.9.2) also holds.

To prove the converse, assume that A)? = b, i 2 0 and that (1.3.9.1),
(1.3.9.2) hold. We Shall Show that (1.3.9.3) holds chK, which would prove
that x solves (P). Now chK,

<2 — a,x — §> = <Ary + {,x — §>
= <ATy,x — §> + <§,x> - <§,§>

= <y,Ax - A§> + <§,x>

10

= <y,b - b> + <§,x>
= <£,x> 2 0,

which is (1.3.9.3).

1.3.10 REMARK. The condition (1.3.9.2) is equivalent to each of the

following:

(1.3.10.1) <y,b> = <u,§>

and

(1.3.10.2) "on; = <y,b> - <u,a>, where u = i — a.

This is so, Since
<u,§> = <ATy + 53> = <ATy,1—t>
=<y,A§> = <y,b>,
and
2 _ _ _
||ul|2 — <u,u> — <u,x - a>

= <u,§> — <u,a> = <y,b> - <u,a>.

1.3.11 COROLLARY. For the t2—norm, if x,y,£, etc. are as in
Theorem 1.3.9, then (d_ly,d-1{), where d = use - allz, solves the dual
(P') for the tZ-norm i.e.

(P'): max{<z,b> - <ATz + (,a>||lATz + (”2 = 1, zcsm,ccsn,c 2 0}

Proof Due to (1.3.9), ||AT(d—ly) + crlgu2 = 1. By (1.3.10.1) for
u = i — a, <d-ly,b> = d_l<u,x>, whereas by (1.3.9.1)

<AT(d"y) + d“'§,a> = d‘ld — a,a> = d"<u,a>.
Thus,
<d’1y,b> - <AT(d—1y) + d—1§,a> = d-1<u,SE — a> = d,

which completes the proof.

11

1.4 ALGORITHM

We assume b a! 0 and that the system Ax = b, x 2 0 is feasible.
Here then is the algorithm for finding i solving (P)
(P): min{l|x|l|Ax = b, x 2 0}, which corresponds to a = 0 in Section 1.3.

We assume that the norm ll-ll is strictly convex.

1.4.1 ALGORITHM.
Step 1. Fid x0, the solution of the problem

Ax = b, x 2 0, ||x||2 (min).
Set g0 = xo/leoll', .60 = <g0,xo> and k = 0.
Step 2. Define 21k = Bkgl:K and find xk+1 solving the problem

Ax = b, x 2 0, [IX — akll2 (min).
Let uk = xk+1 — ak. If 11k = 0, STOP; xk+1 solves (P), else
proceed.
Step 3. Let 7k = <uk,xk+1>. If 7k S 0, set 5k = flk/(flk — 7k)

and

GO TO Step 5, else set 5k = 1 and proceed.
Step 4. If

7k <ulgk> 2 flkllukll'
set 0k = 1 and GO TO Step 6, else proceed.
Step 5. Find, if exists, akc(0,3k) such that

(akak + (1 - ski/3k)

< (akuk + (1 - ak)gk)', uk — gk>
= (7k " flk)llakuk + (1 - 0981‘".-

(It will be proven that such an ak always exists and it is unique, if
the norm [H] is also smooth).

Step 6. Define

12

gk+l = (akuk + (1 " ak)gk)/llak“k + (1 - “1981‘".
and

4+1 = (ak'rk + (1 - opal/Hake, + (1 — ak)gkll'-
Increase k by l and RETURN to Step 2.

1.4.2 REMARK. As it can easily be seen from the subsequent proof of
convergence of the above algorithm, Step 1 is only a convenient initialization.
In fact, it can be replaced by

Step 1. Pick any g0 such that there are yodlm, {01591, {0 2 0 with

go :2 A‘ry0 + £0, [lgoll' = l and <y0,b> 2 0.

1.5 FEASIBILITY OF THE ALGORITHM
In this section we Show that the various steps in the algorithm are

prOperly formulated.

1.5.1 LEMMA. Let go, etc. be as in Step 1 of the algorithm. Then
Elyodlm, (Odin, £0 2 0 such that
$0 = ATYO + £02 "80". = l
and
SD = <y0,b> > 0.
Proof By Theorem 1.3.9, Bchm, Cell", C 2 0 such that
x0 = A’z + c and <<,x0> = 0. Let yo = z/llxoll' and £0 = C/le0l|'-
By Step I of the algorithm, g0 = x0/llxoll' = A‘ry0 + (0.
Also
2
30 = <30’x0> = "xollg/llxoll' > 0
and

13

= <y0,Ax0> = <y0,b>.
This completes the proof of the Lemma.

1.5.2 LEMMA. In the algorithm Vk 2 1, if “k—l 2; 0, then
aruk_1 + (1 — cz)gk_l # 0, Vac[0,1].
Furthermore, in this case, if we also assume that ak—l has been
determined, then
Bykdlm, 5km“, 5k 2 0 such that
gk = Aryk + (k, llgkll' = 1.
and
16k = <yk,b>.
Proof We Shall prove this lemma by induction on k. Take k = 1.
Since 110 at 0, with ”80W = 1, auo + (1 - a)g0 = 0 cannot hold for
a = 1 or a = 0. So, if Slac[0,l], such that auo + (1 — a)g0 = 0, then
ac(0,1). Assume that such an 0 exists. We see that
"11,113 = uxl - so"; = <x1- a0,u0>
= a"1 (a - 1) <x1 - a0,g0>
= o‘1 (a — 1) (<x1,g0> — <ao,g0>)
a" (a — 1) («1.1190 + 60> - 110),
Since a0 = flogb,
= a" (a - 1) (110 + <x1,£0> - ho),

. T _
Slnce <x1,A y0> — <b,y0>,

= 01—1 (a — l) <xl,£0> S 0,
contradicting our assumption that 110 a! 0.
Since x1 is the solution of the problem
Ax = h, x 2 a. 11x — a0||2 (nun),
by Theorem 1.3.9, azcllm, (can, ( 2 0 such that

14

110 = x1 — a0 = ATz + C and <z,b> = <u0,x1> = 70.
Since auo + (1 - or)g0 t 0, Vacl0,1], and Since Steps 4 and 5 of the
algorithm have determined 010 by assumption, we have
“0'10 + (1 — c10)g0 if 0. So Step 6 is well defined. Define yl, {I by

yl = (“’02 + (1 - 00)Y0)/"aouo + (1 "' “(980“.
and

£1 = (00C + (1 " ao)£0)/"a0“0 + (1 _ 00)g0""
Then £1 2 0, and

Aryl + £1 = (“0‘10 + (1 ' ao)go)/llaou0 + (1 " “(980“.-
Furthermore,

<y1,b> = (ao<z,b> + (1 — c110)<y0,b>)/||arou0 + (1 — ao)y0||'

= 61, by Step 6 of the algorithm.

Now we have verified the lemma for k = 1. For the general index k, the
argument is identical and is obtained from above by Simply replacing yo, {0,
g01"0130 and "1 by yk-l’ {It-1’ gk-l’ uk—l’ flk-l and xk’

reSpectively. This completes the proof of this lemma.

1.5.3 LEMMA. Let u,ycli”, 7,5211 and
Z = {adilau + (l - a)y = 0}. Also let ll-ll be a strictly convex norm

on Rn. Define the function

10(0) = (017 + (1 - (MD/Ilall + (1 - a)YII'

 

 

for acR\Z.

Then, we have for the derivative of (p

(1.5.3.1) io'(a) = 7-fi _ L07+(l-a)fl)<Lau+(l-g)y)',u-y>
llau+(1-a).V||' ||0I11+(l -a))'|l'

for acR\Z.

Now let acll\Z be such that (0(a) > 0.

15

Then we have

(1.5.3.2) If (p'(a) 2 0 then (0(A) 5 (0(0) VA < a, Adl\Z.
(1.5.3.3) If p'(a) 5 0 then tp(A) 5 tp(a) VA > a, Acll\Z.
If the norm [MI is also smooth, then

(1.5.3.4) <p(A) < tp(a) in both (1.5.3.2) and (1.5.3.3).

Proof The proof is a straightforward repetition for the above to of
the proofs of Lemmas 5.3, 5.4, 5.5 and 5.6 in Sreedharan [6]. Note that, as
one easily sees, in Lemma 5.5 of [6] we can replace the assumption that y
and h are linearly independent by the weaker one that both y + ah and
y + Ah are nonzero. We have used this weaker assumption for the above
Lemma. (1.5.3.1) corresponds to relation (5.4.3) of Lemma 5.4 in [6] and
(1.5.3.2), (1.5.3.3) correspond respectively to statements (i) and (ii) of Lemma
5.6 in [6].

1.5.4 LEMMA. Let u,ycltn, 7,5211. Also let M be a strictly
convex norm on It”. Assume that all + (l - a)y t 0, Vac[0,1]. Then
define

(2(a) = (07 + (1- elm/nah + (1 — a)yll' for «10.11-
Also assume that

(p(0) > 0 and p'(0) > 0.
Consider the following algorithm:
(i) If 7 S 0 then 3 = ,6/(6 - 7) and GO TO (iv).

Else proceed.
(ii) 3 = 1
(iii) If

7<U',y> Z flIIUII'
set a = l and STOP. Else proceed.

16

(iv) Find 040,5) such that

(07 + (1 - (1)1040m + (1 - 0)y)',u - y> =

= (7 - [3) "all + (1 - ab’ll'

STOP.
Then this algorithm is well formulated and it produces an 0 which is a
global maximizer of 1p on the interval [0,1]. Moreover, if the norm ll-ll
is also smooth, then 1p has only one global maximizer on [0,1]. If we
replace the assumption (40) > 0 by (40) = 0 and 7 > 0 then
the Lemma is still true.

Proof Since 0u + (1 — 0)y t 0, V0c[0,1], (p is continuous over the
compact interval [0,1]; thus a global maximizer exists. From (1.5.3.1) we see
that tp' is also continuous over [0,1].

It is easy to verify that the following are true: from the hypothesis that
p(0) > 0, which is the same as ,6 > 0, and the definition of (p we have
that

3 540,1] such that 112(5) = 0

iff

’7 S 0.
If this is true, i.e. if 7 5 0, then 5 = fl/(fl - 7) and it is unique. Using
this and (ii), we see that we always have 0 < 5 5 1.

From (1.5.3.1) we get that the relation in (iii) is true iff tp'(1) 2 0
and the relation in (iv) is true iff 1p'(0) = 0.

Note that writing (iii) makes sense because the assumption
0n + (1 - 0)y ,1 0, V0([0,1] guarantees that u ,1 0. Note also that lp'(l)
is defined iff u t 0. Also the relation in (iv) makes sense for all 040,5)
because 0 < 5 $1 and thus 0u + (1 — 0)y # 0. This is the same as
saying that tp'(0) is defined for all 040,5).

17

Using the above facts we can rewrite the algorithm of the above Lemma

as follows:
(i) If exists, then find 540,1] such that (0(5) = 0 and go to (iv).
If there's no such 5, proceed.
(ii) Put 5 = 1
(iii) If 1p'(1) 2 0, then 0 = 1 and STOP. If (p'(1) < 0, proceed.
(iv) Find 040,3 such that
14(0) = 0
and STOP.

We distinguish two cases:
Case 1. Suppose 3540,1] such that (0(5) = 0. Since this 5 is
unique and since (0(0) > 0, then
(1.5.4.1) <p(0) > 0, V0405).
If it were true that
0(0) 2 0, V040,5], then
1;: would be increasing over [0,5] and thus
0 = (0(5) 2 1p(0) > 0 which is a contradiction.
So, 35405] such that
(0(5) < 0.
Since tp'(0) > 0, then
3040,51) such that tp'(0) = 0.
Since 0 5 5, 040,5). By (1.5.4.1) we also have (40) > 0. Now (1.5.3.2)
and (1.5.3.3) of Lemma 1.5.3 imply that this 0 is a global maximizer of <0
on [0,1] and it is unique, if the norm "all is smooth, by (1.5.3.4).
Case 2. Suppose there iS no 540,1] such that (0(5) = 0. Then
5 = 1 and Since (0(0) > 0, we have

(1.5.4.2) (0(0) > o, voc[0,1].

18

Now if tp'(1) < 0, then
3040,1) such that (p'(0) = 0

because 1p'(0) > 0. Also 1p(0) > 0 by (1.5.4.2). AS in Case 1, we now
conclude that this 0 is a global maximizer of (p on [0,1] and it is unique
if the norm ll-ll is smooth.
Now suppose tp'(1) 2 0. From (1.5.4.2) we have (p(1) > 0. Now (1.5.3.2)
of Lemma 1.5.3 implies that 1 is a global maximizer of (0 on [0,1]. If the
norm l|~l| is smooth, then this global maximizer is unique by (1.5.3.4).

Now suppose that (0(0) = 0, i.e. ,6 = 0, and 7 > 0. Then (i) is not
executed and 5 = 1.
Also 1p(0) = 0 and (p(0) > 0, V040,1].
Suppose the criterion of (iii) is satisfied, i.e. (0(1) 2 0. Since (p(l) > 0,
we have that 1 is a global maximizer of (p on [0,1] via (1.5.3.2) of Lemma
1.5.3. If (0'(1) < 0, and Since (0'(0) > 0, then 3040,l) S.t. (0'(0) = 0
and this 0 is a global maximizer of (p on [0,1] via Lemma 1.5.3. This
0 is unique if the norm |l~|l is also smooth via Lemma 1.5.3.

So 0 is picked to be a global maximizer of (p on [0,1] and it is

unique if the norm ll-ll is also smooth, in all cases.

1.5.5 LEMMA. Let k 2 0. Suppose that at the kth iteration of
Algorithm 1.4.1 uk 96 0. Then, by Lemma 1.5.2, the function
me) = (07k + (1- amp/noel, + (1— a)skll' where 71,, (1,,
uk, gk are as in Algorithm 1.4.1, is finite over the interval [0,1] Since the
denominator does not vanish.
Also assume that 6k > 0.
Then,

19

i) the 0k Specified by Algorithm 1.4.1 in the Steps from 3 to 5, is
a global maximizer of (ok on [0,1]. 0k is unique if the norm ll-ll is also
smooth.
ii) flk+1 > flk'
Proof We have (pk(0) = 6k > 0 by assumption.
Also
=n-h<awm
= llukllg > 0 since “It 1: 0 by assumption.
Now (i) follows from Lemma 1.5.4 and Steps 3,4,5 of Algorithm 1.4.1.
Since 0k is a global maximizer of (pk on [0,1], we have
(pk(0k) 2 (pk(0) = 6k; but in addition to this, we know that (4'40) > 0
and thus (pk(0k) > (0k(0) = 6". From Step 6 of Algorithm 1.4.1 we have
that Bk+1 = <0k(0k) and this completes the proof of (ii).

1.5.6 LEMMA. The sequence (6k) generated by Algorithm 1.4.1 iS
positive and strictly increasing.

Proof From Lemma 1.5.5 we have that for uk 11 0, if 6k) 0 then
6k +1 > 6k and thus 6k +1 > 0, too. In other words: 6k > 0 implies
Bk+1 > 0, unless the algorithm is terminated at the kth iteration. From
Lemma 1.5.1 we have 60 > 0. So by induction, the finite or infinite
sequence (61‘) is positive and thus, by Lemma 1.5.5 (ii), it iS also strictly
increasing. So, if it is not a finite sequence, it converges to some limit
which, by Lemma 1.5.2, is less than or equal to the value of problem (P):

min{l|x|l|Ax = b, x 2 0}, or the value of the problem (P') dual
to (P).

20

1.5.7 THEOREM. If “k at the kth iteration of Algorithm 1.4.1
equals zero, then xk+1 solves (P):
min{l|x|l|Ax = b,x 2 0}.
Proof If 11k = 0, then we have by Step 2 of the algorithm,
xk +1 = 6kg]; and x1‘ +1 is feasible for (P).
The last relation via Lemmas 1.5.2, 1.5.5 and 1.5.6 becomes
xk+1 = <yk,b>(ATyk + 6k)" "Aryk '1' 6k". = 1-
Now apply Theorem 1.3.2 for a = 0 to get the result. Take into account
that 6k > 0 by Lemma 1.5.6 and that b at 0 which was assumed in
Section 1.4.

1.6 CONVERGENCE OF THE ALGORITHM

We can now prove convergence of Algorithm 1.4.1.

1.6.1 THEOREM. Assume that the norm Il-ll on It“ is strictly
convex. Then the sequence (xk) generated by Algorithm 1.4.1 either
terminates at or converges to the unique solution of (P) i.e. of the problem
(P): Ax = b, x 2 0, ||xl| (min).

Proof If Algorithm 1.4.1 terminates at xk then uk_1 = 0, in which
event this theorem reduces to Theorem 1.5.7. So consider the case when we
have a genuine infinite sequence (xk). We Shall first Show that the
sequence (uk) constructed in Algorithm 1.4.1 converges to zero.

Denote by d the value of (P). Then 6k = <yk,b> S d, Vk. By
Lemma 1.5.6 (6k) is a strictly increasing sequence, and so 6k l 6 S d.

A

Fix x20, with Ax=b. We have

llxk+1ll2 S "1‘1”.1 - 3kll2 'l‘ "akllg
5 ix - 1k", + llakllz

21

s "all, + 214112
= Ih‘tu2 + 2111.15.11,
s "Jen, + 2111111121111
= is", + 24M.
This shows that the sequence (xk) is bounded.
It follows that the sequence uk = xk+1 - a1‘ is also bounded. So if (uk)
does not converge to zero, there is a subsequence (uk.) of (uk)
converging to u 9% 0.
Observe that
”“11”; = <xk+1 ‘ he“?
= <xk+1’“k> - <ak,uk>
(1.6.1.1) = 7k - flk<gk’uk>'
Due to the boundedness of (71‘) and (gk), we can pass to a further
subsequence, again denoted by (k') such that 7k. -1 7 and gk. -1 g.
Since llgkll' = 1, Vk, llgll' = 1 and by the continuity of the map
z l" z' on lin\{0}, we get from (1.6.1.1), as k' -1 oo,
(1.6.1.2) Hull; = 7 - fl <g',u>.

We now distinguish two cases.

Case 1. There exist an infinity of indices k' for which Step 5 is
executed. Denote this subsequence by (k') again. Furthermore we may
assume that the sequence (0k.) iS such that 0k. -+ 040,1]. Let us also
assume that 0n + (1 — 0)g (1 0. We Shall take care of the possibility
0n + (l — 0)g = 0 Shortly. Using Step .5 of the algorithm and allowing
k' -1 on, since 0u + (1 - 0)g t 0, (0uk. + (1 — 0)gk.)' -1 (0n + (1 — 0)g)'.
This yields the equation
(1.6.1.3) (07 + (l - 0W) < (0u + (1 - 0)g)', u — g>

= ('7 - fl) llml + (1 - a)sll'-

22

Also by Step 6 of the algorithm

(1.6.1.4) 6||0u + (1 - 0)gll' = 07 + (l — 0)6
Since 0n + (l - 0)g at 0, combining (1.6.1.3) and (1.6.1.4), we get
(1.6.1.5) fl <(0u + (1 - 0)g)', u - g> = 7 — 6.

Since <(0u + (1 — 0)g)', g + 0(u - g)> = ||0u + (1 —0)gll', we have
(1.6.1.6) 0 <(0u + (l - 0)g)',u - g> = |l0u + (1 - 0)gll'
— <(0u + (1 - 0)g)',g>.
Combining (1.6.1.6), (1.6.1.5) and (1.6.1.4) we get the equation

(1.6.1.7) fl = fl <(0u + (1 - 0)g)',g>,

i.e.

(1.6.1.8) <(0u + (1 - 0)g)',g> = 1, Since 6 > 0.

Since llgll' = l, with the norm |||| strictly convex, (1.6.1.8) imples that
(1.6.1.9) (0n + (1 - 0)g)' = g'.

Inserting this in (1.6.1.5) gives us the equation

(1.6.1.10) fl <g', u — g> = 7 — 6,

i.e.

(1.6.1.11) ,6 <g',u> = 7, Since <g',g> = 1,

which in view of (1.6.1.2), implies u = 0, a contradiction.

Now suppose that 0n + (1- 0)g = 0. Since g 11 0, 0 91 0. So
u = 0—1(0 -— 1)g. By Step 6 of the algorithm

3k'+1""lr'“k' + (1 ‘ “k'lglr'll' = ak'7k' + (1 + “101310

Allowing k' -+ no, we get
(1.6.1.12) 07 + (1 — 0))6 = 0.
Writing u = 0—1(0 - 1)g in equation (1.6.1.2) yields
(1.6.1.13) nun; = 7 - sot-101 — 1) = o, by (1.6.1.12),

once more a contradiction.

23

Case 2. There exist an infinity of indices k' for which Step 4 of the
algorithm is answered affirmatively. Passing to a subsequence, again denoted
(k'), we assume this to be the case for all k'. Then by Step 6 of the
althorithm,

flk'+l = 7ki/"11k1ll'-
Since (6k) is an increasing sequence with limit 6 > 0, (61‘. +1) -1 B. Let
7k. -1 7. Then 7 > 0 and
(1.6.1.14) 7 = Bllull'.
Due to Step 4

7k' < “fatgko Z flkllluklll'!
which in the limit yields

7 <u',g> 2 flIIUII' = 7-
Since 7 > 0, this shows that <u',g> 2 1. But since llgll' = 1 with
llu'll = l, we conclude that <u',g> = 1 and hence u' = g'. Using this
in (1.6.1.2) we get

Hung = 7 - fl<U',U>
(1.6.1.15) = 7 - fillull' = 0, by (1.6.1.14)
contradicting the assumption u (t 0. So we have shown that in all cases
uk -1 0.

To Show that (xk) converges to the solution of (P), we first Show
that every cluster point i of (xk) is a solution of (P). Then Since
solutions of (P) are unique, with (xk) bounded, we can conclude that the
sequence (xk) converges to the unique solution 5 of problem (P). Let
then i be any cluster point of (xk). Then there is a subsequence (k')
such that xk.+1 -1 5. Recall that by Lemmas 1.5.2, 1.5.5 and 1.5.6
3ykcllm, kelin, {k 2 0 such that
(1.6.1.16) g], = Myk + 6.. Ilgkll' = 1,

24

and
(1.6.1.17) 6k = <yk,b>, Vk.
Furthermore, (6k) converges to 6 > 0.
By passing to a further subsequence of (k'), if necessary, and denoting
the new subsequence again by (k'), we can assume that

gk. -1 g, llgll' = 1. By Step 2 of the algorithm 11k = xk+l - ak, and so

(1.6.1.18) xk'+1 = 111‘. + 81‘. = 11k. + flklg'k'.
Allowing k' a 00, due to the strict convexity of the norm II-Il, we get
(1.6.1.19) ii = 0g, Ilgll' = 1.

Since Axk+1 = b, with xk+1 2 0, Vk, we get A5 = b, i 2 0.

If yeRm and gal”, (,1 2 0 is such that llA’y + {Ir 5 1, by the
weak duality principle,
(1.6.1.20) <y,b> S Hill = a, by (1.6.1.19).
But as observed above, 6 > 0 is the limit of the sequence (<yk,b>),
ykelim, 5km“, 5k 2 0, ||ATyk + cku' = 1. So equality holds in (1.6.1.20),
showing that i is a solution of (P), thus completing the proof of the

theorem.

CHAPTER 2

2.1 INTRODUCTION

In this chapter we assume that the system of m real linear equations
in n unknowns Ax = b has a non-negative solution. We give another
implementable iterative algorithm converging to the least norm ll - ll solution
of Ax = b, x 2 0 for a strictly convex norm Il-ll on It”. This
algorithm is given as a Special case of a more general algorithm and it is
analogous to the one of Chapter 1, but it is never used for actually solving
the above problem since the algorithm of Chapter 1 is a better algorithm for
this purpose. We include it because the theorem about its convergence will
be heavily used in Chapter 3 where we prove the convergence of a more
general algorithm. Some Lemmas and Definitions, which will be used in

Chapter 3, are also given.

2.2 NOTATION AND SOME PRELIMINARIES
Besides the notation in Section 1.2 we also need the following:
A convex polytope in Rn is the convex hull of a finite (at least one)
number of points in It“.
Let C be a convex cone in R“. Then its negative polar, denoted by
0°, iS defined by
Co = {yelln|<y,x> 5 0, VxeC}.
A finitely generated convex cone in Rn is a set of the form
{A1x1+...+AmxmlAi 2 0, V i = 1,...,m},
where xieltn, V i = 1,...,m. A finitely generated convex cone is a convex

cone. We also define It: by 11: = {xellnlx 2 0}.

25

26

We Shall also use the symbol :=. Thus x:= y will mean x is defined

by y.

2.3 SOME DUALITY THEORY

Let K: = {xcRnle = b, x 2 0}. AS already stated, we have assumed
that K is non-empty. Then, according to Theorem 19.1 in [5], K is the
sum of a convex polytOpe P and a finitely generated convex cone C. We
have the following lemma.

2.3.1 LEMMA. Let K = P + C with K, P and C as above.
Then C = (KerA) n Iii, where KerA is the kernel of A. This shows
that in the P + C-representation of K, C is unique and independent of
b.

Proof Let peP and ceC; then p + Ac 6 P + C = K, VA 2 0
and thus peK and p + c e K. By the definition of K we have
(2.3.1.1) Ap = A(p+c) = b
and
(2.3.1.2) p + Ac 2 0, VA 2 0.

(2.3.1.1) implies ceKerA and (2.3.1.2) implies c 2 0. So, C is a subset
of (KerA) 0 R2.

Conversely, let k4KerA) n It: and peP. Then peK = P + C. Let
A > 0. pcK implies Ap = b, p 2 0. Then p + Ak 2 0 and
A(p+Ak)=Ap=b andthus p+AktK,VA>0. Since K=P+C
we see that 3 pAeP, cAeC such that p + Ak = pA + CA or

C
D-PA=CA-x\k=A(-:--k). Letting 14+... weseethat

c c
A(—:- - k) is bounded and thus —)' - k has to go to zero. Since
A

27

0
fi 6 C, VA > 0, we have that keC = C because a finitely generated

convex cone is closed. This completes the proof.

Let us denote by F the negative of the negative polar of the above
cone C, i.e. F: = - C°. Note that
F = — (KerA 0 [135°
= - (lmA’ + 113 ) = ImAT + II:
= {A’y + (Iydim. 011“. c 2 0}
and thus F at {0}. We have the following lemma.

2.3.2 LEMMA. Assume that K: = {xellnle = b, x 2 0} is
non-empty. Then, the inf{<y,x>|xeK} is finite, i.e. it is not — no, if and
only if yeF, in which case the infimum is attained.

Proof Let P,C as in Lemma 2.3.1. Let yell“. Let 01 and 02
be real numbers such that

- on < 02 g <y,p> 5 01 < +oo, VpcP.
We have,
01 + inf{<y,c>|ctC} = inf {01 + <y,c>lceC}
2 inf {<y,p+c>|peP,ccC}
= inf {<y,x>|xeK}
2 inf {02 + <y,c>lceC}
= 02 + inf{<y,c>lceC}.
From these relations, it is easy to see that
inf{<y,x>|ch} is finite, i.e. it is not -oo, if and only if

inf{ <y,c> lceC} is finite.

28

Because C is a cone, we have that
inf{<y,c>|ceC} is finite if and only if <y,c> 2 0, VceC, i.e.
if and only if yeF = - Co.
Whenever the infimum is finite, then due to the polyhedral convexity of

the set K, we see that the infimum is actually attained.

2.3.3. Let M be a norm on s“ and let acRn. With the "primal"
problem (P)

(P) min{llx-alllxdln, Ax = b, x 2 0}
we associate a "dual" problem (P')
(P') max{-<y,a> + min{<y,x>|xelln,Ax = b, x 2 0}]ydln, ||y||' = 1, yeF}.
Note that the objective function of (P') makes sense for yeF because of

Lemma 2.3.2. Now we have the following basic theorem.

2.3.4 THEOREM. Let "all be any norm on ll“ and adln.
Assume that K: = {xcRnle = b, x 2 0} is non-empty and that a¢K.
Then the above problems (P) and (P') have the same value.

Proof The value of (P) equals inf{llx—alllch} because K is a
non—empty closed set and the objective function has non—negative values: so
the inf is min. Now from Nirenberg [4, page 39] we have, since K iS
convex,

value of (P) = II llrllax (<y,a> - sup{<y,x>lxeK})
Y 51

= max (<y,a> + inf{<-y,x>|ch})
"1’" '.<.1

= max (<—y,a> + inf{<y,x>|ch})
llyll'sl

29

= max (<—y,a> + min{(y,x>lxeK}) by

llyll'sl

yeF
Lemma 2.3.2,
(2.3.4.1) = <—y,a> + min{<§,x>|xeK},
for some 36F. ||§||' S 1,

< - —_y—, a) + min{< —_L, x>|xeK} because
Ilyll' llyll'
a¢K and so the value of (P) is greater than zero,

IA

5 max (<—y,a> + min{<y,x>|xeK})
llyll '=l
yeF

S max (<-y,a> + min{<y,x>|xeK})
llyll '51
yeF
and now the result clearly follows.

2.3.5. i) The part of Theorem 2.3.4 stating that the value of (P')
is not greater than the value of (P) will be referred to as the weak duality
principle. The proof of this is easy and it does not invoke any duality
theorems as the one in Nirenberg [4].

ii) If we omit the condition a¢K in Theorem 2.3.4, then the
theorem is still true if we modify (P') Slightly, namely

(P') max{<-y,a> + min{<y,x>|xdln, Ax = b}|yeF, llle' 5 1}.

This is clear from (2.3.4.1).

2.3.6 THEOREM. Let the norm ll-ll on Rn be strictly convex and
let adln. Assume that K: = {xeRnle = b, x 2 0} is non—empty and
that acR“\K. Then its“ solves (P) if and only if ASE = b, a? 2 0

30

and 3 yell”, llyll' = 1 such that the following are true:

(2.3.6.1) — <y,a> + min{<y,x>|ch} > 0
and
(2.3.6.2) i — a = (—<y,a> + min{<y,x>|ch})y'.

Proof "If" part: Since (2.3.6.1) is true, then, by Lemma 2.3.2, ycF.
By (2.3.6.2) and (2.3.6.1) we get
ll; - all = - <y,a> + min{<y,x>|xeK}.
Now the weak duality principle implies that i solves (P) and y solves
(P').
"Only if" part: Let i solve (P) and y solve (P'). By Theorem
2.3.4, [If — all = <—y,a> + min{<y,x>|ch}. Note that

 

<§ - a,y> 2 - <y,a> + min{<y,x>|xeK} because icK
= ”3? — all > 0.
So,
i—a
_ 1 y> 2 1 = M'-
llx-all
Since the reverse inequality is also satisfied and the norm ll-ll is strictly

convex, we get

i—a
Ili-all

This completes the proof.

 

= y' and then (2.3.6.2) clearly follows.

2.3.7. In proving Theorem 2.3.8 we will use (1.3.8.1), which may be
rewritten as:
If K is a non—empty closed convex subset of 3" and ask“, then felt“
is the unique point in K nearest to a for the Euclidean norm if and only
if 56K and

(2.3.7.1) <3? — a,§> 5 <5 — a,x>, VxeK

31

01'

(2.3.7.2) <5 — a5?) = min{<x' — a,x>lxeK}.

2.3.8 THEOREM. Let all”. Assume that the set
K: = {xcllnle = b, x 2 0} is non—empty. Then SEelln solves (P) for

the Euclidean norm ||-|l2 if and only if A5 = b, i 2 0 and the following
relation is true

(2.3.3.1) u; -— an; = - <as‘t - a> + min{<§ - a,x>le = b, x 2 0}.
In the case when this is true, we have i - aeF. Note that we can replace
(2.3.8.1) by

(2.3.8.2) <5 — a,3E> = min{<§ - a,x>le = b, x 2 0}.

Proof We can see that (2.3.8.1) and (2.3.8.2) are identical by writing
lli — allg = <5 - a,i - a>. Now the theorem immediately follows from
2.3.7. Finally, if if solves (P) for the Euclidean norm, then i — aeF
because of Lemma 2.3.2 and the fact that

min{<x' — a,x>le = b, x 2 0} is finite.

2.4 ALGORITHMS AND FEASIBILITY

Let "all be a strictly convex norm on It”.

Let bke{Ax|xcR_':_}, Vk 2 0, with lim bk = h. Then be{Ax|xeR3_}
too, because any finitely generated convex cone is closed (see Theorem 19.1 in
[5]). Now consider the following Algorithm, which is an infinite one, Since

there are no stopping criteria:

2.4.1 ALGORITHM.
Step 0. Let goal“ be such that gOeF and llgoll' = 1. Recalling

the definition of F, which is given following Lemma 2.3.1, we see that such

32

g0 exists since F is a cone not equal to {0}. Put k = 0.
Step 1. Calculate
pk: = min{<gk,x>|Ax = bk’ x 2 0}.
If pk 2 0, put
yk: = gk and 6k: = pk and GO TO STEP 3.
If pk < 0, proceed.
Step 2. Pick any yk such that
yktF, Ilykll' = 1 and
6k: = min{<yk,x>|Ax = bk’ x 2 0} 2 0.
(A way of doing this is the following:
Let zk be the solution of the problem
Ax = bk’ x 2 0, llxll2 (min).
By Theorem 2.3.8 we have zkeF and
(2.4.1.1) nakug = nlin{<zk,x>|Ax = bk, x 2 0}.
Let yk: = zk/llzkll' and
11k: = Ilzkllg/uzku').
Steps 3 through 10 calculate gk+1 from yk. Note that for the already
computed yk and 6k we have
6k = n1in{<yk,x>|Ax = bk, x 2 0} 2 0.
Step 3. Let ak: = flkyk
and let xk be the solution of the problem
Ax = bk’ x 2 0, "x — akll2 (min).
Let uk: = xk - ak.
Step 4. If 11k = 0, then put 7k: = 0, 0k: = 0, gk+1: = yk,
increment k by 1 and RETURN TO Step 1, else proceed.
Step 5. Let 7k: = <uk,xk>. Note that 7k = "11k"; + <uk,ak>.
Note also that by Theorem 2.3.8 we have ukcF and

33

(2.4.1.2) 7k = min{(uk,x>|Ax = bk’ x 2 0}.
Step 6. If 7k S 0, then 5k: = 6k/(6k-7k) and GO TO Step 9,
else proceed.
Step 7. 5k: = 1.
Step 8. If
7k <Ufpyk> 2 Bkllukll',
then 0k: = l and GO TO Step 10, else proceed.
Step 9. Find 0k in the interval (0,5k) such that
(ak7k + (1 " 0196],) < (akuk + (1 ' ak)yk)'3 11k " YR)
= (7k ' 'Bk) llakuk + (1 ' ak)yk""
It will be Shown that such an 0k exists. 0k is unique if the norm IN]
is also smooth.
Step 10. Let
gk+f = (akuk + (1 ' ak)yk)/llakuk 'l’ (1 " akb’kll't
Increment k by 1 and RETURN TO Step I.

REMARK. Note that Step 2 makes sense: suppose that bk = 0.
Then
pk = min{<x,gk>|Ax = 0, x20} 5 0 by taking x = 0.
If 3 x, Ax = 0, x 2 0 such that <x,gk> < 0 then
inf{<x,gk>|Ax = 0, x 2 0} = — co, by taking
Ax, A -+ + on. But Since gkeF, pk 2 0. So finally pk = 0 and
after this we see that Step 2 is skipped and
xk = 0, gk+1 = yk = gk. So whenever Step 2 is executed, we have
bkfo andthus zkato.

34

2.4.2. We consider the following algorithm which is just Algorithm 2.4.1
for the case when bk = b, Vk = 0,1,.... We are assuming that
bclelxcRn,x 2 0}. Also, the norm [H] on It” is assumed strictly
convex. Everything that is valid for Algorithm 2.4.1 is valid for the

following algorithm too, but not vice versa.

2.4.3 ALGORITHM.
In Algorithm 2.4.1 replace bk by b, Vk = 0,1,... and zk by z, Vk
= 0,1,... where z is the solution of the problem

Ax = b, x 2 0, llxll2 (min).
Now we deal with the feasibility of Algorithm 2.4.1.

2.4.4 LEMMA. Suppose that Algorithm 2.4.1 has been able to reach its
kth iteration cycle, k 2 0, having produced a gk such that gkeF and
llgkll' = 1. Then all Steps from 1 through 10 are executable and gk+1
will be calculated such that gk-H‘F’ llgk+1l|' = 1. If the uk of Step 3
is nonzero, then uk and yk are linearly independent and we can define
the function

vkte) = (07k + (1 — twp/netk + (1 — a)ykll' for «[0,1],
and the 0k which is calculated in Steps 6 through .9 is a global maximizer
of (pk on [0,1]. 01‘ is unique if the norm ||-|| is also smooth.

Proof From the Algorithm, we can see that Steps 1 and 2 are
executable—note that pk makes sense because gkeF by assumption—and
a yk will be produced such that llykll' = 1. Also, we will have ykcF
because gkeF by assumption, and zkeF by Step 2. Note that we always

35

have 6k = min{<yk,x>le = bk’ x 2 0} 2 0 and
A. 2 11.-

Now assume uk = Ayk for some real number A. By Step 5, we
have
(2.4.4.1) llukllg + <uk,ak> = min{<uk,x> le = bk’ x 2 0}.
Using Step 3 and the assumption “k = Ayk, the last relation becomes

A , for A 2 0
42114113 +1111]; flk
A max{<yk,x>le = bk’ x 2 0}, for A < 0
5 A 6k.
So, A2||yk||§ g 0 which implies that A = 0 i.e. 11k = 0. So, if
uk 31 0 then yk and “k are linearly independent and so (pk can be
defined. Note that (pk(0) = 6k 2 0 and, by (1.5.3.1),
(2.4.4.2) (01"(0) = 7k - 6k <“k’yk> = 7k - <uk,ak> = llukllg > 0.
Now apply Lemma 1.5.4 to see that Steps 6 through 9 are pr0perly
formulated and 0k iS a global maximizer of (pk on [0,1]. 0k is unique
if the norm ll-ll is also smooth. Note that if 6k = 0, then 0k = 0
and thus 7k = llukllg > 0 which makes Lemma 1.5.4 applicable.

Now it is clear that the Algorithm will produce a gk+1 such that
||gk+1||' = 1, Since all Steps are well-formulated. Note also that gk+1eF,
Since ykeF and ukeF.

Also, we have for “k at 0

min{<gk+1,x>le = bk’ x 2 0} 2 (pk(0k)
(2.4.4.3) > (0k(0) = 6k 2 0, Since
(pl'((0) > 0. Also min{<gk+l,x>|Ax = bk’ x 2 0} 2 (4(0) = 7k/llukll'.
If uk = 0,
(2.4.4.4) min{<gk+1,x>|Ax = bk, x 2 0} = 51r-

So, we always have

(2.4.4.5) min{<gk+1,x>|Ax = bk’ x 2 0} 2 6k 2 0
and
(2.4.4.6) llukll'min{<gk+1,x>|Ax = bk,x 2 0} 2 7k(if uk=0,7k = 0).

2.4.5 LEMMA. Algorithm 2.4.1 is feasible and it is generating infinite

sequences (gk), (yk) such that
gk‘Fi ”gkll' = 19 YRCF’ "Ykll' = 1’ Vk = 0,1,29"”
Proof Follows by a simple induction argument using Lemma 2.4.4 and

Step 0 of the Algorithm.

2.4.6. The sequence (6k), k 2 0, generated by Algorithm 2.4.1 need not

be increasing.

2.4.7. In practice, in order to initialize, we can replace Step 0 of
Algorithm 2.4.1 with the following Steps 0, 01, 02.

Step 0. k = 0.

X
0 , where x0 is the solution of

llxoll'

 

Step 01. If bk 4 0, let go: =

the problem
AX = bk’ x 2 0: “xllg (min),
and GO TO Step 1, else proceed.
Step 02. Let xk: = 0, increment k by 1 and RETURN TO Step
01.

2.4.8. From Steps 1 and 2 of Algorithm 2.4.1, we see that if at some
stage pk < 0, then gk is thrown away and the Algorithm restarts at this

37

point, in the sense that no previous information is used except for the
current bk‘ However, the previous information is used in the following

variation of Algorithm 2.4.1.

2.4.9 ALGORITHM.
All the hypotheses of Algorithm 2.4.1 are assumed here also.
Steps 1 through Ie calculate yk from gk and bk’
Step 0. as in 2.4.1.
Step 1. as in 2.4.1.
Step Ia. Let Zk be the solution of

Ax = bk’ x 2 0, ||xl|2 (min).
Step 11. 11 pk s "21."; < 2;. gk>lllzkll',
then put

4: = 0. ykz = zk/Ilzkll'. 41.: = IIzkIIg/IIzkII'
and GO TO Step 3, else proceed.

“ 2 2
Step It. ck: = llzkllg/(llzkllz - IIzkII'pk).

Step 1d. Find 0k in (0,5k) such that

 

 

   

      

2
. * "zkllg . Zk
(ep+<1-e) )<(eg +11 .2-
"1‘ k llzkll' H II kll' 1‘ llzkll'
_zII II2 zk
=( k?) II akgk+ (1 kl —7||'
II kII llzkll

It will be shown that such an 0k exists and 0k is unique, if the norm
ll-ll is also smooth.

Step 1e. Let

38

z A A g
k zk
+ akgk)/ll(1 " 0k) — akgkll'-

y = = ((1 - it )
k " llzkll' llzkll'

Step 2. Calculate
6k: = min{<yk,x>le = bk’ x 2 0}.
Steps 3 through 10 are the same as in 2.4.1.
Now we deal with the feasibility of Algorithm 2.4.9.

2.4.10 LEMMA. Suppose that Algorithm 2.4.9 has been able to reach
its kth iteration cycle, k 2 0, and that gk has thus been computed so
that gkeF. Suppose pk < 0; if zk and gk are linearly dependent ,
then the criterion of Step 1b is answered affirmatively.

Proof First note that pk makes sense, since gkeF by assumption.
Suppose gk = Azk for some real number A. Using Step Ia and relation
(2.4.1.1) which is still valid, we see that the criterion of Step 1b checks if

min{A < zk,x>|Ax = bk, x 2 0} _<_ Allzkllg
=A min {<zk,x>|Ax = bk’ x 2 0}.
This is clearly true for A 2 0 as equality. If A < 0, the left hand side
becomes
A max {<zk,x>|Ax = bk’ x 2 0} and the above relation is again

found to be true.

2.4.11 LEMMA. Suppose that Algorithm 2.4.9 has been able to reach
its kth iteration cycle, k 2 0, and that gk has thus been computed so
that gkeF and llgkll' = 1. Also assume that pk < 0 and gk, zk are
linearly independent. Then, defining

. II II2
eke) = ((1 - e 3—2 + ark)/II(1 - a) -Z"— + askll'

Ilzkll' llzkll'

39

for 040,1], we have that

Steps Ib through 1d of Algorithm 2.4.9 are pr0perly formulated and the
resulting 0k is a global maximizer of wk on [0,1]. 0k is unique if the
norm ll'll is also smooth.

Proof (pk is clearly defined because the denominator never vanishes as
a result of the linear independence assumption, and also because pk makes
sense as a result of the gkeF assumption. Note that 142140) > 0. We can
easily check that the following is true by referring to relation (1.5.3.1): The
Criterion of Step 1b is satisfied if and only if (619(0) 5 0. If this criterion
is satisfied, then by (1.5.3.3) we get that 0k = 0 is a global maximizer of
(pk on [0,1]. 0k is unique if the norm ll-|| is also smooth by (1.5.3.4).
When the criterion of Step 10 is true, we put yk = zk/llzkll' which is the
same as Step 16 for 0k = 0.

If the Criterion of Step 1b is not satisfied, then (pk)'(0) > 0 and it is
clear that Steps 1c and 1d are pr0perly formulated and they produce an 5k
with the pr0perties stated, by referring to Lemma 1.5.4 and noting that pk
< 0.

From the above, it is clear that a yk iS produced such that
ykeF—because zk and gkeF—and |lykl|' = 1. Thus the 6k of Step 2

makes sense, since ykcF. From Step Is, which is valid even if 0k = 0

and Step 2 we get

Z A
k
“(1 ‘ 0k) —llzk“' + akgkll' flk 2

(1-0k)
"Zkll '

 

2 min{<zk,x>|Ax = bk’ x 2 0} +

+ 0k min {<gk,x>|Ax = bk’ x 2 0}.

40

But this becomes
'Bk 2 1Malt)

 

2
(2.4.11.1) 2 (4km) = "2""2
Ilzkll'
Also, 6k 2 (pk(0k)
(2.4.11.2) 2 (4k (1) = pk.

2.4.12. At the kth iteration cycle of Algorithm 2.4.9, assuming
pk < 0, we have the relations
11,, 2 IIzkIIgIIIzkII' > o and 4,214,.
If zk, gk are linearly independent, these are just (2.4.11.1), (2.4.11.2). If
they are linearly dependent, then
14. = IIzkIIgIIIzkII' and by Step 11,
pk s 3,, < 2,; . gk> s hkllzln 1ng1' = 4.-

Note that the relations 6k 2 pk and 6k 2 0 are true even if

pk20.

2.4.13. Lemmas 2.4.10, 2.4.11 and 2.4.4 Show that Algorithm 2.4.9 is

feasible.

2.4.14. Now that we know that the Algorithms are feasible, we see that
the assumption of Lemmas 2.4.4, 2.4.10 and 2.4.11 that "the Algorithm has
reached its kth iteration cycle with a gk computed such that llgkll' = 1,

gkeF ", is always true.

41

2.5 CONVERGENCE OF ALGORITHM 2.4.3

In this section we are still assuming that [MI is a strictly convex norm
on s" and that be{Ax|xeRn, x 2 0}. We prove that Algorithm 2.4.3
converges to the solution 5 of the problem
(Po)
Note that Algorithm 2.4.3 is infinite because Algorithm 2.4.1 is. The

Ax = b, x 2 0, |lx|l (min).
assumptions regarding Algorithm 2.4.1 are the same as those in Section 2.4.

2.5.1 LEMMA. Consider the functions
fl(c,d): = min{<c,x>|Ax = d, x 2 0}
over Fx{AxlxeRn, x 2 0} and

f2(a,d): = min{llx — all2|Ax = d, x 2 0}
over Rnx{Ax|xelln, x 2 0}.
Then f1, f2 are continuous over their respective domains.

Proof For the continuity of f1 we refer to [1], [9]. Now we prove
that f2 is continuous. Let the sequences (ak) and (dk) be such that
ak .. a and dk a d, where ak, aelln and dk, de{AxlxeRn, x 2 0}. Let
xk be the solution of the problem

Ax = dk’ x 2 0, llx — akll2 (min)
and thus llxk — akll2 = 2(ak,dk).
From 2.3.5 ii) we have that 3 ykeF, llykll2 5 1 such that
(2.5.1.1) 'le — akll2 = <-yk,ak> + min{<yk,x>|Ax = dk’ x 2 0}.
Since (ak), (yk), (dk) are bounded and the functions fl and <~,-> are
continuous, we get that the right hand Side of (2.5.1.1) is bounded. Since

llxkll2 S llxk — akll2 + llakll2, the sequence (xk) is bounded.

42

Now let xk. -t 5. By taking further subsequences, we can assume that
J

ykj " Y-
Taking limits in (2.5.1.1) we get
I]? — all2 = <—y,a> + min{<y,x>|Ax = d, x 2 0}
with ycF, ll'yll2 S 1 and also A3? = d, i 2 0. In view of 2.3.5 ii), these
relations imply that i solves the problem
Ax = d, x 2 0, llx - all2 (min)
and thus lli — all2 = 2(a,d). Since such a solution is unique, we have
(2.5.1.2) lim xk = K
and thus for k -1 oo,
lim f2(ak,dk) = lim llxk — akll2 = II} — all2 = 2(a,d)

which completes the proof that the function f2 is continuous.

2.5.2. Let f3(a,d) be the minimizer of the problem
Ax = d, x 2 0, llx - all2 (min)
where aelin and de{Ax|x 2 0}. f3(a,d) is, of course, a vector in R".
Then, due to (2.5.1.2), f3 is a continuous function of

Rnx{Axlx 2 0} into 11".

2.5.3 REMARK. Referring to Algorithm 2.4.1, the following are true
because of Lemma 2.5.1:
(61‘) is bounded, since (yk) and (bk) are.
(ak) is bounded, Since (6k) is.
(uk) is bounded, since (bk) and (ak) are.
(xk) is bounded, Since (uk) and (ak) are.
(7k) is bounded, since (uk) and (xk) are.

43

(pk) is bounded, since (bk) and (gk) are.
In the same fashion, all sequences appearing in Algorithm 2.4.9 are
bounded, too.

2.5.4 LEMMA. Consider Algorithm 2.4.1 for a strictly convex norm
||-|| on R“ and

bk ({Axlxdli}, k 2 0, with lim bk = b, b at 0. Assume that the
algorithm is initiated with a given goeF with ||g0l|' = 1. Then,

(i) Every cluster point of (pk), k 2 0, is greater than zero.

(ii) 3 k0 such that

pk > 0, V k 2 k0.

k0 depends on (bk)’ k 2 0, and g0.

Proof Suppose (i) is not true. Then there is a subsequence such that

(2.5.4.1) lim pk. = lim min{<gk.,x>le = bk.’ x 2 0} S 0.
J J J
From (2.4.4.5) and (2.4.4.6) we get

for all kj 2 1, and

2
= ”U I] + <u _ , a _ > for all k. 2 1.
(kj)‘1 2 (kj) 1 (kj) 1 J

By taking further subsequences, we can assume that

gk. -1 g. Note that ch, Since F is a closed set.
I
By allowing j -1 oo in (2.5.4.2), we get that

lim min{<gk.,x>|Ax = b(k.)-l’ x 2 0} 2 0
J J
= min{<g,x>le = b, x 2 0}

= lim pk. by (2.5.4.1) S 0
J

44

and so
(2.5.4.4) lim pk. = 0.
J
By (2.5.4.4) and (2.5.4.2),
lim 3 = 0 as j 4 00.

k. -—1 ’

1 ,)
But then
(2.5.4.5) a(kj)—1 = fl(kj)_l yzkj)-l 4 0, as j 'l 00.
Moving <u(k.)-1’ 3(k.)—1> to the left hand Side of (2.5.4.3) and then

I J
taking the lim as j -1 co, we get
limu _=0,aSj-100.

(kj) 1
For this conclusion we have used (2.5.4.4), (2.5.4.5) and the fact that
(“(k.)-l) is a bounded sequence.

I
But
(2.5.4.6) llu _ II = min{llx — a _ ll [Ax = b k. _1, x 2 0}.
11,) 1 2 111,.) 1 2 1 JI
Passing to the limit in (2.5.4.6) we get
= min{llx - 0||2|Ax = b, x 2 0}

which implies that b = 0. But one of the hypotheses was that b is
nonzero. 80 (2.5.4.1) cannot be valid and, thus, (i) follows. Now suppose

(ii) is not true. Then there is a subsequence such that

(2.5.4.7) pk. 5 0, v j.
J
Since (pk) is a bounded sequence, (2.5.4.7) contradicts (i).

2.5.5 REMARK. Lemma 2.5.4 implies that, in Algorithm 2.4.1 with
b 11 0, there exists k0 such that
(2.5.5.1) 6k = pk > 0, V k 2 k0,

45

(2.5.5.3) Step 2 is not executed V k 2 k0, where k0 is the same as
the one of Lemma 2.5.4 (ii).

It is easy to see that the proof of Lemma 2.5.4 applies to Algorithm
2.4.9 as well. So, there is a k6 such that Steps Ia through (and including)
Step 2 of Algorithm 2.4.9 are not executed for all k 2 k6 because pk > 0,
V k 2 k6.

2.5.6 THEOREM. Assume that the norm Hell on R” is strictly
convex and that be{AxlxeR_I'l_}. Then the sequence (xk) generated by
Algorithm 2.4.3 converges to the solution i of problem (P0):

1P0) Ax = h, x 2 0, Ilel 11111).
Proof Assume b # 0. Note that for all k 2 0
(2.5.6.1) pk+1 = min{<gk+1,x>|Ax = b, x 2 0} 2 6k 2 0

by (2.4.4.5) and the fact that bk+1 = bk = b. Now (2.5.6.1) implies
that for all k 2 l we have:
(2.5.6.2) 61‘ = pk and yk = gk and Step 2 is not executed.
For k = 0, we have 60 2 0 and — co < p0 < + co , as in Algorithm
2.4.1. However, if po 2 0, then Step 2 is never executed.
(2.5.6.1) also implies that (6k), k 2 0, is an increasing sequence of
non—negative numbers:

5k+1=Pk+133k301 V1120.
From (2.4.4.3) and (2.4.4.4) it is clear that for k 2 0,
(2.5.6.3) 6k+1 = 6k if and only if uk = 0.
Now suppose 3 k' such that u]; = 0. Then

XE = 6]; y}; and thus

llell = 61;, Since 6]; 2 0 (in fact '61? > 0 Since b]; (t 0)
(2.5.6.4) = min{<yK,x>|Ax = b, x 2 0}.

46

Since y]; e F, "YEII' = 1 and Axk- = b, x]; 2 0, then (2.5.6.4) together
with 2.3.5(i), i.e. the weak duality principle, imply that X}; solves (P0)
and y}; solves the dual problem of (P0) defined in 2.3.3 and flk is the
value of the two problems. So, 61; cannot be increased further and we
must have
(2.5.6.5) 61‘ = 51:1 v k 2 E
because (6k), k 2 0, is an increasing sequence. (2.5.6.5) and (2.5.6.3) imply
that
uk = 0, V k 2 IE.

Let k 2 1?. Since 11k = 0, the above argument, for k instead of 13,
shows that xk solves (P0) and yk solves its dual. The solution to
(P0) is unique, so xk = xE, V k 2 I? and thus the sequence (xk)
converges to the solution of (P0) as an eventually constant sequence.
Also, yk solves the dual of (P0), V k 2 k'. So any cluster point of (yk)
also solves (P0), because of the continuity of the map
min{<-,x>le = b, x 2 0} over F.

Now we can assume that

“k at 0, V k 2 0.

This implies that (6k), k 2 1, is a strictly increasing positive sequence. Let
lim 6k = 6. Clearly 6 > 0. Also 6 < + 00 because (6k) iS a bounded
sequence by Remark 2.5.3.

We will prove that lim uk = 0 as k -1 oo.

Suppose this is not true. Then, there is a subsequence of
(uk), k 2 0, denoted by (uk.) such that uk. -1 u at 0.

By considering further subsequences, and by Remark 2.5.3 we can assume
that yk. -+ y, 7k. -+ 7 and 0k. -1 040,1].
From Step 5 of the Algorithm we have

47

(2.5.6.6) 7 = nun; + 0 < u,y'>.
Note that the map x l-t x' is continuous on Rn\{0} due to the strict
convexity of the norm Hill.
In Lemma 2.4.4 we showed that if “k 91 0, then uk and yk are linearly
independent. By repeating that argument we can Show that u and y are
linearly independent because u at 0. Of course we have to use that
6 = min{<y,x>|Ax = b, x 2 0}
and
7 = min{<u,x>|Ax = b, x 2 0}, which result from the
corresponding relations for the indices k'.
Case 1. Assume that
0k. ,1 1, for all k'.
Then, by the equation for 0k of Step 9 of the Algorithm we get
(017 + (1 - (1)/3) <(0u + (1 - a)r)', u - y> =
(2-5-6-7) = (7 - 6) "all + (1 - a)yll'-
From the relations
6k+l= min{<gk+1,x>|Ax = b, x 2 0} Since bk+1 = bk = b,
2 wok) = (ak7k+(1 ‘ ak)/3k)/||akuk+(1 " akb’kll' by 24-4-3.
> 61‘ 2 0 by 2.4.4.3,
we get
6 2 (a7 + (1 - 01)fl)/||0111 + (1 - 0)yll' 2 6
and thus (2.5.6.7) becomes
(2.5.6.8) 6 < (0n + (l — 0)y)', u — y> = 7 — 6.
Since
0< (0u+(1-0)y)',u—y> =
= ||0Al + (1 - a)y||'- < (a11 + (l—a)y)', y>,
(2.5.6.8) becomes

48

a7 - a6 = 6 New + (1- 0)yll' - 6 < (m1 + (1 - 0)y)'. y>
(2.5.6.9) = 07 + (1 — 0)6 — 6 < (0u + (1 — 0)y)', y>.
Since 6 ,t 0, we get from (2.5.6.9)

(2.5.6.10) l = < (0u + (l — 0)y)', y>. This implies
(2.5.6.11) (0n + (l — 0)y)' = y', because the norm ll-ll is strictly
convex and llyll' = 1.

Using (2.5.6.11) in (2.5.6.8), we get

(2.5.6.12) 6 <y',u> = 7 which, together with (2.5.6.6), implies that

u = 0 which is a contradiction.

Case 2. Assume that

0k. = 1, for all k'.

From Step 8 of the algorithm we get

(2.5.6.13) 7 <u',y> 2 6 ||u||'.

As in Case 1, we still have
6 "011 + (1 - a)yll' = a7 + (1 - 0)6,

which for our case becomes

(2.5.6.14) 6 llull' = 7.

In particular, this implies that 7 > 0. (2.5.6.13) and (2.5.6.14) imply that
<u',y> 2 1, Since 7 > 0.

But

Ilu'll "W = 1.

<u',y>

IA

30,
<u',y> = l which implies that u' = y' because llyll' = l and
the norm ||-|| is strictly convex. Now (2.5.6.6) becomes
7 = "11113 + 6 <u,U'>
(2.5.6.15) = llullg + 6 llull'.
(2.5.6.15) and (2.5.6.14) imply that u = 0 which is a contradiction.

49

It is clear that by taking further subsequences we can assume that either
Case 1 or Case 2 is true for (0k.) and thus we always have a
contradiction. So, u has to be zero and thus lim 11k = 0.

Now let xk. -i x. By considering further subsequences we can assume
that yk. -l y.

Taking limits in the relation

“k' = "k' " 311'
= "lt' " ”k'yl't'
we get
it = (min{<y,x>|Ax = b, x 2 0}) 9.

Then llxll = 6 = min{<y,x>|Ax = b, x 2 0}. We also have
yeF, llyll' = 1 and Ax = b, x 2 0, since the corresponding relations for
the indices k' hold. Now the weak duality principle 2.3.5(i) implies that
x solves (P0), y solves its dual and that 6 is the common value of the
two problems. Since the solution of (P0) is unique, the sequence (xk)
converges to the solution of (P0). Also 6, the limit of the sequence (6k),
is the value of (P0). Now, since
lim 6k = lim (min{<yk,x>|Ax = b, x 2 0}) = value of the dual of (P0),
we have that any cluster point of (yk) is a solution of the dual of (P0),
by continuity of the function min{<-,x>|Ax = b, x 2 0} over F.
Now assume b = 0; then i = 0 and
p0 = min {<g0,x>|Ax = 0, x 2 0} = 0 Since gOeF.
Thus x0 = 0, gl = g0.
Repeating, we get that
gk=go,Vk and xk=0,Vk.
So, indeed

xk-1x=0

50

and gk -1 g0 which solves problem
1P5) max {min{<y,x>le = o. x 2 0}| Ilyll' = 1}
because
min {<y,x>le = 0, x 2 0} = - on, V y¢F
min {<y,x>le = 0, x 2 0} = 0, V yeF.

2.5.7 DEFINITION. Consider Algorithm 2.4.3 with the norm ll'll on
Rn strictly convex and be{Ax|xeR_?_}. Let geF such that Ilgll' = l.
Denote the sequence (6k), k 2 0, generated by Algorithm 2.4.3 initiating
from g0: = g, by (&), k 2 0. By Theorem 2.5.6, we see that
(61%), k 2 1, is an increasing positive sequence converging to “ill for any
ch, llgll' = 1, where i is the solution of the problem

(P Ax = b, x 2 0, l|x|| (min).

0)

Now consider the following algorithm which is an infinite one.

2.5.8 ALGORITHM.
Assume that the norm ll-ll on Rn is strictly convex. Let bk -1 b
such that bkc{Ax|xdli}, v k 2 0.
Step 0. Same as in Algorithm 2.4.1.
Step 1. Calculate
pk: = min{<gk,x>|Ax = bk’ x 2 0}.
Step 2. Put
yk: = gk and 61‘: = pk.
Step 3 - 10. Same as in Algorithm 2.4.1.
We will not worry about the existence of 0k or about the feasibility of

this algorithm because all we need is the following remark.

51

2.5.9 REMARK. Assume b (t 0. Apply Algorithm 2.4.1 to
(bk)’ k 2 0, initiating from a goeF, Ilgoll' = 1. Let k0 be as in Remark
2.5.5. Then it is clear that from the ko—th iteration onwards, Algorithm
2.4.1 is identical to Algorithm 2.5.8 applied to (bk)’ k 2 k0, and initiated

from gk . In particular this is true for Algorithm 2.4.3 which is identical
0

to the corresponding Algorithm 2.5.8 after the first iteration.

The same is true for Algorithm 2.4.9 from the kb—th iteration onwards.
So, Algorithms 2.4.1 and 2.4.9 can just be viewed as Algorithm 2.5.8 applied
to a sequence (bk)’ k 2 0, and initiating from a g0 such that pk 2 0, V
k 2 0. It is clear that if this happens, i.e. if pk 2 0, V k 2 0, then
Algorithm 2.5.8 is feasible because it coincides with 2.4.1 and 2.4.9 which are
feasible.

Note that Algorithms 2.4.1 and 2.4.9 do not necessarily generate

sequences that eventually coincide.

2.5.10 LEMMA. For Algorithm 2.4.1 under the same set of hypotheses

as in Section 2.4, with b 91 0 we have that there is an

i0 2 k0, k0 as in Lemma 2.5.4(ii), such that, V k 2 i0,

(2.5.10.1) min{<yk,x>|Ax=b,x 2 0}=min{<gk,x>|Ax = b,x 2 0} > 0.
i0 depends on (bk)’ k 2 0, and g0.

Moreover,

(2.5.10.2) All cluster points of (min{<yk,x>|Ax = b, x 2 0}),

k 2 0, (min{<gk,x>|Ax = b, x 2 0}), k 2 0, are greater than zero. The
same Lemma is true for Algorithm 2.4.9 for an i6.

Proof Via (2.5.5.2), it is enough to consider only gk '3.

52

Suppose there is a subsequence such that

lim (min{<gk.,x>|Ax = b, x Z 0}) S 0. By taking a further subsequence,
J
we can assume lim gk. = g. Then,
J
0 2 min{<g,x>le = b, x 2 0} = lim pk. contrary to Lemma
J

(2.5.4)(i). The rest follows easily.

CHAPTER 3

3.1 INTRODUCTION
We keep the notation introduced in Chapters 1 and 2.
In this chapter we consider Algorithm 2.4.1 with bk—tb,

gOeF, ||g0ll' = 1, and we prove that it converges to the solution X of the

problem
1P0) Ax = h, x 2 0, IIxII (min).
For this we assume smoothness of the norm ll . ll on Rn in addition to the

already assumed strict convexity. AS an immediate application of this, an
algorithm for nonnegative least error minimal norm solutions is given.

Some numerical results follow.

3.2 CONTINUITY OF THE 6! FUNCTIONS
In this section certain functions are defined and then their continuity

proved.

3.2.1 DEFINITIONS. Let s be a closed ball in Rm not containing 0
such that it contains at least one point of {Axlxelli}. B will be considered
fixed. Let H - ll be a strictly convex and smooth norm on Rn and let
To: = {(g,b)4Fn{zeRn| llzll' = 1}) a ({Axlxcsfi} n s) such that f1(g,b) 2 0},
where fl(g,b): = min{<g,x> l Ax = b, x 2 0}. In Section 2.5.1 we saw that
fl is continuous on the set where it is finite. It is easily seen that
T0 is a compact subset of R“ x km. The set {Axlxtlln, x 2 0} is closed
because it is a finitely generated convex cone.

Given (g,b)cT0, let us perform one iteration of Algorithm 2.4.1 for
k = 0, replacing g0 by g and b0 by b. This is the same as doing Algorithm

53

54

2.5.8 because f1(g,b) 2 0. Then the algorithm will evaluate the following:

p0, yo, 60, a0, x0, uo, 70, 00, gl. These can be viewed as the values of

corresponding functions at (g,b). Let us denote these functions by

11211) 1101-0501»).1101-.-).a01-.-).x01-.-I,101,-),
700,-). 010(n'), gl(-.-) reSpectively.

Their domain is T0‘ Note that 00( - ,-) is a function because the 00 of

Step 9 is unique, by the smoothness and strict convexity of the norm ll - ll.

So gl(-,-) is afunction, too. Also for (g,b)eTo and u0(g,b) #0 define
evo1s.h)+11—e)1101a,h)

IIeuo1a.h)+11—ely01a,h)u'
which is defined because, as we know, u0(g,b) and y0(g,b) are linearly

 

vo(g.b):[0,1] -1 R such that for 040,1], (00(g,b)(a) =

independent.

3.2.2 THEOREM. Assume that H - I] is a strictly convex and smooth norm
on R“. Then the function gl( - , -) is continuous over T0.
Proof Let (gk,bk)eT0, Vk
and
(gk,bk) -1 (g,b). Then, Of course, (g,b)eTO.
Note that we have
401-.-)=i,1~.-),ovet T01
001o,-)=1,1-,-),ovet To,
and
70(gtb) = s, V(s,b)tT0-
SO, p0(-,-), 60( ~,~), y0( -,t) are all clearly continuous over T0.
Also,
1,14) = 1101...) 1y01-.-))'.

SO a0(o,-) iS continuous over T0“

 

55

For (g,b)eTo, we have
x0(g,b) = 3(30(81b)1b)

and thus x0(-,-) is continuous over TO' u0(-,-) is also continuous over T0,
Since u0(-,-) = x0(-,-) —a0(-,-). The same is true for 70(-,-), Since
70(°3°) = <u0(°1°)1 X0(°,)>.

Case 1. Suppose u0(g,b) it 0. Then for all large enough k we have
u0(gk,bk) at 0 by the continuity of u0(-,-).

Subcase 1. Suppose (00(gk,bk)) were determined using Step 9for infinitely
many k'S in an index set 1. Extract a further subsequence kjeI such that

00(gkj,bkj) -1 0, 0 5 0 5 1.
By taking limits in the relation Of Step 9 and using continuity of

70(°7°)3 60(°,-), u0(-,t), y0(-,-) over TO’ and the fact that
ud(g,b) and y0(g,b) are linearly independent as u0(g,b) is

non—zero, we have
(070(gib)+(l_a)fl0(gib)) <(0u0(g,b)+(l — 0)y0(g,b))',u0(g,b) — Yo(gib)> =

(32-21) = Ila/1106,11) + (1 - a)yo(gab)ll' (70(grb) - 60(stb))-
But (3.2.2.1) says that
141012.110 111) = 0.
We know that 00(gk,bk) was chosen to be the global maximizer Of (00(gk,bk)
on [0,1] and thus
(100(gkabk))(ao(gkabk)) .>. (120(sk.bk))(0) = 60(gkibk) 2 0.
SO, 00(gktbk)70(8ktbk) ‘l‘ (1 ‘ 00(8ktbk))flo(8ktbk) 2 0-
Allowing j-1 on in the subsequence (kj) we get
ero1sh) + 11— a)11,1ah) 2 o,

56

i.e. 100(g,b)(0) 2 0.

Let us assume

(3.2.2.2) (00(g,b)(0) = 0.
Then by (3.2.2.1),

(32-2-3) 70(g,b) = 60(55)-

By (3.2.2.2) and (3.2.2.3),
7001,11) = 60(stb) = 0-
But 60(g,b) = 0 implies a0(g,b) = 0.
Since 701ah) = IIu,1s.h)II§+ <uo1a,h),a,1shl>,
u0(g,b) = 0 which is a contradiction.
SO, 100(g,b)(0) > 0. Since also (1p0(g,b))'(0) = 0, then, by Lemma 1.5.3,
0 is the global maximizer of (00(g,b) on [0,1]. Such an 0 is unique because
the norm ll - ll is smooth and strictly convex. But we know that 00(g,b) is the
global maximizer, Since u0(g,b) it 0. So, 0 = 00(g,b). It follows that
[1361? 00(gk,bk) = 0 = 00(g,b) as the only cluster point.

Subcase 2. Suppose (00(gk,bk)) were determined using Step 8for
infinitely many k's in an index set J, so that 00(gk,bk) = 1 for these
k's. Taking limits in the Criterion of Step 8 and by the continuity Of

70(°i°)1fl0(°9°)7 uo(°i°)i Yo('i°)a we get

13.2.2.4) 70(8th <1uo1a.h))',y01shl> 2 (loch) IIuO1a,h)II'.
(3.2.2.4) means that
(3-2-2-5) (Po(s.b))'(l) 2 0.

By Step 6, 70(gk,bk) > 0 and thus 70(g,b) 2 0. If 70(g,b) = 0, then by
(3.2.2.4), 0 2 60(g,b). But 60(g,b) = f1(g,b) 2 0 because (g,b)eTo.

SO, 60(g,b) = 0. AS in Subcase 1, we get a contradiction from

70(g,b) = 0 = 60(g,b). SO, 70(g,b) > 0 which means that

57

(3.2.2.6) 1pO(g,b)(1) > 0.
(3.2.2.6) and (3.2.2.5) imply that 1 is the global maximizer of (00(g,b)

on [0,1] and thus 00(g,b) = 1, Since u0(g,b)#0. So,
lim0 (g ,b )=1im1=1=0(g,b).
keJ 0 " 1‘ 11.1 0

Subcases 1 and 2 together imply that

lim 00(gk,bk) = 00(g,b), as k 4 co
and thus from Step 10

lim gl(gk’bk) = 31(gib)9 88 k " m)
since u0(g,b) and y0(g,b) are linearly independent. Also
“0(gk’bk)’ y0(gk,bk) are linearly independent eventually for all k.

Case 2. Suppose uo(g,b) = 0. Then, gl(g,b) = y0(g,b) and
x0(g.b) = ao(g.b) = 60(g.b)(yo(s.b))'
= (min{<yo(stb).X> lAx = b, x 2 0}) (70(glb))'-

Also, 60(g,b) = fl(g,b) 2 0 because (g,b)eTo.
Also, Ax0(g,b) = b and x0(g,b) 2 0.
Suppose 60(g,b) = 0; then x0(g,b) = a0(g,b) = 0. But x0(g,b) is
the solution of the problem n1in{llxll2|Ax = b, x 2 0} since
a0(g,b) = 0. This implies that b = 0, a contradiction to (g,b)eTO.
So, 001st) > 11. Since IIx,1sh)II = 401st) = hhni<y01shtx> I Ax = h, x 2 0}.
||y0(g,b)l|' = 1, then due to the weak duality principle 2.3.5,
y0(g,b) solves the problem

(P6) ll Illllax (min{<y,x>|Ax = b, x 2 0}).
y =1
Now let a subsequence (k j) be chosen such that

gl(gk.’bk.) 7 5561‘, "SW = 1.
J J
As we know from (2.4.4.5),

58

min{<gl(gk.,bk.),x> le = bk.’ x2 0} 2
J J J
2 min{<y0(gk.,bk.),x>|Ax = bk.’ x 2 0} =
J J J
= fi0(gkj1bkj) 2 0 because (Skjtbkj) (To-
By taking the limit as j -1 00, we get
(3.2.2.7) min{<g,x> l Ax = b, x 2 0} 2
2 min{<y0(g,b),x>le = b, x 2 0} = 60(g,b) 2 0.
(3.2.2.7) can be true only if equality holds and E solves (P6). Then we
have
x0(g.b) = 60(g,b) (70(g.b))'
(3.2.2.8) = 60(g,b) g’ as in Theorem 2.3.6.
Since the norm ll . ll is smooth and 60(g,b) # 0, (3.2.2.8) implies
5 = Yo(gtb)- 801 lim 81(gkbk) = Yo(gab) = 31(8113), 3-3 k " 0°-

This completes the proof that gl( - ,-) is continuous over T0.

3.2.3 DEFINITIONS. Let the norm ll'll on It11 be strictly convex
and smooth. We defined earlier the compact set T0 and the functions
1111...): 10.. Fn{2611”lllzll' = 1}
and
60(-,-): TO -+ [0, +60).
We have verified earlier that these functions are continuous on T0' Let
t be an integer, (2 1. Suppose we have defined a compact set T (_1

subset of Rn 1: (Rm)! and a function
s1. ..,-=) T(_1-1Fn{zdinlllzll' = 1}
7371——

which is continuous over T (_1.

Then define the set

59

Tl: {(g,a1,...,al,b)|(g,al,...,at) e TG—l and b e{AxlxcR_?_} n B
such that f1(gt(g,a1,...,a(),b) 2 0}.
TI is a subset of Rnx(llm)l+l.
T! is compact, i.e. closed and bounded, fl(gt(g,al,...,a(),b) being
continuous as a function of (g,al,...,al,b) over the set
{(g,a1,...,at,b)l(g,a1,...,al) 6 TH, be{Axlxdl_':_} }.
Noting that for (g’al’""al’b)‘Tt’ (gt(g,al,...,at),b)eT0,
we can make the following definitions:

Define the functions

)6", . ..,°): Tl-1[0,+oo),
73:2—
6t(g,a1,...,al,b) = 60(gt(g,al,...,al),b)
= f1(gl(g,al,...,a(),b)
and

gl+1(~,. ..,.);T,x Fn{zelln| l|z||'=1}.
2+2

gl+l(g,a1,...,al,b) = gl(gl(g,al,...,al),b),
for (g,a1,...,a(,b)eT[
Clearly, g1 +1(-,...,-) iS continuous over Tl’ because of the
continuity Of g1(~,-)and gt(~,...,-) over T0 and T(_1
respectively. Similarly, 64-, ..,-) is continuous over Tl‘
So now we have defined compact sets T l and continuous

functions flt’ gl+1 for all t: 0,1,2,....

3.2.4. Apply Algorithm 2.4.1 to the sequence (bk)’ k 2 0,
bk 6 {Axlxelli} n B, Vk 2 0, bk -1 b, starting with gocF, llgoll' = 1,
and let k0 be as in Lemma 2.5.4, [1k 2 0, Vk 2 k0. Then,
Vk2k0 and Vl2 0 wehave

60

(3.2.4.1) (gk, bk, bk+l,..., bk+l) f To
because (’j 2 0 Vj=k,...,k+l,

and moreover

(3.2.4.2) 644. bk. bk+1.m. but) = 6],”

(32°43) 31.14310 but bk+l"'" but) = gk+l+1°
(8k). 11 2. 0. (61‘), k 2 0, (pk), k 2 0 are the sequences

generated by the Algorithm.
Tl” 6l(-,...,-), gt“ (,,) were defined in 3.2.3.

3.3 CONVERGENCE OF ALTHORITHM 2.4.1.

In this section we consider Algorithm 2.4.1 for a given sequence
bk 6 {Axlxefli}, Vk 2 0, with, lim bk = b. Suppose the algorithm starts from
a given gocF, llgoll' = 1. We keep the assumption that the norm ll - II on
It“ is strictly convex and smooth.

We prove that the algorithm converges to the solution 31' of the problem
(P Ax = b, x 2 0, lell (min).
From this and Remark 2.5.9, it is clear that Algorithm 2.4.9, applied to

0)

(bk)’ k 2 0, and g0, also converges to 5.

3.3.1 THEOREM. Let ||-|| be a strictly convex and smooth norm on 11".
Let bellm, b ,1 0 and assume that Ax = b, x 2 0 is feasible. Let
bk 6 {Axlxdli}, Vk 2 0, such that lim bk = b. Let gOeF, ||g0||' = 1.
Then, the sequence (xk), k 2 0, generated by Algorithm 2.4.1 converges to
the solution SE of the problem
(P Ax = b, x 2 0, lell (min).

Proof Let 0 < M < ||b||2 and s = {xcllml llx — b||2 g M}.

0I

61

Let i0 as in Lemma 2.5.10 and let kl such that bkeB, Vk 2 k1.
Let k2 = max{io, k1}. It suffices to prove that Algorithm 2.4.1 applied
to the data gk and (bk)’ k 2 k2, converges. So, it constitutes
2

no loss of generality in assuming that

bkeB, pk > 0, pk = 6k, yk = gk, min{<yk,x>|Ax = b, x 2 0} > 0, Vk 2 0.

In accordance to this, the ko of 3.2.4 will be taken to be zero. Clearly,
V 6 > 0, 3 i(6) depending on 6 such that

(3.3.1.1) llbk - bll2 < 6, Vk 21(6).

For each k 2 0, we consider Algorithm 2.4.3 for b starting from gk.

Since min {<gk,x>|Ax = b, x 2 0} >0, we have that

8 _
(3.3.1.2) (69'), i 2 0, is a positive sequence increasing to ||x||.

g
(See 2.5.7 for the meaning of (6ik)).

Also, Vt’ 2 0, Vk 2 0,

(gk,b , ...,b) (Tl.
2+1 times
From 3.2.4, we also have that Vt 2 0, Vk 2 0,

(er in bits-~11...) ‘Tt
Let w = (y, c0, 01,...,cl)eT(, yell“, ciclim, Vi, 0 5 i 5 t.
Then define

110, to, c1.....c,)III= = llyll +iéollcill2-

It is easy to verify that l" - III is a norm on R” :1 (Rm)(+1.
Note that T! _c_ [in x (Rm)l+l .

Now let (2 0 be a given integer and let e > 0 be given.

5! ( - ,...,-) is uniformly continuous Over the compact T l and thus

3 n(e,l) > 0 depending on e and t, such that
V wl, wchl, |||w1 — ngll < q(e,l) we have that

62

(3-3-1-3) l6t(wl) -6l(w2)l < ([2.
In (3-3-1-1) 910k 5: "(610/ ((+1) Then 31(6) = i(e,l) i.e. depending
on e and t, such that
V11 2 i(e,() we have that
Ilbk — bll2 < nag/(4+1) and also
”ka - bll2 < Wall/((+1),
Ilbk+,— b||2 < «ea/(4+1).

Summing up, we get that

““ng bk, bk+l,"°,bk+() — (gkib a m’b) ”l < "(‘70
2+1 tlmes

and thus, by (3.3.1.3), we have that
lflggk,bk,...,bk+l) _ flgng) , ...,b )l < 6/2.

2+1 tlmes
This last relation, via (3.2.4.2) and Definition 2.5.7, is the same as

8k
mint-fl! |< 42'
Summarizing, we have that
V l 2 0, l interger, V6 > 0,
3 i(c,l) depending on e and t such that

(3.3.1.4) (6H,- pikl < 2/2, Vk 2 i(e,l).
Now define

Kb: = {ch such that ||gl|' = 1 and f1(g,b) 2 0}.
Kb is compact as closed and bounded, since f1( - ,b) is continuous over F.
Note that from 3.2.4 and Algorithm 2.4.3 we have that if geKb, then

(gab 7 msb)CTl, V42 0.
2+1 tlmes
Also note that, in our case, gchb, Vk 2 0, Since

min{<gk,x> I AX = b, X Z 0} = fl(gk,b) > 0.

63

Now let 5 > 0 and geKb both be given.
In view Of 2.5.7,
3 k (c,g) depending on e and g, such that
(33.1.5) "X“ — ¢(£’g) < C/4.
By unlform contlnulty of 6“ ‘,g)(-,...,-) over Tk( e, g) we have that
3 n(e,k(e,g)) = n(e,g) > 0 depending on e and g, such that
V wl, W26Tk(e,g)’ |||wl - w2|ll < n(e,g) we have that
Now let
nybi ”y -g" < "(‘73)
Then,
|l|(y.b.---.b) -(g,b.--- ,b) Ill < ”(6.5)-
k(e,g)+1 k(e,g)+1 times

 

 

By (3.3.1.6),
|6k(£,g)(g,b,...,b) — 6k(£’g)(y,b,...,b)| < e/4
which is the same as
(3.3.1.7) “36.3) - @463“ < 2/4.
(3.3.1.7) is true VyeKb n B(c,g) where
B(e,g): = {xdlnl ||x - gll < 17(e,g)} is an Open ball in the I] -ll norm
with center g and radius 7)(e,g). The notation B(e,g) denotes that it
depends on e and g.
From (3.3.1.5) and (3.3.1.7) we get that
V c > 0, V chb,
3 an integer k(e,g) and a neighborhood of g,B(e,g) such that
(3.3.1.3) llx" - pi < 2/2, v k 2 k(e,g), v yeKb n B(e,g).
By summing (3.3.1.5) and (3.3.1.7) we get (3.3.1.8) for k = k(e,g);

64

after this the result is clear because for each y,
(61:), k 2 0, increases to llill.
Let r > 0. Since Kb is compact, 3 l0 and g1,...,g(0cKb such that
f 0
(3.3.1.9) K = U (K n B(e, .)).
b i=1 b 81

Writing (3.3.1.8) for each gi, i = 1,...,(0, we get
(3.3.1.10) llill — 6?; < 6/2, V11 2 k(e,gi), Vye Kb 0 B(e,gi).
Let k(e) = max{k(e,gi)|i = 1,...,lo}; k(e) depends on e.
Combining (3.3.1.9) and (3.3.1.10) we get that
V c > 0, 3 an integer k(e) depending on e, such that

"ill - 6% < 6/2, Vk 2 k(e), V yeKb.
In particular,

_ 8
(3.3.1.11) llx|| — si" < 2/2, Vi 2 I46), v k 2 0.
Now let 6 > 0 be given. By choosing l = k(e) in (3.3.1.4), we get that
3 i(e,k(e)) = i(e), i.e. depending on e, such that

(3.3.1.12) (61%“) — ail,“ < 2/2, v k 2 i(e).

From (3.3.1.11) we get

(3.3.1.13) Ilill — 6183(6) < e/2, V k 2 0.

Adding (3.3.1.12) and (3.3.1.13), we conclude that

V e > 0, 3 non—negative integers k(c) and i(e) such that
l “ill “flk+k(£)l < ‘1 V1121“)

Letting j(t): = i(e) + k(e), the last statement is the same as
V e > 0, 3 j(e) such that

I IIxII —11,.I < ., V1216).
I.e.

(3.3.1.14) lim 6k = llill.

65

Now assume lim 3k. = a. By taking further subsequences we can
J

assume that lim yk. = y.

J
Then,
lim flk. = min{<x,y>| Ax = b, x 2 0}
J
(3.3.1.15) = llill by (3.3.1.14).
Via the "Only if" part Of Theorem 2.3.6 and since b t 0, (3.3.1.15)
implies
(3.3.1.16) x = llx” y.
50.
lim ak. = lim 6kg]; = llx—Ily' = i
J J J
and thus
(3.3.1.17) lim ak = i.

From (3.3.1.17) and the continuity of the function f3 defined in 2.5.2, we get
lim xk = lim f3(ak,bk) = 3(Zb).

f3(§,b) is the solution of the problem
Ax = b, x 2 0, llx —5?||2 (min).

But the solution is clearly 5, since A? = b, 52 0.

SO, “[11 Xk = i

Now assume lim yk. = y. By (3.3.1.15) and the weak duality principle
J

2.3.5(i), we have that y is a solution of the problem

1P5) max {min{<y,x>|Ax = h, x 2 0“ Ilyll' = 1}.

By (3.3.1.16) and Since the norm ll - ll is smooth, we get that any two
cluster points of (yk) are equal since they both satisfy (3.3.1.16).
Also, any solution of (P6) satisfies (3.3.1.16) and thus it is unique.

Consequently, (yk) converges to the unique solution of (P6) which iS

66

dual to (P0) as defined in 2.3.3.

The proof of the theorem is now complete.

3.3.2 THEOREM. Let I] ~ I] be a strictly convex norm on It". Let
bk ({Axlxelii}, V k 2 0, and lim bk = 0. Then the sequence (xk) generated
by Algorithm 2.4.1 converges to zero, which is the solution of the problem
Ax = 0, x 2 0, lell (min).
Proof Let us take a subsequence 6kj —. 6. Then 6 2 0.

By taking further subsequences we can assume yk. -t y.
J

Then,
flk. = min{<yk.,x> le = bk.’ x 2 0}
J J J
implies
6=min {<y,x> | Ax=0,x20} _<_0 bytaking x=0.
SO finally, 6 = 0 and thus lim 6k = 0.
Then lim ak = lim flkyk = 0.
Consequently,
But f3(0,0) iS the solution Of
Ax = o, x 2 o. IIxII2 1111111)
which is, of course, 0.

80 um Xk = 0.

3.3.3. Theorem 3.3.2 says that Theorem 3.3.1 is still true if we remove
the assumption b non-zero.
Theorems 3.3.1, 3.3.2 are also true for Algorithm 2.4.9 due to Remark 2.5.9.

Note that in these two theorems we also have lim uk = 0.

67

3.4 AN ALGORITHM FOR NON-NEGATIVE LEAST ERROR
MINIMAL NORM SOLUTIONS

3.4.1. Let H - ll0 be a strictly convex norm on Rm and ll - ll be a
strictly convex and smooth norm on It”. Suppose that the system Ax = b, x 2 0
has no exact solution. We are interested in estimating the solution 5 of
the following problem
111) Ax = Ax, x 2 0. IIxII 1111111),
where x is a solution of
(S) x 2 0, [lb — Axll0 (min).
In other words, i is the minimum norm solution of (S).
One way to do this is the following:
First we use Algorithm 4.1 in Sreedharan [6] to get an estimate of A11 and
then apply Algorithm 1.4.1 to problem (R). This does not require smoothness
of I] - ll. Algorithm 4.1 in [6], if we remove its stopping criterion, is
generating a sequence (Axk), k 2 0, converging to Ax. Applying Algorithm
2.4.1 to this sequence, we get a sequence (xk), k 2 0, converging to 5 via
Theorems 3.3.1, 3.3.2. An algorithm which implements this idea is given
below and it can be used for estimating 3E. The norm || - ll is also required
to be smooth. The algorithm calculates Aik and if the duality gap for
problem (S) is small enough, then it calculates xk. After this, Axk+1

is calculated and SO on.

3.4.2 ALGORITHM.
r) > 0, 0 < e < ‘1 and 62 > 0 are given. ||- ll0 and ll‘ ll—dual vectors

will not be distinguished notationally.

68

Step 0. Let 5&0 be a solution Of the problem
x 2 0, llb — Axll2 (min).
Let r0: = b—Axo and yo: = ro/Ilrollé.
A more general choice of y0 requires that Ary0 S 0 and <b,y0> > 0,
111.113“ Let 4: 0, i2 = 0.
Step I. Let goeF, llgoll' = 1. Put k = 0.
Step 2. Let bk: = b — <b,yk> y];
and ’11. be a solution of the problem
x 2 0, llbk — Axll2 (min).
Let rk: = bk — Axk.
Step 3. If Dk: = l - (<b,yk>/ llb — Axk"0) S 6,
put I = 1 and GO TO STEP 8, else, proceed.
If Bk 5 ‘1’ GO TO STEP 8, else, put 3k+1' = gk,
increment k by 1 and proceed.
Step 4. If <b,rk> S 0, then
5k: = <b,yk> / <b,yk - rk>
and GO TO STEP 6, else, 5k: = 1 and proceed.
Step 5. If <b,rk> <rl'(,yk> 2 <b,yk> llrkllb,
set 0k: = 1 and GO TO STEP 7, else, proceed.
Step 6. Find 0k, 0 < 0k < 5k such that
<b,0krk + (1 — 0k) yk> <(0krk + (1 — ok)yk)', rk —yk>
= |l0krk + (l - 0k)yk||('J < b,rk —yk>.
Step 7. Let
- _ 0krk+ (1 - 0k)yk
yk+1"IIaktk + 11 - eklikng,’
Increment it by 1 and RETURN TO STEP 2.

 

69

Step 8. If
a. m ..
"Axkllf = igll (AXRM > ‘21
GO TO STEP 9, else, proceed.
If I = 1, STOP; xk: = 0 solves (R). Else, proceed.
Put xk: = 0, gk+1: = gk, increment k by 1 and GO TO STEP 4.
Step 9. Calculate pk: = min{<gk,x>| Ax = Axk, x 2 0}.
If pk 2 0,
6k: = pk, yk: = gk and GO TO STEP 11, else, proceed.
Step 10. Let, zk

be the solution of the problem
AX = Axki X 2 09 "xllz (H1111).

2
2k __ Ilakll2
llzkll' Ilzkll'
Step 11. Let ak: = flkyk‘

Let xk be the solution of

 

 

Ax = Axk, x 2 0, llx - akll2 (min).
Let “k: = Xk — 3k.
llxkll ’ 3k
Step 12. If —— > 7], GO TO STEP 13, else, proceed.

llxkll
If t = 1, xk is taken as the solution of (R) and STOP. Else, proceed.

Put gk+1: = yk, increment k by 1 and GO TO STEP 4.

Step 13. Let 71‘: = <uk,xk>.

Step 14. If 7k 5 0, let 51‘: = 6k|(6k—7k) and GO TO STEP 16,
else, 5k: = 1 and proceed.

Step 15. If 7k <ul",yk> 2 6k||uk||', set 0k: = 1 and GO TO STEP 17, else,
proceed.

70

Step 16. Find 0k40,5k) such that
(ak7k + (1’ 0196],) <(akuk ‘l' (1" ak)yk)'t 11k " yk>
= llakuk + (1" akJYkll' (7k "’ Bk)
Step 17. Let
"0ka + (1 " ak)ykll' ~ ~
If t = 0, RETURN TO STEP 4, else, proceed. Axk +1: = Axk and RETURN
TO STEP 9.

and increment k by 1.

 

gk+1‘

This combined algorithm essentially amounts to:
lst) An application of algorithm 4.1 Of [6] to problem (S), from which we
get a finite sequence {A210, ARI,...,AKk } with Axk regarded as Air, and
0 0

2nd) An application of Algorithm 2.4.1 to some finite sequence
{ij1, ij2,...,ijl, Axko, Axk0,...,Axk0}

with 0 5j1<j2 <...<jls k0 — 1.

It is not apparent which of the two alternative methods, suggested in
this thesis for solving problem (R), is better.

If a "good" g0 for doing Step 1 is not at hand, we do the following:

1st) change Step 1 as follows:

Step I. Put g0: = 0, k = 0.

2nd) change Step 9 as follows:

Step 9. If gk = 0, GO TO STEP 10, else, proceed.

Calculate pk: = min{<gk,x> l Ax = Axk, x 2 0} and the rest of Step 9
is as before.

Instead Of this, if A110 satisfies the Criterion of Step 8, we can

replace Step 1 with

71

Step 1. Put k = 0
and Step 9 with
Step 9. If k = 0, GO TO STEP 10, else, proceed.
Calculate pk: = min{<gk,x> [Ax = A121,, x 2 0} and the rest of Step 9 is

as before.

3.5 NUMERICAL RESULTS
Algorithm 3.4.2 was coded in FORTRAN 77 in double precision for a SUN
computer. The norm ll - ll0 was taken to be the II - I] p norm for various
values of p, i.e.
IIxIIp = 121,:1Ix,IPI'/P,
for x = (x1,...,xn)elln and 1 < p < co. The dual norm of ll-llp is the
ll - ll q norm for q = p/ (p - l). The H - llp—dual of x at 0 has components
x; = (Isl/IIxIIql‘l‘l Sgnxi.
for i = 1,...,n. (See also [8]).
The other norm ll - ll was taken to be either equal to II - H0 or dual to it.
As in [6], the problems were done starting from p = 2 and then eventually
increasing or decreasing p. For each new value of p, the yo and go
of Steps 0 and 1 were taken to be the prOperly scaled terminal values of
yk and gk of the problem for the previous p. The e and ‘1 of

Step 3 were taken to be 10"5 and 10—3

respectively. The 1) Of Step 12 was
10—6. The 0k's of Steps 6, 16 were calculated using subalgorithms 4.5 and
4.6 Of [6] with tolerance 17 = 10—9. Steps 2 and 11 were executed using the
NN LS and LDP programs of [2] respectively. The linear programs were done
using the simplex algorithm.
In all the tested examples the algorithm was indeed capable of approximating

the solutions, although convergence was at times very slow. On the same

72

examples, the sequential alternative proposed in 3.4.1 was never found to
be inferior to Algorithm 3.4.2 in rapidity Of convergence. In some cases,
Algorithm 3.4.2 did much worse than the sequential alternative.

Below we tabulate the results of Algorithm 3.4.5 applied to the

following data:

1 0 0.1 0.9 2

0 l 0.1 0.9 2

A = l l 0.2 1.8 and b = 2
1 -l 0 0 1

-l l 0 0 1

2 0 0.2 1.8 3

Note that A is not 1 — 1 nor onto, as its rank is 2. The system Ax = b
is seen to be inconsistent. The NN LS solution of Ax = b which was calculated
using the N NLS program of [2], is
(0.064516, 0., 0., 1.505376)
and the least ||-||2 NNLS solution is
(0.557673, 0.493157, 0.105083, 0.945747).
In this example no Axk was zero and no pk was less than zero. That
also was the case with most of the other examples that were tested.
In the table that follows, x = (x1, x2, x3, x 4) denotes the terminal
value of xk for each p. Also,
81: = llb -— Axllo,
1,: = IIxII.
k1 and k2 denote the number of times that Steps 6 and 16 were executed
respectively.
k3 is the number of times that Step 16 was executed after t was set

equal to l, and

73

k 4: = k' — 1, where k' is the number of times that the duality gap of
Step 12 was _<_ 7).

74

(X11x21x31x4)
(.640144, .640047, .463923, .719947)

(.637454, .636924, .445596, .726099)
(.634068, .632974, .423662, .733306)
(.632562, .631062, .413666, .73751
(.630434, .627651, .397171, .744031)
(.624941, .62045, .364158, .757479)
(.62249, .616665, .343717, .764323)
(.618263, .609619, .32252, .776705)
(.608964, .592084, .268588, .805761)
(.592372, .560547, .197272, .353557)

(.5447, .470442, .084868, .975027)

(.504321, .407001, .045666, 1.053366)
(.427267, .303775, .014517, 1.175417)

(.360989,
(.269809,
(.170394,
(.144062,
(.141133,
(.141225,

Case 1- Mo = ll°llp. M = Il-llp

p 111 k2 k3 k4 s1 32

6 14 14 0 0 1.145953 .812068
5.5 12 11 0 1 1.165731 .826833
5 6 6 0 0 1.191253 .344335
4.3 6 6 0 0 1.203523 .353339
4.5 7 6 0 1 1.224734 .867860
4 4 3 0 1 1.270246 .397045
3.3 4 4 0 0 1.293109 .911349
3.5 4 4 0 0 1.334227 .936461
3 3 3 0 0 1.423797 .991904
2.5 2 2 0 0 1.573439 1.07432
1.9 1 1 0 0 1.91694 1.244917
1.7 1 1 0 0 2.109377 1.332154
1.5 3 2 0 1 2.331531 1.437116
1.4 4 3 0 1 2.562909 1.491591
1.3 5 4 1 2 2.739927 1.541435
1.2 3 3 0 4 3.03179 1.580765
1.15 3 6371 6363 0 3.260797 1.595663
1.1 10 1433 1424 0 3.468509 1.610757
1.095 7 6 0 1 3.491111 1.612414
1.09 7 6 0 1 3.514074 1.614101

TABLEl

(.141309,

.223195, .005133, 1.260717)
.132402, .000901, 1.36654)
.031523, .000035, 1.476733)
.003317, 0., 1.506606)
.000013, 0., 1.509853)
.000023, 0., 1.509753)
.000017, 0., 1.509661)

 

 

591‘!

 

75

(X1,X2,X3,X4)

1.463659 (.074163, .074066, .000023, 1.400359)
(.0979, .097371, .000069, 1.375106)

(hw2-HMO=H45JLH=H4Q
p R1 R2 R3 R4 31 82
6 * 12 0 2 *
5.5 9 0 3 1.463255
5 5 0 1 1.455210 (.128449,
4.8 5 0 1 1.451075 (.142974,
4.5 5 0 2 1.443894 (.167815,
4 3 0 1 1.426226 (.216799,
3.8 3 0 1 1.417131 (.239757,
3.5 3 0 1 1.400453 (.278088,
3 3 0 0 1.361760 (.353518,
2.5 2 0 0 1.301961 (.445046,
1.9 1 0 0 1.183322 (.583329,
1.7 1 0 0 1.124865 (.637786,
1.5 3 l 1 1.049213 (.692718,
1.4 3 0 1 1.001097 (.716131,
1.3 4 0 1 .944481 (.734526,
1.2 4 0 3 .880758 (.748566,
1.15 4 0 4 .847235 (.753729,
1.1 4 0 5 .756889 (.756889,
1.095 3 0 4 .810186 (.757026,
1.09 3 0 4 .806876 (.757068,

* Identical to the corresponding column for Case 1.

TABLE 2

.127354,
.141475,
.165032,
.212307,
.233932,
.269444,
.336639,
.412721,

.509071,
.539965,
.569226,
.533337,
.597119,
.609199,
613434,
.615774,
.615324,
.615776,

.000204,1.342657)
.000313,1.327424)
.000595,1.302166)
.001716,1.251242)
.002614,1.223037)
.004396,1.139969)
.013301,1.1179)

.033351,1.035466)

.123343,.927275)
.191153,.339962)
.233527,.350531)
.34399,.32347)
.415901,.304077)
.502064,.77915)
.55213,.76735)
.608495,.758069)
.61457,.757244)
.620744,.756514)

REFERENCES

REFERENCES

Gal, T., "Linear parametric programming, a brief survey",
Sensitivity, Stability and Parametric Analysis,
Mathematical Program_n_1_1n g 51115111 21, a publication of the
Mathematical Pro ramming Society, A. V. Fiacco, Editor,
North—Holland—imsterdam, June 1984, 43—68.

Lawson, C. L. ,and Hanson,RJ.,S_Q1n11g_L§a_§q11fles_
Pro,blem§ Prentice Hall, Englewood Cliffs, N. J. (1974).

Luenberger D G 111W
Programming, Addison Wesley: Reading, Mass. (1984)

Nirenberg, L., W, lectures given in
1960—361, notes by Lesley Sibner, New York University,
1961

Rockafellar, R.T., anvex Analysis, Princeton University
Press, Princeton, N.J., 1969.

Sreedharan, V. P. An Algorithm for non—ne ative norm minimal
solutions, Numer. Enngt. Anal. and ggptimizq 9 (1 83 2),

193—232 (1937).

Sreedharan, V.P., Least squares A1 orithms for finding
solutions of overdeterminedfi near equations which
minimize error in an abstract norm, Nnm. Math, 13,
(1969), 146—151.

Sreedharan, V. P. ,Least squares algorithms for finding
solutions of overdetermined systems of linear equations
which minimize error in a smooth strictly convex norm,

,1. Appr 1911111511911 Theory, 3, (1973), 46-61.

Wets, J. B., "On the continuity of the value of a linear
program and of related polyhedral—valued
multifunctions", Mathematical
Programming Essays 1n Honor of G. B. Dantzig, Part 1,
Mathematical Programming §t11113124 ,a publication of the
Mathematical Programming Society, R. W. Cottle, Editor,
North Holland—Amsterdam, October 1985, 14—29.

76

. '.
Ia-I' 2. .1

 

 

nICHIan STATE UNIV. LIsRnRIEs
lllll"WIWilli”MWll"Ill“!lllNIHlIllHllllllll
31293006096642