tl;dr Dual ascent method を振り返る Augmented Lagrangians method の概要について述べる toy problem に対して Augmented Lagrangians method を適用した結果について述べる モチベ 前回の記事では，等式制約付き最適化問題に対するラグランジュ双対問題…

これは何？ 一変数関数 $f\colon\mathbb{R}\to\mathbb{R}$ を与えられた閉区間 $\Omega \subseteq \mathbb{R}$ 上で最小化する $x^\star$ を求める方法について扱う 最適化問題として記述すると以下のように表される: \begin{align} \min \quad &f(x) \\ \ma…

フルランクな行列をランダムに生成する手法を教えて頂きました: https://t.co/mp7HaadpwZランダムなゼロでない固有値を対角にならべてから、ランダムなユニタリー行列で相似変換すれば良さそうです。ランダムなユニタリー行列はランダムなエルミート行列から…

CVXPY による制約付き最適化問題を求解

yukicoder No.1077「Noelちゃんと星々4」

以前の記事で ABC167-D について扱いました。ここで出題された問題は幅優先探索を用いることによって綺麗に解くことができました。今回はほぼ同様の実装で解くことのできる例題を見つけたので扱ってみたいと思います。 問題の概要 $N$ 個の町（町 $1,$ 町 $2…

概要 前回の記事において、単一始点最短経路（Single Source Shortest Path; SSSP）の重みを求めるプログラムである Dijkstra（ダイクストラ）法のpythonによる実装例を紹介しました。そこでは、隣接リストを用いて実装をしましたが、隣接行列を用いても同様…

はじめに element in listについて 例題 問題概要 制約 解答 おわりに はじめに 以前の記事で、pythonにおいてelement in listという書き方は非常に遅いので気を付けましょうと書きました。これについて、実例とともに見ていきたいと思います。 element in l…

話題になった^1問題なので取り上げてみます。 a, b, h, m = map(int, input().split()) from math import sqrt, cos, radians angle = abs(30 * (h + m / 60) - 6 * m) c = sqrt(a**2 + b**2 - 2*a*b*cos(radians(angle))) print(c) 針の動きは次のように考…

幅優先探索を使う典型的な問題でした...。pythonではcollectionsモジュールのdequeを用いることによって実装してあげるのが最も自然なのかなと思うので、そのように実装してあげます。「幅優先探索ってそもそも何？」という方は、けんちょんさんの記事を一度…

AtCoder ABC 167 D - Teleporter (400 点) in Python

AtCoder ABC 164 D - Multiple of 2019 (400 点) in Python

AtCoder 150 C in Python

リーマン多様体上の最適化問題を，PythonのPymanoptソルバーを用いて実装する．

はじめに 相補性問題の定式化 相補性問題の再定式化 相補性問題に対するアルゴリズム アルゴリズム実装における注意点 B 劣微分 $V \in \partial_B \Phi(x)$ の導出 勾配ベクトル $\nabla\Psi(x)$ の導出 Python による実装 実装: 関数の定義 実装: 相補性問…

はじめに 数理最適化とは CVXPY 導入 数値実験 例1：線形計画問題(Linear Programming Problem; LP) Python によるサンプルコード 例2：最小二乗問題(制約付き) Python によるサンプルコード 例3：半正定値計画問題(Semidefinite Programming Problem; SDP) …