19th Ave New York, NY 95822, USA

# 数学代考| The HSD Algorithm 运筹学代写

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

## 运筹学代写

There is an algorithm, termed the Homogeneous Self-Dual Algorithm that overcomes the difficulties mentioned above. The algorithm achieves the theoretically best $O(\sqrt{n} \log (1 / \varepsilon))$ complexity bound and is often used in linear programming software packages.

The algorithm is based on the construction of a homogeneous and self-dual linear program related to (LP) and (LD) (see Sect. 5.5). We now briefly explain the two major concepts, homogeneity and self-duality, used in the construction.

In general, a system of linear equations of inequalities is homogeneous if the right hand side components are all zero. Then if a solution is found, any positive multiple of that solution is also a solution. In the construction used below, we allow a single inhomogeneous constraint, often called a normalizing constraint. Karmarkar’s original canonical form is a homogeneous linear program.

A linear program is termed self-dual if the dual of the problem is equivalent to the primal. The advantage of self-duality is that we can apply a primal-dual interiorpoint algorithm to solve the self-dual problem without doubling the dimension of the linear system solved at each iteration.
$5.7$ Termination and Initialization
157
The homogeneous and self-dual linear program (HSDP) is constructed from (LP) and (LD) in such a way that the point $\mathbf{x}=\mathbf{1}, \mathbf{y}=\mathbf{0}, \tau=1, z=1, \theta=1$ is feasible. The primal program is where $$\overline{\mathbf{b}}=\mathbf{b}-\mathbf{A l}, \overline{\mathbf{c}}=\mathbf{c}-\mathbf{1}, \bar{z}=\mathbf{c}^{T} \mathbf{1}+1$$
Note also that the top two constraints in (HSDP), with $\tau=1$ and $\theta=0$, represent primal and dual feasibility (with $\mathbf{x} \geq \mathbf{0}$ ). The third equation represents reversed weak duality (with $\mathbf{b}^{T} \mathbf{y} \geq \mathbf{c}^{T} \mathbf{x}$ ) rather than the reverse. So if these three equations are satisfied with $\tau=1$ and $\theta=0$ they define primal and dual optimal solutions. Then, to achieve primal and dual feasibility for $\mathbf{x}=\mathbf{1},(\mathbf{y}, \mathbf{s})=(\mathbf{0}, \mathbf{1})$, we artificial variable $\theta$. The fourth constraint is added to achieve self-duality.

The problem is self-dual because its overall coefficient matrix has the property that its transpose is equal to its negative. It is skew-symmetric.

Denote by $\mathbf{s}$ the slack vector for the second constraint and by $\kappa$ the slack scalar for the third constraint. Denote by $\mathcal{F}{h}$ the set of all points $(\mathbf{y}, \mathbf{x}, \tau, \theta, \mathbf{s}, \kappa)$ that are feasible for (HSDP). Denote by $\mathcal{F}{h}^{0}$ the set of strictly feasible points with $(\mathbf{x}, \boldsymbol{\tau}, \mathbf{s}, \boldsymbol{\kappa})>\mathbf{0}$ in $\mathcal{F}_{h}$. By combining the constraints (Exercise 14) we can write the last (equality) constraint as
$$\mathbf{1}^{T} \mathbf{x}+\mathbf{1}^{T} \mathbf{s}+\tau+\kappa-(n+1) \theta=(n+1)$$
which serves as a normalizing constraint for (HSDP). This implies that for $0 \leq \theta \leq$ 1 the variables in this equation are bounded.

$5.7$ 终止和初始化
157

$$\mathbf{1}^{T} \mathbf{x}+\mathbf{1}^{T} \mathbf{s}+\tau+\kappa-(n+1) \theta=(n+1)$$

## 什么是运筹学代写

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

## 运筹学代写的三个特点

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