优化作业4

1

若在点 $x^*$ 处 KKT 条件满足，$\{a_i(x^*),i\in I^*\cup E\}$ 线性无关，证明：$x^*$对应的 Lagrange 乘子 $\lambda^*$ 唯一.

$$g^* =\sum_{i \in \mathscr{A^*}}\lambda_i^*a_i^*$$

由于线性无关性，则 $\lambda_i^*$ 作为其系数一定唯一

2

首先判断是否满足约束条件。$x^{(1)},x^{(3)}$ 满足， $x^{(2)}$ 不满足，所以不是解。

$$L(x,\lambda) = (x_1-1)^2+(x_2-2)^2 - \lambda_1(-x_1^2+x_2) -\lambda_2 (6-x_1-x_2) - \lambda_3x_1-\lambda_4x_2$$

KKT:

$$\frac{\partial L}{\partial x_1} = 2x_1 - 2 +2\lambda_1x_1+\lambda_2-\lambda_3=0$$

$$\frac{\partial L}{\partial x_2} = 2x_2 -4 -\lambda_1+\lambda_2-\lambda_4=0\\ \lambda_1(-x_1^2+x_2)=0\\ \lambda_2 (6-x_1-x_2)=0\\ \lambda_3x_1=0\\ \lambda_4x_2=0\\ \lambda_i \geq 0\\ I\cup E$$

对于 $x^{(1)}$ ，起作用的约束为第一个，在此点有可行的下降方向为负梯度方向，所以不是最优解。
对于 $x^{(2)}$，同样有可行的下降方向$(1,0)$

3

1

$$L(x,\lambda) = (x_1-1)^2+(x_2-2)^2 - \lambda[(x_1-1)^2 - 5 x_2]$$

$$\frac{\partial L}{\partial x_1} = 2x_1 - 2-\lambda(2x_1-2) =0$$

$$\frac{\partial L}{\partial x_2} = 2x_2 -3 +5\lambda = 0\\ \lambda \geq 0\\ (x_1-1)^2 - 5 x_2 = 0\\$$

$x^* = (x_1,x_2) = (1,0)^T\quad \lambda = \frac3 5\qquad a(x^*) = (0,-5)^T$

$$\mathcal{F} = \{(d_1,0)^T|d_1\neq 0\}\\ W^* = \begin{bmatrix} 1-\lambda &\\ &1 \end{bmatrix} = \begin{bmatrix} \frac2 5&\\ &1 \end{bmatrix} \\ d^TW^*d > 0$$

所以是最优解

2

$$L(x,\lambda) =(x_1+x_2)^2 +2x_1+x_2^2 + \lambda_1(x_1+3x_2-4) + \lambda_2 (2x_1+x_2-3) - \lambda_3x_1 - \lambda_4 x_2$$

$$\frac{\partial L}{\partial x_1} = 2x_1 +2x_2+2 +\lambda_1+2\lambda_2-\lambda_3 = 0$$

$$\frac{\partial L}{\partial x_2} = 4x_2 +2x_1 +3\lambda_1+\lambda_2-\lambda_4 = 0\\ x_1+3x_2-4 \leq 0\\ 2x_1+x_2-3 \leq 0\\ x_1 \geq 0, x_2\geq 0\\ \lambda_1(x_1+3x_2-4) = 0\\ \lambda_2 (2x_1+x_2-3) = 0\\ \lambda_3x_1 = 0\\ \lambda_4 x_2 = 0\\ \lambda_i\geq 0$$

$x^* = (0,0)^T\quad \lambda_1 = 0,\lambda_2 = 0,\lambda_3 = 2,\lambda_4 =0$
$a_3(x^*) = (1,0),a_4(x^*) = (0,1)$

$$\mathcal{F} = \{d|d^Ta_i= 0,d\neq 0\} = \emptyset$$

所以是最优解