Tóm tắt Luận văn Thạc sĩ Kỹ thuật điều khiển và tự động hóa: Ứng dụng phương pháp Aladin để giải bài toán tối ưu trong đánh giá tính bền vững của mạng truyền thông

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

14
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn gồm 4 chương chính: Chương 1: Nghiên cứu tổng quan về hệ thống đa đối tượng và mạng truyền thông; Chương 2: Phương pháp ALADIN (Augmented Lagrangian based Alternating Direction Inexact Newton); Chương 3 : Ứng dụng phương pháp ALADIN (Augmented Lagrangian based Alternating Direction Inexact Newton) trong giải bài toán tối ưu; Chương 4 : Kết quả mô phỏng và nhận xét.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận văn Thạc sĩ Kỹ thuật điều khiển và tự động hóa: Ứng dụng phương pháp Aladin để giải bài toán tối ưu trong đánh giá tính bền vững của mạng truyền thông

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA TRẦN VĂN HOÀN ỨNG DỤNG PHƯƠNG PHÁP ALADIN ĐỂ GIẢI BÀI TOÁN TỐI ƯU TRONG ĐÁNH GIÁ TÍNH BỀN VỮNG CỦA MẠNG TRUYỀN THÔNG Chuyên ngành: KỸ THUẬT ĐIỀU KHIỂN VÀ TỰ ĐỘNG HÓA Mã số: 8520216 LUẬN VĂN THẠC SĨ KỸ THUẬT ĐIỀU KHIỂN VÀ TỰ ĐỘNG HÓA Đà Nẵng - Năm 2020
Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA Người hướng dẫn khoa học: TS. Trần Thị Minh Dung Phản biện 1: TS. Nguyễn Lê Hòa Phản biện 2: TS. Hà Xuân Vinh Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ Kỹ thuật họp tại trường Đại học Bách Khoa vào ngày 18 tháng 1 năm 2020 Có thể tìm hiểu luận văn tại:  Trung tâm thông tin - Học liệu, Trường ĐHBK – Đại học Đà Nẵng  Thư viện Khoa Điện, Trường ĐHBK – Đại học Đà Nẵng
1 MỞ ĐẦU 1. Đặt vấn đề Ngày nay với tốc độ phát triển nhanh chóng của khoa học công nghệ, con người ngày càng nghiên cứu và chế tạo ra nhiều hệ thống có độ phức tạp và chính xác cao, với rất nhiều đối tượng cùng tham gia để hoàn thành những nhiệm vụ khó, nguy hiểm với tốc độ nhanh và độ chính xác cao. Để điều khiển được một hệ đa đối tượng đạt hiệu quả tối đa thì ngoài tốc độ điều khiển nhanh, chính xác ra thì độ mạnh, hay là khả năng chịu đựng của nó khi hệ thống ngẫu nhiên xảy ra một vài sự cố là rất cần thiết. Độ ổn định và tính bền vững của một mạng điều khiển trong hệ thống là rất quan trọng. Nó thể hiện tính an toàn, hiệu quả kinh tế trong quá trình hoạt động, sản xuất. Ngoài ra sự hiểu biết về tính bền vững của mạng điều khiển có thể bảo vệ và cải thiện hiệu suất của mạng một cách hiệu quả. Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại. Đặc biệt trong khoảng vài chục năm trở lại đây, cùng với sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học, Lý thuyết đồ thị càng được quan tâm đến nhiều hơn. Đặc biệt là các thuật toán trên đồ thị đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như: Mạng máy tính, Lý thuyết mã, Tối ưu hoá, Kinh tế học v.v... Đồng thuận (consensus) là dựa trên thông tin địa phương và tương tác giữa các đối tượng (ở đây là các nút) [6], làm thế nào tất cả các đối tượng có thể đạt được một thỏa thuận. Đó là thiết kế một giao thức mạng dựa trên thông tin địa phương thu được của đối tượng để sau đó có một thỏa thuận chung. Các vấn đề về sự đồng thuận của MAS (multi agent systems) đã nhận được sự quan tâm rất lớn từ các cộng đồng
2 nghiên cứu khác nhau do các ứng dụng rộng rãi của họ trong nhiều lĩnh vực bao gồm toán học, vật lý, sinh học, khoa học máy tính, khoa học xã hội. Do đó để đánh giá tính bền vững của một mạng điều khiển tác giả sử dụng thuật toán đồng thuận để kiểm tra sự đồng thuận của các đối tượng (được mô hình hóa bằng đồ thị) trong thời gian hữu hạn và ứng dụng phương pháp ALADIN (Augmented Lagrangian based Alternating Direction Inexact Newton) [1] để đánh giá tính bền vững. 2. Mục tiêu và nhiệm vụ nghiên cứu a) Mục tiêu tổng quan Đề xuất ứng dụng phương pháp ALADIN (Augmented Lagrangian based Alternating Direction Inexact Newton) trong việc đánh giá tính bền vững mạng truyền thông của hệ thống đa đối tượng. Xây dựng được hàm mục tiêu, điều kiện buộc và thuật toán trong tính toán đánh giá bền vững của mạng điều khiển. Ứng dụng phương pháp ALADIN để đánh giá mạng truyền thông. b) Mục tiêu cụ thể Tính toán đưa ra hàm mục tiêu, điều kiện ràng buộc và thuật toán, đưa ra kết quả mô phỏng đánh giá tính bền vững của một vài mô hình bằng Matlab. 3. Đối tượng và phạm vi nghiên cứu a) Đối tượng nghiên cứu Đối tượng nghiên cứu là hệ thống điều khiển đa đối dựa trên cơ sở lý thuyết đồ thị. Coi các đối tượng là các nút trong đồ thị. Đề tài chỉ thực hiện nghiên cứu trong phạm vi các đối tượng là các nút trên cơ sở lý thuyết đồ thị và mô phỏng trên Matlab, không thực hiện trên mô hình đối tượng thực tế
3 Để đơn giản, Luận văn dựa trên cơ sở lý thuyết đồ thị coi các đối tượng là các nút (các đỉnh) trong đồ thị, được kết nối với nhau nhờ các cạnh. b) Phạm vi nghiên cứu Nghiên cứu lý thuyết: nghiên cứu lý thuyết thuật toán đồng thuận, lý thuyết đồ thị và xây dụng hàm mục tiêu, thuật toán đồng thuận trong hệ đa đối tượng. Nghiên cứu ứng dụng phương pháp ALADIN trong đánh giá tính bền vững của mạng điều khiển. Nghiên cứu thực tế: khi đã có đầy đủ cơ sở lý thuyết, tác giả sẽ tiến hành mô phỏng trên Matlab để kiểm tra và đánh giá tốc độ của thuật toán, tính bền vững của một số mô hình. 4. Ý nghĩa khoa học và thực tiễn của đề tài a) Ý nghĩa khoa học Ngoài các phương pháp tối ưu kinh điển như: Lagrange, QP, SQP, Gradient, Newton-Raphson, Gaus – Newton…đề tài sẽ mang đến thêm một hướng đi bằng cách ứng dụng phương pháp ALADIN để giải bài toán tối ưu. b) Ý nghĩa thực tiễn Đề tài nhằm xây dựng và đánh giá tính bền vững của mạng điều khiển hệ đa đối tượng bằng cách đồng thuận các đối tượng trong mạng với nhau trong một thời gian hữu hạn, dùng phương pháp ALADIN đánh giá tính bền vững của mạng truyền thông. Nhằm đưa ra các giải pháp hoặc cải thiện hệ thống phù hợp, thích nghi với từng chức năng, nhiệm vụ.
4 5. Cấu trúc luận văn Ngoài phần mở đầu và phận kết luận, Luận văn gồm 04 chương chính Chương 1 : Nghiên cứu tổng quan về hệ thống đa đối tượng và mạng truyền thông • Nghiên cứu về hệ đa đối tượng và lý thuyết đồ thị. • Nghiên cứu về thuật toán đồng thuận, tính toán đưa ra hàm mục tiêu và điều kiện ràng buộc. Chương 2 : Phương pháp ALADIN (Augmented Lagrangian based Alternating Direction Inexact Newton) • Giới thiệu về phương pháp ALADIN, các thuật toán, hàm mục tiêu và điều kiện ràng buộc. • Tính hội tụ toàn cục của ALADIN. Chương 3 : Ứng dụng phương pháp ALADIN (Augmented Lagrangian based Alternating Direction Inexact Newton) trong giải bài toán tối ưu • Ứng dụng thuật toán ALADIN để tính toán hàm mục tiêu và điều kiện ràng buộc của hệ đa đối tượng. • Viết thuật toán cho hệ đa đối tượng dựa theo phương pháp ALADIN. Chương 4 : Kết quả mô phỏng và nhận xét • Sử dụng Matlab để mô phỏng, đưa ra kết quả. • Đánh giá tốc độ của thuật toán và tính bền vững của một số mô hình.
5 CHƯƠNG 1 : NGHIÊN CỨU TỔNG QUAN VỀ HỆ THỐNG ĐA ĐỐI TƯỢNG VÀ MẠNG TRUYỀN THÔNG 1.1. Giới thiệu về hệ thống đa đối tượng (MAS) 1.2. Hệ thống mạng truyền thông 1.3. Điều khiển hợp tác 1.4. Thuật toán đồng thuận 1.4.1. Giao thức đồng thuận 1.4.2. Vấn đề đồng thuận trong thời gian tuyến tính 1.4.3. Thiết kế ma trận đồng thuận 1.4.4. Thiết kế ma trận trọng số 1.4.4.1. Trọng số có bậc lớn nhất 1.4.4.2. Trọng số có cạnh là hằng số 1.4.4.3. Trọng số Metropolis 1.4.5. Tối ưu hóa 1.5. Lý thuyết đồ thị 1.5.1. Định nghĩa 1.5.2. Biểu diễn đồ thị 1.5.3. Đồ thị có hướng và đồ thị vô hướng 1.5.4. Đơn đồ thị và đa đồ thị 1.5.5. Tính kết nối của đồ thị 1.5.6. Đặc tính đồ thị đại số 1.5.7. Quang phổ ma trận Laplacian 1.5.8. Các loại đồ thị tiêu chuẩn 1.6. Tính bền vững của mạng truyền thông 1.6.1. Độ liên kết của nút 1.6.2. Độ kết nối đại số 1.6.3. Số spanning tree
6 1.6.4. Độ phản kháng của đồ thị 1.7. Tính bền vững của mạng lưới theo hình thức phân tán 1.7.1. Tính toán các giá trị riêng riêng biệt của ma trận Laplacian 1.7.2. Tính toán bội số của mỗi giá trị riêng riêng biệt của ma trận Laplacian
7 CHƯƠNG 2 : PHƯƠNG PHÁP AUGMENTED LAGRANGIAN BASED ALTERNATING DIRECTION INEXACT NEWTON (ALADIN) 2.1. Giới thiệu Tối ưu hóa là quá trình tìm ra các biến được thiết kế để đạt đến mục tiêu mong muốn, đồng thời cũng thỏa mãn các ràng buộc kèm theo. Các vấn đề tối ưu hóa phi tuyến quy mô lớn phát sinh trong nhiều ứng dụng khác nhau, từ tối ưu hóa kinh tế theo tài nguyên dùng chung thông qua thuật toán học thống kê cho mạng lưới thông minh đến điều khiển tối ưu phi tuyến phân tán cho phương trình vi phân thông thường và phương trình vi phân từng phần. May mắn là, mặc dù các vấn đề tối ưu hóa phát sinh từ các trường hợp này có thể có quy mô lớn nhưng chúng thường được cấu trúc và có một mục tiêu riêng biệt để vấn đề tối ưu hóa [1] có thể được viết dưới dạng. N  N A i xi = b  i =1 min  f i ( xi ) st.  (2.1) hi ( xi )  0, i  1,...., N  x i =1  Các thuật toán phân tán hiện có cho vấn đề (2.1) thường cho rằng các hàm fi và hi là lồi. Ví dụ một trong những thuật toán tối ưu lồi phân tán cơ bản và lâu đời nhất là phương pháp phân tích kép [23]. Ở đây ý tưởng chính là giải quyết vấn đề tăng kép có liên quan đến vấn đề (2.1) bằng cách sử dụng phương pháp gradient, trong khi chính hàm mục tiêu kép được đánh giá theo cách phân tán. Nhiều bài báo và tài liệu đánh giá gần đây về phương pháp phân tích kép cho các vấn đề tối ưu lồi có thể tìm thấy trong [9, 10]. Trong những năm gần đây, phân tích kép đã được sử dụng thường xuyên trong điều khiển tối ưu phân tán và các thuật toán điều khiển dự báo mô hình. Một loạt các thuật toán
8 sử dụng thông tin độ dốc làm cơ sở để có được một thuật toán phân tán đầy đủ [4, 24, 25, 26, 27]. Các phương pháp này thường yêu cầu số lần lặp lớn để đạt được độ chính xác trung bình trong giải pháp. Nếu các hàm fi và hi là không lồi thì có rất ít cách tiếp cận. Các phân tích kép không được áp dụng trong trường hợp này, vì chúng có thể có một khoảng cách đối ngẫu. Tương tự, mặc dù các phát triển thành công và các đặc tính thuận lợi của ADMM đối với các vấn đề tối ưu lồi được nêu ở trên, ADMM nói chung không thể áp dụng nếu các hàm fi không phải là lồi. Bài viết này sẽ giới thiệu một phương pháp xen kẽ dựa trên Lagrangian newton không chính xác (ALADIN). Phương pháp này thiết kế nhằm giải quyết các vấn đề tối ưu hóa không tiềm năng của mẫu (2.1). 2.2. Thuật toán tối ưu hóa hàm không lồi Phần này đề giới thiệu một thuật toán mới để giải quyết các bài toán tối ưu hóa có dạng (2.1). Thuật toán 1. ALADIN Đầu vào: cho trước các giá trị ban đầu xi  ,  và  0 n m Lặp lại: Chọn một tham số hiệu chỉnh   0 đủ lớn và một ma trận tỉ lệ bán xác định dương i  nx + và giải với mọi i 1,..., N  cho các vấn đề tối ưu hóa tách rời  min fi ( yi ) +  T Ai yi + || yi − xi ||2 i st hi ( yi )  0 | i  (2.2) yi 2 Để tối ưu hóa cục bộ hoặc toàn cục Nếu || i N Ai yi − b ||1  và  || i ( yi − xi ) ||1  , chấm dứt với x* = y
9 chọn ràng buộc xấp xỉ Jacobian Ci  Ci* của các ma trận Ci* được xác định bởi   (hi ( x)) j |x= yi if (hi ( yi )) j = 0 Ci*, j =  x 0   o.w i 1,..., N   j  1,..., nh  Tính toán độ dốc đã thay đổi gi = fi ( yi ) + (C* − Ci )T i i và chọn các Hessian xấp xỉ đối xứng  H i   2 f i ( yi ) +  iT hi ( yi )  Chọn một tham số hiệu chỉnh đủ lớn   0 và giải phương trình i=1 1 yiT Hi yi + giT yi  + T s +  || s ||2 N QP min y, x 2 2 2  N A ( y + y ) = b + s | st    i =1 i i i QP (2.3) Ci yi = 0, i 1,..., N   Chạy thuật toán 2 để tìm những kích thước bước a1 , a2 , a3  + hoặc một cách khác là đặt a1 = a2 = a3 = 1 để chạy ALADIN mà không cần đảm bảo hội tụ toàn cục. Xác định: x + = x + a1 ( y − x) + a2y và  + =  + a3 (QP −  ) Cập nhật các lần lặp x  x+ và   + và tiếp tục với bước 1. 2.3. Điểm tương đồng và khác biệt so với SQP và phương pháp lagrangian tăng cường
10 2.4. Tính hội tụ của thuật toán Thuật toán 2. Bài toán tối ưu hóa toàn cục Khởi tạo: Chọn một số  đủ lớn 0     và 0     cũng như cố định 0 1 Các bước toàn cục hóa: (a) Đặt a1 = a2 = a3 = 1 . Nếu lần lặp x + từ bước 5 của thuật toán 1 thỏa mãn  N   N   ( x) −  ( x + )       +  Ai xi − b 2 yi − xi  (2.9)  i =1  2 i  i =1   1 Với L1 là hàm hiệu chỉnh +   max 0, (hi ( xi )) j  N N  ( x) =  fi ( xi ) +   Ax −b i i i =1 i =1 1 i, j Quay lại a1 = a2 = a3 = 1 (b) Nếu bước đầy đủ không được chấp nhân, đặt a1 = 1 và a2 = a3 = 0 sao cho x+ = y . Nếu điều kiện (2.9) được thỏa mãn, quay lại a1 = 1 và a2 = a3 = 0 (c) Nếu cả (a) và (b) đều không có kết quả, đặt a1 = a2 = 0 sao cho x + = x . Tiếp theo, xác định tối đa toàn cục a3*  (0,1] của hàm V ( x,  + a3 (QP −  )) với V biểu thị mục tiêu tối ưu của vấn đề kép tách rời
11 N    T V ( x ,  ) = min   f i ( yi ) +  T Ai yi + yi − xi − b 2 i i =1  2  y (d) (2.10) s. t . h i ( yi )  0, i  1,..., N  Quay lại a1 = a2 = 0 và a3 = a3 * Đầu ra: thông số tìm kiếm đường thẳng a1 , a2 , a3 cần thiết trong bước 5 của thuật toán 1. 2.5. Phân tích hội tụ cục bộ
12 CHƯƠNG 3 ỨNG DỤNG PHƯƠNG PHÁP ALADIN TRONG ĐÁNH GIÁ TÍNH BỀN VỮNG CỦA MẠNG TRUYỀN THÔNG 3.1. Tính bền vững của mạng truyền thông Để đảm bảo an toàn và hiệu quả tối đa trong vận hành khai thác các hệ thống phức tạp. Tùy theo mục đích và nhu cầu mà các hệ thống cần đảm bảo độ bền vững khác nhau. Một hệ đa đối tượng để đảm bảo an toàn, ổn định và kinh tế cần phải có sự chia sẻ thông tin hoặc nhiệm vụ để hoàn thành một mục tiêu chung, hoặc chúng phải đồng thuận với mục đích là đạt đến thống nhất tại một giá trị chung. Để đánh giá tính bền vững của mạng truyền thông của hệ đa đối tượng trong Luận văn này tác giả sử dụng thuật toán đồng thuận và phương pháp ALADIN tính toán giá trị để đánh giá tính bền vững. N 1 1 N R=  1i  j N R ij = N i =2 i (L) ; =  i (L) N i=2 Như đã nói trong chương 1, để tính được thông số này ta phải tìm thông tin phổ của ma trận Laplacian sp(L) của mạng điều khiển đó. Phương pháp này có ưu điểm là sử dụng được cho cả mạng kết nối và không kết nối. Trong ma trận phổ sp(L) thì giá trị riêng nhỏ thứ 2 2 là thông số quyết định đến khả năng hoạt động cũng như tính bền vững tùy theo vai trò độ kết nối đồ thị biểu diễn cho mạng điều khiển đó. Một đồ thị G(E, V) biểu diễn cho một mạng truyền thông có N nút và E cạnh, ta có phổ của ma trận L là sp(L) = 1 , 2 ,..., N  . Ta có trạng thái ban đầu của các nút là x(0) = [x1 (0), x2 (0),..., xN (0)]T và x(k) = [x1 (k), x2 (k),..., xN (k)] từ đó ta có phương trình cập nhật đồng thuận.
13 x(k + 1) = (I N −  L)x(k) = (I N −  L)k x(0) 11T x= x(0) N Ta có hàm mục tiêu: 1 h αk  min N 1 ,k =1,2,...,h  j ( j,k − i,k )2 2 k =1 iV Ni s.t. x(h) = x Hoặc tương đương với: 1 h αT Lα 2 k k min N 1 αk ,k =1,2,...,h k =1 s.t. x(h) = x Ta sử dụng phương pháp ALADIN để giải bài toán tối ưu hóa không lồi. Vì vậy, ta viết lại hàm mục tiêu như sau: 1 h αT Lα 2 k k min N 1 αk ,k =1,2,...,h k =1 (3.1)  h  Lα k = 0 s.t.  k =1  h(α ) = x(h) − x = 0  k 3.2. Ứng dụng phương pháp ALADIN Thuật toán 3 Cho trước các giá trị ban đầu: • αk  N , k = 1,2,..., h, λ  N , k = LT L + 0.01I,  , , Hệ số Lagrange: β N , k  N , λ QP  N
14 Lặp lại: Lặp lại cho đến khi điều kiện hội tụ của tuật toán được thỏa mãn. Chọn   0 và giải với mọi k = 1, 2, …, h cho vấn đề tối ưu hóa NLP (nonlinear programming) sau để tìm y: 1 T  y k Ly k + λ T Ly k + (y k − α k 2 min N 1 k yk  , k =1,2,...,h 2 2 (3.2) s.t. h( y k ) = 0  Điều kiện hội tụ của thuật toán:  Ly k  và   k (y k − α k )  thì nghiệm tối ưu là h Nếu k =1 α* = y Xác định các ma trận Jacobian, gradient và Hessian: Gradient: g k = f k (y k ) +h(y )T  = Ly k − diag (Lx k −1 ) k với  h =   k −1 = Wk k và Wk = I − y k L Ck = h(y )T = −diag (Lx k −1 ) ih=k +1 Wi Hk = L Cho   0 , giải vấn đề tối ưu hóa QP sau để tìm y và λ QP h 1   2 y k  N h min1 ,s N , k =1,2,...,h   2 yTk Ly k + gkT y k  + λT s + 2 s k =1   (3.3)   L(y k + y k ) = s λ QP  k =1 h s.t.   Ck y k = 0, k = 1,2,..., h  Tính step size a1, a2 , a3 dùng để update giá trị của α  N h Chọn 0    inf (giá trị lớn nhất), 0  k  inf và 0   1
15 • Trường hợp 1: Cho a1 = a2 = a3 = 1 ta có z = y k + y k Tính giá trị hàm: h αT Lαk +   Lαk h  ( ) = k + k h( ) 1 k =1 k =1 1 Tính giá trị hàm  (z) Kiểm tra nếu:  h   ( ) h ( ) − (z)    k =1  Lαk 2 y k − αk +  2 k  k =1 1 thỏa mãn thì ta có α+ = z Trường hợp 2: a1 =1, a2 = a3 = 0, z = y nếu:  h   ( ) h ( ) − (z)    k =1  Lαk 2 y k − αk +  2 k  k =1 1 Trường hơp 3: a1 = a2 = 0, a3 tìm từ bài toán tối ưu sau: Tìm a3  (0,1] với: h 1   2 y Ly k + λ T Ly k + (y k − α k T 2 max min k k  (3.4) a3 yk  k =1 2  s.t. h( y k ) = 0 Update: α + = α + a1 (y − α ) + a2 y (3.5) λ + = λ + a3 (λ QP − λ ) (3.6) + Outputs: α = α *
16 CHƯƠNG 4 : MÔ PHỎNG VÀ NHẬN XÉT 4.1. Kết quả mô phỏng Trong phần này một ví dụ sẽ được thực hiện để kiểm tra độ hiệu quả của phương pháp đề xuất trong việc đánh giá độ mạnh của mạng truyền thông (thông qua R). Để đánh giá độ mạnh của mạng chúng ta sẽ lấy một mạng có bốn nút làm ví dụ về sự thay đổi giá trị của độ bền vững khi cấu trúc của mạng bị thay đổi. 4.1.1. Trường hợp 1 Hình 4.1 Cấu trúc của mạng lưới bốn nút toàn diện Ta có trạng thái ban đầu của các nút là: x(0) = [x1 (0), x2 (0), x3 , x4 (0)]T x(k) = [x1 (k), x2 (k), x3 , x4 (k)]T Từ đó ta có phương trình cập nhật đồng thuận. 11T x(k+ 1) = (I4 −  L)x(k) x= x(0) 4
17 Ta có hàm mục tiêu 1 h αk  min N 1 ,k =1,2,...,h  j ( j,k − i,k )2 2 k =1 iV Ni s.t. x(h) = x 1 h αT Lα 2 k k Hoặc tương đương với: α  min N 1,k =1,2,...,h k k =1 s.t. x(h) = x Ta sử dụng phương pháp ALADIN để giải bài toán tối ưu không lồi. Vì vậy, ta viết lại hàm mục tiêu như sau: 1 h αT Lα 2 k k min N 1 αk ,k =1,2,...,h k =1  h  Lα k = 0 s.t.  k =1  h(α ) = x(h) − x = 0  k Chúng ta hãy xem xét đồ thị được mô tả trong hình. Sử dụng thuật toán ALADIN ta tính được các giá trị alpha: 0.5822 0.4592 0.2503 0.5824 0.4594 0.2500 α 0.5823 0.4594 0.2500 0.5824 0.4594 0.2500
18 Với giá trị X là: 0.6864 0.6521 0.6677 0.3156 0.9626 0.6677 X 1.3380 0.1064 0.6677 0.3309 0.9498 0.6677 Giá trị trung bình của x = x(h) = 0,6677 Áp dụng thuật toán tính các giá trị riêng riêng biệt ở phần 1.7.1 ta tìm được S2 của ma trận Laplacian: 0.2500 0 0 0.2500 0 0 S2 =   0.2500 0 0   0.2500 0 0 Ta tìm được alpha cần tính là 0.25, áp dụng thuật toán tính bội số của giá trị riêng ở phần 1.7.2 ta tính được m=3. Từ đó tính ra  (L) = (0,4,4,4) .