ĐẠI HỌC SƯ PHẠM TP.HCM
LỚP TOÁN VB2-K2












TỔNG HỢP BÀI TIỂU LUẬN
TỐI ƯU PHI TUYẾN







Năm học 2014


TRƢỜNG ĐẠI HỌC SƢ PHẠM
THÀNH PHỐ HỒ CHÍ MINH
















































MÔN: QUY HOẠCH PHI TUYẾN


ĐỀ TÀI:

CƠ SỞ LÝ LUẬN CỦA HÀM LỒI – HÀM LÕM






HVTH: 1. Trịnh Cẩm Vân
2. Nguyễn Thị Bích Hồng

3. Ngô Thị Duy Bình

Lớp Toán -Văn bằng 2- khóa 2



1
Chƣơng 4: HÀM LỒI VÀ HÀM LÕM
I. Định nghĩa
1) Định nghĩa hàm lồi
Một hàm số

xác định trên tập
n
R
được gọi là lồi tại
x 
nếu
 
       
0 1 1 1
1
x
x x x x
xx
      





       




  



được gọi là lồi trên

nếu nó lồi tại mọi
x
.
Trường hợp đặc biệt: nếu

là tập lồi,
n
R
thì ta có mệnh đề sau:
Mệnh đề 1:
Một hàm số

xác định trên tập lồi

gọi là lồi trên

nếu và chỉ nếu
 
   

 
12
1 2 1 2
,
11
01
xx
x x x x
     




     





Ví dụ:
 
2
xx


là hàm lồi trên R.



Hàm lồi


trên R Hàm lồi

trên
 
1,   

Hình 4.1: Hàm lồi trên các tập con của
n
RR



2
2) Định nghĩa hàm lõm
Một hàm số

xác định trên tập
n
R
được gọi là lõm tại
x 
nếu
 
       
0 1 1 1
1
x
x x x x
xx

      




       




  



được gọi là lõm trên

nếu nó lõm tại mọi
x
.
Trường hợp đặc biệt: nếu

là tập lồi,
n
R
thì ta có mệnh đề sau:
Mệnh đề 2:
Một hàm số

xác định trên tập lồi


gọi là lõm trên

nếu và chỉ nếu
 
   
 
12
1 2 1 2
,
11
01
xx
x x x x
     




     





Ví dụ:
 
2
xx



là hàm lõm trên R.
Chú ý:


lõm tại
x 
(lõm trên Γ) khi và chỉ khi


lồi tại
x 
(lồi trên Γ).

Hàm lõm

trên R Hàm lõm

trên
 
0,1

Hình 4.2: Hàm lõm trên các tập con của
RR
n

.

3) Bài toán 1: Chứng minh rằng:
 
,

n
x cx x R

  
là hàm tuyến tính

 
x

vừa lồi vừa lõm trên
n
R
.
Chứng minh:
 

Vì
 
x

là hàm tuyến tính nên
12
,
n
x x R
;
 
0,1



và
 
12
1
n
x x R

  
ta có:

3
   
   
1 2 1 2
11f x x f x f x
   

    


   
   
   
   
1 2 1 2
1 2 1 2
11
11
f x x f x f x
f x x f x f x

   
   


    





    




Vậy
 
x

vừa lồi vừa lõm trên
n
R
.
 

Vì
 
x

là hàm lồi trên

n
R
nên
 
   
   
12
1 2 1 2
,
1 1 1
01
n
x x R
x x x x
     




     





Vì
 
x

là hàm lõm trên

n
R
nên
 
   
   
12
1 2 1 2
,
1 1 2
01
n
x x R
x x x x
     




     





Từ (1) và (2) suy ra
   
   
1 2 1 2
11f x x f x f x

   

    


Vậy
 
x

là hàm tuyến tính.
4) Định nghĩa hàm lồi ngặt
Một hàm số

xác định trên tập
n
R
được gọi là lồi ngặt tại
x 
(với
x
tùy ý trên

)
nếu
 
       
11
01
1
x

xx
x x x x
xx
     







     






  



được gọi là lồi ngặt trên

nếu nó lồi ngặt tại mọi
x
.
Ví dụ: hàm

trên hình 4.1b) là hàm lồi ngặt.

5) Định nghĩa hàm lõm ngặt
Một hàm số

xác định trên tập
n
R
được gọi là lõm ngặt tại
x 
(với
x
tùy ý trên

)
nếu
 
       
11
01
1
x
xx
x x x x
xx
     








     






  



4

được gọi là lõm ngặt trên

nếu nó lõm ngặt tại mọi
x
.
Ví dụ: hàm

trên hình 4.2 a), 4.2 b) là hàm lõm ngặt.
Chú ý:
- Nếu một hàm lồi ngặt (lõm ngặt) trên tập
n
R
thì hàm đó lồi (lõm) trên Γ, chiều ngược
lại thì không.
Ví dụ: một hàm hằng trên
n

R
đều lồi và lõm trên
n
R
, nhưng nó không lồi ngặt và lõm ngặt
trên
n
R
. Thật vậy, dễ dàng thấy tất cả những hàm tuyến tính
 
x cx


trên
n
R
thì không
lồi ngặt và lõm ngặt trên
n
R
.
- Một hàm véctơ n chiều ƒ xác định trên tập Γ trong
n
R
gọi là lồi tại
x 
, lồi trên Γ, nếu
mỗi hàm thành phần
, 1, ,
i

f i m
lồi tại
x 
, lồi trên Γ.
II. Các tính chất cơ bản
1) Định lý 1 (Các phép toán với các hàm lồi)
Cho U là một tập lồi trong không gian
n
R
. Khi đó
1. Nếu f và g là các hàm lồi trên U thì f + g cũng là hàm lồi trên U . Nếu f hoặc g là hàm
lồi ngặt thì tổng f + g cũng là hàm lồi ngặt.
2. Nếu f là hàm lồi (lồi ngặt) trên U và µ là một số thực dương thì µf là một hàm lồi (lồi
ngặt) trên U .
3. Nếu f là một hàm lồi (lồi ngặt) trên U và V là tập con lồi của U . Khi đó hạn chế f |V của
hàm f lên V cũng là một hàm lồi (lồi ngặt) trên V .
2) Định lý 2
Cho
 
1
,,
m
f f f
là hàm véc tơ m chiều xác định trên
n
R
. Nếu ƒ lồi tại
x 
(lồi
trên Γ) thì mỗi một tổ hợp tuyến tính không âm của các hàm thành phần

i
f

   
,0x pf x p


là hàm lồi tại
x
(lồi trên Γ).
Chứng minh:
Lấy
10, 

x
, và
 xx

)1(
. Ta có :
   
xxpfxx

 )1()1(


 
)()()1( xfxfp



(do f lồi tại
x
và
0p
)

5

)()()1(
)()()1(
xx
xpfxpf





Vậy
 
x

là hàm lồi tại
x
(lồi trên Γ).
3) Bài toán 2
Cho

là một hàm số xác định trên tập lồi
n
R

. Chứng minh rằng

lồi, lõm, lồi ngặt,
hoặc lõm ngặt trên Γ nếu và chỉ nếu với mọi
12
,xx
, hàm số

xác định trên đoạn thẳng
 
0,1
là
   
1
2
1 xx
    

  

lồi, lõm, lồi ngặt, hoặc lõm ngặt trên
 
0,1
.
4) Định lý 3
Cho một hàm số

xác định trên một tập lồi
n
R

, điều kiện cần và đủ để

lồi trên

là
tập trên đồ thị của

:
 
 
1
, / , , ( )
n
G x x R x R

   

    
là tập lồi trên
1n
R
.
Chứng minh:
(Điều kiện đủ)
Giả sử

G
lồi.
Lấy


21
,xx

11
[ , ( )]x x G



và
22
[ , ( )]x x G




Vì

G
lồi nên
1 2 1 2
[(1 ) ,(1 ) ( ) ( )]x x x x G

    
    
(
10 

)
Hay
1 2 1 2

[(1 ) ] (1 ) ( ) ( )x x x x
     
    
(
10 

)
Vậy

là hàm lồi trên


(Điều kiện cần)
Giả sử

lồi trên

.
Lấy
11
,xG



và
22
,xG




.
Vì

lồi trên

nên
1 2 1 2
[(1 ) ] (1 ) ( ) ( )x x x x
     
    
(
10 

)

12
(1 )
  
  

1 2 1 2
(1 ) ,(1 )x x G

    

     


Vậy
G


là tập lồi trên
1n
R
. (đpcm)
5) Hệ quả 1
Cho một hàm số

xác định trên tập lồi
n
R
, điều kiện cần và đủ để

lồi trên

là tập
dưới đồ thị của

:
 
 
1
, / , , ( )
n
H x x R x R

   

    
là tập lồi trên

1n
R
.

6

Hình 4.3: a) Tập trên đồ thị của hàm lồi

là tập lồi
G


b) Tập dưới đồ thị của hàm lõm

là tập lồi
H



6) Định lý 4
Cho

là hàm số xác định trên tập lồi
n
R
. Điều kiện cần để

lồi trên

là tập

 
/ , ( )
n
x x x R


      
lồi với mọi số thực

.
Chứng minh:
Cho

lồi trên

.
Lấy
 
12
, ; 0,1xx


 
ta có:
1 2 1 2
[(1 ) ] (1 ) ( ) ( )x x x x
     
    
(
10 


)

(1 )
  

  


12
(1 )xx


   

Vậy


là tập lồi.
Tiếp theo ta chứng minh


lồi với mọi số thực

.
Xét hàm

trên R :
 
3

xx




không lồi trên R.
Tập
 
 
1
3
3
/ , / ,x x x x x x


      
là tập lồi với mọi

(hiển nhiên)
7) Hệ quả 2

7
Cho

là hàm số xác định trên tập lồi
n
R
. Điều kiện cần để

lõm trên


là tập
 
/ , ( )
n
x x x R


      
lồi với mọi số thực

.
Hình 4.4: a) Hàm lồi

liên kết tập lồi


.
b) Hàm không lồi

liên kết tập lồi


.
c) Hàm lõm

liên kết tập lồi


.

8) Bài toán 3
Cho

là hàm số xác định trên tập lồi
n
R
. Chứng minh rằng: điều kiện cần và đủ để


lồi trên

là với mọi số nguyên
1m 
,
     
1
1 1 1
11
1
, ,
, , 0 (*)
1
m
m m m
mm
m
xx
p p p x p x p x p x
pp
  




      


  


Chứng minh:
(Điều kiện cần) Chứng minh qui nạp theo k
+
2k 
ta có bất đẳng thức đúng sau:
     
2
12
1 2 1 2
1 2 1 2 1 2
1
,
,0
1
xx
p p p x p x p x p x
pp
  




    





+ Giả sử bất đẳng thức (*) đúng với
1km
nghĩa là ta có bất thức đúng sau:
     
11
1 1 1 1
1 1 1 1 1 1
11
, ,
, , 0
1
m
mm
m m m
m
xx
p p p x p x p x p x
pp
  


  





      


  



8
+Chứng minh bất đẳng thức (*) đúng với
km
. Đặt
,
1
i
i
m
p
p
p



   
 
   
 
11
,,

1 1 1
11
m m m
i m i m i
i m m i m m i
i i i
p x p x p p x p x p p x
    

  

     


  


 
1
,
11
1
mm
m i i
m m i i
ii
p x p p x p x




   
   


   

(đpcm)
(Điều kiện đủ) Hiển nhiên
Bất đẳng thức (*) ở trên gọi là bất đẳng thức Jensen.
9) Định lý 5
Nếu
 
i
iI


là một họ các hàm số (hữu hạn hoặc vô hạn) lồi và bị chặn trên trên tập lồi
n
R
thì hàm số
 
sup ( )
i
iI
xx



là một hàm lồi trên


.
Chứng minh:
Vì mỗi
i

là hàm lồi trên

nên tập trên đồ thị của mỗi
i


})(,,/),{(


 xRxxG
i
i
là các tập lồi trên
1n
R

(định lý 2)
{( , )/ , , ( ) , }
i
i
iI
G x x R x i I

   


      


{( , )/ , , ( ) }x x R x
   
   
cũng là một tập lồi trên
1n
R

.
Mà giao của các tập lồi này là tập trên đồ thị của

.
Vậy


là một hàm lồi trên

(định lý 2). (đpcm)
10) Hệ quả 3
Nếu
 
i
iI


là một họ các hàm số (hữu hạn hoặc vô hạn) lõm và bị chặn dưới trên tập lồi
n
R

thì hàm số
 
inf ( )
i
iI
xx



là một hàm lõm trên

.
Chú ý:
- Hàm

là lồi trên tập lồi
n
R
thì không nhất thiết là hàm liên tục.
Ví dụ: trên nữa đoạn thẳng
}1,/{  xRxx
, hàm số
2
2, 1
()
( ) , 1
x
x
xx









là một hàm lồi trên

( tập trên đồ thị của

là tập lồi trên

), nhưng không liên tục tại
1x 
(
   
1
lim 1
x
x



) (hình 4.1b).
- Tuy nhiên, nếu

là một tập lồi mở, thì hàm lồi

trên


liên tục.


9
11) Định lý 6
Cho

là một tập lồi mở trên
n
R
. Nếu

là một hàm lồi trên

thì

liên tục trên

.
Chứng minh :
+ Lấy
0
x 
và

là khoảng cách (xem 1.3.9) từ
0
x
đến điểm gần nhất trên

n
R
không trên



 
nếu

n
R
. Cho
C
là hình lập phương n chiều với tâm
0
x
và chiều dài cạnh
2

, nghĩa là:
 
0
1
{ , , : , 1, , }
n
n i i
C x x R x x i n

      


Với
 
0 0 0 0 0
0 1 2
1
, , , ,
n
n i i
i
x x x x x x



   



Cho
 
1/2
n



C  
.
Cho
V
là tập các đỉnh
2

n
của
C
và
max ( )
xV
x




Theo định lý 3 ta có:
 
/ , ( )x x x


   
là tập lồi.
Vì
C
là bao lồi của
V
(điều này thì dễ dàng chứng minh bằng phép quy nạp trên
n
) và

V
nên

C

(định lý 3.1.13) (hình 4.5).
Cho
x
là điểm bất kỳ thỏa


0
0 xx
, xác định x° + u, x° — u trên đường thẳng qua
0
x
và
x
như hình 4.5.

Khi đó
x
là tổ hợp lồi của
0
x
và
0
xu
;
0
x
là tổ hợp lồi của
x
và
0

xu
.
Nếu

/
0
xx
thì
)(
11
1
)(
)1()(
0
00
00
uxx
xuxxuxx
xuxuxx















10
Vậy

lồi trên


 
 
 
 
 
0 0 0
1 1 ( )x x u x x
      
      

 
 
 
 
00
1
1 1 1
x
x x x u
 


  
  

   
  


 
 
0 0 0
( ) ( )x x x x
       
   
      
   


 
 
 
0
00
x
x x x x




   


Vậy
0



 
 
0
xx
  
  
với mọi x thỏa
 
00
x x x
  

  

và do đó
 
x


liên tục tại
0
x
. (đpcm).
Từ đó phần trong của mỗi tập
n

R
là tập mở, nếu

là một hàm lồi trên một tập lồi
n
R
thì
nó liên tục trên phần trong của tập lồi.
12) Định nghĩa: Một hàm f : [a, b] → R được gọi là hàm lồi theo nghĩa Jensen hay J-lồi trên
[a, b] nếu bất đẳng thức
( ) ( )
22
x y f x f y
f






thỏa với mọi điểm
 
,,x y a b

13) Định lý 7 (J.L.W.V.Jensen): Cho I là một khoảng của tập số thực và f : I → R là một
hàm liên tục. Khi đó f là hàm lồi nếu và chỉ nếu f thỏa mãn
( ) ( )
(**)
22
x y f x f y

f





với mọi
,x y I

Chứng minh:
)
Hiển nhiên
)
Giả sử ta có (**). Nếu f không phải là hàm lồi trên I thì tồn tại một đoạn [a; b] ⊂ I để
đồ thị của hàm f |[a;b] không nằm dưới dây cung nối (a, f (a)) và (b, f (b)). Dây cung nối (a,
f (a)) và (b, f (b)) là


11

 
( ) ( )
()
f b f a
x a f a
ba





Khi đó hàm
     
 
( ) ( )
( ) , ,
f b f a
x f x x a f a x a b
ba


    


Với
 
 
 
sup / , 0x x a b

  

Ta có

cũng là hàm J-lồi. Thật vậy, do f là hàm J-lồi nên ta có
 
( ) ( )
()
2 2 2
x y x y f b f a x y
f a f a

ba

   
   
   
   

   


   
( ) ( ) ( ) ( ) ( ) ( )
2 2 2 2 2 2
f a f a
f x f b f a x a f y f b f a y a
b a b a
   
   
     
   

   


( ) ( )
22
xy




Do f (x) liên tục trên [a; b] nên ta có
()x

liên tục trên [a; b] và do đó tồn tại x ∈ [a; b]
để
()x


.
Đặt c = inf{x ∈ [a; b] |

(x) = γ }. Ta suy ta
()c


và c ∈ (a; b) vì
( ) ( ) 0ab


.
Khi đó với h > 0 sao cho c ± h ∈ (a; b) ta có
( ) ( )c h c


và
( ) ( )c h c



Hay

 
()
()
2
c h c h
c


  


mâu thuẫn với

là J-lồi.
Định lý được chứng minh.
14) Hệ quả 4: Cho f : I → R là một hàm liên tục. Khi đó f lồi nếu và chỉ nếu
f (x + h) + f (x − h) − 2f (x) ≥ 0 với mọi x ∈ I và với mọi h > 0 để x + h và x − h nằm trong I .
Ví dụ : Cho hàm
x
e
. Xét biểu thức
2
, , 0
x h x h x
e e e x R h

   

Theo bất đẳng thức Cauchy, suy ra
2

0
x h x h x
e e e

  

Do đó, áp dụng hệ quả 4 ta có hàm
x
e
là hàm lồi.

1
Nhóm 4: 1. Nguyễn Thị Bích Hồng
2. Trịnh Cẩm Vân
3. Ngô Thị Duy Bình


Chương 5:
TIÊU CHUẨN TỐI ƯU ĐIỂM YÊN NGỰA CỦA BÀI TOÁN QUY HOẠCH
PHI TUYẾN KHÔNG KHẢ VI

Mục đích của chương này là tìm các tiêu chí tối ưu của các điểm yên ngựa (điểm
dừng) cho bài toán qui hoạch phi tuyến. Minh họa bằng ví dụ đơn giản sau.
Hãy xem xét các vấn đề cực tiểu của hàm

trên tập
 
/ , 2 0X x x x    
;
   

2
xx


cho giải pháp
2x 
, thì hàm cực tiểu là
 
4x


. Các điểm yên ngựa
tối ưu cho bài toán này là: Một điều kiện cần và đủ để
x
là một giải pháp cực tiểu,
tồn tại một số thực
u
(ở đây
4u 
) sao cho với mọi
xR
,
,0u R u
:
     
   
2 ( 2) 2x u x x u x x u x
  
          


Dễ dàng xác định bất đẳng thức trên với
2x 
,
4u 
. Do đó hàm

xác định trên
2
R
bởi:
     
,2x u x u x

   

có một điểm yên ngựa tại
2x 
,
4u 
, có 1
điểm cực tiểu tại
 
,xu
với
xR
, và u cực đại với
uR
.
Đối với những vấn đề trên, các điểm yên ngựa tối ưu xảy ra khi điều kiện cần và đủ
cho tiêu chuẩn tối ưu

x
một giải pháp cực tiểu. Điều này không xảy ra với mọi
trường hợp. Chúng ta sẽ rõ điều kiện điểm yên ngựa trên là một điều kiện tối ưu đủ
với điêu kiện lồi.
Tuy nhiên để thiết lập điều kiện cần thiết cho các điểm yên ngựa trên, chúng ta
không những xét tính lồi mà còn xét điều kiện chính quy, tính ràng buộc.
Chúng tôi sẽ phát triển các tiêu chuẩn tối ưu của chương này trên giả thiết vi
phân. Tiếp theo chương 7 và 11, sẽ thiết lập các tiêu chí tối ưu liên quan đến hàm
lũy thừa.
I. Các bài toán cực tiểu và điểm yên ngựa (điểm dừng).
Các tiêu chí tối ưu của chương này liên quan các giải pháp vấn đề cực tiểu, vấn đề
cực tiểu địa phương, và hai điểm yên ngựa với nhau. Chúng tôi định nghĩa vấn đề
dưới đây.



2
Cho
0
X
là một tập hợp con của
n
R
, cho

và g tương ứng là một hàm số và hàm
vector m chiều xác định trên
0
X
.

1. Bài toán cực tiểu (MP)
Tìm
x
, nếu nó tồn tại:
 
 
min
xX
xx




 
0
/ ,g(x) 0x X x x X   

Tập X được gọi là vùng cho phép hoặc tập khả vi,
x
là giải pháp tối thiểu, và
 
x


là cực tiểu. Tất cả các điểm
x
trong vùng cho phép X gọi là điểm khả vi. Điểm có
tính khả vi trên X được gọi là điểm khả vi.
Nếu X là một tập lồi, và nếu


là hàm lồi trên tập
X
, hàm cực tiểu MP thường
được gọi là một hàm lồi.
(Nhận thấy rằng hàm cực tiểu trên là một trường hợp đặc biệt của hàm cực tiểu tổng
quát 1.6.9, đẳng thức vector k chiều h (x) = 0 . Lý do cho điều này là trong trường
hợp khả vi không có ý nghĩa tối ưu cho đẳng thức phi tuyến. Xem 5.8.2, 6.4.2,
6.4.8)
2. Bài toán cực tiểu địa phương (LMP)
Tìm
x
trong
X
, nếu nó tồn tại, như vậy đối với quả cầu mở
()Bx

;
x
với bán kính
0


,
( ) X (x) ( )x B x x


   

3. Bài toán điểm dừng Fritz John (FJSP)


Tìm
 
0
00
, , , , 0
m
x X r R r R r r   
, nếu chúng tồn tại

     
 
 
0 0 0
0
00
, , , , x, ,
or_ _ 0, ,and_ _
, , ( )
m
x r r x r r r r
f all r r R all x X
x r r r x rg x



  


4. Bài toán Điểm dừng The Kuhn-Tucker(KTSP)
Tìm

0
, , 0
m
x X u R u  
, nếu tồn tại

3
     
   
0
,u , x,
or_ _u 0,u ,and_ _
,u ( )
m
x x u u
f all R all x X
x x ug x
  


  


5. Ghi chú
Nếu (
x
,
0
r
,

r
) là một giải pháp của FJSP và
0
0r 
, thì (
x
,
r
/
0
r
) là một giải pháp
của KTSP. Ngược lại, nếu (
x
,
u
) là một giải pháp của KTSP, thì (
x
,1,
u
) là
một giải pháp của FJSP.
6. Ghi chú
Các hàm số
 
0
,,x r r

và
 

,xu

xác định như trên thường được gọi là hàm
Lagrangian hoặc chỉ đơn giản là Lagrangians, và vector m-chiều
r
và
u
là nhân tử
Lagrange hay biến kép. Trò chơi qui tắc nhân tử Lagrange trong các bài toán tuyến
tính và phi tuyến thì rất đơn giản, (xem ví dụ 65). Ở đây, bởi vì chúng tôi có những
ràng buộc bất đẳng thức, nhân tử Lagrange sẽ trả về số không âm. Khi chúng ta xem
xét những ràng buộc đẳng thức trong 5.3.2, 5,4-2, và 5,4-8, nhân tử liên kết với các
đẳng thức sẽ không phải là số dương.
7. Ghi chú
Bất đẳng thức đúng của cả hai vấn đề điểm yên ngựa, FJSP 3 và KTSP 4
   
00
, , x, ,x r r r r




với mọi
0
xX

và
   
, x,x u u



với mọi
0
xX

có thể được giải thích như là một nguyên tắc tối thiểu, tối đa giống như Pontryagin
của nguyên tắc [Pontryagin et al. 62]. Nguyên tắc Pontryagin là một điều kiện tối ưu
cần thiết cho việc điều khiển tối ưu hệ thống của các phương trình vi phân . Như
vậy, nó là một điều kiện tối ưu cần thiết cho bài toán quy hoạch, không phải trong
n
R
,nhưng trong một tập khác. Gần hơn [Halkin 66, Canon et al. 66, Mangasarian-
Fromovitz 67] một nguyên tắc tối thiểu cũng đã được thành lập cho vấn đề kiểm
soát tối ưu của các phương trình vi phân . Đây là một vấn đề quy hoạch trong
n
R
,
không phải là lồi, và do đó các kết quả của chương này không áp dụng.Tuy nhiên
các điều kiện tối ưu của chương 7 và 11 dựa chủ yếu trên tuyến tính và không lồi,
để áp dụng trong các bài toán điều khiển tối ưu được mà phải mô tả bởi phương
trình vi phân phi tuyến.

4
II. Một số kết quả cơ bản cho bài toán cực tiều hóa và cực tiểu địa phương
Một số kết quả cơ bản liên quan đến việc tập hợp các giải pháp của các bài toán
cực tiểu, mối liên quan giải pháp của vấn đề cực tiểu và cực tiểu địa phương với
nhau.
1. Định lý: Cho X là một tập lồi, và để cho

là hàm lồi trên X. Tập các giải pháp

của MP 5.1.1 là lồi.
Ghi chú: Điều kiện đủ nhưng không cần thiết cho các tập lồi của X là X ° là một
tập lồi và g lồi trên X °. Từ 4.1.10 và 3.1.9.
Chứng minh: Lấy
1
x
và
2
x
là giải pháp của MP. Đó là,
   
 
12
min
xX
x x x
  



Theo trên
,X

lồi, nên
 
12
0 1, 1 x x X
  
    
và

   
     
 
1 2 1 2 1
1 1 min
xX
x x x x x x
       


      


Do đó
 
12
1 xx


cũng là một tập giải pháp của MP, và tập giải pháp lồi.
+ Pontryagin đưa ra nguyên tắc cực đại thay vì nguyên tắc cực tiểu bởi vì ông phủ
định các quy hoạch phi tuyến của Lagrangian.
2 Định lý tính đơn trị
Cho X là tập lồi và
x
là một giải pháp của MP 5.1.1. Nếu

là hàm lồi nghiêm
ngặt tại
x

, thì
x
là giải pháp duy nhất của MP.
Chứng minh:
Cho
ˆ
xx
là một giải pháp khác của MP, có nghĩa là,
ˆ
xX
, và
 
 
ˆ
xx


. Từ
X là tập lồi, thì
 
ˆ
1 x x X

  

lồi chặt chẽ về

tại
x
khi

01


.

   
 
 
 
ˆˆ
11x x x x x
      

     


Điều này mâu thuẫn với giả thiết rằng
 
x

là cực tiểu, và do đó
ˆ
x
không thể có 1
giải pháp nào khác.
3. Định lý
Cho X là tập lồi, và cho

là một hàm lõm,



không là hàm hằng trên X.
Không có điểm bên trong nào thuộc X là giải pháp của MP 5.1.1, hoặc tương đương
với bất kỳ giải pháp
x

nào của MP, nếu nó tồn tại, phải là một điểm liên kết của X.

5
Chứng minh:
Nếu MP 5.1.1 không có giải pháp, định lý không đúng. Để cho x là một giải pháp
của MP. Cho


không chứa trong X, tồn tại một điểm
xX
như vậy
 
 
xx



. Nếu z là một điểm bên trong của X, tồn tại một điểm
yX
, vài

sao cho
01



thì
 
1z x y

  

Xem hình 5.2.1. Do đó:
           
     
1 1 1z x y x y x x x
          
         



và
 
x

không đạt được cực tiểu tại z.
Hình 5.2.2 cho thấy một ví dụ đơn giản của định lý 3 trong
R

1. ĐỊNH LÝ:
Nếu
x
là một giải pháp của MP 5.1.1, thì nó cũng là một giải pháp của
LMP 5.1.2. Ngược lại nếu X là lồi và


là lồi tại
x



Chứng minh:
Nếu
x
là giải pháp của MP 5.1.1, x cũng là giải pháp của LMP 5.1.2 cho bất kỳ 8>
0.
Ngược lại cũng đúng nếu
X là tập lồi và

lồi tại
x
.
Chứng minh:

Hình 5.2.2
x
R

6
Nếu
x
là giải pháp của MP,thì
x
cũng là giải pháp của LMP với bất kỳ
0



. Để
chứng minh, ta giả sử
x
là giải pháp của LMP với
0


và X là tập lồi,

lồi tại
x
.
Lấy
yx
là một điểm trong tập X. Khi X là tập lội thì
 
1 x y X

  
,với
01



Bằng cách chọn

đủ nhỏ,
0/yx


  
và
1


ta có:
 
 
1x y x x y B X

  
      

Do đó:
   
x x y x
  



(khi
x
là giải pháp của LMP)

 
 
 
1 xy
  
  

(lôi tại
x
)
Từ các chứng minh trên:
 
 
xy



III. Tiêu chuẩn tối ưu đủ
Các tiêu chí tối ưu chủ yếu phát triển ở đây (1 và 2 dưới đây) đòi hỏi không có giả
định lồi trong bài toán cực tiểu MP 5.1.1.
Những tiêu chí này khá đơn giản để có được và không cần phải phức tạp
máy móc để lấy được. Kết quả đầu tiên của loại hình này đã thu được trong
[Uzawa 58].
1. Định lý tối ưu đủ
Nếu
 
,xu
là một giải pháp của KTSP 5.1.4, thì
x
là một giải pháp của MP 5.1.1.
Nếu
 
0
,,x r r
là một giải pháp của FJSP 5.1.3, và
0
0r 

thì
x
là giải pháp của MP
5.1.1.
Chứng minh:
Từ định lý thứ 2 và chú ý 5.1.5.
Cho
 
,xu
là giải pháp của KTSP 5.1.4. thì mọi
0u 
trên
m
R
và mọi x trên
0
X

       
   
x ug x x ug x x ug x
  
    

Từ bất đẳng thức đầu tiên chúng ta có:

7
   
0u u g x
với mọi

0u 

Với bất kì j,
1 jm

Cho
,
1
ii
jj
uu
uu


1, 2 1, 1, i j j m  

Theo trên thì
 
0
j
gx
. Lặp lại điều này cho tất cả j, sẽ nhận được
 
0
j
gx
, và do
đó
x
là một điểm khả vi, đó là

xX
.
Nếu
0u 
và
 
0gx
, ta có
 
0ug x 
. Nhưng bất đẳng thức đầu tiên của bài
toán điểm dừng , đặt
 
0ug x 
. Do đó
 
0ug x 

Lấy x là điểm bất kỳ trong X, từ bất đẳng thức thứ hai của bài toán điểm dừng, ta
nhận được:
 
   
x x ug x


(khi
 
0ug x 
)


 
x


(khi
 
0, 0u g x
)
Do đó
x
là một giải pháp của MP.
Điều này cần phải được nhấn mạnh ở đây là vì không có giả định lồi đã được thực
hiện trong các định lý trên, ràng buộc của đẳng thức có thể được xử lý bởi
thay thế chúng bằng hai ràng buộc của bất đẳng thức. Đó là, thay thế
 
0hx
bởi .
 
0hx
và
 
0hx

2. Bài toán
Hãy xem xét các bài toán cực tiểu:
 
 
min
xX
xx





   
 
0
/ , 0, 0x X x x X g x h x    

ở đây h là hàm vecto k_chiều trên
0
X
và ngược lại được xác định trên MP 5.1.1.
Cho:
       
00
, , ,x r r s r x rg x sh x

  

Và:

8
       
,,x u v x ug x vh x

  

Nếu tồn tại
0

, , 0,
mk
x X u R u v R   
thì:
     
0
, , , , , ,
0, , ,
mk
x u v x u v x u v
u u R v R x X


   

Hoặc nếu tồn tại
km
RsrRrrRrXx  ,0,,0,,
0
0
sao cho
0
000
,,,0
),,,(),,,(),,,(
XxRsRrr
srrxsrrxsrrx
km





Thì
x
là nghiệm của bài toán cực tiểu hoá. (Chú ý v và s không bị hạn chế về dấu.)
Câu hỏi có thể nảy sinh như loại điểm nào là điểm
x
nếu
),,(
0
rrx
là nghiệm của
FJSP 5.1.8 và ta không yêu cầu
0
0
r
. Đáp án cho câu hỏi này được cho bởi kết quả
sau.
5.3. Hệ quả
Nếu
),,(
0
rrx
là nghiệm của bài toán FJSP ở mục 5.1.3, thì hoặc
x
giải quyết bài
toán MP ở mục 5.1.1 hoặc X không có tương quan gì với
0)( xg
, nghĩa là:


 }0)(,/{
0
xgXxx

Chứng minh Bằng lý luận tương tự như trong chứng minh định lý 1 ở trên chúng ta
chứng minh rằng
0)( xg
và
0)( xgr
.
Nếu
0
0
r
thì
x
giải quyết bài toán MP do định lý 1.
Nếu
0
0
r
thì
0r
và từ bất đẳng thức thứ hai của bài toán FJSP 5.1.8 ta có
0
),()(0 Xxxgrxgr 

Nếu tập
}0)(,/{
0

 xgXxx
không rỗng, thì cho phần tử bất kỳ
x
ˆ
trong đó
0)
ˆ
( xgr
, ngược với giả thiết ở trên là
0
,0)( Xxxgr 
, ta có

 }0)(,/{
0
xgXxx

5.4. Tiêu chuẩn tối ưu cần có
Việc đáp ứng tiêu chuẩn cần thì phức tạp đáng kể hơn so với việc đáp ứng tiêu
chuẩn tính tối ưu đủ. Ta xem các tiêu chuẩn được so sánh trong bảng sau :

9
Tiêu chuẩn cần
Tiêu chuẩn đủ
(a) Cần tính lồi
(b) Cần hệ quả của định lý tách của tập lồi
(c) Điều kiện chính quy (tính chất ràng
buộc) cần phải có trong các tiêu chuẩn quan
trọng hơn (7 tiêu chuẩn dưới)
- Không cần tính lồi

- Không cần định lý tách của tập lồi
- Không cần tính chất ràng buộc

Chúng ta bắt đầu bằng việc thiết lập 1 tiêu chuẩn tối ưu mà không đòi hỏi bất
kỳ điều kiện chính quy nào. Tiêu chuẩn tối ưu cần có này tương tự với tiêu chuẩn
tối ưu do Fritz John đưa ra (xem thêm chương 7) mà được suy ra trong trường hợp
hàm θ và g khả vi nhưng không lồi. Ở đây ta không dùng tính khả vi, thay vào đó ta
dùng tính lồi. Tiêu chuẩn hiện tại là tiêu chuẩn điểm yên ngựa, trong khi của Fritz
John là tiêu chuẩn gradient. Điểm tương đồng chính là sự hiện diện của số nhân
0
r

trong cả hai tiêu chuẩn
5.4.1. Định lý tính tối ưu điểm yên ngựa Fritz John
Cho
0
X
là một tập lồi trong
n
R
và lấy

và g lồi trên
0
X
. Nếu
x
là nghiệm của bài
toán MP 5.1.1, thì
x

và một số
0),(,,
00
 rrRrRr
m
thỏa bài toán FJSP 5.1.3 và
0)( xgr

Chứng minh: Vì
x
thỏa bài toán MP
0)(
0)()(


xg
xx

không có nghiệm
0
Xx

Do hệ quả 4.2.2, tồn tại
0),(,,
00
 rrRrRr
m
sao cho
0)()]()([
0

 xgrxxr

for all
0
Xx

Với cách đặt
xx 
ở trên, ta có
0)( xgr
.
Nhưng vì
0r
và
0)( xg
, ta có
0)( xgr
. Do đó
0)( xgr

Và
)()()()(
00
xgrxrxgrxr 

với mọi
0
Xx
thỏa bất đẳng thức thứ II của bài toán
FJSP 5.1.3.

Ta cũng có vì
0)( xg
mà
0)( xrg
với mọi
m
Rrr  ,0

và do đó , từ
0)( xgr

)()()()(
00
xgrxrxrgxr 


m
Rrr  ,0
thỏa bất đẳng thức thứ I của bài toán
FJSP 5.1

10
5.4.2. Bài toán
Xem xét bài toán cực tiểu hóa
)(min)( xx
Xx





}0)(,0)(,/{
0
 xhxgXxxXx

Với h là 1 hàm vecto tuyến tính k chiều trên
n
R
,

và g lồi trên
0
X
, và các thành
phần còn lại được định nghĩa như trong MP 5.1.1. Chứng minh rằng nếu
x
là 1
nghiệm của bài toán trên thì
x
và một vài
0),(,,,
00
 rrRsRrRr
km
,
0,,
0
srr

thỏa
0)( xgr

, và
)()()(),,,(
,,,0),,,,(),,,(),,,(
00
0
000
xshxrgxrsrrx
XxRsRrrsrrxsrrxsrrx
km





(Gợi ý : sử dụng hệ quả 4.2.2. )
Nên chú ý trong tiêu chuẩn tối ưu cần thiết ở trên không bảo đảm
0r
Trong
những trường hợp mà
0r
dễ thấy ràng tiêu chuẩn tối ưu cần thiết FJSP 5.1.3
không nói nhiều về bài toán cực tiểu MP 5.1.1, vì hàm

đã mất khỏi 5.1.3 và một
hàm khác có thể đã thay thế vai trò của nó. Để tránh trường hợp như vậy, chúng ta
phải đưa vào một vài điều kiện chính quy. Điều kiện chính quy này được chỉ ra để
dùng một số tính chất ràng buộc xuyên suốt sách này. Một số tính chất ràng buộc
này (giống như 3 tính chất giới thiệu ở dưới ) chỉ sử dụng của tính chất lồi của các
hàm xác định trên miền X. Các tính chất ràng buộc khác, được giới thiệu sau, như
trong chương 7 chẳng hạn, chủ yếu dùng tính khả vi của hàm xác định trên miền X.

5.4.3. Tính chất ràng buộc của Slater
Cho
0
X
là một tập lồi trên
n
R
. g là hàm vectơ lồi m - chiều trên
0
X
với miền khả
thi lồi được xác định
}0)(,/{
0
 xgXxxX
được cho là thỏa mãn tính chất ràng buộc của Slater (trên
0
X
) nếu tồn tại 1
0
Xx
mà
0)( xg

5.4.4. Tính chất ràng buộc của Karlin
Lấy
0
X
là 1 tập lồi trên
n

R
. g là hàm vecto lồi m-chiều trên
0
X
với miền khả thi
lồi được xác định

11

}0)(,/{
0
 xgXxxX
được cho là thỏa mãn sự ràng buộc của Karlin (trên
0
X
) nếu
0,  pRp
m
sao cho
0)( xpg
với mọi
0
Xx

5.4.5. Tính chất ràng buộc nghiêm ngặt
Cho
0
X
là 1 hàm lồi trên
n

R
. G là hàm vecto lồi m - chiều trên
0
X
với miền khả thi
lồi được xác định
}0)(,/{
0
 xgXxxX
được xem như thỏa mãn tính ràng buộc nghiêm ngặt (trên
0
X
) nếu X chứa ít nhất 2 điểm phân biệt
1
x
và
2
x
sao cho g lồi ngặt tại
1
x

5.4.6. Bổ đề
Tính ràng buộc của Slater và tính ràng buộc của Karlin là tương đương. Tính ràng
buộc nghiêm ngặt bao hàm tính ràng buộc của Slater.lẫn của Karlin
Chứng minh
)43( 
Dùng định lý 4.8.3 của Gordan, 3 và 4 là các phương trình tương đương
)34( 
Vì

0
X
lồi, với mọi
10, 


021
)1( Xxx 


Do g lồi ngặt tại
1
x
nên từ 4-1-4 suy ra
0)()()1(])1[(
2121
 xgxgxxg


trong đó bất đẳng thức cuối cùng có được là do
0)(
1
xg
và
0)(
2
xg
. Do đó g
thoả mãn tính chất ràng buộc của Slater và của cả Karlin.


Bây giờ chúng ta đã có thể suy ra tiêu chuẩn tối ưu cần thiết quan trọng nhất mà
không sử dụng tính khả vi. Định lý được biết nhiều dưới tên gọi Kuhn-Tucker, ngay
cả Kuhn và Tucker đều đòi hỏi cả tính lồi lẫn tính khả vi trong phép lấy đạo hàm
của nó. Định lý trong dạng hiện tại của nó, không có bất kỳ yêu cầu nào về tính khả
vi, được quy cho Uzawa và Karlin
5.4.7. Định lý tối ưu cần thiết điểm yên ngựa Kuhn-Tucker
Cho
0
X
là 1 tập lồi trên
n
R
, giả sử

và g thoả mãn tính chất ràng buộc của Slater,
tính chất ràng buộc của Karlin, hay là tính chất ràng buộc nghiêm ngặt trên
0
X
.

12
Nếu x là nghiệm của bài toán MP 5.1.1, thì
x
và một số
0,  uRu
m
giải đáp bài
toán KTSP 5.1.4 và
0)( xgu
.

Chứng minh
Trước hết, ta thấy rằng với bổ đề 6 ở trên, cần phải thiết lập duy nhất định lý tính
chất ràng buộc của Karlin ở bên dưới. Bằng Định lý 1, và một số
0),(,,
00
 rrRrRr
m
, giải ra bài toán FJSP 5.1.3 and
0)( xgr
. If
0
0
r
, thì với
chú ý 5.1.5 ta đã chứng minh xong. If
0
0
r
, then
0
0
r
, và từ bất đẳng thức thứ hai
của bài toán FJSP 5.1.3
0
),(0 Xxxgr 
[vì
0
0
r

and
0)( xgr
]
Mâu thuẫn với tính chất ràng buộc của Karlin. Do đó
0
0
r

Chúng ta tóm tắt trong hình 5.4-1 hệ thức giữa nghiệm của bài toán khác nhau trong
chương này

Cuối cùng chúng ta kết thúc chương này bằng bằng việc suy ra tiêu chuẩn
tính tối ưu điểm yên ngựa Kuhn-Tucker với sự có mặt của các ràng buộc đẳng thức
Hình 5.4.1: Hệ thức giữa nghiệm của
Bài toán cực tiểu hoá địa phương (LMP ) 5.1.2,
Bài toán cực tiểu hoá ( MP ) 5.1.1,
Bài toán saddle point Fritz John ( FJSP ) 5.1.3,
Bài toán saddle point Kuhn-Tucker ( KTSP ) 6.1.4.