Giải bài toán tối ưu bằng phương pháp Gradient và ứng dụng

t c ñin. 
 Trong bài báo cũng gii thiu v bài toán phân lp d liu dùng phương pháp SVM ñ 
ñưa bài toán phân lp d liu v bài toán ti ưu. Sau ñó, bài báo trình bày mt s tính toán 
th nghim, ng vi các thut toán ñã ñưc ñ xut. 
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 137 
2. GII THIU V BÀI TOÁN PHÂN LP D LIU SUPPORT VECTOR 
MACHINE (SVM) 
 Support Vector Machines (SVM) [1] là k thut mi ñi vi bài toán phân lp d liu, 
ñây cũng là mt trong nhng phương pháp hc s dng không gian gi thit các hàm tuyn 
tính trên không gian ñc trưng nhiu chiu da vào lý thuyt ti ưu và lý thuyt thng kê. 
Trong k thut SVM , không gian d liu nhp ban ñu ñưc ánh x vào không gian ñc 
trưng có xác ñnh mt siêu phng phân chia ti ưu. SVM dng chun nhn d liu vào và 
phân loi chúng vào hai lp khác nhau. Do ñó, SVM là mt thut toán phân loi nh phân. 
 n
 Tp D={}( xcxRiiii , ), ∈= , 1,2,..., mc , i ∈−{} 1,1 ñưc gi là tp mu hc. Tp mu 
hc tm thưng nu tt c các nhãn ci có giá tr như nhau. Gi s tp là phân tách tuyn 
tính, nghĩa là tp ñưc chia thành hai min ñưc xác ñnh bi hai siêu phng song song, 
sao cho mi mt lp thuc v mt không min không gian mà không nm gia hai 
siêu phng. 
 Hình 1. Các siêu phng phân tách trong không gian hai chiu. 
 Hình 2. Siêu phng tách. Hình 3. Siêu phng ti ưu. 
138 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 Phương trình tương ng ca hai siêu phng: 
 +) ,     1. 
 +) ,     1. 
 Trong ñó: 
 +) w gi là vector pháp tuyn n chiu. 
 +) b là giá tr ngưng, xác ñnh khong cách gia siêu phng và gc. 
 Ngưi ta mun tìm mt véc tơ W sao cho khong cách gia hai siêu phng tách là ln 
nht. Điu ñó dn ñn bài toán ti ưu và bài báo s trình bày  mc 4. 
3. GII BÀI TOÁN TI ƯU BNG PHƯƠNG PHÁP GRADIENT 
3.1. Phương pháp Gradient 
3.1.1. Bài toán qui hoch phi tuyn không ràng buc 
 Xét bài toán qui hoch phi tuyn không ràng buc: [3] 
 min 
 
 ∈ ,
 Gi s rng là hàm kh vi, khi ñó ñim cc tr ca tha mãn: 
 ∗
   
 ∗
 Vic trc tip gii phương trình    0, rt phc tp. Do ñó cn xây dng mt 
phương án hiu qu hơn so vi vic gii trc tip 0 bài toán . 
  
 Ý tưng ca phương pháp này là tìm mt dãy phương án chp 0nhn ñưc hi t 
ñn . Giá tr mi ca dãy s ti bưc ñưc ưc tính: 
 ∗
    1 
    
 Trong ñó, véc tơ là hưng di chuyn t   ñn , và ñ dài bưc di chuyn . 
    
 Đ ñiu kin:    
  
ñưc bo ñm ti mi giá tr mi, thì véc tơ hưng gim phi tha mãn: 
 
  
  
 Khi ñó vi ñ dài bưc ñ bé 〈ta có: ,  〉  0.
 
  
          
 Chn hưng      . Suy  ra:     〈 ,  〉      ,
   
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 139 
 xk+1 =−∇ x kk tfxk( k ), = 1,2,3... 
 Biu din dưi dng ta ñ biu thc trên: 
 ()xik+1 = () x ikk −∂ tfx ( k )/ ∂= xi i , 1,2,...,. n 
 Vì tính ñơn gin, hiu qu nên ñây là phương pháp ph bin ñưc s dng cho bài 
toán qui hoch phi tuyn không ràng buc. Vn ñ còn li là la chn tk trong mi bưc 
tính như th nào. Thut toán sau ñây ñưa ra giá tr ưc tính ca tk ti mi bưc . 
 Bưc 0. Chn trưc mt giá tr . 
 Bưc 1. Tính x= xk − tfx ∇ ( k ), 
 Bưc 2. Kim tra: 
 − Nu fx()< fx ()k , ly tk = t . 
 − Ngưc li, ñt t= t / 2 và quay li bưc 1. 
 Hình 4. Ý nghĩa hình hc ca phương pháp gradient. 
3.1.2. Bài toán ti ưu có rng buc 
 Xét bài toán ti ưu có ràng buc: [3] 
 minfx ()< fx (k ) (3.1) 
 x∈ C
 Đ áp dng các phương pháp gii bài toán ti ưu không ràng buc, ngưi ta chuyn 
bài toán ti ưu có ràng buc v dng bài toán ti ưu không ràng buc. Có nhiu phương 
pháp chuyn ñi như: Phương pháp nhân t Lagrange, phương pháp hàm chn.  ñây ta s 
dng phương pháp hàm chn, bng cách ñnh nghĩa mt hàm chn Ψ là hàm li trên tp 
như sau: 
 0, x∈ C
 Ψ(x ) =  
 +∞,x ∉ C .
 Và thc hin xét bài toán ti ưu không ràng buc ca hàm ñưc biu din bi tng 
ca hai hàm: 
140 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 (3.2) 
      Ψ
xác ñnh trên tp . Trong ñó, kh vi. 
 
 Tuy nhiên, ta không th áp dng trc tip phương pháp gradient vì hàm là không 
kh vi ti biên ca . Do ñó ngưi ta s dng thut toán gradient ci tin ñ giiΨ bài toán 
ti nói trên. 
 Đt: 
 
là tp các hưng chn nhn.,∈,0⊂ ñưc ti . Và: ,
  
 
là mt nón li.   : ,     0,  ∈  ⊂  ,  ∈ 
 Ta xét các ñiu kin ti ưu tương ñương ñ là ñim cc tiu: 
 ∗
 
 (3.3) 
  ∗ ∗ ∗ ∗
          ∈  ,
vi . Nói cách khác: 
 ∗ ∗
  ∈ Ψ 
 (3.4) 
 ∗ ∗
  ,   0, ∀ ∈  ,
 Mà là hàm li, suy ra: 
 Ψ
 (3.5) 
  ∗ ∗
   ,   0, ∀ ∈  .
 Chú ý: Vi trưng hp hàm li, mt trong các ràng buc t (3.2) ñn (3.4) là ñiu 
kin ñ ñ là cc tiu toàn cc ca trên tp li . 
 ∗
 Đnh lý 3.1: Đim tha mãn ñiu kin ti ưu cc tiu ña phương bc nht ca 
hàm trên tp vi ñ chính∈  xác nu: 
     0
 (3.6) 
 
 〈 ̅, 〉  , ∀ ∈ , ||||  1.
 Đây cũng là ñiu kin dng ca thut toán gradient. Trong trưng hp và 
 
 , rút gn bt ñng thc (2.5):   
  Ψ  0
  
   ||〈 , 〉  || ∈ ̅〈 ̅  , 〉
  || ∈ ̅〈 ̅  , 〉
  ∈ ̅ ||〈 ̅  , 〉
   ||‖ ̅  ‖.
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 141 
 Vi mi , ký hiu: 
  ∈ 
 (3.7) 
  
 ;     〈,   〉  ‖  ‖  Ψ,
 2
 (3.8) 
    ∈; ,
trong ñó là hng s dương. 
 Xét véc tơ: 
 (3.9) 
 
      ∈  .
 Trong trưng hp thì vi mi tham s 
 
 . Mt s tính cht ca ≡ ñiu  , Ψkin ≡ 0ti ưu bc nht:   ≡ 
  0
 (3.10) 
 〈      ,   〉  0, ∀ ∈ ,
trong ñó . Suy ra: 
  ∈ Ψ
 (3.11) 
 
       ∈  .
 Gi s hàm mc tiêu (2.1) tha mãn ñiu kin Lipschitz: 
 (3.12) 
 ‖  ‖  ‖  ‖, ∀,  ∈ ,
 Do tp li, biu thc (3.9) tương ñương vi: 
 
 (3.13) 
  
 |    〈,   〉|  ‖  ‖ , ∀,  ∈ ,
 2
 Gi là ñ bin thiên ca hàm trên tp 
   
   
    .
 ‖  ‖
3.1.3. Thut toán gradient [4] 
 Thut toán 3.1. Vòng lp ca phương pháp gradient 
 , .
  : :  . 
  : :  . 
    , . : ..
 :  , . 
  : , .   ; , .   ;
142 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 Chn giá tr khi to cho thut toán gradient: 
 − trong ñó là hng s Lipschitz ca gradient ca hàm f (thưng 
chn hng , 0 s  L  rt ln).  
 − Hai tham s ñiu chnh và . 
   1   1
 − Chn bt kỳ. 
  ∈ 
 − k nguyên, . 
 Vi vic chn tham 0 s ñiu chnh như trên, d thy rng giá tr luôn tăng và . 
    
 Thut toán 3.2. Thut toán gradient 
 , .
 ITERATION: (Bưc lp k) 
 :  , . ,
  ≔ , . ,
 
  ≔ max ,  .
 
 Suy ra , t thut toán trên thu ñưc biu thc sau hin nhiên ñúng: 
   
 (3.14) 
       .
 Ngoài ra, nu thì: 
  
    
   , ∀  0.
3.2. Thut toán Gradient ci tin 
 Sau ñây, chúng ta phát biu thut toán Gradient ñi ngu. 
 Thut toán 3.2. Thut toán Gradient ñi ngu [2] 
 , ,   0
 INITIAL (Khi to) : Cho , ñnh nghĩa hàm , chn hng s 
  
dương sao cho .  ∈  Ψ    ‖  ‖
    
 ITERATION (Bưc lp k) : 
   , ,   , ,
  1
   max ,  ,   ,
   
       〈,   〉  Ψ.
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 143 
 Tip theo ñây, chúng ta s xét ñn mt thut toán ñưc ci tin có tc ñ hi t tt hơn 
hn so vi hai thut toán là thut toán gradient và thut toán gradient ñi ngu ñã ñưc 
xét ñn. 
 Thut toán 3.3. Thut toán gradient ci tin [1] 
  
 INITIAL (Khi to) : Chn , thuc ñon,  ,  ñ bé, . Đt 
 , chn hng s dương x ∈saodom choΨ  . 0,    0  
 
 ‖ ITERATION‖ (Bưc lp k) :    
  Đt 
 :  
  Tìm là giá tr tha mãn phương trình bc hai  . Đt , tính 
   
   2  
 theo biu thc (3.7).   
 
  Nu dng thut toán, ly giá tr 
    
  Nu không,〈  chuyn,  sang  bưc〉  iii và thc hin gán:  ≔ . .
  ≔ ,  ≔ ,  ≔ ,
 
  ≔ ,  ≔ ,
  
 Quay li bưc ii.      〈,   〉  Ψ.
4. MT S TÍNH TOÁN TH NGHIM 
 T bài toán phân lp nêu  Mc 2, chúng ta ñưa bài toán ñó v dng ti ưu. Vùng 
không gian nm gia hai siêu phng gi là cn biên, khong cách gia hai siêu phng là 
 2
 . Bài toán ñt ra là, tìm khong cách ln nht gia hai siêu phng. Như vy, bài toán 
 w
chuyn v bài toán ti ưu ñưc phát biu như sau: 
 Tìm cc tiu ca hàm: 
 
vi ñiu kin: |||| 
  
 Trong nhiu  trưng,   1,∀hp, tp hun 1,2,...,. luyn D có th không phân tách tuyn tính (hay tn 
ti ñim nhiu), khi ñó ta s dng bin bù ñ ño mc ñ không th phân loi ñim d 
liu : 
 
  
   
hàm mc tiêu tăng thêm mt  lưng,  tương  ng 1 khi  tham, 1  s   . khác không. C th bài toán 
lúc này tr thành: 
144 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
  
 1 
 min ‖‖    
vi ñiu kin 2  
 Đây là hàm ,mc  tiêu  dng  1 quy   ,∀hoch  1,2,...,.toàn phương, mt trưng hp riêng ca qui 
hoch li tuyn tính. Vì vy, nó còn có th ñưc gii bng phương pháp FrankeWolfe hay 
phương pháp ñơn hình Beale. Tip ñây, chúng ta s dng thut toán gradient cơ bn ñ gii 
bài toán ti ưu vi hàm mc tiêu trên. 
 1
 Xét vi mt trưng hp riêng ca bài toán nêu trên khi , chn tham s C =
   0 λm
vit li bài toán ti ưu cn gii: 
  (4.1) 
   1
    ‖‖   
 2  
vi ñiu kin: Trong trưng hp này 
 , và hàm  0,1, . ,  1,2,...,.
    
  ‖‖ Ψ  ∑ 
 Ta s s dng thut toán gradient ñ gii bài toán c th trên. Tc là tìm ta ñ ca 
véc tơ là nghim ti ưu toàn cc ca hàm s: 
 , 
  
   1
   ‖‖   
 Ý tưng ca bài toán như sau: 2  
 − Cho trưc mt véc tơ pháp tuyn a, có gc nm trên ñưng thng bt kỳ phân chia 
hai lp d liu cho trưc. 
 − Hai lp d liu này ñưc to ngu nhiên và gán nhãn . 
 − Sau ñó s dng thu toán ti ưu gradient ñ tìm véc tơ1; pháp 1 tuyn ca ñưng thng 
ti ưu phân chia hai lp d liu ñã to ngu nhiên (véc tơ pháp tuyn này có gc nm trên 
ñưng thng). 
 − Khi ñã xác ñnh ñưc véc tơ pháp tuyn có gc nm trên ñưng thng, thì chúng ta 
cũng d dàng xác ñnh ñưng thng duy nht tha mãn ñiu kin này. 
 Khai báo sai s . Thut toán có th ñưc vit li như sau: 
 
 Thut toán 4.1: Thut  10 toán gradient 
 
  Chn giá tr ban ñu , chn s cho trưc . 
 
  Lp:    0
 Bưc 1: Tính  1,2, . .. 
 Bưc 2: Kim tra:    
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 145 
  Nu fx(k+1 )< fx () k , chn . 
 α
  Ngưc li, ñt α = và quay li Bưc 1. 
 2
 Chy th nghim vi mt s b d liu sau: 
 a. Th nghim vi d liu ngu nhiên gm 20 ñim 
 >> [a,w] = PhanLop(20,2) 
 a = w = 
 2.2805 1.0671 
 5.6246 3.1872 
 Hình 5. Mô phng ñ th phân lp d liu 20 ñim ngu nhiên. 
 b. To 100 ñim d liu ngu nhiên 
 >> [a,w] = PhanLop(100,2) 
 a = w = 
 1.2821 1.1631 
 0.5431 0.5111 
 Hình 6. Khi tăng ñim d liu lên 100 ñim ngu nhiên. 
146 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 Thc hin tăng s ñim ngu nhiên trên không gian 2 chiu. 
 c. Th nghim vi 200 ñim d liu ngu nhiên 
 >> [a,w] = PhanLop(200,2) 
 a = w = 
 5.3324 4.5695 
 2.6038 2.2495 
 Hình 7. Mô phng khi tăng h s ñim ngu nhiên 
 d. Th nghim vi100 ñim d liu ngu nhiên trên không gian ba chiu 
 >> [a,w] = PhanLop(100,3) 
 a = w = 
 1.0645 0.8317 
 3.9196 3.2198 
 3.6634 3.1436 
 e. Th nghim vi100 ñim d liu ngu nhiên trên không gian 5 chiu 
 >> [a,w] = PhanLop(100,5) 
 a = w = 
 1.1616 0.6263 
 4.9320 2.5409 
 0.8892 0.7258 
 5.2191 2.8727 
 3.5934 2.0685 
 Da trên các kt qu trên, có th ñưa ra mt s các nhn xét như sau: 
 − Khi s ñim ngu nhiên càng ít, có th thy ñưc 2 véc tơ phân chia 2 lp d liu ti 
ưu tìm ñưc có khong cách ln hơn rõ so vi 2 véc tơ ngu nhiên chn ban ñu. 
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 147 
 − Đim d liu ngu nhiên càng nhiu, 2 véc tơ chn ngu nhiên ban ñu rt gn so 
vi 2 véc tơ ti ưu tìm ñưc v sau. Điu này là do vi s ñim d liu nhiu thì có rt 
nhiu ñim ca phân lp thuc trên véc tơ phân cách, do ñó kh năng chp nhn ñưc ca 
thut toán là ít và rt gn nhau. 
5. KT LUN 
 − Bài báo ñã trình bày bài toán phân cm d liu và phương pháp Support Vector 
Machines ñưa bài toán phân cm d liu v bài toán ti ưu. Sau ñó dùng phương pháp 
Gradient ñ gii quyt bài toán ti ưu. 
 − Bài báo tp trung vào phương pháp Gradient và Gradient ci tin gii bài toán ti ưu 
phi tuyn không rng buc và áp dng nó vào bài toán phân cm d liu. Chương trình 
ñưc cài ñt trên MATLAB cho thy kt qu là rt tt. 
 TÀI LIU THAM KHO 
1. Tseng, P. Yun, A coordinate gradient descent method for linearly constrained smooth 
 optimization and support vector machines training , B 47, pp.179206. 
2. Tseng, P. Yun (2009), A coordinate gradient descent method for nonsmooth separable 
 minimization.Math , Program, B117, pp.387423. 
3. Nguyn Trng Toàn (2012), Giáo trình các phương pháp tính toán s, Hc vin K thut 
 Quân s. 
4. Nguyn Th Bch Kim (2014), Giáo trình các phương pháp ti ưu lý thuyt và thut toán , Nxb 
 Đi hc Bách khoa. 
 SOLVING THE OPTIMAL PROBLEM USING 
 THE GRADIENT METHOD AND THE APPLICATION 
 AbstractAbstract: The article analyzes the method to solve the nonlinear optimization problem 
 that is bound by the classical Gradient method. For classical gradient methods use the 
 defining method to take on the non constraint nonlinear problem , then 
 solve the non constraint optimal nonlinear problem. The article  also  provides  the 
 advanced gradient method for solving the optimal problem with a function Ψ 
 much more complex than the classical gradient method. The article  also presents the 
 problem of data stratification; apply Gradient method to put the data stratification 
 problem to optimization problem. 
 KeywordsKeywords: The gradient method, Advanced Gradient Method, Support vector machine, 
 defining, sample set.