最適化問題

目次 最適化問題は、与えられた問題のことを主問題。 主問題の制約条件から目的関数を導入した双対問題から構成されます。 本日はそんな双対問題について説明していきます。 主双対問題とは 最適化における 「双対性（Duality）」 は、ある問題を 「別の視点」 から眺めることを指します。 元々の問題を 「主問題（Primal Problem）」 、それと表裏一体の関係にある問題を 「双対問題（Dual Problem）」 と呼びます。 1. 視点の違い：生産者 vs 資源価値 先日のジュース工場の例を使うと、非常に直感的に理解できます。 先日のジュース工場の例 読者の方は一旦、ジュース工場の店長だ…

目次 最適化（Optimization）の世界は非常に奥が深いですが、その根底にあるのは「限られたリソースの中で、最善の結果を導き出す」というシンプルな目的です。 数学や工学、あるいはビジネスの文脈で最適化を理解するために、特に重要な概念と、事実上の「公理」として扱われる考え方を整理の上、問題の具体例で説明してみます。 概念 最適化を行う上で重要な概念について整理します。 1. 最適化の3要素（定式化の基本） どんな最適化問題も、まずは以下の3つの要素に分解して考えることから始まります。これらを定義できないと、最適化はスタートしません。 意思決定変数（Variables）: 自分がコントロール…

目次 目的関数が微分不可能な凸関数である場合勾配を定義できないということになります。 こんなケースで凸関数を最小化したい場合に取りえる方法が劣勾配法（subgradient method）という手法です。 劣勾配法 劣勾配法は、微分不可能な凸関数を最小化するための最適化アルゴリズムです。勾配降下法を「微分不可能な関数」に拡張したもの、と考えるとイメージしやすいです。 1. 劣勾配の定義 凸関数 fff の点 xxx における劣勾配集合 ∂f(x)\partial f(x)∂f(x) は、 ∂f(x)={g∣f(y)≥f(x)+g⊤(y−x) for all y}\partial f(x) = …

LayerX のバクラク事業部の AI・機械学習部で機械学習エンジニアをしている島越（@nt_4o54）です。こちらはLayerX AI Agent ブログリレー 31 日目の記事です。 昨日は松村 (@yu__ya4)による「Langfuse の Experiment Runner SDK を利用した AI エージェント機能の性能評価と実験管理」でした。 無事にこのブログリレーも日付換算で一ヶ月を突破しました。過去のブログ記事も知見が溢れているので、是非ご覧ください！ はじめに LLM 以前の機械学習システムにおけるパーソナライゼーション LLM を用いたシステムにおけるパーソナライゼーショ…

以下は、近年の実務現場や学術研究で広く検証された（数値実験やベンチマークに基づく）実用的な組合せ最適化問題の例と、その各問題に対して実績のある state‐of‐the‐art (SOTA) 解法（宣伝的な手法や比較が不十分なものは除外）をまとめた表の一例です。なお、以下に挙げた解法は問題の定式化や規模、実務上の要件により最適解法が変化するため、代表例として理解してください。 実用的な問題 問題概要・用途 SOTA解法例 数値実験・比較実績・備考 巡回セールスマン問題 (TSP) 各都市間の移動コストが与えられ、全都市を一度ずつ訪問して出発地へ戻る最短路を求める。 Concorde TSP S…

はじめに 本記事は NTTドコモ Advent Calendar 2024 の12日目の記事です。 こんにちは。NTTドコモサービスイノベーション部の淺田です。 普段はデータ分析・AI技術を活用した業務効率化や意思決定支援を行っています。 今回のテーマ「需要予測と新聞売り子問題による在庫最適化」は、私が業務の中で取り組んでいる課題の一つである在庫の最適化を基にした内容です。 目次 はじめに 目次 概要 対象読者 新聞売り子問題とは 概要 機械学習モデルによる将来の需要推定量を用いる場合 Pythonプログラムによる在庫最適化の実装 問題設定 初期設定 サンプルデータの作成 シミュレーション用デ…

＜最適化問題の概要＞ ＜最短経路問題の解説＞ ＜動的計画法の解説＞ ｜まとめ（最適化問題、最短経路問題、動的計画法） 数値計算は、コンピュータを利用して数値的な方法で数式やデータを解析し、問題の解決や最適化を行う手法です。 ここでは、数値計算の中で重要な要素となる「最適化問題」、「最短経路問題」、「動的計画法」の３つをそれぞれ解説していきます。 【令和５年度】 いちばんやさしい 基本情報技術者 絶対合格の教科書＋出る順問題集 作者:高橋 京介 SBクリエイティブ Amazon ＜最適化問題の概要＞ 最適化問題とは、特定の目的を達成する際に、与えられた制約条件の下で最適な解を見つける問題のことで…