# Juliaによる数値計算

## 数理最適化

- **数理最適化**:
    - 与えられた制約の中で、ある関数の値を最大化（あるいは最小化）すること
    - 現実の問題のポイントを整理して数式で表し、数式にあった解法（アルゴリズム）で最適な解を求める
    - 数理最適化は、意思決定にかかわる科学的アプローチであるオペレーションズリサーチの一分野として発展してきたが、今日においては社会にとって欠かせない技術の一つである

ここでは、機械学習アルゴリズムでよく使われる数理最適化手法を見ていく

### 線形計画問題
線形計画問題そのものは機械学習アルゴリズムの中で現れることはあまりないが、数理最適化問題の基礎となる問題であるため、ここで軽く触れておく

次のような問題を考える

---

ある工場では製品 X, Yを製造している

これらは原料 A, B, C から作られており、それぞれの製品1個（1単位）を作るのに必要な原料（kg）は次の表である

$$
\begin{array}{cccc}
& A & B & C \\ \hline
X & 1 & 2 & 2 \\ \hline
Y & 4 & 3 & 1
\end{array}
$$

工場の倉庫にある原料の量（kg）は次の表のとおりである

$$
\begin{array}{ccc}
A & B & C \\ \hline
1700 & 1400 & 1000
\end{array}
$$

製品 X, Y を売ると、それぞれ利益は1つあたり3ドルと4ドルになる

このとき、利益を最大化するには X, Y をそれぞれどれだけ製造すれば良いか

---

ここでは話を簡単にするため、製造する量は整数とは限らないとする

これを式で表してみる

まず製品 X と Y を製造する量をそれぞれ $x$, $y$ とおくと、このとき使われる原料 A は $x+4y$ となるため、原料 A の在庫についての制約から、

$$
x + 4y \leq 1700
$$

となる

同様に原料 B, C について考えると、以下の式を得ることができる

$$
\begin{align}
2x + 3y &\leq 1400 \\
2x + y &\leq 1000
\end{align}
$$

また、各製品の製造量は 0 以上である必要があるため、

$$
x \geq 0,\ y \geq 0
$$

となる

これらの制約条件のもと、利益 $3x+4y$ を最大化するという問題である

以上のことをまとめて次のように書くことがある

$$
\begin{align}
\rm{Maximize} \quad & 3x + 4y \\
\rm{Subject\ to} \quad & x + 4y \leq 1700 \\
& 2x + 3y \leq 1400 \\
& 2x + y \leq 1000 \\
& x \geq 0 \\
& y \geq 0
\end{align}
$$

上記のように最適化したい関数を先に記述し、最大化したいのか最小化したいのかを $\rm{Maximaize}$ または $\rm{Minimize}$ で表す

ここに書かれる関数を **目的関数** と呼ぶ

目的関数の後ろに $\rm{Subject\ to}$ で制約式を書くことになる

ここでは $x$ と $y$ の値を変化させるが、これらは **変数** と呼ばれ、制約式を満たすような変数の値を **実行可能解** と呼ぶ

また、目的関数を最適化（最大化もしくは最小化）する変数の値を **最適解** と呼び、その時の目的関数の値を **最適値** と呼ぶ

変数を明示したい場合は、目的関数を $\rm{Maximize}_{x, y}\ 3x+4y$ のように記述する

今回のように、目的関数も制約式も1次式（つまり線形）である最適化問題を特に **線形計画問題** と呼ぶ

制約式を満たす領域を図示すると以下のようになる



上図の赤色部分の点は境界線上の点も含めて、全て実行可能解ということになる

最適解を求めるには、この赤色領域について目的関数 $3x+4y$ が最大となる点を見つければ良い



ここでは任意定数 $k$ について $3x+4y=k$ を満たす点の集合を考えてみる

$3x+4y=k$ を満たす点の集合は直線になるが、$(x,y)$ が赤色領域内にあるとき $3x+4y$ を最大化する問題は、つまり直線 $3x+4y=k$ が赤色部分を通過するという条件で $k$ を最大化するという問題と言える

$k$ を変えていったとき、$3x+4y=k$ で表される直線群は全て平行になるため、これは $3x+4y$ の等高線であると見なすことが出来る

従って、直線を平行にずらしていきながら、ぎりぎり赤色部分と共有点をもつ場合を考えれば良いことになる

今回の場合は、図より $3x+4y=k$ が点 $(400,200)$ を通過するときが最適解であり、これを $x$, $y$ に代入して $3\times400+2\times400=2000$ が最適値となる

#### 線形計画法の一般型
ここまでは例として2変数の場合の線形計画問題を見てきたが、一般には$n$変数の場合の線形計画問題を考えることが出来る

$n$次元ベクトル $\boldsymbol x$ を変数とすると、線形計画法の一般型は次のように表される




```julia

```

309dca86babb7ded209a1141e81928beae745faf
ipynb
Jupyter Notebook
02_machine-learning/03-04_optimization.ipynb
amenoyoya/julia_ml-tuto
9c0be0923ea00ca4d1d51c0c6f61f6f2748232be
MIT
02_machine-learning/03-04_optimization.ipynb
amenoyoya/julia_ml-tuto
9c0be0923ea00ca4d1d51c0c6f61f6f2748232be
MIT
02_machine-learning/03-04_optimization.ipynb
amenoyoya/julia_ml-tuto
9c0be0923ea00ca4d1d51c0c6f61f6f2748232be
MIT
Qwen/Qwen-72B
1. YES
2. YES