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

..__,". ..--_....._ _..,

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...