19th Ave New York, NY 95822, USA

数学代考| Farkas’ Lemma for Conic Linear Programming 运筹学代写

my-assignmentexpert愿做同学们坚强的后盾，助同学们顺利完成学业，同学们如果在学业上遇到任何问题，请联系my-assignmentexpert™，我们随时为您服务！

运筹学代写

We first introduce the notion of “interior” of cones.
Definition 1 We call $\mathbf{X}$ an interior point of cone $K$ if and only if, for any point $\mathbf{Y} \in K^{*}, \mathbf{Y} \bullet \mathbf{X}=0$ implies $\mathbf{Y}=\mathbf{0}$.
The set of interior points of $K$ is denoted by $\stackrel{\circ}{K}$.
Theorem 1 The interior of the following convex cones are given as:

• The interior of the nonnegative orthant cone is the set of all vectors where every entry is
positive.
• The interior of the positive semidefinite cone is the set of all positive definite matrices.
• The interior of $p$-order cone is the set of $\left{(u ; x) \in E^{n+1} \quad: u>|\mathbf{x}|{p}\right}$. We give a sketch of the proof for the second-order cone, i.e., $p=2$. Let $(\bar{u} ; \overline{\mathbf{x}}) \neq$ 0 be any second-order cone point but $\bar{u}=|\overrightarrow{\mathbf{x}}|$. Then, we can choose a dual cone (also the second-order cone) point $(v ; y)$ such that $$v=\alpha \bar{u}, \mathbf{y}=-\alpha \overline{\mathbf{x}}$$ for a positive $\alpha$. Note that $$(\bar{u} ; \overline{\mathbf{x}}) \bullet(v ; \mathbf{y})=\alpha \bar{v}^{2}-\alpha|\overline{\mathbf{x}}|^{2}=0 .$$ Then, one can let $\alpha>0$ so that $(v ; \mathbf{y})$ cannot be zero Now let $(\bar{u} ; \overline{\mathbf{x}})$ be any given second-order cone point with $\bar{u}>|\overline{\mathbf{x}}|$. We like to prove that, for any dual cone (also the second-order cone) point $(v ; \mathbf{y})$, $(\bar{u} ; \overline{\mathbf{x}})$ $(\bar{u} ; \overline{\mathbf{x}}) \bullet(v ; \mathbf{y})=0$ 173 Proposition 1 Let $\mathbf{X} \in K$ and $\mathbf{Y} \in K^{} .$ Then For any nonnegative constant $\kappa, \mathbf{Y} \cdot \mathbf{X} \leq \kappa$ where the interior of the feasible region is $$\stackrel{\circ}{\mathcal{F}}:={\mathbf{X}: \mathcal{A} \mathbf{X}=\mathbf{b}, \mathbf{X} \in \stackrel{\circ}{K}}$$ If $\mathcal{F}$ is empty with $K=E{+}^{n}$, from Farkas’ lemma for linear programming, a vector $\mathbf{y} \in E^{m}$, with $\mathbf{y}^{T} \mathbf{A} \leq \mathbf{0}$ and $\mathbf{y}^{T} \mathbf{b}>0$, always exists and is called an infeasibility certificate for the system ${\mathbf{x}: \mathbf{A x}=\mathbf{b}, \mathbf{x} \geq 0}$.
Does this alternative relations hold for $\bar{K}$ being a general closed convex one? Let us rigorousize the question. Let us define the reverse operator of (6.2) from a vector to a matrix:
(6.4)
$\mathbf{y}^{T} \mathcal{A}=\sum_{i=1}^{m} \mathbf{A}{i} y{i} .$ $\mathbf{X} \in E^{k \times n}$
$$\mathbf{y}^{T} \mathcal{A} \bullet \mathbf{X}=\mathbf{y}^{T}(\mathcal{A X}),$$
Note that, by the definition, for any matrix
that is, the association property holds. Also, $\left(\mathbf{y}^{T} \mathcal{A}\right)^{T}=\mathcal{A}^{T} \mathbf{y}$, that is, the transpose operation applies here as well.
Then, the question becomes: when $\mathcal{F}$ is empty, does there exist a vector $\mathbf{y} \in$ $E^{m}$ such that $-\mathbf{y}^{T} \mathcal{A} \in K^{}$ and $\mathbf{y}^{T} \mathbf{b}>0$ ? Similarly, one can ask: when set $\left{\mathbf{y}: \mathbf{C}^{T}-\mathbf{y}^{T} \mathcal{A} \in K\right}$ is empty, does there exist a matrix $\mathbf{X} \in K^{*}$ such that $\mathcal{A} \mathbf{X}=\mathbf{0}$ and $\mathbf{C} \cdot \mathbf{X}<0$ ? Note that the answer to the second question is also “yes” when $K=E_{+}^{n}$. $K=E_{+}^{n}$
Example below.
• 非负正锥的内部是所有向量的集合，其中每个条目都是正的。
• 正半定锥的内部是所有正定矩阵的集合.
• $p$-order 锥的内部是 $\left{(u ; x) \in E^{n+1} \quad: u>|\mathbf{x} |{p}\right}$。我们给出了二阶锥的证明草图，即 $p=2$。令 $(\bar{u} ; \overline{\mathbf{x}}) \neq$ 0 为任何二阶锥点，但 $\bar{u}=|\overrightarrow{\mathbf{x}}|$ .然后，我们可以选择一个双锥（也是二阶锥）点 $(v ; y)$ 使得 $$v=\alpha \bar{u}, \mathbf{y}=-\alpha \overline{ \mathbf{x}}$$ 为正的 $\alpha$。注意 $$(\bar{u} ; \overline{\mathbf{x}}) \bullet(v ; \mathbf{y})=\alpha \bar{v}^{2}-\alpha|\overline {\mathbf{x}}|^{2}=0 。$$ 那么，可以让 $\alpha>0$ 使得 $(v ; \mathbf{y})$ 不能为零 现在让 $(\bar{u} ; \overline{\mathbf{x}})$是具有 $\bar{u}>|\overline{\mathbf{x}}|$ 的任何给定二阶锥点。我们想证明，对于任何双锥（也是二阶锥）点 $(v ; \mathbf{y})$, $(\bar{u} ; \overline{\mathbf{x}})$ $(\bar{u} ; \overline{\mathbf{x}}) \bullet(v ; \mathbf{y})=0$ 173 命题 1 令 $\mathbf{X} \in K$ 和 $\mathbf {Y} \in K^{} .$ 那么对于任何非负常数 $\kappa，\mathbf{Y} \cdot \mathbf{X} \leq \kappa$ 其中可行域的内部是 $$\stackrel{ \circ}{\mathcal{F}}:={\mathbf{X}: \mathcal{A} \mathbf{X}=\mathbf{b}, \mathbf{X} \in \stackrel{\circ}{ K}}$$ 如果 $\mathcal{F}$ 为空且 $K=E{+}^{n}$，来自 Farkas 的线性规划引理，向量 $\mathbf{y} \in E^{ m}$，$\mathbf{y}^{T} \mathbf{A} \leq \mathbf{0}$ 和 $\mathbf{y}^{T} \mathbf{b}>0$，总是存在并被称为系统 ${\mathbf{x} 的不可行证书： \mathbf{A x}=\mathbf{b}, \mathbf{x} \geq 0}$。
这种替代关系是否成立$\bar{K}$ 是一个一般闭凸的？让我们把问题严格化。让我们定义从向量到矩阵的 (6.2) 的逆算子：
(6.4)
$\mathbf{y}^{T} \mathcal{A}=\sum_{i=1}^ {m} \mathbf{A}{i} y{i} .$ $\mathbf{X} \in E^{k \times n}$
$$\mathbf{y}^{T } \mathcal{A} \bullet \mathbf{X}=\mathbf{y}^{T}(\mathcal{AX}),$$
注意，根据定义，对于任何矩阵< br>也就是说，关联属性成立。还有$\left(\mathbf{y}^{T} \mathcal{A}\right)^{T}=\mathcal{A}^{T} \mathbf{y}$，也就是转置操作这里也适用。
那么问题就变成了：当 $\mathcal{F}$ 为空时，是否存在一个向量 $\mathbf{y} \in$ $E^{m}$ 使得 $- \mathbf{y}^{T} \mathcal{A} \in K^{ }$ 和 $\mathbf{y}^{T} \mathbf{b}>0$ ?类似地，人们可以问：当设置 $\left{\mathbf{y}: \mathbf{C}^{T}-\mathbf{y}^{T} \mathcal{A} \in K\right}$ 是空，是否存在矩阵 $\mathbf{X} \in K^{*}$ 使得 $\mathcal{A} \mathbf{X}=\mathbf{0}$ 和 $\mathbf{C} \cdot \mathbf{X}<0$ ?请注意，当 $K=E_{+}^{n}$ 时，第二个问题的答案也是“是”。 $K=E_{+}^{n}$
示例如下。

什么是运筹学代写

• 确定需要解决的问题。
• 围绕问题构建一个类似于现实世界和变量的模型。
• 使用模型得出问题的解决方案。
• 在模型上测试每个解决方案并分析其成功。
• 实施解决实际问题的方法。

运筹学代写的三个特点

• 优化——运筹学的目的是在给定的条件下达到某一机器或者模型的最佳性能。优化还涉及比较不同选项和缩小潜在最佳选项的范围。
• 模拟—— 这涉及构建模型，以便在应用解决方案刀具体的复杂大规模问题之前之前尝试和测试简单模型的解决方案。
• 概率和统计——这包括使用数学算法和数据挖掘来发现有用的信息和潜在的风险，做出有效的预测并测试可能的解决方法。