数理計画　～目次～

# はじめに
数理計画の凸最適化を中心に良記事と思われるURLを記載しました。
補足的な事項を記事として書いていこうと思います。

# 線形計画問題(LP)

線形計画は式1で記述される。

```math
\begin{eqnarray}
\min &  &c^Tx \\
s.t. & &Ax=b\\
     & &x\geq 0
\end{eqnarray}
\tag{1}
```

参照

- [数理計画法～線形計画法をPythonで実装～](https://qiita.com/momo10/items/824c2fd8a0f432a676f4)
- [半正定値計画による線形計画](https://qiita.com/momo10/items/ca8aa50a0a4985d63e97)
- [学習・研究用テキスト(水野眞治先生)](http://www.me.titech.ac.jp/~mizu_lab/text.html)

# 二次計画問題(QP)

二次計画は式2で記述される。

```math
\begin{eqnarray}
\min &  &\dfrac{1}{2}x^TQx+c^Tx \\

s.t. & &Ax=b\\
     & &x\geq 0
\end{eqnarray}
\tag{2}
```


参照

- [凸最適化の概要と主双対内点法のアルゴリズムの解説](https://qiita.com/taka_horibe/items/0c9b0993e0bd1c0135fa)
- [内点法による二次計画法](https://qiita.com/shiro-kuma/items/a51f44f209b6f935787a)
- [学習・研究用テキスト(水野眞治先生)](http://www.me.titech.ac.jp/~mizu_lab/text.html)
- [二次計画法のアルゴリズム](https://jp.mathworks.com/help/optim/ug/quadratic-programming-algorithms.html#bvj25y3-1)

# 半正定値計画(SDP)

半正定値計画は式3で記述される。

```math
\begin{eqnarray}
\min &  & C \bullet X\\

s.t. &  & \ \ A_{i}\bullet X = b_{i} \ \ (i=1,2,...,m)\\
     &  & \ \ X\succeq 0
\end{eqnarray}
\tag{3}
```

参照

- [半正定値計画問題に対する主双対内点法](http://www.me.titech.ac.jp/~nakata/SDP_IPM/SDP_IPM.html)
- [対称クロネッカー積におけるvecからsvecに変換する行列Qの実装について](https://qiita.com/momo10/items/ed9d67f6e4a3c317f73c)
- [数理計画～半正定値計画をPythonで実装～](https://qiita.com/momo10/items/0f91b4284163b2452be5)
- [On the Kronecker](https://www.math.uwaterloo.ca/~hwolkowi/henry/reports/kronthesisschaecke04.pdf)

# 二次錐計画(SOCP)

参照

- [錐線形計画への招待](https://www.jstage.jst.go.jp/article/isciesci/47/5/47_KJ00001013487/_pdf)
- [二次錐計画アルゴリズム](https://jp.mathworks.com/help/optim/ug/cone-programming-algorithm.html)
- [二次錐計画の基本と応用](https://www.logopt.com/book/cone.pdf)

# 二次制約二次計画(QCQP)

# 確率計画

参照

- [確率計画法とその周辺の紹介](https://qiita.com/kievdhia/items/3a5cc31f42cfd5464b12)

# ロバスト最適化(RO)

参照
- [ロバスト最適化の紹介](https://ibisml.org/wp-content/uploads/2020/10/ibisml41-takeda.pdf)
- [連続最適化および関連分野に関する夏季学校](https://www.ism.ac.jp/~mirai/sscoke/2022/gotoh-lecture.pdf)
- [最大kノルムの双対表現](https://qiita.com/momo10/items/1144ec09ac44698b91f8)

# 分布的ロバスト最適化(DRO)

分布的ロバスト最適化は、経験分布$\hat{\mathbb{P}}_N$の不確実性を集合で表し、その集合の中で最悪ケースの期待コストの最小化を目指す。

```math
\inf_{\xi}\sup_{\mathbb{Q}\in\mathbb{B}_{\epsilon}(\hat{\mathbb{P}}_N)} 
\mathbb{E}^{\mathbb{Q}}[l(\xi)]
```

不確実性集合$\mathbb{B}_{\epsilon}(\hat{\mathbb{P}}_N)$は、下式で与えられる。

```math
\mathbb{B}_{\epsilon}(\hat{\mathbb{P}}_N)
:=
\{\mathbb{Q}\in\mathcal{M}(\Xi):
d_{W}(\hat{\mathbb{P}}_N,\mathbb{Q})\leq\epsilon\}
```

経験分布$\hat{\mathbb{P}}_N$を中心とした半径$\epsilon$のWasserstein球とみることができる。

参照

- [連続最適化および関連分野に関する夏季学校](https://www.ism.ac.jp/~mirai/sscoke/2022/gotoh-lecture.pdf)
- [Kullback-Leiblerダイバージェンスに基づく不確実性集合](https://qiita.com/momo10/items/edc3cf4cc76742fe0f9d)
- [Φ-ダイバージェンスはKLダイバージェンスを包含してるよ。](https://qiita.com/momo10/items/ff6c05d5b329ffc3ffac)
- [Wasserstein距離に基づく分布的ロバスト最適化の凸最適化問題への帰着](https://qiita.com/momo10/items/eaef721fb16608d38ff1)
- [分布的ロバスト最適化をロジスティク回帰に適用しcvxpyで実装](https://qiita.com/momo10/items/467f647d2875549be875)
- [Dual Normについて](https://qiita.com/mosh/items/afeaf100379f49c470e8)
- [convex conjugate of logistic regression](https://math.stackexchange.com/questions/3530662/convex-conjugate-of-logistic-regression)
- [Relationship between the Lipschitz modulus and conjugate function](https://math.stackexchange.com/questions/4219583/relationship-between-the-lipschitz-modulus-and-conjugate-function)
- [Atomic Functions](https://www.cvxpy.org/tutorial/functions/index.html)
- [行列の平方根](https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.sqrtm.html)


# リーマン多様体上の最適化

リーマン多様体$\mathcal{M}$としたとき、

```math
\begin{eqnarray}
\min &  &f(x) \\

s.t. & & x\in \mathcal{M}

\end{eqnarray}
\tag{4}
```


参照

- [曲がった空間上の最適化](https://www.fse.sci.waseda.ac.jp/20200415-kasai/)
- [曲がった空間での最適化](http://www.orsj.or.jp/archive2/or60-9/or60_9_549.pdf)
- [リーマン多様体上の連続最適化](https://qiita.com/wsuzume/items/3f391369330abefbdb41)
- [リーマン多様体上の最適化](https://www.jstage.jst.go.jp/article/isciesci/62/1/62_21/_pdf/-char/ja)
- [特異値分解をリーマン多様体上の最適化で実装してみた。](https://qiita.com/momo10/items/ccb03cb336891feafcfc)
- [Manifold Optimization](https://nineties.github.io/manifold-optimization/)
- [リーマン幾何学](https://www.kazuhirosato.work/entry/%E7%A0%94%E7%A9%B6%E3%81%A7%E5%88%A9%E7%94%A8%E3%81%97%E3%81%A6%E3%81%84%E3%82%8B%E6%95%B0%E5%AD%A6)
- [連続最適化および関連分野に関する夏季学校](https://www.ism.ac.jp/~mirai/sscoke/2021/sato-lecture.pdf)



# KKT条件

主問題を考える。

```math
\begin{eqnarray}
\min &  &f(x) \\

\mathrm{s.t.} & &g(x)\leq 0\\
              & & x\in X
\end{eqnarray}
```

$\Phi(x,u)=f(x)+\langle u,g(x)\rangle, u\geq0$とおくとき、$\Phi(x_0,u_0)$の鞍点を下式で定義する。

```math
\Phi(x_0,u)\leq\Phi(x_0,u_0)\leq\Phi(x,u_0)
```

このとき、凸最適化問題では、鞍点とKKT条件と主問題の最適解には以下の関係がある。

<p align="center">
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/139678/ed706276-c515-d8f2-850a-5aa5619e7fa9.png" width="60%">
</p>

参照

- [数理計画法　～KKT条件～](https://mathlog.info/articles/2178)

# ラグランジュ双対問題

主問題を考える。

```math
\begin{eqnarray}
\min &  &f(x) \\

\mathrm{s.t.} & &g(x)\leq 0\\
              & & x\in X
\end{eqnarray}
```

このときのラグランジュ双対問題は、$\theta(u):=\inf_{x\in X}\lbrace f(x)+u^Tg(x)\rbrace$とおけば、


```math
\begin{eqnarray}
\max &  &\theta(u) \\

\mathrm{s.t.} & &u\geq 0\\
\end{eqnarray}
```

凸最適化問題について考えると、主問題とラグランジュ双対問題は下図の関係にある。
$(x_0,y_0)$は主問題の最適解である。凸最適化問題では、主問題とラグランジュ双対問題の最適解は一致する(**強双対性**)。ラグランジュ双対問題を考えるとき、傾き$u\geq0$の条件をつけないといけないことに注意する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/139678/22753d53-71e5-21ac-3d8c-25d3d334cd90.png)

参照

- [ラグランジュ関数，ラグランジュ双対問題，KKT条件のあらすじをまとめる](https://seetheworld1992.hatenablog.com/entry/2017/04/10/200453),
- [ラグランジュ双対問題について解説](https://qiita.com/birdwatcher/items/b23209f06177373c6df4)
- [双対問題(山下信夫先生)](http://www-optima.amp.i.kyoto-u.ac.jp/~nobuo/Ryukoku/2002/course5.pdf)
- [ラグランジュ緩和と双対問題(松井知己先生)](http://tomomi.my.coocan.jp/text/relax1.pdf)
- [ラグランジュ双対問題の強双対性について幾何学的にみてみよう！](https://qiita.com/momo10/items/d3e7ccacc6390286f679)
- [ラグランジュ双対問題の強双対性について](https://qiita.com/momo10/items/661752f82b25ce046702)

# 不動点近似法

ADMMなどの近接分離最適化など凸最適化問題の収束について考えるときに用いる。

- [不動点理論と最適化](https://www.ism.ac.jp/~mirai/sscoke/2021/)

# ADMM

```math
\begin{array}{ll}
\mathrm{ min } & f(x) + g(z) \\
\mathrm{ s.t. } & Ax + Bz = c
\end{array}
```

- [交互乗数法(ADMM)の理解を深めてみなイカ？【あらすじ編】](https://qiita.com/momo10/items/b3e92993c37f922640e9)
- [On the Douglas-Rachford splitting method and proximal point algorithm for maximal monotone operators](https://link.springer.com/article/10.1007/BF01581204)
- [Proof about Conjugate and subgradient](https://link.springer.com/article/10.1007/BF01581204)
- [How can we prove equation of sub-gradient and conjugate?](https://math.stackexchange.com/questions/4538501/how-can-we-prove-equation-of-sub-gradient-and-conjugate)

# SAM

- [SAMのわかりやすい記事](https://qiita.com/momo10/items/4816a9a6d21b88e50779)

# 凸解析

- [最適性条件で出てくる凸解析の用語のイメージについて](https://mathlog.info/articles/3486)

# 代数幾何

参照

- [凸代数幾何と最適化理論](http://www2.kaiyodai.ac.jp/~yoshi-s/Lectures/ConvAlg/ConvAlg-web-kyushu.pdf)

# 整数計画のモデリング

参照