证明两个优化问题中极点最优解的存在性、等价性及参数β的阈值条件

作者: 久别重逢已经那边v发 | 来源:发表于2024-10-31 07:29 被阅读0次

动态规划
算法：动态规划
机器学习理论系列2——梯度下降法
动态规划-Python
线性规划与单纯形法
凸优化相关概念学习笔记
改变自己：局部最优与全局最优
解的存在性及解的个数
优化算法
动态规划

考虑如下两个优化问题：

$\begin{array}{ll} \text{(A):} & \min f(x), \\ & \times\\ & \text{s. t. } g(x)=0,\\ & x_{i}\in\mathcal{F}_i,\ i=1,\ldots,n \end{array} \quad \text{和} \quad \begin{array}{ll} \text{(B):} & \min f(x)+\beta g(x)^{\mathrm{T}} 1_p, \\ & \times\\ & \text{s. t. } x_i\in\mathcal{F}_i,\ i=1,\ldots,n, \end{array}$

其中 $x=[x_1^\mathrm{T},\ldots,x_n^\mathrm{T}]^{\mathrm{T}}\in\mathbb{R}^{m}$ （ $m,n\in\mathbb{N}$ ），且对于 $i=1,\ldots,n$ ， $x_i\in\mathbb{R}^{m_i}$ （ $m_i\in\mathbb{N}$ ），满足 $\sum_{i=1}^{n}m_i=m$ . 函数 $f:\mathbb{R}^{m}\rightarrow\mathbb{R}$ 和 $g:\mathbb{R}^{m}\rightarrow\mathbb{R}^{p}$ （ $p\in\mathbb{N}$ ）是多仿射的，即对任意 $i\in\{1,\ldots,n\}$ ，在固定下标在 $\{1,\ldots,N\}\setminus\{i\}$ 中的块后，它们对 $x_i$ 是仿射函数。这里，我们称一个函数 $h:\mathbb{R}^{q}\rightarrow\mathbb{R}^{r}$ （ $q,r\in\mathbb{N}$ ）是仿射的，若对任意 $a\in\mathbb{R}$ 以及 $y^{(1)}, y^{(2)}\in\mathbb{R}^{q}$ ，有

$h(ay^{(1)}+(1-a)y^{(2)})=ah(y^{(1)})+(1-a)h(y^{(2)})$ 。

对任意 $i\in\{1,\ldots,n\}$ ，集合 $\mathcal{F}_i\subseteq\mathbb{R}^{m_i}$ 是一个有界多面体。函数 $g$ 在 $\times_{i=1}^{n}\mathcal{F}_i$ 上非负，其中“ $\times$ ”表示集合的笛卡尔积．此外，在问题(B)中，标量 $\beta$ 是一个实数， $1_p\in\mathbb{R}^{p}$ 代表 $p$ 维全一向量。

请证明如下三个结论：

对任意 $\beta\in\mathbb{R}$ ，问题(B)至少有一个最优解是可行域的极点(即极点最优解)。
存在 $\bar{\beta}\in\mathbb{R}$ ，使得对任意 $\beta\geq\bar{\beta}$ ，问题(B)的极点最优解都是问题(A)的最优解。
存在 $\tilde{\beta}\in\mathbb{R}$ ，使得对任意 $\beta\geq\tilde{\beta}$ ，问题(A)和(B)的最优解集相同。

证：

证明结论1: 极点最优解的存在性

首先，明确问题(B)的可行域是有限个多面体的笛卡尔积，即 $\times_{i=1}^{n}\mathcal{F}_i$ ，根据多面体的性质它本身也是一个多面体。

对于多仿射函数，我们进一步说明其性质。已知函数 $f(x)$ 和 $g(x)$ 是多仿射的，那么目标函数 $F\left(x\right)=f\left(x\right)+\beta g\left(x\right)^{\mathrm{T}}1_{p}$ 也是多仿射的。

多仿射函数在定义域内是连续的(此处可根据多仿射函数的定义及相关性质推出连续性，具体可参考多仿射函数相关理论，因篇幅省略详细推导)。

根据线性规划的基本定理，对于在多面体上连续的函数，其最小值一定可以在多面体的顶点(极点)处取到。

由于问题(B)的目标函数 $F(x)$ 在其可行域（多面体）上是连续的多仿射函数，所以问题(B)至少有一个最优解是可行域的极点。

2.证明结论2：存在 $\bar{\beta}$ 使得极点最优解也是问题(A)的最优解

因为函数 $g(x)$ 在可行域 $\times_{i=1}^{m}Fi$ 上非负,且集合 $Fi\subseteq R^{mi}$ 是有界多面体( $i=1,\ldots,n$ )。

对于有界多面体上的连续函数 $g(x)$ (多仿射函数是连续的)，根据有界闭集上连续函数的性质， $g(x)$ 在该可行域上有最大值，设为 $M$ （即存在 $M\geq0$ ，使得对于任意 $x\in\times_{i=1}^{n}Fi$ ，都有 $g(x)\leq M$ )。

令 $\bar{\beta}=\frac{\max_{x\in\times_{i=1}^{n}}|f(x)|}{M\times p}$ （这里通过取 $f(x)$ 在可行域上绝对值的最大值与 $g(x)$ 最大值及向量维度相关量来确定 $\bar{\beta}$ ，确保后续分析的合理性）。

当 $\beta\geq\bar{\beta}$ 时，对于任意 $x\in\times_{i=1}^{n}\mathcal{F}_i$ ，有：

$\begin{aligned}\beta g(x)^T 1_p & \geq \bar{\beta}g(x)^T 1_p\\&=\frac{\max_{x\in\times_{i=1}^{n}\mathcal{F}_i}|f(x)|}{M\times p}\times g(x)^T 1_p\\\ &\geq\frac{\max_{x\in\times_{i=1}^{n}\mathcal{F}_i}|f(x)|}{M\times p}\times0\\&=0\end{aligned}$

此时，对于问题(B)的目标函数 $F(x)=f(x)+\beta g(x)^T 1_p$ ,当 $\beta\geq\bar{\beta}$ 时，在最小化过程中，主要是由 $f(x)$ 来决定最优解的走向，因为 $\beta g(x)^T 1_p\geq0$ 且其对目标函数值的增加相对 $f(x)$ 的影响较小（由 $\bar{\beta}$ 的选取方式决定）。