【中科大凸优化-7】凸优化问题的定义、基本概念及四条性质

新闻资讯 | 2024-03-11 14:32

定义：一个优化问题可以表示为

$\\begin{align*}& \\min & f_0(x) \\\\ & s.t. & f_i(x) & \\leq 0, i=1,..., m \\\\ && h_i(x) &=0, i=1,...,p \\end{align*}\\\\$

其中 $f_0$ 称为目标函数或者损失函数（若是最大化问题则称为效用函数），两个约束分别称为不等式约束和等式约束。

定义：目标函数和所有约束函数定义域的交集称为域，即 $\\mathcal{D}=\\bigcap_{i=0}domf_i \\cap \\bigcap_{i=1}domh_i$

定义：域中所有满足约束条件的元素称为可行解（feasible point），可行解组成的集合称为可行域（feasible set），即 $X_f=\\{ x | x \\in \\mathcal{D}, f_i(x) \\leq 0, h_i(x)=0 \\}$

定义： $p^*=\\inf \\{ f_0(x) | x \\in X_f \\}$ 称为问题的最优值（optimal value），若 $f(x^*)=p^*, x^* \\in X_f$ ，那么 $x^*$ 称为优化问题的最优解（optimal point），最优解组成的组合称为最优解集

注意：当优化问题不可行时（可行域为空），最优值 $p^*=+\\infty$

定义： $\\{ x | x \\in X_f, f_0(x) \\leq p^* + \\varepsilon \\}$ 称为优化问题的 $\\varepsilon$ 次优解集

定义： $\\inf \\{ f_0(z) | z \\in X_f , ||z-x||_2 \\leq R \\}$ 称为目标函数在 $x$ 附近的局部最优解

定义：一个凸优化问题可写成如下标准形式

$\\begin{align*}& \\min & f_0(x) \\\\ & s.t. & f_i(x) & \\leq 0, i=1,..., m \\\\ && a_i^Tx &=b_i, i=1,...,p \\end{align*}\\\\$

其中目标函数和不等式约束函数均为凸函数，同时等式约束 $h_i(x)=a_i^Tx-b_i$ 为仿射映射

定义：在上述定义的基础上，如果目标函数为拟凸函数，那么该优化问题就是一个拟凸优化问题

证明：

推论：对于目标函数一阶可微的凸优化问题，若 $x$ 为最优解，则 $x \\in X_f$ 且对于任意的 $y \\in X_f$ 均有 $\ abla f_0(x)^T (y-x) \\geq 0$ ，反之亦成立

说明：即可行域一定在下图中实线所定义的超平面的同一侧

证明：

推论：对于无约束条件的凸优化问题， $x$ 为最优解等价于 $\ abla f_0(x) ^T=0$

证明：

推论：对于仅有等式约束的凸优化问题

$\\begin{align*}& \\min & f_0(x) \\\\ & s.t. & Ax=b \\end{align*}\\\\$

若可行域非空且最优解为 $x$ ，那么对于任意的 $v \\in \\mathcal{N}(A)$ ，均有 $\ abla f_0(x)^T v \\geq 0$

证明：

推论：对于仅有非负约束的凸优化问题

$\\begin{align*}& \\min & f_0(x) \\\\ & s.t. & x \\geq 0 \\end{align*}\\\\$

若可行域非空且最优解为 $x$ ，那么 $\ abla f_0(x)^T x=0$ ，即 $(\ abla f_0(x))_i$ 和 $x_i$ 中至少有一个为零

证明：