forked from 01tu01/Optimization-Method-Sun-Wenyu
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path线性搜索与信赖域方法.tex
242 lines (242 loc) · 16.2 KB
/
线性搜索与信赖域方法.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
\section{线性搜索与信赖域方法}
\begin{enumerate}
\item 推导0.618法的迭代公式.\\
\sol 由Fibonacci法迭代公式：
\[\lambda_k = a_k + \left(1 - \frac{F_{n-k}}{F_{n-k+1}}\right)(b_k - a_k), \quad \mu_k = a_k + \frac{F_{n-k}}{F_{n-k+1}} (b_k - a_k),\]
由式(3.2.20)可知：$\displaystyle \tau = \lim_{n \to \infty} \frac{F_{n-k}}{F_{n-k+1}} = \frac{\sqrt{5}-1}{2}$，取$\tau \approx 0.618$，则可得0.618法的迭代公式：
\[\lambda_k = a_k + 0.382(b_k - a_k), \quad \mu_k = a_k + 0.618(b_k - a_k).\]
\item 分别用0.618法，二次插值法，Goldstein不精确线性搜索方法求函数
\[f(x)=(\sin x)^6 \tan (1-x) \mathrm{e}^{30x}\]在区间$[0,1]$上的极大值.\\
\sol 由于这三种方法都是求解函数的极小值，故我们不妨设
\[g(x)=-(\sin x)^6 \tan (1-x) \mathrm{e}^{30x}.\]
0.618法：(取精度为0.0001)
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline
迭代次数$k$ & $[a_k,b_k]$ & $[\lambda_k,\mu_k]$ & $g(\lambda_k)$ & $g(\mu_k)$ \\ \hline
$0$ & $[0.00000,1.00000]$ & $[0.38200,0.61800]$ & $-180.93169$ & $-1712603.84319$\\ \hline
$1$ & $[0.38200,1.00000]$ & $[0.61800,0.76392]$ & $-1712603.84319$ & $-236591928.32087$\\ \hline
$2$ & $[0.61800,1.00000]$ & $[0.76392,0.85408]$ & $-236591928.32087$ & $-3621963454.74789$\\ \hline
$3$ & $[0.76392,1.00000]$ & $[0.85408,0.90982]$ & $-3621963454.74789$ & $-15629095526.75970$\\ \hline
$4$ & $[0.85408,1.00000]$ & $[0.90982,0.94426]$ & $-15629095526.75970$ & $-31645853714.38405$\\ \hline
$5$ & $[0.90982,1.00000]$ & $[0.94426,0.96555]$ & $-31645853714.38405$ & $-40525854255.03307$\\ \hline
$6$ & $[0.94426,1.00000]$ & $[0.96555,0.97871]$ & $-40525854255.03307$ & $-39217975674.21036$\\ \hline
$7$ & $[0.94426,0.97871]$ & $[0.95742,0.96555]$ & $-37941310649.54459$ & $-40525854255.03307$\\ \hline
$8$ & $[0.95742,0.97871]$ & $[0.96555,0.97057]$ & $-40525854255.03307$ & $-41085789962.33502$\\ \hline
$9$ & $[0.96555,0.97871]$ & $[0.97057,0.97368]$ & $-41085789962.33502$ & $-40851559012.30843$\\ \hline
$10$ & $[0.96555,0.97368]$ & $[0.96866,0.97057]$ & $-40993501131.26535$ & $-41085789962.33502$\\ \hline
$11$ & $[0.96866,0.97368]$ & $[0.97057,0.97176]$ & $-41085789962.33502$ & $-41056235078.63431$\\ \hline
$12$ & $[0.96866,0.97176]$ & $[0.96984,0.97057]$ & $-41070108314.89887$ & $-41085789962.33502$\\ \hline
$13$ & $[0.96984,0.97176]$ & $[0.97057,0.97103]$ & $-41085789962.33502$ & $-41082739735.01510$\\ \hline
$14$ & $[0.96984,0.97103]$ & $[0.97030,0.97057]$ & $-41082767355.81810$ & $-41085789962.33502$\\ \hline
$15$ & $[0.97030,0.97103]$ & $[0.97057,0.97075]$ & $-41085789962.33502$ & $-41085803940.89211$\\ \hline
$16$ & $[0.97057,0.97103]$ & $[0.97075,0.97085]$ & $-41085803940.89211$ & $-41085091885.42854$\\ \hline
$17$ & $[0.97057,0.97085]$ & $[0.97068,0.97075]$ & $-41085973087.67970$ & $-41085803940.89211$\\ \hline
\end{tabular}
\end{table}
故$f(x)$的极大点为0.97071，极大值为$-4.1086\times10^{10}$.\\
二次插值法：(取精度为0.0001，初始迭代点为0.1、0.5、1)
{\small
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$k$ & $a_1$ & $a_2$ & $a_3$ & $\bar a$ & $g_1$ & $g_2$ & $g_3$ & $\bar g$ \\ \hline
$0$ & $0.10000$ & $0.50000$ & $1$ & $0.55000$ & $-0.00003$ & $-21685.89733$ & $0$ & $-144313.48798$ \\ \hline
$1$ & $0.50000$ & $0.55000$ & $1$ & $0.74609$ & $-21685.89733$ & $-144313.48798$ & $0$ & $-133409650.84449$ \\ \hline
$2$ & $0.55000$ & $0.74609$ & $1$ & $0.77494$ & $-144313.48798$ & $-133409650.84449$ & $0$ & $-335472520.81192$ \\ \hline
$3$ & $0.74609$ & $0.77494$ & $1$ & $0.86519$ & $-133409650.84449$ & $-335472520.81192$ & $0$ & $-4941583365.98999$ \\ \hline
$4$ & $0.77494$ & $0.86519$ & $1$ & $0.88556$ & $-335472520.81192$ & $-4941583365.98999$ & $0$ & $-8543117362.08340$ \\ \hline
$5$ & $0.86519$ & $0.88556$ & $1$ & $0.92277$ & $-4941583365.98999$ & $-8543117362.08340$ & $0$ & $-20938281955.02223$ \\ \hline
$6$ & $0.88556$ & $0.92277$ & $1$ & $0.93571$ & $-8543117362.08340$ & $-20938281955.02223$ & $0$ & $-27213528026.34990$ \\ \hline
$7$ & $0.92277$ & $0.93571$ & $1$ & $0.94986$ & $-20938281955.02223$ & $-27213528026.34990$ & $0$ & $-34493283849.16349$ \\ \hline
$8$ & $0.93571$ & $0.94986$ & $1$ & $0.95654$ & $-27213528026.34990$ & $-34493283849.16349$ & $0$ & $-37577724676.75349$ \\ \hline
$9$ & $0.94986$ & $0.95654$ & $1$ & $0.96193$ & $-34493283849.16349$ & $-37577724676.75349$ & $0$ & $-39577028005.21829$ \\ \hline
$10$ & $0.95654$ & $0.96193$ & $1$ & $0.96495$ & $-37577724676.75349$ & $-39577028005.21829$ & $0$ & $-40395052418.74240$ \\ \hline
$11$ & $0.96193$ & $0.96495$ & $1$ & $0.96706$ & $-39577028005.21829$ & $-40395052418.74240$ & $0$ & $-40798680632.87956$ \\ \hline
$12$ & $0.96495$ & $0.96706$ & $1$ & $0.96834$ & $-40395052418.74240$ & $-40798680632.87956$ & $0$ & $-40963298550.04148$ \\ \hline
$13$ & $0.96706$ & $0.96834$ & $1$ & $0.96919$ & $-40798680632.87956$ & $-40963298550.04148$ & $0$ & $-41035621691.04285$ \\ \hline
$14$ & $0.96834$ & $0.96919$ & $1$ & $0.96972$ & $-40963298550.04148$ & $-41035621691.04285$ & $0$ & $-41065099592.32568$ \\ \hline
$15$ & $0.96919$ & $0.96972$ & $1$ & $0.97006$ & $-41035621691.04285$ & $-41065099592.32568$ & $0$ & $-41077456061.09961$ \\ \hline
$16$ & $0.96972$ & $0.97006$ & $1$ & $0.97028$ & $-41065099592.32568$ & $-41077456061.09961$ & $0$ & $-41082487976.77145$ \\ \hline
$17$ & $0.97006$ & $0.97028$ & $1$ & $0.97042$ & $-41077456061.09961$ & $-41082487976.77145$ & $0$ & $-41084558359.15994$ \\ \hline
$18$ & $0.97028$ & $0.97042$ & $1$ & $0.97051$ & $-41082487976.77145$ & $-41084558359.15994$ & $0$ & $-41085400853.61729$ \\ \hline
\end{tabular}
\end{table}}
故$f(x)$的极大点为0.97051，极大值为$-4.1085\times10^{10}$.\\
Goldstein不精确线性搜索方法略.
\item 写出Fibonacci法的计算过程和C程序(或MATLAB,FORTRAN程序).\\
\sol Fibonacci法的计算过程：
\begin{enumerate}[label=步\arabic*:,left=0em]
\item 给定初始搜索区间$[a_1,b_1]$和精度要求$\delta > 0$，计算满足$\displaystyle F_n \geqslant \frac{b_1-a_1}{\delta}$的最小的$n$；
\item $\displaystyle \lambda_1 := a_1 + \frac{F_{n-2}}{F_n}(b_1-a_1)$，$\displaystyle \mu_1 := a_1 + \frac{F_{n-1}}{F_n}(b_1-a_1)$\\
计算$\varphi(\lambda_1),\varphi(\mu_1)$，置$k:=1$；
\item 若$k = n - 1$，则转步4，否则转步5；
\item 停止计算，输出$\lambda_k$(或$\mu_k$，因为$\lambda_k = \mu_k$此时恰好成立). 也可再计算一个函数值$\displaystyle \varphi \left(\frac{a_k+b_k}{2}\pm\varepsilon\right)$，比较后输出$\lambda_k$或$\displaystyle \frac{a_k+b_k}{2}\pm\varepsilon$；
\item 若$\varphi(\lambda_k) > \varphi(\mu_k)$，转步6，否则转步7；
\item 令$\displaystyle a_{k+1} := \lambda_k, b_{k+1} := b_k, \lambda_{k+1} := \mu_k, \varphi(\lambda_{k+1}) := \varphi(\mu_k), \mu_{k+1} := a_{k+1} + \frac{F_{n-k-1}}{F_{n-k}}(b_{k+1}-a_{k+1})$，计算$\varphi(\mu_{k+1})$，令$k := k+1$，转步3；
\item 令$\displaystyle a_{k+1} := a_k, b_{k+1} := \mu_k, \mu_{k+1} := \lambda_k, \varphi(\mu_{k+1}) := \varphi(\lambda_k), \lambda_{k+1} := a_{k+1} + \frac{F_{n-k-2}}{F_{n-k}}(b_{k+1}-a_{k+1})$，计算$\varphi(\lambda_{k+1})$，令$k := k+1$，转步3.
\end{enumerate}
注：在步6、步7中，当$k = n - 2$，无需计算$\varphi(\mu_{k+1})$，$\varphi(\lambda_{k+1})$. 因为此时$\mu_{k+1} = \lambda_{k+1}$，但由于舍入误差，它们未必精确相等.\\
Matlab程序为：
\begin{lstlisting}
function [xmin, fval, k] = Fibonacci(f, a, b, delta)
% f是所求函数表达式，a是区间左端点
% b是区间右端点，delta是精度
% xmin是极小点，fval是极小值，k是迭代步数
format long
Fn = (b - a) / delta; F = []; F(1) = 1; F(2) = 1; i = 1;
while F(i) < Fn
F(i + 2) = F(i) + F(i + 1); i = i + 1;
end
n = i;
lambda = a + F(n - 2) / F(n) * (b - a); mu = a + F(n - 1) / F(n) * (b - a);
x = symvar(f);
phi_lambda = subs(f, x, lambda); phi_mu = subs(f, x, mu);
k = 0;
fprintf('k \t [a_k, b_k] \t [lambda_k, mu_k] \t phi(lambda_k) \t phi(mu_k)\n');
fprintf('%d \t [%.5f,%.5f] \t [%.5f,%.5f] \t %.5f \t %.5f\n', k, a, b, lambda, mu, phi_lambda, phi_mu);
k = 1;
while true
if k == n - 1
xmin = vpa(lambda, 5); fval = vpa(subs(f, x, lambda), 5);
break;
else
if phi_lambda > phi_mu
a = lambda; b = b; lambda = mu; phi_lambda = phi_mu;
if k == n - 2
xmin = vpa(lambda, 5);
fval = vpa(subs(f, x, lambda), 5);
break;
else
mu = a + F(n - k - 1) / F(n - k) * (b - a);
phi_mu = subs(f, x, mu); k = k + 1;
fprintf('%d \t [%.5f,%.5f] \t [%.5f,%.5f] \t %.5f \t %.5f\n', k, a, b, lambda, mu, phi_lambda, phi_mu);
end
else
a = a; b = mu; mu = lambda; phi_mu = phi_lambda;
if k == n - 2
xmin = vpa(lambda, 5);
fval = vpa(subs(f, x, lambda), 5);
break;
else
lambda = a + F(n - k - 2) / F(n - k) * (b - a);
phi_lambda = subs(f, x, lambda); k = k + 1;
fprintf('%d \t [%.5f,%.5f] \t [%.5f,%.5f] \t %.5f \t %.5f\n', k, a, b, lambda, mu, phi_lambda, phi_mu);
end
end
end
end
end
\end{lstlisting}
\item 设$\varphi(t)=\mathrm{e}^{-t}+\mathrm{e}^t$，区间为$[-1,1]$.
\begin{enumerate}[label=(\arabic*)]
\item 用0.618法极小化$\varphi(t)$.
\item 用Fibonacci法极小化$\varphi(t)$.
\end{enumerate}
\sol \begin{enumerate}[label=(\arabic*)]
\item 取精度为0.01：
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline
迭代次数$k$ & $[a_k,b_k]$ & $[\lambda_k,\mu_k]$ & $\varphi(\lambda_k)$ & $\varphi(\mu_k)$ \\ \hline
$0$ & $[-1.00000,1.00000]$ & $[-0.23600,0.23600]$ & $2.05595$ & $2.05595$\\ \hline
$1$ & $[-1.00000,0.23600]$ & $[-0.52785,-0.23600]$ & $2.28515$ & $2.05595$\\ \hline
$2$ & $[-0.52785,0.23600]$ & $[-0.23600,-0.05579]$ & $2.05595$ & $2.00311$\\ \hline
$3$ & $[-0.23600,0.23600]$ & $[-0.05579,0.05570]$ & $2.00311$ & $2.00310$\\ \hline
$4$ & $[-0.05579,0.23600]$ & $[0.05570,0.12454]$ & $2.00310$ & $2.01553$\\ \hline
$5$ & $[-0.05579,0.12454]$ & $[0.01309,0.05570]$ & $2.00017$ & $2.00310$\\ \hline
$6$ & $[-0.05579,0.05570]$ & $[-0.01320,0.01309]$ & $2.00017$ & $2.00017$\\ \hline
$7$ & $[-0.01320,0.05570]$ & $[0.01309,0.02938]$ & $2.00017$ & $2.00086$\\ \hline
$8$ & $[-0.01320,0.02938]$ & $[0.00306,0.01309]$ & $2.00001$ & $2.00017$\\ \hline
$9$ & $[-0.01320,0.01309]$ & $[-0.00316,0.00306]$ & $2.00001$ & $2.00001$\\ \hline
\end{tabular}
\end{table}
故$\varphi(x)$的极小点为$-0.000046968$，极小值为2.
\item 取精度为0.01：
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline
迭代次数$k$ & $[a_k,b_k]$ & $[\lambda_k,\mu_k]$ & $\varphi(\lambda_k)$ & $\varphi(\mu_k)$ \\ \hline
$0$ & $[-1.00000,1.00000]$ & $[-0.23605,0.23605]$ & $2.05598$ & $2.05598$\\ \hline
$2$ & $[-1.00000,0.23605]$ & $[-0.52790,-0.23605]$ & $2.28521$ & $2.05598$\\ \hline
$3$ & $[-0.52790,0.23605]$ & $[-0.23605,-0.05579]$ & $2.05598$ & $2.00311$\\ \hline
$4$ & $[-0.23605,0.23605]$ & $[-0.05579,0.05579]$ & $2.00311$ & $2.00311$\\ \hline
$5$ & $[-0.23605,0.05579]$ & $[-0.12446,-0.05579]$ & $2.01551$ & $2.00311$\\ \hline
$6$ & $[-0.12446,0.05579]$ & $[-0.05579,-0.01288]$ & $2.00311$ & $2.00017$\\ \hline
$7$ & $[-0.05579,0.05579]$ & $[-0.01288,0.01288]$ & $2.00017$ & $2.00017$\\ \hline
$8$ & $[-0.05579,0.01288]$ & $[-0.03004,-0.01288]$ & $2.00090$ & $2.00017$\\ \hline
$9$ & $[-0.03004,0.01288]$ & $[-0.01288,-0.00429]$ & $2.00017$ & $2.00002$\\ \hline
$10$ & $[-0.01288,0.01288]$ & $[-0.00429,0.00429]$ & $2.00002$ & $2.00002$\\ \hline
$11$ & $[-0.01288,0.00429]$ & $[-0.00429,-0.00429]$ & $2.00002$ & $2.00002$\\ \hline
\end{tabular}
\end{table}
故$\varphi(x)$的极小点为$-0.0042918$，极小值为2.
\end{enumerate}
\item 用二分法解
\[\begin{array}{lll}
\min & x^2 + 2x\\
\mathrm{s.t.} & -3 \leqslant x \leqslant 6.
\end{array}\]
取最后区间长度为$\delta=0.2$. (解$x^*=-0.961$).\\
\sol \begin{table}[H]
\centering
\begin{tabular}{|c|c|}
\hline
$k$ & $[a_k, b_k]$ \\ \hline
$1$ & $[-3.00000,6.00000]$ \\ \hline
$2$ & $[-3.00000,1.50000]$ \\ \hline
$3$ & $[-3.00000,-0.75000]$ \\ \hline
$4$ & $[-1.87500,-0.75000]$ \\ \hline
$5$ & $[-1.31250,-0.75000]$ \\ \hline
$6$ & $[-1.03125,-0.75000]$ \\ \hline
$7$ & $[-1.03125,-0.89063]$ \\ \hline
\end{tabular}
\end{table}
故$x^2 + 2x$在$[-3,6]$上的极小点为$-0.96094$，极小值为$-0.99847$.
\item 设$\varphi(t)=1-t\mathrm{e}^{-t^2}$，区间为$[0,1]$. 试用三点二次插值法极小化$\varphi(t)$.\\
\sol 取精度为0.0001，初始迭代点为0、0.5、1
{\small
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$k$ & $a_1$ & $a_2$ & $a_3$ & $\bar a$ & $\varphi_1$ & $\varphi_2$ & $\varphi_3$ & $\bar \varphi$ \\ \hline
$0$ & $0.00000$ & $0.50000$ & $1.00000$ & $0.72381$ & $1.00000$ & $0.61060$ & $0.63212$ & $0.57136$ \\ \hline
$1$ & $0.50000$ & $0.72381$ & $1.00000$ & $0.72278$ & $0.61060$ & $0.57136$ & $0.63212$ & $0.57133$ \\ \hline
$2$ & $0.50000$ & $0.72278$ & $0.72381$ & $0.70822$ & $0.61060$ & $0.57133$ & $0.57136$ & $0.57112$ \\ \hline
$3$ & $0.50000$ & $0.70822$ & $0.72278$ & $0.70769$ & $0.61060$ & $0.57112$ & $0.57133$ & $0.57112$ \\ \hline
$4$ & $0.50000$ & $0.70769$ & $0.70822$ & $0.70716$ & $0.61060$ & $0.57112$ & $0.57112$ & $0.57112$ \\ \hline
$5$ & $0.50000$ & $0.70716$ & $0.70769$ & $0.70713$ & $0.61060$ & $0.57112$ & $0.57112$ & $0.57112$ \\ \hline
\end{tabular}
\end{table}}
故$\varphi(t)$的极小点为0.70713，极小值为0.57112.
\item 设$\varphi(t)=-2t^3+21t^2-60t+50$.
\begin{enumerate}[label=(\arabic*)]
\item 用Goldstein方法极小化$\varphi(t),t_0=0.5,\rho=0.1$.
\item 用Wolfe方法极小化$\varphi(t),t_0=0.5,\rho=0.1,\sigma=0.8$.
\end{enumerate}
\omitted
\item 设$f(x)=x_1^4+x_2^2+x_2^2$，给定当前点$x_k=(1,1)^\mathrm{T}$，方向$d_k=(-3,-1)^\mathrm{T}$，并设$\rho=1,t=0.5$.
\begin{enumerate}[label=(\arabic*)]
\item 试分别用Goldstein方法和Wolfe方法求新点$x_{k+1}$.
\item 分别以$\alpha=1,\alpha=0.5,\alpha=0.1$说明哪些$\alpha$满足Wolfe准则，哪些$\alpha$不满足Wolfe准则.
\end{enumerate}
\omitted
\item 设$\displaystyle f(x)=\frac{1}{2}x_1^2+x_2^2$. 设初始点$x_0=(1,1)^\mathrm{T}$. 对于(1)$\Delta_0=1$, (2)$\displaystyle\Delta_0=\frac{5}{4}$,
\begin{enumerate}[label=(\roman*)]
\item 用折线法计算下一个迭代点$x_1$;
\item 用双折线法计算下一个迭代点$x_1$.
\end{enumerate}
\omitted
\item 证明：
\begin{enumerate}[label=(\arabic*)]
\item Cauchy点满足(3.8.4).
\item 子问题(3.7.2)的精确极小点满足(3.8.4).
\end{enumerate}
\omitted
\end{enumerate}
\clearpage