联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

Analytical methods have considerable intrinsic interest, but their importance for applications is the driving motive behind this course. The main analytical tools developed in this course can be thought of as generalisations of the Fourier and power series representations of functions studied in MATH2120. This leads to new types of functions and to practical methods for solving differential equations. We will pay special attention to functions defined on infinite domains.

这是一份unsw新南威尔士大学MATH3161 的成功案例

优化|MATH3161 Optimization

问题 1.

Under the conditions of the previous theorem, the backtracking Armijo line search terminates withαk≥min(αinit?2τ(β?1)pkT?f(xk)L(xk)|pk|22) alpha_{k} geq min left( alpha_{ text {init }} frac{2 tau( beta-1) boldsymbol{p}{k}^{T} nabla f left( boldsymbol{x}{k} right)}{L left( boldsymbol{x}{k} right) left| boldsymbol{p}{k} right|_{2}^{2}} right)

证明 .

Proof. Either αinit? alpha_{ text {init }} already satisfies the Armijo condition, or there is a second to last step in the Armijo backtracking algorithm which does not yet satisfy the Armijo condition, and hence the next step will multiply this second to last one by τ tau, which then satisfies the Armijo condition, and the algorithm stops with αk alpha_{k} satisfying (4.28).

In general, it would be very difficult to get an est imate of the local Lipschitz constant L(xk)L left( boldsymbol{x}_{k} right), and the backtracking Armijo search is precisely a tool to find a suitable line search parameter without knowing this quantity.

问题 2.

Assume a graph of order nn with vertex-probabilities verifying pmin?p_{ min } geqslant t. If minimum coloring is polynomially approximable within approximation ratio ρ rho, then PROBABILISTIC MIN COLORING is approximable in polynomial time within ratio ρ/t rho / t

证明 .

Proof. denoting by C=(S1,…,Sk)C^{}= left(S_{1}^{}, ldots, S_{k^{}}^{} right) an optimal a priori solution for PROBABILISTIC MIN COLORING, we get:E(G,C)?kpmin?kt E left(G, C^{} right) geqslant k^{} p_{ min } geqslant k^{} t Consider a ρ rho-approximation algorithm A computing a feasible coloring ?C hat{C} for GG (by not taking probabilities into account), and set ?C=(?S1,…,?S?k) hat{C}= left( hat{S}{1}, ldots, hat{S}{ hat{k}} right). Then, the functional E(G,?C)E(G, hat{C}) for ?C hat{C}, in other words, the objective value of ?C hat{C} for PROBABILISTIC MIN COLORING, is, by [5.4]:E(G,?C)=?k∑j=1(1?∏vi∈?Sj(1?pi))??k E(G, hat{C})= sum_{j=1}^{ hat{k}} left(1- prod_{v_{i} in hat{S}{j}} left(1-p{i} right) right) leqslant hat{k} By hypothesis, ?k/χ(G)?ρ hat{k} / chi(G) leqslant rho (where χ(G) chi(G) denotes the chromatic number of the graph GG, see Appendix A.2); furthermore, CC^{} being a feasible coloring, k?χ(G)k^{} geqslant chi(G). Therefore, ?k/k?ρ hat{k} / k^{} leqslant rho and the approximation ratio of A for PROBABILISTIC MIN COLORING is, taking [5.10] into account, E(G,?C)/E(G,C?)?ρ/tE(G, hat{C}) / E left(G, C^{*} right) leqslant rho / t.

分析方法有相当大的内在兴趣，但其对应用的重要性是本课程的驱动力。本课程开发的主要分析工具可以被认为是MATH2120中研究的函数的傅里叶和幂级数表示法的一般化。这导致了新类型的函数和解决微分方程的实用方法。我们将特别注意定义在无限域上的函数。