1 2( ( ⎨最优化方法部分课后习题解答1.一直优化问题的数学模型为：习题一min f (x ) = (x − 3)2 + (x − 4)2⎧g (x ) = x − x − 5 ≥ 0 ⎪ 11 2 2 ⎪试用图解法求出：s .t . ⎨g 2 (x ) = −x 1 − x 2 + 5 ≥ 0 ⎪g (x ) = x ≥ 0 ⎪ 3 1 ⎪⎩g 4 (x ) = x 2 ≥ 0（1） 无约束最优点，并求出最优值。

（2） 约束最优点，并求出其最优值。

（3） 如果加一个等式约束 h (x ) = x 1 −x 2 = 0 ，其约束最优解是什么？ *解 ：（1）在无约束条件下， f (x ) 的可行域在整个 x 1 0x 2 平面上，不难看出，当 x =（3，4） 时， f (x ) 取最小值，即，最优点为 x * =（3，4）：且最优值为： f (x * ) =0（2）在约束条件下， f (x ) 的可行域为图中阴影部分所示，此时，求该问题的最优点就是在约束集合即可行域中找一点 (x 1 ,x 2 ) ，使其落在半径最小的同心圆上，显然，从图示中可以看出，当 x *=15 , 5 ) 时， f (x ) 所在的圆的半径最小。

4 4⎧g (x ) = x −x − 5 = 0⎧ 15 ⎪x 1 = 其中：点为 g 1 (x) 和 g 2 (x ) 的交点，令 ⎪ 1 1 2 ⎨2 求解得到： ⎨ 45即最优点为 x *= ⎪⎩g 2 (x ) = −x 1 −x 2 + 5 = 015 , 5 ) ：最优值为： f(x * ) = 65 ⎪x =⎪⎩ 2 44 48（3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。

2.一个矩形无盖油箱的外部总面积限定为 S ，怎样设计可使油箱的容量最大？试列出这个优化问题的数学模型，并回答这属于几维的优化问题. 解：列出这个优化问题的数学模型为：max f (x ) = x 1x 2 x 3⎧x 1x 2 + 2x 2 x 3 + 2x 1x 3 ≤ S ⎪ s .t . ⎪x 1 > 0⎪x 2 > 0 ⎪⎩x 3 > 0该优化问题属于三维的优化问题。

⎝⎠i j n×n 1 2 n 1 2 nn⎝⎠⎪1 x=y=z=v=s3==1⎛=s⎞218 2⎪3⎪习题二3.计算一般二次函数f(x) =1X T A X +b T X +c的梯度。

2解：设：A=(a ) ,b=(b,b ,...b )T, X = (x ,x,...x )T 则：f(x) =1n n na xx +bx +c，将它对变量x(i=1, 2,...n) 球偏导数得：∑∑i j i j∑i i i2 i=1j=1i=1⎡1n 1 n⎤⎡n⎤⎡n ⎤⎡∂f(x) ⎤⎪∑a1 j x j +∑a i1x i +b1 ⎪⎪∑a1j x j ⎪⎪∑a i1x i⎪⎪⎪⎪2 j=1 2 i=1⎪⎪j=1⎪⎪i=1⎪⎪∂x1 ⎪⎪1n 1 n⎪⎪n⎪⎪n⎪⎡b ⎤⎪∂f (x) ⎪⎪∑a2 j x j +∑a i2x i+b2⎪∑a j x j ⎪∑a i2x i⎪⎪⎪∇f(x) = ⎪⎪= ⎪2j=12 i=11 ⎪2⎪=⎪+1+ b⎪j=1⎪⎪i=1⎪⎪ 2 ⎪⎪∂x2 ⎪⎪⋮⎪ 2 ⎪⋮⎪ 2 ⎪⋮⎪⎪b⎪⎪∂f(x) ⎪⎪⎪⎪⎪⎪⎪⎣ 3 ⎦⎪⎪⎪1n 1 n⎪⎪n⎪⎪⎪⎣∂x3 ⎦⎪∑a nj x j +∑a i n x i +b n ⎪⎪∑a nj x j⎪⎪∑a i n x i⎪⎣2 j=11 T2 i=1⎦⎣j=1⎦⎣i=1⎦= (A X + A X) +b25.求下列函数的梯度和Hesse 矩阵（1）f(x) = x2 +2x 2 +3x 2 −4xx⎛2 0 -4 ⎞解：∇2f (x) =⎪0 4 0⎪1 2 3 1 3⎛x2e x1x2⎪⎪⎪−4 0 6 ⎪6x +e x1x2 +xx e x1x2 ⎞（2）f(x) =3xx 2 +e x1x2解：∇2f (x) =⎪2 2 1 21 2 1 2 1 2 ⎪1 2 6x +e x x +xx e x x6x+x2e x x⎝ 2 1 2 1 1 ⎠6.判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：1 2 1 2 1 21 2 1 1 2 2 1 （1） f (x , x ) = −x 2+2x 2 + 3xx 解： ∇2 f (x ) 不是半正定，即 f (x ) 非凸，然后判断- f (x ) ，经验证： ∇2 (− f (x )) 不是半 正定，由此可知： f (x ) 非凸非凹。

（2） f (x , x ) = 2x 2 − 4xx + 3x 2 − 5x −6 解： ∇2 f (x ) 半正定，故 f (x ) 为凸函数。

1 12 2 2 1 2 1 2 T12⎨ 2 2k 1 （3） 222f (x 1 , x 2 , x 3 ) = x 1+ 2x 2 − 3x 3 −4x 1x 2 解： ∇2 f (x ) 不是半正定，即 f (x ) 非凸，然后判断- f (x ) ，经验证： ∇2 (− f (x )) 不是半正定，由此可知： f (x ) 非凸非凹。

7.设约束优化问题的数学模型为：min f (x ) = x 2 + 4x + x 2 − 4x +10⎧g 1 (x ) = x 1 − x 2 + 2 ≥ 0 s .t . ⎨⎩g (x ) = −x 2 − x 2 − 2x + 2x ≥ 0试用 K-T 条件判别点 x = [−1,1]T是否为最优点。

解：对于点 x = [−1,1]T， g (x ) =0， g (x ) ≥ 0 ，点满足约束条件，故点 X 是可行解。

1 2 ⎛2 ⎞⎛1 ⎞且 g 1 (x) 是起作用约束，I = {1} , ∇f (x ) = ⎪ ⎪ , ∇g 1 (x ) = ⎪ ⎪ ，由 ∇g i (x ) ≥ 0 条件下的 ⎝ −2 ⎠ ⎝−1⎠K-T 条件得： ∇f (x ) −∑λi ∇g i (x ) = 0, λi ≥ 0 ，得到 λ1 = 2 ，点 x = [−1,1]i ∈I满足 K-T 条件。

又因 ∇2 f (x ) 正定，故 f (x ) 为严格凸函数，该最优化问题是凸规划问题，由x * = [−1,1]T是 K-T 点，所以 x * = [−1,1]T也是该问题的全局最优点。

8.设约束优化问题：min f (x ) = (x − 2)2 + x 2⎧g 1 (x ) = −x 1 ≤ 0 s .t . ⎪g (x ) = −x ≤ 0 ⎪g (x ) = −1 + x 2 + x ≤ 0 ⎩ 3 1 2它的当前迭代点为 x = [1, 0]T，试用 K-T 条件判定它是不是约束最优解。

解：对于点 x = [1, 0]Tg (x ) = −1 ≤ 0, g (x ) = 0, g (x ) = 0 ，点 x = [1, 0]T是 可 行 点 ， k 1 k 2 k 3 kk⎛ −2 ⎞ ⎛0 ⎞ 且起作用的约束条件是， g 2 (x ), g 3 (x ) ， I = {2, 3} , ∇f (x k ) = ⎪ ⎪ ， ∇g 2 (x k ) = ⎪ ⎪ ⎝ 0 ⎠ ⎝ −1⎠⎛2 ⎞ ∇g3 (x k ) = ⎪ ⎪ ，由约束条件为 g i (x ) ≤ 0 时的 K-T 条件得，应有：⎝ ⎠⎧λ2 = 1 T∇f (x ) + ∑λi ∇g i (x ) = 0,λi ≥ 0解得： ⎨ ，所以 x = [1, 0] λ = 1 k为 K-T 点。

i ∈I⎩ 31 2 k ⎩⎝ ⎠ 现判断该问题是否为凸规划问题，因 ∇2f (x ) 正定，故 f (x ) 为凸函数，g (x ), g (x ) 为 线性函数，亦为凸函数， ∇2g (x ) 半正定，所以 g (x ) 为凸函数，所以该优化问题为凸 3 3规划问题，即点 x =[1, 0]T是该问题的约束最优解。

习题三1. 对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。

max f (x ) = 3x 1 +x 2 + 2x 3 ⎧12x 1 + 3x 2 + 6x 3 + x 4 = 9 ⎪（1） ⎪8x 1 +x 2 − 4x 3 + 2x 5 = 10 s .t . ⎨⎪3x 1 − x 6 = 0 ⎪x j ≥ 0, ( j = 1, 2...6)⎛12 3 6 3 0 0 ⎞ ⎪ ⎪ 解：令 A = ⎪ 8 1 -4 0 2 0⎪ = (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 )⎪ 3 0 0 0 0 -1 ⎪（1） 基解 x = (0,16 , − 7, 0, 0, 0) 不是基可行解， 1 3 6（2） 基解 x 2 = (0,10, 0, 7, 0, 0) 不是基可行解，（3） 基解 x 3= (0, 3, 0, 0, 3.5, 0) 是基可行解，且 f (x ) = 3 ， 7 21（4） 基解 x 4 = ( , −4, 0, 0, 0, 45) 不是基可行解，4 （5） 基解 x5 = (0,0, − , 8, 0, 0) 不是基可行解， 2 （6） 基解 x = (0, 0, 3, 0,16, 0) 是基可行解，且 f (x ) = 3 ， 62 （7） 基解 x = (1, 0, − 1, 0, 0, 3) 不是基可行解， 72（8） 基解 x 8 = (0,0, 0, 3, 5, 0) 是基可行解，且 f (x ) = 0 ，（9） 基解 x = ( 5 ,0, 0, −2, 0, 15) 不是基可行解。

9 4 4 3 9 9（10） 基解 x 10 = ( 4 ,0, 0, 0, 4, 4) 是基可行解，且 f (x ) = 4 。

16 7（11） 基解 x 11 = (0, 3 , − 6, 0, 0, 0) 不是基可行解。

（12） 基解 x 12 = (0,10,0, −7, 0, 0) 不是基可行解。

7（13） 基解 x 13 = (0,3, 0, 0, 2, 0) 是基可行解，且 f (x ) = 3 。

⎪⎨5 1 2 ⎪ ⎨5 1 2 4 （14） 基解 x = (0, 0, − 5, 8, 0, 0) 不是基可行解。

142（15） 基解 x = (0, 0, 3, 0, 8, 0) 是基可行解，且 f (x ) = 3 。

15 2（16） 基解 x 16 = (0, 0, 0, 3, 5, 0) 是基可行解，且 f (x ) = 3 。