mokazaka220

データサイエンス関連の勉強中です。 今までは機械学習について勉強していました。 業務で…

mokazaka220

データサイエンス関連の勉強中です。 今までは機械学習について勉強していました。 業務で数理最適化を使った方がよいのでは？と思うような事例がいくつかあったので、最近数理最適化の勉強を始めました。 自分の理解度を深めるため、noteにまとめていきたいと思います。

数理最適化（双対問題と双対定理①）

今回は双対定理についてまとめていきます。 最適化問題でよく登場してきます。 相対問題とは主問題（元の解くべき問題）に対し、新たに定義した表裏の関係にある問題のことを双対問題と呼びます。 主問題が以下の場合を考えます。 目的関数 $$ 最大化 c^{\top}x $$ 制約条件 $$ ax \leq b\\ x \geq 0 $$ これの、双対問題は、以下となります。 目的関数 $$ 最小化 b^{\top}y $$ 制約条件 $$ a^{\t

mokazaka220

    • 数理最適化（単体法②）

      今回は例題を解きながら単体法の解き方の流れを見ていきます。 例題を解いてみる単体法の概略を知るために、オペレーションズリサーチ学会の入門解説を使って、流れを見ていきたいと思います。 例題 目的関数を最小化する。 $$ u = −x_1 − x_2\\ $$ 制約条件 $$ 2x_1 + x_2 \leq 6\\ x_1 + 3x_2 \leq 8\\ x_1 \geq 0, x_2 \geq 0 $$ 解いていきます この制約条件を、標準系に変換します。

      mokazaka220

      • 数理最適化（単体法①）

        単体法（Simplex method）についてまとめていきたいと思います。 単体法は、線形計画問題を解くための方法の1つです。 長年にわたって使用されている実用的な方法です。 単体法が使われる理由・高速に解を見つけることができる ・アルゴリズムが理解しやすい ・さまざまな制約条件や目的関数に対応できる 線形計画問題は、目的関数と呼ばれる線形関数を最大化または最小化する問題です。 この問題のキーポイントは、解が凸多角形（すなわち凸集合）の頂点の一つに存在するということです。

        mokazaka220

        • 数理最適化（線形計画問題④）

          区分線形凸関数最小化問題の定式についてまとめていきます。 定式区分線形凸関数最小化問題の定式はこちらです。 $$ min f(x) = \displaystyle\max_{i=1,2…,m-1} \lbrace{\cfrac{f(a_{i+1}) - f(a_i)}{a_{i+1} - a_i}(x - a_i) + f(a_i)} \rbrace\\ a_1 \leq x \leq a_m $$ 最小化を求める問題なので、「min」はわかりますが、途中にいる「m

          mokazaka220

        数理最適化（双対問題と双対定理①）

        mokazaka220

          数理最適化（線形計画問題③）

          今日は非線形計画問題を線形計画問題で近似して解くということについてまとめていきたいと思います。 非線形計画問題非線形計画問題は、非線形計画関数の最小化もしくは最大化を解く問題です。 非線形関数とは 非線形関数は、一次関数（直線）ではない関数のことです。 例えば、二次関数のような直線ではない関数です。 凸関数（とつかんすう） 二次関数のように上下どちらかに出っ張った関数です。 山形の関数を、上に凸な関数と呼びます。 上の図のように、Uの字型の関数を下に凸な関数と呼びま

          mokazaka220

          数理最適化（線形計画問題③）

          mokazaka220

          数理最適化（線形計画問題②）

          線形計画問題の定式化をいくつか見ていきたいと思います。 生産計画問題・○○製造会社は、複数の製品を生産している 製造会社の清算効率を最大化し、コストを最小化したいという問題です。 問題 ・M：製品の数 ・T：製造会社の生産可能な総時間 ・R：利用可能な総資源量 ・ci：製品 i の単位時間当たりのコスト ・di：製品 i の需要量 ・pi：製品 i 1個当たりの販売価格 ・ti：製品 i 1個当たりの生産時間 ・ri：製品 i 1個当たりの資源量 ・xi：製品 i の生

          mokazaka220

          数理最適化（線形計画問題②）

          mokazaka220

          数理最適化（線形計画問題①）

          線形計画問題は、次の特徴を持つ最適化問題です。 ・目的関数が線形 ・変数が0以上 ・全ての制約条件が線形の等式、不等式で表現できる ・目的関数を最大化、または最小化する問題 線形とは一次関数を示します。 一次関数とは、y = ax + b の形で表される関数です。 変数 x に対して、係数（定数）のみを掛けている関数です。 ナップサック問題が線形問題です。 品物Aと品物Bをナップサックに入れるとします。 重さをw、品物の個数（変数）をx、ナップサックに入れた品物の総重量を

          mokazaka220

          数理最適化（線形計画問題①）

          mokazaka220

          数理最適化（モデリング言語とソルバー）

          組み合わせ問題を深堀していく前に、モデリング言語とソルバーというものについてまとめてみます。 （勉強していたらこの言葉が出てきたので、何だろうと思い調べました） モデリング言語数理最適化問題を「人が書きやすく・わかりやすい」形式で表現するための言語です。 モデリング言語の種類 モデリング言語の種類もいくつかあります。 ・AMPL ・PuLP ・PICOS ・Pyomo ・CVXOPT ・JuMP などなど。 モデリング言語の違い 何が違うんだろうと調べてみると、「対

          mokazaka220

          数理最適化（モデリング言語とソルバー）

          mokazaka220

          数理最適化（組み合わせ最適化）

          今回は組み合わせ最適化についてまとめていきます。 私がこれから解決していきたい問題が組み合わせ問題なので、初めにこちらを調べていきたいと思います。 組み合わせ最適化とはあらためておさらいです。 組み合わせ最適化は、離散的な値を取る最適化問題のことを指します。 離散的な値とは、[0, 1, 3, ・・・] というようにとびとびの数値のことを言います。 有名な問題に、ナップサック問題というのがあります。 ナップサックに食料や道具等の物品を詰める際、ナップサックの許容重量範囲内で

          mokazaka220

          数理最適化（組み合わせ最適化）

          mokazaka220

          数理最適化とは③

          基本的用語についてもう少し理解をはっきりさせておきたいので、「目的関数」「変数」「制約条件」について例を交えてまとめたいと思います。 おさらい数理最適化とは①で、↓のようにまとめました。 目的関数：最大化あるいは最小化したい関数 決定変数(変数)：目的関数を最適化するために決めたい変数 制約条件：最適化するうえで満たさないといけない条件 これを、具体的な例を当てはめてみていきます。 例は、わかりやすく「ナップサック問題」を使います。 ナップサック問題ナップサック問

          mokazaka220

          数理最適化とは③

          mokazaka220

          数理最適化とは②

          前回に引き続き、機械学習との違いについて調べてみました。 自分なりにすっきりしたのでまとめます。 違い１：モデルの作り方・機械学習：ラベル付けされたデータを使って学習し、モデルを作成 ・数理最適化：ルールからモデルを作成 機械学習は、過去のデータを使って学んだ結果から予測するものです。 そのため、モデルを作るためには、過去データが必要です。 数理最適化はルールが決まっていればモデルを作ることができるため、過去データは必要ありません。 下記ページでは「最適化といえば”目的関

          mokazaka220

          数理最適化とは②

          mokazaka220

          数理最適化とは①

          データサイエンスの数理最適化について勉強していきたいと思います。 （勉強のメモがてらまとめていく） 数理最適化とは？「ある条件下で、集合の中から最もよさそうなものを選択すること」を数理最適化と呼びます。 データサイエンス内の立ち位置は、三好さんの図がわかりやすいです。 　※参照：AI・データサイエンスにおける技術群 言葉にすると難しそうな気がしますが、「私たちが日常やっている選択」を「数式を使って選択する」のが、数理最適化になります。 例えば、子供にお小遣いを500円あ

          mokazaka220

          数理最適化とは①

          mokazaka220

          データサイエンス

          データサイエンス関連を勉強中です。 （現在機械学習を勉強中。数理最適化も開始。） 改めて、データサイエンスってなんだっけ？と思ったのでまとめてみます。 データサイエンスとは人によって異なりますが、大枠は「データを元に、有益な指標を導き出すもの」という解釈が多いです。 ただ、単純なデータ分析だけを示すものではなく、範囲は幅広いです。 データの集計から統計、機械学習、数理最適化なども含めてデータサイエンスに含まれます。 データに関する最初から最後までをひっくるめて、データサイエ

          mokazaka220

          データサイエンス

          mokazaka220