数学代写|Optimization problems 数值分析代考
数值分析代写
4.1 Optimization problems
4.1.1 Basic terminology
We use the notation
$$
\begin{array}{ll}
\text { minimize } & f_{0}(x) \
\text { subject to } & f_{1}(x) \leq 0, \quad i=1, \ldots, m \
& h_{1}(x)=0, \quad i=1, \ldots, p
\end{array}
$$
to describe the problem of finding an $x$ that minimizes $f_{0}(x)$ among all $x$ that satisfy the conditions $f_{1}(x) \leq 0, i=1, \ldots, m$, and $h_{i}(x)=0, i=1, \ldots, p$. We call $x \in \mathbf{R}^{n}$ the optimization variable and the function $f_{0}: \mathbf{R}^{n} \rightarrow \mathbf{R}$ the objective function or cost function. The inequalities $f_{i}(x) \leq 0$ are called inequality constraints, and the corresponding functions $f_{1}: \mathbf{R}^{n} \rightarrow \mathbf{R}$ are called the inequality constraint functions. The equations $h_{1}(x)=0$ are called the equality constraints, and the functions $h_{1}: \mathbf{R}^{n} \rightarrow \mathbf{R}$ are the equality constraint functions. If there are no constraints (i.e., $m=p=0$ ) we say the problem (4.1) is unconstrained.
The set of points for which the objective and all constraint functions are defined,
$$
\mathcal{D}=\bigcap_{i=0}^{m} \operatorname{dom} f_{i} \cap \bigcap_{i=1}^{p} \operatorname{dom} h_{i}
$$
is called the domain of the optimization problem (4.1). A point $x \in \mathcal{D}$ is feasible if it satisfies the constraints $f_{t}(x) \leq 0, i=1, \ldots, m$, and $h_{i}(x)=0, i=1, \ldots, p$. The problem (4.1) is said to be feasible if there exists at least one feasible point, and infeasible otherwise. The set of all feasible points is called the feasible set or the constraint set.
The optimal value $p^{\star}$ of the problem (4.1) is defined as
$$
p^{\star}=\inf \left{f_{0}(x) \mid f_{1}(x) \leq 0, i=1, \ldots, m, h_{1}(x)=0, i=1, \ldots, p\right} .
$$
We allow $p^{\star}$ to take on the extended values $\pm \infty$. If the problem is infersible, we have $p^{\star}=\infty$ (following the standard convention that the infinum of the empty set
is $\infty$ ). If there are feasible points $x_{k}$ with $f_{0}\left(x_{k}\right) \rightarrow-\infty$ as $k \rightarrow \infty$, then $p^{\star}=-\infty$, and we say the problem (4.1) is anbounded below.
Optimal and locally optimal points
We say $x^{\star}$ is an optimal point, or solves the problem (4.1), if $x^{\star}$ is feasible and $f_{0}\left(x^{\star}\right)=p^{*}$. The set of all optimal points is the optimal set, denoted
$$
X_{\mathrm{opt}}=\left{x \mid f_{\mathrm{i}}(x) \leq 0, i=1, \ldots, m, h_{\mathrm{i}}(x)=0, i=1, \ldots, p, f_{0}(x)=p^{\star}\right} .
$$
If there exists an optimal point for the problem (4.1), we say the optimal value is attained or achieved, and the problem is solvable. If $X_{\text {apt }}$ is empty, we say the optimal value is not attained or not achieved. (This always occurs when the problem is unbounded below.) A feasible point $x$ with $f_{0}(x) \leq p^{\star}+E$ (where $\epsilon>0)$ is called $\epsilon$-suboptimal, and the set of all $\epsilon$-suboptimal points is called the e-suboptimal set for the problem (4.1).
We say a feasible point $x$ is locully optimal if there is an $R>0$ such that
$$
\begin{aligned}
f_{0}(x)=& \inf \left{f_{0}(z) \mid f_{1}(z) \leq 0, i=1, \ldots, m\right.\
&\left.h_{1}(z)=0, i=1, \ldots, p,|z-x|_{2} \leq R\right}
\end{aligned}
$$
or, in other words, $x$ solves the optimization problem
$$
\begin{array}{ll}
\text { minimize } & f_{0}(z) \
\text { subject to } & f_{1}(z) \leq 0, \quad i=1, \ldots, m \
& h_{1}(z)=0, \quad i=1, \ldots, p \
& |z-x|_{2} \leq R
\end{array}
$$
with variable $z$. Roughly speaking, this means $x$ minimizes $f_{0}$ over nearby points in the feasible set. ‘The term ‘globally optimal’ is sometimes used for ‘optimal’ to distinguish between ‘locally optimal’ and ‘optimal’. Throughout this book, however, optimal will mean globally optimal.
If $x$ is fensible and $f_{1}(x)=0$, we say the $i$ th inequality constraint $f_{1}(x) \leq 0$ is active at $x$. If $f_{1}(x)<0$, we say the constraint $f_{t}(x) \leq 0$ is inactive. (The equality constraints are active at all fensible points.) We say that a constraint is redundant if deleting it does not change the feasible set.
Example 4.1 We illustrate these definitions with a few simple unconstrained optimization problems with variable $x \in \mathbf{R}$, and dom $f_{0}=\mathbf{R}_{+}+$
$f_{0}(x)=1 / x: p^{*}=0$, but the optimal value is not achieved.
$f_{0}(x)=-\log x: p^{*}=-\infty$, so this problem is unbounded below.
$f_{0}(x)=x \log x: p^{\star}=-1 / e$, achieved at the (unique) optimal point $x^{\star}=1 / e .$
Feasibility problems
If the objective function is identically zero, the optimal value is either zero (if the feasible set is nonempty) or $\infty$ (if the feasible set is empty). We call this the
数值分析代考
.1 优化问题
4.1.1 基本术语
我们使用符号
$$
\开始{数组}{ll}
\text { 最小化 } & f_{0}(x) \
\text { 服从 } & f_{1}(x) \leq 0, \quad i=1, \ldots, m \
& h_{1}(x)=0, \quad i=1, \ldots, p
\结束{数组}
$$
描述在满足条件 $f_{1}(x) \leq 0, i=1, \ldots, m 的所有 $x$ 中找到最小化 $f_{0}(x)$ 的 $x$ 的问题$，并且 $h_{i}(x)=0，i=1，\ldots，p$。我们称 $x \in \mathbf{R}^{n}$ 为优化变量，函数 $f_{0}： \mathbf{R}^{n} \rightarrow \mathbf{R}$ 为目标函数或成本功能。不等式 $f_{i}(x) \leq 0$ 称为不等式约束，对应的函数 $f_{1}: \mathbf{R}^{n} \rightarrow \mathbf{R}$ 称为不等式约束函数。方程 $h_{1}(x)=0$ 称为等式约束，函数 $h_{1}: \mathbf{R}^{n} \rightarrow \mathbf{R}$ 是等式约束函数.如果没有约束（即 $m=p=0$ ），我们说问题（4.1）是不受约束的。
定义目标和所有约束函数的点集，
$$
\mathcal{D}=\bigcap_{i=0}^{m} \operatorname{dom} f_{i} \cap \bigcap_{i=1}^{p} \operatorname{dom} h_{i}
$$
称为优化问题（4.1）的域。一个点 $x \in \mathcal{D}$ 是可行的，如果它满足约束 $f_{t}(x) \leq 0, i=1, \ldots, m$, and $h_{i}(x) =0，i=1，\ldots，p$。如果至少存在一个可行点，则称问题（4.1）是可行的，否则不可行。所有可行点的集合称为可行集或约束集。
问题(4.1)的最优值$p^{\star}$定义为
$$
p^{\star}=\inf \left{f_{0}(x) \mid f_{1}(x) \leq 0, i=1, \ldots, m, h_{1}(x)= 0, i=1, \ldots, p\right} 。
$$
我们允许 $p^{\star}$ 采用扩展值 $\pm \infty$。如果问题是可推断的，我们有 $p^{\star}=\infty$（遵循空集的无穷大的标准约定
是 $\infty$ )。如果有可行点 $x_{k}$ 与 $f_{0}\left(x_{k}\right) \rightarrow-\infty$ 为 $k \rightarrow \infty$，则 $p^{\star} =-\infty$，我们说问题（4.1）在下面是有界的。
最优和局部最优点
我们说 $x^{\star}$ 是一个最优点，或者解决了问题 (4.1)，如果 $x^{\star}$ 是可行的并且 $f_{0}\left(x^{\star}\对）=p^{*}$。所有最优点的集合就是最优集合，记为
$$
X_{\mathrm{opt}}=\left{x \mid f_{\mathrm{i}}(x) \leq 0, i=1, \ldots, m, h_{\mathrm{i}}(x )=0, i=1, \ldots, p, f_{0}(x)=p^{\star}\right} 。
$$
如果问题（4.1）存在一个最优值，我们就说达到或达到了最优值，并且问题是可解决的。如果 $X_{\text {apt }}$ 为空，我们就说没有达到或没有达到最优值。 （当问题在下方无界时，总是会发生这种情况。）具有 $f_{0}(x) \leq p^{\star}+E$（其中 $\epsilon>0）$ 的可行点 $x$ 称为 $ \epsilon$-suboptimal，并且所有 $\epsilon$-suboptimal 点的集合称为问题（4.1）的 e-suboptimal set。
如果存在 $R>0$，我们说可行点 $x$ 是局部最优的，使得
$$
\开始{对齐}
f_{0}(x)=& \inf \left{f_{0}(z) \mid f_{1}(z) \leq 0, i=1, \ldots, m\right.\
&\left.h_{1}(z)=0, i=1, \ldots, p,|z-x|_{2} \leq R\right}
\end{对齐}
$$
或者，换句话说，$x$ 解决了优化问题
$$
\开始{数组}{ll}
\text { 最小化 } & f_{0}(z) \
\text { 服从 } & f_{1}(z) \leq 0, \quad i=1, \ldots, m \
& h_{1}(z)=0, \quad i=1, \ldots, p \
& |z-x|_{2} \leq R
\结束{数组}
$$
带有变量 $z$。粗略地说，这意味着 $x$ 在可行集中的附近点上最小化 $f_{0}$。 ‘全局最优’一词有时用于’最优’以区分’局部最优’和’最优’。然而，在本书中，最优意味着全局最优。
如果$x$ 是可理解的并且$f_{1}(x)=0$，我们说第$i$ 个不等式约束$f_{1}(x) \leq 0$ 在$x$ 处有效。如果 $f_{1}(x)<0$，我们说约束 $f_{t}(x) \leq 0$ 是无效的。 （等式约束在所有可分解点都是有效的。）我们说如果删除一个约束不会改变可行集，它就是冗余的。
例 4.1 我们用变量 $x \in \mathbf{R}$ 和 dom $f_{0}=\mathbf{R}_{+}+$ 的几个简单的无约束优化问题来说明这些定义
- $f_{0}(x)=1 / x: p^{*}=0$，但没有达到最优值。
- $f_{0}(x)=-\log x: p^{*}=-\infty$，所以这个问题在下面是无界的。
- $f_{0}(x)=x \log x: p^{\star}=-1 / e$，在（唯一）最优点 $x^{\star}=1 / e .$
可行性问题
如果目标函数完全为零，则最优值要么为零（如果可行集非空）或 $\infty$（如果可行集为空）。我们称之为
数学代写| Chebyshev polynomials 数值分析代考 请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。
时间序列分析代写
统计作业代写
随机过程代写
随机过程，是依赖于参数的一组随机变量的全体，参数通常是时间。 随机变量是随机现象的数量表现，其取值随着偶然因素的影响而改变。 例如，某商店在从时间t0到时间tK这段时间内接待顾客的人数，就是依赖于时间t的一组随机变量，即随机过程
