罰金関数法

OR事典

罰金関数法

読み方：ばっきんかんすうほう
【英】：penalty function method

ペナルティ(罰金)関数法は, 制約付き最適化問題を無制約最適化問題に変換して解く方法である. この方法では, 制約を満たさないことに対するペナルティ項を目的関数に加えて定義されるペナルティ関数を無制約最適化することを, ペナルティ項の重みを増やしながら繰り返す. 60年代に盛んに研究された方法であるが最適解近くでの悪条件がこの方法の欠点とされ, その後研究の主流は乗数法などに移っていったが, 80年代後半に内点法として復活した.

ウィキペディア

ペナルティ関数法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/27 09:36 UTC 版)

ペナルティ関数法（ペナルティかんすうほう、英: Penalty method）とは、制約付き最適化問題（英語版）に対する解法の一種である。

ペナルティ関数法は制約付き最適化問題を無制約最適化問題に変換して最終的には元の問題の最適化に収束させることを目指す手法である。無制約最適化問題に変換する際に目的関数に追加される項はペナルティ関数^{[注釈 1]}と呼ばれ、制約の違反度合いとそれに対応する係数のペナルティパラメータの積で表される。もし制約を違反している場合、ペナルティ関数は非ゼロの値をとり、制約を違反していない場合はゼロの値をとる。

説明

以下の制約付き最適化問題について考える:

${\displaystyle \min _{x}f(\mathbf {x} )}$

Optimization computes maxima and minima.

非線形(制約付き)

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

凸最適化

凸縮小化	切除平面法 簡約勾配法 劣勾配法
線型 および 二次	内点法 アフィンスケーリング法（英語版） カーマーカーの射影変換法 メロートラの予測子修正子法（英語版） 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法（英語版） 有効制約法

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法）
グラフ理論	最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版）
ネットワークフロー (最大流問題)	Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法

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