冷めたコーヒー

Weniger, aber besser

$\|\mathbf{x}\mathbf{x}^\top\|_F$ の導出

tl;dr

  • $\mathbf{x}\mathbf{x}^\top$ のフロベニウスノルム(Frobenius norm)を導く
  • 体 $K$ として,$K=\mathbb{R}^{m\times n}$ を考える

フロベニウスノルム

行列 $\mathbf{A}\in\mathbb{R}^{m\times n}$ に対して,その全成分の二乗和に対してルートをとったものをフロベニウスノルムといい,$\|\mathbf{A}\|_F$ で表す.

また,次に述べるように $\|\mathbf{A}\|_F$ はトレースを用いて次のように表すことができる:

$$ \|\mathbf{A}\|_F = \sqrt{\mathrm{tr}(\mathbf{A}^\top\mathbf{A})}. $$

証明は 行列のフロベニウスノルムとその性質 を参照 こちら に証明を記載しました.

導出

\begin{align} \|\mathbf{xx}^\top\|_F &= \sqrt{\mathrm{tr}((\mathbf{xx}^\top)^\top\mathbf{xx}^\top)} \\ &= \sqrt{\mathrm{tr}(\mathbf{x}\mathbf{x}^\top\mathbf{xx}^\top)} \\ &= \sqrt{\|\mathbf{x}\|^2_2\cdot\mathrm{tr}(\mathbf{x}\mathbf{x}^\top)} \\ &= \sqrt{\|\mathbf{x}\|^2_2\cdot \|\mathbf{x}\|^2_2} \\ &= \|\mathbf{x}\|^2_2. \end{align}

Augmented Lagrangians method(拡張ラグランジュ法)

tl;dr

  • Dual ascent method を振り返る
  • Augmented Lagrangians method の概要について述べる
  • toy problem に対して Augmented Lagrangians method を適用した結果について述べる

モチベ

前回の記事では,等式制約付き最適化問題に対するラグランジュ双対問題を導出し,双対問題を解くためのアルゴリズムである "dual ascent method" について概説した.

mirucacule.hatenablog.com

記事の中で数値実験として凸二次関数を線型の等式制約の下で最小化する問題を扱った.記事では主問題の目的関数と双対問題の目的関数が反復を重ねるごとに近くなっていく様子を提示したが,その結果はあくまでも上手くいったときの結果であり,初期点を変えたり,定数行列 $P,\, A$ や定数ベクトル $q,\, b$ を変えると途端に上手くいかない場合が多々ある.例えば,以下のような場合である.変更点は $m=5,\, n=20$ から $m=20,\, n=100$ にしただけである.

m = 10
n = 100
np.random.seed(1)
P = np.random.randn(n, n)
P = P.T @ P
q = np.random.randn(n)
A = np.random.randn(m, n)
b = np.random.randn(m)

最適化アルゴリズムの部分は 前回の記事 と同一であるため省略し,dual ascent method を適用して得られる各反復での主問題と双対問題の目的関数値の推移のみ以下に載せる.

f:id:mirucacule:20211207090412p:plain
主問題の目的関数値と双対問題の目的関数値の推移

グラフから明らかなように,反復を重ねると主問題の目的関数値)は正の無限大に発散し,双対問題の目的関数値)は負の無限大に発散してしまっている.

この記事では,dual ascent method を拡張した「拡張ラグランジュ」と呼ばれる最適化アルゴリズムについて扱う.この手法は dual ascent method とほとんど同じ反復を行うアルゴリズムであるものの,より緩い仮定のもとで収束性を示すことができるなどの利点がある.収束解析については触れないが,数値実験として拡張ラグランジュ法が dual ascent method に比べて頑健に動作することを確認する.なお,本記事を通して,ベクトルは太字で記述しないので注意されたい.

拡張ラグランジュ関数

次の等式制約付き最適化問題 (P) を考える:

\begin{align} \mathrm{(P)}\qquad \begin{gathered} \min_{x\in\mathbb{R}^n} \quad &f(x) \\ \mathrm{s.t.} \quad &Ax = b. \end{gathered} \end{align}

ここで,$A\in\mathbb{R}^{m\times n}, \, b\in\mathbb{R}^{m}$ はそれぞれ適当な大きさの定数行列,ベクトルである.また,$f$ は凸関数とする. このような等式制約付きの凸計画問題に対して拡張ラグランジュ関数は次のように定義される.

定義 等式制約付き凸計画問題 (P) に対して, \begin{align} L_\rho(x, y) = f(x) + y^\top (Ax - b) + \frac{\rho}{2}\| Ax-b\|^2_2 \end{align} で定義される関数 $L_\rho$ を拡張ラグランジュ関数(augmented Lagrangians function)という.ここで,$\rho > 0$ はペナルティである.

拡張ラグランジュ関数における $\rho$ は正の値をとるが,$\rho=0$ としたときは通常のラグランジュ関数に対応する.また,拡張ラグランジュ関数 $L_\rho$ は次の最適化問題に対する(通常の)ラグランジュ関数と見ることもできる.

\begin{align} \min_{x\in\mathbb{R}^n} \quad &f(x) + \frac{\rho}{2}\|Ax-b\|^2_2 \\ \mathrm{s.t.} \quad &Ax = b. \end{align}

なお,この最適化問題は (P) と本質的に等価である.実際,任意の実行可能解 $\hat{x}$ に対し,目的関数に追加した項の値は $\frac{\rho}{2}\|A\hat{x}-b\|^2_2 = 0$ である.

拡張ラグランジュ

前節で定義した拡張ラグランジュ関数を用いて,凸計画問題 (P) に対し,以下の反復を繰り返す手法を拡張ラグランジュ(Augmented Lagrangian method; method of multipliers)という.

\begin{align} x^{k+1} &:= \arg\min_x L_\rho(x, y^k) \\ y^{k+1} &:= y^k + \rho (Ax^{k+1} - b). \end{align}

この反復は dual ascent method とほとんど同じであり,違いは $x$ の更新式において拡張ラグランジュ関数を用いている点と,$y$ の更新においてステップサイズ $\alpha^k$ の代わりに $\rho$ が用いられている点のみである.

例:凸二次計画問題に対する拡張ラグランジュ

凸計画問題における目的関数 $f$ が $f(x)=\frac{1}{2}x^\top Px + q^\top x$ で与えられる場合を考える.ここで,$P$ は半正定値対称行列とする.この凸計画問題に対する拡張ラグランジュ関数 $L_\rho$ は

$$ L_\rho (x, y) = \frac{1}{2}x^\top Px + q^\top x + y^\top (Ax-b) + \frac{\rho}{2}\| Ax-b\|^2_2 $$

で与えられる.この $L_\rho$ は $x$ に関して凸であるから,拡張ラグランジュ法における $x$ の更新では,方程式 $\nabla_x L_\rho (x, y^k)$ を解いた解を $x^{k+1}$ とすればよい.拡張ラグランジュ関数の $x$ に関する勾配は

\begin{align} \nabla_x L_\rho (x, y^k) = Px + q + A^\top y^k + \rho (A^\top Ax - A^\top b) \end{align}

で与えられる.したがって,$\nabla_x L_\rho (x, y^k) = 0$,すなわち,正規方程式

\begin{align} (P + \rho A^\top A)x = -q + A^\top (\rho b - y^k) \end{align}

を解いて得られる解を $x^{k+1}$ とすればよい.

数値実験

前節の凸二次計画問題を扱う.以下で numpymatplotlib を用いるため import しておく(省略). 拡張ラグランジュ関数 $L_\rho$ と拡張ラグランジュ法の $x$ を更新する部分は次のように書ける.ただし,目的関数が凸二次関数の場合に限る.なお,f や他の定数については 前回の記事 を参照されたい.

def L_rho(x, y, rho):
    return f(x) + y.T@(A@x-b) + 0.5 * rho * np.linalg.norm(A@x - b) ** 2

def argminLrho(y, rho):
    return np.linalg.solve(P + rho * A.T@A, rho * A.T@b - A.T@y - q)

拡張ラグランジュ法は次のように書ける.引数として,初期点 y0,ペナルティパラメータ rho,反復回数 itermax を設定している.また,返り値として各反復における主問題の目的関数値 f_log,双対問題の目的関数値 g_log,残差 $\|Ax^k - b\|_2$ の値 residue を設定している.

def Augmented_Lagrangians_method(y0, rho, itermax=10):
    yk = y0
    f_log = np.zeros(itermax)
    g_log = np.zeros(itermax)
    residue = np.zeros(itermax)
    for k in range(itermax):
        xk = argminLrho(yk, rho)
        y = yk + rho * (A@xk - b)
        f_log[k] = f(xk)
        g_log[k] = g(y)
        residue[k] = np.linalg.norm(A@xk - b)
        yk = y
    return f_log, g_log, residue

まず,冒頭で述べた dual ascent method で上手くいかなかった例について実験してみる.適当な初期点の下で Augmented_Lagrangians_method() を呼び出せばよい.ここでは,初期点を標準正規分布から生成し,ペナルティパラメータとして $\rho=1$ と設定した.

f_log, g_log, residue =\
 Augmented_Lagrangians_method(y0=np.random.randn(m), rho=1, itermax=10)

結果として,f_logg_log をプロットした図を載せる.この図を見ると,僅か 4 反復程度で主問題の目的関数値と双対問題の目的関数値がほとんど一致していることが確認できる.

f:id:mirucacule:20211207181842p:plain
主問題の目的関数値と双対問題の目的関数値の推移

また,各反復における残差 $\|Ax^k - b\|_2$ は以下のようになる.縦軸は log スケールで表示しており,反復によって残差は指数的に減少していくことが確認できる.

f:id:mirucacule:20211207191013p:plain
残差の推移

蛇足

拡張ラグランジュ法について扱いました.今回は目的関数が凸二次関数というシンプルな形で記述される関数を扱ったので,$x$ の更新を最適化問題を解くことなく行うことができました.しかしながら,一般には $\arg\min_x L_\rho(x, y^k)$ を解く必要があるので毎回の反復で凸計画問題を扱う必要が出てきます.なんかそういうインスタンスを見つけて実験してみたいですね.

共役関数と双対問題

tl;dr

  • 共役関数を定義した後,等式制約付き最適化問題に対するラグランジュ双対問題を導出する
  • 双対問題を解く "dual ascent method" について概説する
  • toy problem に対して dual ascent method を適用した結果について述べる

共役関数

定義 真凸関数 $f\colon\mathbb{R}^n\to\mathbb{R} \cup \{+\infty\}$ に対して, \begin{align} f^\star (\mathbf{\xi}) := \underset{x\in\mathbb{R}^n}{\sup} \, \left\{ \left<\mathbf{\xi}, \mathbf{x} \right> - f(\mathbf{x}) \right\} \end{align} で定義される関数 $f^\star \colon \mathbb{R} \cup \{\pm \infty\}$ を $f$ の共役関数(conjugate function)という.

上の定義では $f$ の共役関数を $\sup$ によって定義したが,次のように $\inf$ によって定義することもできる:

\begin{align} f^\star (\mathbf{\xi}) := -\inf_{x\in\mathbb{R}^n} \, \left\{ f(\mathbf{x}) - \left< \mathbf{\xi}, \mathbf{x} \right> \right\}. \end{align}

実際,以下のように確かめることができる:

\begin{align} f^\star (\mathbf{\xi}) &:= \sup_{x\in\mathbb{R}^n} \, \left\{ \left<\mathbf{\xi}, \mathbf{x} \right> - f(\mathbf{x}) \right\} \\ &= -\inf_{x\in\mathbb{R}^n} \, -\left\{ \left<\mathbf{\xi}, \mathbf{x} \right> - f(\mathbf{x}) \right\} \\ &= -\inf_{x\in\mathbb{R}^n} \, \left\{ f(\mathbf{x}) - \left<\mathbf{\xi}, \mathbf{x} \right> \right\}. \end{align}

ここで,一般に $\sup\, f(\mathbf{x}) = - \inf\, \{-f(\mathbf{x})\}$ であることを用いた.

共役関数の例

例えば,分離可能な凸関数 $f(x_1, x_2) = g(x_1) + h(x_2)$ の共役関数は,

$$ f^\star ( \xi_1, \xi_2 ) = g^\ast(\xi_1) + h^\ast(\xi_2) $$

で与えられる.

共役関数を用いた双対問題の導出

次の等式制約付き最適化問題を考える:

\begin{align} \min_{x\in\mathbb{R}^n} \quad &f(x) \\ \mathrm{s.t.} \quad &Ax = b. \end{align}

ここで,$A\in\mathbb{R}^{m\times n}, \, b\in\mathbb{R}^{m}$ はそれぞれ適当な大きさの定数行列,ベクトルである.また,$f$ は凸関数とする.

この最適化問題に対するラグランジュ関数は

$$ L(x, y) = f(x) + y^\top (Ax - b) $$

で定義される.ここで,ベクトル $y\in\mathbb{R}^{m}$ はラグランジュ乗数を表す.双対関数は,

\begin{align} g(y) &= \inf_{x\in\mathbb{R}^n} L(x, y) \\ &= \inf \left\{ f(x) + y^\top (Ax - b) \right\} \\ &= \inf \left\{ f(x) - \left< -Ax+b, y \right>\right\} \\ &= \inf \left\{ f(x) - \left< -Ax, y \right> \right\} - \left<b, y \right> \\ &= \inf \left\{ f(x) - \left< -A^\top y, x \right> \right\} - \left<b, y \right> \\ &= -f^\star (-A^\top y) - \left<b, y \right> \end{align}

で与えられる.これより,主問題に対する双対問題は

\begin{align} \max \quad &g(y) \\ \mathrm{s.t.} \quad &y\in\mathbb{R}^m \end{align}

で与えられる.

いま,双対問題の最適解を $y^\star$ とする.このとき,主問題の最適解は $y^\star$ の情報を用いて次のように求めることができる:

\begin{align} x^\star = \arg\min_x L(x, y^\star). \end{align}

ただし,ラグランジュ関数 $L(x, y^\star)$ の最適解は一意であるときに限る(例えば,主問題の目的関数 $f$ が強凸関数であるとき).

dual ascent method

双対問題を解くことを考える.ここでは,双対問題の目的関数 $g$ は微分可能であるとする.

まず,$x^+$ をラグランジュ関数を最小にする点として求める,すなわち, $$ x^+ = \arg\min_x L(x, y). $$

すると,関数 $g$ の点 $y$ における勾配ベクトルは $\nabla g(y)=Ax^+-b$ で与えられる.実際,$x^+ = \arg\min_x L(x, y)$ であるとき,

$$ g(y) = \inf_x L(x, y) = L(x^+, y) $$

であり,両辺 $y$ について微分すると,

\begin{align} \nabla_y g(y) &= \nabla_y L(x^+, y) \\ &= \nabla_y \left\{ f(x^+) + y^\top (Ax^+ - b) \right\} \\ &= Ax^+ - b \end{align}

を得る.これは,主問題の等式制約の残差に相当する.

dual ascent method は次のような更新則で構成される:

\begin{align} x^{k+1} &:= \arg\min_x L(x, y^k) \\ y^{k+1} &:= y^k + \alpha^k (Ax^{k} - b). \end{align}

ここで,$\alpha^k > 0$ は第 $k$ 反復目におけるステップサイズを表す.この手法が "dual ascent" と呼ばれる所以は,ステップサイズ $\alpha^k$ を適切に選ぶことによって,$g(y^{k+1}) > g(y^k)$ が成り立つことに拠る.

数値実験

折角なので dual ascent method を実装して数値実験してみる.解くべき最適化問題として次のような二次計画問題を考える:

\begin{align} \min_{x\in\mathbb{R}^n} \quad &\frac{1}{2}x^\top Px + q^\top x \\ \mathrm{s.t.} \quad &Ax = b, \end{align}

ここで,$P$ は $n$ 次対称定数行列,$q\in\mathbb{R}^n,\, A\in\mathbb{R}^{m\times n},\, b\in\mathbb{R}^{m}$ はそれぞれ適当な大きさの定数ベクトルとする.

以下で numpymatplotlib を用いるため import しておく.

import numpy as np
import matplotlib.pyplot as plt

それぞれの行列,ベクトルは次のように生成しておく.

m = 5
n = 20
np.random.seed(1)
P = np.random.randn(n, n)
P = P.T @ P
q = np.random.randn(n)
A = np.random.randn(m, n)
b = np.random.randn(m)

また,必要な関数を次のように定義しておく.

def f(x):
    return 0.5 * np.dot(x, P@x) + q.T@x

def L(x, y):
    return f(x) + y.T@(A@x-b)

def argminL(y):
    return np.linalg.solve(P, -q-A.T@y)

def g(y):
    x = argminL(y)
    return L(x, y)

さて,dual ascent method の反復は以下のように記述できる.

yk = np.random.randn(m)
maxiter = 1000
alpha = 0.001
f_log = []
g_log = []
for k in range(maxiter):
    xk = argminL(yk)
    y  = yk + (A@xk - b) * alpha
    f_log.append(f(xk))
    g_log.append(g(y))
    yk = y

ここでは,ステップサイズとして定数ステップ $\alpha^k = \frac{1}{1000}$ を用いた.また,f_log, g_log にはそれぞれ暫定解 $x^k$ における主問題の目的関数値,$y^k$ における双対問題の目的関数値を格納する.

f_log, g_log を図示すると次のようになる.

f:id:mirucacule:20211130224803p:plain
主問題の目的関数値と双対問題の目的関数値の推移

なお,可視化コードは以下.

fig = plt.figure()
ax = fig.add_subplot(111)
cycle = plt.rcParams['axes.prop_cycle'].by_key()['color']
ax.plot(f_log, label="f", color=cycle[2])
ax.plot(g_log, label="g", color=cycle[3])
ax.legend()
ax.set_xlabel("iter")
ax.set_ylabel("the value of objective function")
ax.grid(True)

他にも $Ax^k - b$ の値の推移など興味あるが,また追記したいと思う.

$\sum_{i=1}^{n}\min \{x_i, (Ax+b)_i\}$ の凹性について

tl;dr

この記事では,以下の関数

$$ f(\mathbf{x}) = \sum_{i=1}^{n}\min \left\{x_i, (A\mathbf{x}+\mathbf{b})_i\right\} $$

が凹関数(Wikipedia)であることを見ていく.ここで,$A$ は適当な大きさの実行列であり,$\mathbf{b}$ は適当な大きさの実ベクトルである.また,$x_i$ はベクトル $\mathbf{x}$ の第 $i$ 成分を表す.

お気持ち

関数 $g_i,\, h_i$ を以下のように定義する.

\begin{align} g_i(\mathbf{x}) &:= \mathbf{e}_i^\top \mathbf{x} = \left< \mathbf{e}_i, \mathbf{x}\right>, \\ h_i(\mathbf{x}) &:= \mathbf{e}_i^\top (A\mathbf{x} + \mathbf{b}) = \left<A^\top \mathbf{e}_i, \mathbf{x}\right> + \left< \mathbf{e}_i, \mathbf{b}\right>. \end{align}

ここで,$\mathbf{e}_i$ は $n$ 次元のベクトルであり,その第 $i$ 成分のみ $1$ で他の成分がすべて $0$ であるとする.すなわち,$\mathbf{e}_i = (0,\dots, 0, \underset{i}{1}, 0, \dots, 0)^\top$ である. すると,関数 $f$ は関数 $g_i,\, h_i$ を用いて

$$ f(\mathbf{x}) = \sum_{i=1}^{n}\min \left\{g_i(\mathbf{x}), h_i(\mathbf{x})\right\} $$

と表されることが分かる.

和の部分を無視して,関数 \begin{align} \phi_i(\mathbf{x}) &= \min \left\{g_i(\mathbf{x}), h_i(\mathbf{x})\right\} \\ &= \min \left\{ \mathbf{e}_i^\top \mathbf{x}, \mathbf{e}_i^\top (A\mathbf{x} + \mathbf{b})\right\} \end{align} を観察すると,これは 2 つの線型関数に対して $\min$ をとったものになっているので,気持ちとしては以下のような図として表され,確かに凹関数であるように思える.

f:id:mirucacule:20211124145913j:plain
関数 $\phi_i$ の形状

証明に用いる道具

次の 2 つの命題を用いる:

  • 凹関数の列に対して $\min$ をとった関数もまた凹関数である
  • 凹関数の列に対して和をとった関数もまた凹関数である

まず,一つ目の命題について考える.なお,一般的に数理最適化の分野では凸関数を扱うことが多いため,命題としては凸関数で述べ,その系として凹関数について述べることとする.

補題 凸集合 $S\subset \mathbb{R}^n$ 上で定義された上に有界な実数値関数の列 $\{f_i\}_{i=1}^{n}$ に対して,すべての $f_i$ が $S$ 上の凸関数ならば,実数値関数 $$ f(\mathbf{x}) = \max_{i\in [n]} f_i(\mathbf{x}) $$ は $S$ 上の凸関数である.ここで,$[n]$ は集合$\{1,2,\dots, n\}$ を表す.

証明.関数 $f$ のエピグラフが凸集合であることを言えばよい.いま,$f_i$ は凸関数であるため,そのエピグラフ $$ \mathrm{epi}\, f_i = \left\{ (\mathbf{x},z)^\top \in \mathbb{R}^{n+1} \mid f_i(\mathbf{x}) \leq z, \, \mathbf{x}\in S,\, z \in \mathbb{R} \right\} $$ は $\mathbb{R}^{n+1}$ 上の凸集合である.また,これらの共通集合 \begin{align} \bigcap_{i \in [n]} \mathrm{epi}\, f_i &= \left\{ (\mathbf{x},z)^\top \in \mathbb{R}^{n+1} \mid f_i(x) \leq z, \, \mathbf{x}\in S,\, z \in \mathbb{R},\, i \in [n] \right\} \\ &= \left\{ (\mathbf{x},z)^\top \in \mathbb{R}^{n+1} \mid \max_{i \in [n]}f_i(\mathbf{x}) \leq z, \, \mathbf{x}\in S,\, z \in \mathbb{R} \right\} \\ &= \left\{ (\mathbf{x},z)^\top \in \mathbb{R}^{n+1} \mid f(\mathbf{x}) \leq z, \, \mathbf{x}\in S,\, z \in \mathbb{R} \right\} \end{align} もまた凸集合である.これは $S$ 上の実数値関数 $f$ のエピグラフである.したがって,$f$ は $S$ 上の凸関数である.(証明終)

この補題の系として,次の命題が成り立つ.

凸集合 $S\subset \mathbb{R}^n$ 上で定義された下に有界な実数値関数の列 $\{f_i\}_{i=1}^{n}$ に対して,すべての $f_i$ が $S$ 上の凹関数ならば,実数値関数 $$ f(\mathbf{x}) = \min_{i\in [n]} f_i(\mathbf{x}) $$ は $S$ 上の凹関数である.ここで,$[n]$ は集合 $\{1,2,\dots, n\}$ を表す.

さて,関数

$$ \phi_i(\mathbf{x}) = \min\{g_i(\mathbf{x}), \,h_i(\mathbf{x})\} = \min\{\mathbf{e}_i^\top \mathbf{x}, \,\mathbf{e}_i^\top (A\mathbf{x} + \mathbf{b})\} $$

について,関数 $g_i,\, h_i$ はそれぞれ $\mathbf{x}$ に関して線型であるため,凸であり,かつ凹である.したがって,系より関数 $\phi_i$ は凹関数であることが分かる.

次に,凹関数の列の和がまた凹関数であることを見ていく.こちらでもまず凸関数の列の和がまた凸関数であることを述べた後,その系として凹関数について述べることとする.

補題 凸集合 $S\subset \mathbb{R}^n$ 上で定義された実数値関数の列 $\{f_i\}_{i=1}^{n}$ に対して,すべての $f_i$ が $S$ 上の凸関数ならば,実数値関数 $$ f(\mathbf{x}) = \sum_{i=1}^{n} f_i(\mathbf{x}) $$ は $S$ 上の凸関数である.

証明.関数 $f$ が凸関数の定義,すなわち,任意の $\mathbf{x},\, \mathbf{y} \in S$ と実数 $\lambda \in [0,1]$ に対して $$ f(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda) f(\mathbf{x}) $$ を満たすことを確認すればよい.容易なので読者に任せる.(証明終)

これについても系として次の命題が成り立つ.

凸集合 $S\subset \mathbb{R}^n$ 上で定義された実数値関数の列 $\{f_i\}_{i=1}^{n}$ に対して,すべての $f_i$ が $S$ 上の凹関数ならば,実数値関数 $$ f(\mathbf{x}) = \sum_{i=1}^{n} f_i(\mathbf{x}) $$ は $S$ 上の凹関数である.

この系を用いると,先の議論より関数 $\phi_i$ はすべての $i\in [n]$ で凹であったから,関数

$$ f(x) = \sum_{i=1}^{n} \phi_i(\mathbf{x}) = \min \left\{x_i, (A\mathbf{x}+\mathbf{b})_i\right\} $$

は凹関数であることが分かる.

結論

以上の議論より,次の命題が成り立つことが確認された.

定理 次の関数 $f\colon\mathbb{R}^n\to\mathbb{R}$ は凹関数である. \begin{align} f(\mathbf{x}) = \sum_{i=1}^{n} \min \left\{x_i, (A\mathbf{x}+\mathbf{b})_i \right\} \end{align}

参考文献

二次関数の凸性

原点を通る二次関数 $f(\mathbf{x}) = \left< \mathbf{x}, \mathbf{Ax} \right>$ は行列 $\mathbf{A}$が半正定値対称であるとき凸であることについて以下の記事で述べた.

mathlog.info

証明の技法としてはシンプルで,以下の事実を基に式変形を行うだけである.

定義(凸関数) 凸集合 $S\subset \mathbb{R}^n$ 上で定義された実数値関数 $f\colon S\to\mathbb{R}$ が任意の $\mathbf{x},\,\mathbf{y}\in\mathbb{R}^n$ とスカラー $\lambda\in [0,1]$ に対して \begin{align} f(\lambda \mathbf{x} + (1-\lambda)\mathbf{y}) \leqq \lambda f(\mathbf{x}) + (1 - \lambda ) f(\mathbf{y}) \end{align} を満たすとき,関数 $f$ は $S$ 上で定義された凸関数であるという.

証明ではスカラー $\lambda$ として $0<\lambda < 1$ として取っているが,$\lambda = 0,\, 1$ のときは自明に $f(\lambda \mathbf{x} + (1-\lambda )\mathbf{y}) = \lambda f(\mathbf{x}) + (1 - \lambda ) f(\mathbf{y}) $ が成立するため $0<\lambda < 1$ の場合についてのみ検討すれば十分である.

さて,一般の二次関数は行列 $\mathbf{A}\in\mathbb{R}^{n\times n}$,ベクトル $\mathbf{b}\in\mathbb{R}^n$,スカラー $c\in\mathbb{R}$ によって

$$ f(\mathbf{x}) = \left< \mathbf{x}, \mathbf{Ax} \right> + 2 \left< \mathbf{b}, \mathbf{x} \right> + c $$

と表すことができる.これは,次のように変形することができる:

$$ f(\mathbf{x}) = \begin{pmatrix} 1 & \mathbf{x}^\top \end{pmatrix} \begin{pmatrix} c & \mathbf{b}^\top \\ \mathbf{b} & \mathbf{A} \end{pmatrix} \begin{pmatrix} 1 & \mathbf{x} \end{pmatrix}. $$

したがって,行列 $\begin{pmatrix} c & \mathbf{b}^\top \\ \mathbf{b} & \mathbf{A} \end{pmatrix}$ が半正定値行列であれば,この関数は凸であることが言える. → 行列 $\mathbf{A}$ が半正定値であれば $ \left< \mathbf{x}, \mathbf{Ax} \right>$ は凸であり,$\mathbf{x}$ に関する線型項 $ 2 \left< \mathbf{b}, \mathbf{x} \right> + c$ も凸であるので,実数値関数 $f$ は $\mathbf{A}$ が半正定値でありさえすれば凸であることが言える.