Masalah matematika klasik memanifestasikan dirinya di dunia nyata

Seratus tahun yang lalu, ahli matematika hebat David Hilbert mengajukan pertanyaan penelitian dari bidang matematika murni. Perkembangan terbaru dalam teori optimasi membawa karya Hilbert ke dunia robot mobil

Jauh sebelum robot bisa berlari, dan mobil bisa menyetir sendiri, matematikawan menganggap pertanyaan matematika sederhana. Akhirnya, mereka mengatasinya dan mengesampingkannya - tidak bisa tahu bahwa objek dari keingintahuan matematika mereka akan memanifestasikan dirinya dalam mesin masa depan yang jauh.

Masa depan telah tiba. Sebagai hasil dari karya baru Amir Ali Ahmadi dan Aniruda Majumara dari Universitas Princeton, masalah klasik matematika murni siap memberikan bukti yang kuat bahwa drone dan robot otomatis tidak akan menabrak pohon atau taksi ke jalur yang akan datang.

"Ada jaminan penuh, 100% yang dapat dibuktikan bahwa sistem Anda" dapat menghindari tabrakan, kata Georgina Hall , seorang mahasiswa pascasarjana dari Princeton yang bekerja sama dengan Ahmadi dalam pekerjaan ini.

Amir Ali Ahmadi, Profesor dari Princeton

Garansi diambil di tempat yang tidak terduga - dalam masalah matematika yang dikenal sebagai " jumlah kuadrat ". Itu dimasukkan pada tahun 1900 oleh ahli matematika hebat David Hilbert. Dia bertanya apakah persamaan tertentu selalu dapat dinyatakan sebagai jumlah dari dua istilah terpisah, yang masing-masing kuadrat.

Matematikawan menjawab pertanyaan Hilbert beberapa dekade kemudian. Kemudian, hampir 90 tahun kemudian, ilmuwan dan insinyur komputer menemukan bahwa properti matematika ini - ekspresi persamaan dalam jumlah kuadrat - membantu memecahkan banyak masalah nyata yang ingin mereka pecahkan.

"Banyak matematika klasik abad ke-19 digunakan dalam apa yang saya lakukan, bersama dengan matematika komputasional yang sangat modern," kata Ahmadi.

Namun, begitu para peneliti menyadari bahwa jumlah kuadrat dapat membantu menjawab berbagai jenis pertanyaan, mereka mengalami masalah dalam menerapkan pendekatan ini. Pekerjaan baru menghilangkan salah satu masalah terbesar seperti itu, memaksa pertanyaan matematika lama untuk memecahkan beberapa masalah teknologi paling penting di zaman kita.

Dijamin Positif

Apa artinya jumlah tertentu adalah jumlah kuadrat? Ambil nomor 13. Ini adalah jumlah dari dua kotak - 2 ² dan 3 ² . Angka 34 adalah jumlah dari 3 ² dan 5 ² .

Alih-alih angka, pertanyaan Hilbert - masalah 17 dari 23 yang ia usulkan pada awal abad ke-20 - berkaitan dengan polinomial seperti 5x ² + 16x + 13. Polinomial semacam itu kadang-kadang juga dapat direpresentasikan sebagai jumlah kotak. Misalnya, 5x ² + 16x + 13 dapat ditulis ulang sebagai (x + 2) ² + (2x + 3) ² .

Ketika ekspresi adalah jumlah kuadrat, Anda tahu bahwa itu selalu positif (semua angka [nyata] kuadrat memberikan angka positif atau nol, dan jumlah angka positif adalah positif). Hilbert ingin tahu apakah ini berfungsi sebaliknya: dapatkah semua polinomial non-negatif diekspresikan sebagai jumlah kuadrat fungsi rasional. Pada 1927, ahli matematika Emil Artin membuktikan bahwa hipotesis Hilbert benar.

Hubungan ini cukup bermanfaat. Jika Anda diberi polinomial yang kompleks, dengan puluhan variabel dinaikkan ke tingkat tertinggi, cukup sulit untuk segera menentukan apakah selalu non-negatif. “Beberapa polinomial jelas tidak negatif, yang lain tidak. Sulit untuk menguji mereka untuk non-negatif, "kata Ahmadi.

Tetapi segera setelah Anda menunjukkan bahwa polinomial ini dapat diekspresikan dalam bentuk jumlah kuadrat, maka non-negativitas hanya akan menjadi konsekuensi dari ini. "Jumlah kotak memberi Anda sertifikat kepositifan yang indah," kata Pablo Parrilo , seorang ilmuwan dan insinyur komputer di Massachusetts Institute of Technology yang terlibat dalam menarik masalah jumlah kotak ke dunia aplikasi.

Mengetahui bahwa polinomial tertentu selalu non-negatif mungkin tampak seperti kesederhanaan matematis. Tetapi seratus tahun setelah Hilbert mengajukan pertanyaannya, non-negatif dari polinomial ternyata menjadi jawaban untuk masalah yang diterapkan yang mempengaruhi kita semua.

Cara terbaik

Jumlah kuadrat memenuhi dunia nyata di bidang optimisasi. Teori optimisasi disibukkan dengan menemukan cara terbaik untuk melakukan sesuatu sambil berada dalam batasan - misalnya, menemukan rute terbaik untuk mulai bekerja, mengingat keadaan jalan dan halte yang perlu Anda lakukan di sepanjang jalan. Skenario seperti itu seringkali dapat direduksi menjadi polinomial. Dalam kasus seperti itu, dimungkinkan untuk menyelesaikan atau "mengoptimalkan" skenario dengan menemukan nilai minimum yang diambil polinomial.

Menemukan minimum polinomial dengan banyak variabel adalah tugas yang sulit. Tidak ada algoritma sederhana dari buku teks untuk menghitung nilai minimum polinomial yang kompleks, apalagi mereka sulit untuk dibangun pada grafik.

Georgina Hall

Karena nilai minimum polinomial sulit untuk dihitung secara langsung, para peneliti membuat asumsi tentang nilai ini dengan metode lain. Di sinilah non-negativitas berperan, dan pertanyaan apakah polinomial adalah jumlah kuadrat. "Memastikan non-negatif adalah inti dari semua masalah optimisasi," kata Reha Thomas, ahli matematika di University of Washington.

Salah satu cara untuk menemukan nilai minimum adalah dengan mengajukan pertanyaan: nilai maksimum apa yang dapat dikurangkan dari polinomial non-negatif sehingga pada beberapa titik tidak menjadi negatif? Untuk menjawab pertanyaan, perlu memeriksa berbagai nilai - apakah mungkin untuk mengurangi 3 sehingga tidak menjadi negatif? Dan 4? Dan 5? Mengulangi prosedur, pada setiap langkah Anda perlu tahu apakah polinomial tetap non-negatif. Ini diverifikasi melalui kemungkinan ekspresinya sebagai jumlah kuadrat.

“Pertanyaan yang perlu ditanyakan adalah“ apakah polinomnya non-negatif? ”Masalahnya adalah bahwa dengan sejumlah besar variabel, pertanyaan ini sulit dijawab, kata Ahmadi. "Karena itu, kami menggunakan jumlah kuadrat sebagai pengganti non-negatif."

Segera setelah peneliti menyadari minimum - nilai optimal polinomial - mereka dapat menggunakan metode lain untuk menentukan parameter input yang mengarah ke nilai ini. Namun, agar non-negatif untuk membantu menyelesaikan masalah optimisasi, Anda harus menemukan cara untuk dengan cepat menghitung apakah polinomial dinyatakan dalam jumlah kuadrat. Dan bagi para peneliti untuk dapat melakukan ini, butuh 100 tahun sejak Hilbert mengajukan pertanyaan.

Memecahkan masalah

Masalah ke-17 Hilbert pindah dari dunia matematika murni ke bidang terapan sekitar tahun 2000. Saat itulah beberapa peneliti datang dengan algoritma untuk memeriksa apakah polinomial dapat diwakili dalam hal jumlah kuadrat. Mereka sampai pada titik ini dengan memecahkan masalah kuadrat melalui “ pemrograman semi-terdefinisi ”, berkat komputer yang mampu mengatasi tugas seperti itu. Hal ini memungkinkan bagi para peneliti dari berbagai bidang seperti ilmu komputer dan teknik untuk menggunakan kemungkinan non-negatif untuk mengarahkan pencarian mereka ke arah cara optimal untuk memecahkan masalah.

Aniruda Majumdar

Tetapi pemrograman semi-pasti memiliki batasan besar: ia bekerja lambat pada tugas-tugas besar dan tidak dapat memproses beberapa polinomial paling kompleks yang sangat diminati oleh para peneliti. Pemrograman semi-definisi dapat digunakan untuk mendekomposisi ke dalam jumlah kuadrat polinomial seperti itu yang terdiri dari tidak lebih dari selusin variabel yang dinaikkan menjadi kekuatan tidak lebih dari 6. Polinomial menggambarkan masalah teknik yang rumit - misalnya, memastikan bahwa robot akan tetap berdiri - dapat masukkan 50 variabel, atau bahkan lebih dari itu. Suatu program dapat mengunyah polinomial seperti itu sampai akhir waktu, dan masih belum memberikan jumlah kuadrat tersebut.

Dalam sebuah makalah yang dipublikasikan secara online Juni lalu, Ahmadi dan Majumdar menjelaskan bagaimana cara mengatasi lambatnya pemrograman semi-definisi. Alih-alih mencoba menemukan dekomposisi dalam jumlah kuadrat dengan satu, program lambat, mereka menunjukkan bagaimana Anda bisa melakukan ini dengan solusi
urutan tugas yang lebih sederhana, yang akan jauh lebih cepat untuk dihitung.

Tugas jenis ini disebut "linear," dan dikembangkan pada tahun 1940-an untuk menyelesaikan masalah optimisasi terkait masalah militer. Program lini sekarang dipahami dengan baik dan cepat diselesaikan. Dalam sebuah makalah baru, Ahmadi dan Majumdar menunjukkan bahwa seseorang dapat menyelesaikan banyak program linear yang terhubung (atau, dalam beberapa kasus, jenis masalah yang berbeda, program kerucut orde kedua), dan menggabungkan hasilnya untuk mendapatkan sesuatu yang hampir sama baiknya dengan jawaban , yang dapat memberikan program untuk pemrograman semi-definisi. Akibatnya, insinyur memiliki alat praktis baru yang dapat mereka gunakan untuk memeriksa non-negatif dan dengan cepat menemukan dekomposisi dalam jumlah kuadrat.

"Kami mempelajari beberapa masalah robotika dan teori kontrol, dan menunjukkan bahwa kualitas solusi yang dihasilkan berguna untuk penggunaan praktis, dan mereka jauh lebih cepat untuk dihitung," kata Majumdar.

Bukti keamanan

Kecepatan pengambilan keputusan adalah segalanya jika Anda menggunakan robomobile. Dalam situasi seperti itu, polinomial dapat bertindak sebagai penghalang matematis yang diatur di sekitar penghalang yang tidak ingin Anda tabrak - jika itu dapat dihitung dengan cukup cepat.

Bayangkan sebuah contoh sederhana: mobil robot di tempat parkir raksasa. Tidak ada apa-apa di tempat parkir kecuali bilik keamanan di ujung. Tugas Anda adalah memprogram mesin sehingga tidak pernah menabrak stan ini.

Dalam hal ini, Anda dapat menarik grid ke tempat parkir. Kemudian buat polinomial yang mengambil titik pada grid sebagai input. Pastikan bahwa nilai polinomial di lokasi mesin negatif, dan nilai di lokasi bilik penjaga adalah positif.

Pada beberapa titik antara mobil Anda dan bilik, polinomial akan berubah dari minus ke plus. Karena mobil Anda hanya dapat ditemukan di tempat polinomial negatif, titik-titik ini akan memainkan peran sebagai tembok.

“Jika kamu memulai dari tempat tertentu, maka robot tidak akan melewati garis di belakang yang menjadi penghalang. Ini memberi Anda bukti formal untuk menghindari tabrakan, ”kata Ahmadi.

Tentu saja, akan merepotkan jika dinding ini berada di tengah jalan antara mesin dan stan. Hal ini diperlukan untuk membangun polinomial sehingga dinding mengelilingi penghalang sekencang mungkin. Opsi ini akan melindungi stan, dan memberi mobil banyak ruang untuk bergerak.

Dalam praktiknya, perlu untuk meminimalkan nilai - jarak antara dinding dan kotak - sehingga Anda perlu menggeser grafik polinomial dan melihat seberapa jauh dapat dipindahkan sampai bergerak dari minus ke plus. Ini dicapai dengan memeriksa apakah polinom tetap jumlah kuadrat.

Parkir yang hampir kosong adalah satu hal. Tetapi dalam skenario realistis mengendalikan mesin, sensornya selalu mendeteksi hambatan bergerak baru - mobil, sepeda, anak-anak. Setiap kali muncul hambatan baru atau yang diketahui bergerak, mesin perlu membuat polinomial kompleks baru yang melampirkan hambatan ini. Ini adalah banyak pemeriksaan pada jumlah kotak yang harus dilakukan dengan cepat.

Tujuh tahun yang lalu, sepasang peneliti lain telah membayangkan bahwa teknik untuk bekerja dengan polinomial mungkin dapat digunakan untuk memisahkan robot mobil dan tempat-tempat di mana mereka tidak boleh jatuh. Tetapi pada saat itu, kekuatan komputer membuat ide ini menjadi mimpi.

Pendekatan baru Ahmadi dan Majumdar membuka cara baru untuk melakukan komputasi instan semacam itu. Jadi, jika dan ketika robomobiles dapat bergerak dengan aman di seluruh dunia, kita dapat berterima kasih kepada Google dan Tesla - serta Hilbert untuk ini.