15 1 31 15 11 . . , SQCQP , . , , , . . , . SQCQP , . , SQCQP .SQCQP , , SQCQP . , , . ,SQP , , .SQP , , . , SQP . , , , ,

! "

#$ &%('*)

+,

11

- .

+,

15

- /0

132 4

+,

15

-

1

5

31

6879

<>=

,

?A@CBEDGFCHJILK8MONCPRQTSEUWVAIWXZY\[A]AXA^_HOBa`cbOd

,

eAfWXcgihkjlVmICn8oqpAr MsjJtcuEMmbWdmvAdEwsH

.

^xqtqyqz

,

eqfqXTgJh|{~}€‚JƒT„…‡†CS~Bqˆ

,

fq‰qŠT‹~tEŒ€OuŽq

tE‘k’Ua“A”k–•kH

.

xAt_—L˜™MR“A”C{ašCyi^|RƒT„ …›†œSCu8ad

,

žAŸA WŸWŽA¡W¢¤£

SQP

^¢_¥U

—A§¦¨™•LdiwcH

. SQP

^¢œˆ

,

©Aª|tE«A¬q­AeAfWXcgihCBafA‰(®•

,

V¯RtR°œ±W}GtE²A³|na´W©AŸ

µq¶

^sHaU

,

uav~BW·c¸º¹»Pi¼W½ku~¾J¿~•kHiÀmÁœUWÂsÃWd µq¶

‘œÄœUW«mÅ|B~ƺRMœbWdœqÇ ˜‚È

uUœÉCH

.

^È®•Lˆ

, SQP

¢mUOÊqËcgRhGtiÌmÍAÎAÏCB8ÐTgJh|t8©WŸq²AÑC{a‰OwLH~yAzOB

,

^{ÒWviÓÔÈq}

•kHcjJtAnqɜH_ÈWuRUW¦¨Õ•d8wsH

.

ÈitaÖ|B~ׯØJWd

,

^²AÙ

,

ÌqÍqÎAÏGta qŸq²qÑC{aÚ>ÛÝÜa•kH ÈAuina·c¸€¹§Pi¼A½|{|ÞißW^THEžqŸq qŸAÌqÍq qŸqŽq¡W¢à£

SQCQP

¢_¥Gu~¾J¿a•kHRáq¢œUWâq㯍

•ÔdEwTH

. SQCQP

^¢|ˆ

,

fq‰|nCvqHmgihœUWäqËqåqæ_MœçiŽq¡Tgih|B|è|¨Õ•kH8U

,

^oAéTê

µq¶që

u

ìAí

êJ WŸ

µW¶Aë

UOîAïcêaBEðAñkÝ•ÔdiwTH

.

^~òœ

,

ócô~tEeWfAX_gJhCBaõ_~d

SQCQP

^¢C{8f

‰c~y_u§w˜÷öAøCˆœÇEùOúCû»•diw|MEw

.

üAöAøWýGtcØiêaˆ

SQCQP

¢CtióqþC{aúOw

,

^ÿ|t

ËCBaÀ8•ÔHJÀAócê~MCgRh|B8õ_OdafW‰W^cHGÈWuJnmÉmH

.

^<>= Ðu8Wd Aÿ|B8DWwGd

,

^·aƒ

…l>Y ·WƒOƒLPGua¾i¿a•kHON_P‚QS8UA‰AwÔ¨ •Ôd8wTH

.

^{·Oƒ …Ձ>Y ·Wƒ}

aƒTPanOˆ

,

_t! "œU$#%CB&'TOɘ›yAz

,

$Gt ()|{af*CB!+

,

^cH.-q“qUCÉmH

.

ȇ•ÔÇ~nsÈJtmgJhCBaõcOd/AX(®•yA‚ƒT„…®†œSaˆaâAã( •(diwcH8U

,

^-0

cj§¼1TêCu»w ˜®ûAFqnqˆqMEw

.

üqöqøAý|nAˆ

,

ÈitEeqfAXTgJh|B~õ_Wd

SQCQP

^¢|{~fW‰T

,

^x

t!2q‰

ë

{CWzi^

.

1

⁵⁶

1

2

7898:;98<=>

1

2.1 SQCQP

¢GtqJƒs„…‡†CS

. . . . 1

2.1.1

^gih

. . . . 2

2.1.2

^ÊqËTgih

. . . . 2

2.1.3

^?@qÖ_t!AB

. . . . 3

2.1.4

Jƒs„…‡†œSWt!CD

. . . . 4

2.2

^{îqïcê µq¶që}

. . . . 5

3

EFGHJIK$LNMOPQR.S

5 3.1

^TU

. . . . 5

3.2

^V ¹XWqeqfqXTgih_t ,Y X

. . . . 6

3.3

`ZGtAiƒT„…™†œS

. . . . 7

4

^{[\]^}

8 4.1

,_` ¸NabcAt+ ,

. . . . 8

4.2

^ódAáq¢

. . . . 9

4.3

^ódeq½

. . . . 9

4.4

^fg

. . . . 10

5

^h6

11 A

^ijR.S

(2.3)

kl98m<=R.S$nkop

13 A.1

 qŸqqŽq¡Tgih

(SOCP)

^uJˆ

. . . . 13

A.2 QCQP

^t

SOCP

^rTtsq­

. . . . 14

B

]^ht$kJuvwIxM!yz

15

B.1

?@AÖ_tAB_t8I{

. . . . 15

1

^|~}

< =

.

?q@_t!qËGBEDGF|H~NGPRQcSOˆ~VqIqX Y [q]qXGti©G{my€œbWdiwTH

.

^xqtWMqòqn

,

^ó

ôaBaÂcÃqHReAfAXcgih(jlVqICn~oApAr|MTjJtGuiMqbOdqv~dEwLH

.

^xAtAyWz

,

eAfWXcgJhC{~}¯Rƒ

„…®†œSaBqˆ

,

fA‰AŠc‹~t8ŒkauŽA|t8‘k§UW“A”(®•(H

.

xWtT—L˜®ME“q”C{aš|yi^_RƒT„…®†mS uaWd

,

žqŸq qŸmŽq¡q¢ £

SQP

^{¢c¥aU(—œ ¦(¨Õ•ÔdEwH}

. SQP

^¢|ˆ

,

©qªcta«q¬m­qemfqXTgEhGB fq‰¯›•

,

^{oqéTê µq¶Aë} {2A^TH|uquCjB

,

V¯JtE°q±q}Gti²œ³|n~´q©qŸ

µq¶

^TH8U

,

^u8vWBa·c¸

¹’PE¼q½(u~¾E¿a•€HiÀœÁœUAÂsÃAd µm¶

‘mÄCUq«mÅGB~ƺJMœbWdCmǘ‚ÈquRUGÉmH

.

^ÈՕˆ

, SQP

¢œUWÊmËTgihctaÌqÍmÎqÏ|BOÐTgihct8©qŸm²qÑG{O‰WwTHAymzAB

,

ÒAviӀÈm›•ºHcj‚tAn|ɜH_Èqu‚U

¦(¨™•(dEwTH

.

^·c¸¹ Pi¼q½G{CÞ8ßW^THAymzAB

, SQP

¢C{$‚A^sHEáq¢|U~w€„ƒ|òOâm㯍›•kdEw H8U

,

x’•¨Et8áq¢GnWˆœRƒs„…®†CS~ˆ~[q]GMLjtcu8MCH

.

^©qá

,

ÊqËcgih|B~ÌqÍqÎWÏ_t8 qŸq²qÑ {~Ú Û›Ü~•¯HcÈquEnO·T¸¹’PE¼q½_{|Þ8ßGn|vœHiåmæ

ë

U…†€®•kdaD Û

[4],

ÈEt~ÖGB~׺ØEAd

,

²qÙ

,

ÌqÍqÎmÏ_t8 qŸm²qÑG{~Ú>ÛÝÜO•kHGÈquin~·T¸º¹§PE¼A½G{|ÞißA^sH8žqŸm qŸqÌqÍm qŸqŽm¡q¢

£

SQCQP

¢_¥Gua¾J¿a•kHRáq¢œUWâqãk›•(dEwcH

[2]. SQCQP

^¢|ˆ

,

fq‰|nCvmHAgihœUWäWËqåqæ_M çJŽA¡cgihCBœèC¨™•(HiU

,

^{oAécê µA¶Wë u ìAí êJ WŸ µA¶Aë} UOîWïcêOB8ðAñ( •ÔdED Û

,

^{·G¸€¹ P}

¼q½_tmÞißuqumjRB

,

^µq¶ ti‘€qjˆ‡‰CnCvWH

.

^Oòœ

,

óTôOt8eAfqXcgihCB~õcOd

SQCQP

^¢G{

fA‰_Oy_u§w ˜ öWø|ˆœÇEùOúœû•Ldiw_Miw

.

üAöWøAýCtTØiê~ˆ

SQCQP

¢|tEóAþC{aúOw

,

^ÿ

tEËCB~Ài•(HJÀAócêOMmgJhCBaõ_WdEfA‰W^cHGÈWuinqÉmH

.

<>=

ÐÔuaOd WÿGBEDOw_d

,

^·~ƒ

…l>Y ·OƒŠ!WƒsJ‹LPcu8¾E¿8•€H~NGPJQsS8UA‰Aw¯¨™•(dEwH

.

^{·Wƒ …l Y ·Wƒ}

aƒTbLP~nOˆ

,

Gt "mU$#%CB!&'cOɘ›yAz

,

$_t! (.)C{af*|B + ,

^TH-q“mUCÉmH

.

ț•kÇ8nLÈRtœgRhGB8õc~d!/WX¯ •ÔyWRƒT„ …‡†œSaˆaâWãk®•diw_H8U

,

^-

0cj ¼l1TêGu’w˜®ûmFqnqˆmMEw

.

üqöqømýGnqˆ

,

ÈitaeqfqXsgih|B~õcqd

SQCQP

^¢|{~fq‰c

,

xAt2q‰

ë

{COzE^

.

üqöqøqý_nqˆ

,

Çb0JŒŽ|n

SQCQP

¢GtqJƒs„…‡†|S|uExAt µœ¶që

BƒAw_d$‘’J^TH

.

^Ÿ|B

,

Œ”“•Gn

,

ÿ.GBEDqwGd~óTô~BaÂcÃmHieqfqXcgih|{–—c

,

^xqt

,Y

XGB!ƒAwTd!‘’J^TH

.

^Œ

˜

CnAˆ

,

^ŒŽ“XCn

,Y

X_OymgJhCBEõcOd

SQCQP

¢œ{8fA‰_Oy _™

ódGteA½C{8öAøG

,

^x»•

BaõA^TH.fgG{!š›|H

.

^eœGB

,

ŒžŸGneqïG{!D LH

.

2

^¡ 4£¢¤4~¥£¦~¢¤4~§£¨¤©

Èit!Gnqˆ

,

ª_zABažqŸq qŸqÌqÍq qŸqŽq¡q¢à£

SQCQP

¢c¥WtqJƒs„…‡†CS~{‘’A

,

^Ÿ|B

,

^x

t8îqïTê µq¶që

BƒAw_dD LH

.

2.1 SQCQP

«”¬®­°¯²±´³µ·¶

SQCQP

^¢|ˆ¸¹

[2]

^B8DAwcd

,

äqËqåqæ_MCçiŽq¡Tgih|B~õcWdaâq㯍›•ÔdawsHEU

,

^{Øiêº _ U}

«Tçº

_

nqɜHi°q±|B~õ_WdLj§fq‰qåAæ|nmÉCH

.

^OòC

,

ÈAÈJnqˆ»¼GtWymzAB

,

çRŽq¡TgihGBCè

,

Wd!½qïG{¾GzœH

.

2.1.1

^R.S

üqöqøqýGnqˆƒ¿st8eqfqXTgihC{~Ú>ەÀ˜

. minimize f (x)

subject to c i (x) ≤ 0, i = 1, . . . , m (2.1)

ÈmÈin

, f : < ⁿ −→ <, c i : < ⁿ −→ <, i = 1, . . . , m

ˆ~ LÞ.ÁÂsêiämËqåmæ_MCçº

_

u’^LH

.

^©mª

BCçiŽm¡TgihctaÌqÍmÎqÏ|BmˆÃÄ

Y

ÌqÍctÅqòmB~¬q­_tÄ

Y

ÌmͯjÇÆLǒ•kH8U

,

ÈWÈinqˆ»¼_t yAzOB

,

ÌOÍqÎAÏCˆÃÄ

Y

tTjRtOBCèWH|u’^cH

.

ÈÉ~t.½mïCˆa¬A­|t.Ä

Y

ÌAÍmUÊËW^THJ°q±CBsj

ÌÍ

nœvmH

.

^gih

(2.1)

BaõTOd8Ÿ_t!Î

,

{+GFœH

.

ÏÐÒÑ

1.

^gih

(2.1)

ˆÓGnmMEwmeqfq}GtÔm±|{Ճ

.

2.

PV!ÖcmÎqÏ|{~š_yE^

x ¯ ∈ < ⁿ ,

^{^GMAû×}

, c i (¯ x) < 0, i = 1, . . . , m

^{{~š|yE^}

x ¯

^{U$ÊËA^TH}

.

gih

(2.1)

^BaõTWd

, l 1

^Ø tÙÚGM.ÛÜAƒmQÞÝ$º

_

F r : < ⁿ −→ <

^{{aŸGtT—˜‡B ,ß ^TH}

. F r (x) := f (x) + r

m

X

i=1

[c i (x)] + (2.2)

ÈqÈJn

, r > 0

^{ˆÛÜAƒmQ°Ý `} ¸NabcWnmÉ Û

, [·] +

^ˆ

max{0, ·}

^{{àáR^LH}

.

^{Î ,žâ tlÉ~nqˆ}

,

^ã

ËAo_viw

r > 0

^Baõ_Wd

F r

tEÌqÍ|MmieäA}Ôuagih

(2.1)

tJemfA}œUO©åW^cH_ÈAuUWËCòCb~diw H

[1, §5.5].

ÇWyNæWPV!Öc.mÎmÏ_{~š_y8^qÖ

,

^_Mmû×mPV!Öc.mÖCUÊËA^sH_u8v

,

^xWtԗL˜

M8ÖG{2TèqÞWt.çÂcv~nOŽqA^THOJƒs„…‡†CS8U¸¹

[3]

naâq㯍®•dEwTH

. 2.1.2

^ijR.S

?@_B8Dqwcd~Ö

x ∈ < ⁿ

Uš›T¨l•ÔyTu’^sH

. SQCQP

¢ctaÊqËsgihG{

,

^ŸctCgEh

(2.3)

^u~

d

,Y

XO^cH

.

^{^GMWû×}

, SQCQP

¢œˆ?@GBEDAw|d

,

^ÊWËcgih

(2.3)

^{

d

BƒWwTdEeäqX_

,

^è

é

áêO{ë

,

^TH

.

minimize g(x) ^T d + 1 2 d ^T Bd subject to c i (x) + g i (x) ^T d + α i

2 d ^T G i (x)d ≤ 0, i = 1, . . . , m (2.3)

ÈqÈJn

, α i ∈ [0, 1], g(x) := ∇f (x), g i (x) := ∇c i (x), G i (x) := ∇ ² c i (x) ∈ S ⁿ , i = 1, . . . , m

^u



, B ∈ S ⁿ

^ˆ‚

,™

u»^cH

.

^yOùC

, S ⁿ

^ˆ

n × n

õìAúíîï|t.Ôq±|{ðO^

.

^ÊAËcgJh

(2.3)

^ˆœç

 mŸœÌqÍq mŸqŽm¡TgEhGnmÉCHOòs¨

,

ÄñcM8 qŸlqqŽm¡TgEh|BsòGnCv

i ,

ó8Öm¢|{~‰qwGdO¼1sêOB }€WÈAu‚UCnœvAH

.

gJh¤£

2.3

^{¥RB!Æ_Ç •(H}

`

¸la„Nc

(α i ) ^m _i=1

^ˆaÊAËGgJh

(2.3)

^{t8óWúWåAæ ë UOðWñ( •kHG—s˜}

,

^Ÿ

i^ô‹õöø÷

,

^ùûú

A

^üXýÿþ

.

t8p

(2.4)

^{BL—ibAd zc¨™•kH}

[2, Lemma2.1],

s 1 ≤ 2s 1 = ⇒ α i = 0, i = 1, . . . , m s 3 ≤ 2s 1 ≤ s 2 = ⇒ α i =

( 1, i ∈ J 0, i / ∈ J s 3 > 2s 1 = ⇒ α i = 1, i = 1, . . . , m

(2.4)

ÈqÈJn

, J

^D¯—

s 1 , s 2 , s 3

^{ˆ Ÿ}

Y

BL—ibAd ,ß

®•(H

.

J := {i|θc i (¯ x) ≤ c i (x)}, (2.5) s 1 := max

i:c

i

(x)>0

c i (x)

c i (x) − ϑc i (¯ x) , (2.6)

s 2 := min

min i∈J

c i (x) − ϑc i (¯ x) κ i

, 1

, (2.7)

s 3 := min

s 2 , min

i / ∈J

−2(ϑ − θ)c i (¯ x) κ i

(2.8)

yAùG

, ¯ x

^{ˆÎ ,}

1

n$š›L¨Õ•ÔyGPlVÖc.œÖ

, θ ∈ [0, 1)

^u

ϑ ∈ (θ, 1)

^{ˆàGB , ›•ky ` ¸}

a„c

, κ i := (¯ x − x) ^T G i (x)(¯ x − x), i = 1, . . . , m,

^{u’^TH}

.

ÈJtCu8v

,

^ÊOËcgRh

(2.3)

ˆ|PV.ÖcAÎWÏ|{Eš ~^cHJóOúAåWæO}C{!ÕN×

[2],

~¨RB’ƒCNœY

>Y cAÎqÏ

(KKT

^ÎWÏ

)

{aš|yi^_¸G¸

_

¯¹ ƒ

v = (v 1 , . . . , v m ) ^T

^UÊ

ËTWd

,

Bd + g(x) +

m

X

i=1

v i (α i G i (x)d + g i (x)) = 0, c i (x) + g i (x) ^T d + α i

2 d ^T G i (x)d ≤ 0, v i ≥ 0, (2.9) v i

c i (x) + g i (x) ^T d + α i

2 d ^T G i (x)d

= 0, i = 1, . . . , m

U>ۃkÈqu‚UW¦k¨Õ•dEwTH

[8, Theorem 28.2] .

^Èit

(d, v)

^{aÊmËTgih

(2.3)

^t

KKT

^Ö(ua¾

.

2.1.3

^$k

d

^{~ÊqËTgih

(2.3)

taeqfq}Ôu»^TH|u

,

^ŸGt?@

x ^new

^{ˆGP‚Q !}

β

^{~‰Wwcd

x ^new := x + βd

ubšJ›_¨Õ•(H

.

JƒT„…®†œSOt8oAéTê µq¶Aë

{8ðqñW^THWyqzWB

, β > 0

^{ˆaŸ Y} {8š_yi^k—˜®B"q¿

•kH

.

F r (x + βd) − F r (x) ≤ σβ( ¯ F r (x, d, α) − F r (x)) (2.10)

ÈqÈJn

, σ ∈ (0, 1)

^{ˆ~f$#AM ,_}

, α = (α i ) ^m _i=1

^nœÉºÛ

, ¯ F r (x, d, α)

^ˆ

G(x) := ∇ ² f (x)

^{Lj×Jw_d

Ÿ Y

nmÉqy›T¨‡•kH

.

F ¯ r (x, d, α) := f (x) + g(x) ^T d + 1

2 d ^T G(x)d + r

m

X

i=1

h c i (x) + g i (x) ^T d + α i

2 d ^T G i (x)d i

+

d

^ˆ~ÊqËTgih

(2.3)

t8ómúqåqæq}|nmÉCHaòT¨

, c i (x) + g i (x) ^T d + ¹ ₂ α i d ^T G i (x)d ≤ 0

^uEMœHOtOn

, F ¯ r (x, d, α) − F r (x) = g(x) ^T d + 1

2 d ^T G(x)d − r

m

X

i=1

[c i (x)] ₊ (2.11)

U>ۃ

.

ÈqȂn

,

^à|t

x ∈ < ⁿ

^u

α = (α i ) ^m _i=1

^B~õT~d

,

^ÊqËTgRh

(2.3)

^t

KKT

^Ö

(d, v)

^{UÊËO^THGu}

Î ,

^TH

.

^~¨8B

,

2B − G(x) +

m

X

i=1

α i v i G i (x) µI (2.12)

{aš_yE^¯—(˜›M ,_

µ > 0

^UÊËTOd

, r ≥ max i v i

^U>ۃu‹Î

,

^TH|u

,

^Y

(2.11)

^t%&G{

g(x) ^T d + 1

2 d ^T G(x)d − r

m

X

i=1

[c i (x)] ₊ ≤ − 1

2 µ k d k ² (2.13)

u('ñGnœv

,

^{Ÿ Y ts—L˜‡B}

, d

U!ÛÜqƒmQÞÝ$º

_

t*) +qáê|uEMCH|ÈquRUawJ›|H

[2, Lemma3.1].

F ¯ r (x, d, α) − F r (x) ≤ − 1

2 µ k d k ² (2.14)

8¨JB

, d 6= 0

^nWɒ•|¿

,

ãOËäԍ™wO^$ _dWt

β > 0

^BEõ_ad

,

Y

(2.10)

^U,Û-$ƒ

[2, Lemma3.2].

2.1.4

./0214365k78

SQCQP

¢GtqRƒs„…‡†œSOˆ

,

ƒ¿Tts—˜®BC9¯ •;:

.

step0:

^{ª‡ <}

x ¹ ∈ < ⁿ ,

^ÛÜ=> Ý@?6A6BDCFEGªH I

r ⁰ ∈ (0, +∞),

^JK

γ ∈ (0, 1), θ ∈ [0, 1), ϑ ∈ (θ, 1), σ ∈ (0, 1)

^L;MN

,

O PQERCST6U*VFWRX

x ¯

^U,Y,Z

. k := 1

^{[(L \}

.

step1:

^{]JI^_`a}

B ^k

^UbY,Z

. (2.4)

^cbdebf

α ^k = (α ^k ) ^m _i=1

^UbgJ,XF:

. (x, B, α) = (x ^k , B ^k , α ^k )

c*^ X$:hi$jk

(2.3)

^U,lnm

, KKT

^<

(d ^k , v ^k ) ∈ < ⁿ × < ^m

^{U*o pq:}

.

^rts

, d ^k = 0

^uv

wFxy$z

ii .

^{{}|4u~ q wFx}

step2

^

. step2:

€ =>ƒ‚(?FAFB(CnEU

r ^k :=

( r ^k−1 r ^k−1 ≥ max i v ^k _i + δ

^G„

max i v ^k _i + 2δ

^{{…|4u~b†$„}

(2.15)

[*sf‡ˆns

,

‰Š6U*VFWRXŒ‹FG

β ^k

^U

{1, γ, γ ² , γ ³ . . .}

^Ž$YZ

.

F r

^k

(x ^k + βd ^k ) − F r

^k

(x ^k ) ≤ σβ F ¯ r

^k

(x ^k , d ^k , α ^k ) − F r

^k

(x ^k )

{Œsf

, x ^k+1 := x ^k + β ^k d ^k , k := k + 1

^[‡ˆFs

, step1

^

.

ii^‘“’•”

, (x

^k

, v

^k

)

^{–@—•˜š™}

2.1

^{› ’}

KKT

œ•ž Ÿ¢¡“£,¤

,

^¥§¦©¨

x

^{k–ª—•˜š™}

2.1

^› ’¬«“­¯®4°t±³²

.

2.2

´¶µ¸·º¹…»…¼

½©¾

, SQCQP

¿6G*À$ÁÂÃÄcp †$fÅÆÇ:

.

À$ÁÂÃÄc*p†$f È

,

^{‰6G*J É}

1

^ÊË2

w

fb†$:

[2, Theorem3.1].

ÌÍ

1 SQCQP

¿6cÎMnϧЌÑ;Ò

w

W,<a

{x ^k }, {B ^k }, {α ^k }

^{c^$s f}

,

^<a

{x ^k }

^ÈÓÔušÏ

,

^Ò

c

,

^XÆÕfG

k

cp †nf*‰ŠŒÊÑÖÏØ×p;Mº|¯~

µ > 0

^[

µ 1 ≥ µ 2 > 0

ÊÙÚ X$:[©ÛJX$:

. 2B ^k − G(x ^k ) +

m

X

i=1

α ^k _i v _i ^k G i (x ^k ) µI

^Ž*p

µ 1 I B ^k µ 2 I

{ GF[,m

, SQCQP

^¿ÈjbkÝÜ

2.1

Þ G*‹ßlc*L†$fàá XÕ:,Ž

,

^rbs$\tÈ

, {x ^k }

^GâãFGäå

<6Èjk

(2.1)

^{G*‹ßlº[b~:}

.

‰6c

, SQCQP

¿6G*æç$Á~*ÂÃÄc*p†nf,Åƺ:

.

æç$ÁÂÃÄc*p †Ff

,

‰6GbÛJÖè G$r[u JÉ

2

ÊÑÖÏ×p2é [tÊËΏ

w

f†Õ:

[2, Theorem4.1].

ễë

1.

^jk

(2.1)

^È

,

^vŒ:RJK

µ ^∗ > 0

^{c*^$sf}

,

H (x ^∗ , v ^∗ ) µ ^∗ I, ∀v ^∗ ∈ V ^∗

UtìWX‹ßl

x ^∗

^Unr³p

.

^W*íŒs

, H (x, v) := G(x)+ P m

i=1 v i G i (x), V ^∗ := {v ^∗ ∈ < ⁿ |(x ^∗ , v ^∗ )

ÈjkÝÜ

2.1

^ÞG

KKT

^<6uvŒ:

.

2. G

^{L M§N}

G 1 , ..., G m

^È

x ^∗

Gîïc*L †6f}ðñòºóôõöuv:

.

ÌÍ

2 SQCQP

¿6cL †6f,÷H <

x ¹

^U,‹ßl

x ^∗

Gø iî \©cYbN

,

^Ž*p

,

^XÆ$fG

k

^{cp †$f}

B ^k := G(x ^k )

^{[(X wnx}

,

^{ÐÑ;Ò w :<a}

{x ^k }

^È

x ^∗

^c

Q-

^{è‰ÂŒÃX$:}

.

^Ò,bc

, dist(v ^k , V ^∗ )

^È

ù c

R-

^{è‰Âà X$:}

. ⁱⁱⁱ

3

^{úüûþýüÿ}

u È

,

cbL6q:nÁ,~jtk6Gp6uv:

,

!#"GbÐ$ :&%'(=*)uG+

=,%-.'šð0/213+=,%ñ=,/5476ÎOcbL6q58PtC 9;:Œ‹ß#<Õjkc,p †Õf>=@?s

,

A‹ß#<Õjk [*sfGJŠ#<U,` |

.

3.1

^BDC

#

uFE †ƒ

w

8R† \@pŽG>EGc*p†nf&=@?RX@8

.

•

^PtC29;:

PC29[tÈ

,

6GHIŽn7JIc#K

w

íqGML#NŒÊ]Oc>PH;Ò

w

WŽU,ãQ©X8nr

G uv;Ï

,

^PtC29R:È

,

ò6Ot>,S#TVUŒCW.X#YuGPtCZ9¯G:FU*ã@QRX@8

.

iii

dist(v, V ) = min{kv − vk | ¯ ¯ v ∈ V }

•

+,=,%bñ=,/[476ÎO

+=\%*ñ=,/54V6ÎO[È&]KFGUC#WÊ^._#`#a6U[b„cFcÓ$s fF`U` |té[bU†

|

.

^éGW#d

,

^{e w} WFf#gK#h#iU,Ójc&k#[email protected]Êv.8

.

•

+,=,%-`'šðn/

]`OcŒÈ

,

+=o%-`'…ðp/>q.r#sŠUÕ[† |

.

+=o%-`'…ðt/q.r`sŠ2[È

,

^L#N6Uu]KnG

vw

-#'¶ðx/F[>y xw

8z{6~-#'¶ðx/ciqf>PHX@8Ms ŠuŒv`8

.

^vw -#'¶ðx/ GbKU

N

^{[DX wnx}

,

H##I6cL†FfV|¶‚M}E©=[L#Na6U

N

~G>a##c&q#€ns

,

^punc

,

^{G>

U

N

~FG>‚6~.8Mf#gKFG v`w

-`'šðp/GF:c&q#€FsfF+,=,%-`'šð0/q#r##6U*ÐÑ X

8

.

^{{ G&ƒ}

,

„CD…ªQ†EtCu‡=$U>ˆ#‰nsfU>H#X@8

.

^J#IuÈ

,

ŠFG‹ŒcÇMe,f



U*` |

.

•

+,=,%-`'šðn/Ž1+,=,%ñ,=,/[4V6ºO

+,=,%bñ=,/[4V6ºO,cbL †$f

,

+,=,%-`'šð0/Fqr#sŠ6UF#E$sWÕrRG,u

,

^]KFGMUCWÊ

]K6Gu-.'šðn/U&cÓnsf#6U*` |‘sŠ6uv`8

.

+=,%#-#'šðp/Ž1’+=\%ñ=o/*4“6ºOuÈ

,

]KFGUC#WÊbŒ„,c&]K6G#-#'šðt/U&cÓ X,8 W d

,

~o”G>H###@ *u&!#"ŒÊÐ@$

,

L#NŒÊXÆ$f*]#Oc&PHƒÒ

w

8F•q uÈ~b†

.

^Û6cF#FG.–

—

cF˜™ŒÊŒ~†º[(X w6x

,

^{UCW6GFFG`– — UF)š@8é[Ru}

,

^{PHƒÒ w} 8LN›U>œ#ƒÒ0ž\86é [©ÊuŒm`8

.

^sŽs

,

#6cÈFŸuUCWFG[–

—

cÈ& É$Á~>˜@eÊv Ï

,

v*8VUCWnG`–

—

UF)#š

Wn[m.b#$-`'šðn/U&¡`E X,8¢FGUC#WnGPtC 9¯È5£ÊFefŒs

½

|¯W`d

,

¤¥6c&`FG`–

— U

)š8é [Ru ȌjRkÈ*lgns~b†

.

^sW*Êe,f

,

^{{ w} bG˜™Gnr [RuòO>\S“XY6GPCŽ9¦:U

‹#< X@8nM2|~.–

—

U&§¨d.8é [È&©#m6~Fªkuv#8

.

3.2

«.¬®­u¯±°±²±³µ´\¶2·¹¸»ºo³

+¼,%#-#'šðp/Ž1’+¼\%ñu¼o/*4“6ºOcLFq58M½Ñ`¾#¿n~PtC 9;:nG‹ŒIÈ

,

^HÀ1’J``#

cLFq[8MÁ.Â#L#N`›u&à Ò

w

,

^–

—

c[ÄX@8˜`™Î[7Ş$f‰nGÕMº|¯c*JŠ`<;Ò

w

8né[tÊ Ë2

w

fb†@8

[7].

maximize

C

X

c=1

log 1 + ρ c U

X

u=1

|H u (ω c )| ² p u,c

!

subject to

C

X

c=1

p u,c ≤ P u u = 1, . . . , U

(3.1)

é é©u

,

^Æ.ÇFÈ

u, c

^{È{ w¨Éw} U C#W#Ê#º[-'¶ð0/MÊ6U>ÃFs

U, C

ÈMU C#WKÎ[-'¶ð0/KU ÃX

.

^{½ W}

, H u (ω c )

^È

u

^{ÊÌːGUCWnG}

c

ÊÍË©G&-#'¶ð0/cbLq*8

,

^fgK

ω c = 2πc/C

^GMP#½Ä

K6uv Ï

, ρ c

^È

c

ÊÎË©G-`'šðn/cLFq58Á,ÄMÏKU&ÃÕsfb†@8

.

^[éÐu

,

^jk

(3.1)

^G\ËÁ#Ä

K6È*Ñ#ÄKuŒv Ï

, H u (ω c )

^[

ρ c

^È{

w@Ébw

,

Æ[Ç&Èc&Ò ÙX@8JKuv#8né [cFÓãX@8F[

,

^Š

(3.1)

È*‰FGÕMÕ|¯~.AMÔ#Õ$jk2[sfJŠ#<um`8

. minimize −

C

X

c=1

log 1 +

U

X

u=1

α u,c p uc

n c

!

subject to

C

X

c=1

p u,c ≤ P u u = 1, . . . , U

(3.2)

Wí6s

, n c = 1/ρ c

^È

c

ÊÎËtG#-`'šð0/ cLFq58`Ö,Q×,?ÌØ@CFUvnM•s

, α u,c = |H u (ω c )| ²

^È

u

ÊÎËtGMUCWnG

c

ÊÎËtG-`'…ðn/c*L6q[8MÙ#Ú#ÛU&ÃFsf†@8

.

ééRu*Š

(3.2)

UF#c&Ü$sW>ÝcF#Þ#< X@86é [U&ß[Ç[8

.

#Þ#<c.àsf

,

^{‰Gné[UFß#á}

X@8

.

1.

^Š

(3.2)

^{GâËÁ`ÄbK6È}

,

XnfG#-#'…ðt/ cp†nfuã`ä6c6PtC 9 GF:6U$[,ef†@8,Ê

,

^`Fc

È#-`'šð0/ G* ,c&å#æ#ç#èŒÊ,ÙÚ X@8F[éß5Ç*8sÊÍêìë6uv.8

.

^{$éRu

,

PtCZ9¯cF©ìnUFí qfF:U$[&8FMº|4cX@8

.

^{é w U}

,

©ì#íÇPtCZ9R:Î[&y©Zƒé[cX@8

.

2.

UCW.IFŽÕªìÕf

,

Ÿ¨-`'¶ðt/nG5–

—

[sfFî

½

s†ŒIÊ6v*86[7ß5ÇՏ

w 8

.

^{ÕéRu

,

^Ë

Á#ÄKc&©ì`íÇPtCZ9R:íqu~Ç\

,

UCWnG>m#îŒÊß#á;Ò

w

8nMÇ|¯~>ï6UFí6q>[Ç[8

. 3.

åæçèUpqWðñu

,

v8Mò#ó6GŒP©C29³U>ôõX@8l#mG v`87U.öuW;r@ÙÚ X8[÷ß[Ç

 w 8

.

^{néu

,

ø J6GMU.öWnG6P“ö29³U&ô#õX@8$Mº|¯~M˜#™ST6UFù# X@8

. 4.

Ÿ[-`'šð0/c,^X@8“U.öWnG`–

—

c*^$sf

,

v.8MJFG>˜@eU>ú6q*8

.

1.,2.

c>û ãFsf\ËtÁÄRKUFü ]Fs

, 3.,4.

^{ý { w@Éw U>þ}

2,

^þ

3

ý˜™ S Tº[*sfùX@86é[Rc MnÏ

,

^‰¨ýjbk

(3.3)

^UFÿ@8

.

minimize −

C

X

c=1

w c log 1 +

U

X

u=1

α u,c p u,c

n c

! +

C

X

c=1 U

X

u=1

(p u,c − q u,c ) ² subject to

C

X

c=1

p u,c ≤ P u

^{Ü XÆ$f#ý}

u

^{c,^nsf}

.

^Þ

C

X

c=1

log

1 + α u,c p u,c

n c

≥ I u

^{Ü † \ pŽ.ý}

u

^{c,^nsf}

.

^Þ

0 ≤ p u,c ≤ P ¯

^{Ü XÆ$f#ý}

u

^{c,^nsf}

.

^Þ

(3.3)

éé©u

, ρ > 0

È©*ìínPVöŽ9 :Ç[pU#öuW[ý

î,X8–

—

[“ý#©ŒU v“•bXJ KŒuvƒÏ

, q u,c , u = 1, . . . , U, c = 1, . . . , C

^ȓU#öuW

u

Êuî*-F' ð0/

c

^ý#–

—

U v6“•X

.

^{½ W}

, P C c=1

P U

u=1 (p u,c − q u,c ) ²

^{[(† |¦ïÈ}

, 2.

U X,8W#d#ý$rý uv Ï

, p u,c = q u,c

ýF[*mc,‹ Î[~ Ï

,

^U`ö#Wý`–

—

p u,c

^Êî

½

sb†ŒI

q u,c

^ŽÕ

w

8.K*$mR†I6U$[u8FMº|³c~ef†\8

.

^jk

(3.3)

^Èi#¾

¿F~.AMÔ#Õ$jkuŒv.8,Ž$

, SQCQP

¿cºMbefblU&§5d*86é [tÊuŒm#8

.

3.3

^·

!

[7]

^u6jk

(3.1)

c*^Õsf&ø#< Ò

w

W#/M¼#"}ð0×[SÊ$ % Ò

w

fb†o8

.

^ééuÈ

,

^{`ý/¼

"šðn×.SUjk

(3.3)

cÇrªß#E6um#8$MÇ|4c&ü]$sW$rVýU& X

.

,

/“¼'"šðn×.S (uFE †8bhi$jkUjk

(3.4)

[,sfJŠ#<X,8

.

minimize −

C

X

c=1

w c log



1 + X

v6=u

α v,c p v,c

n c + α u,c p u,c

n c





+







C

X

c=1

X

v6=u

(p v,c − q v,c ) ² +

C

X

c=1

(p u,c − q u,c ) ²





 subject to

C

X

c=1

p u,c ≤ P u C

X

c=1

log

1 + α u,c p u,c

n c

≥ I u

0 ≤ p u,c ≤ P ¯

(3.4)

éMýbhiÕjk

(3.4)

^{ýÀqKÈU#ö`W}

u

^ý#–

—

p u,c

^ýìnuv¶Ï

, u

) *¨ýMU`öW@ý*–

—

,

^XF~#•,+

, p v,c (v 6= u)

ÈXÆÕfJŒKÎ[ªì$~Œsfb†o8

.

^éý*hi$jk

(3.4)

È&øJ5ýU`ö`W

u

c*ÄRX@8b‹ß#<

jk2[éß5Ç*86é[tʌum`8

.

ü ]$sW#/“¼#"šðx×[S*U,‰csdX

.

step0

^-

p ¹ _u,c = 0, u ∈ [1, U], c ∈ [1, C ], k := 1

[÷ .<ns

,

^JK

ε > 0

^U*YZ

. step1

^

. step1

^-

p ¯ u,c := p ^k _u,c , u = 1, . . . , U, c = 1, . . . , C

^L;M4N

, u := 1

^[(X@8

. step2

^

.

step2

^-xU#öW

u

c.ÄtX@8h i$jtk

(3.4)

^U*lnm

,

^{‹ß l}

p ^∗ _u,c , c = 1, . . . , C

^U§¨d

, p ^k _u,c := p ^∗ _u,c , c = 1, . . . , C

^{[‡ ˆX8}

. u = U

^{uv wx}

step3

^

.

^{{š|§u~q wFx}

u := u + 1

^[*sf

step2

^

. step3

^-

δ ^k := P

u

P

c |¯ p u,c − p u,c | < ε

^{uv wFxy$z}

.

^{Ò rR~º\ x}

, k := k + 1

^[*sf

step1

^

.

éMý#/¼'"šð0×.S,U

,

/¼'"šð0×.S

1

[Fy©Z;é[cX@8

.

4

^/103214

`

uÈ

,

‹ß#<Çjbk

(3.3)

^{c^ns f}

, SQCQP

¿L MNÌ/¼5"šðp×.S

1

^Uß`E$s

,

^{{#ý6 7FU}

N 8 X@8

.

4.1

¸:9<;>=?¬A@ ·CB±¸

‹ ß<njtk

(3.3)

^{cED ½ w} 8RJKFHGHI÷öKJ,È

,

[ýjRkc*^FsfMLKN,~$rVýu~q wx

~F

~b†

.

^{$étu

,

^ŸJKF'GOI ö'JýFúJ#s P6UE)£,c& X

.

ρ

ËbÁ.ÄK¨ýQ R!S TFUU VX,8bIFuv*8

. log

^ÄKFcÆ è‰,ÄbKFÈ*Iýq*<`›ŒÊW!X6c,

m†¨ýu

, 10 ⁻⁶ ≤ ρ ≤ 10 ⁻⁴

^ò#óº[DX@8

.

w c

^©ì*ÏK6È

1

^Ž$

10

^{½ u`ýZYKI6u}

,

^#Œ [6cFúJ X@8

.

α u,c

Ù#ÚÛU&ÃX¨ýu

, α u,c ∈ (1, 0)

[~.8nMÇ|¯c>^Œ [c&úJ X@8

.

n c

^#Þ6c

10 ≤ n c ≤ 20

^{uv.8ý u}

,

éMý]\#^ýZYKI6uF^#Œ[6cFúJ X@8

.

P u

^ތc

,

^{U#öW[ýZ_5– — È vuw -' ðx/K*ý}

500

`òuóÎ[t~ef†¨8

.

^auÈ

,

^{vw -'}

ð0/*K[ý

480

^`Ž$

520

`¨ýZ\'^,c*Â

½

8nMÇ|¯c>^#Œ[c&úJ X@8

. I u

v`8“ø J[ý-&' ðn/,cb^X8–

—

Ub‹ cs,WF[m&ýPéö294È

5

^~†ns

20

^{òóº[~#8uýu}

,

éMýE\K^,ubG>†c,S,c&úJX,8

. P ¯

^#Þc

,

^–

—

ý*‹I

P ¯

^È

1000

^{ò#óÎ[ŒÒ w fb†\8}

.

auÈ

, ¯ P := 1000

^[dJX@8

. q u,c p u,c

^{ýE\'^,È}

0

^)#)

1000

)@£*uŒv.8,Ž$

,

{#ý]\#^#T,c,Â

½

8nMÇ|4c&^#Œ [c&úJ X@8

½ W

,

^U`öWK

U

^È

5 ≤ U ≤ 10,

vw

-`'šð0/*K

C

^È

8 ≤ C ≤ 16

ò#óujkU&úJ X@8

.

‹#ƒ6c

,

^jk

(3.3)

ý>þÖèpýF˜#™ STU,ß#E X@8VU.öWýøŒJ#s¿U,Å,Æ,8

.

U`öWFc*ÄRX@8MŸ

JK F'G#Iéö'J È^`Œ [Fc,Y Z,ýu

,

U.ö#W.Ê*6UeJX\8ý uȌ~Î\

,

˜`™STÊß`E Ò w 8

U`öWýMfK

s

^U,gJFsf

,

^U`öW

1, . . . , s

c*^$sf>þÖènýF˜#™S TU,ß#EX wnx

MҠ

.

^sW,ÊFe

f

, s

^È

0 ≤ s ≤ U

ýE\'^,u&^#Œ[6cFúJ X@8

.

4.2

^g:hjilk

a[ým#YnÁ,~Ms ¿ÈE)5£uý6[@LÖÏ4uŒv8

.

^½(¾ ‹ ßu<njRk

(3.3)

^{ý7U`öW K}

,

^{vw -u' ðn/K}

,

L;MN$J KFKGKI öOJý,IUL'N~E\O^#Tu*g J X@8

.

^{Œsf

, SQCQP

¿ L;MN¹/“¼'"šð0×.S

1

UßEFsfb‹ ß l[ýbîn lUF§[d`8

.

^W,ís

, SQCQP

^¿È

kd ^k k < 10 ⁻⁶

^{[R~ wx ynz X@86rVý6[}

s

,

/M¼5"šðn×*S

1

^È

ε := 10 ⁻⁶

^[,sf

,

^{yÕz UoJX@8}

.

^{½ W}

,

^{†p w} ý`/¼5"šð0×[S,c,L†nf rOqsruýZ



u#ýoËtÁ#ÄRK¨ýÙ tÊ

10 ⁻¹⁰

)@£[b~eW>ðñ6È

,

‹ß lc*øiîpŒ†nW6[Dì6~s

,

/¼'" ð0×.SU y$z

X\8

.

^~L

,



ȋu

100

^{r ½ uÕ[DX@8}

.

^Wí6s

,

/¼#"šð0×[SCq@u`ýuq rýZ



[È

, step1

^Ž$

step3

^½ u.ýZvÉUÇғX

.

½ W

,

au>E †@8RK I wÈ

, 4.1

u*ÅÆnWs¿u*gJX8

.

^sW*Ê6e,f

,

x ãnÁ,c*g JX8I È

,

^U`öWK

U ,

^{v`w -#'šðn/bK}

C,

^L;MN

,

^[b~.8

.

4.3

^g:hjylz

aÈ

DELL

^{`ý

DIMENSION8200

^)u

, turbolinux 8

ý|}`ý~E€]‚ƒ„

.

^M„

, SQCQP

†

ý‡Oˆ‰EŠ\ý

SOCP

‹ŒŽ]H,„’‘

, Jos F. Sturm

“H”b$,•b–˜—

MATLAB

^™šœ›,

Se- DuMi1.05

^‹ž!Ÿ

,

 Z›¢¡Ž£¥¤H¦C§s™‡bˆ#‰EŠO‹Œ:¨,b„bƒ©!ª

, MATLAB

^™

Optimization Toolbox

^{”« •–'—}

fmincon

^{¬]­,‹EžŸO„}

.

® ¯

ZžŸ'—]­ ° ±,ª

, 4.1

^{²HE³´O„Eµ †} Z¶ ·'¸„'~¹™ ‹

4

^{º » ž ¼O¸„}

.

½s¾j¿]‹Z­ ° ±

§

,

^{­ ° ±’À}

,

^{­ ° ±ÂÁ}

,

­ ° ±uÀœ–5—

.

½s¾#ÄM¾™Z­ ° ±OEÅ'¸©

SQCQP

†

€Z ]›'¡j£Æ¤b¦

§ÈÇ<ÉËÊ

SQP

^{† ‹ZÌ žK¸„}

.

^®¯ Z͞'¸„Z­°±O™]ÎHÏHÐsÑOÒ,€Z½ ™MÓÔ,™EÕHÏÖ ™]Åb׋ZØ

§¥

,

Ù ­ °!±,EÇHÚH—½¹¾KÄM¾˜™  ›5¡j£Û¤,¦™MÜbÝ Þ!Ì ŒÇuÉËÊ

®

‚'ß àâáäã!å,ªæKç‹EØ

ÀèEé–

.

^„

,

ê¿è¾5„ZÓÔH™jëÆì

SQCQP

^{† ǘÉíÊ}

SQP

^{† ™}

kd ^k k

€M ¨›'¡l£í¤¦§î™

δ ^k

^

¬–'—]Ó Ô‹

B.1

²,ÕHÏÖO€E¸©ZéO¸„

.

½¹¾HÄM¾¢™EÕOÏÖ ª

,

ï ð,Zñ òKó]­

k

^‹'€#‘

,

^ô

ðH ª

log ₁₀ kd ^k k

^„ª

log ₁₀ (δ ^k )

^‹'€Eƒ„

.

Øj§:õ

® ¯

žŸO„]­b° ±

­ ° ± ÎOÏ'МÑOÒ ÕHÏÖ

U C S

1 5 8 2

^öC§

2 5 16 2

^ö<À

3 10 8 5

^öuÁ

4 10 16 2

^ö'Ã

Ø÷À<õø­ ° ±€ÙH ›#¡j£í¤¦™EÓ Ô

ù ú

Ó Ô

­ ° ±

SQCQP

†

 ›#¡j£í¤¦˜§

SQP

†

ÜÝ Þ Ì Œ

®

‚'ß à Ü Ý Þ Ì Œ

®

‚'ßà Ü Ý Þ Ì Œ

®

‚Oß à

1 −303.916579 14.1818 −302.934261 8.3152 −303.916579 12.0804 2 −469.028033 46.6824 −468.428752 13.8602 −469.028033 44.0745 3 −328.256035 45.5442 −327.108074 15.6066 −328.256035 49.3501 4 −624.208358 499.5916 −622.889778 24.4265 −624.208358 495.6086

4.4

^û:ü

…¹ý

,

^ö

1

^þ

4

^‹Mÿ'—O€

, SQCQP

^{† ™ b”!—}

.

^„

,

^{¨ÑÞ Ì}

‰ŠÅO¸©

,

,™  ¨›'¡:£Û¤b¦ªZÞÌ ŒÜ ™!” ”! "#u%$ ƒE©Zǎ‘

,

^ñò

ó]­b”&('™

100

óE!)K¸©+*,-'¸©MŸ($]Ÿ

.

^.í¾5ª

,

Ø÷ÀƙÜÝ Þ Ì °,™/10‹]ÿ5—32

,

 ^›

¡’£Æ¤,¦˜§œ™EÜ Ý!ÞbÌ °”

SQCQP

™!½s¾÷É#‘4*657Ÿ

,

^–$98,ì

,

Þ!Ì-,”:'ƒ©EŸ5—.2<;

¿9*>=?39!—

.

^@E¿M

, SQCQP

†

ªZŸý¾™]­!°±,ÅO¸©+*

11

^þ

13

^{óA'¸©]Ÿ#—™}

,

–'— …!™]ñ!ò'ó]­,ª,‰]ŠO™B-C, ªD+24E9FGHK¸$MŸI2KJ3L!©#ÉèŸ

.

H

,

®

‚'ß à!M10]¸©]ÿ#—

.

^ö

1

^þ

4

^‹Mÿ—32

,

 ¹›5¡j£Æ¤¦C§èªñ ò'ó]­”&+'™

100

^ó

!)#¸©EŸ'—N*]¬8'¿ ý

,

O7P!¸©EŸQ$Ÿ

.

^¸;¸

,

ؒ§¥AR10î–#—2

, SQCQP

†

!S´'©

®

‚'ß àZ”TŸU.2¹”8-;,—

. SQCQP

^{† ª}

,

Ÿý¾¢™Z­b° ±O™VW,ÇŸK©X*îñ!ò#ó]­Hª

13

^ó‹

Y

L!©ZŸ$ZŸ'™

,

§œó™MñbòHZ –'—bß!àª! ]›#¡j£Æ¤¦C§ ™Zµb”[\+!]Q$ZŸU2sŸë4.2

”38-;H—

.

^{„^O¸}

,

^ö

1

^þö

4

^‹Zÿ#—(2

,

^_7`A;5¿

δ ^k

™E°,”D724EF!a9'¸ ©ZŸ$EŸb.-2”ˆ;

—

.

^.˾Xª

,

Ü݌!”c,™ZÞ ÌŒH™]Ü-EÜdbŸQe;Fjë; ‹f·–K—Q.2ª9gh3  —

.

^µ

, SQCQP

^{† ™}

®i

ßàb!—”

,

^؎§

,

^À¨ÉO‘

,

‰Š,™BCb”A5'%$!—Ÿ

,

;$u‘j5(Ok$l

©MŸ'—(.2¹”ˆ;,—

. SQCQP

^{m,‹ ®n –'—™!¾Qo}

,

.]™pHq ¼–#—rZb”,b—2sŸ3LH—

.

5

v-w9xy

!ª

,

z!ˆ-{-|$}ZÞ Ì-#‰MŠHÅ#¸©«-~b@í¾C©MŸ#—

SQCQP

^m”

,

^-7--

H‹Eé–U.2]‹!'¸!e

.

^½b¸©

,

€+‚EÇ,ÚH—,—ºH™}]Þ ÌO‰]ŠHEÅ'¸©

,

^<É'‘

«~b@˾˜©MŸ#— ¨›#¡j£Æ¤b¦32%SƒK¸©

,

^ÉK‘]É ŸŒ”ê¿è¾C—3.2]‹K¸e

.

½!™<µ

,

5-BC#‰]ŠO‹!„ ë…&3!ª

,

®9i

ß!à™!†3Ahpb”Hb—Q2KJ3L#¿è¾

,

^‡9ˆ

,

®-n

™‰™

Š

Š‹2<$b—2Œ8¹¾C—

.

^{vwxy ª}

,

ñòKó­,ªŽŠ,™B-C 9˜‘GHK¸!$]Ÿb.2”A‘;le

™

,

^{’‘(Ž]Š,™}

QCQP

‹Œu,“”($<•mb”«~I@˾ ¾o

, SQCQP

^mH™

®i

ß àEª!T–U@˾

,

5BC+Ž]ŠHEŖ#—]Ì žb*>—˜,$—32%J3L'¿è¾C—

.

œ,

;'¿6ž9Ÿ Ÿ+e^3

,

^v¡¢ ÅK¸©X*,£9¤$ž-¥¦I2%ž¥§O‹!¨’‘ ¸e!©+ª«-¬Ÿ

 

,

v-w-x9y

!„+lAe3ŽMŠHÅ#¸©£-¤($ž¥9§H‹ŸQe^Qb¸e

McMaster

^5-‚K™

Z.-Q. Luo

Ÿ 

,

$O¿Ûʏ­®€¯°•,!±u,²³H™E¼,‹ØO¸-¨–

.

^!e

,

5aÇ´µ,-$lAe<¶·¸¹°Ÿ

 H‹ ªº»(2œ–'—©+ª

¡¢¼

™½¾,!¿u,žÀ1Á¸<&Â7¨–

.

ÃÅÄuÆÅÇ

[1] D.P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, NY, 1982.

[2] M. Fukushima, Z.-Q. Luo and P. Tseng, A sequential quadratically constrained quadratic programming method for differentiable convex minimization, SIAM J. Optimization, 12 (2002), pp. 436–460.

[3] M. Fukushima, A finitely convergent algorithm for convex inequalities, IEEE Trans. Autom.

Contr., AC-27 (1982), pp. 1126–1127.

[4] M. Fukushima, A successive quadratic programming algorithm with global and superlinear convergence properties, Math. Programming, 35 (1986), pp. 253–264.

[5] Z.-Q. Luo and S. Zhang, On extensions of Frank-Wolfe theorems, Comput. Optim. Appl., 13 (1999), pp. 87–110.

[6] M.S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programing, Linear Algebra Appl., 284 (1998), pp. 193–228.

[7] S. Ohno, P. Anghel, G. B. Giannakis, and Z.-Q. Luo, Multi-carrier multiple access is sum-rate optimal for block transmissions over circulant ISI channels, Proc. of Intl. Conf.

on Communications, vol. 3., pp. 1656-1660, New York City, N.Y., April 28-May 2, 2002.

[8] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.

A

^{ÊÅËuÌÎÍ}

(2.3)

ÏÑÐÎÒÅÓÅÔuÕÅÌÎÍ×ÖuÏÑØÎÙ

’‘+Ž<Ú

(2.3)

ª!Û- ÜÝÛ- Þß7ŽÚ

(QCQP)

2!à<oZ¾C—Ž<ÚO™9á Ïâã –'—

.

^.]™Z²Q

ª

,

^ä+

,

^O™

QCQP

^{åÛ æÞß+ŽÚ}

(SOCP)

!aç–'—]µ9måèé–'—

. minimize x ^T P 0 x + 2q ₀ ^T x + r 0

subject to x ^T P i x + 2q _i ^T x + r i ≤ 0, i = 1, . . . , m (A.1)

e-^'¸

, P 0 , P i

ª+êë,·°Åì+H,—72¨–¢—

.

^í'

, P 0 := ¹ ₂ B, q 0 := ¹ ₂ g(x), r 0 := 0,

^ÇlÉ¥Ê

, P i := ^α ₂

ⁱ

G i (x), q i := ¹ ₂ g i (x), r i := c i (x), i = 1, . . . , m,

^2œ–Z¾(o

(A.1)

^ª3ŽÚ

(2.3)

^îM–'—

.

A.1

ï‹ð›ñóò›ôöõ‹÷

(SOCP)

^øXù

äQú

, SOCP

ª! ,™'ÉëûúØU@˾u—

. minimize f ^T x

subject to k A i x + b i k≤ c ^T _i x + d i , i = 1, ..., N (A.2)

..4

, x ∈ < ⁿ

^{ª!a­Q ‘}

, f ∈ < ⁿ , A i ∈ < ⁽ⁿ

ⁱ

^−1)×n , b i ∈ < ⁿ

ⁱ

⁻¹ , c i ∈ < ⁿ , d i ∈ <

^{ªEŸý¾›*,ü}

L'¿Æ¾NeZ· ­ÎOÏOÐsÑKÒAb—

.

Û æI2]ª

K ^j = ("

x 1

x 2

#

x 1 ∈ <, x 2 ∈ < ^j−1 , k x 2 k≤ x 1

)

2s·ýb@˾<—4þW3b‘

,

^{.Û¾7å! ÿ}

j

^{™Û æN2à}

.

^í3ú

, j = 1

^s¾(o

K ¹ = {x 1 |x 1 ∈ <, 0 ≤ x 1 }

2<$b—

.

^Ae

,

^·ý<ÉK‘

k A i x + b i k≤ c ^T i x + d i ⇐⇒

"

c ^T _i A i

# x +

"

d i

b i

#

∈ K ⁿ

ⁱ

!b—.2¹”‘;,—

.

.]™+.2kå ž–'—Q2

, SOCP

^{å! ,™'Éëûú y .2-*%3 —}

. minimize f ^T x

subject to A ¯ i x + ¯ b i ∈ K ⁿ

ⁱ

, i = 1, . . . , N (A.3)

eA^H¸

, ¯ A i = (c i , A ^T _i ) ^T , ¯ b i = (d ^T _i , b ^T _i ) ^T

^!b—

.

A.2 QCQP

SOCP

QCQP(A.1)

^ª

,

^{QeAúAa ­}

t

å!§–'—.2ú5Él©

,

^,™'Éëûú

y

<çQL'¿Û¾C—

. minimize t

subject to x ^T P 0 x + 2q ^T ₀ x + r 0 ≤ t

x ^T P i x + 2q ^T _i x + r i ≤ 0, i = 1, ..., m

(A.4)

..4

,

H™Eµm3åÌ ž–5—Q.2ú¢ÉO‘

, (A.4)

^å

(A.2)

™3ú!aç–'—(.2¨”9b—

.

^$MÇ

, y = (t, x ^T ) ^T

^2s–'—

.

1. P 0 O

^eª

P i O

^™<VWª

,

½œ¾:¿4úZÅזO—4Üݪ

P ₀ ^1/2 x + P ₀ ^−1/2 q 0

≤ t

^e

ª

P _i ^1/2 x + P _i ^−1/2 q i

≤ q i P _i ⁻¹ q i − r i 1/2

2

SOCP

™ÜÝQúaçb@˾<—

[6].

2. P 0 = O

^Aeª

P i = O

^™VWª

,

½s¾j¿4úEÅז'—ÜÝHª

2q ^T ₀ x + r 0 ≤ t, 2q _i ^T x + r i ≤ 0

2-ú$ —Z™!

,

^½¥¾Oľ

q ¯ ^T ₀ = (−1, 2q ₀ ^T ), q ¯ _i ^T = (0, 2q _i ^T )

^2îÇ

.A2%

, 0 ≤ − q ¯ ₀ ^T y −r 0 , 0 ≤

−¯ q ^T _i y − r i

²

1

^ÿH™

SOCP

^{™ÜÝQúaç3 —}

.

3.

&K™MŸAd!¾XúN*© ªQ,¿$ZŸV9W

,

^–($8Hì

,P 0 6= O

^;

P 0 O

^{Ae ª}

P i 6= O

^;

P i O

^{™VW3ú ª}

,

P ¯ 0 = 0 0 0 P 0

!

, P ¯ i = 0 0 0 P i

!

, q ¯ ^T ₀ = (−1, 2q ₀ ^T ), q ¯ ^T _i = (0, 2q ^T _i )

2ς

.

^–'—2

,

^ÜÝHª

y ^T P ¯ 0 y + ¯ q ₀ ^t y + r 0 ≤ 0, y ^T P ¯ i y + ¯ q ^t _i y + r i ≤ 0

26aç9 —

. ¯ P 0 O, P ¯ i O

^—A;#¿

, ¯ P 0 = C ₀ ^T C 0 , P ¯ i = C _i ^T C i

^2%‘Qb—

.

^+l©

,

ÜÝHª





 1 − r 0

1 + r 0

0





 −





 q ₀ ^T

−q ₀ ^T

−2C 0





 y ∈ K ^γ

⁰

⁺² ,





 1 − r i

1 + r i

0





 −





 q _i ^T

−q ^T _i

−2C i





 y ∈ K ^γ

ⁱ

⁺²

2<$b—

.

^{eA^H¸}

γ i = rankC i , i = 0, 1, . . . , m

^—

.

B

^{! Ï%$} &('*),+.-0/,1

B.1

2435687:9;=<4>

-3 -2 -1 0 1 2 3 4

0 10 20 30 40 50 60 70 80 90 100 log 10 δ k

k

-3 -2 -1 0 1 2 3 4

0 2 4 6 8 10 12

log 10 δ k

k

-4 -3 -2 -1 0 1 2 3 4

0 2 4 6 8 10 12

log 10 | d k |

k

-3 -2 -1 0 1 2 3 4

0 2 4 6 8 10 12

log 10 |d k |

k

ö

1:

^{­ ° ±’§}

,

 @?#¡l£Û¤b¦C§ áBA& õ

k ≤ 100,

^{C& õ}

k ≤ 12

^ç

,SQCQP

^{m áDA+®ç}

,

SQP

^{m áDC+®ç}

-3 -2 -1 0 1 2 3 4 5

0 10 20 30 40 50 60 70 80 90 100 log 10 δ k

k

-3 -2 -1 0 1 2 3 4 5

0 2 4 6 8 10 12 14

log 10 δ k

k

-6 -5 -4 -3 -2 -1 0 1 2 3 4

0 2 4 6 8 10 12 14

log 10 |d k |

k

-5 -4 -3 -2 -1 0 1 2 3 4

0 2 4 6 8 10 12

log 10 |d k |

k

ö

2:

^{­ ° ±÷À}

,

 @?#¡l£Û¤b¦C§ áBA& õ

k ≤ 100,

^{C& õ}

k ≤ 13

^ç

,SQCQP

^{m áDA+®ç}

,

SQP

^{m áDC+®ç}