close

Вход

Забыли?

вход по аккаунту

?

723

код для вставкиСкачать
ОГЛАВЛЕНИЕ
Элементы теории оптимизации !" # $ % &
%# '
% () * + ,!, -# ()
* #" # ! * .!" #" # !'
(**) ** /# ! '
% (*)
0 ,#' 1 # &
% 1 2'
(*) * % 2,3 () /#
, #
! (4)
4 0 -" ,# 4 2" "$ $ () 4* /#
.-5.51
(46) 4 /# , '
#
! (4)
* Начальные сведения о методах оптимизации * 7+ # $ % * .&
%# % ##
$ (6) ** 7%
$ '
()
** 8" % ** 8 ()
*** 8 $ 8 , # (:)
Методы безусловной оптимизации 8" 7+# $ (4) * '
" " (9*)
**
*
6
6
9
4
4
4
* 8 ! .!
" * 8 ! # () ** 8'
! # % (:)
* .!
" (:*)
8" #3"$ :
8" #3"$ # '
"$ &
% (::) * 8 #3"$ ,'
(6*)
4 8" , #
6
4 Методы условной оптимизации 4 8" -# " ,# 4 8" % , (6:) 4* 3'
" # " () 4 8"
, , /" " ! (9)
4* 8" 3"$ 4 8" -# ; ,#' 4 8" -# " 2,3 (*)
4* 8 , -& (*) 4 8'
&%" &
% 2,3 " ,
-&" &
% (4)
44 ! , 44 7,#' (4*) 44* -"
,# (4)
4 8" -# " .-5.51
4 <
" &
"
.-5.51
() 4* <" ,
,
+" ! (:) 4 7'
+" ! # " .-5.5
1
()
4 =&
%# "$ , 4 =&
%#> # %
$ #'
# (94) 4* 7%
## (9)
49 ?&" &%" &
% 2,3 # '
-" ,# 49 ?&" (6) 49* 8&%" &
%
2,3 (:) 49 1" -&" (:4)
Стратегии глобализации сходимости 7" * 8" ! 3 ." ," 3# (*4)
* 3 -# !
(*)
4 %# $ !,
, ,# 4 %# $ (**) 4* '
$ $ (**:)
6:
6:
:
*
4*
9
6
*6
*6
*6
*
**
Методы негладкой выпуклой оптимизации <" "
, " " <" &&%!, # (*4*)
* @# %# (*4)
* ," " . # '
%# * ," " (*4) ** 8" '
% (**)
8,-," " " 9 Специальные задачи оптимизации 9 <" , ,# 9 7+ "$ (*9) 9* 1#
# "$ (*99)
9* ' 9* 7+# $ ' (*) 9** ='
%# ' (*4)
9 8" -# , ,#
9 7" (*:) 9* 8 "$ '
(*:)
94 8" 94 A!" (*:) 94* " # '
, (66) 94 #" " '
# "$ (6*) 944 #'
" " # "$ '
(6)
" " ! *4
*4*
*4
*
*9
*9
*
*:6
*:
4
9
ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ
! " # $ %& ! '
(
") * ' ( "
* " " +, $ -
.' (
. " / ( + $ ( (
+ $ .' 0 "
' "
(
+ $ * . -
" (
1 - $ '
" 0 %& - (
) BCDEDFGH;IGJ K LJMNDH;IJOP NO JCDEGQDNGNO>
OQOEOMCJP
NO GMRGQDPO ;JMSOTG O NO NUGQDNGNOVWDJ NO XGMODYJZ [\]^> *66
¾)
BCDEDFGH;IGJ K * \ROCJNJP ;JE_UCG;DJMGDPV
WDJ NO XGMODYJZ [\]^> *669
½
! "#
9
" 2 (
' " . 3 + (
$
0 . -
4 5 (
/ -
.
66
-
. " 789:;< # 66
-
. / - .
. .' (
0 4 => 66 ? +@AB$
-
C ( -
"
' . DEFE<GHEI<FJE "
. (. - K " .
- !
ВВЕДЕНИЕ
/ " L 6
- ( M
(
" + ' -
$ . (
" - (
' " 0 ( (
"
+.
N ' ' "
(
$ 0 .
' 3 (
"
"
" * " . -
+ - $ ' . (
(
C ' ( + $ " + %O > 5 P Q O O O5
OP OQ 5 R S 5 R > >O >>S>5 >R&L . - $ T
Q -
0 " ". %>O =& - U
( 6
%R& . ' "
0 . "
(
( 3 $
:
'.' " -
(
" ( - (
V
3 # (
W (
. X 3 - (
. 3 X
.' (. ( -
W .
/ ( -
+ $
0 (
" -
X '
' (
" W " - "
'
?(
( .' -
" .' (
. + . . $ C (
" ' (
T
(
- " (
W .
.
(
T -
. 0 ( + (
$ , ' -
"
(. (
-
. 6
$
(
* . DEFE<GHEI<FJE " (.
Y (
+ 4 O >= =>$ 6 . ' " , " +
-
- 66
"
$ (
. /(
- . (
0 Z [
. %O > >5 >P >Q =& ?
" ( % Q& (' 6" " *-
' # '
-
0(
. 0 (' U , - 3 . 66
"
6
" 0 (
( 0 - -
+ .
5$ - -
M
6 . (
. (
+ 0- 6
" N$ C . T ." 3 .
(
. +
$
( - U $
(
-
*
(
6
M %5 >O&
0' ". + -
6"$ . . ". ! 6" .' . .' "
. . 0 ( - / ( + $
(
(
.' 3 . ( ( N % O P >O&
T'
"
. U .' " / 6 "6 6 \
"6 . 6 /" 3 +6
$ ( 6 3 6 '
"6 . 6
# 3 6 Z [ (
+ (
$ (
ZW[
X " (
6 0?C ?V1 ?0]
6 6 N1U/ ( ^9DE_E8EG :< `FE<abFE_cF B8JF < de;_cF
:F +Nf
Y $ \ ^`Bd - Z[ T. (. g;F8:_F @FhFDE_ibF7F; . 6
. . ' ( ?
T\ Y(
( - . - j j j
*
$
\ '. 0 V C
k Z? [ .'. " * . " + ' OQP= # R %>&$ U 0
V "
' 6 " 6 0?C ?V1
. ' ]
6
'
0
V ( (
# "
СПИСОК ОБОЗНАЧЕНИЙ
# ( '
# ( "
'
# 6 (
.' R # '
" (
R R # R R + $
# # +
($
# + # Æ R Æ # - Æ
"
R Æ R Æ # - Æ "
R # ( # # + .
( # (
+
$ # ( # ( # ( +
(' # ( +
( (' R
R
R
4
%& '"()
# ( +
(' # # "
R # ( R R # +(
$ (
R # (
" + # +
( $ " +
$ # +
( $ " +
$ # " " # " # " +
$ # ( ] 6
" ( # ( 6
" # 66
" + 66
" $ 6
" # 66
" 6
" # ( (
( # " ( # 6 (
# "#$ # # % &
ЭЛЕМЕНТЫ ТЕОРИИ ОПТИМИЗАЦИИ
" '
. ", '
-
"
( -
( Y 0 ' . - " (
' (
'
§ 1.1. Начальные сведения о задачах оптимизации
1.1.1. Постановка и классификация задач оптимизации. T
3 # 6
" R (
R X +O$
' + ! !#$ ( . ( # ( ) 6
". # ' *(' +O$
T O W ,
!+
, +O$ +$
, +O$ +$
N -
' k +$ +$ * + , - & ".
! !+
! , ! -
+ -
$
T - +O$ U . "
+>$
(
"
]
-
. . W +" "$ , (
0 "
N-
+O$ +>$ . . . ( 6
" ( +O$ +>$ . . 2' ( +O$ .
' ,
+=$
R # ( R R # (
6
" ( 1 (
( #
! # *('
!#
R +O$ k R +
. +( +
($ ' !
" ( +O$ +=$ + R 6
"
(
6
W
'
4 O
R +O$ +=$ W . + %&$ 0 ( " ]
(L '
4 O /
" " -
+
$ 4 O>
/ ++ 0(1- 2 "(3 & ".
9
/
( . (
( -
T(
**
(
(
l
" ( 6 66
6
"
Y "
" ( (
66
+ ( $ k # 6
" +O$ +=$ . ! !# # 6
" ! !# *
.' " . ! !L '
P
N 6" " / (
+ $
T' .' (
U
+=$ 6
"
T
6
"
.' 0 (
- /
(
6
"
+
'. 6
" (
0 " 6 T
(
6
"
T
( Z[
$ - $ R T
. ( = R R + $
. 6
"
.
( - "
, ) 83
R "# -&!- > "'
# 3 #+ $ Z + ¾)
&& R "# # '
"$ > 3 R , V " > =, '
!> ' , "! " '
" ½
* + , - & ".
6
"
W .' -
(
! O M -
R ! W ( R ! W ( R R # ! > M R R -
# - 1.1.2. Существование глобального решения. k +O$ ( -
+ " 6
" (
$ Y ( -
( Y- . .' '
-
6 -
-
+ ( (
$
.' 0- . +
%&$
W O "( R / ( )
R / # *('#
0! +O$ +>$ 1 !+
,#
/ ++ 0(1- 2 "(3 & ".
:
1 6
" (
$
0 ( 0- , ( +
- ( (
(
$ (
- 6
". . O * O "( R / ) R / # *('# ($ (
# ! ) 2+! *(' ( 0! +O$ !+ ,
O ( +O$ (
R " 6
"
R -
! ( 0- W 6 ∅ +
(
6
( ( '
k ( (
k ( - (
W ( ) `
%# R "# &!&-) "! ( R # #
! > `
'
%# &!&- "! 4 a
3 3 # "
$ # ," ½
∈
*6
* + , - & ".
( ' ∈ R l
" !
/ → (
W ( O
! = R +
( l
" R + ($ .' +
.
M (
O .' (
R #
( R # ' 6
" W +O$ -
0(
O .' T "' R ( R (- (
-
* "'# 1+ 1+ ( ( ) R ($ ( ! 5 U U (
" 0 ( R +
$ " R ! P # ( R U R U # $ R R ) 83 R "# ! > 3 $#+ a (3> )Z ½
/ ++ 0(1- 2 "(3 & ".
*
! R # ( R U (
.' R ! Q # ( R U R 6
"
! R R ! " " .' 6
"
! R R ! " ! "#"
.' ! O # R U
" ! OO R # " $ ∈ R R N . 6
".
R R $ U .' (
,
$ " 6
" -
" "
-
L
$ " (
6
" ' R + =$ " . ( R -
1 (
$ '
! O * '. * (
OO R " 6
"
R R -
! O " R 6
" R R -
*
. -
" . ( R )
! O> " R 6
" R R . -
* . -
" 6
" )
**
* + , - & ".
§ 1.2. Прямые условия оптимальности
1.2.1. Касательный
конус.
Прямые
условия
оптимальности.
0 "
+O$
R # ( R # 6
" T O 0 % R ( "% & " " T
( ( X ( ( '
'
% R "% & " " % R
" R " % R % % " % C
( / . ! ( + ( 3(!$ ( (
% R " R " " % & " " R " % R % R
% % " % T
'
(
' 0
'
(
- (
. + . .
$ k '
(
R ! O ! U . ( . 0 ( . . . / +5 2 - !2 & 1
*
( O "( R / ( ) 0! '
(
! U (
O
!
6 +O$
W O "( R / ) *('# R **'( $ 0! ## # , +O$ % % (
+$
U !6 % (
.' " R % " % % + $ " % k #
-
+O$ . - " % " % & " N . . " +$ T W R ' +O$ +$
W O ( -
+O$ .' " 6
"
"
T
' + # (
# 6
" / O . #
6. - +( #
$
+$ +$
(
C ( (
4 4 ½)
0! "$ %#$ ,#> &
%# !
1
3 # ,! &&%'
*4
* + , - & ".
. # M
+$ '
( '
+$
0 ( (
O O .' * O "( R / ( ) *(
'# R **'( 0! ## # , +O$5 +>$
! > O (
+>$ . " " " . " O b . % +$ W "( (# O
0! % % (
+=$
## # ! , +O$
U T , ( '
# ( 6 R . Y
'
( % R % T
% (
U & N . . % +=$ / +5 2 - !2 & 1
*
! +=$ ( (
(
( 6
"
- (
(
+ (
( (
"
(
-
6
( - +
$ X . "
4 O
4 O> 0 .' - R 1.2.2. Условия оптимальности в задаче безусловной оптимизации.
Y "
R +5$
R R # 6
" M O .' + $ l
W "( *('# R R **'( R 0! ## # , +5$ +P$
U T
R
. R R O
% % R k ( % % R . % T W R '
+5$ + 6
" +P$
W .' 6
" -
+5$ + -
.' $ "
' T
*
* + , - & ".
" -
6
" W " .' (' W > "( *('# R R )
**'
( R 0! ## # , +5$ ' % *(' ' ,
% % % R +R$
U l % R k # -
+5$ . " "% "% "% "% & " % % & "
+P$ N . . " " → +R$ W = "( *('# R R )
**'
( R 0! +P$ ' % *(' ) +Q$
% % % R ## # ! , +5$
U T , ( '
R # '
(
' % R U & & +P$
N . . % % +Q$ / +5 2 - !2 & 1
*9
+P$ +R$ . / 6
" R R -
+5$ \
+P$ +Q$ . U 6
" R R -
+5$
0 > = +R$ +Q$ (
C
S= . . " +O$ ( ∈ " + - (
R O / 6
"
R R R U "
k -
. /
U 0 ! ! T
" > 0 ( " (
=
# / -
R ?
( ( 1 . "
. # *
* + , - & ".
! = U 6
" ' + O=$
M (
6
O= = "
-
! 5 6
" R R 66
" R .' . R *
' )
! P U . ) ) R -
§ 1.3. Задача с ограничениями-равенствами
R R # 6
" R R # (
0 6 " +O$
R +$
W # " ]
( (.' +O$ +$ .' C " ( ' + -
L 4 O>$
1.3.1. Теорема о неявной функции. Теорема Люстерника. (
+O$ +$ ( -
(
( *.' 6
" # (
- + %&$
W O "( +) R R R **
'( R R ! # # "( / +6 7( (2 8 *:
0! ( # * # 4 ($ ( +) + R + * + +$
" . +4 + +) + **'( + + + # +)# + M
6" /( .' 6" '
6
"
W "( +) R R R **
'( R R ! # # "( 0! ( # +) + → R , +$ +>$
+ , U !6 . " R .'. .' ,
T
. " . " + $ R 0 (
Φ R
R R
R Φ U (
O (
+ R + Φ
+ + + +$ ! 6
* + , - & ".
Φ Φ Φ
Φ
R $ . Φ Φ + Φ + Φ Φ + Φ
+ Φ "+ " Φ + Φ + Φ
X "
+>$ , * '
6
" "
( +$
W "( +) R R **'(
! #
R "( 0! ( # , # ! +$ ) '
, U 0 (
Φ R
R R Φ (
. /
" "
].
) , > 3 R R &&'
% 3 > #+,
R ½
/ +6 7( (2 8 W > "( +) R R **'(
R ! #
"( 0! # !
+$ ) (1$,
$ (
$ '
(
! O M > + (
$ (
OO$
1.3.2. Принцип Лагранжа. W +O$ +$ # -
6
" (
+=$
! ( !(# +O$ +$ R *
].
(
] O 6# # '
R( )
( ) ( ) ! U O
OO .' +
6 +O$$ ( O +O$
+$, ' - R +
. -
-$ 0 "
]
( ( .' 6
*(' 2!) +O$ +$
R
R
R - - ! - - - R -R
*
* + , - & ".
W = "( *('# R R **'( R +) R R **'( . ! # 0! ## # , +O$5 +$ +=$ # . - R - +5$
0 ].
(
-.
+=$L (
. / 6
" R R = R = (
W ( -
+O$ +$ "
6
" R R * 6
" +5$ - R T'
].
" ]
( +=$ (
%O &
T O W R '
+O$ +$ +5$ - R X
- ) 2!)
.' "
W -
+O$ +$ + -
.' $ +=$ "
' T
( ]
( .' "
T
( +=$ O
+ ].
# ( 1 +O$ +$ . .
' * - - R R .'. "
+O$ +$ .' ( ]
( .
/ +6 7( (2 8 2!) ! ]
( (
,
- + $ 2 + $ -
X (
. 4 >
V " ]
( .' +=$ -
+O$ +$ b " " m .' (
N l + O$ ( " ]
( 0 - " ]
( - +O$ +$ O 6
"
R R (
R *'
0- T
6
" R R
( 0
6
". ]
(,
- - R - R
.'. ]
(,
- - - - 0(
k - # k ( ( - . - - # - X
- "
4
* + , - & ".
W
"
, *
" 6
" ( # #
1.3.3. Условия второго порядка оптимальности. /
W 5 "( *('# R R +)
R R )
**'(
R 0! ## # , +O$ +$ +=$ # ! . - R ( #1$! +5$ (1$ ,
-% % % +P$
U l % W ].
% '
' (
. R R "% . " " R . " & "
# -
+O$ +$ .
. "
"% . " "% . " - "% . " - "% . " - - - "% . " - "% . " "% . " & " -% % & "
+ +5$$ N . . " " +P$ 0 +=$ 6 '
( ]
(
W P "( (# 5
0! ($ ( ( #1$ +5$ .
- R # ! -% % % +R$
## # ! , +O$ +$
/ +6 7( (2 8 U T , ( '
# (
' % R T
% (
(
$ ].
% U & " # & * . . -
(
- -
+5$ , - - " # & - - & - & N . . -% % +R$ W O> O= 5 P 0 5 P +P$ +R$ (
C =SP . c "
* + , - & ".
6
(
R R R # \
O (
*
]
( -
- / - # - # M = #
#
- # "
'.
(
# # *'
(
' 6
" 6
OO= *
" 6
" ( ! / 6
"
R R (
R + O$
! > U . ". ! = R # " /
6
R R 6 R ! 5 * -. '
! P / . (
*
. (
-)
§ 1.4. Задача со смешанными ограничениями
X 6 '
" -
6
"
+O$
/ +9 7( :- (2 R 9
+$
R R # 6
" R R R R #
(
Y ' '
0 .' 6" (
(
0 ( ( +O$ +$ 1 6
"
(
%O P&
! (
'. .' (
0 / -
+O$ +$ -
R R 0 / R
R 0 / + R $ X . -
+O$ +$ + 4 >P$ %5& T
. ?(
( b
+ $ " G ! ( (
6" , (
(
- "
- Z(
[ 0 ( .
+ .
-
$
* + , - & ".
"6 1.4.1. Леммы о линейных системах. ? 6 '
4 O 0 '
OO 0 . '
. 6 - ] O 6# 1+ '
R( ) ( ) R R ,
U T
R " / U( ( / '
. R R +$
W m
( +$ / / N( " + k k ( (
(
1 1 T
" " '.
1 /(
R R +>$
(
. " '. R R .' .
k . +>$ . ( ! " R 1 .
$ 2 2 / 1
+=$
=
/ +9 7( :- (2 :
(
" '
3 R R 3 $ 3 +5$
(
3 2 +=$ +5$ ! C / 1 $ 2 $ $ $ 3 $ 3 -
+=$ +5$ U
2 /
" +=$ +5$ $ 2 $ $ $ 3 $ 3 - +>$ * O 6# 1+
4 ' R R R R R ,
! O U O
*.' . ?"
] 6# 1+
4 ' R( ) / , (1$4 (4 ,
R +
( ) (R ) R R 46
* + , - & ".
U k ( # -
# -
(
W ( / . O R R R R
+P$
+R$
T T
+P$ +R$ # -
(
(
. W (
(
6 N (
l-
] (
R ! R( ) R( )
0!
R R R +Q$
U T
. +Q$ 4 W
4 R R 4 W R ( ( '
R R R T. 4 4 1.4.2. Условия Каруша–Куна–Таккера. /
+$ ( * / +9 7( :- (2 4
*-
- . ( + $ ) 4 ! +O$ +$ R (
5 / 0 66
" (
" +O$
6 % 0 % / 5 Y ( !(# !7' $ ' % 0 % / 5 *.' ' ].
W O "( +) R R **'(
R !
#
+) R R **'
( "( ( 6 +O$
0! # ! +$ ) (1$,
$ (
6 $ ( !(# !
7' '
(
6 U * (
$ '. (
OO
U( $ % 6 % # ?
Sl" !6 7 # % 7 7% 7% T
% 7 (
. ].
'
(
. R R "% 7 . " " R . " & "
+OO$
½)
7+## V \bLc ( ,
, \GMdGPGYDGM5
bYJEJSDCF ;JMPCYGDMC eUGQDf;GCDJM)
4*
* + , - & ".
C 0 % 7 70 % 70 % / 5 . " 0 "% 7 . " "0 % 7 & " / 5 +O$
M +OO$ +O$ "% 7 . " .
" -
+OO$ % 7 '
/
" '
+ O$ % % 7 '
# -
+O$ +$ 6
" 66
" (
. O ?
Sl" W OO + ( +O$$ .' , '. - R
8 / 5 - 8 0 2 6 C-SC
SW *(
'1 2!) +O$ +$,
R R R R
- 8 - 8 T
- 8 - 8
R - R 8 R W "( *('# R R +)
R R **'(
R +)
R R **'( . ! # 0! ## # , +O$ +$ ( !(#
!7'
( # . - R 8 R - 8 +O$
8 +O>$
/ +9 7( :- (2 4
1 +O>$ ( #1$ ) +
- $ *
.' 8 +O>$ 8 0 / 8 / 5 W .' ( Z.
[ . T O W R '
+O$ +$ -
+O$
+O>$ - R 8 R X
- 8 . ) # 2!) .' "
! U ?
Sl" "
+O$ +$ ( ( ]
( .' "
M -
+O$ +$ ?
Sl" "
T
' L +O$ +$ . .'
! ?
Sl" ( ]
( .' "
k
( ( $ ' " 0 / 5 .
. R C ?
Sl"
( ]
( .' "
! (
!(# !7' $ N ½)
7+## V g[Lc ( ,
, gDMOGY DMNO_OM'
NOM;O¾ ;JMPCYGDMC eUGQDf;GCDJM)
) 7+## V h\bLc ( ,
, hCYD;C
\GMdGPGYDGM5bYJEJSDCF ;JMPCYGDMC eUGQDf;GCDJM)
44
* + , - & ".
! ?
Sl" "
+O$ +$
.' ., .' (
- R 8 R " ]
(
0 / 5 8 . . R ' % 0 % / 5 8 0 % / 5 5 8
5 8 / 5 8 * - 8 8 8 - 8 R R R .'. "
+O$ +$ .' ( ]
(
. &(,7&(70 $ V C-SC
SW
.' ?
Sl"
-
+O$ +$ " 6
" b
" " m
(
" 0 / 5 " ]
( + O=$ / C-SC
SW ( -
+O$ +$ *
, (
- C-SC
SW "
+ '. .' $ T
(
-
?
Sl" 2
-
C-SC
SW '
4 >= +
( >O -
]
(
$ N . - - +
OO O$ C-SC
SW . +O$ +$ 0 (
(
(
. ) 7+# + V ..1
½
/ +9 7( :- (2 4
0 .
' 6
. M ?
Sl" '
. ( - R
8 R . +O=$
- 8 +O>$ / (
?
Sl" .'
6" +O$ T'
6
l U(
0 ++$(1 *('1
2!) +O$ +$,
R R R R R
- - 8 - - 8 W "( (# 0! ## # , +O$5 +$ ( # - . - R 8 R (1 - - 8 +O5$
+O>$
U
?
Sl" +O5$ - - 8
# - . - 8 +O=$ - (
, . " 6
" -
+O$
+$ ?(
l U(
( 6 -
?
Sl" W " l U(
(
(
/ (
?
Sl
" %& * l U(
" ! '
6
" ]
( ( - - 8 R R R .'
(
- - - 8 (
4
* + , - & ".
- 6
O . "
C-SC
SW
0' ( !(# ! +O$
+$ . . (
- %P& 1 ?
Sl" . U (
( ' (
66
]
-
+O$
+$ . *'
$ ! > U ! = U ?
Sl"
+ $ ' +O$
+$ .' , ∈ (
+O>$ +O5$ - - R 8 R . + $
1.4.3. Условия второго порядка оптимальности. 0 +O$ +$ U 6 ( + ( 4 $ +O$ +$ .' 6
" (
+OP$
% 6 % ] > "( *('# , R R +)# , R , R R **'(
R ## ## # ' +O$ +$
0! # # ) 2!) - R 8 R 1$4 ' 1 () % 6 () () % % 6 () 8 0 () % / 5 () +OR$
→ R
½)
7+#" ,
# # ,# ,'
V LJMPCYGDMC eUGQDf;GCDJM (Lc)
/ +9 7( :- (2 49
U U % 6 +O$
+O>$ 8 8 0 %
% - % 8 % (
T.
k 8 / 5 "
( ! + (
]
( - 8 ! +OR$ % 0 % / 5 W > "( *('# R R +)# R R R R )
**'(
∈R 0! ## # , +O$ +$ ( # . - R 8 R ( #1
$4 +O$ +O>$ (1$ ,
- 8% % % +OQ$
! ( +OP$
U l % 0 ( 5 % / 5 0 % *
].
' (
. R R
" R "% . " 0 "% . " / 5 %
. " & "
T. ( 6 5 % "% . " . " # -
+O$ +$ > -
+O$ +O>$ , . " "% . " "% . "- "% . " 8 "% . " - 8 - 8 "% . "
"% . " - 8 - 8 4
* + , - & ".
- 8 "% . " "% . "
& " - 8% % & " N . . "
" +OQ$ ! O O -
+O$ +$ Y .' (
.' $ W = "( (# >
0! ($ (1 ( #1$ +O$ +O>$ .
- R 8 R # 4 - 8% % % +$
! ( +OP$ ## # ! , +O$ +$
U * -
OP T , ( ' $ ' % R T
% (
(
$ O % 6 C % ( ( R (
$ O % W % + +OP$$
U & " # & ½)
7+## # , #> ,
a V hBhL ( ,
, hO;JMN'JYNOY PUi;DOMC ;JMNDCDJM)
/ +9 7( :- (2 0
0 4:
0 0 & / 5 U
( - . . -
( 8 . . .'
-
/ 5 .' -
+O$ +O>$ , - 8 - " # 8 " # & - 8 - 8 & - 8 & N . . - 8% % +$ W O5 OP . > = C S= c 0 .
(
-. . ' 6 + +O=$ ?
Sl" -
$ (
(
(
- "
* (
% O &
НАЧАЛЬНЫЕ СВЕДЕНИЯ О МЕТОДАХ
ОПТИМИЗАЦИИ
/
# ' +$ " . . ! ( . -
" !
( . .' -
(
§ 2.1. Общее понятие о методах оптимизации
R # ( R # 6
" R R # (
N .' -
+O$
+$
+ OOO$ /
( + $ 6
" (
+ $ 0 '
+ 5 . P . "
$
2.1.1. Классификация методов оптимизации. Понятия сходимос-
]. -
+O$ +$ " .' 6
" (
+$ T
" (
"
,
ти.
/ 5+ '; &2 3 & ".
-
.. " +
$ "
Z
'[ ? . . " . " 6" " .
' -
R . +)# -
. X . . ( - ( .'
(
. ,! ' *
. ' 4
% +$
% # (
R ( R - (
k "
6
(
. % % % N
"
+$ ,!
M
!,!
%
' (
"# " .' 6
" +O$ +$ '
" W 6
" - 6
" k ( . + $ + $ k . (
. -
,!
C
(. P U ' " +,!
' . -
- . 0 " *
* 5 0(1- 2 3 & ".
4 / # -
4 !(
( 4 (
+ . M
-
. - ,
9 9 # ( -
0 4
) ( , k 9 # . ( 9 ( 9 ( ' k - # +O$ 4 *('
. (1
$ N .' (
2 ( +
$ -
- ( "
. .'
/ " 4 ! ( 2 . "
/
" R . (
R !+
4 k ( (
-
. +
( -
"
(
"
$ 4 0 " . ' (
' (
/ " 0 -
(
" N / 5+ '; &2 3 & ".
66
-
/ /.
-
-
. 6
6
\
-
' " .
" "
" ? " . " . ' - (
(
' (
2.1.2. Оценки скорости сходимости. Правила остановки. - (
4 .'
66
Y
L -
-
. T"
(. . ' ! . (
R
b .
- .' ( k
:
: # 1 : 4 0(
# (
+ ( # $
! O R R . * . )
* (+
"
.' .
4
* 5 0(1- 2 3 & ".
( (
0 * k (
(
:
: ! T
. ' * "
%5 O&
T"
. (
0 (
66
/ " . . . ". Y ' " (
( " - U (
# -
. . '
(
" /
.
+
/ 6
" K (
' . (
.'
k - . "
. (
(
. k ( -
.'
- 0 "
' .' C " ( ( . - (
( (
. '. "
/ 5+ '; &2 3 & ".
U
"
- .' (
+ $ T
"
+ -$ '
" (
0 "
6. +
: ( 0 "
/ . (
. ' - ( / 6. .
- + - $ " . ( m
(
. (
-
. / -
R = W . C - ( + (
$ .' 2 " - - T
. " "
.' 6
" C
Z(
[ ( -
. -
* 5 0(1- 2 3 & ".
0 * .' T
' . . ' X ' - .
. -
' ' N ' (
( (
-
(
' "
-
+
( "
$ .
' (
- ' .
W
6 -
W
.' , +'
"
G ( "
. "
$ "
+(
$ /
" . =
2 ( -
+ (
$ .' . -
.. "
. -
$ .' ( -
"
W
) `
%# R "# 1 -&!) "
3
R !
"
# &
%# "# -&!) -&!1# "( () # "
! , 3
% &
% 2 ! - "
% ### ,!"> # %# ( "
# **) ### -j 3 - , "
0 % " ! "
3! &
% "
3 , - `
%# "# !)> &
%# "
% , &
% "
3 ," "
%
½
+ / 55 <- ) & ".
9
" +
'
n$ (
.
" .' -
' (
(
. - (
/ " " 6
" - (
(
6
6
T
- L ( Y
" .
. " - ( ( " . -
+"
$ W . (
. /( " T " %OR 5&
§ 2.2. Методы одномерной оптимизации
0 6 . -
" $#
+O$
$ R $ " $# R 0 66
" $# 6
" - U 66
- 6
" "
N
( "
%> O O P P&
o 6 # (' '
.' .
"6 X T
(
66
" -
+O$
' +
Matlab Maple$ ( "
"
%>Q& X "
. * 5 0(1- 2 3 & ".
2.2.1. Метод перебора на равномерной сетке.
( # " $# 6
" = +O$ ( (
-
-
; " $# X (
.' " $# ;
\ O Æ $ #; Æ
/Æ / ; 0
(
W + 0
!, 1 + 6
"$ k - (
. 6
; -
( T"
-
(
- 6
" 6
" ]
-" $ " $# " $# #
-
+O$ ! Æ # W
Æ 1( - - "
+
; .' .$ - .
/
(
6
" ]-" " $# .' , . " $# 6
" -
.' - + " %O P&$
! . -
( U
(
6
"
) > &
%# R "# &-) & =&8
:.! 3
R k," a # #
# 3 R ½
/ 55 <- ) & ".
:
; (
. " $# ]
-" 6
". (
$ Æ #
! O " $# 6
" " $# → R ]-" ( " # " $#
]-" " $# ! 6
" " $# R " $#
66
" " $# . .
( " $# / 1 ]-" " $# ! 6
" " $# R ]-" " $# 6
" ]-" " $# ! > " $# 6
" .' ]-" 2.2.2. Метод дихотомии. Метод золотого сечения.
T O l
" " $# R (
+
" $# " $# < < " # < < < " $# <
/
" $# 6
" " $# +
.' $ ]. $ " $# 6
" '. 6
"
! = R # ( l
"
R ( +
. ( ] .',
½)
`
%# R "# -&!) "
'
3
R ∈ 6
* 5 0(1- 2 3 & ".
" " #
+$
" 6
" .' ! 5 R # ( l
" R ! ( +
" +$ U " $# 6
" ! P 6
" " $# R " $# * . 6
" " $# )
*.' 6
" "
.
( ] O "( *('# , " $# R ( / !+
( " $#
0! # 4 < " $# 4 <
(1$ ,
) () (<) " <#L
) () (<) " $#
U U( (
$ +(
$
$ ( < > < W < < (
. W 6
" " $# (
-
+O$ - " (
- " *
.' . ! +O$ -
- 4 +
$
\ $ $ $# O # k $ k ( < + $ # < " / 55 <- ) & ".
k
< k ( < $ $ < 1 - O
$ < ] O . - " $ # $ # $ $ $ 0 (
(
..
" $ # U " ( - - "
6
" +
- $ ( -
; ; W ; # - "
-
+
$
$ $ && $ W ; -
- . : && /( 66
"
: !' +
-b ; ' - $
- -
-
-
. - - X " W '
" $# (
( $ T. $ $ ' $ 0 ' " $# 6
< < $ $ !' $ Y < , +, *
* 5 0(1- 2 3 & ".
* .' (
] "( < / ,# +8,# " $# 0! ,
) < $ ( ( )($ )#L
) / +8,# # " <# < / ,#
# " $#
T- ! # \ $ $ $ < < $ O 0 < '
k < $ < $ < k (
< $ $ = < < < $ 1 - O
! . - $ < < $ (
$ C O ∈ " $ # (
. $ $ $ $ 0 (
(
.. " $ #
" ( - " 6
" +
(
$ $ W ; . = ; - "
-
$ !' $ $ g ; -
- . : !'
/ . - " 6
" (. " " - / 55 <- ) & ".
/ " -
' " ( " T
O . 0 (
" 6
" " U
6 Æ Æ Æ W O " ( " Æ# k ( + Æ Æ .
. 6
" 0 6
" (
-
. +O$ 0 (
" 6
" W
! R * - & " (#
МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ
0 (
-
/ +
.
(
$ . X 3 ". " " (
6- '.' § 3.1. Методы спуска
R R # 6
" T
. -
"
+O$
R .' U ' (
-
. 6
" - . U (
" ?
. L 6
3.1.1. Общая схема методов спуска. /
T O 0 R (+
# 6
" R R R .
" " ?
( 6
" ∈ R
W ∈ . -
. 6
" X
/ 6+ <- &!
] O "( *('# , R R **'( R 0! ,
) # 1+! () () L
) R ( # (1 () ()
! O U .' O k
6
" R R ( 66
" R ,
$ . $ R C ( (
"
= +$
,! = . +$
!
∅ ∅ " . ! +$
. = W
Z[ (
" 6
" (
-
. C
( " - W " (
6
"
' . "
! $ M
.'. "
, (
6
" ' 6
" M O (
*.' " ( (
L ) 7+#" ,
V >?@A@BCD
½
* 6 <- '"!) & ".
O ! ( " O . 66
!
- . 4 ( " 4 R (
"
Z
[ " + $L O 4 ( 6
" 4 \
( ( Z
[ '
" .
N " ' (
( " ' = = = -
"
! = = R +>$
! R R ! = = ! 6
" 66
" ! = = +=$
' 6
" ' W = - .' (
- " 6
" k
# 6
" $ R R # " $ R " (
-
= +>$ / 6+ <- &!
6,
T
' = U -
( - " +>$ 4 C
(
+ (
n$ - (
! " + 6 .
"
" 6
"$ +>$ . ! = = " = #
= # 6
0 - " . = +>$
" 4 X 66
"
6
" ' l = 7 ∈ = =
O +5$
= = k +5$ = 7= O 0 = =
W = = = +5$ 0
= +5$ Z
[ . " 6
" - = . W +5$ " 6
" (
.
+ . $ . Z
[ *.' . 6
O +P$
\ ] "( *('# , R R **'( R 0! . R ( # +P$ +5$ # 1+! ! = = 9
* 6 <- '"!) & ".
U U . = = = & = = & = = = = = & =#= T
+P$ = \ +$ Y +5$ = = "
- "
+$
U '
' = ] "( *('# , R R **'( R
# 2,'( R 0! # 4 R +P$ +5$ # 1+! = ( = # !
= ( ) ( )> +R$
U .' 6
" ]-" ] > (#4 ( ) () () R U 6 /.
S]
" " "
" " " " ( C-SY
Sp" U M > +R$
. = = # / 6+ <- &!
= = = = = = :
W Æ +Q$
Æ # ' = 7 ( " \ = ' / " = 6 .' -
" #! l +
' = = = X L . "
6
" " ! +Q$ =
+5$ ( - = = W
- .' \
! " ]-
" "
6 +R$ ( - T
( - "
]-" ' C - - = - ( .
( L . (
W . + (
$ T
% ' - .' +O$
6
] #
\ +5$ " 6
" 0 \ . = +O$ 96
* 6 <- '"!) & ".
- = . 0 . , - - . U " ( (* ( V
+O$ +OO$
= = = +O$
0 6
" -
06 66
0(
.
+ $
" .'. 06 +
V
( $ l
= = 0
= O +OO$ +O$ k 5
k -
+OO$ = = =
k -
+O$ = =
> k = = = +Z
" [$ O
= 0 = = = +Z
" [$ O
5 = =
/-
+OO$ ' = Z- [ -
+O$ Z- [ T
" .' *
. - Z "[ = (
. - Z
"[L = ( - (
= # - =
ZX " [ Z
" [ " / (
6
7 7 Z "[ = 7 = Z
"[ = 7 = 7 =
/ 6+ <- &!
9
Y '
(. %=& 0(
- Z "[ = - Z
"[ = = .
] = "( *('# , R R **'
( ! ( R 0! # 4 R (&)
(1$# (* '( = ( +! ,! Z. #'[ (= = ) ( +! ,! Z #'[ +( / 66
" R ! R U k ( - Z "[ " .' = ( = = +O$
+P$ W - Z "[ ( - Z
"[ W = = ' =
+O$ = +O>$
= = +O=$
+O$ +O=$ = = +O5$
* +O=$ = . . - =
M
+O5$ - +O=$ = = = = =
=
= = = 9*
* 6 <- '"!) & ".
+P$ = +OP$
* +O>$ = ' +OP$ 0 -
'
X . - ( "
6
" " \ = = +
$ 6
" 6
-.' " 66
3.1.2. Градиентные методы. 0 6
" 66
" R % . +$ 6
" + ' "
+O$ L 6
W +$ = +OR$
0 . \ O 0 R 0
OO " , = + = = " =
7 ∈ \ = O 0 = . + = (
6
$
0 6 +OR$
1 - O
/ 6+ <- &!
9
V
- .
" ,! ( $ 0(
. + = .' +=$ " W Z
[
/
+5$ \ = = ! +Q$ Æ +R$ = +OQ$
6
" . ]-" R \
=
+$
=
= # ' M .' W O "( *('# R R **'(
R # 2,'( R "( ( # ! O #! = ( # (1
= +O$
0! 1+# # 1+ ! O ## # ' +O$ 9 #
($ ( *('# ! ( R +$
U *
\ k ½)
,#" # "! " ,'
" "
94
* 6 <- '"!) & ".
. L + 6
" R $ 0 \ +$ . = = . !
+$ "
U ( ' (
\ = # .' - W
= T '. = = " /
+OQ$ . +O$ \ = = 0 " \ O
]-" 66
" R (
+$ . = (
-
-
W "( *('# R R **
'( R "( ! O ( # ' 4
0! 1+# # 1+ ! O ## # ' +O$ 9 ! , +$
U * " . \ ( O \ . R > *
= / 6+ <- &!
9
( O + (
( (
= > W . - > =
= -
= = #7 +5$,
T
= = #7 = = ! = > T. '. = (
(
! U V
06
*'
O ( V
'
(
(
( ] R ' ! (
U 9 9 "
R
+O$ Y . 66
"
6
" T
( ! "
. , '
. 2 9
* 6 <- '"!) & ".
& 2 +$
] 5 "( *('# , R R **'( R )
**'(
. "( ## # ' +O$
. *( O=
( ! # 0! # 1+! ? ( ) # # #( +$ +( () ?2 ( () ()) +>$
U U R & & & & W -
+$ ? ? & ? 2 & +=$
? T. -
+$ ? ?2 ?2 W +=$
?2 ?2 ?2 W "( (# O *(
'# )
**'( R "( #
/ 6+ <- &!
99
# # ' +O$ . *( O= ( ! # "( ' ( # ! O ' =
+ 0!,
F$ # ! O ## 1+
+) R + 4 # 4 *(' # !( ( ! #, 1 '
+5$
: ) : ) +P$
! : " ) # $ ( # ' = ( # (1
+R$
= +Q$
! / * / + # '
$ ( # 4 = ( #
(1 +R$ 7 / (1
+$
7 +O$
) # ( +$ 7 ) 5 #
7 +$
$ ( # #! = * =
+$
9
* 6 <- '"!) & ".
U l .
-
+$ +>$ 2 ? ∈ +
5 .
'
$
0 " = " =# = = = > \
+
= ( " =# = = =
# +>$ = = = ?2 +>$
=
0 \ -
+$
+>$ = =?2 +=$
* . \ + OL
= = = W . +5$ .'
: Y(- # U
.' .' +$,
+5$
l . . Æ .' .
Æ .
Æ
+P$
+
Æ . Æ -
+5$ +P$ Æ = .
Æ =
9:
/ 6+ <- &!
. T. -
+$ : +5$ (
( . 1 W +5$
: : 1
+5$ : =
T. +P$ = =
Æ =
1
: Æ .
.
W 0 . "
+5$ -
+$ "
+P$ ) #2 W - (
$
1(
$S$ . (
$ 6
+>$ +=$ "
2 ]-"
6
" * ( 6 5 ? (
$ (
= +$ $ (
+OQ$ = =
=# ! > U (
$S$ ! = U 66
" 6
" R + ]-" R (
- - 6
* 6 <- '"!) & ".
Y "
+Q$ - %5 >O =&
* "
+O$ \ # ( # "
+O$ ( "
+Q$ - "
+$ * 7 (
7
( \ ' /
" "
+$ - = = # "
+$ +Q$
U
(
K . +
$ "
- - %5 O >&
T
- -
6 / ( # -
+O$ .' ( -
9 0 (
- R +R$
R R # (
0 "
+$ .'
"
( 9 +Q$
2 9 # 2 # = # +O$ / (
O +R$ 6
" "
+Q$ !
' +$ . 6
" ( 0 . +Q$ # ( 9 U .' +Q$ ( . ( ! 2 . "
/ 6+ <- &!
9 Æ R 9 Æ R Æ R Æ Æ T
(
.' ( 9 ( ( "
/ .' +Q$ 9 Æ Æ 2 .', (
9 .' \ ( 9 . 6
" . + %O&L ( (
$ N
-
' (
M
. ( +Q$ 2 9 U 6 .
( 9 "
+O$ "
( .' ,
2 9 +>$
# ( 9 2 # ! 5 0
5 .' (
'. Æ 2 6
" R R ( 66
" 9 Æ +Q$ W . ? . ?2 9 .
"
+>$ W
5 9 9 6
" .
+Q$ 9 Æ Æ 2 "
+>$ .' +(
$ ( 9 2 *
* 6 <- '"!) & ".
0 - +>$ R Æ Æ + "
+>$ 9 Æ Æ R Æ (
Æ C
O > +$ . O (
( M
' . k' ( 4 4
(# .', ' + .
9 + X
( 9
. ( (
. ( 6
" ( ! P 6
" R R 66
" R ]-" R ( - ! R R R # 6
" .
' . +>$ + R 2 +
$
W > "( (# O
+O$ ( +>$ R Æ 4 Æ 2 "( !
( 4 4 (#
"( ! O ( # 4 #! 0! 1+# # ! O 4 # ' +O$ 4 *(
' # !( ( / ! #
U * . \ (
- W +>O$
/ 6+ <- &!
+O$ -
M -
+OR$
+$ .
= = '
(
W -
"
+>$ "
+>$
# " ( 9 "
+O$ + OO$
M +>$ / '
. - +>$
W 9 > "
"
+>$ * +>O$
. , , "
: +>>$
: ,# , X .
U +>O$ +>>$ .
- 4
* 6 <- '"!) & ".
: : T
) = # / : ) T. 6
R / "
/
"
+>$ 9 ∈ 9 0 .
N " 6
" Z [ .
Z(
[ C
66 (
, -
.
" - -
#* . "
+Q$ +O$S+$ . -
"
, " (
V + 6
$
.', (
. Z
[ . Z[ Z
[ ' -
- T
.' 66 Z
[ M
Z(
[ 6
" %O& C 4 4 .' . Z(
[ "
6
" ! Q M (
- - " 6
"
R R / 65 < 01# E"1# -
! O M (
" 6
"
R R - .' \ = 7 #
§ 3.2. Метод Ньютона. Квазиньютоновские методы
l
6 /.
(
, ( ' " /.
"
M - " /.
- ' . "
* "
. .'. " 0 *
"
'
" C . /.
.
- . /.
"
- " 3.2.1. Метод Ньютона для уравнений. C /.
Φ +O$
Φ R R # (
R # '
(
-
. +O$L (
"
Φ Φ +$
X "
:1 \ O 0
R O 0 R -
+$
1 - O
(
Φ "
. /.
. +$
Φ Φ * 6 <- '"!) & ".
'
" Φ "
-
W O "( +) Φ R R **'(
R ! # . "( ## # , (
# +O$ Φ 0! 1+ +) R +
# 1 ! O #
4 # 4 4# # Φ 2,'( #
U *
'
(
" $ , Φ , +>$
Φ 0 +$ -
" O C +$ +>$ (
Φ Φ Φ Φ Φ Φ , Φ " " Φ +=$
! Φ " " Φ +=$ : Æ Æ Æ : ) =# + 3 l*mZ R # %" R #'
+ > ½
½
/ 65 < 01# E"1# -
9
Æ W (
. O .
/
" Φ ]-" +=$ , +5$
, . $ ! .
"
Φ ]-" Φ Φ * * # # W
" ( -" -
M
(
Φ (
'. (
Φ W . Φ .
' .' (
% R R :1 $ (
"
+P$
% Φ * O "( (# O
0! # 1+! +)# % R R ! % Φ 1+ +) R + # 1 +P$ # 4 #
4 4# # Φ
2,'( ($ (1
* ; % Φ ; * #
! O U O
) . () 3 !-! > !!# '
"
, " 4 # 3
¾)
7+#" ,
V [MOTG;C nOoCJM EOCpJN
½
* 6 <- '"!) & ".
/ /.
- . (
:1 $ - 0 "
+$ /.
-. '. "
( " (. -
+$ . -
'. "
/
"
" (
+$ + (
$
U (
6" /.
(
" 4 ,
+R$
Φ Φ ! (
. (
Φ ( " - . ( " ( /.
! U O +R$ . - ( / . Φ ( - .' W Z[ ( +$ +R$ ". (
-
0 - /.
(
Φ ( 6" 66
(
+ %O &$
! M (
-
/.
# "
L 3 . 66 ?6" /.
- ) 7+#" ,
V qYUM;GCON nOoCJM EOCpJN
½
/ 65 < 01# E"1# -
:
! > U .' (
6
"
R 66
" R # +O$ Φ Φ Φ Φ W /.
.
- Φ R
3.2.2. Метод Ньютона для задачи безусловной оптимизации. W
"
R +Q$
R R # ( 66
" R 6
" *
"
. +O$ Φ R R Φ # ! +) "
(
/.
.
R # ' (
"
+Q$L .' (
' -
+O$
+OO$
! " .'. "
. 0 +Q$ (
" "
6
",
R +O$
+O$ "
W :1 " .'
\ 0 R O 0 R "
. +O$
1 - O
M O :6
* 6 <- '"!) & ".
* "( *('# R R )
**
'( R # # . "( ## # ' +Q$ . *
( O= ( ! #
0! 1+ +) R +
# 1 ! #
4 # 4 4# #
# 2,'( #
/
" V ( 66
" 6
" 0 "
-
"
+O$ q"
+ $ (
(
" #! (
( (
%O& # (
" (
$ W. "
(
-
(
' " (
"
+
2 - 2 %5 O O5 >O =&$ (
" + 4 =O$ C 6" . "
- 0 /.
Z
[ "
+Q$
V
/.
# /
4 O - (
- . T
( /.
.
'
( - . ( (
.
. "
+Q$ m
# 6
" +O$
$ R R # " $ R " (
/.
.
/ 65 < 01# E"1# -
:
. . (
-
T
( , ( ' "
(
*.' %O&
O N 6
".
R R # /
. 6
" ( 66
" R +Q$ " 6
"
. "
.
Y # 0 , 0 " .
( = - " ( - "
( - +OO$ = = ( 0 -
- .' /.
( /.
C ( " /.
(
. . " 6
" - .
'. . 0 " " '
" ?6
" .' . '
! = M (
- /.
" 6
"
R R ) /.
:*
* 6 <- '"!) & ".
3.2.3. Квазиньютоновские методы. o " ( "
= 4 +O>$
( " 4 R (
= # - " OO /
+O>$ # "
+Q$ 4 +O=$
OO 4 +O>$ # 4 = # /.
\ 0 R 0
OO
" , = +
= " = 7 \ = O 4 4 R # (
" = . + 6
= = 1 - O
&1 # +O>$ " 4 . -
\ " 4 (
. +OP$ .'
U
S?
W "( (# # "( ! # ! (1$! 4 = # 4 # 0! (1$ ( )# . ,
$ 4 ## #
4 = # 1+! +,! +O5$
4 , ! , / #$# L
/ 65 < 01# E"1# -
:
$ ,
4 & +OP$
U ( $L
+O>$ = - 4 & * 4 & -
4 & 4 T +O5$ & 4 & $ 0
+O5$ U(
= - 0 " " # 4 4 4 4 " 4 U
4 4 4 4 +OR$
! 4 +
+O5$$ W +OP$
+OR$ & & :4
* 6 <- '"!) & ".
- # F (
(
. U( " - -
+O>$ +OP$ = 4 & & & ! 5 -
+OP$
.
+OQ$
4 4 & 4 ! P U V
- = 0(
- U
S?
, 66
" +4 6". Z [L .' - . 66
! /.
/.
+OP$ T
6". Z [ (
T
.
. -
.' " ' -
4 + $ -
+OP$
W " (
6" . (
' U ( (
. 1 +$
! ( (
4 . +OQ$ (
6
4 1 . +O$
/ 65 < 01# E"1# -
:
1 ( U
= + $ +O>$ +$ . 4 +OQ$ (
4 4 . . 1
7 7 . 7
(
" 7 7 + $
4 . 1 +O$
M . (
. " 4 . 1 .
(
. " 4 .' .
. +O$ X (
(
k
Z
[ + $ 4 4 (
, " " " 4 (
(
- 0 Z
[ .
.
M .
67 7"(. +Ul $ 4 # (
" +
4 $ ( . . 4 1 4 1 4 4 . 1 4 1 1 +$
! 6 " .
. .
.
+O$,
. 1 4 1 1 4 1 4 1 . 4 1 . 1 4 1 1 4 1 . 4 1
. C 4 4 " 4 4 ( . 4 1 Z[
2 ( (
" 4 .
6 " - +O>$ W
.'
:
* 6 <- '"!) & ".
( O "( 4 R / #
) # ' "( *('# R R
**'( 4 R #
*(
+O>$ ,! = 0! *(
+$ +$ #1 ) (1 '( 4 ( # # +$
U / +O>$
+$ .
+O$ = . 1 4 1 1 6 1 6 +$ U( *
+O>$ +$ +$
. 1 = +>$
0 1 4 1 1 (
" 4 " 4 U R +$ 4 1 4 4 .. 1 4
1 1 . 4 4 1 4 4 1 . 1 4 1 "
+>$
C-SY
Sp" Y 4 ( . +=$
4 4 1 4 4 1 4 "4 1 " " 4 "1 / +=$ ". 1 . +>$ (
- " 0 - +O>$ " + +O=$$
+O=$ +$ / 65 < 01# E"1# -
:9
2 ( +$ -
+O>$ 06 ( \
V
. 1
.
06
* 66
.
' ' 37
7%*+7;. +YlVp$ ( . 4 1 . . . 4 1 4 4 . 1 +5$
. 4.1 11 . . X
Ul 6 " . . .
. +O$ 4 4
. " - ! R Ul YlVp .
Z
[ .' U (
" 4 R ( 6 4 " 4 6 +5$ " 6 # 6
1 1 6 . 6 . 6 6 . 1 6 . . + +$$ " 6 (
W "
4 (
6 4 0 . (
R YlVp
?(
# 6
" +O$
(
" = " Ul YlVp . . 6
" + .'. -
+Q$L OOOO$ . (
- 4 = # %5 >O& /
6
" - " . 6L OO " 6
" .
. (
4 :
* 6 <- '"!) & ".
N Ul YlVp (
%O5 > > >5 =& X (
- M
Ul YlVp . 6
" W .
-
6
6
+ . YlVp$
+O>$ . - 4 " .'
T Z
[ -
. . + $ " %5& V
- 4 =O - (
" 4 " (
+ +=O$$ Ul YlVp (
(
0 ( .
U .
+
$ +OP$ . U
S?
C
.
" .
. . "
"
* . .
" 6
/.
" - T ' .
%O O5 > >O >5 =&
§ 3.3. Методы сопряженных направлений
! ' (
.
"
/ 66 <- &24-3 &)
::
. . -
'
-
" 0 " . 3.3.1. Методы сопряженных направлений для квадратичных
функций. M
(
"
R +O$
" 6
"
R R $ +$
R # (
" $ R 0 ( .'
T O * R #) / > / >
m
' +
. ] O 6# ) '
R( ) 1+# #)# U ( (
( @ @ / 1
(
@ (
M (
R ( - T' #)
4 6
"
+$ ,
= +$
66
* 6 <- '"!) & ".
# (
- =
. = = +>$
R
= +=$
?
+>$ = R = 6
" Y (
. ' L (
"
N . (
(
W .
' 6
6, . (
-
" 6
" +$ (
"
- . (
W O "( R / ) # # ' $ R *('# R R +$
0! +
+
+) R (# 4 +$ +>$ 1+ + #)
## # +!+
$ , +O$
U 0 (
" +O$ . "
. ∈ R .'. +5$
$ "
-
+ OOOO$ 0 O R (
@ +P$
/ 66 <- &24-3 &)
6
@ * +$ = = +=$ T @ =
M +P$ (
@ @ +R$
@ ( +5$ 0
+$
(
= +=$ +R$ (
! O U O (
R +$ +>$ .
(
+
$ -
0 / T (
(
(
-, (
4 " 4 . Ul YlVp + $
(
%5 >O& *"6 Ul
YlVp . -
" (
* " Ul
YlVp ( " " 4 R - ( Y " (
( (
6*
* 6 <- '"!) & ".
3.3.2. Метод сопряженных градиентов. 0(
- (
#)
4 !
@ +Q$
@ . (
Z
[ @ +O$
@ \ O 0 R O k k @ 6 +O$
0 6 +Q$ 0 = 6 +=$
> 0 6 +$
= k - O
l +=$ = + 6 +O$
@ # k ' = + @ ( + W +Q$
@ .
=
+OO$
+ +O=$$ W ' = + @ *.' (
(
W "( (# O
0! +
+
+) R #
! ! O ! +(1 #)(1 ( !
/ !(1 ( R / 66 <- &24-3 &)
6
U * - U " (
(
. +OO$
(
1 (
/ 1 +O$
0 +Q$ (
" (
O
@ / 1 +O$
U / 1 +O$ .
/ 1 +Q$ (
" @ +O$
/ +$
= ( +O$ 0 +O$ - +O$ *
O (
-
" 6
" +$ (
" . (
-
(
6 +O$ @ " C .
/ 6 +O$ (
@ (
(
64
* 6 <- '"!) & ".
! 6 +O$ ( @ @ 0 6 @ . ' . (
. " T( (
(
( + $ 6
" - . W
0
6 L 3 %5 >O =& 0 (
6
@ /
( +Q$ +OO$
OO
(
+>$ = = (
0 " (
. 06 %=&
U -
.
Z
[ - + $
N (
. %O > > =& M
. 6 @ W
.' " " .' "
+ "
$ , ' 0 - .
(
. -
" U
(
/ 69 <- ! &2
6
%5 > >O >& 0 ' ' . .
(
- ' . - 0 (
.
Z [
\ (
.' 6 " - (
(
- YlVp 6 +$ " 4 '
- " M
(
# YlVp "
" 4 ( -
! ( R R (
R +Q$
6
(
4 " 4 6 +$ 4 ! > N- (
" 6
"
R R (
§ 3.4. Методы нулевого порядка
X 6 ( ( ( * . C
-
(
R R # 6
" N" -
"
+O$
R - - (
" 6
" T
. - "
(
' (
6
" M
- (
" 6
" 6
* 6 <- '"!) & ".
+
. " 6
"$ 0 " ( " 6" 6
"
-
" + . #! $
"
" 6
" ( (- - ( ( T
-
. (
" 6 "
( ? " L '
5
C( - - (
" " / (
6
" R (
,
0 ! > ' ,
0 ! ! > " # ) ) # R \" "
'
- 6
" / ! ! ! = 0 +$
0 R . - - = . . 0 + OO$
M
(
(
6
" O U 6
"
R R / 69 <- ! &2
69
0 '. .' Z [ 6
" 0 , ( " ( - 3 "
/ +
(
$ ! ( = +$
) ) ) ) 2 - = '. " = R = = R ( 6
" W " -
" 6
" 6
L " " . 0 - / " 6. = 7 . = =
/ ( - . = . = = 0 . = . = = k . = + -$ . = 7=
. . " -
W 6
" (
%> O >& M
Z
[ 6
* 6 <- '"!) & ".
(
- 6
"L O - C . , "
+O$L %=&
? " ( 0 (! ! ( +$
) > " .' 0 (
! " 6 R - . '. "
.' U (
. %>&
/
" . 6
" 2
(
+ ( -.'$ .' , 6
" ]-" ( R 66
" . R ] + >=$ (
( 6
" 66
" Æ "
' (
X (
4
( ( !( ! ! +$ 0 ! > " = Æ "
(
( "
+O$ . %R& + "
$
! O M (
" 6
"
R R - - '. "
! W ( 6
"
R R (
МЕТОДЫ УСЛОВНОЙ ОПТИМИЗАЦИИ
X "
? -
. § 4.1. Методы решения задач с простыми ограничениями
M(
" +O$
R # ( Z [ + $ R R # 6
" T
. " -
(
/
(
R '
" + OO OO5$ /
( "
+O$ O +$
( " +$
" " . " + (
OO OO O>$
4.1.1. Методы проекции градиента. ' ! " (
( 0 = +>$
6
* 9 <- !) & ".
- = . " .' '
.' " OO T
6
"
! R R ! = =
= = / ( ' = ' -
! = = R ! = = " = #
= # T
. !
' 4 ( OO +O5$ = = +=$
/
" (
= 7 . ( 6
" \ +
V
$ #! . = = 6
+
' = \ O 0 0
" , = + = " = 7 \ = O 0 = 0 6 +>$
1 - O
! "
+O$ - = ! ( = R " - = '. .' / 9+ <- :2 "( &- (2 * " T
'.' OO O> 0(
. .'
,
+5$
= = = T
, = = = = = = = = = = OOP
] O "( ) R ( ( *('# , R R **'( R #
2,'( R 0! # ! R +=$ # 1+! = ( =# !
= ( ) +P$
U M O> +5$ 6
+P$ . = =# = = = = = = M . ( \ =
=
+R$
= # ' C = +Q$
. \ = = *
* 9 <- !) & ".
W O "( ) R ( (
*('# R R **'( R #
2,'( R 0! 1+# # 1+ ! O ## # ' +O$ 9 #
($ ( *('# ! ( # 1+ ! " R
" +O$
U \L +5$ . +OO$
k "
+O$ = = +OO$ . R +
+ 6
" R $ W +OO$ . +O$
" R " OOQ -
+R$ +O$
" = +O$
0 '. -
+O$ " " " # + OOR$ +$ "
* " ( OO / 9+ <- :2 "( &- (2 T
( "
+O$ 9 ! O O (
U 9 + O$
W ( 6
( O + (
9 "
2 9 +O$
R Æ
+O>$
Æ 2 # 0 R ( O / # 6
" # 9 ∅ + OR$
W "( (# O +O$ +O$ # ) !
+O>$5 4 Æ 2 "( ! ( 4
4 (#
0! 1+# # ! O 4 # ' +O$ 4 *(
' # !( ( ! #
U (
6
" O> /(
"
( OOQ O>
! U C
+ ( -$ "
" (
6
" (
%O > P&
C( " . " " ( +(
# " $ ( 4
* 9 <- !) & ".
- ( U
66
" '
" # L %5 P& ! " -
. L 4 P
! .' 6 ",
$ Æ R Æ R
Æ # R $ R R
> $ R " $ # > $ #
$ > R
$ > $ $ $ R $ R $ R R
$ $ R
R $ R $ R $ $ R $ R $ R R
$
2 ( ( " +>$ . = = " " . =
" \ = N / 9+ <- :2 "( &- (2 (
= ( ( = = = = " ?(
" . .
O 0 . (
W " 6 .' . " 6
" '
6" .'
" ! > M (
R - " .' 4.1.2. Возможные направления и методы спуска. T- 6 '
(
. ' 4 O " U " 6
" (
T 0 R )
( R . " " ?
( (
( W
. ( *.' . (
] "( ) R ( (
0!
() ] "( R () * 9 <- !) & ".
! +) , R R **'( 0! ,
) # 1+! () 0 () / 5 ()L
) R ( # (1 0 () / 5 ()
()
! . 0 # (
/ 5 / 0 # ( ! = + 66
(
(
$ (
( ' "
+O=$
( R ' " 6
" C .' .'. "
. ,
= +O5$
- = . +OP$
! +OP$ . = ∅ " . W
Z[ (
" 6
" ( C
(
( " - = k R +O5$
+OP$ ' " OO
k # ( +OP$ = " = # =
+OR$
= + = +OP$ = U
= ( " / 9+ <- :2 "( &- (2 9
OO = = " '
' = (
"
! 5 R $
R # " / $ R +OR$ = .',
$ / = $ / = 0 .' " 4.1.3. Методы условного градиента. Условные методы Ньютона.
Y ( +O$ (! !
. .' (
+O5$ + U ' (
- +OQ$
" " 6
" +O$ .' #
. -
+OQ$ # +-
' 0-$ ! k "
+O$ + +$$L " . k
( OO . W . (
!
6
" ( ] = +OR$ " " - = * 9 <- !) & ".
U OL
%P >O& Y (
6. + %O > >&$ "
- % >O& W C . - -
+OQ$ " 6
" k # +OQ$ # L P
! P 6
" R R 66
" R .' 6 -
+OQ$,
$ Æ R Æ Æ $ R " $ # > $ #
$ > -
( .
> $ " $ # / . .
. . -
" 6
" 6
" .' "
*. .
6 4 > (
6
"
" 6
" k
" " "
6
" 0 (
:1 +O5$ ' -
+$
/ 95 <- " 4-3 &)
:
k # +$ # L 4 P 0 -
+$ ( ' +O$ k ( 6
"
(
' T
6
6
" 6
" .' , ( .
(
" + (
6". Z
[ "
6
" '
4 >> 4 =>
! R M (
- - "
§ 4.2. Методы возможных направлений
/ ( " " - 4 >O ( "
, " ' /.
' -
"
( ( N (
Z
b
[ - ( U (
.' . 6
". . ' (
-
.
X 4 )
4 6
"
,
+O$
R +$
6
". R R (
R R T 6
*6
* 9 <- !) & ".
/
. >O '. ,
= +$
- = . +>$
. (
( # -
6
"
(. X . (
Z[ Y " (
.' +$ U ' (
- +=$
3 R R 0 / 5 > +5$
0 # (
/ 5 5 / 0 # ( +O$ +$
0 ( > ( -
+=$ +5$ U
∅ - +=$ +5$ OOO
3 # . -
+=$ +5$ T
" 6
"
+=$ +5$ k "
.
( O "( *('# R R +)
R **'(
! ) +$
0! ( !(# !
## #
7' R
, +=$ +5$ 5 5 / '#
+O$ +$
R
/ 95 <- " 4-3 &)
*
U /
?
Sl
" '
% ∈ R +P$
0 % / 5 5 k -
+=$ +5$ ( -
O> +=$ +5$ . . (
O>> '
8 8 / 5 8
8 +R$
8 8 0 +Q$
N
+R$ 8 8 / ∈ 5 (
W ( . . +Q$ % +P$ 8 ( . N . . +Q$ 8 8 0 8 8 #8 / 5 "
+O$ +$ (
O ( k ( OO >O . *
+=$ +5$ -
(
(
0 5 ∅ . 6
" U - = "
OO (
= = = # = = " = # X +>$ k ( +
6
" 0 / **
* 9 <- !) & ".
= 6
= =
/ ( = "
- "
+ >O$ k ( - ' . C ( = ( ( (
(
' Z[ .' "
+O$ +$ *.' ( %>& U
5 5 +=$ +5$ +O$ +$ Z[ X ( . = - '. (
(
b- -
M Z[ 4 - " 6. Æ ? ( .
5 / 0 Æ k -
3 .' +=$ +5$ Æ ' (
0 Æ . ?Æ . " -
U !
(
( . ( "
+ %O >&$
! " . 0 (
" 4 >O 0 ' ( . "
%> >O& (
( (
-
+O$ +$
(. (
Z
[ -
. " 6
"
( - !
66
/ 96 <- :2 "( C (2 8 *
' (
. (
§ 4.3. Методы решения задач c ограничениями-равенствами
0 6 -
+O$
R +$
R R # 6
" R R # (
/
. (
(
+O$ +$
L 4 O> " -
1 ( 66
".
( -
0 4 >P
-
> > ' 6 0 (
- - T
, ]
( C-SC
SW ' + "
( .' $ T "
-
4 >>S>5
4.3.1. Методы решения системы Лагранжа. *"
+O$ +$ . ]
(
- +$
R R R - - # 6
" ]
( / +$ - R R "
.' ( ]
( (
+$ /.
O,
- - - - N- .
. ". 6
" ]
( # ' (
*4
* 9 <- !) & ".
"
+O$ +$ - R # .'
(. ]
( W .' (
- ' -
- - - - +>$
+=$
- R R W :1 ]
( .'
\ O 0 - R R O 0 - R R -
+>$ +=$
1 - O
W O "( *('# R R +) R )
**'(
R 4 . "( ( !(# !
/ '# +O$ +$ - R / 1$ ) 2!) "( '
*( OP ( ! # 0! 1+ +) - R R + - # 1
! O # 4 # - 4 4# 2,'( #
U W O (
"
- - N 3 - -
- - +5$
+P$
R
/ 96 <- :2 "( C (2 8 *
1
( . . +5$ +P$
- - - X -
/ +5$ - +R$
1 . +R$ ( - - W 3 - " - (
! " +>$ +=$ " (
U -
' %O& "
.' . " %>&
C
' . + OO$ X ( " /.
]
( ( + 4 >> 4 =>$
M
"
- (
-
(
- (
U
(
" "
.' ( ]
( - - '
(
" ! O ! (
R *
* 9 <- !) & ".
(
- R - A A R # 0 . - "
+O$ +$ / /.
- R ' A *
" O
N ]
( +$ ( /.
6" + O
%5&$ ( -
%O& Y- . $ - " - Z[ "
+
- + " " + R . ' * +$ (
- " - - R R +Q$
V
-
. -
+$ + - $ 0 ' -
+$ (
' " +Q$ "
-
]
(
"
'
+O$ +$ . /( 6 4.3.2. Метод квадратичного штрафа. M 6
"
" ". 6
". .'
Z-6
[ -
"
/
-
6 ' " 4 >P !
½)
7+# ,
# , V WO'
NU;ON rOPPDGM EOCpJNP
/ 96 <- :2 "( C (2 8 *9
( +O$ +$ 0 , *
4 *(' ! , * # (
, * +O$
! R R ! " ! ! . ( -6
0 "
! R +OO$
. +O$ +$ ! , * +O$ +$ .'
\ 0 R .
O 0 R "
. +OO$ "
6
" 6 +O$ 1 - O
U "
+OO$ " !
6
" (
.. (
. " 6
" +OO$
\ (
6 "
( (
+ $ 2 (
Z
-[ (
-6 (
- M .' -6
W "( *('# R R +) R R **'(
R 0! ! !( 1+# # R (
!(# ! ## # ' +O$ +$ 3 ! # 1+ 4#$# - / +O$
*
* 9 <- !) & ".
! - R / + $ 1$ ) 2!
)
U U ( - ! - +O$
- M '
(
" - > " (
- T. 66
" -
+O>$
- - / - / +O$ - - C +O>$
"
W # "
+O$ +$
- - # ( ]
( .' "
*
-
+O$ +O>$ 0 ' +OO$ ( "
"
*.' ( W "( *('# R R +)
R R R "( R ## #
! , +O$ +$
0! # Æ # # 1+!
+!+!$ ,# ! Æ
'# *('# # *( +O$ +O=$
/ 96 <- :2 "( C (2 8 *:
# 1+! +,! ## # , +OO$
! 0- + OOO$ . '
U 0 Æ -
Æ
+O5$
!
6
" R R ( Æ 6
" . Æ U( -
+O5$
U
! ! Æ
+$ +O$ ! ! Æ
Æ
Æ +O5$ W
6 R . + $ +OP$
T. Æ +OR$
+OP$ ( W +OP$ +OR$ +O5$ #
-
6
* 9 <- !) & ".
/ Æ 6
" +O=$ Æ - T
. -
+OO$ ! U '
+O$ +$ -
'
( -
+ ( -
' -
( 9 R Æ 9 Æ R
9 Æ ( -
(' 9$
! 1 .
-6
6
" ! B R B R R # +
$
R -6 6
" .' B B R *
. -
+O$ +$ ( "
+OO$ . .' 0 (
(
( - +OO$ " 6
" 6
+O$ . "
. (
"
( (
" (
( (
X
(
( .
- + (
( $ (
( W > "( (# O
0! ($ (1 , # )! +OO$ '
/ 96 <- :2 "( C (2 8 *(' *( +O$ (1 '(1 ( +OQ$
, " - , " U 0 (
C + C +$
Φ R R R R R Φ + C
- R # .' "
( ]
( ( + - W Φ + Φ + - (
"
#
' O (
. Φ + .
6
" + OO$ '
+ R R Φ + +O$
+ R R -
+ = C 6
" + 66
" C O "
+ + , Φ + , - +$
, ( # # W . +$ C ! "
"
"
+OO$ C "
+$ . "
+OQ$ .
C /
" R R / ( / "
+OO$
C +$ ( / + -
+O$ # - / + - / + + # X # *
* 9 <- !) & ".
"
+OO$
- C 6
" C 66
" +
- (
.. (
. 6
" 6
" C +$ (
.
+$
R U66
" . .' 66
"
,
, +>$
. C ( OO 6 6
" (
- *
.'. Z
.[ -6 l R -
+$ = -
( +$ = 0 (
-
+>$
( " '. 6 W N > (
(
(
* '
" (
(. 4 =
U "
+OQ$ - + > # .
- -6 .' , - -6 "
" +OO$ -
.
+O$ +$ p6
. 6
". !
( . / 96 <- :2 "( C (2 8 k ( - +>$ ( ]
( , - Z[ -
( , ( 0 "
+OQ$ - -6
( ! > U .' 6 .' (
>,
$ . -- "
- - "
$ . - " ! (
"
+OO$
6
O= W (
"
+OQ$ m
-
"
0- ( - -6 (
T
( -6 -
6 (
+ .
-
* +OO$ ( , " 6
"
Z(
[ + OL -
-6 -6 (
%5&$ -
0 '. .
+ - -
"
"L %R& C ( -6 > -
+ (
$ 4
* 9 <- !) & ".
-6 (
! = N- # "
-6 L 3 .
66
! 5 N- R -6
! P W ( R 4.3.3. Модифицированные функции Лагранжа и точные гладкие
штрафные функции. T
.' -6 +
$ -6
"
6
" +O$ +$ 6
" ]
( *'
4
*(' 2!) +O$ +$,
+=$
R R R - - " (
(
3 .
' *"
+O$ +$ "
- R +5$
- # .' ( ]
( -
]
( +O$ +$ (
"
.
+5$ N ( - (
6". ' (
+ O$
/ ( O (
" - +5$
" (
- (
0 6"
6
" ]
( ( / 96 <- :2 "( C (2 8 - - - R - - R - R ( -
- ( -
]
( +O$
+$ 6"
6
" ]
( ' 0(
- ' (
.' ! R 6
" R R (
R → R ( 66
" R # "
+O$ +$ ( ]
( - R U . - "
- - (
"
- R 6
O= M" *'
4 *(' 2!) -
(
- - "
- R +P$
.' - "
(
6 +O$ +
6 -6 6"
6
"
]
($ ( Q ( 2 ( " ( ( " L
\ 0 .'. R - R O 0 R "
. +P$ "
6
" 6 +=$ - =-
* 9 <- !) & ".
- - 1 - O
*'. ( 6 " 6" T %5 >O&
! Q - R R "
+P$
- + O$
W = "( (# O
0! ($ (1 Æ
, ,
$ # 1+ - - Æ !
R - - Æ - Æ - R
+P$ ' *(' *( +=$ (1 '(1 ( - - , " +R$
- - - , " $ ($ ( Æ Æ# # 1+ (+
1$
R 1+ - R # 4 - - Æ
+Q$
*(
- - - # - + - - Æ # #! - $ - - - → 4 - #
4#
' L - (
- (
$ (
> U $ ( / 96 <- :2 "( C (2 8 9
> (
6
" (
$ '
Æ Æ# . - .'
+Q$ - ( - Æ
k +R$ $ - $
" - - " - -
$ - - $
" - - " - -
- - - . C - ( - (
(
%5 O>&
*
= - .
+Q$ "
+P$ (- -
. +O$
+$ - - + -$ U Z
[ "
. . ( (-. -6, ( (
" T
-
+O$ +$
0(
- R -
+Q$ M
- (
(. ]
( (
- -6
! O U .' (
$
=, . - - Æ " - - (
"
- +P$ 6
O= + (
$ > R$
* 9 <- !) & ".
* 6"
6
" ]
( ! , *
*(', 6
" -6.' -
6
" 0 6
"
! R R R
! - - "
-
- " "
-
+$
! - - R R
+O$
+ +Q$$ ] . -
]
( +O$ +$ "
+O$ ] O "( *('# , R R +) , R R )
**'(
R 4 . "( () 0! # ! - R # ( # ( -) ( ) !( +
+
+ +
# 1+!
( ) ( -) +
' +O$
' *(' *( +$ ( ! / '# +O$ +$ - / 1$ ) 2!)
U 0 "
-
(
# U 6 # - "
-
(
k . . - R R - "
:
/ 96 <- :2 "( C (2 8 . - - R (
+
(
(
. - '
(
"$ -
! - . - - - ( "
+O$ - - # -
]
( +O$ +$ W 5 "( (# O
0!,
$ *('# +) )
**'(
# #! # # 1+! ' ! - )
+! *('# ! *( +$$ ' - +O$ *(
O= ( ! # L
$ ($ ( # - !( +
+
+ +
# 1+! +O$ (1 '(1 ( -
U U $ (
66
" 6
" ! - (
- * $ O -
- ]
( +O$ +$ ( 6
" +
OO$ O (
" - (
! OO U (
$ 5
/ -6
6
" -6 *' (
(
-6
6
" / 6 (
( R R 46
* 9 <- !) & ".
6
"
! R
R
R
! - - ( -
- " ( - +$
! - - R R +$
C - -6
6
" ! .
-
]
( +O$ +$ "
+$
] "( (# O +
) ( , R R( ) **'( R ! # . (( ()( ())) 0! # ! - R ($ (1 ( -) # 1+! ( -) ## # ' +$ '
*(' *( +$ ( ! / '# +O$ +$ - / 1$
) 2!)
U * ( O 0 . - "
-( . R ( ( (
R - ( -
N 3 - . -
-( - +>$
( ( - M ( ( ( -
+=$
/ 96 <- :2 "( C (2 8 4
W +>$ ( -( ( ( - - ( ( 0 - " (
U - +=$ ( 0' +>$ 3 W P "( (# O +
) ( R R **'( ! # . ( 0! ($ (1 - # 1+! +$ ' *('
*( +$ (1 '(1
( - *('# +) )
**'(
' ! - ) ' - *(
O= ( ! # U 5 + ( OO$ O (
(
"
( ! -6
6
"
- (
-6
6
" U 6
" +$ +$ . - 6
(
- ( Z-
[ ! O ! ( R ( O
(
( - ( +$ 6
" ! - ! - - R
. 4*
* 9 <- !) & ".
! O U " +O$ +$
" 6
" 6 +$ +$ ( - + O$ /.
(' 6
" (
§ 4.4. Последовательное квадратичное программирование
C +'
# @AB <=>?=@ABCD >?CEFCABG HFIJFCKKB@J $ -
.' . " " 0 ( '. 6
6
+ $ -
L 4 P W
" * @AB 6
.
" c 6
"
/
@AB "
" .
-
]
( ( ! -
/ -
@AB 6
6
"
' -
" .' "
.
4.4.1. Ограничения-равенства.
. 66
" 6
" R R (
R R
R +O$
R +$
/ 99 1 ( & 4
R # ' (
"
+O$ +$ W (
6 +$
R +>$
6 R # "
/ ( 6 = " 6
" . ". 6
"
+ /.
>O$ T
U " (
(
. 6". .' * .
". (
.' .' ' .' -
(
- ( 66
"
-
0 "
" . -
C . . 6". " (
". 6
". +=$
6 - - R # " ( ]
( -
.' "
R R R - - # 6
" ]
( +O$ +$ ! " 6
" +$ +>$ " 6
" - ' U + 6
$ (
" +$ +>$ " >O .
" ]
(
+O$ +$ /
]
( - +5$
44
* 9 <- !) & ".
.
" -
- - - - +P$
+R$
- R R - R R # '
(
-
. +5$
U
R # "
+$ +>$ R # .' ( ]
(
X -
6 R R *
.. +P$ +R$ ( . " 6
+=$ W 6
.
T- ! ! !
# +@AB$ \ O 0 - R R O 0 R "
. +$ +>$
6 +=$ 0 R .' "
+$ +>$ (
]
(
- 1 - O
0 - . (
- O ( . - /.
]
( +5$ >O
+
.$ @AB
0 6
" (
6
OP >O @AB - . Y / 99 1 ( & 4
]-" ! " /.
]
( @AB X " "
/.
" ( "
T
@AB .' -
(
! O 1
+$ +>$ " 6 +=$ 6 - # C (
' )
! N +O$ +$ *'
' ! = = # +>$ 1
@AB + .' 6 M
. 4.4.2. Смешанные ограничения. (
R R ( 66
" R . " -
+
$,
+Q$
R +O$
R # ' (
"
+Q$ +O$ k
.'
+$ +>$ .' ,
+OO$
6 R +O$
U -
! ! !# +@AB$ .'
4
* 9 <- !) & ".
\ 0 - 8 R
O 0 R "
. +OO$ +O$
6 R # " 0 ∈ R < R .' "
+OO$ +O$ ( ]
(
- 8 < 1 - O
R
R
0 - (
( .' " 6 +O$
6 - 8 R R R R - 8 - 8 # 6
" ]
( +Q$ +O$
! ∅ " 6 (
+OO$ +O$ -
-
"
+ "
6
" $ T
(
- - +Q$ +O$ ( - 8 (
. "
6 +O$
( - 8 - 8 + 6
"
6
" ]
( > ( O$ '
+OO$ +O$ "
(
Y ( "
' 0 "
+OO$ +O$ .' . " O . \ +OO$ +O$ . ' -
.' -
.' -
. ( ]
( < L
4 P / Matlab . -
. ! / 99 1 ( & 49
- " 6 (
"
"
-
T %>=& " " @AB (
"
W O "( *('# R R +)# R R R R )
**'(
R 4 . "( ( / '# +Q$
+O$ - R 8 R / 1$ ) 2!) "( 5 '5 *(
O>= ( ! # ) ( ! 0! 1+ +) - 8 R R R
+ - 8 #
4#$(1# - 8 1 ! # )! ' 6 + # !
+O$ + # '# +OO$ +O$
1$# (1 ( 4 4#
2,'(
#
U C 0 / (
5 / 0 # ( +Q$ +O$ ( * R R
× R ( +OO$ +O$
- 8 * - 8 . "
. ( ]
( < N C-SC
SW +OO$ +O$,
- 8 < +O>$
+O=$
< +O5$
< 0 0 / +OP$
< * * R . 4
* 9 <- !) & ".
( ' ( < R
× R < +O>$S+OP$ X +O>$ ( 6 +OP$ < / 5 0 (
Φ * * *
- 8 <
"
!
"
!
"
!
"
!
Φ 3 !
"
<
0
0 "
!
< 0 0 - 8
*
Φ
3
< 3 * +O>$
+O=$ +OP$
*
. "
+Q$ +O$ .' ( ]
( Φ 3 - 8 3 - 8 C Φ 3 - 8 "
! "
!
"
!
"
!
8
0
0
"
!
!
"
!
8 0 0 "
!
8 0 0 "
N 3 < Φ 3 - 8 < +OR$
+OQ$
8 0 0 < / +$
/ 99 1 ( & 4:
M +$ < / 5 0 / 5 +O$
C .'. 6 +Q$ +O$ % 0 % / 5 +$
+ O>>$ +OQ$ +O$ 1
( . . +OR$ +OQ$
+O$ - 8 < - 8 - 8 <
0
X -
/ +OR$ +O$ < 0 1 (
- < / 5 W
3 < " Φ 3 (
(
. Φ 3 . 6
" + OO$ '
* 3 * ' (
+ < * + * Φ + +$
0 - < 8 T. + .
- 8 +>$
0 0 / 5 < / 5 +=$
* (
Φ -
+$S+=$
. - 8 +O>$S+OP$ 6
* 9 <- !) & ".
* -
< 0 - ( (
( -
* ( * R R * # R T. # "
+OO$ +O$ .' . < < # (
]
( .' "
! +>$ +=$ - 8 +O5$ +OP$ +O>$S+OP$ .' < (
+5$
0 0 / 5 < / 5 +P$
M" . -
< +O>$ +O=$ +5$ +P$
N " ,
R
0 / 5 ] -
6
OP T.
.'. ]
( 6
8 / 5 - 8 * -
- 8 + -
(
$ *
O /.
-
. . 6
" (
]-" .
/
' - 8 " /.
< < -
' +O=$ +5$ +P$ - 8 8 0 / 99 1 ( & < 0 +R$
+O>$ - / 8 / 5 , . R 8 R 8
.
8 0 8 8 0 , 8 8
X " +O>$ +O=$ +5$ +P$ ( /.
" +O=$ +5$S+R$
*
. O . .' /.
$ ! ( - 8 - 8 ' ( + OO$ 0 - *.' ( .' T
(
" 6 .' +O$ (
W -
(
- @AB U
S? + $ T 6 (
%=&
W "( (# O ) (# !
"( !
# - 8 ! 4 # - 8
0! 4 ##
# 4
(
!
! 6 - 8 & +Q$
!
% 0 % / 5 % / ( +Q$ +O$
½)
= (*9) > # % , ,> " % &' > 3 # , -,> , !
"> " !
*
* 9 <- !) & ".
U /
( - 8 + C-SC
SW,
6 - 8 +$
+O$
+$
8 8 0 0 / +$
+OO$ +O$
M +$ 6 - 8 - 8 8 - 8 & - 8 8
- 8 & +>$
"
+Q$ +O$ .'
( ]
( ( - 8 - 8 M +>$ - 8 6 - - 8 - 8 & +=$
8
( & W +=$ - 8 6 - 8 8 & +5$
8 8 +$ 8 / 5 O>> +$ . .' ( % - - 8 8 % % 8
8 0 % +P$
/ 99 1 ( & ! - - 8 8 + OOO$ / +5$ - 8 6 & ! * & -
+Q$ +Q$ ( +O$
& C +R$
C & & & +Q$
\
'. +$ +$
8 8 D / 5 0 +>$
0 D / 5 +>O$
0 D / 5 8
+>$
5 / 5 8 5 / 5 8 +>$
D & & / 5 M -
+Q$
+>$
' R +>>$
C 0 D / 5 & & +>=$
( % M +R$S+>O$ +>>$ % ∈ +P$ -
- - 8 8 % 8 0 % 4
* 9 <- !) & ".
+>$ +>$ U
( .
. +=$ % -
- 8 6 % - 8 % & % +>5$
U . 2 - 8% % 2 % % + $ T. +>5$
2 % - 8% % - 8 6 % - 8 % & % - 8 6 % & % & % ! %
- 8 6
& % & % & % & % +>=$ # OOP # +Q$ W % & & / +>=$
% & & X '
" R " . " " / . - & / 9F <- :2 - E!:GE!GH
*6
O .' . @AB .
+ $ /
(
- .' $ ,
- 8% % % % 0 % / 5 /
5 / 5 8 + 8 '
( - 8 . $ ! 5
+ 5 T
(
-
@AB . -
" # ?
Sl" T
6 (
%& C-SC
SW 0 .
(
T"
@AB . "
+ ( .' 6$ 0 " @AB
. 4 =>
§ 4.5. Методы решения системы Каруша–Куна–Таккера
0 6 .
-
C-SC
SW +CCW$ " -
U (' ½)
7+## # a, # V hhBhL ( ,'
, hCYJMd PO;JMN'JYNOY PUi;DOMC ;JMNDCDJM)
* 9 <- !) & ".
T
(
.
-
6 CCW O (
.
- -
L .' -
(
(
M
' 6
CCW, . (
(
. N (
. 6 CCW "
66
2. ( 6 (
U '
"
' '
"
4.5.1. Эквивалентные переформулировки системы Каруша–
Куна–Таккера. R R # 6
" R R
R R # (
N +O$
R +$
*"
.' (
]
( . CCW
- 8 +$
8 8 +>$
R R R R
- 8 - 8 # 6
" ]
(
- 8 # -
+$ +>$ C 0 / (
5 / 0 # ( +O$ +$
k / 9F <- :2 - E!:GE!GH
9
/ 5 - 8 -
+>$ +=$
8 / 5 0 / 5 W CCW +$ +>$ +$ +=$ ' - 8 ∈ R
R
R k ( 66
" /.
>O N ( 5 * 6" ( (
( 6" 4 >5
! ( -
CCW (
6" 5 0 ". /.
+$ +=$ M (
-
+>$ (
( N
+
$ . "
C ( "
(
(
6
-
0 T O l
" B R R R *('
( -
8 B $ ( -
$ $ U (
6
" .
*('# #
B $ $ $ R
+5$
*('# ,73( +P$
B $ $ $ $ R
* 9 <- !) & ".
! O 6 +5$ +P$ 6
" . 6
" ! E R R # . .'
6
" E U 6
"
B R R R B $ E $ E E $
6
" *-
6
". B -
+>$ (
B 8 0 / +R$
*
. rrs +$ +>$ (
+$ +R$ ( T
6
" B +5$ +P$ 66
" +6
" B +5$ 6
6
" $ $ T. .' +$ +R$ 66
" -
- 8
X (
- '
/.
L >=
*'. ( . 66
" 6
" +Q$
B $ $ $ $ R
! +Q$ 6
" 6
" 6 6
" (
(
.' , +$ +R$ - 8 (
\
" .' / 5 8 . ' . 6
CCW 6
" +Q$ /.
CCW
"
/ 6 (
+ ( $ C 6 "
.' 66
/ 9F <- :2 - E!:GE!GH
:
4.5.2. Элементы негладкого анализа и обобщенный метод Ньютона. 0 6
- (
0(
-. .'
N %= R&
W O "( +) R R 2,'( ) * R 0! # ) " **'( 2+! ) * " (1
!
N (
'
(
66
" W **
' (
R R R (
R " +
# Y
$ 6**' & (
(
! > U (
R R ]-" R # N " 66
" K 66
" C (
* .' 6 U (
R R R .
R k 66
" .
! = R R # 66
" R
6
" / 1 (
5 / 1 R 6
* 9 <- !) & ".
R ( / 5 / 5 .
(
/ 5 ' R 5 / ! 5 R R # 66
" R
(
0 / 0 (
Φ R R R ! 8 B 8 0 R 8 R / B # +5$ 6
" R 8 R 66
"
Φ 8 " 8 8 8 #
" 8 0 8 8 0 / +O$
8 0 ! P 0 5 B #
+P$ 6
" l-SY R 8 R Φ 8 " 8 8 8 8 # "
( 8 0 % (
8 +OO$
= 8 0 %
8 0 (
%
+O$
$ 8 @ 8 0 = @ R = @ / 0 / 5 8 / 0 = 8 Φ 8 "
/ 66
" C .' "
. / 9F <- :2 - E!:GE!GH
( '
/.
Y (
R R R (1 ! &( % % & %
#" $
( (1 ! &( % % F % #" $
/ (
"" '
66
"
.
/
(
R R **
'(
R 1 % R '
"% #" * (
1 % % N 66
"
66
" .
. % % % R ! R U (
R R ]-" R 66
" . . , $ (
(
% % R → R ]-" R $ ( % R " % %
$ (
**'( % % & %
C
"" 3
.' (
]-" +
$ C ( 66
" . .
( , (
R R .' R +$ (! .' . *' ! Q U (
R R ]-" R . % R ' $
' *
* 9 <- !) & ".
" %
! O U (
R R ]-" R 66
" . . . C % % & %
#" $
. C % % F % #" $
M 66
" (
k (
]-" (
! OO U 6
" R R +$ R ! O U (
R R
R ( ! O U (
R R R R R (
R R R ! O> U (
R R R (
R R (
R R W (
Φ R R k
'
/.
Φ +O$
.' "
,
Φ +O>$
Φ Φ W ++$
:1 .'
/ 9F <- :2 - E!:GE!GH
\ O 0 ( 0
R O 0 . " Φ Φ ( 0 ∈ R -
Φ 1 - O
1 (
'
/.
.' T(
Φ R R LM!(#
+NM !(#
$ R . " ∈ Φ Φ (
W "( +) Φ R R 2,'( R ( #
. (1 ! &( "( ## # ,
(# +O$ +) Φ LM!(# R ( # ! O NM
!(# ( # (
0! 1+ +) R +
# 1 ! O #
4 # 4 4# Φ (
# ( (1 ! &( #
U * ( O T
+
( $ M > 66
" 66
"
C ( '
(
" (
'
, , Φ +O=$
0 " O . U +O>$ +O=$ C (
Φ Φ Φ Φ & +O5$
4
* 9 <- !) & ".
T. (
. O .
/
" C "
+O5$ F . 0 -
"
-
+O$ 4 >5 Y
66
" R . . (
Φ R R G % R Φ % (
. $ R (
Φ ]-" LM Φ G W "( +) Φ R R 2,'( R **'( . 1+( 1
Φ 0! G +)# Φ ## # +
4
( ($ # , 4 , Φ U U( T ,
(
R Φ U ( ( % # " Y
'
( % % R % W Φ )
Φ ) Φ ) Φ ) Φ % % / 9F <- :2 - E!:GE!GH
Φ % ' G U % R Φ % k , .' (
'. . " "% "% , Φ "% , Φ "% Φ , "Φ % & " & "
(
- % 4.5.3. Обобщенный метод Ньютона для системы Каруша–Куна–
Таккера. *
>=O 6
" B + O$ CCW +O$
+$ .
Φ - 8 +OP$
Φ R
R R R
R R - 8 !
"
!
"
!
"
"
Φ - 8 !
+OR$
! B 8 0 "
!
"
B 8 0 *
'
/.
. +OP$ .' +
.$ Φ NM + LM $ -
( O "( *('# R R +)#
R R R R **'(
R 4
(! R 0! 1+
4 - R 8 R +) Φ +OR$ *(' B +5$ (!
- 8 9 ) )
**'(
4 2,'( . Φ (!
- 8
! O= M OSO> (
O
! O5 U (
O 6
" B +P$
* 9 <- !) & ".
( "( *('# R R +)
# R R R R **'(
R )
**'(
R 4 2,'( "( ( /
'# +O$ +$ - R 8 R / 1$ ) 2!) "( 5 '5 ( ! # - 8% % % +OQ$
!
% 0 % / 5 5 / 5 8 0! +) Φ +OR$ *(
' B +5$ NM!(# + 5 LM!(#$
- 8
U U " 6 Φ - 8
5 ( H 5 / 5 8 H 5 H H 5 .' " (
Φ - 8 %
%
%
"
! "
!
"
!
"
6!
"
! %
"
!
% % %
# H H " " # / H ( H % . H H " % #
" " . ( H
3 - 8 8 8 6 R - R 8 R% 8 R% 8 R% W
- 8 -
8
%
% 8 % 8 +$
/ 9F <- :2 - E!:GE!GH
9
+O$
+$
0 / H 0 8 / H +$
8 +>$
/ 5 5 5 5 H H +O$
+$ .
1
( +$ -
+O$S+>$ - 8 80 +=$
%
N
+$ 8 0 / H " # / +OQ$ -
+=$
C +>$ +$
- % 8 % 8 H H 5 T. - 8 8 3 W 6 6 Φ - 8 ( (#4 )# +) Φ
+OR$ *(' B +P$ NM
!(# + LM!(#$ - 8
U U " 6 Φ - 8
P - 8 "
! "
6!
!
"
8
8 8 8 # " +OO$ +O$ = 8 $ $ 8 / 3 - 8 6 - 8 - 8 +5$
+P$
+R$
0 $ 8 / * 9 <- !) & ".
! +OO$ +O$ / 5 $ +R$ 0 / 5 +Q$
0 +P$ +Q$ U +OO$ +O$ / 5 $ / 5 / 5 8 $ +R$ 8 / 5 +$
+O$
8 0 / 5 1
( +5$ +P$ +Q$
+$ - 8 8 0 / +OQ$ +O$ C +$ +5$ 8 0 - T. - 8 / 5 3 W 6 6 Φ - 8 \ 0 6
". B R
×R R +5$ +P$ 0 - 8 R R R
O 0 .
" 6 R 0 - 8 R R R -
6 - 8 - 8 Φ - 8 Φ +OR$
1 - O
k ( 6 ∈ Φ - 8 6 Φ - 8 ++
$( ( :1 # &&0 U " 6 5 P + 6 ' ($
N '
/.
CCW (
OS O5
= / 9F <- :2 - E!:GE!GH
:
W > "( (# )# *('# R R +)# R R R R
)
**'(
R 4 2,'( . 0! 1+ +) - 8 R R R
+ - 8 # 4#
(
$(1# - 8 1 !
1 # '
6 Φ - 8 # )! 4 #
> ( T
>> +@AB$
.
.
' 6
" (
U 6
"
Y 6 .
' ,
.
% % !
"
! "
"
6 !
+$
!
"
% .
% # (
- 8 H H 8 / 8 0 R
H H 8 / 8 0 % # H H "
! . - 8 5 .
6 Φ - 8 +
.' " (
Φ
W = "( (# > "( ! # - 8 ! +) Φ +OR$ *(' B +5$ # )! ' 6 + # !
+$ 4 # - 8
96
* 9 <- !) & ".
0! 4 ## #4 . - 8 & +$
!
; % 0 % / 5 :+
. - 8 & +>$
4 ## # 4
U 0 +$ ( - - 8 8 . - 8 +=$
+5$
0 8 0 / H +P$
+R$
8 8 8 0 / H *
. H H -
+P$ +R$ . 0 0 / H +Q$
8 / H +>$
C 8 8 .
5 H 5 H
+>O$
. - M +=$ . - 8 - 8 8 - 8 & - 8 8
- 8 & +>$
"
+O$ +$ .' ( ]
( ( / 9F <- :2 - E!:GE!GH
9
- 8 - 8 M +>$ - 8 . - - 8 - 8 & +>$
8
(
& W +>$ - 8 . - 8 8 & +>>$
*
+>$ +>O$ . .' ( % ; - - 8 8 % 8 8 0 % +>=$
- - 8 8 + ; # R # $ / +>>$ - 8 . & T. ( .' >> +$
+>$ ( +5$
& C +>5$
C & & +>P$
& \
'. +Q$ D / H 0 +>R$
9*
* 9 <- !) & ".
D & & / H +>Q$
M -
+>5$ +>R$
' R C 0 D / H +=$
& & +=O$
( % M +>O$ +>5$S+=O$ % ∈ +>=$ -
- - % 8 8 % %
8 8 0 % %
8 0 % +>$ +>R$ +=$
T- -
.' >> C @AB '
/.
CCW
* .
+ $ '
/.
> - 0 ( 4 >> @AB . '
(
?
Sl" C = +>$ '
/.
.' @ABL >>
* " '
/.
@AB -
! ( 5 (
Φ
+OR$ 6
" B +5$ LM - 8 ( !(# '
/ 9I JK.2 -3 ()
9
.', "
- 8 %
"
! "
!
"
!
"
!
% (
. ( H 5 1
( W .' '
/.
.
2 ( ( - @AB " + 4 =>$ V"
'
/.
CCW (
(
66
" T
' " "
+O$ +$ -
W
> (
(
O X '
( § 4.6. Идентификация активных ограничений
0 6 "
+O$
R +$
R R # 6
" R R # (
0 / (
. -
L "
.
. 94
* 9 <- !) & ".
R # "
+O$ +$ o 6" ( 5 / 0 W 6" ( / .' , "
+O$
+$ "
R 0 / 5 ! " 'L . 4 >
(
-
+O$ +$ ? .' "
( ! ) $ W
. ( + 4 P 4 P$ X . , 6" (
5 -
- + '
-$ .' U ' +
$ " ( - N (
6" 5 W
-
6
". . 8 R R # (
8 # (
+( $ (
. ]
( 8 .' 4.6.1. Идентификация,
основанная
на
оценках
расстояния.
*"
+O$ +$ .' (
]
( . C-SC
SW
8 +$
+>$
8 8 R R R 8 8 # 6
" ]
(
) 7+#" ,
V ^;CDSO'POC EOCpJNP
½
/ 9I JK.2 -3 ()
9
# ( ( ]
( .'
"
+O$ +$ (
8 R 8 -
+$
+>$ +
( $ C
(
/ * 6" (
8 8 / 5 8 8
U
8 5 8 5 8 5 8 / 8 0 R 8 R 0 ' (
- .
5 8 5 8 ! " 8 8 R (
5 5 8 5 8 5 / 5 8 W ( 6"
(
..' (
]
( .' "
T
0 8 / Z
6".' 6
"[
( / W 6
" . "
(
/ / 6" C (
-
+O$ +$
Y 6
" . R R R '
# ( / . 8 8 9
* 9 <- !) & ".
6
" . ? /
'. Æ , 8 / , . 8&
8 /
Æ 8 R R 8 / Æ +=$
l
" +
>5$ ! '
# "
L "
(
-
+$ +>$ l.' +=$ ,
K ? . ( " 6"
0 (
"
/ Æ +=$ .
8 / 6
8 +
(
O $
T"
+ ($ . . L , O
"
( (
+'
-
>P5$L >P= ' "
-6L >= "
(
L O . "
( -
"
"
(
5 8 / I . 8 0 R 8 R +5$
! 6
"
# " " "
I R R I " # " " "
+P$
" " # ! 6
" I R 1( ( 5 8 6"
8 / / 9I JK.2 -3 ()
99
( O "( *('# R R +)
R R **'(
R (
$ (1 * *
+R$
"( / '# +O$ +$ *(
'# . R R R ' # ) / 0! # )! 8 # 8 # # ! *( +5$ +P$ ) 5 8 5 8 5 8 +Q$
U / 5 W 8 R R 8 +=$ +R$
0 0 0 , . 8& I . 8
. . / ( ? > -
"& " W / 5 8 5 5 8 * / 5 8 2 8 I . 8 2 0 2 / 5 8 5 8 5 ] 6
" I +P$ 5 8 (
6
".
I R R I " " +O$
7 ? W ( ' ? +=$
! O U (
O ?
S
l" Æ +Q$ / Æ
k 8 8 R "
( (
6"
( 5 + 5 5 5 X 6" ( ( L +$ +>$
(
( 8 / 5 (
5 8 / 8 I . 8 R 8 R +OO$
9
* 9 <- !) & ".
( (#4 )# O '
+O$ +$ ) 2
!) 8 # 8 # # ! *( +P$ +OO$ ) 5 8
5 8 5 8 U 0.
5 5 8 8 R R 8 * 8 / 5 8 8 8 , . 8& I . 8
/ 5 8 5 8 5 (
+P$ 6 +O$ 7 ? 4.6.2. Оценки расстояния. M
' 6
" . "
+=$ . (
/ ' - T
6
" . . +$ +>$ . 8 Φ 8 R 8 R +O$
(
Φ R R R + 1 ( -
+$ +>$ (
-
Φ
8 / .' "
+=$ ? . +O$
8
!
"
!
"
!
" +O$
8
0
Φ R
R R
R Φ 8 !
"
8 0 +
.' .' ( ]
( 8
( U
Φ 8 (
. >=O LM 9:
/ 9I JK.2 -3 ()
(
. >= $ / >= (
$ >=R ! (
+- ( LM Φ ' 1
"
6
". ' (
(
6
" B R R R
+ >=O$ 8 !
"
!
"
B
8
0 " R 8 R Φ 8 !
!
"
B 8 0 T"
+=$ ? +O$ B # Φ LM 8
. 6
"
T"
(
6
" (
. '
. .
' 0 +=$ . +O$ Φ R R R R R R
8 "
!
"
!
"
!
8 "
!
Φ
8
8 0 0 8 !
!
!
!
!
! !
!
!
Φ
"
"
"
"
"
"
"
"
"
? ' ½)
, # % 4> % # '
!, , # , #
!
3 ! !
" 3> > '
,#
6
* 9 <- !) & ".
§ 4.7. Штрафы и модифицированные функции Лагранжа
для задачи со смешанными ограничениями
Y +O$
+$
R R R # 6
" R R R → R # (
X 6 '
. -6 6"
6
" ]
( + .' $ > >
+O$
+$ ('. ( .' ( - 4 O>
T (
(
0 / ! +O$ +$ +$
R
R 0 / +>$
! . R . ∈
" 6
" +$ +>$ - (
Z .[ . , .' - R (
( 0 -
+O$ +$ +$ +>$ , R -
+O$ +$ 0 0 +=$
-
+$
+>$ + ($ -
R (
0 4 O> 4 > (
4.7.1. Штрафы. ; * ( R . 6
" B R R .'
B B R +5$
/ 9L MK-
*.' , *
4 *(' +P$
! R R ! B .' , * +O$ -
"
! R +R$
.' , * \ O l 6
". B R R .
'. +5$ 0 R . → O 0 R "
. +R$ "
6
" 6 +P$ 1 - O
/
.' '
> C > "6 .' ( -6 .
W O "( *('# R / ) "( ## # ! , +O$
0! *('# B R R ( # +5$ # Æ #
# 1+! +!+!$ ,# ! Æ
'# *('# # *( +P$ # 1+! +,! ## # , +R$
! O 66
" 6
" R → R (
R R R R -
R +O$ +$ O O
6
O> l U(
U . "
( +$
*
* 9 <- !) & ".
0(
- -6 +$ ( .' ! (
R % R R
% 0 0 +Q$
(
+O$
B % R # 6
0 +O$ +
- 6
" 6
∈ $ 6
"
B % B % 0 R
+OO$
0 0 R +O$
, * 6 ( , *(
B % 0 R
+O$
+
( # $ \ O 6
" B . ! , * +O$ +$ M
- C
-6 ( > 0(
.' l
" ! +P$
+O$ 66
" 66
" ( R ( 5 = / 0 +O$ +$ X (
" -
+R$
/ 9L MK-
( '. > >>
W '
' '. 6 U . 6 ( +O$ +$ +$ +>$
! U . 6
" R R . (
R R R R R
+$ -
+O$ +$ R +=$ +$ -
+$ +>$
R R R R
- 8 - 8 # 6
" ]
( +O$ +$ 0 ( 6
".
]
( +$ +>$,
R R R R R - 8 8 0 - 8 8 ] O "( *('# , R R +)# , R → R , R R **'(
R - 0! ,
) ## # ' +O$ +$ 1 )
2!) - R 8 R ( )
! R +=$ ## # '
+$ +>$ ) 2!) (- 8)
( ) (> ) (( ) (- 8)) L
) # ! R ( ) ## # '
+$ +>$ ) 2!
) (- 8) R R ( - 8) +O>$
8 0 () / +O=$
$ ( "
+O$ +$ , ( 8 ( "
4
* 9 <- !) & ".
U *"
+O$ +$
( - R 8 R +O5$
+O>$ .' ( +O=$
M +=$ +O5$ +$ +>$
C +O>$ +O=$ - 8 - 8 - 8 8 / 1(
$ 1(
$ (
U R ( 5 / = 0 +O$ +$ -. Y ( " 0 / 5 5 . . R k +O$ +$ 5 ∅ - -
! U . (
R R
R R 66
" R +$ +>$ .
R / 5 5 ] "( *('# , R R +)# , R → R , R R )
**'(
R "( ( / '# +O$ +$ - R 8 R /
1$ ) 2!) "( ' *( O>= ( ! # ) ( !
0! ( ) ! R +=$ ( !(# ! +$ +>$ ( ) ## # ' . ) 2!) (- 8) & ! . # +$ +>$ *( OP ( ! # / 9L MK-
(( ) (- 8))(% A ) (% A ) +OP$
(> )
# 4 (% A ) (R R) 4 +OR$
()% 0 () % A / U *"
(
]
( - 8 (
$ O % A R R +OR$ ( - 8 % A % A - 8% % 8 A +OQ$
M +=$ +OR$ % % 0 % / 5 % +O$ +$ k % +OP$ +O$ +$ +OQ$ "
"
8
% A +=$ +OR$ A = / 5 W A / 5 (
T. +OQ$ +OP$ U +$ +>$ -6
6
"
+$
! R R R ! B ( -6
B R
R
R B 0 +O$
( .' "
! R R +$
! ( 6
R ". R +$ (
-
* 9 <- !) & ".
, R #
0 / +$
0 0 . W !
'R ! "
! R
0 6
" ! +P$ +O$
! > 6
" R R (
R → R (
R R R U . +$ -
+R$ " 6
" 6 +P$ +O$
R +$ +$ -
+$ " 6
"
6 +$ +O$
] "( *('# , R R +)# , R → R , R R **'(
R 0! # 1+! ## # ' +R$ ' *(' *( +P$ +O$
( ! ( ()) ! () R # # +$ ## # ' +$
' *(' *( +$ +O$
U # "
+R$ W +$ *
0
0 ! 0 0 +>$
*
0 / +=$
N
+>$ +=$ . "
+$ T
(
+>$ 9
/ 9L MK-
! +$ ( "
R . .' R ( "
+R$
O R
C 6
" ! . *
*
] . - -
" # / ! 6
" ! T
Z-
[ "
+$ -
] > 6# 1+ *(' , R R 1+
4 +)
, R R , R R # ! ( ) R R ## # , +$ '
*(' *( +$ +O$ () # +$ 1
U 0 6
".
! R R
0 ! ! " X 6
" 66
" R W O
*
0 / +5$
T. / 0 (
U O> " ! "
k ( / * 9 <- !) & ".
0 0 +5$ / *
0 0 "
" ! W "
-
+R$ +$ ( -
+O$ +$
+$ +>$ + 6$
W "( *('# R R +)# R R R R **'(
R 0! ! O ( # *('# B R R
# +O$ ! . ! 1+# # R ( ## # '
+O$ +$ 3 ! # 1+ 4#$# - > +P$
0 8 > / +R$
! - R 8 R / + $ 1$ ) 2!)
M +R$ .' .
, .
- > . / 5 8 0 U N . ( R +$ *
( -6 +$ +>$ M (
# +$ +>$ > # "
+$ +>$ ' -
+P$ 0 8 / > +Q$
- 8 R R # .' ( ]
( M
+$ +Q$ +R$ +R$
/ 9L MK-
:
8 T (
$ O W . -6 "
+O$ +$ - 0 ( ( +O$ +$
R
W
! " " R
"
+R$ . ! U . -
. / +O$
+$ ! -
0 ( -6 ( ( + -
$
R 6
" R W "
+R$ . +O$ +$ ! -
W "( *('# R R +)# R R R R )
**'(
R 4 . "( ( / '# +O$
+$ - R 8 R / 1$ ) 2!) "( ' *(
O>= ( ! # ) ( ! 0! ($ (1 , # )! +R$ ' *('
:6
* 9 <- !) & ".
*( +P$ +O$ (1 '
(1 ( , " %
- , " %
+$
0 8 , " %
/ ! = M S> >> (
$
>> C "
+$
- -6 +O$ +$ -.
0 / 5 . - + (- 6 $
! 5 N- R -6
0 "
(
( -6 L "" -6
6
" '
+
%5 O O= > P R&$ * -6
6
" - - - "
+ $
/ -6
+O$ +$ Z
[ X ( +O$
R # ( Z[ ; * +O$ ( .
6
" B R .' B B *.' , *
4 *(' ! R ! B :
/ 9L MK-
. " +R$ ! " 4 >O
4.7.2. Модифицированные функции Лагранжа.
U (
+$ +>$ 6"
.
6
". ]
( + >$,
R R R R R
- 8 0 +$
- 8 " - R 8 R +$
- 8 R R " R ( \ ( 6
R 8 R 8 0 %" 0 %" 0 %" +>$
/ . ! 0 8 0 %" 0 %" +=$
(
*' *(' 2!) +O$ +$,
R R R R
0 - 8 ' R - 8 8 - 8 :*
* 9 <- !) & ".
- " " 0 8 8 +5$
! 6
" 66
" ' 0 +$ - 8 R +P$
! P 1 6
" R R (
R R R R 66
" R . - R 8 R . - 8 -
C-SC
SW
+O$ +$ - 8 *.' . > ] = "( *('# , R R +)# , R R → R , R R **'(
0! # 1+! 1+
4 - R 8 R #
# # ' +P$ ' *(' *( +5$
( ! ( ())
! () R # # +>$ ## # ' +$ ' *(' *(
+$
! R U =
] 5 6# 1+ *(' , R R 1+
4 +)
, R R , R R # !
4 - R 8 R ( ) R R ## # , +$ ' *(' *
( +$ () # +>$ 1 ! Q U 5
T- *'
4 *(' 2!) +O$ +$
\ 0 .'. R - R 8 R / 9L MK-
:
O 0 R "
. +P$ "
6
"
6 +5$ - 8 8 - - 8 0 8 / 1 - O
+R$
(
6 +R$ (
(. ]
( .' *
6"
6
" ]
( +$ +>$ + >$ ( .' 6,
8 8 0 8 / +R$ +=$
T'
>= (
W > "( (# 0! ($ (1 Æ , ,
$ # 1+ - 8 - Æ !
R R - - Æ 8 8 Æ - Æ - 8 R
+P$ ' *(' *( +5$ (1 '(1 ( - 8 - 8 , " % %
- - 8 - , " % %
0 - 8 8 8 % %
/ ,
"
$ ($ ( Æ Æ# # 1+ (+
1$
R 1+
4 - R 8 R # 4 - 8 - Æ
*(
- - - 8 :4
* 9 <- !) & ".
8 0 - 8 8 / +Q$
! #1
- 8 + - 8 - Æ # #
! - 8 $ - -
8 8 - 8 4 - 8 # 4#
! O M = 5 >= >O >
0 (
. $ > (
.' 6 8 8 - 8 . / 5 . - → 0 - 8 8 +Q$ 8 (
( .' . "
4.7.3. Точные штрафы. T
(
- " . -6 -6
/
.' "
6
" -6 (
"6 .
' ( ( -6
O
\ ( 6
" B R R "
( .'
, '. -
+O$
, ? B +>$
& +>O$
, B +
B $ T
6
" B
+5$ ( -
6 ( W = "( *('# R R 2
,'( ; ∈ R ) R ( "( / , +O$ "( ' # *(' B R R (# +>$ +>O$ 4 , ? :
/ 9L MK-
0! # R R 1 ,#
! ! +>$
+! *('# ! *( +P$$ +>$
# 1+! +,! (1$,
$ ? $ && +>>$
"
$ && +>=$
,
"
$ ? ## # ! , +O$ +$ U 0 +>$S+>$ -
+>$ . - B ! ! B
& +>5$
$
U ( - . ". +'
" OO$ M -
+>$ / -
+O$ .
- +>P$
; T3
+>5$ +>P$ &
+>R$
$
0 (
:
* 9 <- !) & ".
*
-
+>5$ +>R$ & & $ +>Q$
"
. - 1(
$ +>Q$ ++>=$ +>>$ +>5$$ k ( ? +>$ +>Q$ . X ( . - C +>5$ ∈ - (
$ 0 +>$ B * +>$ ( 6
" ! ( (' 0
. -6 0 -
+>$ ( (
T # -
+O$ = ( > + ( > O$
* O "( (#4 = / !
, +O$ ( ? 0! ($ ( # )! ## # ! , +R$ '
*(' *( +P$
U ( W '.
R R ! ! /
+=$
/ +=O$
/ +=$ +=O$ (
. $ = T
(
- .' (
6
". B "
+>O$ +$ ( *
(
' T
.'.
/ 9L MK-
:9
N
'.'. O + % 5&$
W 5 "( +)# R R R R
**'(
R 4 "( ! ) +$ ( !(# !7'
0! ( # , , % +=$
! +) % R R R +Q$
W 5 6
" B -
+O$ +>O$ ? = # N ( .
R R k -6 >PO + +OO$ +O$$
k +
-6$ "
+>>$ +>=$ .
$ $ "
"
+ >$ *
= -
. .' -6 Y . O
+ -6
+$ -
+O$ +$ -
" +R$ . - M
" .'
-6 Z
[ -
+R$ -6 N Z
[ -6 . T
(
' .
' (
, +R$ -
+
Z
[ "
$ X (
( ( 0 %5& -6 ( 6
(
:
* 9 <- !) & ".
! -
-6
6
" ! (
. -
+R$ 0 6 +O$ -6 ' . 0 "
+R$ (
U -6 - +
%5&$
/ -
" (. 5 C -6 . " " + 4 => ( -6 %5&$ -
6 ( 6
0 -
-6 (
?
Sl" (
"
.
+=$ 0 "
( , +=$
: (
+ % O &$
! OO (
R R 66
"
( (
R U "
+=$ ( , - : 0 -
6 + $ (
'.
L %& . - -
, . . "
(
::
/ 9L MK-
C 4 !4 , *
4 *('#4
+O$ +$ *
6
" +$ +>$ ! R R R R R
! - 8 - 8 - 8 8 " 0 - 8 "
" - 8
8 +=>$
+ >$ ! - 8 +==$
- 8 R R R R /(
. 6
R - R 8 R R +==$ . 8 8 0 % " " % 0 % " " % 0 % " " % +=5$
/ (
.' -6
6
" +O$ +$,
! R R R R
! - 8 '
! - 8 !
R
8 - 8 " " - 8 - " 0 8 8 8 8 8 0 +=P$
*66
* 9 <- !) & ".
Y +=R$
! - 8 - 8 R R R ! O 6
" R R (
R R R R ( 66
" R "
+O$ +$ . ( ]
( - R 8 R . - 8 "
+=R$ " 6
" 6 +=P$
\
] P "( *('# , R R +)# , R → R , R R )
**'(
R 0! # 1+
4 1+
4 - R 8 R ( - 8) ## # ' +=R$ ' *(
' *( +=P$ ( !
(( ( 8 )) (- 8)) ! ( 8 ) R #
# +=5$ ## # ' +==$
' *(' *( +=>$
! O U P
*.' ' (
$ >5
W P "( (# 0! ($ ( # - 8 !( +
+
+ +
# 1+! +=R$ '
*(' *( +=P$ (1 '(1 ( - 8
! O> M P >5 (
O P
N +$ +>$ -6
6
" +=>$ +
>$ .' -6
6
" +O$ +$ ! 8 W -6
6
" +O$ +$ ' (
СТРАТЕГИИ ГЛОБАЛИЗАЦИИ
СХОДИМОСТИ
?
(- - (
.
+ 4 >O 4 >> >=$ U . . ' *-
6" .
. . M
' .
- " - (
.
(
"
-
+ ( "
$ ( +
3
.' -
. 66
$ /
'
'
Y (
"
+ %> >>&$
§ 5.1. Одномерный поиск
/
(
. " .
+ 4 O >O >O 4 >$ - X 3
.
U -
( " " *6*
* F % '". 3 .' *(' $ 0 6
" (
. (
"
+6
" ( (
$ k " 6
" (
(
+ .' $ "
Y "
- '
.
W ' " .' 6
" k
"
R +O$
6
" R R 6
" ( " 6
" . ". ' = 4 +$
( " 4 R (
= # - Y \
= *
"
R +O$ + $ (
( 4 Z[ -
+OP$ Y = . - 0 ( = . , "
.' - ( - * = Z
[ \ +O$
Y ( 4 ) 4 % % 2 % % R +$
) 7+#" ,
V \OYDC sUM;CDJM
½
/ F+ -) &
*6
) 2 +$ W +OQ$ Æ 2#) '
' = +>$
= = + OO$
*.' '
OO *
" . \
( OO
W O "( *('# R R **'(
R # 2,'( R "( ! ( # 4 "( '
# + ! ' 4 +$ 4 ) 2 0! 1+# # 1+ ! ## # ' +O$ 9 #
($ ( *('# ! ( R ! O M +>$ OO O
0
+$ " 4 '. .
6 - = 06 + 06 .
( $
2 ( 4 . "
(
6" + $
k ( (
. " 4 + $ (
+$ 6
" R 0 (
" V 6
" '
.' T
. + . $ " +
$ 0 %>5& (
Z
[ /.
*64
* F % '". 3 - "
(
" V " 6
" X " -
, .' ( (
/
. 66 ' ( U " 6
" , (
( -
. " 6
" . 0 4 => " " -6
6
" 0 6
" .
6"
6
" ]
( -6
6
"
%>O >& ( %5& "
.
(
-6
6
" 0 "
6
" . +]
( C-SC
SW$ M
"
. 6
" +
-6
6
" -6$ X ( + 4 =>$
' 6
" " " .
" "
.
Φ +=$
Φ R R # (
+ %O&$ 0 6
". (
-
T
6
" - ,
! R R ! Φ W
! Φ Φ R R # 6
" ! " Φ (
# -
+=$ C R " Φ (
.
Φ Φ 6
" ! -
/ F5 <- 1) '
*6
+=$ X OO ! Φ Φ Φ Φ Φ ! .' /.
- ( Z[ (
(
Φ .' -
+=$ ( 6
" ! " ( L § 5.2. Методы доверительной области
U " .
.' (
0
- ( " " + $
N " (
Z [ - ' (
- . + 1 $ / "
R +O$
6
" R R R # ' (
"
.
+$
B R B R R
B 6 +$
6 R # " +
+O$$ M" .' -
B Æ +>$
Æ # U
" # # 66
(
) 7+#" ,
V qYUPC'YOdDJM
½
*6
* F % '". 3 ( *
( .
/ -
.'
T
-
+>$ Y " ( -
' " +>$ Æ ". 6
" - " . ( -
+ ($ 0 . '. 66
"
" 6
" - %=& -
+>$ " ' C +>$ -
" " . 6
*
(
(
. -
-
- " ( 66
M
- " .' ( ( /
" . ' . (
" 6 ( . . "
- k' 66
66
. -
+>$ q
- 66
-
+>$ %O5& ! - (
! O " R $ R Æ R -
+=$
$ Æ
/ F5 <- 1) '
*69
' 8 8 $ 8 Æ " 8 "
k " (
$ $ Æ
8 $ $ Æ
8 8 $# Æ
! 0 O R 8 8 $ " 8 "
U .' (
,
$ Æ 8 -
+=$L
$ Æ -
$ R Æ
$ Æ 8 -
+=$
Y " 8 (
( (
$S$ -
.' R # -
+>$ (
" 6 (
+5$
8 6 8 8 R C O
8 6 Æ + 8 .
" -
+$$ 8 8 Æ
+P$
8 R X -. +(
$
-. "
" /.
%
Æ *6
* F % '". 3 8 -
6 8 R U .' (
* 8 R 8 R . . # .
- 6 Z [ - 8 #8 - 8 Y +5$ +P$ 8 Æ -
+>$ Æ (
. %O5 =& + ( 4 =$
. + U 6 (
.
.
\ O 0 R 0
Æ 7 7 7 7 O 0 Æ Æ
Æ Æ 0 R -
+>$ " 6
" 6 +$
6 k > 0 B +R$
k > 0 Æ "7 7 Æ # > - O
] "
+O$ 0
B +R$$ Z
[ +>$ "
6
" W +R$ " 6
" (
/ F5 <- 1) '
*6:
. + . $ . Z
[
N O L " . /
- +(
$ -
+>$ Æ -
"
W( ( Æ O / - Æ -.' " Z
-
[
'
. " 6
"
- *
( " O ( O "( *('# R R )
**
'( R 0! # ! ! O !
R # + ## # '
+O$ + . (, *( O> +4 ( ! #
! # ( U U ( Æ Æ
-
+>$ Æ Æ +. " 6
" +>$ 6 +$
6 (
I Æ Æ +Q$
+ Æ 0 (
.
', " "
!
Æ B Æ +O$
I Æ Æ + Æ +R$ (
$
*
( 0 % R % % W Æ% Æ B Æ B Æ% Æ % Æ % %
B Æ Æ % Æ Æ %
*6
* F % '". 3 . Æ U
Æ B Æ Æ Æ Æ Æ & Æ +OO$
M -
I Æ +ÆÆ +Æ & Æ
+O$
' % R % % % W
B Æ B Æ% Æ % %
B Æ Æ % %
T. +OO$ I Æ ÆÆ +O$ W O "( *('# R R )
**'( R 0! 1+# # 1+ ! O ## # ' +O$ . *( O> +4 (
! # U 0 (
O (
. R W 0 +R$ B +O$
# ' 0(
,
Æ +O$
Æ +O>$
/ F5 <- 1) '
*
N +O$ (
Æ
Æ R # -
R Æ +O=$
+O5$
W . - >
Æ Æ 0 +>$ B B > +O$ ( -
+O=$ +O5$ + .$ / O O> +O>$ Y '
(
Æ . / . - > Æ Æ - -
Æ ' -
Æ +>$ Æ Æ Æ B Æ +OP$
Æ 7 Æ 0 Æ Æ > U
- (
(
O ( '
% R % % +OR$
+OQ$
% % **
* F % '". 3 W
B Æ B Æ % Æ
Æ % % %
+OR$ . - >
B Æ Æ %
Æ
Æ % T. Æ I + Æ I & Æ #Æ .' I > +$
/ +OP$
0 +OQ$ +$
+ (
O$ .
+OP$ .
', (
" O
' . ". /.
-
)
X - (
'. (
O
! 6
" R R ( 66
"
R "
+O$ O R T +>$ (
. B R Æ / F6 4 & & !
*
+
( $ W ' . + -
4 P$ ' .
N .' " .
U 6
" § 5.3. Продолжение по параметру
k' . - (
' .' M
. "
. (
. +
$ ( -
- (
-
. .' ( X -
+(
$ (
( N
(
' (
' (
W -
(
( - (
-
. 0
"
R +O$
6
" R R (
Φ " # R R Φ R -
R Φ +$
( . . /
(
Φ R R Φ
*4
* F % '". 3 -
(
Φ " " "Φ " " # R 0 (
6 R (
Φ R Φ " " " " # R ! + -
"$ (
Φ . '
U ( ' (
+ " # R " # + Φ " + " " " #
+$
W + "
+O$ (
(
+ R + + U
( -
.
6
" + OO$ \ " Φ (
R (
+ R + ( $ + Φ " + " " T
. ( -
.
" # (
- (
/ (
. %O& + ( O ($ 0 ( ", (
Φ ' -
R R 1 (
A + " 1# R R A + = A 1 0 %> =& 0 Φ " ", Φ " , ", , " " . W ( 5.3.1. Конечные алгоритмы продолжения. U ; " # " " " / F6 4 & & !
"
"
"
- (
" "
*
+>$
R # .' (
-
. +$ * - /.
Φ "
+=$
/ + +$$ * - /.
+=$
/ " ( / ; − 6
+5$
Φ " Φ "
/ ; / ; +P$
. (
"
+ +O$
0 ( / ; ( +=$ - /.
\ O / " # " " " R "
"
"
0 R 6
Φ " Φ " / ; +R$
T (
(
.. (
. - /
!* (
+ " # R (
+ " " #
R + " W O "( +) Φ " # R R R ($ ( +) + " # R *
* F % '". 3 " # ( #1$ +$ "( Φ **'
( + # # Φ + "( '
Φ " + " " " #
+Q$
0! # 1+! ! Æ # - " " " " #
+) R ( #1 (#
Æ
- - +O$
! - +>$ ! O # ( R + Æ
+OO$
U M +Q$ Φ + '
(
" " # ( + , Φ
Φ
" " , " +O$
* '. (
O . : ∈ Æ / ; ( + " Æ 6 +R$ + " : + " +O$
T
+ " + " +O>$
M +>$ 6
" . Æ Æ - +O$ +O=$
Æ
( / ; + " Æ
> / W +O$ +O$S+O=$
+ " + " + " + " / F6 4 & & !
*9
: + " : + " : : Æ :Æ - Æ
:
Æ
: Æ
: + " :
T. N (
(
/.
.
M
'
-
. + " Φ
" " " # 0 (
+Q$,
-
(
(
+ 0 - - " %>&
M
. +O$
6
". ! " # R R . ! R +
$ -
! R ( . . k -
( ' " # (
+ " # R + + "
-
! " R ( " " # (
.
(
! O 6
" ! " # R R .' , ' R 6
" " # . " " # ! " -
+ " U (
+ " # R " #
*
* F % '". 3 k
Φ
( " " # " " + " (
.' (
Φ OO (
+ 66
" +$ " ". (
+
.'. 6 OO$ + -
Φ " , Φ " +O5$
0
+ - . '. (
X N
SC
%=& 0 X .'
+ O$
\ / " # " " " " " " 0 R R 6
= Φ " Φ " " " +OP$
/ ; 5.3.2. Продолжение посредством решения начальной задачи.
W "( +) Φ " # R R R ($ ( +) + " # R " # ( #1$ +$ "( Φ **'
( !* + ! # + "( ($ ( Φ " Φ " + " + " " +OR$
"( ' +Q$
0! # 1+
4 ( ( # (
; Æ " " " " # +) R ( #
1 (#
,
+OQ$
- ; ; Æ
! - +>$ ! # ( R + U .' 6 V
/ F6 4 & & !
*:
] O "( 7 7 7 $ ( #1
7 / ; 7 7 $
0!
7 ( $)
/ ;
! M ". O
U M +Q$ + " # Φ + +OR$ '
(
" " # .', ( + (
Φ " Φ " % R % " (
% + " # R " # % " % " + " + " " +$
0 Æ " + " Æ " " #
+(
" #
T
% " + " % " + "
+O$
M +>$ +OQ$ (
% + " # 6
" Æ +O$
Æ
- ,
)
Æ
Æ - ) Æ +$
. - ;
( / ; + " Æ
> / W +OP$
"
" % " **6
* F % '". 3 " " % " "
" % " " " % " %
"
"
C +O5$ 6 /.
S]
" + "
%
" + " " %
" + " "
M -
+>$ +OQ$ (
+$ +O$ + " %
"
+
"
%
% " % " + " " % " % " + " " + " " Æ
-
+ " O +$ + " Æ - - Æ
T. k O O ' .' 0 ( ( (
. " /
(
X ( .
" U * 6 "
Y (
+ -
-$ %>&
/ F9 <- &1 ( & 2 **
§ 5.4. Глобализация сходимости методов последовательного
квадратичного программирования
+@AB$ .
(
' 6"
. " (- , ' 6
" ! " @AB
' " + %=&$
5.4.1. Глобализация сходимости.
6
" R R (
R R R R R +O$
R +$
R
- 8 - 8 # 6
" ]
( +O$ +$
0 6
" @AB -6
6
" +O$ +$ .' -6 + >P$
+$
! R R ! B B 0 R +>$
R
R
R
0 # (
/ @AB ' ( , " - (
" %5 > P&
0 => 6
". !
***
* F % '". 3 . .' 6" @AB . \ O 0 - 8 R R R . " 6 R l
7 O 0 R "
. +=$
6 R +5$
0 R < R .' "
+=$ +5$ ( ]
(
k = . 0 $
+P$
< = O ! = ! =- +R$
B - +Q$
6
" ! B +$ +>$
k +R$ = 7= O 0 = =
= - 8 < > 1 - . . " 6 R O
N" '
+=$ +5$ "
( 0 - ) 0! + + #!Z " ### " )- "> - R
R
- R ½
/ F9 <- &1 ( & 2 **
@AB (
( +=$ +5$ ( ' ! O (
R R 6
6
6
" 0 66
" R / +$ ( ( +5$
U .' " (
.
0 . ( (
(
6" + ($
U (
" 6
" +=$ +5$ ( ( '
"
( W " .
(
" 6 " 6 (
*
( O ( 6 ( . (
. . " 6 = 0 ( 6 - 8 + >>$ (
" (
! ( 6"
6
"
]
( - -
6 + >R >>O$ 6"
" - 8 + $ C 6
6 .
+(
L 06 $ . (
. 6 ( 6 . 6
" (
/
B 6
" B R . R + >=$ **4
* F % '". 3 5 / 0 # ( +O$ +$ ! (
R R R R 66
" R +>$
6
" B 66
" . . R B % % 0 0 % # (
> H > = H > H = > 5 / 0 ] O "( *('# , R R +)# , R **'(
R "( # ' R / '
# +=$ +5$ R < R / 1$ ) 2!) ( # +P$ "( *(
' ! B +$ +>$ 0! *('# ! **'( 1+( 1 +O$
! ( L ) - 6 B( )
! - +Q$
U . < C-SC
SW +=$ +5$ 6 < +OO$
+O$
< +O$
< 0 0 / +O>$
M +O$ > > H > H > H → R , R R
6 R( ) / / F9 <- &1 ( & 2 **
C +O$
#
0 0 / 5 0 0 / 5 M -
+Q$ ( (
+O$
U ( +OO$ +O$
+O>$ 6 < < 6 6
6 < T. +>$ +P$ +Q$ - +O$
< 0 0 0 6 B
M +O$ ( " 6 (
O O - +O=$
T. +O$ (
.
', * + OO$ " - = + O$ / +R$ - (
. . ! +R$ '
\ 6
" T
6 +Q$ - ' (
! + $ (
0' - O . -6 . **
* F % '". 3 " T
- +O5$
# ! - O (
"
! R 0(
-6 < + +P$$ * (
C < ( 0 +O5$ - (
.'. .
" / - < / (
- +P$
k < Y '
(
%>&
W O "( *('# R R +)# R R R R **'(
R 4 2,'( R "( ! O '
6 +1 # 6 ! 6 % % 2 % % R +OP$
2 ( # - 8 !
. ! # 1+! +,
! +O5$ ! / # 0! +
! +OR$
+
- 8 0 / 8 / F9 <- &1 ( & 2 **9
5 -8 R R R ## # - 8 / '# +=$ +5$ - 8 / 1$ ) 2!)
! +OP$ + >> (
(
" 6 $ * '
' O
U /
< +OO$S+O>$ ( k . < C-SC
SW +=$ +5$ 0. U( = - 0
= # , # ]-" R W
O> / 0 = 0 =0 0 = 0 =0 $ = +OQ$
0 = 0 =0 C 0 =0 =0 = 0 0 = 0 0 = 0 = 0 +O$ / +OQ$ $ = 0 = = 0 U +O$ O> > = = = = $ = = T. +$ +>$ O> ! = = = 0
= **
* F % '". 3 = = ! =- ( = ( $
0 ( = +$
/ +R$ . = = # = , 0 +O$ +OP$
= , ( +$ +O5$ - / ' ' = +O$
= = U +R$ +O5$ +O$ ! ! = -
+$
. - +O=$ 0 ! M (
-
+OR$ k ( +$ - / +O$ ( +OP$ +OO$ - 8 C -
+O$ B +>$ . -
0 / = + $
U +Q$ -
- B + $ +OO$ -
< + $ T. +O$
/ F9 <- &1 ( & 2 **:
-
= < + $
!
+O>$
8 < < - ! 6
" R R (
R → R R R 66
" R 6 R # " R R # "
+$
6 0 0 / +>$
6
" ! +$ B 0 0 R +=$
* / +$ +>$ 6
" ! +$ +=$ (
O $ 2
( %5 >O& '
(
+$ +>$ / ( ( ' +
-$ -6 (
"
+$ +>$ .' ( ]
( T
- ' '.
5.4.2. Восстановление сверхлинейной скорости сходимости. C
O (
@AB ( -
0
, 6" '
@AB ) *
>> -
. - 8 R R R C-SC
SW
+O$ +$ + $ (
( 3 R
R
) 1
, hc] ',
" tQGPCD; EJNO
½
*6
* F % '". 3 " 6 Z[ " - 8 -
+>>Q$ + Z
" [ 6 - 8
Y -
( (
" - 8
( (
$ T
,
(
' - O - Y '
- 8 R R R - 8 - 8 @AB 6
>>)
C (
. "
.' ..' .**
+ $
O R V
-
+O$ +$ ( ]
( - # U R R R # -
]
( +=$ +5$ Z
[ 6 - +5$
+P$
+ +OO$ +O$$ " 6 (
-
+5$ +P$ ( (
. - .' 0
( . . +5$
( .' +P$ / F9 <- &1 ( & 2 *
0 +P$ M ! ! . "
+O$ +$ +
O$ = (
+R$ +O=$ / .
.' "
+O$ +$
! # - -
. 6
" !
( .' .
.' . -
6 ( T
(
6"
Z '[ -6 '
( O R V
-
+O$ +$ (
( ]
( - # (
N . R . = "
+O$ +$ R
R # -
]
( +=$ +5$ 6 - +R$
+Q$
+ +OO$ +O$$ U
( . . +R$ ( .' +Q$ **
* F % '". 3 + +Q$$ M ! ! X66 ? (
3 k ' ( -6 ( ( -
" 6
" 0 - -6
6
" ! - 0 " @AB " '
(
.
" + 4 =O$ 2 ( (
66 ? O 6"
M
66 ?
( . 6" 6
" 6"
6
"
]
( +
' $ # Z "[
(
Y , +$ ( 6
R +$
0 6
"
+O$
! + R R ! + C C R # M .' 6 +
>PO$
( O "( *('# R R +
) R R )
**'(
R "( / '# +O$ +$ *( OP (
!
# ) 2!) - R 0! ($ ( # 1+
4 C R ( #1$4 (
C - +$
## # ! , ! + R ' *(' *( +O$
/ F9 <- &1 ( & 2 *
U 0
6"
6
" ]
( +O$ +$ (
>R . - ! + - " - " +$
. R * ! + - C - - " +>$
+$ T3
+$ +>$ U ' (
R (
R +=$
R # "
+=$ +=$ R # .' (
]
( W 6 +5$
M -
+5$ ( ( O .
C
! + 6 C +P$
C ! + 6 +R$
"
6 (
* W (
O .' . -6
. 6
". ! + 1
+P$ C +Q$
+R$ # +>$
! + = ! + =! + *.' >> .' " 6 6"
. . W "( *('# R R +) R R )
**'(
R 4 . *4
* F % '". 3 "( ( !(# !
/ '# +O$ +$ - R / 1$ ) 2!) "( *( OP ( ! # "( ! R 4 # # 1+! # ' 6 R ( # (1
6 - & +>O$
! ' - ) R R C R ( #1 +5$ +Q$ 0! # 1+! # # Æ # 1+! +,! # +>$
Æ C - Æ
( +>$ = # +O$ *(' ! + 0 . - 6
" ! + 66
" . .
+>$ /
" - (
. - + >R$ 1 +>O$ 6 ' 6
Z"
[ " >>O - U M +>O$ ' 2 . - 6 2 +>$
C .
+>O$ "
" - 6 & +>>$
M +5$ 6 6 / F9 <- &1 ( & 2 *
T. + 6
"$ " & 6 +>=$
" " # \
+5$
+ (
$ " # " # " " # " " & +>5$
*.' +O$ +P$ +R$ +>$S+>5$,
! + ! + 6 C # F & C " - ! + F C - & ! + 6 F Æ 6 F Æ ! + ! + 2 F Æ ! + . - Æ b " C .' . @AB 6
"
. "
*
* F % '". 3 C " ( T 66 ? 4 ! # X . ". (
.' ( -
. -6
/
-
.' M
+
$ -
+>P$
R
+>R$
! > (
R R 66
"
R R -
+>P$ +>R$ +>Q$
! - (
+ $ (
. . . +5$
F F +=$
W +>Q$ "
F F +=O$
+. Z [$ M +=O$ - .
-
& F & - -
g +>R$ +=O$ "
& / F9 <- &1 ( & 2 *9
& & +=$
- -
. - X -
- 6
" ! U .' (
= + = = ' = +
( 7 $ ! = = ! =- +=$
+=>$
R ! k '
* +O$ O +=$ = >> .' . 6" W "( *('# R R +)
R R )
**'(
R 4 . "( ( !(# !
/ '# +O$ +$ - R /
1$ ) 2!) "( *( OP (
! # "( ! R 4 # # 1+! #
' 6 R ( # (1 +>O$ ! ' - ) R R ( #1
+5$ (
+==$
!.
0! # 1+! # 1+! +,
! +=$ # # = # +=>$ *(' ! U C +>O$ '
2 ! R
*
* F % '". 3 . - . -
+>$ +>>$ M +Q$ +5$ +>O$ +>$ +>>$ +>Q$S+=$ +==$ ! ! - - - & - & - & - & - - - & - - - & - " # - & - & - & 6 6
- & / F9 <- &1 ( & 2 *:
6
6
- & & 6 & 2 & . - 0 -
6 " @AB R # ' (
W "
@AB +=$ ( 6
Æ +=5$
+ +5$$ Æ # #
-
W (
6
" -6
6
" 0 +=$ +=5$ -
- Æ T
- + ' . .' . 6
". -
- -
$ - -
6 6
" / ' . - (. " * (
.' +
(
$ .' M 6
" ( @AB
Y +
6 +>$ -6 B ". 6
". (
Y
". (
"., (
. +
.$
p6
6
" - . B - -6 * .
*46
* F % '". 3 +O$ +$ (
R U " B (
6
" "
" " * ( R R $ $ $ $ (
B 6 ,
B . 6 .
6 . 0 - = - Æ N ( - . . / ( " 6, *
.' ". '. ( - B
*
-
N -
. + $ .' . 0 6
6
( '.'
МЕТОДЫ НЕГЛАДКОЙ ВЫПУКЛОЙ
ОПТИМИЗАЦИИ
X (
' "" +(
$ " ' W (
/ ' Z
[ ' . - / (
" $
"
( "
. '
2 ( .
C (
. . -
* 66
T
(
. (
-
. 0 (
-
. ' .
Z. [ +( . '
- $ M
- -
. . ". ' . /- .
.' ( - .
. . -
6" 0 +
$ ) 7+#" ,
V gGdYGMdDGM YOQGTGCDJM
½
*4*
* I <- ) -&!) & ".
" " .' (
( - § 6.1. Элементы выпуклого анализа и двойственные методы
6.1.1. Элементы субдифференциального исчисления. / '
( , ( + $ (
" c " 6
" " 6
" ( /
. 0 . -
-
( -
V
6 6
66
" 6
" U
(
(
-
%O > = = P&
T O R # (
0 R (+! 6
" R
?
( 6
" (+**' X
66
" # (
U 6
". R R
R 66
"
(
6
" + O ($ k 6
" (
**' 66<
" 6
" *
66
" 6
" ( 66
" 6
" " T " 6
" 66
" C 6
" " W O ('# R R ( R
!
! ! ∅ R / I+ , - -&! " )- -
*4
W "( *('# R R ( R 0!,
$ *('# R $ *('# **'( 1+ R 1+
( 1 % R % %
, $ *('# **'( R ! ! ! ! . +4 ## # W "( *(' R R (
R 0! *('# ( R R W > "( *('# R R ( R 0! R ## # , +( '
R W = "( *('# R R ( R R / ! ) 0! *('# , 2,'( 6.1.2. Двойственная релаксация. Y 6
"
+O$
+$
R # ( R # 6
" R R # (
R R R # 6
" ]
( +O$ +$
- 8 -
! R R +O$ +$ ( - 8 +$
-
*44
* I <- ) -&!) & ".
-
- 8 +>$
M ' ' " " +$ 0 ! - 8 - 8 +=$
+5$
- 8 ! - 8 ! R ! - 8 +P$
- 8
! +O$ +$ ( +$ +>$ #
+ -
. +=$ +5$$ W +O$ +$ - . +=$
+5$ W
Z" [ ( 6 ' ! O N $ $ R R R R ∈ R R $ R $ R R R $ - $ 8 - 8 - 8 ! - 8 - 8 ! R R ! N ( R $
( R # (
" R R $ R ( 8 8 ( $ 8 ( 8 R / I+ , - -&! " )- -
*4
-
(
. -
8 ( 8
N - 3 6
C ( ) ( " -
' -
0 . 66
6
" ! ( +Z
'[$ . - 8 ! (
+P$ 0 (
" +P$ ". - ! R R $
→ R R > 1 +6
" (
. +
$
( 6
" ! +5$ +P$ - 8 ! - 8 ! - 8
! - 8 - 8 > 1
0 " +P$ 1 - -
+
$
T . (
" .
+R$
- 8 ! - 8 - 8 *4
* I <- ) -&!) & ".
" 6
" . ( "
" 6
"
. "
+W "
Z
[
"
( $ 0 E
+Q$
E ! - 8
-
# *
-
+Q$ +
, W 5 6# 1+! ) R 1+ *(
' R 1+
4 +) R R
) ! +5$ ( *('# ! # ! +P$ !( (
4( & ! # - 8 # )## ! +P$
! # - - - ! - 8
! > U 5
0 (
5 U
(
- " 6
" U
" 6
" ( Z
[ " 6
" ( M # (
(
+ ( ( . .$ U + $
6
"
- C . ' L ." 6 (
/
" - 8 -
- " +P$ ! - 8 + $ - - ! - 8
N + ( (
-
$
/ I+ , - -&! " )- -
*49
* .' (
0 ' 6
" ! k (
(
+P$ . - 8 " " C " +P$ -
" - -
. (
.' - . 6". # 6
" M ( .' 66
" "
6
" (
E
+ +Q$$ k , E
-
- 8 - - 8
0 +R$ -
+O$ +$
(
- - 8 +O$
- 8 # . -
+=$ +5$
/ (
+O$ +$ # .
. ! +O$ +$ (! !# ( (
66
0 (
/ T
(
( ' +
.$ ' ( +
PO$
/ ( +O$ ( Z-
[ -
.' -
+O$ +$ + -
. +O$ +$$
0 -
(
*4
* I <- ) -&!) & ".
(
T
- .'
6
! = ( R 6
" R
(
R R - 8 ∈ (
+P$ - - -
.' '
+O$ +$,
- - - 0 - 8 0 / 0 - 8 0 - 0 - / 8 - -
+O$ +$
§ 6.2. Субградиентные методы. Кусочно линейная аппроксимация
6.2.1. Субградиентные методы.
"
T R
+O$
6
" R R R /
.' ". - - " "
"
*
(
. $ 5O R
, -
6 6
" (
66
" +
66
" 6
" L 5OO$ C ( - " (
6
" 66
" +
(
$ 5O$ *
" ( 6
/ I5 %!'- - E!( )2 && .2 *4:
! O N 6
". R R . R .' (
, U. . " /
" . ' R * Z
[ (
, R R N - R C -
.
+O$ Y ( -
6 (
" U
( - (
. " # -
/ " . 0 (+! 4 4 (
. + 6
$ " 6
" - M (
'
( 66
" -
(
R R +$
(+**' 6
" R \ O 0 R 0
= R O 0 = +$
1 - O
W O "( *('# R R ( R "( ! O = ( #1
(#
= +>$
*6
* I <- ) -&!) & ".
+=$
0! # 1+ ! O 5 #
(1$ (
= +5$
! R U M +$ +$ R
= = +P$
( W R Æ Æ +R$
M +=$ +5$ = Æ / +P$ +R$
= = Æ Æ= Æ
= +>$ *
O L
(
( -
.' (
U 66
" 0 @ +Q$
@ # - + ' " .$
/ I5 %!'- - E!( )2 && .2 *
W "( *('# R R ( +O$ , "( ! O
= . ! @ ( # (#
@ @ R
+O$
+OO$
0! 1+# # ! O 4 # ,1
+O$
! U $ R . . $ $ < U R # -
+O$ W +P$ +O$ @ T. -
+OO$ (
0 5O=
( / +O$ +OO$
. -
+>$S+5$ O T. 6
$ 5O$ " R + (
.
R .'. -
+O$ !
- (
. * '. " (
+$ +O$
R # (
! R # (
6
" R R R ?6" O
6 +$ 6
= **
* I <- ) -&!) & ".
O 6" O
+O$
C (
. . \
- (
+
$
+
$ -. -
C -
6
(
(- -
?(
( +OO$ - , @ . @ - (
* ' ( ' @ -
X ( ( 66
/
" " (
- T
" +O$
! > 6
" R R R +O$ -
U . +Q$ @ R -
. +O$ k ( +! $ '. ( -
9 +O$ 2 2 9 k (
6". > .'. "
6.2.2. Методы кусочно линейной аппроксимации. Y +O$ R # 6
" R R R C
/ I5 %!'- - E!( )2 && .2 *
'
-
( Y 6" " " " 6
" 0 . -
Y - .'
+ $ ,
R / W - ( ' -
B +O$
+O>$
B R R B ! ( # +O$ +O=$
R / +O5$
M 66
" +O>$ B B R +OP$
6" " +O>$ 6
" # X ( -
+O$ - ( -
+O$
\ 0 R O 0 0 -
+O$ " 6
"
6 +O>$
1 - O
½)
# "$ "
&% "
!# uUMNQO> 3 v#
w v'
w # a "> " > " "
uUMNQO EOCpJNP 7
> # > # ,# "! -
& 8"> '
" a ,&> " LUCCDMd _QGMO EOCpJNP
*4
* I <- ) -&!) & ".
/ (
.
(
U ( (
B - M +OP$ - B B - - # +O$ X " - - (.' . -
" ! + ($
C . ") W
-
Y . .' (
" -
.' + $ 6
"
+O=$ +O5$ M Z-
[ 6" " "
+ 4 5$
U " (
0 2 +O$ " # R
N "6
6
" L - . ' ?(
( " - . - -
+ >$
W "( R / (
*(
'# R R ( R 0! # 1+ ! B *('
B 1 # *( +O>$
U M +OP$ B !
/ I6 <:- - (- &"( *
/ ( Æ B Æ +OR$
( ( / 5O= '
, . - Æ , $
T. +O>$ +OR$ C-SY
Sp" Æ B Æ
, (
W ( ' Æ . - Æ
+OQ$
0
(
Æ /
5O= , ]-" 6
" B + $ T. +O>$ +OP$
+OQ$ Æ B B B
Æ B B ( (
§ 6.3. Многошаговые методы с квадратичными подзадачами
0
"
R +O$
6
" R R R *
* I <- ) -&!) & ".
N 6 " + 5$ .' 6" .' . ". " . " 6
" " "
2 3 . . '
R # ' (
-
. +O$ < R < / # + $
- L < (
W < R ' -
2
+$
B R +$
B R R B < < 2 # W (
"
" - - < "
( . . ". + 5$
M "
" - < -
. 6
" +
,! $ $ k . < 0 "
"
+ ' (
$
. +( ,! $ $ !
6" -
+$ , ' - ". " 6
"
T
(
( . +$ 6
". B (
.' Z"
[ ,
+>$
B ) ) - Z
"[ 6
" < ) < < / +=$
) 7 +#, ,
, hOYDJUP PCO_
) 7 +#, ,
, nUQQ PCO_
½
¾
/ I6 <:- - (- &"( *9
+
"
$ T
B ( ' +$
" , ( / < R ) ) +F < $ N
- Z
"[ +=$ (
"
M +=$ . / +5$
U -
+$ Z[ .
' 6
". B +>$ C ( +$ m
( (
X +
$
(
( *( 6
" B 6
" - Z[ (
B M +>$ 6
(
B +P$
) # ( .
' '. . / +R$
+ +5$$ ' ( ) / .' +R$ ! +P$ +R$ 66
" B R +Q$
6
" B (
"
+ 5OP$
k' , -b (
- C ( (
/ <
/ + ( $ k
. Z[ ' +R$ (
*
* I <- ) -&!) & ".
6" '
" " 6
" 0 6
.
( ( " 6" -
+$
" 6
" +$ $ -
' C +$ " 6
" +P$ 2
+O$
R
) / +OO$
R
* +$ (
X . 6
6
+
(
L P$
Y " +O$ +OO$ -. .'. .'. (
. + O ($,
? 2
? ) ? ? R ? +O$
+O$
! +O$ +O$ -
0- + OOO$ Y . "
. , R 6 ( 66
-
1
-
< +$
] O "( *('# ,R R ( R 6# 4 R ) . ( ) / 2 )
½)
"
! "
&
% ! "
8
'
"
"$ &
% V "
# &
%#
/ I6 <:- - (- &"( ? *:
+O>$
! ? R / ,
+O$ +O$
0! , < +$ # ! +P$ ' *(' < +O=$
2
( )
+O5$
!
+OP$
? ) ! O O +O$ +OO$ 2
? ? ) ? +OR$
( +O$
W ? O (
]
( .' -
. < +O$ +OO$
U O T
< R -
+$ < -
+O$ +OO$ B < *
O ? -
+O$ +OO$ +
-
+O$ +O$ +OR$ +O$ .$ " 5O -
< -
2
? ) R R " l + O$ 2 < ? +O>$ +O=$
U (
$ 5O 5O 5O>
2 < B <
*6
* I <- ) -&!) & ".
+O=$ .
B < +OQ$
T. +Q$ 66
" +$
B B < < R M -
+ 5O$ +O$ +OO$ +OR$ +O$ +O>$ ? ) 2
B < < 2
T. +O=$ B < +O$
2
+OP$
T3
+$ +O$ +O=$ < 2
R
+O5$
T - " 6
".
+$
B R R B R . ( O
+ +O>$ +O=$ +OP$$ X 6
" . -
? R +O$ +O$ *
+O5$ . 66
"
B R +$
B B "
2 (
.' , -
+O$ .' - (
- X
( Z[ ". " 6
" ( -
( .' Z[
T
- * Z[ (
6
" B - B ( / I6 <:- - (- &"( *
B b- Z[
B T .' Z[ (
". Z[ . 6
". B Y " B = . . +Q$ B B < < R +>$
< 1 +>$ - . ) +=$
) < < ( . .'. ) / +
' (
6
" +5$ ) +O5$$ M
" (
. Z[ < ( Z
[ B 0 " ( " ( ( - ( 0 (
' ' < -
< B <
+5$
2 R N ( "
(
. .' (
6
6
-
+O$ +OO$ T
( B ( - -
! .' +>$ ( . ". B Z
[ B L **
* I <- ) -&!) & ".
Z[ < U
R +O=$ +$S+$ B B < < B B < < < B 2
/
" - = < 6
". B (
"
6
". k .' - + +>$$ ". -.
" - m
- " + Z [
"$ 2 (
' (
( - .' - Z
"[ . -
+R$ + ] (
.'.
6 ,
) ) / +P$
6
. !,!! \ O l " , +
$ R ∅ 0 2 R 0
< < ) .'. . '. ) O 0 < -
+$ " 6
" +P$
0 < < 2 < +R$
- B <
k
< - +Q$
< . (
+
-$ 0 +
-$
/ I6 <:- - (- &"( *
> k , k
( , / / = / ) R . O + +O>$ +O=$ +OP$$
= k ) / 6
+P$ 0 ) ) / 0 ) 6 +=$ T . ( ) / 5 1 - O
/ - > / / .' ? . + $ U
" .' (
1
.'
-
< +O$ +OO$ -
< . ( ]
( ? 2 2 + O
($ 0 2 66
6
T
"
"
T
.' 6 .' .
(
, ( 2 2 + L %>&$ ! - 6 2 2 T M +O5$ C-SY
Sp" R " -
M +O=$ +O$ +R$ - +$
2
- + *4
* I <- ) -&!) & ".
2 $ /( - - .' . 0 ( - - .
!
' - -
- (
" 6
" 6
" B -. ". 66
" T
.' . 6, + $ R
R 0 + $ U O -
W O "( *('# R R ( R "( ! O ( # + ) 2 ( # (1
+O$
2
0! # ! O +$
! R # - +$
9 ) +O$ , +>$
2 2 ! 2 4 # ( ,1 +O$
U 0 O +=$
2
2 +$
-
- -
/ I6 <:- - (- &"( k -
T. +$ 2
*
+5$
+P$
*
-
+O$ +=$ +P$ 5O * . + .' "n$ . +$ -
+$ +5$
R # -
+O$ W 2 2
+R$
+ 5P$ M +>$ +P$ 2
2
+R$ (
5 0 # -
+$ -
+O$ !
- (
. (
- O "
- C ( '
( ( . *.' +Q$ + $ +>$ .' k '
"
-
+O$ +Q$
+ $ *
* I <- ) -&!) & ".
- k ( -
+O$ -
W "( *('# R R ( R "( ! O ( # ) #
# ! 2 ! ( # (1
2 2 +Q$
0! / , +O$ < 4 # # # +$
U 0. *
+O=$ +O$ +$ R
B B < 2
2 < < B <
0 B < B < R
2
2
2
B B < < < +>$
M +Q$ < +>$ +Q$ ( +>$ + = < $ 2
B B < < 2
B < < 2 2 < < < B <
+>O$
M (
-
+>O$ B < 2 < # M +>O$
( +>$ +>$ + $ 2
2
B B < < < T. B < 2 < # 2 +
2 L +Q$$ < +>O$ -
< < +>$
/ I6 <:- - (- &"( *9
0 < 5O=
, / ]-" 6
" ( ' +Q$ +>$ < < < < B < < < < < < T. +>$ < B < +>$
< # < < # < < + > $ W +>$ + (
$ 5O$ B < < > +>>$
C +Q$ +O=$ +OQ$ . R B B < < 2 < < +>=$
B <
! +>$ < < + > $ +>=$ < +>>$ < 2 < < R 2 # .' 2 2 < <
+>5$
< -
2
R
+ 5O S 5O>$ 0 2
< < +>P$
* +Q$ +R$ < - 2 < % B < & B <
*
* I <- ) -&!) & ".
< +>>$ &
%
< / . < W +>P$
< < T. +R$ +>$ +$ C +>5$ .
. 5O> -
+O$ U +$ .' .' T' " ( . . (
- " 6
" N
" 6
" +$ ( " T
- +$ ' +>R$
B 6 R 6 R # (
" *( " " " + 4 =>$ N 6 # 6 (
Z3 [
" 6
" +O$ ( ( ( + 6
" $ (
W
(
6
" . .' ' +>R$
M (' (- 6 6 / .' ". 6
". (
. 0 B R Æ / I6 <:- - (- &"( *:
Æ # k U (
0 R ?( ( .' + $ .' T
0 ( - -
0 .' " ?(
6
, -
6 -
.
6 .' + $ 0 " 6 0 -
6 -
" k R # .' X +$ 2
B (
- (
+
+OR$$
0 +>Q$
R +=$
*96
* I <- ) -&!) & ".
R R # (
0 / (
- "
! R +=O$
-6
6
"
! R
R ! 0 -6 U 6
-6 6 0 * (
-6 ' .
-
+=O$ -
+>Q$ +=$ + >PO$ ' " X "
(
- 66
! " '. '
(
-6
6
" (
>
СПЕЦИАЛЬНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ
!.
'
+!] $ +!C $ 0(
. - - 6 ' . -
!] !C 66
66
-. § 7.1. Элементы теории линейного программирования
?(
( " . !] 66
+ . $ M
(
. (
- '
' 6
7.1.1. Общие свойства линейных задач. /
!]
" " 6
" ( !] " ' 0 . -
!] + -
$ . "
+ O$ -
T'. !] +O$
$ $ +$
R R R R ∈ R R $ R $ R R R 0
"
*9*
* L %&.1- "( & ".
0 . .**' '
*(' "
' ! $ $ $ # # 4
! +O$ +$
! O R $ R $ R ∅ W - - *6 !] T. # -2" +O$ +$ W = . !] (
+$
$
+>$
R R $ $ R R !
'. !] +O$ +$ (
3 3 3 3 3 3 3 3 $ 3 3 $ R R R R U ( -
W O 9 ( ) -2" ( . -2" ,
U 0 - ' !] +O$ +$ ( +$ +>$ ( (
$ R T
"$ " " " R R ?"
+ O>$ '
A R R / L+ , - ) & 2
A *9
$ A / A A $ A
A A A ( A U
!] -
( - (
/
-
!] /
O> 6 + O>>L 6
"
$ U
( -
!] + $
W "( R R R ∈ R R R $ R $ R R R 0 ## # , +O$ +$ ! ! ! ( # . - R 8 R - 8 - 8 +=$
8 $ - 8 +5$
! M -
R & !
'. ! W ( ' R & !
*94
* L %&.1- "( & ".
! 6
-
! +
6
"
$
W ( +$ +P$
R $ $ R R / # " C ∈ R 5 / $ ( *.' . -
T O W , +P$ " / 5 . R k -
) - )
M
-
+P$
-
$ $ / 5 T. .' (
6
( O 21+ . + ! ,
W 6# 1+
4 R R $ R
$ R +P$ . (
,( ! ! ! ∅ # '
3 ! # 1
+ ($ ( # , 5 5 U / U . (
5 5 H 5 k " / 5 . R -
. . W % R % % / 5
+R$
k ( % / H % . / H
/ L+ , - ) & 2
*9
% '
% U " ( " "% +R$
" " % $ " " % $ " " " % $ (
/ 5
+Q$
/ H
" "
] ' / H % +O$
" )
+ >O5L
$ / H ( " 5 5 +Q$ .
5 5 +OO$
M +O$ ) % $ / 5 k ( @ @ / 5 +R$
% % @ % (
X " / 5 . R . .
k . -
+OO$ 0 (
. " 0 1 5 5 5 5 R
. . . . . # " / 5 1 m
1
. # -
5 5 *9
* L %&.1- "( & ".
k (
-
+P$ (
.' U ( ( 5 - . $ $ / 5
k -
' ( -
0 .' ( 5
!
+>$ ( !] . +
+>$ R R $ R U R ( H > = > # " " W > 6# 1+
4 R $ R ## # , ! +>$ + R $ ! . ! ! ! > H 9 ) H . , )# . )#
! > U >
0(
- ( .' W = 6# 1+
4 R $ R +>$
+ R $ . (
,( 3 ! # 1+ ($ ( #
, . H H ! = M =
U .' "
-
U ( ( H > H -
. %
$
k -
> H ( > H -
0 ( H
/ L+ , - ) & 2
*99
*.' (
-
!] V " !]
-
-
-
( 1 -
+(
O$ -
-
+
- $ " 6
" L -
W 5 9 -2" , ( ) ( ,( , ( ! ) ## # ,
-2"
7.1.2. Теория двойственности для линейных задач. U
' !] +O$ +$ + R R $ - $ 8 - 8 +O$
- 8 ! - 8 - 8 +O$
! R R + 5OO$ +O$ +$ + !] (
. $ ! !] !] / !] +$ +>$ + R $ - - - R - -2" ( k .. +O$ +$ +O$ +O$ . +$ +>$ + 6
(
" 6
" $ \
6 ' !] \ !] # '#, . /
' , . +( $ " + .' " 6
"$ + 5O5$
W P -2" +O$ +$ +O$ +O$ ,
+O$ +O$ ## # +O$ +$ + 1
+ ' *(' ! $
*9
* L %&.1- "( & ".
! 5 U P
W ( !] , +O$ +O$ (
+O$ +$ /
+ +5OR$ +5OQ$$ $ - $ 8 - 8 +O>$
E
# E = $ - $ 8 # + (
-
. $ T +O>$ - 8 $ - $ 8
+O=$
M +O>$ # -
+O$ +$
- 8 # -
+O$ +O$ -
E
+O5$
] O 9 (#4 ! R R ) +$ +O$ # 4 ( ) (- 8) +O=$ ! ! ! +5$
U M - 8 - 8 - 8 - 8 - $ 8 $ k +O=$ (
. ] (
+5$ T
+5$ (
. +O=$ *
-
+5$ .'
( W -
+O=$
( .' ( +5$ / L+ , - ) & 2
*9:
- 8 2 .
- 8 +=$ 8 T. O .'
!] W R "( (#4 ! R R ) +$ +O$ 0 ## # , +O$ +$ ! ! ! ($ ( - 8 ( #1$#
( +O=$5 ) +5$ " . - 8 ## # , +O$ +O$
k P R ( .' 6 . W Q "## -2" , ! !
! # -2" , " . # E . 4 1 ,
+O5$
W O (#4 R - 8 ##1 # ,# 4 +O$ +$
+O$ +O$ ! ! ! ( #1$ ) +5$
/
" O Q .' '
.' '
-
( W OO 9 ( ) 4 -2" ( + 1 ,# 9 ) ( ( ) , . 4 +
C 5O ( . ' X !] N
- . !] (
-
. -
'. O
! P M -
& R ! *6
* L %&.1- "( & ".
-
'. O
! R W ( R ! Q / -
R ! O . + -2",
$ > 1
R R $ R R > 1 R $ R ! OO . # ,
=
$
R
> 1
R > 1 R R ! O N- $
R $ R $ R ! O N- > R / / / L5 % &8 *
! O> ?
( -
!] (,
$ L
$ L
$ .' ( -
!] (
. ! O= U ( !]
§ 7.2. Симплекс-метод
* +*?$ 6
(
-
!] + 4 P>$ T'
- ( - 6 (
*? !]
+O$
$
+$
R R $ R R N POO .. !] (
0. 6 H > = ( (
R 2 > . "
" 7.2.1. Общая схема симплекс-метода. 0 (
POO PO= PO5 - -
!] -
(
+ ( POO$, +O$ +$ -
-
-
W -
.
!] ( " + P>$
W "
L *?, (
Z
[
**
* L %&.1- "( & ".
" -
.
/
PO> -
+$ " > H ( H # (
-
- (
! . $ % $ ( " " .' (
66"
(
. (
T O 3 ,
+$ . " " ..' " > H M
" > H H -
" # R +
H $ H H m
(
-
" = > H (
-
( / (
-
" $ ( R " " . '
$ . (
-
/
PO= -
T
-
U (
(
. .
' Z-
[ . "
"
-
( " ( .' ,
/ L5 % &8 *
O$ # -
+O$ +$L
$ +O$ +$ -
L
$ ' +
$ -
( " +$
" " +>$
k O$ $ . k -
(
$
+$ k ( -
(
( +>$ " . ". . (
"
+$ ' +Z-[ ' $ -
W *? . ! ((,# L 6
m
( *? (, (
( 5 H -
+ ( +O$ +$$ -
$
% W -
( - +O$ +$ -
-
" - O$
$ M
+O$ +$ - -
-L ( +O$ +$
-
6 ( -
-
. *? ( Z
[ -
( -
M
T
" *? - !] (
*4
* L %&.1- "( & ".
-
( + -
($ " > H # -
H 0 " " " H H " # R " " . ,
2 / +=$
%
2 > H / . .**' $# T ' $#
2 / +5$
- %
! #
> /
- / H 2 > H /
/ H 66"
"
'
. \ - 2 > H / H PO + / H / H W O "( # R $ R #
# # , ! +$ + R $ . " = > H / + . ,
H 0! # 4 ! +=$ +5$ ' $#
- / H +P$
/ , +O$ +$
U N . !] .'.
+O$ +$,
$ - - +R$
+Q$
- R - *
POR . - $ -
+O$
W " # R ' - R .' - > H
+OO$
7.2.2. Итерация симплекс-метода.
*
/ L5 % &8 U - +=$S+P$ , / H - %
-2 %
2 - +OO$ .
- U " # -
H H > H T. +OO$ .
- +O$
-
- $ -
M +P$
-
+R$ +Q$ ( -
+OO$
] O (#4 O # 4 1 H
" (") R "2 > H +O$
(") " > 1
> H > 1
( # (") $
+O$
(") "- +O>$
U 0 +=$ +5$ +O$ " " " %
%
%
"2 " " 2
" %
%
" +O$ +O>$
$
"2 " %
2
"- "- *
* L %&.1- "( & ".
W "( (# O
0! # 4 ! +=$ +5$ .**' '
$# ($ ( 1 H +O=$
- 2 > H +O$ +$ ,#
U M +O>$ +O=$ " . 6 +O$ " " " "- " 0 +O$ -
. ! O U O . W ( '. 1 H > H - 2 +O5$
T' " *? , (
' -
.' -
" 6
" - ' (
+OP$
" "
M +O$ +OR$
" %
1 Y . . H 22 "
+OQ$
0 (
H H . 1
+$
W "( (# O
0! # 4 ! +=$ +5$ .**' '
$# ($ (1 1 H > H +O5$ " # *( +O$
+OR$ ## # , . " > H
! ) H +OQ$ +$ ## # + " . " ) " " "
U M +O$ +OP$ +OQ$ 2 2 "2
2 *
O
/ L5 % &8 +$ , C +=$ %
H H
2 % 2
*9
+O$
2 22 2 +OQ$ 22 +$
2 % 2
T. +$ " # R " # (
R / +O$ PO> -
" # (
+O$ +O>$
+O5$ W " " - " 2 V " 2
Z [ " Z [ C66"
'
22 . ($ . k # (
-
H H > H / +OR$ " " *? +$ Z-[ -
k ( # (
-
(
> H 2 W +O$ +OR$ " -
" - " -
" ( " . 66"
"
'
(
.' " -
T
( " " *? -
' M
/ ( "
/
( (
-
# Z [ " (
-
-
*
* L %&.1- "( & ".
C ". *? (
. . (
"
(
*? (
.
(
-
!] .' " -
' " * " *? "
" Z
[ T
- 3. +O5$
- ' 1 .
1 /
.
>
% 3
% 1 1 + %&$
W " *? / .' "
" -
" U .' 66"
2
"
- '
> H / "
-
.' + +=$$ T
(
( 66"
"
'
" 6 \ +=$ +5$ +$
/ #
2 2 22 $22 > H .
- 2 22 $22 > 1
! 0 6 .' 66"
"
'
" *?
! N- R -
! > M -
R ". *?
! = W ( / L5 % &8 *:
R ( -
! 5 * -
- ( R ( & ' 0
'. *?
! P W ( R -
0 .
-
(
*? M
N . (1 -2"
$
R R $ R R $ X .' !] ,
< $
+$
R R ] < $ -
R -
0 ' ( -
" *? N -
( ! + . *?
Y '
+O$ +$ $ (
0 . !]
+>$
( +$ W - -
< $ * -
- +$ *? T
"
*:6
* L %&.1- "( & ".
6
" +>$ + ( POO +>$ -
*? -
< -
0(
k +>$
(
( +O$ +$ U
( ' < " 6
" +>$
< . / < -
+>$ k ( # -
(
# -
( ? (
" .' -
" -
!] / '. " (
( ]
( .'
-
. " ( ( + # $ 0 !C (
4 P
! R U O -
(
(
(
.
, -
+O$ +$ +P$ # -
- / H .' (
-
(
( § 7.3. Методы решения задач квадратичного программирования
T
!C 3 ( !] , . " -
'
m . (- 4 >> 4 =>
66
"
' ( - " 4 5 X6
6
'
66
-. !C C !] !C -
/( ( / L6 <- :2 "( ( & 2
*:
!C '. ( 66
- + 4 P>$ T -
!C %=&
Y !C +O$
R $
+$
R R ( ( R # (
" R R $ R *"
( '
.. !C (
C ( (
6" "
(
"
( + 6" %>&$
Y ∅ W +O$ +$ -
" 6
" ( 7.3.1. Особые точки.
/ # " o
. ( .
' T O W + +O$ +$ ' ( 5 -
+$
+>$
R $ / 5 + 5 ∅ 5 .. $
W O 6# # ) '
( R 1+
4 R R $ ∈ R +
4 +O$ +$ ,
. ## # + U 2 +$ +>$ ( . ". 6
". -
+-
5 = ∅ X R # -
+O$ +$ T
-
R $ / 5 *:*
* L %&.1- "( & ".
5 / $ # ( / -
-
+$
+>$ 5 5 M -
+O$ +$ " 6
" U +O$ +$ ( (
5 ∅ - +$ +>$ +O$ +$
2 -
+$ +>$ + $ ( " 6
" U (
". ( + (
$ >O$
( R / 5 ( .
". +
%P =&$ ! " 6
" - - (
+ O$
T
-
+O$ +$ - T
(
- POO PO -
!] !C "
, +$ +>$ " ( - (
! O N- R
( ! W ( R
/ L6 <- :2 "( ( & 2
*:
7.3.2. Метод особых точек. +
4 +O$ +$ 6
" ( .' - ' *
O " ( ( -
+O$ +$ -
( W -
.
. +O$ +$ +=$
X o # .. +
.$ R . +5$
+
# -
+O$ +$$ X (
'
/ +O$ +$ - - (
+ 4 >$
* +O$ +$ +>=$
+>5$ '
. . !]
( +P$
R / 5 > +R$
# -
# k " .
! ( R # "
" R R $ R ( +$ +P$ +R$ . # -
+O$ +$
k OO >O (
>O= . +5$ = . = C
= = ( (
= +5$ = -
= = " = #
+Q$
*:4
* L %&.1- "( & ".
+O$
+ >O5L / = M 6
" (
. ( . 6 -
+Q$,
= , " = , / + - $ '
+O$ +$ .' +OO$
U +O$
R .'
( -
+$ +>$ 5 5 W
+O$
0(
k # +O$ +$ . 0 " +O$
, k ( .' (- +O$ +$,
" +O>$
- +O=$
" "
- - +
L +O$$ -
+O$S+O=$ 6
" " " +O5$
U 5 5 C +O=$ / / W / 5 - -- $ = =
/ L6 <- :2 "( ( & 2
*:
/ 5 ( 5 ( - 5 / ( ( 1 " +O$ - U
+O$ +O5$ +OO$ M +5$ +OO$ +=$ M
" . C (
' U . +
'. (- P
$ - 0 " *
5O +O$ +$ ( 8 8 ( $ 8 ( 8 R +OP$
8 # -
-
6
( 8
+OR$
W - . !C +OP$ -
!C +O$ +$ 6
+OR$ ! +OP$ " !C '
'
%P& 0 ( " ( "
(
- * - (
!C " 6
" ! > U ! R ' " 6
" + " $
0 .
+
" L 4 >>$
-
R !C +O$ +$
*:
* L %&.1- "( & ".
.' -
. ( ]
( ?
(
( 8 R
8 ( 8 / 5 W +-
$ (
L P
§ 7.4. Методы внутренней точки
? +?0W$ . - " R - . ( +*?$ "
+ ($ T
(
-
66
*? -
!] - +( C ?0W .
!C 0 6 (
?0WL (
7.4.1. Барьеры. 0 ?0W +
$ " 6
" . . N +O$
+$
( R 6
" R (
→ R 0 / T (
+$
∅ +>$
# +O$ +$
/ L9 <- !) (
*:9
M -6 +O$ +$ . 6
"
. + $ 0 " 6
"
(
\ 6
" B R + +( , *$ +$ ( . 0 / B *.' +
4
*(' +=$
!' R !' B # +
! +O$ +$ !' +5$
/ . !* +
B + +
0 +P$
+R$
(
! +5$ (
6
"
.' m
6
6
"
+ $
- !' . ' "
.' . . (
( 0 -
+O$ +$ ( " -
(
. T- +
\ O U +$ ( 6
B R 0 .'. R O 0 -
+5$ "
6
" 6 +=$ 1 - O
B *:
* L %&.1- "( & ".
( "
W O "( *('# R (
R ( +) R "( # ! +$ ) +>$ ! = 0! # ! ! O B B +Q$
1+# # ## # !+
, +O$ +$
U U +=$ B !' !' B +O$
* +=$ B !' !' B * 6 B B +Q$ / +O$ B B # +Q$
W ( # > M +$ +$ .
k 0 +OO$
Æ W -
+>$ '
Æ .' + +Q$$ + .
-
+>$$
6
" >
Æ
/ L9 <- !) (
*::
( +OO$ Æ Æ
T. .
6 +=$ -
+Q$ . - >
B !' !' B Æ B B (
! O R # ( 6
" R 0 (
R 66
" U ( -
+5$ " 6
" 6 +=$ B +P$ U "
U B +R$ "
( U (
-
+5$ -6 + >$ T
- + $ . +5$ - ( '
' Y (
+ =O$ - +5$ (
-
- -
66
"
*
( '
?0W
(
(
- 4 = -
(
-
. " -
X Z[ (
. 0 . (
"
66
* L %&.1- "( & ".
7.4.2. Некоторые замечания о трудоемкости алгоритмов.
( 1 - (
+" 6 " "$ -
k "
+
6
"$ +
.'$ ( "
- (
" Z
[
T ?0W . . 0
' / *? (
. . "
/
6
N !] .,
+O$
R
$
+O$
R R $ R C "
. +O$ +O$L . 1:
: # ' $ (
"
+"
(
"
-
$ * 1 .',
# - ' . 6
" *
# .' .' (
6
k -
> # +O$
+O$
/
*? -
- C ( ?0W
., . (
. -
Z
[ ( -
Z
"[ T
- (
. -
( / L9 <- !) (
6
'. '(
( # $ . -
F 6
" N " . L ( *? ?0W W "
?0W .
' +O>$
C ?0W . .', (
+O>$ "
1 0 - (
+O>$ " -
.'. -
"
(
N ?0W . "
U " "
F 1 6 " # F 1
0 ( -
(
"
+
R
-
$ PO *? ( -
( -
*'
. " *? "
/ "
(
. + $ +0 ' *? %>&
( "
$
/ - .
66
X (. *'. ?0W .
-
*? 0 (
?0W +
$ 66
' . -
!] - ) 7+#" ,
V ]UYDf;GCDJM _YJ;ONUYO
½
6*
* L %&.1- "( & ".
7.4.3. Прямые методы внутренней точки для линейных задач.
T- ?0W !] +O$ +O$ '
! ( R
$ "
6
"
Y +O$ ( ∅ +O=$
(
T +#(1$ ' (1 1 +oW$ (
+ R .' ( . > -
+5$ !' R R !' +O5$
(
OO= ( 6 (
+O5$ 6
" !' -
+5$ ' oW oW 0 oW . .' ! +5$ " 6
" +O5$ ( -
+5$ -
+ ! oW ' +O$ ( $ ! ( + (
"
( . " 6
" +O$ +O$ + + -
' / L9 <- !) (
6
' + ?(
'
+ ' "
( -
+O$ +O$ X 6 ( O ( (
oW # (
66
(
+ Z[ $ (
+
T- . +#
4$ ( \ 0 U +O=$
( O * - +
.
$ +5$ " 6
" 6 +O5$ 0 1 - O
(
+ - + '. . . . + . .
0' , - . ?0W U (
" / - k ( + + (
-
- + ( -$ + ' " /( 0 ( - -
" + -
. +O$ +O$ \
-
64
* L %&.1- "( & ".
" 0 4 ,! $ # 4 ,! $ /(
(. - .
- "
! " - .
-
C
?0W ( " "
"" + -
. " "
+ - $ -
+ ($ .' " C (
"
# ' (
-
. +5$
/.
- , .' (
R ' -
!' !' +OP$
k +5$ 6
6
"
(
" /.
- + >O$ + .' ( # " + >>O$
0. ) R R R " . 0 (
- R R - ) +OR$
R
R
- ) +OQ$
! R -
+OP$ 6
" !' +O5$ R R $ R R $ ( +O=$ R - R +OR$ +OQ$ ) 7+#" ,
V hpJYC'PCO_ EOCpJNP
) 7+#" ,
V gJMd'PCO_ EOCpJNP
½
¾
/ L9 <- !) (
6
- -
) R # -
+5$
W (
-
+" .
- +5$ C ( ( ( + *.' ?0W + O$ !]
+O$ +O$ * . (
- ?0W ' ( O "( R R $ R = R $ ) +O=$ "( +
)# - #1 # *( +OR$ +OQ$
0! # 4 $ - +$
! U *
+OQ$
" ) - T. ∈ - +O$
W . -
+O$ +O$
- - - $
.
W +$
U C-SY
Sp"
) - ) ) - ) 6
* L %&.1- "( & ".
) - ) - ) $ - .
T3
-
+$ /
+O$ +O$ 0 ( (
O +O$ - # +O$
+O$ $ - - +$
- R - +$
+$ ( . "
$ - . +
POR$
W ( ( .
+5$ .'
-
- ( (#4 )# O # 4 #
+>$
U ( < - # +OQ$ < ) M < > C < ) < < > 0 (
.
+>$
U - -
) R
+ $ - ) - ) < )
0
< < J < < J<
69
/ L9 <- !) (
-
.
< J< ) < < < < < ) +>$ X .
- '
+
$ - - (
( ( W
.'
( (#4 )# O # 4 Æ 1+ 7 # +=$
Æ 5 7 Æ Æ# Æ Æ
U M +OQ$ +>$ +=$ 6
- -
) R
+ $ - ) - ) " ) !
!
) !
Æ 6
* L %&.1- "( & ".
M + ( - .
" + 0 (
"
C ( - - + 6 +=$ (
$ W 6 "
(
. " k'
- . 0(
(
-
Y ' " "
( - ( . " (
+ 6
+OR$ +OQ$$ X . - .' R 6
) 0 .
- -
+5$ +
+ ' -
, * " Z
[ '. " R Z
[
C 6 -
'. 7.4.4. Прямодвойственные методы внутренней точки для линейных задач. 0- . PO +O$ +O$ 6
"
,
- < $
+5$
< < +P$
- < R R R <
. "
M +
$
.' ( +P$ U +P$ < < > 6:
/ L9 <- !) (
# + .$ W +5$ +P$ - < $ J) )
+R$
U
+$ +$ ( $ - - < +Q$
+$
- < R R - < U 6
. !' < - < +O$
+O=$ R $
- < ! < +$
! - < R R - < +$
!' R < R < R
!' < < < +>$
"# # ' # # (
+ ? D R .' ( -
+O$
! R R $ R R $ ( +O=$ (
# +$ +$ -
+O$ " 6
" +>$ .
+R$
! > !] +O$ +O$ + "
"
M" # 4 ( .' 0 ' - < R R R - < ' .
.
+R$ .
. 6
" ! R R R ! < < $
+=$
.'
(
- < < 6
* L %&.1- "( & ".
! < $ - $ - 0 + ! < $ - 0' ( ! < . $ - $ POR . - -
+O$ +O$ ! ( ?0W 6
". ! . - \ 0 U +$
+$ ( - < R R R - < O 0 / R R R .
-
+R$ - < - < - < = / - = # < ! < ! < 0 > 1 - O
C ?0W (. ' " -
0' ?0W (
/( - ! = R - < (
+$ +$ R R $ R / L9 <- !) (
.
-
R
R +R$ - < / R
J J) ) $ J +5$
/ J ) J) J / +O$ +O$
- < / # +Q$ +$
k = - = = ( ( - = < = / (
( = -
.
6
" !
( > "( R R $ R "( R - < ! ) +$
+$ # ! / R R
× R 1 ,! # +R$ - <
0! = #
= $ = $
+P$
! = < = / !
< = < $ = $
! *('# ! +=$
+R$
U /.
- +R$ - < / $ J / ) J) +Q$
M = $ = $ $ = $
+P$
U
= < = / < = / < = / +>$
1
( . . +Q$ ) / < ) ) J) <
C +5$ +Q$ / $ *
* L %&.1- "( & ".
. +>$ = < = / < = < = $ +=$ +P$ ! = < = / = < = / = $ < = < = $
= $
+R$ C +P$ - - = # +O$ +O$ +
= ( $
C +R$ <# '
= . = = -
. 6
" !
= -
( -
?0W . 66
%=&
! 5 N R $ +>O$
6
" R R 0 (
R → R ( 66
" R / R $ R ' T
. "
. . (
+ ? D R R R R .' ( -
- 8 $
+>$
0 8 8 0 / +>$
- 8 R R R U .'
(
,
$ ( -
+>O$ L
$ . +>$ +>$ -
"
L
/ L9 <- !) (
$ +>$ +>$ -
$ - 8 8 -
L
$ - 8 8 -
СПИСОК ЛИТЕРАТУРЫ
N < " % V 8Z > :99
* N!# N$ /# a
k!" "3"
V 8Z `
> ::9
N: %N> H 3 N$ 1# % $ 3#$ V 8Z > ::
4 O" <> M E , 1# '
," V 8Z 8> :*
O3 0%> P 0> E'1 *< x" " V
8Z > :9
O Q /# %# " 3 2,'
3 V 8Z y #!> :9
9 $1 R 2
% -# a
!"$ V
8Z =' 8/> :94
$1 R 8" % V 8Z `
> *66*
: $1 R 8" -# a
!"$ V 8Z >
:
6 $1 R x" " -# a
!"$ V
8Z > :
$1 R> J.) NS 2 , V
8Z `
> ::
* $ $$> E!". SN 8%" "# V 8Z '
> :4
* R> <#) T> U) < # %# V 8Z
8> :
4 *1:) V*> H12 0$ 8&%" &
%
2,3 V 8Z > ::
* E> E& NN , % V Z > :
QW Q4> M'1 U x" " '
% -# "$ V 8Z 8> :
9 V!: S* 8" -# a
!"$ $ '
$ % V 8Z > :*
P2) NN> P N* 8" ,!, a
'
V 8Z > ::
%& !-
: 7 TJ , V 8Z >
:9
*6 J" NR x!! % V 8Z `>
*66
* J" NR> H12 NN `
"$ '
3 V 8Z > ::4
** J" NR> H12 NN ',#" -# '
"$ 1# " " V 8Z `> :::
* J1 $N> %() $N> % OX 8
'
V 8Z > :9:
*4 E $* 8
, V 8Z `'
> *666
* E R 7%# ,
V 8Z > :
* = V% 1# + ,'
3# V 8Z > ::*
*9 <! < 8
, 1# ,'
" V 8Z > ::6
* <3( $%> *!& N<> 0 $J 8" "
% V 8Z > :9
*: < 00> J S> %2 V< 8" '
% V 8Z > :9
6 0! ) VN x" " "
% V 8Z
> ::
Q4> U)' $ =%" " -# '
"$ , " V 8Z 8>
:9
* , x" " % z" $ V 8Z
8> :94
2 OH % V 8Z > :
4 :(-) O0> Q S< x" " a
!'
"$ $ V 8Z > :9
UK U "
" V 8Z 8> :9
% U* x" " ,a
!"$ '
$ V 8Z > :9
9 %!3 N*> H 3 N$> R $$ . '
% V 8Z > :
R N> <8E * , 8"
! % V 8Z 8> :9*
: X 1'! Q , V 8Z
8> :9
46 YZ@B [>> \@BY ] nUEOYD;GQ ;JMCDMUGCDJM EOCpJNP ^M DMCYJNU;'
CDJM V uOYQDM> rODNOQ{OYdZ h_YDMdOY'KOYQGd> ::6
4 ^@B_A@`A ab nJMQDMOGY _YJdYGEEDMd V hO;JMN tNDCDJM V uOQEJMCZ
^CpOMG> :::
%& !-
4* ^???A c> \d@B_ ceD> >@Bf@CD e> YA_
fd e nUEOYD'
;GQ J_CDEDFGCDJM qpOJYOCD;GQ GMN _YG;CD;GQ GP_O;CP V uOYQDMZ h_YDMdOY'
KOYQGd> *66
4 ^BYZB_ ]g qpO PDE_QOT EOCpJNP ^ _YJ{G{DQDPCD; GMGQ|PDP V
uOYQDM> rODNOQ{OYdZ h_YDMdOY'KOYQGd> :9
44 e?? h> \i j> k?_ bD> qYUPC'YOdDJM EOCpJNP V
]pDQGNOQ_pDGZ h[^\> *666
4 e__@ hl> b?Y c8> _?@ h[ qpO QDMOGY ;JE_QDEOMCGYDC| _YJ{'
QOE V nOo }JY~Z ^;GNOED; ]YOPP> ::*
4 @_CD@B h ]YG;CD;GQ EOCpJNP Js J_CDEDFGCDJM K M;JMPCYGDMON J_'
CDEDFGCDJM V LpD;pOPCOY> nOo }JY~> uYDP{GMO> qJYJMCJZ XJpM €DQO|>
:6
49 @_CD@B h ]YG;CD;GQ EOCpJNP Js J_CDEDFGCDJM K * LJMPCYGDMON J_'
CDEDFGCDJM V LpD;pOPCOY> nOo }JY~> uYDP{GMO> qJYJMCJZ XJpM €DQO|>
:
4 ?YAB? m> nJMQDMOGY ]YJdYGEEDMd V ]pDQGNOQ_pDGZ h[^\>
::4
4: Bf@ cc> lBYD_ c B_CDEDFGCDJM PJsCoGYO dUDNO V ]pDQGNOQ_pDGZ
h[^\> ::
6 jC@ c> lBYD_ c nUEOYD;GQ J_CDEDFGCDJM V nOo }JY~> uOYQDM>
rODNOQ{OYdZ h_YDMdOY'KOYQGd> *666
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
/ '&&%> :
0 '> 4
'&&%> *4:
А,
"> 9
Б -" a> **
A!> *:9
V ,&
> *:9
V "> *:9
В
!"> **
V a&&% % &
'
%> *9*
V "$ ,>
*9*
- a> *94
V V "3#> *94
V V "3#> *94
"
> *
Г&
3#> *
Д&&%
З
.
> :
'
%> V "
, ,#>
*49
V , ,'
#> 9
V , ,#>
9
V V V #> *6
V V V #> *9*
V V V # >
*99
V V V #> *:
З
, '
,#> V %> V V "
#> V V #> *44
V V ##> *44
V # #> *6
V %> V a
!#> 0%
'>
*9
0 %> И%#
> К>
*6
V !"> **
V ," (A,)> **
V (
$ '
)> 4
V "> *
.a&&% +#> *4
М% ,> *9*
8 , 3> 94
V A5`5'
&5?a> :9
V !> *:9
V -,"> V > 6
V V V #"> 6:
V V V " -,> 64
V V V -,> 64
V 3"$ > :
V ,"> 9*
V V > " ,>
6
-) !"1
8 ,"> $'
" '
,> 6
V @5`5 a>
:
V $> 6
V ! > *6
V 0
> **
V , #> *
V , > *:
V , -&> *9>
*
V !
> :*
V -," (
")>
V '
%> *
V ,-," "'
> **
V &%"$ &
%
2,3> > :*
V !> 9
V !> > :> *4
V V "> 9
V V +"> V V +"> *
V V "> V V "> V "$ > *:
V "> V '
> V , > 69
V !, '
, ,#> 44>
4
V V -# > *
V !"> V '
> **6
V % ,> 6:
V V V &%"> 4
V #, > 6
V -, > 9
V , > 6
V V , > 6
V #3"$ ,> 6*
V V > ::
V > > V ,"> *4:
8 , ,> 9
V $> V -&> 83 "
> 9
V > V "$ ,'
> 4
83! 2,3> *> 4
Н 3> V "#> 4
$ !'
#> *
V V V #> *
" "> ***
О! !#> *6
7, > 46
V #> V &
%!> 7%# #> *99
7
> *4
73 / '&&%'
> V ^a ',#> V ea ',#> V &&> 9
V ,> :
V &&% '
> V " 2-%> V ,
> V !> *4
V ! ,
> 7%
+#> *4
П> 9
!"> *:9
V " -,> V !"> *
V -&> *9
V -&> # #> *
V ##> *
,-! > "> a> 9
V > *9
, #
> *
-) !"1
#
> !! '
#> *6
V V +#> *
k$> 9> 6
V Aa> *
V &> 96
V > :
V %> >
6
V #, > :> 6
3 -> % 2,3> V `> *
%#> *6
# >
% #> 6
Р > 66
y! # >
6
V V %!#> 6
y" > *49
y
%# #> *44
y- ,!> V &%> 4
V !> V ,> С > '> **
'#3#>
::
V .-5.51
> 44
V 2,3> ! $> V V &
#> 4
V V ,
#> 4
V V #> V V #> V V $#> V V #> - >
*49
V V > *4
,> *4*
&&%> *4*
&&%> *4*
:
$ %#> V V ,-,#> V V -,#> $!> *
V ,!#> *
V 3 -> *
V !#> *
V ,> *
V ,> *
V &
%> *
Т -> V @a58a> :*
V .-5.51
> 4*
V 2
> V 8%
> :
V > *9:
V # &
%> *
V V + "3'
%"> V V > 6
V V + #
&
%> *
V %
##> 6> 4>
:9
V y$> :
V y> :9
V ` @3> 4
1
#> V # (!-# !-#)>
V #> *
V # ,
,#> *:
V %#> *> *> *> 4
V a
!#> 1
# > V %!#> 6*
V V ##> 6:
1
! > 66
V V !#> 66
V V a
%!#> 66
У !
>
:
/ ,
.> V V V !> V #+ 3
> 4
V , > 9> 6
*6
-) !"1
/ ,#> 9*
V > 4>
4
V > 4
V " (, )> **
V $ '
$ #> *
V ,#> V V 8,5`%>
4
V V V ,> 4
V V ,> 4
V > *49
V , !> 49
Ф % !#> *46
V V !#> *46
`!> *46
`
%# !#> *:9
V +# (
a%'
#)> *6
V ,#> V "
#> V !> 9
V #
> 9
V > *6*
V #> 9
V "
#> :
V 2,3> > 4*
V "# 2-%> `
%# 2,3 &%'
#> 4> :
V V +#> 4
V %+# #> 9
V "# > :
V !#> *4
V ! "
#> V , "
#> :
V , "
#> 6
V !#> :
V `-5A> 9
V %#> V -&#> *9> > :6
V V #> *
V V V ,
#> > ::
Ц > 6*
Ш, > V V > *
V V !"> *
?&> 6> :6
V > *:9
V "> *9> *
V > *
V "> *> :9
Э
> < +> *9
<&&
8> *6
Документ
Категория
Математика
Просмотров
6
Размер файла
2 148 Кб
Теги
723
1/--страниц
Пожаловаться на содержимое документа