Có những bài toán không lồi trong biến gốc của chúng, nhưng trở thành lồi khi ta đo mọi đại lượng theo thang logarit. Quy hoạch hình học (geometric program, GP) là họ bài toán quan trọng nhất thuộc loại này. Nó xuất hiện tự nhiên trong thiết kế kỹ thuật, nơi các đại lượng như kích thước, công suất, thời gian trễ thường dương và liên hệ với nhau qua những tích và lũy thừa.

Bài giảng này thiết lập nền tảng lý thuyết cho GP: Khái niệm monomial, posynomial, phép đổi biến logarit $y=\log x$ để chuyển hóa GP về bài toán lồi chuẩn tắc, cùng hai ứng dụng thực tế tiêu biểu là thiết kế tối ưu kích thước và cân bằng .

1. Monomial và posynomial

Một hàm $f:{\mathbb{R}}_{++}^n\to \mathbb{R}$ có dạng

$$f(x)=c{x}_1^{a_1}{x}_2^{a_2}\cdots x_n^{a_n},c>0,a_i\in \mathbb{R},$$

được gọi là một monomial. Số mũ có thể là số thực bất kỳ, kể cả phân số hay số âm, nhưng hệ số $c$ phải dương. Đây là điểm khác với khái niệm "đơn thức" trong đại số cổ điển, nơi số mũ phải là số nguyên không âm. Cần đặc biệt chú ý quy ước mở rộng này. Một tổng hữu hạn các monomial,

$$f(x)=\sum _{k=1}^K{c}_k{x}_1^{a_{1k}}{x}_2^{a_{2k}}\cdots x_n^{a_{nk}},c_k>0,$$

được gọi là một posynomial. Chẳng hạn $3x_1^{0.5}{x}_2^{-1}$ là monomial, $x_1+2x_1{x}_2+x_2^{-1}$ là posynomial, còn $x_1-x_2$ không phải posynomial vì có hệ số âm.

Các phép toán khép kín là điều làm hai họ hàm này rất linh hoạt trong ứng dụng. Tổng, tích và tích với hằng số dương của các posynomial là posynomial. Tích và thương của các monomial là monomial. Chia một posynomial cho một monomial được một posynomial. Chẳng hạn $(x_1+x_2{)}^2=x_1^2+2x_1{x}_2+x_2^2$ là posynomial, và $(x_1+x_2)/(x_1{x}_2)=x_2^{-1}+x_1^{-1}$ cũng vậy.

2. Quy hoạch hình học

Một quy hoạch hình học ở dạng chuẩn là bài toán

$$\begin{array}{rl}& \text{minimize}{f}_0(x)\\ & \text{subject to}{f}_i(x)\le 1,i=1,\dots ,m,\\ & \phantom{\text{subject to}}{h}_i(x)=1,i=1,\dots ,p,\end{array}$$

với $f_0,\dots ,f_m$ là posynomial và $h_1,\dots ,h_p$ là monomial. Miền của bài toán là ${\mathbb{R}}_{++}^n$, nên điều kiện $x\succ 0$ luôn được ngầm hiểu.

Nhiều ràng buộc trông khác dạng chuẩn vẫn đưa về được nhờ các phép toán khép kín. Ràng buộc "posynomial $\le$ monomial", $f(x)\le h(x)$, viết thành $f(x)/h(x)\le 1$. Ràng buộc "monomial $=$ monomial" viết thành thương của chúng bằng 1. Cực đại một monomial tương đương cực tiểu nghịch đảo của nó, cũng là một monomial. Xét ví dụ biến đổi: Bài toán cực đại $x/y$ với $2\le x\le 3$, $x^2+3y/z\le \sqrt{y}$ và $x/y=z^2$ đưa được về GP dạng chuẩn

$$\begin{array}{rl}& \text{minimize}{x}^{-1}y\\ & \text{subject to}2x^{-1}\le 1,\frac{1}{3}x\le 1,\\ & \phantom{\text{subject to}}{x}^2{y}^{-1/2}+3y^{1/2}{z}^{-1}\le 1,\\ & \phantom{\text{subject to}}x{y}^{-1}{z}^{-2}=1.\end{array}$$

3. Đổi sang thang logarit

GP không lồi trong biến $x$: Một posynomial như $\sqrt{x_1}+\sqrt{x_2}$ là hàm lõm, và tập $\{x:\sqrt{x_1}+\sqrt{x_2}\le 2\}$ không lồi. Đổi biến $y_i=\log x_i$, tức $x_i=e^{y_i}$. Một monomial trở thành

$$c{e}^{a_1{y}_1}\cdots e^{a_n{y}_n}=e^{a^{T}y+b},b=\log c,$$

hàm mũ của một hàm affine, và một posynomial trở thành tổng các hàm mũ của những hàm affine, $\sum _k{e}^{a_k^{T}y+b_k}$. Bước thứ hai là lấy logarit của hàm mục tiêu và của mỗi ràng buộc, một phép biến đổi tăng ngặt nên giữ nguyên tập nghiệm và giữ đúng chiều bất đẳng thức. Ta được GP dạng lồi

$$\begin{array}{rl}& \text{minimize}\log \sum _{k=1}^{K_0}{e}^{a_{0k}^{T}y+b_{0k}}\\ & \text{subject to}\log \sum _{k=1}^{K_i}{e}^{a_{ik}^{T}y+b_{ik}}\le 0,i=1,\dots ,m,\\ & \phantom{\text{subject to}}{g}_i^{T}y+h_i=0,i=1,\dots ,p.\end{array}$$

Mỗi hàm $\log \sum _k{e}^{a_k^{T}y+b_k}$ là hàm log-sum-exp hợp với một ánh xạ affine, nên lồi. Mỗi ràng buộc monomial $h_i(x)=1$ trở thành $\log h_i=0$, một phương trình affine. Vậy GP dạng lồi là một bài toán lồi ở dạng chuẩn. Đáng chú ý là phép biến đổi không cần tính toán gì: Dữ liệu của hai dạng hoàn toàn như nhau, chỉ cách viết hàm là khác.

Về hình học, một đoạn thẳng trong biến $y$ ứng với đường $x(\theta )=p^{1-\theta }{q}^{\theta }$ trong biến $x$, tính theo từng thành phần. Trung điểm của đoạn ấy là trung bình nhân $\sqrt{pq}$ chứ không phải trung bình cộng. Tính lồi trong biến $\log x$ vì thế có nghĩa là: Tập chứa trung bình nhân của hai điểm bất kỳ của nó.

Đổi sang thang logarit

Bên trái là tập trong biến gốc x, bên phải là cùng tập ấy sau phép đổi biến y = log x. Đoạn thẳng nối hai điểm bên phải ứng với đường trung bình nhân bên trái.

tập (hoặc biên của tập)đoạn thẳng trong biến xđoạn thẳng trong biến log x

Tập√x₁ + √x₂ ≤ 2x₁x₂ = 1áp phích: wh ≥ 600, (w + 4)(h + 6) ≤ 864 Hiện đường trung bình nhân

Hai điểm p = (0.16, 2.56) và q = (2.56, 0.16) đều thuộc tập.

Trung điểm cộng (1.36, 1.36) không thuộc tập: trong biến x, tập không lồi.

Trung bình nhân (0.64, 0.64) thuộc tập. Nó là trung điểm của đoạn thẳng trong biến log x, nơi tập là lồi.

Gợi ý thao tác

1. Với tập √x₁ + √x₂ ≤ 2, vì sao đoạn thẳng đỏ đi ra ngoài tập, còn đường xanh thì không?
2. Với x₁x₂ = 1, tập là một đường cong trong biến x. Trong biến log x nó trở thành gì, và vì sao ràng buộc đẳng thức monomial là "affine trá hình"?
3. Với bài toán áp phích, so sánh hình dạng tập mức của hàm mục tiêu ở hai bên. Bên nào cho thấy bài toán là lồi?

Nếu mọi posynomial trong GP chỉ có một số hạng, tức đều là monomial, thì sau khi lấy logarit, mọi hàm đều affine và GP dạng lồi là một LP. Vì vậy có thể xem GP là một mở rộng của quy hoạch tuyến tính.

4. Ví dụ: Thiết kế một tấm áp phích

Ví dụ thiết kế: Một tấm áp phích cần phần chữ có diện tích ít nhất $600{\text{cm}}^2$, với lề trái và lề phải mỗi bên 2 cm, lề trên và lề dưới mỗi bên 3 cm. Gọi $w,h$ là chiều rộng và chiều cao của phần chữ. Ta muốn tối ưu hóa kích thước để tốn ít diện tích giấy nhất:

$$\text{minimize}(w+4)(h+6)\text{subject to}wh\ge 600.$$

Khai triển hàm mục tiêu cho posynomial $wh+6w+4h+24$, và ràng buộc viết thành $600w^{-1}{h}^{-1}\le 1$, nên đây là một GP. Trong biến $(w,h)$, hàm mục tiêu không lồi, vì Hessian của $(w+4)(h+6)$ là $\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$, có một trị riêng âm. Trong biến $u=\log w$, $v=\log h$, ràng buộc trở thành nửa mặt phẳng $u+v\ge \log 600$, và hàm mục tiêu là log-sum-exp của bốn hàm affine.

Nghiệm có thể tìm tay. Tại nghiệm, ràng buộc chặt, nên $h=600/w$, và hàm mục tiêu thành $600+6w+\frac{2400}{w}+24$, nhỏ nhất khi $6w=\frac{2400}{w}$, tức $w=20$ và $h=30$. Diện tích giấy là $24\times 36=864{\text{cm}}^2$. Kết quả có một cách đọc đẹp: Tỉ lệ $h/w=30/20$ đúng bằng tỉ lệ giữa lề trên dưới và lề trái phải, $3/2$. Nếu chọn phần chữ hình vuông cạnh $\sqrt{600}\approx 24.5$, ta tốn khoảng $869{\text{cm}}^2$, nhiều hơn khoảng 0.6%.

5. Ví dụ: Cân bằng một ma trận

Xét bài toán điều hòa thang đo (diagonal scaling): Cho ma trận $M\in {\mathbb{R}}^{n\times n}$, ta muốn đổi thang các tọa độ bằng một ma trận chéo $D=\mathrm{diag}(d)$ với $d\succ 0$, sao cho ma trận mới $DM{D}^{-1}$ "nhỏ", đo bằng bình phương chuẩn Frobenius

$$\parallel DM{D}^{-1}{\parallel }_F^2=\sum _{i,j}{M}_{ij}^2\frac{d_i^2}{d_j^2}.$$

Đây là một posynomial theo $d$, nên bài toán là một GP không ràng buộc, với các số mũ chỉ là 0, 2 và $-2$. Phép đổi thang này làm các phần tử của có độ lớn gần nhau hơn, một điều có lợi cho nhiều thuật toán số.

Ví dụ: Xét cụ thể $M=\left[\begin{array}{cc}1& 4\\ 1& 1\end{array}\right]$. Các phần tử chéo không đổi khi đổi thang, nên chỉ cần cực tiểu $16r^2+r^{-2}$ theo $r=d_1/d_2$. Nghiệm là $r^2=\frac{1}{4}$, tức $r=\frac{1}{2}$, và ma trận mới là $\left[\begin{array}{cc}1& 2\\ 2& 1\end{array}\right]$, với hai phần tử ngoài đường chéo bằng nhau. Bình phương chuẩn Frobenius giảm từ 19 xuống 10.

Một hướng phát triển sâu sắc là bài toán cực tiểu hóa bán kính phổ của dương: Trị riêng Perron–Frobenius có thể được cực tiểu hóa bằng GP khi các phần tử ma trận là posynomial của các thiết kế. Mô hình này được áp dụng trực tiếp để tối ưu hóa sự suy giảm của quần thể sinh học hoặc phân bổ liều lượng điều trị trong dược động học.

6. Những câu hỏi để đào sâu

Câu 1. Giả sử ta cho phép hệ số âm, chẳng hạn ràng buộc $x_1-x_2\le 1$. Phép đổi biến logarit còn dùng được không, và điều kiện $c>0$ thật ra đóng vai trò gì?

Xem lời giải thích

Bước lấy logarit cần các hàm dương. Một monomial với $c>0$ dương trên ${\mathbb{R}}_{++}^n$, nên lấy log được, và kết quả là affine. Với hệ số âm, tổng $x_1-x_2$ có thể âm hoặc bằng 0, và không có cách viết nó thành log-sum-exp. Những bài toán cho phép hệ số âm được gọi là signomial program, và nói chung không lồi theo bất kỳ phép đổi biến đơn giản nào. Hệ số dương không phải chi tiết kỹ thuật: Chính nó làm mỗi số hạng trở thành một hàm mũ của hàm affine, và tổng các hàm như thế mới cho log-sum-exp.

Câu 2. Một posynomial có lồi theo biến gốc $x$ không?

Xem lời giải thích

Có khi có, có khi không. Hàm $x^{-1}$ trên $x>0$ lồi, hàm $x^2$ lồi, nhưng $\sqrt{x}$ lõm và $x_1{x}_2$ không lồi cũng không lõm. Điều chắc chắn là sau phép đổi biến $x=e^y$, mọi posynomial đều trở thành tổng các hàm mũ của hàm affine, nên lồi theo $y$. Đó là lý do người ta nói GP "lồi trong biến logarit" chứ không lồi trong biến gốc. Mô phỏng với tập $\sqrt{x_1}+\sqrt{x_2}\le 2$ cho thấy một posynomial lõm có thể tạo ra một tập không lồi theo $x$.

Câu 3. Trong ví dụ áp phích, vì sao tỉ lệ cạnh của phần chữ tối ưu lại đúng bằng tỉ lệ lề? Hãy chứng minh cho lề tổng quát $a$ (mỗi bên trái, phải) và $b$ (mỗi bên trên, dưới), diện tích chữ $A$.

Xem lời giải thích

Với ràng buộc chặt $h=A/w$, hàm mục tiêu $(w+2a)(A/w+2b)$ bằng $A+2bw+\frac{2aA}{w}+4ab$. Phần phụ thuộc $w$ là $2bw+2aA/w$, nhỏ nhất khi $2bw=2aA/w$, tức $w^2=aA/b$. Khi đó $h=A/w$ cho $h^2=bA/a$, và $h/w=b/a$. Diện tích giấy là $A+4\sqrt{abA}+4ab=(\sqrt{A}+2\sqrt{ab}{)}^2$. Trực giác: Tại nghiệm, việc dời phần diện tích chữ từ chiều này sang chiều kia phải cân bằng giữa lượng giấy lề tiết kiệm được ở hai chiều, nên mỗi chiều của phần chữ tỉ lệ với lề của chiều ấy.

Câu 4. GP có biến ngầm điều kiện $x\succ 0$. Nếu một đại lượng thiết kế có thể bằng 0, chẳng hạn số lượng một linh kiện tùy chọn, thì làm thế nào?

Xem lời giải thích

Không đưa trực tiếp được vào GP, vì $\log 0$ không xác định và các số hạng với số mũ âm sẽ nổ ra vô hạn. Có hai cách thường gặp. Cách thứ nhất là đặt một cận dưới dương nhỏ, $x\ge ϵ$, rồi kiểm tra xem nghiệm có dồn về cận ấy không. Nếu có, giá trị 0 có lẽ là tốt nhất. Cách thứ hai là xét riêng hai trường hợp có và không có đại lượng ấy, mỗi trường hợp là một GP. Bản thân việc lựa chọn "có hay không" là một quyết định rời rạc, nằm ngoài phạm vi của tối ưu lồi.

7. Bài tập tự luyện

Bài tập 1: Nhận diện

Hàm nào sau đây là monomial, posynomial, hay không phải cả hai, trên ${\mathbb{R}}_{++}^2$? (a) $0.5x_1^{-2}{x}_2^{3/4}$. (b) $(x_1+1{)}^3$. (c) $x_1^2-x_1{x}_2$. (d) ${\displaystyle \frac{x_1+x_2^2}{3x_1{x}_2}}$. (e) $\sqrt{x_1^2+x_2^2}$.

Lời giải

(a) Monomial, hệ số $0.5>0$, số mũ thực tùy ý được phép. (b) Posynomial, vì khai triển cho $x_1^3+3x_1^2+3x_1+1$, toàn hệ số dương, trong đó số hạng 1 là monomial với mọi số mũ bằng 0. (c) Không, vì có hệ số âm. (d) Posynomial, vì là posynomial chia monomial: $\frac{1}{3}{x}_2^{-1}+\frac{1}{3}{x}_1^{-1}{x}_2$. (e) Không phải posynomial, vì căn của một tổng không viết được thành tổng hữu hạn các monomial. Tuy vậy ràng buộc $\sqrt{x_1^2+x_2^2}\le t$ tương đương $t^{-2}{x}_1^2+t^{-2}{x}_2^2\le 1$, một ràng buộc posynomial.

Bài tập 2: Viết và giải một GP

Viết bài toán cực tiểu $x+y^2$ với $xy\ge 4$ và $x\le 3y$ thành GP dạng chuẩn và GP dạng lồi, rồi tìm nghiệm.

Gợi ý

Ở nghiệm, ràng buộc $xy\ge 4$ phải chặt, vì nếu không ta có thể giảm $x$.

Lời giải

Dạng chuẩn: Cực tiểu $x+y^2$ với $4x^{-1}{y}^{-1}\le 1$ và $\frac{1}{3}x{y}^{-1}\le 1$. Với $u=\log x$, $v=\log y$, dạng lồi là cực tiểu $\log (e^u+e^{2v})$ với $\log 4-u-v\le 0$ và $u-v-\log 3\le 0$. Để giải, dùng ràng buộc chặt $x=4/y$, cực tiểu $\frac{4}{y}+y^2$: Đạo hàm $-\frac{4}{y^2}+2y=0$ cho $y^3=2$, tức $y=2^{1/3}\approx 1.260$ và $x=4/y\approx 3.175$. Kiểm tra $x\le 3y\approx 3.780$, thỏa và không chặt. Giá trị tối ưu là $x+y^2\approx 4.762$.

Bài tập 3: Cân bằng ma trận

Cân bằng $M=\left[\begin{array}{cc}2& 9\\ 1& 3\end{array}\right]$ theo chuẩn Frobenius như ở mục 5. Bình phương chuẩn Frobenius giảm từ bao nhiêu xuống bao nhiêu?

Lời giải

Cực tiểu $81r^2+r^{-2}$ theo $r=d_1/d_2$: Nghiệm $r^2=\frac{1}{9}$, tức $r=\frac{1}{3}$. Hai phần tử ngoài đường chéo trở thành $9\cdot \frac{1}{3}=3$ và $1\cdot 3=3$, bằng nhau. Bình phương chuẩn Frobenius giảm từ $4+81+1+9=95$ xuống $4+9+9+9=31$.

Tóm tắt

Monomial là tích các lũy thừa thực của biến với hệ số dương, posynomial là tổng các monomial. Quy hoạch hình học cực tiểu một posynomial với các ràng buộc posynomial $\le 1$ và monomial $=1$, trên miền $x\succ 0$. GP nói chung không lồi trong biến gốc, nhưng đổi biến $y=\log x$ rồi lấy logarit các hàm biến nó thành một bài toán lồi, với hàm log-sum-exp của các hàm affine và các ràng buộc đẳng thức affine. Trong biến gốc, tính lồi này có nghĩa là tập khả thi chứa trung bình nhân của hai điểm bất kỳ của nó.

GP xuất hiện trong thiết kế, như bài toán áp phích có nghiệm $w=20$, $h=30$ với tỉ lệ cạnh bằng tỉ lệ lề, và trong tính toán, như bài toán cân bằng theo chuẩn Frobenius. Khi mọi posynomial chỉ có một số hạng, GP dạng lồi là một LP.

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press.