Lecture 03 · Convexity II: Convex Optimization Problems

References

• Lecture: https://www.stat.cmu.edu/~ryantibs/convexopt-F18/
• Reading: Boyd & Vandenberghe, Convex Optimization, Sections 3.2.5, 4.1.3, and 4.2.

1. Optimization Problems

1.1 Problem Formulation

回顾, 一个凸优化问题具有如下形式:

$$\begin{array}{rl}\underset{x\in D}{\min }& f(x)\\ \text{s.t.}& g_i(x)\le 0,i=1,\dots ,m\\ & Ax=b\end{array}$$

• 其中 $f,g_i$ 是凸函数, optimization domain $D={\bigcap }_{i=1}^m\text{dom}(g_i)\cap \text{dom}(f)$ 是凸集. $f$ 称作 criterion 或 objective function. $g_i$ 称作 inequality constraint functions.
• 对于满足所有约束条件的 $x$ 称作 feasible point, 否则称作 infeasible point. 若 $x$ 是 feasible point 且 $g_i(x)=0$ 对某些 $i$ 成立, 则称该约束条件 $g_i$ 在 $x$ 处为 active constraint, 否则称为 inactive constraint.
• 若存在 $x^{\ast }$ 是所有 feasible point 中使 $f(x)$ 取得最小值的点, 则称 $x^{\ast }$ 为 optimal point 或该问题的 solution, 最小值 $f(x^{\ast })$ 称作 optimal value. 若 $x$ 是 feasible point, 且有 $f(x)\le p^{\star }+ϵ$, 则称 $x$ 为 $ϵ$-suboptimal point.

同时方便起见, 定义优化问题的最优值 $p^{\star }$:

$$\begin{array}{r}{p}^{\star }=\inf \{f(x)\mid g_i(x)\le 0,\forall i;Ax=b\}\end{array}$$

• 这里 $p^{\star }$ 可能为 $-\infty$, 若存在 feasible point 使得 $f(x)$ 可以任意小, 则称该问题为 unbounded below.

---

1.2 Global and Local Optimality

• 若优化问题有解, 则记所有最优解组成的集合为 $X_{\text{opt}}$:

  $$X_{\text{opt}}=\{x\mid g_i(x)\le 0,\forall i;Ax=b;f(x)=p^{\star }\}$$

• 若优化问题对于 $ϵ>0$ 满足

  $$f(x)\le p^{\star }+ϵ$$

  则称 $x$ 为 $ϵ$-suboptimal point.

• 若对于某个 feasible point $x_0$, 存在某个 $R>0$, 满足

  $$f(x_0)=\inf \{f(z)\mid g_i(z)\le 0,\forall i;Az=b;\Vert z-x_0{\Vert }_2\le R\}$$

  则称 $x_0$ 为该优化问题的局部最优解.

关于最优解集, 有两条重要性质:

1. 由于 $f$ 和 $g_i$ 均为凸函数, 且约束条件均为凸集, 因此 $X_{\text{opt}}$ 也是凸集.

   Proof of convexity of the optimal solution set

   • 假设 $x_1,x_2\in X_{\text{opt}}$, 则对任意 $\theta \in [0,1]$, 有:
     • $g_i(\theta x_1+(1-\theta )x_2)\le \theta g_i(x_1)+(1-\theta )g_i(x_2)\le 0$, 因此 $\theta x_1+(1-\theta )x_2$ 满足不等式约束条件.
     • $A(\theta x_1+(1-\theta )x_2)=\theta A{x}_1+(1-\theta )A{x}_2=\theta b+(1-\theta )b=b$, 因此 $\theta x_1+(1-\theta )x_2$ 满足等式约束条件.
     • $f(\theta x_1+(1-\theta )x_2)\le \theta f(x_1)+(1-\theta )f(x_2)=p^{\star }$, 因此 $\theta x_1+(1-\theta )x_2$ 也是最优解.
   • 综上, $\theta x_1+(1-\theta )x_2\in X_{\text{opt}}$, 因此 $X_{\text{opt}}$ 是凸集.

   $\square$

2. 若 $f$ 严格凸, 则最优解若存在则唯一. 故可立刻推出任意局部最优解也是全局最优解.

   Proof of uniqueness under strict convexity

   • 假设存在 $x_1,x_2\in X_{\text{opt}}$, 且 $x_1\ne x_2$, 则对任意 $\theta \in (0,1)$, 有:
     • $f(\theta x_1+(1-\theta )x_2)<\theta f(x_1)+(1-\theta )f(x_2)=p^{\star }$, 这与 $p^{\star }$ 为最小值矛盾.
   • 因此, 最优解唯一.

   $\square$

1.3 Different Forms of Convex Optimization Problems

对于上述的优化问题, 我们还可以等价地给出其等价形式:

$$\begin{array}{r}\underset{x}{\min }f(x)\text{s.t.}x\in C\end{array}$$

• 其中 $C=\{x\mid g_i(x)\le 0,\forall i;Ax=b\}$ 是约束条件的可行域, 即所有满足约束条件的 $x$ 的集合.

亦或通过引入 indicator function ${\delta }_C(x)$, 将问题转化为如下无约束优化问题:

$$\begin{array}{r}\underset{x}{\min }f(x)+{\delta }_C(x)\end{array}$$

• 其中 ${\delta }_C(x)$ 是 indicator function, 定义为:

  $$\begin{array}{r}{\delta }_C(x)=\{\begin{array}{ll}0& \text{if }x\in C\\ \infty & \text{otherwise}\end{array}\end{array}$$

---

Example (LASSO). 给定 $\mathbf{y}\in {\mathbb{R}}^n$, $\mathbf{X}\in {\mathbb{R}}^{n\times p}$, LASSO 问题定义为:

$$\begin{array}{rl}\underset{\mathbf{\beta }\in {\mathbb{R}}^p}{\min }& \Vert \mathbf{y}-\mathbf{X}\mathbf{\beta }{\Vert }_2^2\\ \text{s.t.}& \Vert \mathbf{\beta }{\Vert }_1\le \lambda \end{array}$$

• 若 $n\ge p$ 且 $\mathbf{X}$ 是列满秩的, 则该问题的解是唯一的.

  Proof of uniqueness in the full-column-rank case

  考虑 ${\nabla }^2\Vert \mathbf{y}-\mathbf{X}\mathbf{\beta }{\Vert }_2^2=2{\mathbf{X}}^{\top }\mathbf{X}$, 由于 $\mathbf{X}$ 是列满秩的, 因此 ${\mathbf{X}}^{\top }\mathbf{X}$ 是正定矩阵, 故 $\Vert \mathbf{y}-\mathbf{X}\mathbf{\beta }{\Vert }_2^2$ 是严格凸函数, 因此该问题的解唯一.

  $\square$

• 若 $n<p$ 的高维场景, 则该问题可能存在多个解.

Example (SVM). 考虑如下支持向量机(SVM)的优化问题. 对于给定的训练数据集 $\{({\mathbf{x}}_i,y_i){\}}_{i=1}^n$, 其中 ${\mathbf{x}}_i\in {\mathbb{R}}^p$ 是样本特征, $y_i\in \{-1,1\}$ 是样本标签, SVM 的优化问题定义为 (其中 $\mathbf{\xi }=({\xi }_1,\dots ,{\xi }_n{)}^{\top }$ 是松弛变量, 允许一定程度的分类错误):

$$\begin{array}{rl}\underset{\mathbf{\beta }\in {\mathbb{R}}^p,{\beta }_0\in \mathbb{R},\mathbf{\xi }\in {\mathbb{R}}^n}{\min }& \frac{1}{2}\Vert \mathbf{\beta }{\Vert }_2^2+C\sum _{i=1}^n{\xi }_i\\ \text{s.t.}& y_i({\mathbf{x}}_i^{\top }\mathbf{\beta }+{\beta }_0)\ge 1-{\xi }_i,i=1,\dots ,n\\ & {\xi }_i\ge 0,i=1,\dots ,n\end{array}$$

---

1.4 First-Order Optimality Conditions

Theorem (First-Order Optimality Condition). 给定可微的凸函数 $f$, 考虑如下优化问题:

$$\begin{array}{r}\underset{x}{\min }f(x)\text{s.t.}x\in C\end{array}$$

则 $x^{\ast }$ 是该问题的最优解当且仅当:

$$\begin{array}{r}\nabla f(x^{\ast }{)}^{\top }(x-x^{\ast })\ge 0,\forall x\in C(\star )\end{array}$$

Proof of the first-order optimality condition

• $(\star )\Rightarrow x^{\ast }$ 是最优解:

  • 由凸性可知, 对于 $x^{\ast }$ 及任意 $y\in \text{dom}(f)$, 有

    $$f(y)\ge f(x^{\ast })+\nabla f(x^{\ast }{)}^{\top }(y-x^{\ast })$$

  • 由 $(\star )$ 可知, 对于任意 $y\in C$, 有 $\nabla f(x^{\ast }{)}^{\top }(y-x^{\ast })\ge 0$.

  • 又由于 $C\subseteq \text{dom}(f)$, 因此 $f(y)\ge f(x^{\ast })$ 对任意 $y\in C$ 成立, 即 $x^{\ast }$ 是最优解.

• $x^{\ast }$ 是最优解 $\Rightarrow (\star )$:
  • 用反证法, 假设 $x^{\ast }$ 是最优解但存在 $y\in C$ 使得 $\nabla f(x^{\ast }{)}^{\top }(y-x^{\ast })<0$.
  • 此时考虑从 $x^{\ast }$ 到 $y$ 的线段上的点 $z(t)=ty+(1-t)x^{\ast }$, 其中 $t\in [0,1]$. 并记在该点处的函数值为 $g(t):=f(z(t))$. 下尝试说明, 由反证法假设, 我们可以找到某 $t>0$ 使得 $z(t)\in C$ 且 $g(t)<g(0)=f(x^{\ast })$.
  • 首先由凸优化问题可知, $z(t)\in C$ 对任意 $t\in [0,1]$ 成立.
  • 接着考虑 $g(t)$ 的导数 $\mathrm{d}g(t)/\mathrm{d}t=\nabla f(z(t){)}^{\top }\frac{\mathrm{d}z(t)}{\mathrm{d}t}=\nabla f(z(t){)}^{\top }(y-x^{\ast })$. 特别地, 当 $t=0$ 时, 有 $\mathrm{d}g(0)/\mathrm{d}t=\nabla f(x^{\ast }{)}^{\top }(y-x^{\ast })<0$.
  • 由 $g^{\prime }(0)<0$ 和导数定义可知, 存在足够小的 $t_0>0$ 使得 $g(t_0)<g(0)=f(x^{\ast })$. 故矛盾.
• 从几何角度看, $\nabla f(x^{\ast }{)}^{\top }(y-x^{\ast })\ge 0$ 意味着向量 $y-x^{\ast }$ 与 $\nabla f(x^{\ast })$ 的夹角为锐角或直角, 即从 $x^{\ast }$ 指向任意 feasible point 的向量与 $\nabla f(x^{\ast })$ (即最陡上升方向)的夹角非钝角, 即从 $x^{\ast }$ 出发沿着任意 feasible point 的方向, 函数值都是不减的.

$\square$

---

Special Case (Unconstrained problem).

特别地, 当 $C={\mathbb{R}}^n$ 时, 上述条件退化为 $\nabla f(x^{\ast })=0$. 当 $f$ 是凸可微函数时, 该条件是全局最优的充要条件; 若 $f$ 进一步严格凸, 则该最优解唯一. 若为一般非凸可微函数, 则该条件仅为必要条件.

Proof of the unconstrained case

下说明退化之方式.

• 由于 $f$ 是可微函数, 因此在任意 $x\in \text{dom}(f)$, 都能找到小球 $B(x,ϵ)$ 使得 $B(x,ϵ)\subseteq \text{dom}(f)$, 即任意足够靠近 $x$ 的点都是 feasible point.
• 因此构造 $y=x^{\ast }-ϵ\nabla f(x^{\ast })$, 对于足够小的 $ϵ>0$, $y$ 仍是 feasible point.
• 因此, $\nabla f(x^{\ast }{)}^{\top }(y-x^{\ast })=\nabla f(x^{\ast }{)}^{\top }(-ϵ\nabla f(x^{\ast }))=-ϵ\Vert \nabla f(x^{\ast }){\Vert }_2^2\ge 0$. 又由于 $ϵ>0$, 因此 $\Vert \nabla f(x^{\ast }){\Vert }_2^2=0$. 故 $\nabla f(x^{\ast })=0$.

$\square$

---

Special Case (Equality constraints only).

考虑凸优化问题:

$$\begin{array}{r}\underset{\mathbf{x}\in {\mathbb{R}}^n}{\min }f(\mathbf{x})\text{s.t.}A\mathbf{x}=\mathbf{b}\end{array}$$

其中 $f$ 是可微函数, $A\in {\mathbb{R}}^{m\times n}$, $\mathbf{b}\in {\mathbb{R}}^m$.

对于仅含等式约束的凸优化问题其一阶条件退化为: 存在 ${\mathbf{u}}^{\ast }\in {\mathbb{R}}^m$ 使得

$$\begin{array}{r}\nabla f({\mathbf{x}}^{\ast })+A^{\top }{\mathbf{u}}^{\ast }=0\end{array}$$

其中 ${\mathbf{u}}^{\ast }$ 是拉格朗日乘子, 该条件亦称为 Lagrange Multiplier Optimality Condition.

Proof of the equality-constrained case

• 根据初始的一阶最优条件, ${\mathbf{x}}^{\ast }$ 应当满足 $A{\mathbf{x}}^{\ast }=\mathbf{b}$; 且对所有满足 $A\mathbf{y}=\mathbf{b}$ 的 $\mathbf{y}$, 有

  $$\begin{array}{r}\nabla f({\mathbf{x}}^{\ast }{)}^{\top }(\mathbf{y}-{\mathbf{x}}^{\ast })\ge 0.\end{array}$$

• 由于 $\mathbf{y},{\mathbf{x}}^{\ast }$ 同时满足等式约束, 故 $A(\mathbf{y}-{\mathbf{x}}^{\ast }):=A\mathbf{u}=0$. 这说明, 所有的可行位移都应处在 $A$ 的零空间内, 即 $\mathbf{u}\in \text{Nul}(A)=\{\mathbf{u}\mid A\mathbf{u}=0\}$. 换言之, 所有可行的 $\mathbf{y}$ 都应满足 $\mathbf{y}={\mathbf{x}}^{\ast }+\mathbf{u},\mathbf{u}\in \text{Nul}(A)$, 即 $\mathbf{y}$ 和 $\mathbf{u}$ 是一一对应的, 故最优性条件可以改写为:

  $$\begin{array}{r}\nabla f({\mathbf{x}}^{\ast }{)}^{\top }\mathbf{u}\ge 0,\forall \mathbf{u}\in \text{Nul}(A)\end{array}$$

• 而由于 $\mathbf{u}$ 的取值任意性, 必有 $\nabla f({\mathbf{x}}^{\ast }{)}^{\top }\mathbf{u}=0$. 这是因为定同时有 $\nabla f({\mathbf{x}}^{\ast }{)}^{\top }\mathbf{u}\ge 0$ 和 $\nabla f({\mathbf{x}}^{\ast }{)}^{\top }(-\mathbf{u})\ge 0$ 成立. 故有

  $$\begin{array}{r}\nabla f({\mathbf{x}}^{\ast }{)}^{\top }\mathbf{u}=0,\forall \mathbf{u}\in \text{Nul}(A)\end{array}$$

• 而这一表述等价于 $\nabla f({\mathbf{x}}^{\ast })\perp \text{Nul}(A)$. 又根据线性代数结论, $A$ 的 Null Space 的正交补空间为 Row Space, 即 $A^{\top }$ 的 Column Space, 因此 $\nabla f({\mathbf{x}}^{\ast })\in \text{Col}(A^{\top })$, 即存在 $\mathbf{v}\in {\mathbb{R}}^m$, 使得 $\nabla f({\mathbf{x}}^{\ast })=A^{\top }\mathbf{v}$. 记 ${\mathbf{u}}^{\ast }=-\mathbf{v}$, 则有

  $$\begin{array}{r}\nabla f({\mathbf{x}}^{\ast })+A^{\top }{\mathbf{u}}^{\ast }=0.\end{array}$$

$\square$

2. Equivalence between Different Forms of Optimization Problems

有一些变换可以将不同形式的优化问题相互转化.

2.1 Transforms of Variables

设 $\varphi :{\mathbb{R}}^n\to {\mathbb{R}}^n$ 是一个 1-1 映射, 其象能够包含原始问题的定义域 $\mathcal{D}$ (即 $\varphi (\text{dom}(\varphi ))\supseteq \mathcal{D}$). 则原始问题:

$$\begin{array}{rl}\min f(x)& \\ \text{s.t.}{g}_i(x)& \le 0,i=1,\dots ,m\\ h_j(x)& =0,j=1,\dots ,p\end{array}$$

等价于:

$$\begin{array}{rl}\min f(\varphi (z)):=\tilde{f}(z)& \\ \text{s.t.}{g}_i(\varphi (z)):={\tilde{g}}_i(z)& \le 0,i=1,\dots ,m\\ h_j(\varphi (z)):={\tilde{h}}_j(z)& =0,j=1,\dots ,p\end{array}$$

显然, 如果 $x$ 解决了原始问题, 则 $z={\varphi }^{-1}(x)$ 解决了变换后的问题, 反之亦然.

2.2 Transforms of Objective and Constraint Functions

对于单调递增函数 ${\psi }_0:\mathbb{R}\to \mathbb{R}$; 以及函数 ${\psi }_1,\dots ,{\psi }_m:\mathbb{R}\to \mathbb{R}$ 满足当且仅当 $t\le 0$ 时 ${\psi }_i(t)\le 0$, 函数 ${\psi }_{m+1},\dots ,{\psi }_{m+p}:\mathbb{R}\to \mathbb{R}$ 满足当且仅当 $t=0$ 时 ${\psi }_j(t)=0$, 则原始问题等价于

$$\begin{array}{rl}\min {\psi }_0(f(x))& :=\tilde{f}(x)\\ \text{s.t.}{\psi }_i(g_i(x))& :={\tilde{g}}_i(x)\le 0,i=1,\dots ,m\\ {\psi }_{m+j}(h_j(x))& :={\tilde{h}}_j(x)=0,j=1,\dots ,p\end{array}$$

Example (Minimizing Euclidean Norm). 无约束的 Euclidean 范数最小化问题:

$$\begin{array}{r}\underset{x}{\min }\Vert Ax-b{\Vert }_2\end{array}$$

等价于:

$$\begin{array}{r}\underset{x}{\min }\Vert Ax-b{\Vert }_2^2\end{array}$$

• 虽然这两个问题是等价的, 但并不相同, 二者在定义域上的可微性不同.

2.3 Partial Optimum

如果 $f$ 关于 $(x,y)$ 是凸函数, 且 $C$ 是非空凸集, 则函数

$$\begin{array}{r}g(x)=\underset{y\in C}{\inf }f(x,y)\end{array}$$

也是 $x$ 的凸函数 (只要 $g(x)$ 在其定义域内取值有限).

• 其中 $\text{dom}(g)=\{x\mid \exists y\in C,\text{ s.t. }(x,y)\in \text{dom}(f)\}$, 即 $\text{dom}(f)$ 在 $x$ 方向上的投影.

Proof of convexity under partial minimization

• 根据 Infimum 的定义, 对于任意 $x_1,x_2\in \text{dom}(g)$, 以及任意 $ϵ>0$, 存在 $y_1,y_2\in C$ 使得:

  $$\begin{array}{rl}g(x_1)& \ge f(x_1,y_1)-ϵ\\ g(x_2)& \ge f(x_2,y_2)-ϵ\end{array}$$

• 根据 $g$ 的定义, 对于对于任意 $\theta \in [0,1]$:

  $$\begin{array}{rl}g(\theta x_1+(1-\theta )x_2)& =\underset{y\in C}{\inf }f(\theta x_1+(1-\theta )x_2,y)\\ & \le f(\theta x_1+(1-\theta )x_2,\theta y_1+(1-\theta )y_2)(\text{Infimum})\\ & \le \theta f(x_1,y_1)+(1-\theta )f(x_2,y_2)(\text{Jensen Ineq.})\\ & =\theta g(x_1)+(1-\theta )g(x_2)+ϵ(\text{Infimum})\end{array}$$

• 由于 $ϵ>0$ 是任意的, 故有:

  $$\begin{array}{r}g(\theta x_1+(1-\theta )x_2)\le \theta g(x_1)+(1-\theta )g(x_2)\end{array}$$

$\square$

因此, 该性质说明, 我们能够将一个关于多个变量的凸函数, 通过对部分变量取 Infimum 的方式, 得到一个关于剩余变量的凸函数.

2.4 Eliminating Equality Constraints

考虑如下优化问题:

$$\begin{array}{r}\underset{\mathbf{x}\in {\mathbb{R}}^n}{\min }f(\mathbf{x})\text{s.t.}A\mathbf{x}=\mathbf{b},g_j(\mathbf{x})\le 0,j=1,\dots ,p\end{array}$$

• 其中 $A\in {\mathbb{R}}^{m\times n}$, $\mathbf{b}\in {\mathbb{R}}^m$.

则可以通过如下变换将等式约束消除. 对等式约束, 我们可以确定任意一个 particular solution ${\mathbf{x}}_0$ 满足 $A{\mathbf{x}}_0=\mathbf{b}$. 则任意满足等式约束的 $\mathbf{x}$ 都可以表示为:

$$\begin{array}{r}\mathbf{x}={\mathbf{x}}_0+\mathbf{v},\text{where }\mathbf{v}\in \text{Nul}(A)\end{array}$$

• 这是因为对于任意满足 $A\mathbf{x}=\mathbf{b}$ 的 $\mathbf{x}$, 有 $A(\mathbf{x}-{\mathbf{x}}_0)=0$, 因此 $\mathbf{v}:=\mathbf{x}-{\mathbf{x}}_0\in \text{Nul}(A)$.

对于 $\text{Nul}(A)$, 其维度 $\text{dim}(\text{Nul}(A))=n-\text{rank}(A):=k$, 故可以找到一组基 $\{{\varphi }_1,\dots ,{\varphi }_k\}$ 使得 $\text{Nul}(A)=\text{span}\{{\varphi }_1,\dots ,{\varphi }_k\}$. 换言之, 对于任意 $\mathbf{v}\in \text{Nul}(A)$, 都存在 $z_1,\dots ,z_k\in \mathbb{R}$ 使得:

$$\begin{array}{r}\mathbf{v}=\sum _{i=1}^k{z}_i{\varphi }_i:=\Phi \mathbf{z},\end{array}$$

• 其中 $\Phi =[{\varphi }_1,\dots ,{\varphi }_k]\in {\mathbb{R}}^{n\times k}$, $\mathbf{z}=(z_1,\dots ,z_k{)}^{\top }\in {\mathbb{R}}^k$.

故我们可以将 $\mathbf{x}$ 表示为 $\mathbf{x}={\mathbf{x}}_0+\Phi \mathbf{z}$, 因此原始问题等价于:

$$\begin{array}{r}\underset{\mathbf{z}\in {\mathbb{R}}^k}{\min }f({\mathbf{x}}_0+\Phi \mathbf{z}),\text{s.t.}{g}_j({\mathbf{x}}_0+\Phi \mathbf{z})\le 0,j=1,\dots ,p\end{array}$$

2.5 Slack Variables to Eliminate Inequality Constraints

注意到 $g_i(x)\le 0$ 等价于 存在 $s_i\ge 0$ 使得 $g_i(x)+s_i=0$. 因此, 原始问题

$$\begin{array}{rl}\underset{x}{\min }& f(x)\\ \text{s.t.}& g_i(x)\le 0,i=1,\dots ,m;\\ & h_j(x)=0,j=1,\dots ,p\end{array}$$

等价于:

$$\begin{array}{rl}\underset{x,s}{\min }& f(x)\\ \text{s.t.}& g_i(x)+s_i=0,i=1,\dots ,m;\\ & h_j(x)=0,j=1,\dots ,p;\\ & s_i\ge 0,i=1,\dots ,m\end{array}$$

其中 $s_i$ 称作 slack variable. 通过引入 $s_i$, 每个不等式约束都可以转化为一个等式约束加上一个非负约束.

然而, 除非 $g_i,i=1,\dots ,m$ 都是 affine 函数, 否则该变换并不保持凸性.

2.6 Relaxation Non-affine Equality Constraints

考虑一般的优化问题:

$$\begin{array}{rl}\underset{x}{\min }& f(x)\text{s.t.}x\in C\end{array}$$

我们总可以找到一个更大的集合 $\tilde{C}\supseteq C$, 考虑

$$\begin{array}{rl}\underset{x}{\min }& f(x)\text{s.t.}x\in \tilde{C}\end{array}$$

则该问题称作原始问题的 relaxation. 显然, 对于最小化问题, relaxation 问题的最优值不大于原始问题的最优值.

• 特别地, 对于凸但非 affine 的等式约束 $h_j(x)=0$, 我们可以考虑将其放松为 $h_j(x)\le 0$, 以确保凸性.

• 注意, relaxation 问题的解不一定是原始问题的可行解, 其只能作为原始问题的下界估计. 若 relaxation 问题的解恰好是原始问题的可行解, 则该解也是原始问题的最优解.