バリア関数

数学の一分野である、制約付き最適化問題におけるバリア関数（バリアかんすう、英: Barrier function、障壁関数^[1]、しょうへきかんすう）とは、ある点が実行可能領域（英語版）の境界に近付くにつれて、その点での値が無限大へと近付くような連続関数のことを言う（Nocedal and Wright 1999）。制約違反に対する罰則項として用いられる。最も一般的な二種類のバリア関数は、逆バリア関数と対数バリア関数である。対数バリア関数は、主双対内点法との関連で、再び興味を集めるものとなった。

関数 f(x) を最適化するとき、ある定数 $b$ に対して代わりに関数 $f(x)+g(x,b)$ を最適化することによって、変数 $x$ をつねに $b$ よりも厳密に小とすることができる。ここで、 $g(x,b)$ はバリア関数である。

対数バリア関数

対数バリア関数 $g(x,b)$ は、 $x<b$ の場合 $-\log(b-x)$ で、それ以外の場合では $\infty$ となる関数として定義される（但し 1 次元の場合。より高い次元の場合は下記参照）。この定義は本質的には、 $t$ が 0 に向かうにつれて $log(t)$ が負の無限大へと発散する事実に由来する。

この定義は $x$ の極値（この場合、値は $b$ より小さい）がより少ないものを好むように最適化され、一方で極値から離れた関数に対してはあまり影響を与えないような、関数への勾配を導入するものである。

対数バリア関数は、最適化される関数に依存して、計算的に高価値でない逆バリア関数よりも、好まれるものであるかも知れない。

高次元

高次元への拡張は、各次元が独立である限り、簡単なものである。 $b_{i}$ よりも厳密に小さいように制限された各変数 $a_{i}$ に対して、 $-\log(b_{i}-x_{i})$ を足せばよい。

形式的定義

次を最小化せよ: $\mathbf {c} ^{T}x$

次を仮定する: $\mathbf {a} _{i}^{T}x\leq b_{i},i=1,\ldots ,m$

次の、厳密な実行可能領域を仮定する: $\{\mathbf {x} |Ax<b\}\neq 0$

次の対数バリア関数を定義する $\Phi (x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x)&{\text{for }}Ax<b\\+\infty &{\text{otherwise}}\end{cases}}$

脚注

[脚注の使い方]

^ 寒野善博 2019, p. 74.

参考文献

ウィキメディア・コモンズには、ニュートン法に関連するカテゴリがあります。

Nocedal, Jorge; and Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. ISBN 0-387-98793-2
寒野善博著、駒木文保編『最適化手法入門』講談社、2019年。ISBN 978-4-06-517008-3。
lecture on barrier method.^{[リンク切れ]}

数理最適化 • 最適化問題 : メソッド • ヒューリスティック

非線形(無制約)

… 関数　

勾配法

収束性	信頼領域ウルフ条件
準ニュートン法	BFGS法ブロイデン法 L-BFGS（英語版） DFP法対称ランク1法（英語版）
その他の求解法	ガウス・ニュートン法最急降下法レーベンバーグ・マルカート法共役勾配法（非線形共役勾配法）切り捨てニュートン法（英語版）ドッグレッグ法

… ヘッセ行列

最適化におけるニュートン法（英語版）

非線形(制約付き)

一般	バリア関数ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法逐次二次計画法連続線形計画（英語版）

凸最適化

凸縮小化

線型および
二次

内点法	カチヤンの楕円体法カーマーカーの投影アルゴリズム
ベイズ-交換	単体法改訂単体法（英語版）十文字法（英語版）レムケの主ピボット操作法（英語版）

組合せ最適化

系列範例
(Paradigms)

グラフ理論

最小全域木	ベルマン–フォード法ブルーフカ法ダイクストラ法ワーシャル–フロイド法ジョンソン法（英語版）クラスカル法
最大フロー問題	Dinic法（英語版）エドモンズ・カープフォード・ファルカーソンプッシュリラベル最大流アルゴリズム（英語版）

メタヒューリスティクス

カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）

この項目は、応用数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

Read other articles:

Antimon pentoksida

Antimon pentoksida Nama Nama IUPAC (dioxo-λ5-stibanyl)oxy-dioxo-λ5-stibane Nama lain antimon(V) oksida Penanda Nomor CAS 1314-60-9 Y Model 3D (JSmol) Gambar interaktif 3DMet {{{3DMet}}} ChemSpider 14129 Y Nomor EC PubChem CID 14813 Nomor RTECS {{{value}}} CompTox Dashboard (EPA) DTXSID6050467 InChI InChI=1S/5O.2Sb YKey: LJCFOYOSGPHIOO-UHFFFAOYSA-N YInChI=1/5O.2Sb/rO5Sb2/c1-6(2)5-7(3)4Key: LJCFOYOSGPHIOO-YOUOZQPQAC SMILES O=[Sb](=O)O[Sb](=O)=O Sifat Rumus kimia...

2024 World Athletics Indoor Championships – Women's pole vault

Women's pole vault at the 2024 World Athletics Indoor ChampionshipsMolly Caudery in the competitionVenueCommonwealth ArenaDates1–3 MarchCompetitors12 from 11 nationsWinning distance4.80Medalists Molly Caudery Great Britain Eliza McCartney New Zealand Katie Moon United States← 20222026 → 2024 World AthleticsIndoor ChampionshipsTrack events60 mmenwomen400 mmenwomen800 mmenwomen1500 mmenwomen3000 mme...

Febby Rastanty

Febby RastantyFebby pada tahun 2021LahirFebriani Rastanty1 Februari 1996 (umur 28)Jakarta, IndonesiaAlmamaterFakultas Hukum Universitas IndonesiaPekerjaanPemeranmodelpenyanyiTahun aktif2004—sekarangKarier musikGenrePopInstrumenVokalMantan anggotaBlink Febby Rastanty (lahir 1 Februari 1996) adalah pemeran, penyanyi dan model Indonesia.[1] Kehidupan awal dan pendidikan Febby merupakan anak sulung dari pasangan Rasyid Jayaruddin dan Anice Worang.[2] Ayahnya berasal d...

United Nations Observer Mission Uganda–Rwanda

Rwanda (red) and Uganda (green) The United Nations Observer Mission Uganda–Rwanda (UNOMUR) was a peacekeeping mission established by the United Nations Security Council in Resolution 846 and lasted from June 1993 to September 1994. Its mission was to monitor the border between Uganda and Rwanda and verify that no military assistance was being provided across it. It was based in Kabale, Uganda and its mandate thus covered 193 miles of border. Countries contributing to UNOMUR included Banglad...

イスラームにおける結婚

イスラームにおける結婚（イスラームにおけるけっこん）とは、二者の間で行われる法的な契約である。新郎新婦は自身の自由な意思で結婚に同意する。口頭または紙面での規則に従った拘束的な契約は、イスラームの結婚で不可欠だと考えられており、新郎と新婦の権利と責任の概要を示している[1]。イスラームにおける離婚は様々な形をとることができ、個�...

Australian Open 1991

Australian Open 1991 Sport Tennis Data 14 gennaio - 27 gennaio Edizione 79a Categoria Grande Slam (ITF) Superficie Cemento Località Melbourne, Victoria, Australia Campioni Singolare maschile Boris Becker Singolare femminile Monica Seles Doppio maschile Scott Davis / David Pate Doppio femminile Patty Fendick / Mary Joe Fernández Doppio misto Jo Durie / Jeremy Bates Singolare ragazzi Thomas Enqvist Singolare ragazze Nicole Pratt Doppio ragazzi Grant Doyle / Joshua Eagle Doppio ragazze Karina...

Impact driver

Hand tool for loosening threaded fasteners, with a powerful intermittent action Not to be confused with Impact wrench. A manual impact driver (for use with hammer) with screwdriver bits and adapters An impact driver is a tool that delivers a strong, sudden rotational force and forward thrust. The force can be delivered either by striking with a hammer in the case of manual impact drivers, or mechanically in the case of powered impact drivers. Impact driver guide set with bits It is often used...

List of forts in Maharashtra

a green canyon near Nashik Karnala Fort in Navi Mumbai Torna Fort in Maharashtra Deccan Traps in Matheran The forts of Maharashtra which are located on western ghats are also called Green Canyon of India.[1] This is a list of forts in Maharashtra a state of India[2][3] Achala Fort (Nashik) Agashi Fort Ahmednagar Fort Ahivant Fort Ajinkyatara Akola Fort Akluj Fort Alang Fort Ambolgad Anjaneri Anjanvel Fort Ankai Fort Antur Fort Arnala fort Asheri fort Asava fort Avchit...

Enterprise (Star Trek)

Pour les articles homonymes, voir Enterprise. Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Maquette originale de l'Enterprise NCC-1701 USS Enterprise (1799) pendant la guerre de Tripoli HMS Enterprise (1848) (à gauche) Porte-avions USS Enterprise (CVN 65) en 2011 Navette spatiale Enterprise (OV-101) sur son pas de lancement Maquette de l'USS Enterprise NCC-1701-A. Le nom Enterprise a été donné à plusieurs vaisseaux spatiaux fictifs...

中華民國國軍中的中共間諜列表

本表是動態列表，或許永遠不會完結。歡迎您參考可靠來源來查漏補缺。潛伏於中華民國國軍中的中共間諜列表收錄根據公開資料來源，曾潛伏於中華民國國軍、被中國共產黨聲稱或承認，或者遭中華民國政府調查審判，為中華人民共和國和中國人民解放軍進行間諜行為的人物。以下列表以現今可查知時間為準，正確的間諜活動或洩漏機密時間可能早於或晚於以下所歸�...

Badan penegak hukum federal di Amerika Serikat

Aparat dan penegak hukum di Amerika Serikat Hukum Pengadilan Badan kekuasaan pemerintah Lembaga legislatif Lembaga eksekutif Lembaga yudikatif Konteks hukum Prosedur kriminal Kecurigaan logis Peringatan Miranda Penangkapan Perintah penangkapan Penggeledahan dan penyitaan Terry stop Badan kejaksaan Pengacara Kejaksaan Agung Amerika Serikat Daftar lembaga penegak hukum Penegak hukum federal Penegak hukum daerah Operasi/organisasi/terkait kepolisian Lisensi Penegak disiplin Pangkat Seragam Atrib...

الدوري الفرنسي الدرجة الثالثة 2016–17

الدوري الفرنسي الدرجة الثالثة 2016–17 تفاصيل الموسم الدوري الفرنسي الدرجة الثالثة النسخة 24 البلد فرنسا التاريخ بداية:5 أغسطس 2016 نهاية:19 مايو 2017 المنظم اتحاد فرنسا لكرة القدم البطل نادي شاتورو الهابطون نادي سيدان، وسي أ باستيا مباريات ملعوبة 287 &#...

Culture of poverty

Social theory asserting that value systems perpetuate poverty This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (July 2010) (Learn how and when to remove this message) Part of a series onEconomic, applied, and development anthropology Basic concepts Commodification Barter Debt Finance Embeddedness Reciprocity Redistribution Value Wealth Gift economy Limited good...

Coat of arms of the London Borough of Bexley

Coat of arms Coat of arms of the London Borough of Bexley is the official coat of arms of the London Borough of Bexley, granted on 20 May 1965. The arms have wavy lines representing the rivers Thames, Cray and Shuttle, on which Bexley is situated. The gold fields at top with the oak tree and bottom with the cog wheel represent the agricultural and mineral wealth of the Borough. The oak tree was taken from the arms of the former Bexley council, and also signified the rural nature of much of th...

Pumsavana Simantonayana

Modern combination of two Hindu prenatal rites Part of a series onHinduism Hindus History OriginsHistorical Hindu synthesis (500/200 BCE–300 CE) History Indus Valley Civilisation Historical Vedic religion Dravidian folk religion Śramaṇa Tribal religions in India Traditional Itihasa-Purana Epic-Puranic royal genealogies Epic-Puranic chronology Traditions Major traditions Shaivism Shaktism Smartism Vaishnavism List Deities Trimurti Brahma Vishnu Shiva Tridevi Saraswati Lakshmi Parvati Othe...

William S. Burroughs

American writer and visual artist (1914–1997) For other people named William Burroughs, see William Burroughs (disambiguation). William S. BurroughsBurroughs in 1983BornWilliam Seward Burroughs II(1914-02-05)February 5, 1914St. Louis, Missouri, U.S.DiedAugust 2, 1997(1997-08-02) (aged 83)Lawrence, Kansas, U.S.Pen nameWilliam LeeOccupationAuthorEducationHarvard University (BA)GenreBeat literature, surrealism, satireLiterary movementBeat Generation, postmodernism, Science FictionNotable ...

Expedition of Dhat al-Riqa

625 Military campaign led by the Islamic prophet Muhammad Expedition of Dhat al-RiqaDateJuly 625 AD or AD 628 in 3rd month of AH 7 (Islamic calendar)LocationDhat al-RiqaResult Enemy escapes (some sources claim treaty was signed)[1][2]Belligerents Muslims of Medina Banu GhatafanCommanders and leaders Muhammad UnknownStrength 400 or 800[2][3] Unknown vteCampaigns of Muhammad Al-‘Īṣ Safwan Buwat Dhu al-'Ushairah Abwa' Badr Kudr Sawiq Banu Qaynuqa' Dhu 'Amar B...

Fisica

Disambiguazione – Se stai cercando l'opera di Aristotele, vedi Fisica (Aristotele). I fenomeni naturali costituiscono l'oggetto di studio della fisica. Dall'alto a sinistra in senso orario: 1) la dispersione ottica della luce attraverso le gocce d'acqua produce un arcobaleno, un fenomeno studiato dall'ottica; 2) un'applicazione dell'ottica: il laser; 3) delle mongolfiere che sfruttano la forza di Archimede per volare; 4) una trottola, un sistema studiabile in meccanica classica; 5) l'effet...

Гран-при Бразилии 1997 года

Гран-при Бразилии 1997 года Дата 9 марта 1997 года Место Бразилия Трасса Интерлагос Подиум Победитель Жак ВильнёвWilliams-Renault 2-е место Герхард БергерBenetton-Renault 3-е место Оливье ПанисProst-Mugen-Honda Карта трассы ЧМ 1997 года, этап № 2 из 17 Зачётная гонка № 599 Гран-при Бразилии 1997 года �...

Bree Olson

Bree OlsonBree Olson di AEE pada 2012LahirRachel Marie Oberlin7 Oktober 1986 Houston, TexasKebangsaanAmerika SerikatPekerjaan Aktris Model Mantan Film porno Rachel Marie Oberlin juga dikenal dengan nama panggungnya Bree Olson, (lahir 7 Oktober 1986), adalah seorang aktris, model, dan mantan aktris porno Amerika. Dia tampil di lebih dari 600 film porno dari tahun 2006 hingga 2011.[1] Sejak meninggalkan industri film dewasa, ia menjadi kritis terhadap industri dan stigma yang melekat s...