武蔵野個別指導塾の特徴

最適化理論　凸性とラグランジュ双対で「一番よい」を見つける｜武蔵野個別指導塾

公開 2026.10.13更新 2026.10.13武蔵野個別指導塾の特徴大学数学特集（解析・線形代数・代数・幾何・確率統計）

模擬店の仕入れ計画から、制約のある最小化を考えます。凸性、KKT条件、双対の意味を具体的な計算で確かめ、勾配降下法と機械学習へのつながりをたどれます。

最適化理論　凸性とラグランジュ双対で「一番よい」を見つける

模擬店の会計で「利益が最大」を言い切るには

学園祭の模擬店の会計を考える場面から始めましょう。机の上には仕入れ表、残った容器の束、販売個数を書き込む方眼紙があります。塾の講師がその紙の端に「売れそうな品を増やす」と書き、隣に「容器は足りるか」と添えたとします。利益だけを見て決めた仕入れ量が、材料や調理時間の制限を越えてしまうことがあります。一方、制限を守る案が見つかっても、それが一番よい案だとはまだ言えません。

最適化理論が扱うのは、この二重の問いです。まず、何を変えてよく、何を守らなければならないかを明確にします。そのうえで、許された案の中から目的に最も合うものを探します。さらに、得られた案よりよいものが存在しないという説明まで用意します。「かなりよさそう」と「これ以上よくならない」の間にある距離を、数式で埋める分野です。

高校数学にも、面積の最大値や費用の最小値を求める問題があります。大学では、変数が増え、制約が複数になり、計算機で近似解を求める場面へ進みます。そのとき、微分してゼロになる点を探すだけでは足りません。解が存在するか、見つけた点は近所でよいだけなのか、離れた場所にももっとよい点がないかを区別します。

その区別を支えるのが凸性です。また、制約に数を掛けて組み合わせると、どの案も越えられない限界を導けることがあります。この考えを一般化したものがラグランジュ双対です。最適化は、答えを出す計算と、答えの正しさを支える論理を同じ紙の上で結びます。

平方完成から、制約を持つ二変数へ

高校の二次関数で学ぶ平方完成は、最適性を証明する道具でもあります。例えば、費用を表す関数を C(x) = x² – 6x + 13 とすると、

C(x) = (x – 3)² + 4

です。実数の二乗は非負なので、すべての実数 x に対して C(x) ≧ 4 が成り立ちます。しかも x = 3 で等号が成立します。したがって、最小値は 4、最小値を与える x は 3 です。「これより小さくならない」と「実際にその値になる」を両方示していることに注目してください。

ところが、仕入れの都合で 0 ≦ x ≦ 2 と制限されていたら、x = 3 は選べません。この区間では x が 2 に近づくほど (x – 3)² が小さくなるため、最小値は x = 2 のときの 5 です。目的の式を正しく計算しても、変数の動ける範囲を忘れれば別の問題を解いてしまいます。

二次関数、数学II・IIIで扱う微分、数学B・Cなどで触れる数列やベクトルは、それぞれ最適化につながります。微分は改善する方向を調べる道具に、数列は反復計算を記述する言葉に、ベクトルは多数の変数をまとめる器になります。学習する科目や順序には違いがありますが、高校で別々に見えた内容が同じ問題の中で合流します。

ここで、模擬店の2種類の品を作る量を x、y としましょう。量はまとめて作る単位で測り、まず実数として扱います。1単位当たりの利益を共通の単位でそれぞれ 3、2 とし、容器と材料の制約を次のように設定します。

利益 P(x, y) = 3x + 2y

x + y ≦ 6、2x + y ≦ 8、x ≧ 0、y ≧ 0

最初の制約は合計量を、次の制約は最初の品が材料を多く使うことを表します。x だけを増やせば利益が増えるという見方では、y をどれだけ減らす必要があるかを見落とします。ここから先は、式を単独で眺めるより、複数の不等式が平面のどの領域を残すかを描くことが役立ちます。

境界線の交点を調べると、許された領域の頂点は (0, 0)、(4, 0)、(2, 4)、(0, 6) です。それぞれの利益は 0、12、14、12 になります。候補の中では (2, 4) が最良です。ただし、この比較だけを出発点にすると、「辺の途中や内部を調べなくてよいのか」が残ります。その疑問に答えるために、まず領域と関数の形を定義します。

凸性は「途中の案も許される」を数式にする

最適化問題の基本形は、集合 C に属する変数 z のうち、実数値関数 f(z) を最小にするものを求める、というものです。記号では「z ∈ C のもとで f(z) を最小化する」と書きます。f を目的関数、C を実行可能集合、C の要素を実行可能解と呼びます。最大化は -f の最小化に直せるため、理論の多くは最小化に統一して説明できます。ただし、利益の符号を変えたら最後に元の意味へ戻す必要があります。

実行可能集合は、例えば次のように表します。

C = {z ∈ Rⁿ : gᵢ(z) ≦ 0、i = 1, …, m、hⱼ(z) = 0、j = 1, …, r}

ここで Rⁿ は実数を n 個並べたベクトルの集合です。gᵢ は不等式制約、hⱼ は等式制約を表す関数です。添字は複数の制約を区別しています。制約は「都合がよければ守る条件」ではなく、今回の問題で許された案を定める条件です。

第一の重要な定義は凸集合です。集合 C が凸であるとは、任意の u、v ∈ C と任意の t ∈ [0, 1] に対して、

(1 – t)u + tv ∈ C

が成り立つことです。つまり、集合内の2点を結ぶ線分が丸ごと集合内に入ります。u と v が実行できる計画なら、その割合を混ぜた途中の計画も実行できる、という意味です。模擬店の制約はすべて一次不等式なので、両端で満たす不等式はその加重平均でも満たします。このため実行可能集合は凸です。

整数しか許さない場合には注意が必要です。0 と 1 という個数を半分ずつ混ぜた 0.5 は整数ではありません。したがって、一般に整数条件を加えた集合は凸ではありません。飲み物を何杯売るかという問題を、量を連続的に変えられる計画として解くのか、整数計画として解くのかは、最初に決めるべきモデルの違いです。先ほどの例は連続量として解いていますが、得られた最適解は整数でもあるため、同じ制約で整数に限定した場合にも使えます。

第二の定義は凸関数です。凸集合 C 上の関数 f が凸であるとは、任意の u、v ∈ C と任意の t ∈ [0, 1] に対して、

f((1 – t)u + tv) ≦ (1 – t)f(u) + tf(v)

が成り立つことです。グラフ上の2点を結ぶ線分より、途中の関数値が上へ出ないという条件です。集合の凸性は変数の許され方、関数の凸性は値の変わり方を述べています。形容する対象が違うので、「凸だから大丈夫」と言う前に、集合と関数のどちらを調べたかを確かめます。

例えば f(x) = x² の場合、右辺から左辺を引くと、

(1 – t)u² + tv² – ((1 – t)u + tv)² = t(1 – t)(u – v)² ≧ 0

になります。図の印象だけでなく、すべての u、v、t について定義を満たすことを示せました。一方、f(x) = -x² は凸ではありません。u = -1、v = 1、t = 1/2 を選ぶと、左辺は 0、右辺は -1 となり、必要な不等式が成立しないからです。凸でないことを示すには、定義に反する組を1つ見つければ十分です。

第三に、局所最小解と大域最小解を区別します。z₀ ∈ C が大域最小解であるとは、すべての z ∈ C に対して f(z₀) ≦ f(z) が成り立つことです。局所最小解であるとは、ある ε > 0 が存在し、z ∈ C かつ ||z – z₀|| < ε を満たすすべての z に対して f(z₀) ≦ f(z) が成り立つことです。||z – z₀|| はユークリッド距離です。局所という言葉は、「許された点のうち十分近いものと比較する」という範囲を指定しています。

この差は実際に起こります。区間 [-3, 2] 上の f(x) = x³ – 3x では、f′(1) = 0、f″(1) = 6 > 0 なので、x = 1 は局所最小解です。しかし f(1) = -2 に対し f(-3) = -18 なので、大域最小解ではありません。微分で見つけた谷が、領域全体で最も低い谷とは限らないのです。

目的関数が凸で、実行可能集合も凸である最小化を凸最適化問題と呼びます。よく使う十分条件は、目的関数と各不等式制約の gᵢ が凸で、等式制約の hⱼ がアフィン関数であることです。アフィン関数は一次式に定数を加えた関数です。等式を一般の凸関数で書くだけでは、実行可能集合の凸性は保証されません。

局所から大域へ進み、乗数で制約を扱う

凸最適化の中心となる定理を述べます。C を凸集合、f を C 上の凸関数とすると、C 上の局所最小解はすべて大域最小解です。微分可能性は仮定していません。角のあるグラフでも、凸性そのものが成り立てば適用できます。

証明の要は、もし局所最小解 u より値の小さい点 v があったら、u から v へ少しだけ動くことです。凸性から、その途中の点は実行可能で、0 < t < 1 に対して、

f((1 – t)u + tv) ≦ (1 – t)f(u) + tf(v) < f(u)

となります。t を十分小さくすれば途中の点は u のどれほど近くにも置けるので、u が局所最小解だという仮定に反します。線分で結べることと、途中の関数値を押さえられることが、ここで両方使われています。

ただし、この定理は解の存在を述べていません。例えば実数全体で f(x) = eˣ を最小化すると、値は正で、x を負の方向へ進めるほど 0 に近づきますが、0 にはなりません。下限はあっても最小値はありません。存在の確認には別の道具が必要です。実行可能集合が空でないコンパクト集合で、目的関数がその上で連続なら、最小値は達成されます。有限次元の実数空間では、コンパクトであることは閉かつ有界であることと同値です。

次に、等式制約のある微分を考えます。x + y = 6 のもとで f(x, y) = x² + y² を最小化しましょう。制約に沿った動きだけを許すため、単に ∇f = 0 とすると、実行不可能な原点を選んでしまいます。そこでラグランジュ関数を作ります。

L(x, y, ν) = x² + y² + ν(x + y – 6)

x、y による偏微分をゼロにし、制約も一緒に解きます。

2x + ν = 0、2y + ν = 0、x + y = 6

初めの2式から x = y となり、x = y = 3、ν = -6 を得ます。目的関数値は 18 です。大域的な最小性は、制約上で次の恒等式を使えば確かめられます。

x² + y² = ((x + y)² + (x – y)²)/2 = 18 + (x – y)²/2 ≧ 18

乗数法は候補を出し、最後の不等式はその候補よりよい点がないことを示しています。一般に、目的関数と等式制約が候補点の近傍で連続微分可能で、局所最適点における制約の勾配が一次独立なら、目的関数の勾配と制約の勾配の線形結合がゼロになる乗数が存在します。この正則性の仮定を外すと、乗数による必要条件がその形では使えない場合があります。

不等式まで含めると、KKT条件と呼ばれる条件が現れます。先ほどの gᵢ(z) ≦ 0、hⱼ(z) = 0 という書き方に対し、

L(z, λ, ν) = f(z) + ∑ᵢ λᵢgᵢ(z) + ∑ⱼ νⱼhⱼ(z)

と置きます。微分可能な場合のKKT条件は、実行可能性、λᵢ ≧ 0、停留条件 ∇f(z) + ∑ᵢ λᵢ∇gᵢ(z) + ∑ⱼ νⱼ∇hⱼ(z) = 0、そして相補性条件 λᵢgᵢ(z) = 0 です。相補性は各 i ごとに課します。制約が厳密に余っているなら、その乗数はゼロになります。ただし、等号で成り立つ制約の乗数が必ず正になるわけではありません。

非凸の問題では、KKT条件を満たすことだけで大域最適とは言えません。一方、Rⁿ 上で微分可能な f と各 gᵢ が凸、各 hⱼ がアフィンである問題では、KKT条件を満たす実行可能点は大域最小解です。理由は、その乗数を固定した L が凸で停留しているため、その点で全体の最小値をとり、相補性により L の値と f の値が一致するからです。別の実行可能点での L は f 以下なので、この点の f より小さな目的関数値は出せません。

この十分性と、最適解がKKT条件を満たすという必要性は別です。同じ凸問題で最適解が存在し、等式制約を満たしつつすべての不等式を厳密に満たす点が存在すれば、スレーター条件という制約想定が成り立ち、最適解に対応するKKT乗数が存在します。ここでは各関数が Rⁿ 全体で定義された微分可能な場合を考えています。式を暗記するだけでなく、必要条件として使う際の仮定まで読むことが欠かせません。

線形計画法の頂点と、計算方法を育てた研究

目的関数と制約が一次式で書ける問題が線形計画問題です。実行可能集合は半空間や超平面の共通部分となり、凸です。とくに、空でない有界な多面体上で線形関数を最大化または最小化すると、少なくとも1つの頂点で最適値が達成されます。多面体の点は頂点の凸結合で表せるため、線形関数の値も頂点での値の加重平均になる、というのが理由です。辺全体が同じ最適値を持つこともあり、最適解が頂点だけに限られるという主張ではありません。

模擬店の例で頂点を比較できたのは、この仕組みによります。さらに、2本の資源制約をそのまま足すと、

3x + 2y = (x + y) + (2x + y) ≦ 6 + 8 = 14

となります。(2, 4) は両方の制約を等号で満たすので、利益 14 を実現します。全案に共通する上限と、上限に届く案が一致しました。頂点を列挙しなくても、短い式が最適性の証明になります。

単体法は、多面体の頂点に対応する基本実行可能解を、変数の入れ替えによって移っていく方法です。この例なら、まず (0, 0) から y を増やして (0, 6) に進み、次に x を増やしながら x + y = 6 を保つと、(2, 4) に着きます。途中の利益は 0、12、14 と変わります。制約の余りを s₁、s₂ とすると、

x + y + s₁ = 6、2x + y + s₂ = 8

です。最終点に対応する形へ整理すると、

x = 2 + s₁ – s₂、y = 4 – 2s₁ + s₂、P = 14 – s₁ – s₂

となります。余りは非負なので、ここからも 14 を超えないことが読めます。一般の単体法では、退化によって変数を入れ替えても点や目的関数値が変わらないことがあり、適切な規則なしには巡回する可能性もあります。「毎回必ず利益が増える」という説明では、実際の計算の難しさを落としてしまいます。

線形計画の研究では、こうした計算手順の改善と、現実をどうモデル化するかという課題が並んで育ってきました。Dantzigの1956年の論文は、不確実性、組合せ問題、大規模システムという3つの話題を取り上げ、線形計画の技術を利用へつなぐための展開を論じています（Dantzig, 1956）。資源配分の式を書けることと、多数の制約や不確かな需要を含む計画を実用的に解けることは、異なる段階なのです。

退化への対応に焦点を当てた研究として、Dantzigの1989年の論文があります。ここでは、目的関数にパラメータを含む項を加える考えを利用して、線形計画の退化を扱う規則が提案されています（Dantzig, 1989）。この研究を、すべての計算停滞が単純に消えるという意味で受け取るのではなく、目的値が変わらない局面にも手順の設計が必要だと読むと、単体法の理解につながります。

別の方向を示すのが、線形計画に対する多項式時間の内点法を論じた研究です（Karmarkar, 1984）。単体法のように頂点をたどる方法とは異なり、内点法は内部の点を利用して計算を進めます。多項式時間という評価では、変数の数だけでなく、入力を表すビット数も計算量の評価に入ります。ある小さな問題を速く解けたという観察と、入力が大きくなるときの最悪の場合を抑える理論は、区別して考える必要があります。

双対で限界を測り、勾配で予測式を調整する

模擬店の上限の計算を一般化しましょう。最小化問題に対し、λᵢ ≧ 0 を固定して、ラグランジュ関数を変数 z 全体について下から評価した関数を作ります。

q(λ, ν) = inf {L(z, λ, ν) : z ∈ Rⁿ}

これが双対関数です。inf は下限を表し、その値を与える z が存在しない場合も含めます。実行可能な z では、不等式制約に非負の乗数を掛けた項が非正、等式制約の項がゼロになるため、q(λ, ν) ≦ L(z, λ, ν) ≦ f(z) です。したがって q は元の最小値の下界になります。下界をなるべく大きくする問題がラグランジュ双対問題です。この弱双対性には、元の問題の凸性は必要ありません。

元の問題の最適値と双対問題の最適値が等しいことを強双対性と呼びます。単に凸という言葉だけで常に保証するのではなく、先ほどのスレーター条件などを確認します。強双対性が成り立ち、双方で最適解を得られれば、実行可能解の目的関数値と双対の下界が一致し、これ以上改善できないことを数値で確かめられます。途中でも、両者の差は実行可能解が最適値からどれだけ離れうるかの上限になります。

具体的に、x ≦ 1 のもとで f(x) = (x – 3)² を最小化します。ラグランジュ関数は L(x, λ) = (x – 3)² + λ(x – 1)、λ ≧ 0 です。平方完成すると、

L(x, λ) = (x – 3 + λ/2)² + 2λ – λ²/4

なので、q(λ) = 2λ – λ²/4 です。さらに q(λ) = 4 – (λ – 4)²/4 と変形でき、双対側の最大値は λ = 4 で 4 になります。元の問題では x = 1 が実行可能で f(1) = 4 なので、双方の値が一致します。停留条件 2(x – 3) + λ = 0 と相補性 λ(x – 1) = 0 も成立します。境界上の最適点では f′(1) = -4 であってもよく、制約の乗数がその傾きを釣り合わせています。

資源配分では、乗数は制約の厳しさを考える手掛かりにもなります。ただし、制約の右辺を変えたときの最適値の変化率として読むには、その点での微分可能性などが必要です。模擬店で示した係数 1 と 1 は、少なくとも今の制約から利益の上限を作る重みとして解釈できます。資源が増えれば永遠に同じ割合で利益が伸びるという意味ではありません。

需要が事前に確定しない場合には、計画の段階そのものも変わります。Dantzigの1955年の論文は、活動を複数の段階に分け、後の段階の活動は前の決定や不確実な需要に依存するというモデルを扱っています。また、前の段階で許される決定をした後にも、後の段階で実行可能な選択が残るという想定が置かれています（Dantzig, 1955）。模擬店に引き寄せれば、開店前の仕入れと、売れ行きを見て行う追加の対応を分けて考える発想に対応します。これは論文の数値例の紹介ではなく、段階を分ける意味を理解するための読み替えです。

情報分野では、予測式の係数を調整する問題として最適化に出会います。例えば、入力が 1 と 2、対応する目標値が 1 と 2 で、予測式を wx としましょう。二乗誤差に係数を大きくしすぎないための項を加えた目的関数は、λ ≧ 0 に対して、

J(w) = (w – 1)² + (2w – 2)² + λw² = 5(w – 1)² + λw²

です。微分すると J′(w) = 2(5 + λ)w – 10 なので、最適な係数は w = 5/(5 + λ) です。λ = 0 なら w = 1、λ = 5 なら w = 1/2 になります。後者では観測された点への一致より、係数を小さくする条件も重視しています。目的関数を変えると、「一番よい」の意味が変わることを具体的に確認できます。この小さな計算だけで、新しいデータへの予測が改善するとまでは言えません。

変数が多くなり、解の式を直接求めにくいときに使う基本的な反復が勾配降下法です。更新式は、ステップ幅 α > 0 を使って、

zₖ₊₁ = zₖ – α∇f(zₖ)

と書きます。勾配は局所的に値を増やす方向を表すため、その反対へ動きます。ただし、どれほど遠くへ進んでも下がり続けるわけではありません。f(x) = (x – 3)²、α = 1/4、x₀ = 0 では、xₖ₊₁ = xₖ/2 + 3/2 となり、x₁ = 1.5、x₂ = 2.25、x₃ = 2.625 と進みます。誤差 xₖ – 3 は1回ごとに半分になり、関数値は1回ごとに1/4になります。

一般の α では、誤差の更新は xₖ₊₁ – 3 = (1 – 2α)(xₖ – 3) です。この例では 0 < α < 1 のときに誤差の絶対値が縮みますが、α = 1.1 なら毎回 1.2 倍になります。凸な関数でも、歩幅を誤れば反復は収束しません。また、この更新式だけでは制約を守る保証はなく、制約つき問題では実行可能集合への射影などの工夫が要ります。機械学習でも、目的関数が凸か、制約があるか、勾配を正確に計算するかで、使える保証が変わります。

解法を選ぶ前に、条件と証明を分けて学ぶ

最適化でつまずきやすいのは、計算の難しさだけではありません。「微分がゼロなら最小」「候補をいくつか比べれば最適」「計算機が止まれば正解」という、異なる主張の取り違えが起こります。例えば f(x) = x を [0, 1] 上で最小化すれば、最小解は端点の 0 で、微分は 1 のままです。微分がゼロという必要条件は、微分可能な関数の定義域の内点で、制約なしの局所最適を考える場合の話だと読み直します。

微分だけに頼らない見方も役立ちます。Boltは、不等式を使う変分的な方法で最適化を扱い、投げられた球を犬が回収する時間の最小化などを例に、微分を使わない解法を示しています（Bolt, 2010）。また、Teagueは、集団の中の少数の陽性者を見つけるグループ検査の最適化問題について、微積分とモデリングを学ぶ学生が考えた複数の解法を紹介しています（Teague, 2006）。前者は数学的な解法の提示、後者はその学生たちの解法の紹介であり、両者から高校生一般への学習効果を断定することはできません。それでも、同じ目的を異なる道具で捉え直す学び方を考える材料になります。

学習の手順は、次の4段階に分けると、どこで論理が抜けたかを見つけやすくなります。

変数、単位、目的関数、制約を文章と式で対応させます。最小化と最大化の向きを決め、整数条件の有無も書きます。「利益を増やす」と書いたのに、式が売上だけを表していないかも点検します。
実行可能集合を調べます。空ではないか、閉じているか、有界か、凸かを区別します。二変数なら境界と交点を描き、図で気づいた性質を不等式でも確かめます。
候補を求める方法と、最適性を保証する方法を分けて選びます。微分や乗数法で候補を出し、平方完成、凸性、双対の限界などで全体との比較を行います。KKT条件を使うなら、その必要性や十分性を支える仮定を横に書きます。
元の意味へ戻して検算します。候補をすべての制約に代入し、目的関数値を求め、近似なら残っている誤差や制約違反も調べます。反復の隣り合う値が近いという事実だけでは、最適値に近いとは限りません。

高校生のうちには、同じ二次関数を平方完成と微分の両方で解き、どちらの行が「最小であること」を示すのか説明する練習ができます。次に、変数の範囲を変え、頂点が範囲の外へ出ると答えがどう変わるかを追います。計算量を急に増やすより、解答で使った条件に下線を引くほうが、大学の定理を読む準備になります。

塾でこの題材を扱うなら、模擬店の会計表の余白に、利益の式と容器の制約を別々に書くところから始めます。講師はすぐに最適な個数を伝えるのではなく、提案された仕入れ量がどの行の条件に触れるかを一緒に確かめます。その後、別の案を試す作業から、すべての案を一度に抑える不等式へ進みます。個別の数字と一般的な証明を往復する時間を設けます。

家庭では、お子さまが解法名を言えるかだけでなく、「どの条件を守った答えなのか」を短く説明できるかに耳を傾けられます。新しい記号をその場ですべて説明し直す必要はありません。式と日本語を行き来するための落ち着いた時間を持ち、計算ミスと条件の読み違いを本人が分けて振り返れるようにすることが、学習を支えます。

ここで手が止まるなら、止まった単元まで一緒に戻ります。武蔵境の数学塾（1 対 1）／お問い合わせ

最適化を学び始めるときの3つの疑問

微分が苦手でも最適化を学べますか

はい。平方完成や一次不等式による上限の証明から入れます。模擬店の利益が 14 を超えないことは、制約を足すだけで示せました。ただし、大学で多変数の問題や反復法を扱うには、偏微分と勾配の理解が必要になります。最初からすべての微分計算を終えておくより、必要になった場面で、その記号が何を測っているかを確かめて進めましょう。

凸なら答えは必ず1つですか

必ずしもそうではありません。例えば定数関数を区間上で最小化すれば、その区間のすべての点が最小解です。凸性が保証するのは局所最小解の大域的な最小性であり、一意性そのものではありません。異なる2点と 0 < t < 1 に対して凸関数の定義の不等号が厳密になる性質を狭義凸性と呼び、凸集合上の狭義凸関数には最小解が存在すれば1つしかありません。2つあると、その途中でさらに小さな値を取ってしまうからです。

コンピュータが答えを出すなら証明は不要ですか

計算結果をどう受け取るかを決めるために、証明の考え方が要ります。候補が制約を満たすか、下界や上界との差はどれほどか、打ち切り条件は何かを読めなければ、小さな変化で止まった反復と、最適性を確かめた解を区別できません。多くの理系学部では1〜2年で学ぶ微分積分や線形代数が、その読み取りの基礎になります。最適化を専門的に学ぶ時期には違いがあっても、条件を丁寧に読む姿勢は共通です。

会計表に書き込まれた1組の仕入れ量には、それを選んだ理由が必要です。目的関数は何をよしとするかを明らかにし、制約は選べる案を定め、凸性は近くの比較を全体の比較へつなぎます。乗数と双対は、候補に届く限界を添えます。方程式を解いたあとに、その答えが許されるか、よりよい答えがないかを自分の言葉で確かめるところまで進みましょう。「一番よい」と書くための根拠は、候補を得た先にある比較の論理から生まれます。

あわせて読む（数学の地図・高校数学の単元解説）

参考文献

George B. Dantzig（1955）「Linear Programming under Uncertainty」Management Science. https://doi.org/10.1287/mnsc.1.3-4.197
George B. Dantzig（1956）「Recent Advances in Linear Programming」Management Science. https://doi.org/10.1287/mnsc.2.2.131
George B. Dantzig（1989）「Making progress during a stall in the simplex algorithm」Linear Algebra and its Applications. https://doi.org/10.1016/0024-3795(89)90464-3
N. Karmarkar（1984）「A new polynomial-time algorithm for linear programming」Combinatorica. https://doi.org/10.1007/bf02579150
Mike Bolt（2010）「Dogs Don’t Need Calculus」College Mathematics Journal. https://doi.org/10.4169/074683410×475074
Daniel Teague（2006）「Group Testing: Four Student Solutions to a Classic Optimization Problem」College Mathematics Journal. https://doi.org/10.1080/07468342.2006.11922193