Pengantar optimasi yang kuat [... dan daftar belanja kecil yang saya lupa ...]

Bagaimana menentukan berapa banyak orang yang perlu dipekerjakan untuk pemenuhan yang baru, dengan apa sebenarnya untuk mengisinya dan di mana menempatkan produk tertentu? Semakin besar bisnis, semakin besar ketidakpastian dan semakin mahal kesalahannya. Mengalahkan kekacauan dan memilih solusi terbaik adalah salah satu tugas tim ilmu data. Dan karena matematika adalah dasar dari analisis data, kita akan mulai dengan itu.

Dalam posting ini, kami akan mempertimbangkan masalah optimisasi dengan ketidakpastian data dan perkiraannya oleh masalah cembung deterministik. Ini adalah salah satu trik utama dalam optimasi yang kuat - suatu teknik yang memungkinkan Anda untuk mengatasi tugas-tugas optimasi yang terlalu sensitif terhadap perubahan dalam input data.

Masalah sensitivitas sangat penting. Untuk tugas yang kualitas solusinya sangat lemah tergantung pada perubahan data, lebih mudah untuk menggunakan optimasi stokastik biasa. Namun, dalam tugas dengan sensitivitas tinggi, pendekatan ini akan memberikan hasil yang buruk. Ada banyak tugas seperti itu di bidang keuangan, manajemen rantai pasokan, desain dan banyak bidang lainnya.

Dan ya, ini adalah contoh dari pos di mana kompleksitas tumbuh secara eksponensial (sudah sampah) ...

Apa artinya "menyelesaikan" masalah pengoptimalan?

Mari kita mulai dengan pengingat singkat.

Tugas optimasi secara umum terlihat seperti ini:

$$

$$\ min_ {x \ dalam R ^ n} f (x) \\ s.t. \\ x \ dalam X$$

Di sini $$$f (x)$ disebut fungsi objektif, dan $$$X$ - set yang valid.

Dengan memecahkan masalah pengoptimalan, kami maksud seperti itu $$$x ^ * \ dalam X$ yang dieksekusi:

$$

$$f (x) - f (x ^ *) \ geq 0, \ quad \ forall x \ in X$$

Ini adalah konsep standar untuk menyelesaikan masalah optimisasi tanpa ketidakpastian.

Apakah masalah pengoptimalan dengan ketidakpastian?

Saatnya bertanya-tanya tentang asal usul fungsi $$$f (x)$ dan keterbatasan $$$X$ .

Sangat berguna untuk dibagikan

• logika struktural dari masalah (dengan kata lain, fungsi apa yang digunakan),
• keterbatasan teknis (tidak tergantung pada logika atau data manusia),
• parameter yang dievaluasi dari data.

Sebagai contoh, seorang pengusaha datang kepada kami dan menunjukkan masalah pemrograman linier:

$$

$$\ min_ {x \ dalam R ^ 2} 2.16 x_1 + 3.7 x_2 \\ s.t. \\ 0.973 x_1 + 2.619 x_2 \ leq 3.32 \\ x_1 \ geq 0, x_2 \ geq 0$$

Anda melihat tugas ini untuk pertama kalinya. Seorang pria juga (mungkin tidak, tetapi dalam jaket biru semuanya sangat abstrak!). Anda tidak tahu arti variabel. Tetapi bahkan sekarang, dengan kepercayaan besar, kita dapat mengatakan bahwa:

1. Kemungkinan besar tugasnya linier, karena seseorang telah memutuskan demikian. Linearitas adalah struktur yang dipilih seseorang.
2. Keterbatasan $$$x_1 \ geq 0, x_2 \ geq 0$ bersifat teknis. Artinya, mereka berasal dari "fisika" dan bukan dari data (misalnya, penjualan tidak boleh negatif).
3. Koefisien spesifik $$$\ {0,973, 2,619, 3,32 \}$ dalam membatasi $$$0,973 x_1 + 2,619 x_2 \ leq 3,32$ dalam contoh kami dievaluasi dari data. Artinya, pada awalnya seseorang mengatakan bahwa variabel $$$x_1$ terkait dengan variabel $$$x_2$ , maka dikatakan bahwa hubungannya linear, dan akhirnya, koefisien dalam persamaan kopling diperkirakan dari data. Hal yang sama berlaku untuk peluang. $$$\ {2.16, 3.7 \}$ dalam fungsi obyektif.

Ketika kita berbicara tentang tugas dengan ketidakpastian, kita menargetkan secara tepat ketidakpastian dalam parameter yang diestimasi dari data. Kami tidak menyentuh batasan teknis atau pilihan awal dari struktur masalah.

Kembali ke kisah kita. Kami memiliki masalah linier, seseorang memperkirakan koefisien di dalamnya entah bagaimana. Jika kita benar tentang sifat koefisien dalam fungsi, maka sebenarnya kita diminta untuk memecahkan masalah untuk satu skenario pengembangan peristiwa (contoh spesifik dari masalah).

Terkadang ini cukup bagi kita, dan kita hanya menyelesaikannya.

Namun, terkadang menyelesaikan masalah untuk satu skenario adalah ide yang bodoh (misalnya, jika solusinya sangat sensitif terhadap variasi data).

Apa yang harus dilakukan dalam kasus ini, dan bagaimana memodelkan ketidakpastian dalam data?

Pertama, perhatikan bahwa ketidakpastian data selalu dapat ditransfer dari fungsi tujuan ke kendala atau sebaliknya. Cara melakukan ini, lihat di bawah luka.

Stochastic, online, optimisasi yang kuat dan daftar produk

Kita dapat memiliki banyak skenario ketidakpastian, serta opsi untuk apa yang harus dilakukan dengannya. Kami menggambarkan beberapa pendekatan standar dengan contoh sederhana.

Saya tidak tahu bagaimana situasinya dengan pembaca yang terhormat, tetapi di sini saya menikah (berhasil) dan secara berkala pergi ke toko kelontong. Dengan daun, tentu saja (memberikan kekebalan dari pembelian impulsif). Terkadang tidak hanya ke toko, tetapi ke Auchan bersyarat, di mana lebih murah, tetapi ke mana harus pergi jauh.

Kami akan memodelkan situasi ini: kami datang ke Auchan dengan sehelai daun di tangan kami untuk berbelanja.

Perhatian, pertanyaan pertama: bagaimana model?

Input: informasi tentang produk yang akan dibeli dan jumlah yang diperlukan.

Untuk kenyamanan, kita dapat menganggap leaflet sebagai beberapa vektor non-negatif integer $$$y \ dalam Z _ + ^ n$ .

Sebagai variabel, kami mengambil, masing-masing, integer vektor non-negatif $$$x \ dalam Z _ + ^ n$ - berapa banyak dan produk apa yang akhirnya akan kita beli (solusi kita).

Intinya kecil - ambil semacam fungsi objektif $$$f (x, y)$ , yang mengatakan seberapa banyak kami melakukan kesalahan dengan pilihan produk.

Tergantung pada konteksnya, jenis fungsi dapat berubah, tetapi ada beberapa persyaratan dasar untuknya:

• Fungsi $$$f (x, y)$ harus memiliki minimum $$$x ^ * = \ arg \ min_ {x \ dalam R ^ n} f (x, y) = y$ (yaitu, secara optimal kami akan membeli persis apa yang tertulis dalam selebaran)
• Fungsi $$$f (x, y)$ harus dalam cembung $$$x$ (dan lebih disukai lancar) - untuk dapat menghitung secara efektif $$$min$ .

Dengan demikian, kami mendapatkan masalah:

$$

$$min_ {x \ dalam R ^ n} f (x, y)$$

Sekarang bayangkan daun itu tetap di rumah ...

Jadi, dengan satu komentar, kami masuk ke dunia tugas dengan ketidakpastian.

Jadi apa yang harus dilakukan jika dalam tugas $$$min_ {x \ dalam R ^ n} f (x, y)$ tidak kita kenal $$$y$ ?

Sekali lagi, jawabannya tergantung pada konteksnya.

Optimasi stokastik

Optimalisasi stokastik (biasanya) melibatkan

• Ketidakpastian dalam data bersifat stokastik. Pengetahuan lengkap tentang distribusi probabilistik dari nilai parameter non-deterministik
• Keterbatasan termasuk ketidakpastian itu lunak

Dalam contoh kita, jika kita memodelkannya menggunakan optimasi stokastik, kita akan mengatakan

• Oke, saya tidak tahu apa yang tertulis di selebaran, tapi saya sudah berjalan dengan selebaran selama 8 tahun sekarang, dan saya memiliki pengetahuan yang cukup baik tentang distribusi vektor $$$y$
• Bahkan jika saya membuat kesalahan dengan pilihan (mis. Dengan $$$x$ ), kembali ke rumah, saya mencari tahu yang sebenarnya $$$y$ dan, jika saya akan sepenuhnya aman, saya akan pergi ke Pyaterochka dan membeli di sana, meskipun lebih mahal.
• Sekarang saya akan memilih satu $$$x$ , yang akan meminimalkan beberapa jenis agregat dari fungsi tujuan awal dan kemungkinan "denda" untuk kesalahan tersebut.

Ini akan membawa kita ke tugas ini:

$$

$$\ min_ {x \ dalam R ^ n} E_y [f (x, y) + \ psi (y, z)] \\ s.t. \\ x + z \ geq y$$

Perhatikan bahwa dalam tugas ini, kami secara de facto membuat keputusan dua kali: pertama, keputusan utama untuk membeli di Auchan, yang menjadi tanggung jawab kami. $$$x$ , lalu "koreksi kesalahan" dengan $$$z$ .

Masalah utama dengan pendekatan ini adalah:

• Seringkali tidak ada informasi tentang distribusi parameter.
• Keterbatasan bisa parah (untuk tugas dengan risiko tinggi - kematian, kehancuran, nuklir atau kiamat zombie, dll.)
• Tidak selalu mungkin untuk "memperbaiki kesalahan" (keputusan dibuat sekali) atau sebaliknya, keputusan sering dibuat (dalam hal ini akan ada banyak integral bersarang, dan akan sangat sulit untuk dihitung).

Pengoptimalan online

Optimalisasi online adalah kerangka kerja yang mengeksplorasi pengambilan keputusan yang konsisten. Salah satu pendekatan standar untuk pemodelan dalam kerangka kerja ini adalah bandit multi-bersenjata, yang telah banyak ditulis tentang Habré.

Dalam konteks contoh mainan kami, kami akan:

• tidak memiliki (dan tidak pernah menggunakan sebelumnya) selebaran
  
• dan di rumah kita akan dipuji / dimarahi untuk produk-produk yang kita beli (pada saat yang sama kita hanya bisa menebak set yang diinginkan)
• tugasnya adalah untuk belajar secepat mungkin untuk membeli makanan serta mantannya, pangeran imajiner, baik, atau yang terbaik dari teman putra ibunya.

Optimasi yang kuat

Optimasi yang kuat adalah perpanjangan logis dari gagasan solusi minimax.

Idealnya, kita sekarang harus membuat keputusan yang akan selalu dapat diterima, terlepas dari keadaan. Orang-orang yang merancang pot, setrika, dan lemari es di Uni Soviet melakukan ini dalam konteks optimalisasi yang kuat: produk harus bekerja bahkan jika telah digunakan selama 20 tahun sebagai alat utama untuk pemusnahan mutan yang muncul setelah perang nuklir (itu juga perlu selamat).

Selain itu, saya ingin tugas tersebut didorong menjadi pemecah biasa - dan mereka tidak memahami batasan “untuk setiap implementasi variabel acak” (jika tidak ada jumlah terbatas dari implementasi ini).

Dalam masalah dengan selebaran, keputusan harus dibuat di sini dan sekarang dan tetap valid dalam kondisi apa pun:

$$

$$\ min_ {x \ dalam R ^ n, t \ dalam R} t \\ s.t. \\ f (x, y) \ leq t \ quad \ forall y \\ x \ geq y \ quad \ forall y$$

Jelas bahwa bahkan dalam contoh mainan ini, jika Anda tidak memerlukan apa pun dari $$$y$ , maka tidak ada solusi yang berarti yang akan berhasil.

Jadi bagaimana Anda menangani tugas-tugas seperti itu?

Membangun versi tugas yang kuat menggunakan contoh tugas LP

Pertimbangkan masalah optimisasi linier dengan ketidakpastian:

$$

$$\ min_ {x \ dalam R ^ n} c ^ Tx + d \\ s.t. \\ Ax \ leq b$$

Parameter $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ berasal dari data dan termasuk ketidakpastian.

Asumsi 1: Banyak Nilai (Implementasi) $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ dapat diparameterisasi, yaitu ada semacam itu $$$\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix}, \ begin {pmatrix} c_1 ^ T, d_1 \\ A_1, b_1 \ end {pmatrix}, \ dots, \ begin {pmatrix } c_k ^ T, d_k \\ A_k, b_k \ end {pmatrix}$ bahwa setiap implementasi data $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ terletak di set:

$$

$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix} \ di U = \ kiri \ {\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix} + \ sum_ {i = 1} ^ k \ zeta_i \ begin {pmatrix} c_i ^ T, d_i \\ A_i, b_i \ end {pmatrix} | \ quad \ zeta \ di Q \ subset R ^ k \ right \}$$

Di sini $$$\ begin {pmatrix} c ^ T_0, d_0 \\ A_0, b_0 \ end {pmatrix}$ disebut "nominal" data, dan $$$\ begin {pmatrix} c ^ T_i, d_i \\ A_i, b_i \ end {pmatrix} \ quad (1 \ leq i \ leq k)$ - "bergeser".



Kita sudah tahu bahwa semua ketidakpastian dalam masalah dapat dihilangkan dalam keterbatasan. Ayo lakukan.

Kami mendapatkan masalahnya

$$

$$\ min_ {x \ dalam R ^ n, t \ dalam R} t \\ st \\ c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ di U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ di U \\ $$

Versi tugas yang kuat

Sekarang adalah waktu untuk salah satu trik terkeren dalam pengoptimalan yang kuat - cara beralih dari jumlah kendala yang tidak terbatas ke serangkaian kendala terbatas yang terbatas.

Untuk memulai, pertimbangkan contoh sederhana kapan

$$

$$Q = \ {\ zeta \ dalam R ^ k | \ | \ zeta \ | _2 \ leq 1 \}$$

Semua batasan dalam sistem

$$

$$c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ di U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ dalam U \\ $$

jenis yang sama - itu hanya ketidaksetaraan linear. Belajar bekerja dengan satu - belajar bekerja dengan semua orang.

Oleh karena itu, kami mempertimbangkan satu batasan dari jenis ketimpangan:

$$

$$a ^ Tx \ leq b \ quad \ forall (a, b) \ dalam U = \ {(a_0, b_0) + \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i, b_i) | \ quad \ zeta \ di Q \} \\ (a_0 + \ sum_ {i = 1} ^ k \ zeta_i a_i) ^ Tx \ leq b_0 + \ sum_ {i = 1} ^ k \ zeta_i b_i \ quad \ forall \ zeta \ di Q \\ \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx \ quad \ forall \ zeta \ di Q \\ \ max _ {\ zeta \ dalam Q} \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx$$

Izinkan saya menjelaskan apa yang terjadi.

Pertama, kami memindahkan semua bagian dengan ketidakpastian ke sisi kiri ketidaksetaraan; $$$\ zeta$ .
Setelah itu, kami melihat kasus terburuk (masing-masing $$$x$ dia adalah miliknya).
Hasilnya, kami mendapat catatan berikut:

$$

$$g (x) = maks _ {\ zeta \ di Q} f (x, \ zeta) \ leq b_0 - a_0 ^ Tx$$

.

Langkah selanjutnya adalah menulis fungsi eksplisit $$$g (x)$ . Untuk melakukan ini, cukup dengan menyelesaikan masalah optimisasi dengan $$$\ zeta$ dan gantikan yang optimal $$$\ zeta *$ :

$$

$$\ max _ {\ | \ zeta \ | _2 \ leq 1} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) = \ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx - b_i) ^ 2}$$

yang mengarah ke ketimpangan:

$$

$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$$

Perhatikan bahwa ketidaksetaraan yang dihasilkan adalah cembung dan apa pun $$$x$ memuaskan dia memuaskan yang asli $$$a ^ Tx \ leq b$ untuk implementasi apa pun $$$(a, b) \ dalam U$ ...

Batasan $$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$ disebut versi kendala yang kuat $$$a ^ Tx \ leq b \ quad \ forall (a, b) \ dalam U$ .

Ini adalah salah satu workhorses utama dalam optimasi yang kuat - perkiraan kendala probabilitas oleh seperangkat terbatas kendala cembung.

Apa yang harus dilakukan dengan kendala (non-linear) yang lebih kompleks?

Membangun versi kendala yang kuat menggunakan dualitas kerucut

Banyak kendala nonlinier standar dapat direpresentasikan dalam bentuk kerucut (mis., Dalam formulir $$$Axe + b \ dalam K$ dimana $$$K$ adalah beberapa kerucut cembung tertutup):

• Non-negatif $$$X \ geq 0 \ quad \ leftrightarrow \ quad x \ dalam R ^ n _ +$
• Pembatasan Norma $$$\ | x \ | _p \ leq p \ quad \ leftrightarrow \ quad \ begin {pmatrix} x \\ p \ end {pmatrix} \ dalam K_p ^ n = \ left \ {(x, t) \ dalam R ^ n \ kali R_ + | \ quad \ | x \ | _p \ leq t \ benar \}$
• Batasan pada kepastian positif dari matriks $$$x_1F_1 + \ dots x_nF_n + G \ succeq 0$

Kembali ke batasan ketat.

Asumsikan bahwa masalah optimasi berkaitan dengan $$$\ zeta$ berhasil direduksi menjadi bentuk kerucut

$$

$$\ max _ {\ zeta} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx - b_i) \\ s.t \\ C \ zeta + d \ dalam K$$

Kami membangun dual untuk masalah ini.

Beberapa waktu yang lalu, saya menerbitkan posting tentang dualitas kerucut persis untuk mencurahkan sedikit perhatian pada teknik dalam posting ini.

$$

$$\ min _ {\ lambda} \ lambda ^ Td \\ st \\ C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k \\ \ lambda \ dalam K ^ *$$

Sekarang terserah pada hal kecil - teorema dualitas yang lemah:

$$

$$\ max _ {[\ zeta: \ quad C \ zeta + d \ dalam K]} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) \ leq \ min _ {\ lambda \ in G} \ lambda ^ Td \\ di mana \\ G = \ kiri \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ dalam K ^ * \ right \}$$

Oleh karena itu, sebagai perkiraan kuat dari kendala awal $$$a ^ Tx \ leq b, \ quad (a, b) \ dalam U$ pembatasan dapat digunakan

$$

$$\ lambda ^ Td \ leq b_0 - a_0 ^ Tx \\ G = \ kiri \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ dalam K ^ * \ right \}$$

dimana $$$\ lambda$ variabel yang sama dengan $$$x$ .

Jadi kami membangun kendala kuat untuk ketidaksetaraan asli.

Kesimpulan

Kami memeriksa teknik perkiraan kendala buruk (stokastik) oleh serangkaian cembung yang baik. Ini bisa bermanfaat, misalnya, jika:

• Anda tidak ingin menulis algoritma sendiri, tetapi pemecah yang Anda gunakan tidak tahu cara bekerja dengan kendala probabilitas.
• Ada masalah dengan parameter stokastik, sedangkan yang optimal sangat sensitif terhadap fluktuasi data.
• Dan, tentu saja, tugas dengan ketidakpastian, di mana semua batasannya ketat (harga kesalahannya terlalu tinggi)