历年真题

2023

最优化问题 \(\min f(x),\ \text{s.t. } x\in D\)，满足 \(\underline{\qquad\qquad}\) 称为可行解。

答案：约束条件（即 \(x\in D\)）

设函数 \(f(x)\) 在凸集 \(D\) 上有定义，如果对任意 \(x,y\in D,\ x\ne y\) 和任意 \(\lambda\in(0,1)\)，有 \(\underline{\qquad\qquad}\) ，则称 \(f\) 是凸集 \(D\) 上的严格凸函数。

答案：\(f(\lambda x+(1-\lambda)y)\ <\ \lambda f(x)+(1-\lambda)f(y)\)

若 \(x^*\in D\)，对一切 \(x\in D' (x\ne x^*)\) 恒有 \(\underline{\qquad\qquad}\)，则称 \(x^*\) 为最优化问题 \(\min f(x),\text{s.t. }x\in D\) 的严格整体最优解。

答案：\(f(x) > f(x^*)\)

用黄金分割法求函数 \(f(x)=x^3+3x^2-9x+5\) 在区间 \([0,3]\) 的最小值。此时 \(x\) 取值是多少？要求最后 \(x\) 误差小于 \(1\)。

解析:

取 \(\rho=\frac1\varphi\approx0.618\)。

初始区间 \([a_0,b_0]=[0,3]\)，计算

\[ x_1=b_0-\rho(b_0-a_0),\quad x_2=a_0+\rho(b_0-a_0). \]

每步比较 \(f(x_1)\) 与 \(f(x_2)\)，保留函数值较小一侧，直到区间长度 \(\le 1\)。

迭代记录（取 3 步即可满足 \(\,b-a<1\)）

步 \(k\)	\([a_k,b_k]\)	\(x_1\)	\(x_2\)	\(f(x_1)\)	\(f(x_2)\)
1	\([0,\,3]\)	1.145898	1.854102	0.130823	5.000000
2	\([0,\,1.854102]\)	0.708204	1.145898	0.486025	0.130823
3	\([0.708204,\,1.854102]\)	1.145898	1.416408	0.130823	1.112576

第 3 步后更新得新区间 \([a,b]=[0.708204, 1.416408]\)，长度 \(b-a=0.708204<1\)。取：

\[ x^*\approx \frac{a+b}{2}=1.062306,\qquad f(x^*)\approx 0.02353. \]

证明：两个凸集的和是凸集

解析:

设 \(D_1,D_2\) 为凸集，定义 \(D_1+D_2=\{x+y\mid x\in D_1,\ y\in D_2\}\)。取任意 \(u_1,u_2\in D_1\) 与 \(v_1,v_2\in D_2\) 及 \(\lambda\in[0,1]\)。

因 \(D_1,D_2\) 凸，有 \(\lambda u_1+(1-\lambda)u_2\in D_1\)、\(\lambda v_1+(1-\lambda)v_2\in D_2\)。于是：

\[ \lambda(u_1+v_1)+(1-\lambda)(u_2+v_2) = \big(\lambda u_1+(1-\lambda)u_2\big)+\big(\lambda v_1+(1-\lambda)v_2\big)\in D_1+D_2, \]

故 \(D_1+D_2\) 为凸集。

用定义证明 \(f(x)=e^x\) 在 \(\mathbb{R}\) 内是下凸函数。

解析:

对于任意 \(x_1 \in \mathbb R, d > 0\)，我们欲证明：

\[ \begin{aligned} &&\exp(x_1 + \lambda d) &\le (1-\lambda)\exp(x_1) + \lambda \exp(x_1 + d) \\ &\Leftrightarrow& \exp(\lambda d) &\le (1 - \lambda) + \lambda \exp(d) \end{aligned} \]

在 \(\lambda \in [0,1]\) 时成立。考虑函数 \(f(\lambda) = (1 - \lambda) + \lambda \exp(d) - \exp(\lambda d)\)，在 \(\lambda = 0, 1\) 时 \(f(\lambda) = 0\)，待证明的目标为 \(f(\lambda) \ge 0\)。

先写出两阶导数：\(f'(\lambda) = \exp(d) - 1 - d\exp(\lambda d)\)，\(f''(\lambda) = -d^2 \exp(\lambda d)\)。

由于 \(f'(0) = \exp(d) - (d + 1) > 0\)，所以在 \(0^+\) 处 \(f(\lambda) > 0\)。接下来若能证明 \((0,1)\) 上没有零点，则说明在 \((0,1)\) 上恒有 \(f(\lambda) > 0\)。

使用反证法：设存在 \(c \in (0,1)\) 满足 \(f(c) = 0\)，则存在 \(\xi_1 \in (0, c), \xi_2 \in(c, 1)\) 使得 \(f'(\xi_1) = f'(\xi_2) = 0\)，则存在 \(\eta \in (\xi_1, \xi_2)\) 使得 \(f''(\eta) = 0\)。但是 \(f''(\eta) = -d^2 \exp(\eta d) \ne 0\)，矛盾，所以 \(f(\lambda)\) 在 \((0,1)\) 上不存在零点，\(f(\lambda) > 0\)，即原函数为凸函数。

2024

函数 \(f(x) = -e^{(-x^3 + x)}\) 在区间 \([0.35, 0.75]\)，用黄金分割法求极小值。求迭代两次后的区间，并以区间中点作为最终结果。

解析：

取 \(\rho\approx0.618\)。初始区间 \([a_0,b_0]=[0.35,0.75]\)，计算：

\[ x_1=b_0-\rho(b_0-a_0),\qquad x_2=a_0+\rho(b_0-a_0). \]

每步比较 \(f(x_1)\) 与 \(f(x_2)\)，保留函数值较小的一侧，直到完成两次迭代。

迭代记录

步 \(k\)	区间 \([a_k,b_k]\)	\(x_1\)	\(x_2\)	\(f(x_1)\)	\(f(x_2)\)
1	\([0.35,0.75]\)	0.503	0.597	-1.4560	-1.4685
2	\([0.503,0.75]\)	0.597	0.656	-1.4685	-1.4531

第 2 步后更新得新区间

\[ [a,b]=[0.503,0.656]. \]

取区间中点为最终结果：

\[ x^*=\frac{a+b}{2}=0.5795, \quad f(x^*)=-1.4694 \]

已知 \(f_i\) 是凸集 \(D\) 上的凸函数，证明 \(3f_1 + 4f_2 + 5f_3\) 也是凸函数。

解析：

由定义，若函数 \(f_i\) 在凸集 \(D\) 上凸，则对任意 \(x_1,x_2\in D\) 和 \(\lambda\in[0,1]\)，有：

\[ f_i(\lambda x_1+(1-\lambda)x_2) \le \lambda f_i(x_1)+(1-\lambda)f_i(x_2). \]

对三个凸函数分别成立上述不等式。将它们分别乘以正数 \(3,4,5\)，再相加得：

\[ \begin{aligned} &3f_1(\lambda x_1+(1-\lambda)x_2) \\ +&4f_2(\lambda x_1+(1-\lambda)x_2) \\ +&5f_3(\lambda x_1+(1-\lambda)x_2) \\ \le\quad & \lambda [3f_1(x_1)+4f_2(x_1)+5f_3(x_1)] \\ +&(1-\lambda)[3f_1(x_2)+4f_2(x_2)+5f_3(x_2)]. \end{aligned} \]

令

\[ F(x)=3f_1(x)+4f_2(x)+5f_3(x), \]

则上式即为：

\[ F(\lambda x_1+(1-\lambda)x_2) \le \lambda F(x_1)+(1-\lambda)F(x_2). \]

因此，\(F(x)\) 满足凸函数定义，故 \(3f_1+4f_2+5f_3\) 是 \(D\) 上的凸函数。