Trong mục này, chúng ta trình bày các điều kiện đủ cho bài toán tối ưu dạng toàn phương (QP) đã được thiết lập trong [1].
Đặt
f(x) = 1
2xTAx+bTx, gk(x) = 1
2xTAkx+bTkx+ck, k ∈ {1,2, . . . , m}, Với mỗi x ∈ Rn và λ = (λ1, λ2, . . . , λm)T ∈ Rm+, ta xác định
LQP (x, λ) =f (x) +
m
X
i=1
λkgk(x),
χei =
0 nếu xi = ui = vi
−1 nếu xi = ui < vi
1 nếu xi = vi > ui (∇LQP (x, λ))i nếu xi ∈ (ui, vi).
Định lý 2.2. Xét bài toán tối ưu (QP) và x là một điểm chấp nhận được của nó. Giả sử rằng tồn tại λ = (λ1, λ2, . . . , λm)T ∈ Rm+, ma trận đường chéo H = diag(α1, α2, . . . , αn) sao cho λk(1
2xTAkx+bTkx+ck) = 0, k ∈ {1,2, . . . , m}, (A+
m
P
k=1
λkAk)−H 0, và với mỗi i ∈ {1,2, . . . , n}
1
2αi+(vi −ui) +χei(∇LQP (x, λ))i ≤0, (2.4) ở đó α+i = max{0,−αi}. Khi đó x là một nghiệm cực tiểu toàn cục của (QP).
Chứng minh. Vì f(x) = 1
2xTAx+bTx, gk(x) = 1
2xTAkx+bTkx+ck, k ∈ {1,2, . . . , m}, nên ∇2LQP (x, λ) =A+
m
P
i=1
λkAk.
Khi đó khẳng định của định lý được suy ra trực tiếp từ Định lý 1.2.
Lấy x là một điểm chấp nhận được của (QP). Khi đó với mỗi i ∈ {1,2, . . . , n} ta xác định χei, qi(x, λ) và H(x, λ) như trong (1.19),(1.22) và (1.23). Do đó ta có các kết quả sau:
Hệ quả 2.2. Xét bài toán tối ưu (QP) và x là một điểm chấp nhận được của nó. Nếu tồn tại λ = (λ1, λ2, . . . , λm)T ∈ Rm+ sao cho
i) λk(1
2xTAkx+ bTkx+ck) = 0, k ∈ {1,2, . . . , m}, ii) với mỗi i ∈ {1,2, . . . , n}, χei(∇LQP (x, λ))i ≤ 0, iii) Với mọi x ∈ D, (A+
m
P
k=1
λkAk)−H(x, λ) 0 thì x là một nghiệm cực tiểu toàn cục của (QP).
Ví dụ 2.2. Xét bài toán tối ưu toàn phương (E2) min
x∈R2
−1
4x21 − 1
4x22 + 5
4x1x2 −x1 −x2
với ràng buộc
−x1 −x2 ≤ 0 1
3 ≤x1 ≤1
−1 ≤ x2 ≤ 1.
Ta đã chỉ ra trong Ví dụ 2.1, điểm x = (1,−1) đã thỏa mãn điều kiện cần (2.1). Sau đây, ta sẽ kiểm tra điều kiện đủ trong Hệ quả 2.2 tại x.
Đặt
f(x) =−1
4x21 − 1
4x22 + 5
4x1x2 −x1 −x2
g1(x) =−x1 −x2. Ta có
∇f(x) =
−1
2x1 + 5
4x2 −1,−1
2x2 + 5
4x1 −1 T
A = ∇2f (x) =
−12 54
5
4 −12
Do đó,
∇f (x) =
−11 4 ,3
4 T
g1(x) = 0, χe1 = 1, χe2 = −1.
Lấy λ = λ1 = 0. Ta có λ1g1(x) = 0 và (i) được thỏa mãn.
Mặt khác
LQP (x, λ) = f (x) +λ1g1(x) và ∇LQP (x, λ) = ∇f (x) =
−11 4 ,3
4 T
. Suy ra
χe1(∇LQP (x, λ))1 = 1ã
−11 4
< 0 χe2(∇LQP (x, λ))2 = (−1)ã
3 4
< 0.
Ta có ii) được thỏa mãn.
Ta dễ dàng tính được rằng
q1(x, λ) = 2χe1(∇LQP (x, λ))1 v1 −u1
= 2.1.
−11 4
2 3
= −33 4 ,
q2(x, λ) = 2χe2(∇LQP (x, λ))2 v2 −u2
=
2.(−1).
3 4
2 = −3
4. Nên
H (x, λ) = diag
−33 4 ,−3
4
,
A−H(x, λ) =
−12 54
5 −1
−
−334 0 0 −3
=
31 4
5 4 5 1
0,
và iii) được thỏa mãn.
Vậy các điều kiện đủ tối ưu toàn cục trong Hệ quả 2.2 được thỏa mãn tại x = (1,−1) và do đó x = (1,−1) phải là một nghiệm cực tiểu toàn cục của (E2).
Bây giờ ta sẽ xét bài toán tối ưu dạng toàn phương trong trường hợp đặc biệt gk(x) ≡ 0. Xét bài toán
(QP1) min
x∈Rn
1
2xTAx+bTx với ràng buộc x ∈ D :=
n
Y
i=1
[ui, vi].
ở đó ui, vi ∈ R, ui < vi, i∈ {1,2, . . . , n}, A = (aij)ni,j=1 ∈ Sn, b ∈ Rn. Với mỗi i ∈ {1,2, . . . , n}, đặt
χei =
0 nếu xi = ui = vi
−1 nếu xi = ui < vi
1 nếu xi = vi > ui (Ax+b)i nếu xi ∈ (ui, vi).
(2.5)
Chú ý rằng trong các kết quả được phát biểu cho bài toán (QP1) dưới đây thì χei được xác định bởi (2.5).
Hệ quả 2.3. Xét bài toán tối ưu toàn phương (QP1) và x ∈ D. Nếu tồn tại một ma trận đường chéo H = diag(α1, α2, . . . , αn) sao cho A−H 0 và với mỗi i ∈ {1,2, . . . , n},
1
2α+i (vi−ui) +χei(Ax+b)i ≤ 0
thì x là một nghiệm cực tiểu toàn cục của (QP1).
Chứng minh. Khẳng định suy ra trực tiếp từ Định lý 1.3.
Cho bài toán tối ưu toàn phương (QP1). Kí hiệu các giá trị riêng của ma trận A bởi δ1, δ2, ..., δn. Đặt
à= min{δ1, δ2, ..., δn} (2.6) Hệ quả 2.4. Xét bài toán tối ưu toàn phương (QP1) và x ∈ D. Nếu với mỗi i ∈ {1,2, . . . , n},
1
2à+(vi −ui) +χei(Ax+b)i ≤ 0 (2.7) thì x là một nghiệm cực tiểu toàn cục của (QP1).
Chứng minh. Đặt H = àI. Ta dễ dàng kiểm tra được rằng A−H 0.
Do đó khẳng định được suy ra ngay từ Hệ quả 2.3.
Cho bài toán tối ưu toàn phương (QP1). Với mỗi i ∈ {1,2, . . . , n} ta xác định
βi = aii −
n
X
j=1,j6=i
|aij|, (2.8)
βi+ = max{0,−βi}. (2.9) Hệ quả 2.5. Xét bài toán tối ưu toàn phương (QP1) và x ∈ D. Nếu với mỗi i ∈ {1,2, . . . , n},
1
2βi+(vi −ui) + χei(Ax+ b)i ≤0 (2.10)
Chứng minh. Đặt H = diag(β1, β2, ..., βn). Ta có A−H 0. Từ Hệ quả 2.3 suy ra x là một nghiệm của bài toán (QP1).
Một số điều kiện cần và đủ tối ưu toàn cục cho các bài toán tối ưu với hàm mục tiêu và hàm ràng buộc là các hàm khả vi liên tục bậc 2. Cụ thể:
- Các điều kiện cần cũng như điều kiện đủ cho lớp hàm C2 trên ràng buộc hộp và các ràng buộc bất đẳng thức có các hàm thuộc lớp C2.
- Áp dụng các kết quả đạt được cho một lớp bài toán tối ưu có cấu trúc đặc thù với hàm mục tiêu và các hàm ràng buộc là các hàm toàn phương.
Một số vấn đề cần được tiếp tục nghiên cứu:
- Loại bỏ giả thiết về tính dương đối với các phần tử trên đường chéo của ma trận Hessian.
- Thiết lập các điều kiện cần và đủ cực trị cho lớp bài toán trên khi không có ràng buộc hộp.
[A] Tài liệu tiếng Việt
[1] Nguyễn Quang Huy, Khuất Văn Ninh (2008), Điều kiện tối ưu toàn cục cho bài toán cực tiểu toàn phương với ràng buộc bất đẳng thức toàn phương, Tạp chí Khoa học trường ĐHSP Hà Nội 2, số 2, 71–84.
[2] Lê Dũng Mưu, Nhập môn các phương pháp tối ưu, NXB Khoa học và Kĩ thuật, Hà Nội, 1998.
[3] Hoàng Xuân Phú, Lý thuyết các bài toán cực trị, Viện Toán học, Hà Nội, 1997.
[B] Tài liệu tiếng Anh
[4] I. G. Akrotirianakis and C. A. Floudas (2004),Computational ex- perience with a new class of convex underestimators: Box con- strains NLP Problems, J. Global Optim, 29, 249–264.
[5] M. S. Bazaraa, H. D. Sherrali, C. M. Shetty (2006), Nonlinear Programming: Theory and Algorihms, Wiley-Interscience, New York.
[6] A.Beck and M. Teboull (2000), Global optimality conditionfor quadratic optimization problems with binary constrains, SIAM J.
Optim, 11, 179–188.
[7] A. Ben-Tal and A.Nemirovski (2000), Lectures on Modern Con- vex Optimization: Analysic, Algorithms and engineering Applica- tions, SIAM-MPS, Philadelphia.
[8] B. D. Craven (1995),Control and Optimization, Chapman and Hall, London.
[9] G. Dahl (2000), A note on diagonally matrices, Linear Algebra Appl, 317,217–224.
[10] P. De Angelis, P. Pardalos and G. Toraldo (1997),Quadratic pro- gramming with box constrains. Nonconvex Optim, Appl, Kluwer Academic Publishers, Dordrecht, 18, 73–93.
[11] C. A. Floudas (2000), Deterministic global optimization: Theory, methods and application, Kluwer Academic Publishers.
[12] C. A. Floudas and P. M. Pardalos (2000), Optimization incom- putational chemistry and molecular biology: Local and global ap- proaches, Kluwer Academic Publisher.
[13] C. A. Floudas and V. Visweswaran (1995), Quadatic optimiza- tion, Handbook of Global Optimization, Kluwer Academic Pub- lisher, The Netherlands, 217–269.
[14] M. A. Hanson (1991), On sufficiency of Kuhn-Tucker conditions, J. Math. Anal, Appl, 80, 545–550.
[15] M. A. Hanson (1994), A generalization of the Kuhn-Tucker suf- ficiency conditions, J. Math. Anal, Appl, 184, 146–155.
[16] J. B. Hiriart-Urruty (2001),Global Optimization Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constrains, J. Global Optim, 21, 445–455.
[17] J. B. Hiriart-Urruty (1998), Conditions for Global Optimality 2, J. Global Optim, 13, 349–367.
[18] R. Horst, P. Pardalos (1994), Handbook of Global Optimization, Kluwer Academic Publishers.
[19] R. Horst, P. Pardalos, N. V. Thoai (2000),Introduction to Global Optimization, Second edition, Nonconvex Optimization and its Application, 48, Kluwer Academic Publishers, Dordrecht.
[20] R. Horst, H. Tuy (1993), Global Optimization, Deterministic ap- proaches, Second edition, Springer-Verlag, Berlin.
[21] N. Q. Huy, V. Jeyakumar and G. M. Lee (2006), Sufficient global optimality conditions for multi extremal smooth minimiza- tion problems with bounds and linear matric inequality constrains, ANZIAM J, 47(4), 439–450.
[22] V. Jeyakumar and N. Q. Huy (2008), Global minimization of dif- ference of quadraticand convex fuctions over box or binary con- strains, Optimization Letters, 2, 223–238.
[23] V. Jeyakumar and N. Q. Huy (2007), Global optimality of quadratic minimization over symetric polytopes, Optimization, 56, 633–640.
[24] V. Jeyakumar and N. Q. Huy (2010),Global optimality conditions for nonliear programming problems with bounds via quadratic un- derestimators, Optimization, 59, 161–173.
[25] V. Jeyakumar, B. Mond (1992), On generalized convex mathmat- ical programming, J. Aust. Math. Soc. Ser. B, 34, 43–53.
[26] V. Jeyakumar, A. M. Rubinov ang Z. Y. Wu (2006), Sufficient global optimality conditions for non-convex quadratic minimiza- tion problems with box constraints, J. Global Optim, 36, 471–481.
[27] V. Jeyakumar, A. M. Rubinov ang Z. Y. Wu (2007),Non-convex quadratic minimization with quadratic constrains: Global optimal- ity conditions, Math. Prog., Ser.A, 110, 521–541.
[28] V. Jeyakumar, S. Srisatkunrajah and N. Q. Huy (2007), Kuhn- Tucker sufficiency for global minimum of multi-extremal math- matical progamming problems, J. Math. Anal. Appl., 361–370.