Browse Prior Art Database

QUADRATIC PROGRAMMING WITH M-MATRICES

IP.com Disclosure Number: IPCOM000148281D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12

Publishing Venue

Software Patent Institute

Related People

Luk, Franklin T.: AUTHOR [+3]

Abstract

..__,". ..--_....._ _.., ".._...,__I-. . WITH M-]%TRICES Franklin T. Luk and Marcello Pagano Department o E Computer Science Cornell UniversityIthaca, NY 14853 Harvard University Sidney Farber Cancer Institute Boston, MA 02115 *This waork supported in part by U.S. Army Research Office Grant DUG 29-78-G01079. QUADRATIC PROGRAMMING WITH M-MATR:ICES Fkanklin T. Luk Department of Computer Science Cornell University lthaca, NY 14853 and >:arcello Pagano Harvard University Sidney Farber Cancer Institute 44 Binney Street Boston, MA 02115 Accepted for publication in Linear Algebra and its Applications. This work supported in part by U.S. Army Research Office Grant DAAG 29-7840179. Ahseact: In this paper, we study the pmblwu of quabatic programing with H- matrices. Xe describe (1) an effective algorith for the case where the -'ariahles ere scbjec-t to a lower bound constralnt. and (2) an a?alogousalgc?irh for the case w>ere the variables are sdject to lover and u?peer bands constraints. He demonstrate :he special moaotone behavior of theIt=-are and gradient vectors. The result on the gradient vector is new. It 1-228 us to con5ider a sim?le updating procedure which preserves the monoton- iciry c: hth vectors. The procedure oses the fact tlat an ?!-aawix has 2 7s:-negative ilverse. Two new algorith~s m e then construc*.ed by incorpor-a:ins this updatin~ procedure into the two given algo~iths. Wt? give numerical ex*-?les 5 i r h show ?ha: the new n~ethoCs can be mors efficient thsn the origiziai

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 24

..__,".

  -
------ ..--_....._ - _..,

".._...,__I-.

.

*

WITH M-]%TRICES

Franklin T. Luk and

Marcello Pagano

Department o E Computer Science
Cornell University
Ithaca, NY 14853

Harvard University
Sidney Farber Cancer Institute Boston, MA 02115

*This waork supported in part by U.S. Army Research Office Grant DUG 29-78-G01079.

[This page contains 1 picture or other non-text object]

Page 2 of 24

[This page contains 1 picture or other non-text object]

Page 3 of 24

QUADRATIC PROGRAMMING

WITH M-MATR:ICES

Fkanklin T. Luk

Department of Computer Science Cornell University lthaca, NY 14853

and

>:arcello Pagano

     Harvard University Sidney Farber Cancer Institute 44 Binney Street
Boston, MA 02115

Accepted for publication in Linear Algebra --

Applications.

This work supported in part by U.S. Army Research Office Grant DAAG 29-7840179.

and its

[This page contains 1 picture or other non-text object]

Page 4 of 24

[This page contains 1 picture or other non-text object]

Page 5 of 24

Ahseact:

--

    In this paper, we study the pmblwu of quabatic programing with H-
matrices. Xe describe (1) an effective algorith for the case where the -'ariahles ere scbjec-t to a lower bound constralnt. and (2) an a?alogous
algc?irh for the case w>ere the variables are sdject to lover and u?peer bands constraints. He demonstrate :he special moaotone behavior of the
It=-are and gradient vectors. The result on the gradient vector is new. It 1-228 us to con5ider a sim?le updating procedure which preserves the monoton- iciry c: hth vectors. The procedure oses the fact tlat an ?!-aawix has 2
7s:-negative ilverse. Two new algorith~s m e then construc*.ed by incorpor-
a:ins this updatin~ procedure into the two given algo~iths. Wt? give numerical ex*-?les ~ 5 i r h
show ?ha: the new n~ethoCs can be mors efficient thsn the origiziai

-.

c -28.

1. . -

Introduction
In this ?ape? we eddress the lover ar.5 n;:er So-;aCs

quadretic progrw

subject to cz_xsd,

-here A i s an n x 3 :.!-z~Lrl~ e?l 5, c 2 %rĂȘ-~.zc>o~s.

:.f

- -

important specie1 cese of (1.1) is the linear cc:;?-rer.t%ri:y ;?-st:?- --,

in which _c = 2 end _d = 2:
? + -I?

,

. -

Y-An xtt.

6-2

X

subtict x 2 2 .

-


(1.2;.

(1.1,

a d (1.2) find eg:li?zt:c)?.s in tke r:r-erlctl zcl-&,ion of frze ts-;:.icy: oroblems for elliltic parfia: .'lfferen%ial ec_.:l-t:onr. S:.I-?~ ;rr~'1:=~~ include various type: of Dfr:chlet problc~s
with c5ct%z:es (17; ar.- ' ilC]), and nodels of the jourcal bearing [ 5 ] and of the a~-:Lic&lrlcz

We assme that the uetrix A is large end slarse. p.2 pmlj7_er_S

.

                             - tf.
torsion to a bar [ 11.

DFFINITIOR 1.1 [11, p. E5]. A real sqmre m~trix R = [a ) uitt
i j

aiJ ( 0 for a11 i f j is an !.!-~atrix if A is nonsire~lar, an.?

[This page contains 1 picture or other non-text object]

Page 6 of 24

Xe lose no generality by restricting our attention to smetric X-zatrices, fot re can re?lncc the ~ a t r i x A by its symmetric part
t
!A + b...