如果你也在 怎样代写凸优化Convex optimization 这个学科遇到相关的难题，请随时右上角联系我们的24/7代写客服。凸优化Convex optimization由于在大规模资源分配、信号处理和机器学习等领域的广泛应用，人们对凸优化的兴趣越来越浓厚。本书旨在解决凸优化问题的算法的最新和可访问的发展。
凸优化Convex optimization无约束可以很容易地用梯度下降(最陡下降的特殊情况)或牛顿方法解决，结合线搜索适当的步长;这些可以在数学上证明收敛速度很快，尤其是后一种方法。如果目标函数是二次函数，也可以使用KKT矩阵技术求解具有线性等式约束的凸优化(它推广到牛顿方法的一种变化，即使初始化点不满足约束也有效)，但通常也可以通过线性代数消除等式约束或解决对偶问题来解决。
statistics-lab™ 为您的留学生涯保驾护航 在代写凸优化Convex Optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写凸优化Convex Optimization代写方面经验极为丰富，各种代写凸优化Convex Optimization相关的作业也就用不着说。
数学代写|凸优化作业代写Convex Optimization代考|Subgradient Methods with Iterate Averaging
If the stepsize $\alpha_k$ in the subgradient method
$$
x_{k+1}=P_X\left(x_k-\alpha_k g_k\right)
$$
is chosen to be large (such as constant or such that the condition $\sum_{k=0}^{\infty} \alpha_k^2<\infty$ is violated) the method may not converge. This exercise shows that by averaging the iterates of the method, we may obtain convergence with larger stepsizes. Let the optimal solution set $X^$ be nonempty, and assume that for some scalar $c$, we have $$ c \geq \sup \left{\left|g_k\right| \mid k=0,1, \ldots\right}, \quad \forall k \geq 0, $$ (cf. Assumption 3.2.1). Assume further that $\alpha_k$ is chosen according to $$ \alpha_k=\frac{\theta}{c \sqrt{k+1}}, \quad k=0,1, \ldots $$ where $\theta$ is a positive constant. Show that $$ f\left(\bar{x}k\right)-f^ \leq c\left(\frac{\min {x^* \in X^}\left|x_0-x^\right|^2}{2 \theta}+\theta \ln (k+2)\right) \frac{1}{\sqrt{k+1}}, \quad k=0,1, \ldots,
$$
where $\bar{x}k$ is the averaged iterate, generated according to $$ \bar{x}_k=\frac{\sum{\ell=0}^k \alpha_{\ell} x_{\ell}}{\sum_{\ell=0}^k \alpha_{\ell}}
$$
similar analysis applies to incremental and to stochastic subgradient methods.
Abbreviated proof: Denote
$$
\delta_k=\frac{1}{2} \min {x^* \in X^}\left|x_k-x^\right|^2 .
$$
Applying Prop. 3.2.2(a) with $y$ equal to the projection of $x_k$ onto $X^$, we obtain $$ \delta{k+1} \leq \delta_k-\alpha_k\left(f\left(x_k\right)-f^\right)+\frac{1}{2} \alpha_k^2 c^2
$$
Adding this inequality from 0 to $k$, and using the fact $\delta_{k+1} \geq 0$,
$$
\sum_{\ell=0}^k \alpha_{\ell}\left(f\left(x_k\right)-f^\right) \leq \delta_0+\frac{1}{2} c^2 \sum_{\ell=0}^k \alpha_{\ell}^2, $$ so by dividing with $\sum_{\ell=0}^k \alpha_{\ell}$, $$ \frac{\sum_{\ell=0}^k \alpha_{\ell} f\left(x_k\right)}{\sum_{\ell=0}^k \alpha_{\ell}}-f^ \leq \frac{\delta_0+\frac{1}{2} c^2 \sum_{\ell=0}^k \alpha_{\ell}^2}{\sum_{\ell=0}^k \alpha_{\ell}}
$$
数学代写|凸优化作业代写Convex Optimization代考|Modified Dynamic Stepsize Rules
Consider the subgradient method
$$
x_{k+1}=P_X\left(x_k-\alpha_k g_k\right)
$$
with the stepsize chosen according to one of the two rules
$$
\alpha_k=\frac{f\left(x_k\right)-f_k}{\max \left{\gamma,\left|g_k\right|^2\right}} \quad \text { or } \quad \alpha_k=\min \left{\gamma, \frac{f\left(x_k\right)-f_k}{\left|g_k\right|^2}\right}
$$
where $\gamma$ is a fixed positive scalar and $f_k$ is given by the dynamic adjustment procedure (3.22)-(3.23). Show that the convergence result of Prop. 3.2.8 still holds. Abbreviated Proof: We proceed by contradiction, as in the proof of Prop. 3.2.8. From Prop. 3.2.2(a) with $y=\bar{y}$, we have for all $k \geq \bar{k}$,
$$
\begin{aligned}
\left|x_{k+1}-\bar{y}\right|^2 & \leq\left|x_k-\bar{y}\right|^2-2 \alpha_k\left(f\left(x_k\right)-f(\bar{y})\right)+\alpha_k^2\left|g_k\right|^2 \
& \leq\left|x_k-\bar{y}\right|^2-2 \alpha_k\left(f\left(x_k\right)-f(\bar{y})\right)+\alpha_k\left(f\left(x_k\right)-f_k\right) \
& =\left|x_k-\bar{y}\right|^2-\alpha_k\left(f\left(x_k\right)-f_k\right)-2 \alpha_k\left(f_k-f(\bar{y})\right) \
& \leq\left|x_k-\bar{y}\right|^2-\alpha_k\left(f\left(x_k\right)-f_k\right) .
\end{aligned}
$$
Hence $\left{x_k\right}$ is bounded, which implies that $\left{g_k\right}$ is also bounded (cf. Prop. 3.1.2). Let $\bar{c}$ be such that $\left|g_k\right| \leq \bar{c}$ for all $k$. Assume that $\alpha_k$ is chosen according to the first rule in Eq. (3.47). Then from the preceding relation we have for all $k \geq \bar{k}$,
$$
\left|x_{k+1}-\bar{y}\right|^2 \leq\left|x_k-\bar{y}\right|^2-\frac{\delta^2}{\max \left{\gamma, \bar{c}^2\right}} .
$$
As in the proof of Prop. 3.2.8, this leads to a contradiction and the result follows. The proof is similar if $\alpha_k$ is chosen according to the second rule in Eq. (3.47).
凸优化代写
数学代写|凸优化作业代写Convex Optimization代考|Subgradient Methods with Iterate Averaging
如果步长为$\alpha_k$在子梯度法中
$$
x_{k+1}=P_X\left(x_k-\alpha_k g_k\right)
$$
选择较大(如常数或违反$\sum_{k=0}^{\infty} \alpha_k^2<\infty$条件)的方法可能不收敛。这个练习表明，通过平均方法的迭代，我们可以在较大的步长下获得收敛性。令最优解集$X^$非空，并假设对于某个标量$c$，我们有$$ c \geq \sup \left{\left|g_k\right| \mid k=0,1, \ldots\right}, \quad \forall k \geq 0, $$(参见假设3.2.1)。进一步假设$\alpha_k$是根据$$ \alpha_k=\frac{\theta}{c \sqrt{k+1}}, \quad k=0,1, \ldots $$选择的，其中$\theta$是一个正常数。展示一下$$ f\left(\bar{x}k\right)-f^ \leq c\left(\frac{\min {x^* \in X^}\left|x_0-x^\right|^2}{2 \theta}+\theta \ln (k+2)\right) \frac{1}{\sqrt{k+1}}, \quad k=0,1, \ldots,
$$
其中$\bar{x}k$是根据生成的平均迭代 $$ \bar{x}k=\frac{\sum{\ell=0}^k \alpha{\ell} x_{\ell}}{\sum_{\ell=0}^k \alpha_{\ell}}
$$
类似的分析也适用于增量法和随机次梯度法。
缩写证明:
$$
\delta_k=\frac{1}{2} \min {x^* \in X^}\left|x_k-x^\right|^2 .
$$
应用Prop. 3.2.2(a)，令$y$等于$x_k$在$X^$上的投影，我们得到$$ \delta{k+1} \leq \delta_k-\alpha_k\left(f\left(x_k\right)-f^\right)+\frac{1}{2} \alpha_k^2 c^2
$$
把不等式从0加到$k$，利用$\delta_{k+1} \geq 0$这个事实，
$$
\sum_{\ell=0}^k \alpha_{\ell}\left(f\left(x_k\right)-f^\right) \leq \delta_0+\frac{1}{2} c^2 \sum_{\ell=0}^k \alpha_{\ell}^2, $$除以$\sum_{\ell=0}^k \alpha_{\ell}$， $$ \frac{\sum_{\ell=0}^k \alpha_{\ell} f\left(x_k\right)}{\sum_{\ell=0}^k \alpha_{\ell}}-f^ \leq \frac{\delta_0+\frac{1}{2} c^2 \sum_{\ell=0}^k \alpha_{\ell}^2}{\sum_{\ell=0}^k \alpha_{\ell}}
$$
数学代写|凸优化作业代写Convex Optimization代考|Modified Dynamic Stepsize Rules
考虑次梯度法
$$
x_{k+1}=P_X\left(x_k-\alpha_k g_k\right)
$$
步长根据两个规则之一选择
$$
\alpha_k=\frac{f\left(x_k\right)-f_k}{\max \left{\gamma,\left|g_k\right|^2\right}} \quad \text { or } \quad \alpha_k=\min \left{\gamma, \frac{f\left(x_k\right)-f_k}{\left|g_k\right|^2}\right}
$$
其中$\gamma$为固定正标量，$f_k$由式(3.22)-(3.23)的动态调整过程给出。证明Prop. 3.2.8的收敛性结果仍然成立。简证:我们以反证法进行，如提案3.2.8的证明。根据提案3.2.2(a)中$y=\bar{y}$，我们得到所有$k \geq \bar{k}$，
$$
\begin{aligned}
\left|x_{k+1}-\bar{y}\right|^2 & \leq\left|x_k-\bar{y}\right|^2-2 \alpha_k\left(f\left(x_k\right)-f(\bar{y})\right)+\alpha_k^2\left|g_k\right|^2 \
& \leq\left|x_k-\bar{y}\right|^2-2 \alpha_k\left(f\left(x_k\right)-f(\bar{y})\right)+\alpha_k\left(f\left(x_k\right)-f_k\right) \
& =\left|x_k-\bar{y}\right|^2-\alpha_k\left(f\left(x_k\right)-f_k\right)-2 \alpha_k\left(f_k-f(\bar{y})\right) \
& \leq\left|x_k-\bar{y}\right|^2-\alpha_k\left(f\left(x_k\right)-f_k\right) .
\end{aligned}
$$
因此$\left{x_k\right}$是有界的，这就意味着$\left{g_k\right}$也是有界的(参见Prop 3.1.2)。让$\bar{c}$为所有$k$成为$\left|g_k\right| \leq \bar{c}$。假设根据式(3.47)中的第一条规则选择$\alpha_k$。从前面的关系式中我们得到所有$k \geq \bar{k}$，
$$
\left|x_{k+1}-\bar{y}\right|^2 \leq\left|x_k-\bar{y}\right|^2-\frac{\delta^2}{\max \left{\gamma, \bar{c}^2\right}} .
$$
正如Prop. 3.2.8的证明一样，这就引出了一个矛盾，结果就出来了。如果根据式(3.47)中的第二条规则选择$\alpha_k$，则证明是类似的。
统计代写请认准statistics-lab™. statistics-lab™为您的留学生涯保驾护航。