Bài toán quy hoạch toàn phương

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

——————————

TRẦN THỊ NGỌC HUYỀN

BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG

Chuyên ngành: Toán Giải Tích

Mã số: 8460102

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2019

Công trình được hoàn thành tại

Trường Đại học Sư phạm - ĐHĐN

Người hướng dẫn khoa học: PGS.TS. HUỲNH THẾ PHÙNG

Phản biện 1:

PGS TS. Nguyễn Nhụy

Phản biện 2:

TS. Nguyễn Duy Thái Sơn

Luận văn sẽ được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ Khoa học họp tại Trường Đại học Sư phạm - ĐHĐN vào ngày

12 tháng 5 năm 2019.

Có thể tìm hiểu luận văn tại

- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lý do chọn đề tài

Quy hoạch toàn phương (QP) là bài toán quy hoạch phi tuyến đơn giản

nhất. Đó là bài toán tìm cực tiểu của một hàm bậc hai với các ràng buộc

tuyến tính. Nếu dạng toàn phương xác định dương hay nửa xác định dương

thì ta có bài toán quy hoạch toàn phương lồi, còn nếu dạng toàn phương

không xác định thì ta có bài toán quy hoạch toàn phương không lồi. Các

bài toán này quan trọng và rất được quan tâm nghiên cứu vì nhiều vấn đề

nảy sinh trong kinh tế, tài chính, công nghiệp và kỹ thuật có thể diễn đạt

như một bài toán quy hoạch toàn phương. Rất nhiều bài toán thực tế có

sử dụng lý thuyết thống kê đều đưa được về dạng một bài toán quy hoạch

toàn phương. Vì vậy phạm vi áp dụng của bài toán dạng này là rất rộng lớn,

bao trùm mọi lĩnh vực của đời sống như kinh tế, kĩ thuật, nông nghiệp, công

nghiệp, hoặc các ngành khoa học thực nghiệm như sinh học, hoá học. Mặc

dù đây là một bài toán khá kinh điển, các phương pháp giải nó vẫn thường

xuyên được cải tiến để nâng cao hiệu quả trong việc ứng dụng giải các bài

toán thực tế. Để cải tiến thuật toán người ta trước hết phải nghiên cứu các

vấn đề định tính như thiết lập lại các điều kiện tối ưu (cần và đủ), khảo

sát lý thuyết đối ngẫu trong quy hoạch toàn phương lồi và từ đó đề cập tới

những phương pháp giải bài toán quy hoạch toàn phương. Việc tìm hiểu chủ

đề này là rất cần thiết và hữu ích giúp hiểu và vận dụng các phương pháp

quy hoạch toàn phương vào các bài toán tối ưu khác. Vì vậy, được sự đồng

ý hướng dẫn của PGS.TS Huỳnh Thế Phùng, em chọn đề tài : “BÀI TOÁN

QUY HOẠCH TOÀN PHƯƠNG” cho luận văn thạc sĩ của mình.

2. Mục tiêu của đề tài

Nghiên cứu bài toán tối ưu, hạn chế trên quy hoạch toàn phương, xây

dựng các phương pháp giải dựa trên đặc điểm của bài toán.

3. Phương pháp nghiên cứu

2

Luận văn được nghiên cứu dựa trên các phương pháp:

- Nghiên cứu các tài liệu liên quan đến đề tài, bao gồm các tài liệu kinh

điển và các bài báo mới, tổng hợp và trình bày báo cáo tổng quan.

- Tham khảo, trao đổi với cán bộ hướng dẫn.

- Tham khảo một số bài báo đã đăng trên các tạp chí khoa học.

4. Đóng góp của đề tài

- Tổng hợp tài liệu để có một báo cáo tổng quan khá đầy đủ về Lý

Thuyết Xếp Hàng cùng các ứng dụng bằng số đối với các mô hình cụ thể.

- Bổ sung các ví dụ, hình ảnh và các chứng minh chi tiết.

5. Cấu trúc luận văn

Ngoài phần mở đầu và kết luận, tài liệu tham khảo, luận văn gồm ba

chương:

Chương 1: Bài toán tối ưu tổng quát . Chương này trình bày khái niệm,

các định lý tồn tại cơ bản, cũng như các điều kiện tối ưu cấp một , điều kiện

tối ưu cấp hai và bài toán đối ngẫu của bài toán tổng quát.

Chương 2: Bài toán quy hoạch toàn phương. Chương này là nội dung

chính của luận văn, trình bày các vấn đề liên quan đến bài toán quy hoạch

toàn phương.

Chương 3: Các phương pháp số giải bài toán quy hoạch toàn phương.

Chương này trình bày một số về các phương pháp số để giải bài toán quy

hoạch toàn phương với ràng buộc đẳng thức và ràng buộc bất đẳng thức.

CHƯƠNG 1

BÀI TOÁN TỐI ƯU TỔNG QUÁT

Chương này trình bày các khái niệm, định lý tồn tại cơ bản, các điều

kiện tối ưu và bài toán đối ngẫu của bài toán tổng quát.

1.1. Phát biểu bài toán, các định lý tồn tại cơ bản

Cho f : R

n → R là hàm nhận giá trị thực mở rộng, M là tập con của

R

n

. Ta xét bài toán

P(M; f) :







f(x) → min,

x ∈ M.

Đây là bài toán tìm cực tiểu hàm f giới hạn trên tập M. f được gọi là hàm

mục tiêu còn M được gọi là tập chấp nhận được và mỗi x ∈ M được gọi là

một điểm chấp nhận được. Một điểm x ∈ M được gọi là nghiệm (toàn cục)

của P(M; f) nếu

f(x) ≥ f(x); ∀x ∈ M,

được gọi là nghiệm địa phương nếu tồn tại ε > 0 sao cho

f(x) ≥ f(x); ∀x ∈ M ∩ B(x; ε).

Kí hiệu Sol(M; f) là tập tất cả các nghiệm và Solloc(M; f) là tập các

nghiệm địa phương của bài toán P(M; f).

Định lý 1.1.1. Trong bài toán quy hoạch lồi ta luôn luôn có

Sol(M; f) = Solloc(M; f)

và đó là tập lồi (có thể bằng rỗng).

Định lý 1.1.2. Trong bài toán quy hoạch lõm với hàm mục tiêu khác

hằng (trên M) ta có

Sol(M; f) ⊆ ∂M.

Định lý 1.1.3. Nếu M compact không rỗng và f nửa liên tục dưới thì

Sol(M; f) 6= ∅

4

1.2. Bài toán đối ngẫu

Thông thường, trong P(M; f), tập M được cho chi tiết hơn. Cụ thể,

M := {x ∈ X0 | g(x) ≤ 0; h(x) = 0}, (1.1)

với X0 ⊂ R

n

, g : R

n → R

m, h : R

n → R

k

. Lúc đó bài toán trở thành:

P(X0; g; h; f) :







f(x) −→ min

x ∈ X0,

g(x) ≤ 0,

h(x) = 0,

(1.2)

trong đó, tập chấp nhận được xác định bởi (1.1). Các ràng buộc x ∈ X0,

g(x) ≤ 0, h(x) = 0 lần lượt được gọi là ràng buộc tập, ràng buộc bất đẳng

thức và ràng buộc đẳng thức của bài toán. Rõ ràng, nếu f, g, h là các hàm

affine và X0 = R

n

thì P(X0; g, h, f) là bài toán qui hoạch tuyến tính; nếu f,

g là các hàm lồi, h là hàm affine và X0 lồi thì đó là bài toán qui hoạch lồi;

nếu X0 mở và g, h, f khả vi liên tục thì ta có bài toán qui hoạch trơn.

Bổ đề 1.2.1. Cho a ∈ R

m, b ∈ R

k

. Lúc đó,

[< a, x >≤ 0, ∀ x ∈ R

m

+] ⇔ [a ≤ 0].

[< b, y >≤ 0, ∀ y ∈ R

k

] ⇔ [b = 0].

[< a, x > + < b, y >≤ 0, ∀ (x, y) ∈ R

m

+ × R

k

] ⇔ [(a ≤ 0) và (b = 0)].

[< a, x >≤ α, ∀ x ∈ R

m] ⇔ [(a = 0) và (α ≥ 0)].

Bổ đề 1.2.2. Cho a ∈ R

m, b ∈ R

k

. Lúc đó,

sup

x∈Rm

+

< a, x >=







0, nếu a ≤ 0,

+∞, nếu tồn tại ai > 0.

sup

y∈Rk

< b, y >=







0, nếu b = 0,

+∞, nếu b 6= 0.

sup

(x,y)∈Rm

+ ×Rk

[< a, x > + < b, y >] =







0, nếu (a ≤ 0) và (b = 0),

+∞, nếu b 6= 0 hoặc tồn tại ai > 0.

Định lý 1.2.3 (Định lí đối ngẫu yếu). Ta luôn có bất đẳng thức sau:

inf

x∈X0

sup

(λ,µ)∈Rm

+ ×Rk

L(x, λ, µ) ≥ sup

(λ,µ)∈Rm

+ ×Rk

inf

x∈X0

L(x, λ, µ). (1.3)

Thật ra, định lí này là hệ quả của một định lí tổng quát hơn sau đây.

5

Định lý 1.2.4. Cho ánh xạ f : A × B →, với A và B là các tập hợp

khác rỗng tùy ý. Lúc đó

inf

x∈A

sup

y∈B

f(x, y) ≥ sup

y∈B

inf

x∈A

f(x, y).

Định lí 1.2.3 gợi ý chúng ta khảo sát bài toán

sup

(λ,µ)∈Rm

+ ×Rk

inf

x∈X0

L(x, λ, µ), (1.4)

mà được gọi là Bài toán đối ngẫu, trong khi (??) được gọi là Bài toán gốc.

1.3. Điều kiện tối ưu

Một bộ ba (¯x, λ, ¯ µ¯) ∈ X0 × R

m

+ × R

k được gọi là điểm yên ngựa của

hàm Lagrange L(x, λ, µ) (trong bài toán P(X0; g; h; f)) nếu

L(¯x, λ, µ) ≤ L(¯x, λ, ¯ µ¯) ≤ L(x, λ, ¯ µ¯); ∀(x, λ, µ) ∈ X0 × R

m

+ × R

k

. (1.5)

Tương tự, ta có khái niệm điểm yên ngựa cho hàm Lagrange của các bài toán

P(X0; g; f) và P(X0; h; f).

Định lý 1.3.1. Nếu (¯x, λ, ¯ µ¯) là một điểm yên ngựa của hàm L(¯x, λ, µ),

thì x¯ là nghiệm của bài toán P(X0; g; h; f).

Bài toán quy hoạch lồi P(X0; g; f) được gọi là thỏa mãn điều kiện Slater

nếu tồn tại xˆ ∈ X0 sao cho g(ˆx) < 0.

Định lý 1.3.2. Giả sử bài toán quy hoạch lồi P(X0; g; f) thỏa mãn điều

kiện Slater. Nếu x¯ là một nghiệm của bài toán thì tồn tại λ¯ ∈ R

m

+ sao cho

(¯x, λ¯) là một điểm yên ngựa, hơn nữa,

λ, g ¯ (¯x) = 0.

Bài toán quy hoạch lồi P(X0; g; h; f) được gọi là thỏa mãn điều kiện

Slater suy rộng nếu tồn tại xˆ ∈ X0 sao cho g(ˆx) < 0 và h(ˆx) = 0.

Định lý 1.3.3. Giả sử bài toán quy hoạch lồi P(X0; g, h; f) thỏa mãn

điều kiện Slater suy rộng. Lúc đó, nếu x¯ là một nghiệm của bài toán, thì tồn

tại một cặp (λ, ¯ µ¯) ∈ R

m

+ × R

k

sao cho (¯x, λ, µ) là điểm yên ngựa, hơn nữa,

< λ, g(¯x) >= 0.

Định lý 1.3.4. Nếu (¯x, λ, ¯ µ¯) là điểm yên ngựa của bài toán trơn P(X0; g; h; f)

thì nó cũng là điểm dừng. Khẳng định ngược lại cũng đúng với bài toán

trơn lồi.

Hệ quả 1.3.5. Nếu (¯x, λ, ¯ µ¯) là điểm dừng của bài toán trơn lồi P(X0; g; h; f)

thì x¯ là nghiệm của nó.

Hệ quả 1.3.6. Giả sử P(X0; g; f) là bài toán trơn, lồi, thỏa mãn điều

6

kiện Slater. Lúc đó, x¯ là nghiệm của bài toán khi và chỉ khi tồn tại λ ∈ R

m

+

sao cho (¯x, λ¯) là điểm dừng.

Hệ quả 1.3.7. Giả sử P(X0; g; h; f) là bài toán trơn, lồi, thỏa mãn

điều kiện Slater suy rộng. Lúc đó, x¯ là nghiệm của bài toán khi và chỉ khi

tồn tại một cặp (λ, ¯ µ¯) ∈ R

m

+ × R

k

sao cho (¯x, λ, ¯ µ¯) là điểm dừng.

Nhắc lại rằng nếu x¯ ∈ M thì ta kí hiệu I(¯x) = {i ∈ I | gi(¯x) = 0}.

Định lý 1.3.8. Nếu x¯ là nghiệm địa phương của bài toán trơn P(X0; g; f)

và tồn tại v0 ∈ X sao cho

< ∇gi(¯x), v0 >< 0, ∀ i ∈ I(¯x), (1.6)

thì tồn tại λ¯ ∈ R

m

+ sao cho (¯x, λ¯) là điểm dừng.

Hệ quả 1.3.9. Nếu x¯ là nghiệm địa phương của bài toán trơn P(X0; g; f)

và hệ {∇gi(¯x) | i ∈ I(¯x)} độc lập tuyến tính, thì tồn tại λ¯ ∈ R

m

+ sao cho

(¯x, λ¯) là điểm dừng.

Định lý 1.3.10. Nếu x¯ là nghiệm địa phương của bài toán trơn P(X0; h; f)

sao cho {∇h1(¯x), . . . , ∇hk(¯x)} độc lập tuyến tính, thì tồn tại µ¯ ∈ R

k

sao cho

(¯x, µ¯) là điểm dừng.

CHƯƠNG 2

BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG

2.1. Phát biểu bài toán, tính chất cơ bản

Trước hết, ta nhắc lại định nghĩa và một số khái niệm liên quan đến ma

trận.

Định nghĩa 2.1.1. Ma trận thực vuông, đối xứng G cấp n được gọi là xác

định dương nếu x

TGx > 0 với mọi x ∈ R

n \ {0} được gọi là nửa xác định

dương nếu x

TGx ≥ 0 với mọi x ∈ R

n

. Ma trận G được gọi là xác định âm

(nửa xác định âm) nếu −G là xác định dương (nửa xác định dương).

Mệnh đề 2.1.1. Mọi ma trận con chính của ma trận xác định dương

(nửa xác định dương) là ma trận xác định dương (nửa xác định dương).

Hệ quả 2.1.2. Các phần tử trên đường chéo chính của một ma trận

xác định dương (nửa xác định dương) là dương (không âm).

Định lý 2.1.3. Ma trận đối xứng G là xác định dương khi và chỉ khi

mọi định thức con chính của nó đều dương.

Mệnh đề 2.1.4. Nếu G nửa xác định dương và x

TGx = 0 thì Gx = 0.

Mệnh đề 2.1.5. Nếu ma trận G xác định dương thì ma trận nghịch

đảo G−1

tồn tại và xác định dương.

Mệnh đề 2.1.6. Nếu C là ma trận chữ nhật tùy ý thì CCT

và C

TC là

các ma trận nửa xác định dương (T là ký hiệu chuyển vị ma trận).

Mệnh đề 2.1.7. Ma trận đối xứng, lũy đẳng là ma trận nửa xác định

dương.

Định nghĩa 2.1.2. Hàm toàn phương là một hàm số có dạng

f(x) = 1

2

x

TGx + g

T x + α,

với

G =





G11 · · · G1n

.

.

.

.

.

.

.

.

.

Gn1 · · · Gnn





, g =





g1

.

.

.

gn





, α ∈ .

8

Lúc đó, f(x) có thể viết lại là:

f(x) = 1

2

X

n

i,j=1

Gijxixj +

X

n

i=1

gixi + α

Định nghĩa 2.1.3. Bài toán min{f(x) | x ∈ ∆} trong đó hàm mục tiêu f

là hàm toàn phương, tập ràng buộc ∆ ⊂ R

n

là tập lồi đa diện được gọi là

bài toán quy hoạch toàn phương (ký hiệu là (QP)).

Định lý 2.1.8. Cho hàm f(x) = 1

2

x

TGx + g

T x + α trong đó G là ma

trận đối xứng. Khi đó, nếu G là ma trận nửa xác định dương thì f là hàm

lồi.

2.2. Điều kiện tối ưu của bài toán (QP)

Định nghĩa 2.2.1. Cho điểm x

0 ∈ M. Véc-tơ d ∈ R

n được gọi là một hướng

chấp nhận được của M tại x

0 nếu tồn tại số t0 > 0 sao cho x

0 + td ∈ M,

với mọi t ∈ [0, t0]. Nghĩa là khi di chuyển đủ nhỏ từ x

0 dọc theo hướng d ta

không đi vượt ra ngoài miền chấp nhận được M.

Tập các hướng chấp nhận được của M tại x

0

tạo thành một nón lồi, gọi

là nón chấp nhận được của M tại x

0

. Kí hiệu S(x

0

).

Với mỗi x

0 ∈ M ta kí hiệu I(x

0

) là tập các chỉ số i ∈ I sao cho tại đó

ràng buộc xảy ra dấu đẳng thức chặt, nghĩa là:

I(x

0

) = {i ∈ I | a

T

i x

0 = bi}.

Mệnh đề 2.2.1. Với x

0 ∈ M, ta có

S(x

0

) = {d ∈ R

n

| a

T

i d = 0, ∀i ∈ E; a

T

i d ≥ 0, ∀ i ∈ I(x

0

)}.

Bổ đề 2.2.2. Nếu x

∗ ∈ M là một nghiệm địa phương của (QP) thì

d

T∇f(x

∗

) = d

T

(Gx∗ + g) ≥ 0, ∀d ∈ S(x

∗

).

Bổ đề 2.2.3 (Bổ đề Farkas). Cho trước véc tơ g ∈ R

n

và ma trận A

cấp n × m. Lúc đó

[∀x ∈ R

n

, AT x ≥ 0 ⇒ g

T x ≥ 0] ⇔ [∃u ∈ R

m

+, g = Au.]

Nếu ma trận A biểu diễn dưới dạng m véc-tơ cột

A = [a1, a2, . . . , am]; ai ∈ R

n

,

thì bổ đề trên có thể phát biểu lại như sau

[∀x ∈ R

n

, aT

i x ≥ 0, i = 1, m ⇒ g

T x ≥ 0] ⇔









∃u1, ..., um ≥ 0

g =

X

m

i=1

uiai









.

9

Định lý 2.2.4 (Điều kiện cần tối ưu). Giả sử x

∗

là nghiệm địa phương

của bài toán quy hoạch toàn phương. Khi đó tồn tại các nhân tử Lagrange

λ

∗

1

, . . . , λ∗

m thoả mãn:







Gx∗ + g =

X

m

i=1

λ

∗

i ai

,

a

T

i x

∗ = bi

, i ∈ E,

a

T

i x

∗ ≥ bi

, i ∈ I,

λ

∗

i

(a

T

i x

∗ − bi) = 0, i ∈ I,

λ

∗

i ≥ 0, i ∈ I.

(2.1)

Hơn nữa:

d

TGd ≥ 0, ∀d ∈ G(x

∗

, λ∗

),

với G(x

∗

, λ∗

) là tập hợp các vectơ d ∈ R

n

thỏa mãn:







d

T ai = 0, ∀i ∈ E,

d

T ai ≥ 0, ∀i ∈ I(x

∗

), λ∗

i = 0,

d

T ai = 0, ∀i ∈ I(x

∗

), λ∗

i > 0.

hay







d

T ai = 0, ∀i ∈ E,

d

T ai ≥ 0, ∀i ∈ I(x

∗

),

λ

∗

i d

T ai = 0, ∀i ∈ I(x

∗

).

Những điểm thỏa mãn điều kiện (2.1) được gọi là điểm KKT của (QP).

Định lý 2.2.5 (Điều kiện đủ tối ưu). Giả sử x

∗

là một điểm KKT

và λ

∗

là vectơ nhân tử Lagrange tương ứng. Nếu d

TGd > 0, với mọi 0 6=

d ∈ G(x

∗

, λ∗

) thì x

∗

là nghiệm địa phương chặt của bài toán quy hoạch toàn

phương (QP).

Định lý 2.2.6 (Điều kiện cần và đủ). Giả sử x

∗

là điểm chấp nhận

được của bài toán quy hoạch toàn phương. Khi đó x

∗

là một nghiệm cực tiểu

địa phương của (QP) khi và chỉ khi (x

∗

, λ∗

) thỏa mãn điều kiện (2.1) và:

d

TGd ≥ 0, ∀d ∈ G(x

∗

, λ∗

) (2.2)

Vậy tìm điểm KKT tương đương với tìm cặp (x

∗

, λ∗

) thỏa mãn (2.1).

10

2.3. Bài toán đối ngẫu

Với mỗi bài toán quy hoạch toàn phương lồi ta xét bài toán đối ngẫu

tương ứng. Ở đây ta quan tâm bài toán đối ngẫu sau:

Bài toán tổng quát:

P :







f(x) = g

T x +

1

2

x

TGx → min,

a

T

i x = bi

, i ∈ E,

a

T

i x ≥ bi

, i ∈ I.

⇒







hi(x) = bi − a

T

i x, i ∈ E,

gi(x) = bi − a

T

i x, i ∈ I.

Khi đó bài toán trở thành







1

2

x

TGx + g

T x → min,

bi − a

T

i x ≤ 0, i ∈ I,

bj − a

T

j x = 0, j ∈ E,

ta có hàm Lagrange

L(x, y) = 1

2

x

TGx + g

T x +

X

m

i=1

yi(bi − a

T

i x),

x ∈ R

n

, y ∈ R

m, yi ≥ 0, i ∈ I.

Bài toán đối ngẫu lúc đó là

sup

y∈Rm, yI≥0

inf

x∈Rn

L(x, y),

với giả thiết G là nửa xác định dương ta giải bài toán

inf

x∈Rn

L(x, y),

theo cách sau

∇xL(x, y) = Gx + g − A

T

y = 0,

giải ra ta được

Gx = A

T

y − g hay g = A

T

y − Gx,

thay vào hàm Lagrange ta có

L(x, y) = 1

2

x

TGx + g

T x + b

T

y − y

TAx

=

1

2

x

TGx + (A

T

y − Gx)

T x + b

T

y − y

TAx

= −

1

2

x

TGx + b

T

y.

11

Vì vậy bài toán đối ngẫu là bài toán







b

T

y −

1

2

x

TGx → max,

yi ≥ 0, i ∈ I,

Gx = AT

y − g.

Nếu G là xác định dương thì từ Gx = AT

y − g suy ra

x = G

−1

(A

T

y − g),

nên

b

T

y −

1

2

x

TGx = b

T

y −

1

2

(A

T

y − g)

TG

−1

(A

T

y − g).

Do đó ta có bài toán đối ngẫu là







b

T

y −

1

2

(AT

y − g)

TG−1

(AT

y − g) → max,

yi ≥ 0, i ∈ I.

CHƯƠNG 3

CÁC PHƯƠNG PHÁP SỐ GIẢI (QP)

3.1. Phương pháp khử biến số

Trong mục này ta xét phương pháp giải bài toán (QP) với ràng buộc

đẳng thức:

f(x) = g

T x +

1

2

x

TGx −→ min, (3.1)

A

T x = b, (3.2)

trong đó g ∈ R

n

, b ∈ R

m , A ∈ R

n×m, G ∈ R

n×n và G là đối xứng. Không

giảm tổng quát, ta giả thiết m ≤ n và rank(A) = m nghĩa là bằng số cột

của A.

Mục này trình bày phương pháp khử biến biến số. Giả sử có phân hoạch

như sau:

x =





xB

xN



 , A =





AB

AN



 , g =





gB

gN



 , G =





GBB GBN

GNB GNN



 .

Trong đó xB ∈ R

m, xN ∈ R

n−m, và AB là khả nghịch. Theo cách phân hoạch

này ràng buộc AT x = b có thể viết lại thành

A

T

BxB + A

T

N xN = b,

do tồn tại A

−1

B

nên

xB = (A

−1

B

)

T

(b − A

T

N xN ) = (A

−1

B

)

T

b − (A

−1

B

)

TA

T

N xN . (3.3)

Thay vào hàm mục tiêu của (QP) ta nhận được bài toán (không ràng buộc)

tương đương

min

xN ∈Rn−m

1

2

x

T

N GdN xN + gcN

T

xN + bc. (3.4)

Trong đó

gbN = gN − AN A

−1

B

gB + [GNB − AN A

−1

B GBB](A

−1

B

)

T

b,

GbN = GNN − GNB(A

−1

B

)

TA

T

N − AN A

−1

B GBN + AN A

−1

B GBB(A

−1

B

)

TA

T

N ,

bc =

1

2

b

TA

−1

B GBBA

−T

B

b + g

T

BA

−T

B

b.

Nghiệm x

∗

N của (3.4) thỏa mãn điều kiện cần tối ưu : GbN x

∗

N + gbN = 0