非線形計画法

概要

非線形計画法（Nonlinear Programming）は、目的関数または制約条件に非線形性を含む最適化問題を扱う分野です。現実の多くの問題は非線形性を持つため、工学・経済学・機械学習などで重要な役割を果たします。

基本的な定式化

一般的な非線形計画問題

$n$ 次元ベクトル $x \in \mathbb{R}^n$ を変数とするスカラー関数 $f(x)$ に対して、制約条件を課した最適化問題：

$$\begin{align} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \leq 0, \quad i = 1, \ldots, m \\ & h_j(x) = 0, \quad j = 1, \ldots, p \end{align}$$

ここで：

• $f(x)$: 目的関数（最小化したい関数）
• $g_i(x) \leq 0$: 不等式制約条件（Inequality constraints）
• $h_j(x) = 0$: 等式制約条件（Equality constraints）

制約条件の分類

不等式制約条件（Inequality Constraints）

形式: $g_i(x) \leq 0$

例:

• 資源制約: $\sum_{j=1}^n a_{ij} x_j \leq b_i$
• 非負制約: $x_j \geq 0$ （$-x_j \leq 0$ として表現）
• 球制約: $\|x\|^2 \leq r^2$

等式制約条件（Equality Constraints）

形式: $h_j(x) = 0$

例:

• 予算制約: $\sum_{j=1}^n p_j x_j = B$
• 物質収支: $\sum_{j=1}^n s_{ij} x_j = 0$
• 正規化条件: $\|x\|^2 = 1$

制約の変換

等式制約 $h(x) = 0$ は、$h(x) \leq 0$ かつ $h(x) \geq 0$ （つまり $-h(x) \leq 0$）として不等式制約に変換できますが、理論的な取り扱いが異なります。

許容領域と最適解

許容解と許容領域

許容解（Feasible Solution）: 制約条件を満たす点 $x$

許容領域（Feasible Region）: 許容解全体の集合

$$S = \{x \in \mathbb{R}^n : g_i(x) \leq 0 \; (i=1,\ldots,m), \; h_j(x) = 0 \; (j=1,\ldots,p)\}$$

許容領域の存在性

許容領域が空集合の場合、最適化問題は実行不可能（Infeasible）となり、解が存在しません。

最適解の分類

大域的最適解（Global Optimal Solution）

$x^* \in S$ が任意の $x \in S$ に対して $f(x^*) \leq f(x)$ を満たす解

$$f(x^*) = \min_{x \in S} f(x)$$

局所最適解（Local Optimal Solution）

$x^* \in S$ かつ、ある $\epsilon > 0$ が存在して、任意の $x \in S \cap B(x^*, \epsilon)$ に対して $f(x^*) \leq f(x)$ を満たす解

ここで $B(x^*, \epsilon) = \{x \in \mathbb{R}^n : \|x - x^*\| < \epsilon\}$ は中心 $x^*$、半径 $\epsilon$ の開球（Open Ball）

孤立局所最適解（Isolated Local Optimal Solution）

$x^* \in S$ かつ、ある $\epsilon > 0$ が存在して、任意の $x \in S \cap B(x^*, \epsilon) \setminus \{x^*\}$ に対して $f(x^*) < f(x)$ を満たす解

近傍内に他の局所最適解が存在しない局所最適解

大域最適解の探索

非線形問題では一般に局所最適解しか求まりません。大域最適解を求めるには特別な手法（大域最適化アルゴリズム）が必要です。

解の存在性

ワイエルシュトラス定理

定理（Weierstrass' Extreme Value Theorem）: 許容領域 $S$ が有界閉集合で、目的関数 $f$ が $S$ で連続ならば、最適解が存在する。

証明のアイデア

1. $S$ が有界閉集合であることから、$S$ はコンパクト集合
2. 連続関数のコンパクト集合上での最大値・最小値の存在定理を適用
3. したがって、$f$ は $S$ 上で最小値を持つ

実践的な含意

• 制約条件が適切に設定されていれば解の存在が保証される
• 無制約問題では $f(x) \to \infty$ as $\|x\| \to \infty$ などの条件が必要

数学的厳密性

実際の応用では、ワイエルシュトラス定理の条件が満たされているかを確認することが重要です。

最適性条件

無制約問題の最適性条件

無制約問題 $\min f(x)$ において：

一次必要条件

$x^*$ が局所最適解ならば：

$$\nabla f(x^*) = 0$$

二次必要条件

$x^*$ が局所最適解ならば：

$$\nabla^2 f(x^*) \succeq 0 \quad \text{（半正定値）}$$

二次十分条件

$$\nabla f(x^*) = 0 \text{ かつ } \nabla^2 f(x^*) \succ 0 \quad \text{（正定値）}$$

ならば、$x^*$ は孤立局所最適解

制約条件付き問題の最適性条件

制約条件付き問題では、制約の有効性（Activeness）を考慮する必要があります。

有効制約と非有効制約

点 $x^*$ において：

• 有効制約（Active Constraint）: $g_i(x^*) = 0$ となる不等式制約
• 非有効制約（Inactive Constraint）: $g_i(x^*) < 0$ となる不等式制約

等式制約は常に有効です。

制約想定（Constraint Qualifications）

最適性条件を適用するための技術的条件：

線形独立制約想定（LICQ）

有効制約の勾配ベクトルが線形独立：

$$\{\nabla g_i(x^*) : i \in I(x^*)\} \cup \{\nabla h_j(x^*) : j = 1, \ldots, p\}$$

が線形独立（ここで $I(x^*) = \{i : g_i(x^*) = 0\}$）

マンガサリアン・フロムビッツ制約想定（MFCQ）

$$\exists d \in \mathbb{R}^n : \begin{cases} \nabla g_i(x^*)^T d < 0, & i \in I(x^*) \\ \nabla h_j(x^*)^T d = 0, & j = 1, \ldots, p \end{cases}$$

KKT条件

カルーシュ・キューン・タッカー（KKT）条件

制約想定が満たされるとき、$x^*$ が局所最適解であるための必要条件：

KKT条件

以下の条件を満たす $\lambda^* = (\lambda_1^*, \ldots, \lambda_m^*)$ と $\nu^* = (\nu_1^*, \ldots, \nu_p^*)$ が存在する：

1. 停留条件（Stationarity）:

   $$\nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^p \nu_j^* \nabla h_j(x^*) = 0$$

2. 主実行可能性（Primal Feasibility）:

   $$g_i(x^*) \leq 0, \quad h_j(x^*) = 0$$

3. 双対実行可能性（Dual Feasibility）:

   $$\lambda_i^* \geq 0$$

4. 相補スラック性（Complementary Slackness）:

   $$\lambda_i^* g_i(x^*) = 0$$

KKT条件の解釈

ラグランジュ乗数の意味

• $\lambda_i^*$: 制約 $g_i(x) \leq 0$ のシャドウ価格
• $\nu_j^*$: 制約 $h_j(x) = 0$ のシャドウ価格

シャドウ価格は制約の右辺を少し緩和したときの目的関数値の変化率を表します。

相補スラック性の意味

• $g_i(x^*) < 0$ （制約が非有効）なら $\lambda_i^* = 0$
• $\lambda_i^* > 0$ なら $g_i(x^*) = 0$ （制約が有効）

経済学的解釈

相補スラック性は「余っている資源に対する限界価値は0」という経済学の原理と対応しています。

KKT条件の十分性

特別な場合にはKKT条件が最適性の十分条件にもなります：

凸計画問題の場合

目的関数 $f$ と制約関数 $g_i$ がすべて凸関数で、$h_j$ がアフィン関数の場合、KKT条件は最適性の必要十分条件

二次計画問題の場合

目的関数が凸二次関数で、制約が線形の場合

数値解法の概要

制約なし最適化アルゴリズム

勾配法系列

• 最急降下法（Steepest Descent）
• 共役勾配法（Conjugate Gradient）
• 準ニュートン法（Quasi-Newton Methods）

ニュートン法系列

• ニュートン法（Newton's Method）
• 修正ニュートン法（Modified Newton Methods）

制約付き最適化アルゴリズム

ペナルティ法（Penalty Methods）

制約条件をペナルティ項として目的関数に組み込む

バリア法（Barrier Methods）

制約の境界に近づくにつれて無限大になる項を追加

SQP法（Sequential Quadratic Programming）

各反復で二次計画部分問題を解く

内点法（Interior Point Methods）

制約の内部から最適解に向かう

応用例

工学最適化

構造最適化

$$\begin{align} \min_{x} \quad & \text{重量}(x) \\ \text{subject to} \quad & \text{応力}(x) \leq \sigma_{\text{許容}} \\ & \text{変位}(x) \leq \delta_{\text{許容}} \\ & x_{\min} \leq x \leq x_{\max} \end{align}$$

制御系設計

$$\begin{align} \min_{K} \quad & \|G_{cl}(K)\|_{\infty} \\ \text{subject to} \quad & \text{安定性制約} \\ & \text{性能制約} \end{align}$$

機械学習

サポートベクターマシン

$$\begin{align} \min_{w,b,\xi} \quad & \frac{1}{2}\|w\|^2 + C\sum_{i=1}^n \xi_i \\ \text{subject to} \quad & y_i(w^T x_i + b) \geq 1 - \xi_i \\ & \xi_i \geq 0 \end{align}$$

ニューラルネットワーク

$$\min_{w} \quad \sum_{i=1}^n L(f(x_i; w), y_i) + \lambda R(w)$$

経済学・ファイナンス

ポートフォリオ最適化

$$\begin{align} \min_{x} \quad & x^T \Sigma x \\ \text{subject to} \quad & \mu^T x \geq r \\ & \sum_{i=1}^n x_i = 1 \\ & x \geq 0 \end{align}$$

実装例

Python実装（scipy.optimize）

import numpy as np
from scipy.optimize import minimize

def objective(x):
    """目的関数: f(x) = (x[0] - 1)^2 + (x[1] - 2)^2"""
    return (x[0] - 1)**2 + (x[1] - 2)**2

def constraint1(x):
    """不等式制約: x[0] + x[1] - 2 <= 0"""
    return 2 - x[0] - x[1]

def constraint2(x):
    """等式制約: x[0]^2 + x[1]^2 - 1 = 0"""
    return x[0]**2 + x[1]**2 - 1

# 制約の定義
cons = [
    {'type': 'ineq', 'fun': constraint1},
    {'type': 'eq', 'fun': constraint2}
]

# 初期値
x0 = np.array([0.5, 0.5])

# 最適化の実行
result = minimize(objective, x0, method='SLSQP', constraints=cons)

print(f"最適解: {result.x}")
print(f"最適値: {result.fun}")
print(f"収束: {result.success}")

MATLAB実装

function [x, fval] = solve_nonlinear_problem()
    % 目的関数
    objective = @(x) (x(1) - 1)^2 + (x(2) - 2)^2;
    
    % 不等式制約: x(1) + x(2) <= 2
    A = [1, 1];
    b = 2;
    
    % 等式制約: x(1)^2 + x(2)^2 = 1
    nonlcon = @(x) deal([], x(1)^2 + x(2)^2 - 1);
    
    % 初期値
    x0 = [0.5; 0.5];
    
    % 最適化
    options = optimoptions('fmincon', 'Display', 'iter');
    [x, fval] = fmincon(objective, x0, A, b, [], [], [], [], nonlcon, options);
end

高度なトピック

大域最適化

局所最適解に陥らない手法：

多点探索法

• 遺伝的アルゴリズム（Genetic Algorithm）
• 粒子群最適化（Particle Swarm Optimization）
• 差分進化（Differential Evolution）

決定論的手法

• 分枝限定法（Branch and Bound）
• 区間解析（Interval Analysis）

ロバスト最適化

不確実性を考慮した最適化：

$$\min_{x} \max_{u \in U} f(x, u)$$

確率制約

$$P(g(x, \xi) \leq 0) \geq 1 - \alpha$$

多目的最適化

複数の目的関数を同時に最適化：

$$\min_{x} \{f_1(x), f_2(x), \ldots, f_k(x)\}$$

パレート最適解の概念が重要

まとめ

非線形計画法の要点：

1. 問題の定式化: 目的関数と制約条件の適切な設定
2. 最適性条件: KKT条件による理論的基礎
3. 数値解法: 問題の性質に応じたアルゴリズムの選択
4. 実装: 実用的なソフトウェアツールの活用
5. 応用: 様々な分野での問題解決

実践的なアドバイス

• 問題の構造（凸性、分離可能性など）を理解する
• 制約条件の必要性を慎重に検討する
• 複数の初期値から最適化を実行する
• 解の妥当性を物理的・経済的観点から検証する

参考文献

1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization. Springer.
2. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
3. Bazaraa, M. S., Sherali, H. D., & Shetty, C. M. (2006). Nonlinear Programming: Theory and Algorithms. Wiley.
4. Bertsekas, D. P. (2016). Nonlinear Programming. Athena Scientific.