没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
最优化方法-习题解答
张彦斌
计算机学院
2014年10月20日
Contents
1 第第第一一一章章章最最最优优优化化化理理理论论论基基基础础础-P13习习习题题题1(1)、、、2(3)(4)、、、3、、、4 1
2 第第第二二二章章章线线线搜搜搜索索索算算算法法法-P27习习习题题题2、、、4、、、6 4
3 第第第三三三章章章最最最速速速下下下降降降法法法和和和牛牛牛顿顿顿法法法P41习习习题题题1,,,2,,,3 7
4 第第第四四四章章章共共共轭轭轭梯梯梯度度度法法法P51习习习题题题1,,,3,,,6(1) 10
5 第第第五五五章章章拟拟拟牛牛牛顿顿顿法法法P73-2 12
6 第第第六六六章章章信信信赖赖赖域域域方方方法法法P86-8 14
7 第第第七七七章章章非非非线线线性性性最最最小小小二二二乘乘乘问问问题题题P98-1,,,2,,,6 18
8 第第第八八八章章章最最最优优优性性性条条条件件件P112-1,,,2,5,6 23
9 第第第九九九章章章罚罚罚函函函数数数法法法P132,,,1-(1)、、、2-(1)、、、3-(3),6 26
10 第第第十十十一一一章章章二二二次次次规规规划划划习习习题题题11 P178-1(((1))),,,5 29
1 第第第一一一章章章最最最优优优化化化理理理论论论基基基础础础-P13习习习题题题1(1)、、、2(3)(4)、、、3、、、4
1.验证下列各集合是凸集:
(1) S={(x
1
,x
2
)|2x
1
+x
2
≥1,x
1
− 2x
2
≥ 1};
需要验证:
根据凸集的定义,对任意的x(x
1
, x
2
), y(y
1
, y
2
) ∈ S及任意的实数λ ∈ [0, 1],都
有λx + (1 − λ)y ∈ S.
即,(λx
1
+ (1 − λ)y
1
, λx
2
+ (1 − λ)y
2
) ∈ S
证:由x(x
1
, x
2
), y(y
1
, y
2
) ∈ S得到,
{
2x
1
+ x
2
≥ 1, x
1
− 2x
2
≥ 1
2y
1
+ y
2
≥ 1, y
1
− 2y
2
≥ 1
(1)
1
把(1)中的两个式子对应的左右两部分分别乘以λ和1 − λ,然后再相加,即得
λ(2x
1
+ x
2
) + (1 − λ)(2y
1
+ y
2
) ≥ 1,
λ(x
1
− 2x
2
) + (1 − λ)(y
1
− 2y
2
) ≥ 1
(2)
合并同类项,
2(λx
1
+ (1 − λ)y
1
) + (λx
2
+ (1 − λ)y
2
) ≥ 1,
(λx
1
+ (1 − λ)y
1
) − 2(λx
2
+ (1 − λ)y
2
) ≥ 1
(3)
证毕.
2.判断下列函数为凸(凹)函数或严格凸(凹)函数:
(3)f(x) = x
2
1
− 2x
1
x
2
+ x
2
2
+ 2x
1
+ 3x
2
首先二阶导数连续可微,根据定理1.5,f在凸集上是
(I)凸函数的充分必要条件是∇
2
f(x)对一切x为半正定;
(II)严格凸函数的充分条件是∇
2
f(x)对一切x为正定。
∇
2
f(x) =
(
2 −2
−2 2
)
(4)
半正定矩阵
(4)
∇
2
f(x) =
4 1 −3
1 2 0
−3 0 4
(5)
正定矩阵
3.证明f(x) =
1
2
x
T
Gx + b
T
x为严格凸函数当且仅当Hesse矩阵G正定。
证明:根据严格凸函数定义证明。
对任意x = y,及任意实数λ ∈ (0, 1)都有f(λx+(1−λ)y) < λf (x)+(1−λ)f(y).
充分性:Hesse矩阵G正定=》严格凸函数.
f(λx + (1 − λ)y)=
1
2
(λx + (1 − λ)y)
T
G(λx + (1 − λ)y) + b
T
(λx + (1 − λ)y)
λf(x) + (1 − λ)f(y)=λ(
1
2
x
T
Gx + b
T
x)+(1 − λ)(
1
2
y
T
Gy + b
T
y)
λf(x) + (1 − λ)f(y) − f(λx + (1 − λ)y)=λ(
1
2
x
T
Gx)+(1 − λ)(
1
2
y
T
Gy) −
[
1
2
(λx)
T
G(λx) +
1
2
(1 − λ)y
T
G(1 − λ)y +
1
2
λx
T
G(1 − λ)y +
1
2
(1 − λ)y
T
Gλx]
=
1
2
λx
T
G(1 − λ)x +
1
2
(1 − λ)y
T
Gλy −
1
2
λx
T
G(1 − λ)y −
1
2
(1 − λ)y
T
Gλx
2
=
1
2
λx
T
G(1 − λ)(x − y) +
1
2
(1 − λ)y
T
Gλ(y −x)
=
1
2
λ(1 − λ)(x − y)
T
G(x − y) > 0 G正定保障了严格不等式成立。
反之,必要性:严格凸函数=》Hesse矩阵G正定.
类似,当对任意x = y,及任意实数λ ∈ (0, 1)都有f(λx + (1 − λ)y) < λf(x) +
(1 − λ)f(y).
λf(x) + (1 − λ)f(y) − f(λx + (1 − λ)y)=λ(
1
2
x
T
Gx)+(1 − λ)(
1
2
y
T
Gy) −
[
1
2
(λx)
T
G(λx) +
1
2
(1 − λ)y
T
G(1 − λ)y +
1
2
λx
T
G(1 − λ)y +
1
2
(1 − λ)y
T
Gλx]
=
1
2
λx
T
G(1 − λ)x +
1
2
(1 − λ)y
T
Gλy −
1
2
λx
T
G(1 − λ)y −
1
2
(1 − λ)y
T
Gλx
=
1
2
λx
T
G(1 − λ)(x − y) +
1
2
(1 − λ)y
T
Gλ(y −x)
=
1
2
λ(1 − λ)(x − y)
T
G(x − y) > 0
4.若对任意x ∈ ℜ
n
及实数θ > 0都有f(θx) = θf(x),证明f(x)在ℜ
n
上为凸函数
的充要条件是∀x, y ∈ ℜ
n
, f(x + y) ≤ f(x) + f(y)
证明:根据严格凸函数定义证明。
定义:对任意x = y,及任意实数λ ∈ (0, 1)都有f(λx + (1 − λ)y) ≤ λf (x) +
(1 − λ)f(y).
充分条件:∀x, y ∈ ℜ
n
, 有f (x + y) ≤ f (x) + f (y)
对任意x = y,及任意实数λ ∈ (0, 1)都有f(λx+(1−λ)y) ≤ f(λx)+f((1−λ)y)
利用f(θx) = θf ( x),
f(λx + (1 − λ)y) ≤ f(λx) + f((1 − λ)y)=λf(x) + (1 − λ)f(y).
充分性证毕;
必要性:f(x)在ℜ
n
上为凸函数=》∀x, y ∈ ℜ
n
, f(x + y) ≤ f(x) + f(y)
根据定义有对任意x = y,及任意实数λ ∈ (0, 1)都有f(λx + (1 − λ)y) ≤
λf(x) + (1 − λ)f(y).
不妨取λ =
1
2
,则
f(
1
2
x + (1 −
1
2
)y) ≤
1
2
f(x) + (1 −
1
2
)f(y).
利用f(θx) = θf ( x),
f(
1
2
(x + y)) =
1
2
f(x + y) ≤
1
2
(f(x) + f(y))
∀x, y ∈ ℜ
n
, f(x + y) ≤ f(x) + f(y)
证毕!
3
2 第第第二二二章章章线线线搜搜搜索索索算算算法法法-P27习习习题题题2、、、4、、、6
第2题:
黄金0.618算法:
function [s,phis,k,G,E]=golds(phi,a,b,delta,epsilon)
%输入:phi是目标函数,a,b是搜索区间的两个端点
% delta,epsilon分别是自变量和函数值的容许误差
%输出: s, phis 分别是近似极小点和极大值,G是n × 4矩阵,
% 其第k行分别是a,p,q,b的第k次迭代值ak, pk, qk, bk,
% E = [ds, dphi],分别是s和phis的误差限
%%%%%%%%%%
t=(sqrt(5)-1)/2; h=b-a;
phia=feval(phi,a); phib=feval(phi,b);
p=a+(1-t)*h; q=a+t*h; phip=feval(phi,p); phiq=feval(phi,q);
k=1; G(k,:)=[a, p, q, b];
while(abs(phib-phia)>epsilon)|(h>delta)
if(phip<phiq)
b=q; phib=phiq; q=p; phiq=phip;
h=b-a; p=a+(1-t)*h; phip=feval(phi,p);
else
a=p; phia=phip; p=q; phip=phiq;
h=b-a; q=a+t*h; phiq=feval(phi,q);
end
4
k=k+1; G(k,:)=[a, p, q, b];
end
ds=abs(b-a); dphi=abs(phib-phia);
if(phip<=phiq)
s=p; phis=phip;
else
s=q; phis=phiq;
end
E=[ds,dphi];
运行:[s, phis, k, G, E] = golds(inline(
′
s
3
− 2 ∗ s + 1
′
), 0, 3, 0.15, 0.01);
结果
ak,pk,qk,bk
0 1.1459 1.8541 3.0000
0 0.7082 1.1459 1.8541
0 0.4377 0.7082 1.1459
0.4377 0.7082 0.8754 1.1459
0.7082 0.8754 0.9787 1.1459
0.7082 0.8115 0.8754 0.9787
0.7082 0.7721 0.8115 0.8754
0.7721 0.8115 0.8359 0.8754
(6)
[s, phis, k, G, E] = golds( inline(
′
s
3
− 2 ∗ s + 1
′
), 0, 3, 0.15, 0.001);
≫ G
G =
5
剩余29页未读,继续阅读
资源评论
- yixiao_9992020-06-01这个答案包含的题不多,而且没必要下载,百度文库有
叫我黑霉君
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 高等数学第一章第二节数列的极限
- Python 版冒泡排序算法源代码
- tensorflow-gpu-2.7.2-cp38-cp38-manylinux2010-x86-64.whl
- tensorflow-2.7.3-cp39-cp39-manylinux2010-x86-64.whl
- tensorflow-2.7.2-cp39-cp39-manylinux2010-x86-64.whl
- Python版本快速排序源代码
- Python 语言版的快速排序算法实现
- 450815388207377安卓_base.apk
- 超微主板 X9DRE-TF+ bios 支持 nvme启动
- 基于Python通过下载气象数据和插值拟合离散数据曲线实现对寒潮过程的能量分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功