線形計画問題
Overview
与えられた制約の中で、ある関数の値を最大化（あるいは最小化）する問題を数理最適問題と呼びます。線形計画問題そのものは機械学習アルゴリズムで現れることはあまりないですが、数理最適化問題の基本を理解するには良い問題です。
Theory
例えば、下図の赤枠面積で3x+4yが最大になるような問題を考えます。この場合、図を見ると、大体、3x+4y=kが点(400, 200)を通過するときに最大値を取ることがわかります。
https://gyazo.com/78bb86fb2206e22a9426e3ff9ded3ad1
Coding
code: Python
import numpy as np
from scipy import optimize
# 目的関数の最小化を求める形にするために符号を反転する
c = np.array(-3, -4, dtype=np.float64) G = np.array(1, 4], 2, 3, [2, 1, dtype=np.float64) # bounds(上限、下限)
sol = optimize.linprog(c, A_ub=G, b_ub=h, bounds=(0, None))
print(sol.x)
print(sol.fun)
--------------------------------------------------------------------------
-2000.0
--------------------------------------------------------------------------