西北工业大学工程优化设计课件word版第三秠 擠綦束非綿性裄划

第三章 无约束非线性规划 （Unconstrained Nonlinear Programming） §3.1 最优解的基本性质（Basic Properties of Optimum Solutions） 3.1.1 局部最小的必要和充分条件 （1）定义：若 ， ，对满足 的所有的 ，存在 ，则 是函数 在集 上的局部最小点，上述不等式换成严格不等式 ，则 是函数 在集 上的严格局部最小点。 定义：对所有 ，存在 则 是函数 在集 上的整体最小点，同样当 时， 是严格整体最小点。 （2）局部最小点的一阶必要条件 假设函数 （ ， 位于1维空间 ），在 处是可微的，对所有的 ， 是局部最小点的一阶必要条件是 证：若 是 的局部最小点 那么 （3.1） 当 时， （3.2） 当 时， 当 趋近于零，取极限，则有： （3.3） 可以从任意方向趋近于零，即 可以是正值也可以是负值，所以式（3.3）只有 即 （3.4） 若 在 维空间， ，设 ，第 个元素为1，其他元素为0的单位向量 （3.5） 同样，若 是局部最小点 （3.6） 当 时， （3.7） 当 时， （3.7） 当 趋近于零，取极限，我们有 （3.8） 写成向量形式 （3.9） 注意上述 是在可行域内部，向任意方向的微小移动都是可行的。 （3）若规定了 的可行方向 ，则 是最小点的一阶必要条件是： （3.10） 证： 只能沿可行方向 移动 （3.11） 式中 是一个标量，表示移的步长， 是 的函数 （3.12） 目标函数也可表示为 的函数 （3.13） （3.14） 当 时 时， 是最小点 因而 是最小点的一阶必要条件是 （4）局部最小点的必要和充分条件 若函数 二阶可微 ， ， 是局部最小点的必要和充分条件是 证： （3.15） 当 （3.16） 当 ，对足够小的 （3.17） （3.18） 是局部最小点 例： 当 是极值点，最小点 当 这时 是拐点（见图3.1） 图3.1 当 在 维空间 ， 二阶可微 ，其T aylor级数展开式 （3.19） 定理：对 ， ，在 处 ，对向量 ，即 正定，那么 是函数 的局部最小点。 证：对任一向量 ，其模量 ，设 （3.20） 已知 （3.21） 若 正定，对足够小的 （3.22） （3.23） 是局部最小点 3.1.2 凸函数及其性质 （1）凸函数的定义 在凸域 中任意二个点 若存在 （3.24） 则函数 为凸函数，若 （3.25） 则函数 为严格凸函数，见图3.2。 图3.2 从图形上看凸函数是碗形，凸函数曲线上任意二点间的连线，其中没有任何一个点低于该曲线。 （2）凸函数的条件 定理：若 ， 是凸集，函数一次可微 那么， 是域 上的凸函数 证：i，若 是凸函数。 （3.26） 当 取极限，式（3.26）左端实际上是 沿 方向的方向导数 即 （3.27） 得到满足 ii，若 一这条件满足， 是凸函数。 设： ， ， 先设 （3.28） 再设 （3.29） 乘式（3.28）加上乘式（3.29）得 （3.30） 由式（3.30）可得 已知 是凸函数。 图3.3 （4）凸函数的局部最小和总体最小 定理：若 是凸集 上的凸函数， 。 ，对所有 ，满足 ，那么 是在 域上的总体最小点。 证： 是凸函数，由式（3.27） 满足 ，也就是说 是沿 这一可行方向的局部最小点，见式（3.10） ， 是函数 在域 上的整体最小点。 这个定理可进一步叙过为：若 是连续可微的凸函数，满足使 是局部最小的一阶必要条件的 ，也满足它是总体最小的必要和充分条件。 推论1：若 是凸函数在凸集 二个不同点上达到总体最小，那么在这二点连线上所有点都达到总体最小。 推论2：若 在凸集 上是严格凸函数，那么 只有单一总体最小。 3.1.3 收敛性 （1）算法和点系 设 ，通过某种算法产生一新点 ，按 得到点系 。算法A可以是 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 表达式，也可以是程序。通过算法得到的也可能是个子集，新点是该子集中的一个点，即 。当 时， ，算法A在 处具有封闭性。 （2）算法的总体收敛 对任意初始点 通过算法A产生点系 ，当 时其函数值达到最小，这时称该算法为总体收敛。 （3）收敛速度：序列数 收敛至 ，设 ， ，若 满足该关系式的最大非负数 为收敛阶数。对 为线性收敛， 为收敛速度。 为超线性收敛。对向量收敛，如 收敛至 ，其收敛性质用某种函数， 收敛至 来进行分析， 称为误差系数，在规划问题中可以用目标函数作为误差函数。 例： 这是收敛速度为 的线性收敛。 §3.2 一维搜索（One-dimensional Search） 大多数优化设计问题是从一个初始点出发，按数学规划方法，找出搜索方向，沿这个方向寻求新的设计点（局部最小点），使目标函数得到改进。如此循环直到求出最优设计。在给定搜索方向上寻求局部最小点的过程，称为一维搜索，这是很多数学规划方法的基础。 3.2.1 缩小区间法 逐步缩小搜索区间，直到最小点存在的范围足够小，在预定的误差范围内停止搜索，最简单的缩小区间法如下图所示。 (1) (2) (3) 搜索区间 EMBED Equation.DSMT4 计算点 缩小的区间 图3.4 这种任意选择计算点，缩小搜索区间的方法，计算函数值次数多，效率低，下面介绍的方法按一定规律尽量减少计算函数值的次数，提高搜索效率。 （1）Fibonacci法 Fibonacci数 （3.31） 数序列为 1，1，2，3，5，8，13，… 由式（3.31） （3.32） 设 图3.5 如图3.5所示，对区段[0,1]，按式（3.32）得 设 ，比较端点和二个中间点的函数值，假设保留区间 ，对缩小后的区间，保持一个点不变。 按对称原则找出 ，只需计算一个新点的函数值，决定缩小区间 ，如此循环。Fibonacci法有下列特征。 迭代次数 0 1 2 3 …… 搜索区间长度 1 迭代次数 0 1 2 3 4 5 6 Fibonacci数 1 1 2 3 5 8 13 搜索区间长度比 / 1 0.5 0.6667 …… …… 0.618 （2）黄金分割法 在区段 内按等比例分割，二个中间点对称分布，区间收缩率不变，这种方式称为黄金分割法。 图3.6 区间长度为 ， 保持对称，下一个循环区间长度 按黄金分割法 （3.33） 设 为区间收缩率 迭代停机准则： EMBED Equation.3 为预定精度要求。 3.2.2 曲线拟合法 沿搜索方向选择若干测量点，求得这些点的函数值或导数值，据此拟合出单一模式的光滑曲线，可以容易地求出最小值。 （1）牛顿法 已知某点 处的函数值 ，一阶导数 和二阶导数 ，用这三个数值构造一个二次函数 （3.34） 二次函数 在 点的函数值，一阶导数，二阶导数与目标函数的相应值相等，即 （3.35） 见图3.7。 图3.7 牛顿法 对新建的二次函数 求极值，在 处求得函数最小值 （3.36） （3.37） 对 重复上述过程，直到相邻二次迭代所得结果非常接近 停止迭代 若用 代替 ， 式（3.37）变成 （3.38） 也就是说，过 点用直线 （3.39） 代替原来的迭代见图3.8。 通过 得到新解 见式（3.38） 图3.8 （2）虚点法 用二个点的一阶导数信息代替牛顿法中已知点的二阶导数信息，即已知 构造二次函数 （3.40） 由 求出 （3.41） 其他计算步骤如牛顿法 见图3.9。 图3. 9 虚点法 （3）二次拟合 沿搜索方向已知三个点 的函数值 ，三个点应是 ，并将最小点包括进去，也就是 。 由此建立二次曲线，见图（3.10）。 图3.10 （3.42） 由 ，求出最小点 （3.43） 下一个循环应注意区分下列情况。 若 当 若 当 当 由新一轮三个点构成新的二次曲线，直到相邻二次循环目标函数非常接近，其差小于事先设定精度，停止迭代运算。 （4）三次拟合 已知二个点 ， 的函数值 以及在搜索方向上的导数值 ，这二个导数值应异号，从而保证最小点在 区间内。由上述4个已知的数值构造三次曲线，见图3.11。 （3.44） 由 求出最小点 （3.45） 式中 按这一规则进行迭代运算直到求出所需最小点。 图3.11 §3.3 最徒下降法（The Method of Steepest Descent） 3.3.1 最徒下降法的算法 从某一设计点 出发，沿目标函数负梯度方向 进行搜索，寻找新点 ，使目标函数 最小，求出步长 ，从而得到新点 ，以此规律进行迭代计算直到 足够小为止。 对二次型函数 （3.46） 式中 为 阶向量， 为对称正定 阶矩阵 由 得最小解 （3.47） （3.48） 沿负梯度方向搜索寻找新点 （3.49） 新点目标函数 （3.50） 式（3.50）对 求导 由 求步长 （3.51） （3.52） 3.3.2 最徒下降法的性质 对二次函数来说，相邻两个最徒下降方向是相互垂直的。 在 点， （3.53） （3.54） 在 和 点目标函数梯度向量积为零，也就是相邻两个最徒下降方向相互垂直。图3.12在目标函数等高线图上，表示最徒下降方向轨迹。 图3.12 最徒下降方向轨迹呈锯齿形，迭代开始阶段目标函数下降比较快，越接近最优点，下降速度趋缓，收敛速度和目标函数性质有关。最徒下降方向只反映目标函数的局部特性，在设计点局部它是下降最快的方向，就总体收敛来看它并不是一个好的方向。最徒下降法是最古老和最简单的一种优化方法。许多先进方法都是在它的基础上改进的，并以它作为比较效率的基础，它可以和其他先进方法混合使用。 §3.4 牛顿法（Newton Method） 3.4.1 牛顿法的算法 对一维问题目标函数的梯度 ，设计点 的梯度 曲线见图3.13。 图3.13 在 点以直线代替 曲线，由式（3.55）求得最小点 ，见式（3.56） （3.55） （3.56） 对多变量问题，过 点的近似超平面代替目标函数超曲面。 由式（3.57）求得最小点 ，见式（3.58） （3.57） （3.58） 将 在 点用Taylor级数展开，保留二次项 由 得 式中 得到和式（3.58）同样的解 3.4.2 牛顿法的性质 由式（3.58）可以看出，牛顿法的搜索方向考虑了设计点的负梯度方向和由二阶导数信息提供的修正。 对二次函数 从初始点 出发用牛顿法可通过一次迭代达到最优点。 据式（3.58） （3.59） 由式（3.47）可知二次函数的最优解 所以从 用牛顿法经一次迭代得到最优解 。对任意目标函数，在最优点附近呈现接近二次型函数的性质，用牛顿法十分有效。所以在迭代初期用最徒下降法，继而用牛顿法求最优解是十分有效的。使用牛顿法的主要困难在于求目标函数Hession矩阵之逆， ，特别对于多变量问题，计算工作量较大。 §3.5 共轭方向法（Conjugate Direction Method） 为了提高最徒下降法的收敛速度，不产生一系列锯齿形搜索方向，避免牛顿法中应用Hession矩阵之逆的大量计算工作。本节研究共轭方向法，公式推导仍局限在对二次函数，推导过程简单，概念明确，也有一定指导意义。 3.5.1 共轭方向 定义：给定一个对称矩阵 ，和任意二个向量 ，如果 ，那么 对 来说是共轭的，称为 共轭（或 正交），当 则 为正交。 若有一组向量 ，它们是 共轭的，则必须满足 （3.60） 例1 初始点 过 做 的切线 （3.61） 最优点处 （3.62） 研究向量 和 （3.63） 也就是 和 是 共轭的 图3.14 由图3.14可见，过 的负梯度方向 不是好的搜索方向，沿 方向搜索，即沿与切线方向 呈 共轭的方向，是更有效的搜索方向。 例2： 选择一个方向 ，确定另一个与 共轭的方向 若 ，则 ， 和 构成一组 共轭方向，从 出发，沿 找到最优点 ，再沿 找到最优点 。 共轭方向不是唯一的， 和 构成另一组 共轭方向，从 出发，先沿 找到最优点 ，再沿 找到最优点 ，见图3.15。 图3.15 定理：若 正定，有一组非零向量 ，它们是 共轭的，那么这组向量是线性独立的。 证：设一组常数 使 （3.63） 用 左乘式（3.63）， 是 共轭的 （3.64） （3.65） 正定 （3.66） 要使 必须有 也就是说，只有使所有的系数 ，式（3.63）才成立， 是线性独立的。 3.5.2 共轭方向理论 定理：若一组向量 是 共轭向量， 是任意初始点 （3.67） （3.68） 证：对二次函数 ， （3.69） （3.70） （3.71） 定理：设 是在 空间中相互 共轭的非零向量系列， 是 组成的子空间。 是任意初始点 这时， 使 在 空间中最小，此定理可称之为延伸子空间定理（Expanding Subspace Theroem）。 证： （3.72） 在任意中间点 ，使目标函数 沿 方向搜索求出最优步长 ，从而找到下一个最优点 。 （3.73） 在 点函数的梯度方向和搜索方向 垂直 当 当 由式（3.72） （3.74） 左乘式（3.74） （3.75） 根据式（3.73）和向量 是 共轭的 （3.76） 也就是说 在 空间中使 达到最小，见图3.16。 图3.16 因而 ， 在 上使 达到最小。 3.5.3 共轭梯度法 （1）共轭梯度法的算法 共轭梯度法是共轭方向法的一种，在迭代第 步用该点的负梯度方向和前边各次搜索方向的线性组合形成一个新的搜索方向。所有这些搜索方向是相互共轭的。 设起始点 ，第一个搜索方向是起始点的负梯度方向 （3.77） （3.78） （3.79） （3.80） （3.81） （2）共轭梯度定理 由式（3.77）~（3.81）所形成的系列搜索方向 是 共轭的。 证：用归纳法证明：若 成立，那么 也成立，则定理成立， 是 共轭的。 用 右乘式（3.80） （3.82） 为保证在 时， 和 共轭，也就是 由式（3.82）得 式（3.81）得证。 当 时，由归纳法假设 ，也就是 是 共轭的。 要证明 也是 共轭的，也就是 （3.83） 已知 沿 方向搜索得最优点 ， （3.84） 代表由 构成的空间 ∵ 要研究 的情况 （3.85） 我们知道搜索方向 式中 表示 和 的线性组合。 同样 （3.86） 式中 表示 由式（3.86）可知： （3.87） （3.88） 由式（3.85）、（3.87）可知 （3.89） （3.90） 由归纳法假设 和式（3.89） （3.91） 已证明式（3.81）的 使 成立 （3.92） 也就是由归纳法证明 也是一组 共轭向量。 （3）算法中系数 的推导 前面已证明，对二次函数 ，已知设计点 ，改进设计的迭代式 （3.92） 第 点是在空间 中的最小点 （3.93） 用 左乘式（3.92） 同式（3.79）。在共轭方向法中 （3.94） 用 左乘式（3.94） （3.95） 已证明 是一组共轭方向 由式（3.95） 可以写成 （3.96） 由式（3.81） 它可以使相邻二次搜索方向呈 共轭 由式（3.92） （3.97） 用 左乘式（3.97） （3.98） 我们已知 （3.99） 式（3.98）可写成 （3.100） （4）Fletcher-Reeves法 对目标函数为非二次函数的无约束优化问题 为任意函数，仍可用共轭梯度法称为Fletcher-Reeves法，本节给出具体计算步骤。 用 点的梯度 代替 ， 点的Hessian矩阵 代替 ，仍用本章所推导的适用于目标函数为二次函数的公式。 第一步 给出起始点 ， 第二步 设 i， ii， iii， 第三步 计算到 ，若 ，且不满足收敛准则 ， 为预定收敛精度。把 输入到 中，重新执行第一步，直到满足收敛准则。 为避免在每次迭代循环都计算设计点的Hessian矩阵，为确定新点进行一次一维搜索。 第一步 给出初始点 ， 第二步 设 i， 沿 方向进行一维搜索求得最优点对应的 ii， iii， 第三步 计算到 ，若 且不满足收敛准则，把 输入到 ，重新执行第一步直到满足收敛推则。 §3.6 拟牛顿法（Quasi-Newton Method） 3.6.1 拟牛顿法的基本概念 无约束最优化，从某已知点 出发，寻找搜索方向 ，沿 做一维搜索确定步长 ，从而找到改进的设计点 ，经过若干次迭代计算，得到最优设计点。寻找搜索方向是关键，前面几节讨论的方法都是在负梯度方向基础上加以修正，以提高计算效率。 ：目标函数 沿 进行一维搜索确定的步长 ：对负梯度方向 的修正矩阵 （1）最徒下降法 （2）牛顿法 （3）共轭方向法 本节讨论的拟牛顿法利用目标函数的梯度信息建立Hessian矩阵之逆的近似值，用 近似 。 通过迭代近似精度提高，并做到有限步收敛。 3.6.2 对称单秩法（SR1法，Symmetric Rank One Method） 研究目标函数为二次函数 SR1法用 近似 （3.101） （3.102） 式中 为一向量， 构成秩为1的矩阵，迭代过程中用 修正 ，并用已知一阶导数信息加以定义。 由式（3.101）、（3.102）得 （3.103） 用 左乘式（3.103） 对式（3.104）进行转换 （3.105） 将式（3.105）代到式（3.102） （3.106） 注意式（3.104），式（3.106）可写为 （3.107） 由式（3.107）可以看出，用已知一阶导数信息构成修正矩阵 。 SR1算法有下列性质： （1）如 对称， 也对称 （2）如 正定， 也正定 对任一向量 ， 正定则 设 已知 ，要使 必须使 （3.108） 也就是说， 正定，必须满足式（3.108） 否则用 替代，再计算搜索方向。 （3）SR1法对 维二次函数，可以做到有限步收敛 对称正定 设： 正定条件得到满足 经过 次迭代，下式成立 （3.109） 现要证明 （3.110） 当 （3.111） 当 （3.112） 将式（3.112）右边第2项重新组合 我们知道对二次函数 由归纳法的假设 式（3.109） 对 成立 设： （3.113） （3.114） 经过 次迭代 等于二次函数Hessian矩阵之逆，也就是SR1法经过 次迭代收敛到最优解，SR1法具备有限步收敛的性质。 （4）SR1法计算步骤 给出 ：初始对称正定矩阵 i， ii， 沿 方向，由 求 由 计算 iii， iv， 重新执行i， 直到 收敛至最优解 3.6.3 变尺度法（Variable Metric Methed） （DFP法 Davidon-Fletcher-Powell Method） （1）变尺度法的算法 给定初始对称正定矩阵 i， ii， 沿 方向 求 iii， （3.115） iv， 执行i， 迭代过程中用二个对称单秩矩阵之和修正Hessian矩阵之逆，也可称为双秩修正方法（A Rank Two Correction Procedure） （2）变尺度法的性质 i，正定性 若 正定，对任一向量 ，有 ，需证明 也正定， （3.116） 定义一个矩阵使 使 （3.117） 设 （3.118） 那么 式（3.116）可写为 （3.119） 据Cauchy-Schwarz不等式 式（3.117）第1项非负 我们已知从 沿 作一维搜索，使 需满足 （3.120） 式（3.119）第2项 由式（3.120）可知 正定， 式（3.116） 下边还需证明式（3.119）右端二项不能同时为零。 若第1项为零， 两个向量共线， 应成比例。 由式（3.118） 成比例，也就是 和 成比例。 这时 由此得出结论 ，正定 ii，有限步收敛 假设目标函数是二次函数 其Hessian矩阵是常数 ，需要证明由DFP法产生的搜索方向 是 共轭的，执行第 步使 。 定理： 是二次函数，其Hessian矩阵正定，由DFP法得到下式成立。 （3.121） （3.122） 证： 要证明 用归纳法证明，也就是假设上式对 成立，证明对 也成立。 假设： 成立 已知 也就是一直到 （3.123） 同样由归纳法的假设 对 成立 那么 由式（3.123）可知 由DFP法产生的系列搜索方向 是共轭向量。 由归纳法假设 需证明 成立 前面已证明 设： 对 维二次函数，用DFP法经过 步运算使修正矩阵 等于Hessian矩阵之逆，也就是实现有限步收敛。 PAGE 65 _1147809551.unknown _1147812411.unknown _1148149370.unknown _1148151628.unknown _1148152729.unknown _1148995119.unknown _1149174673.unknown _1149408465.unknown _1149423122.unknown _1149424186.unknown _1149425919.unknown _1155497007.unknown _1155497170.unknown _1149426525.unknown _1149424200.unknown _1149423423.unknown _1149422893.unknown _1149423020.unknown _1149408466.unknown _1149175286.unknown _1149175986.unknown _1149176440.unknown _1149176562.unknown _1149176592.unknown _1149176590.unknown _1149176532.unknown _1149176382.unknown _1149176429.unknown _1149176005.unknown _1149175511.unknown _1149175649.unknown _1149175770.unknown _1149175380.unknown _1149174978.unknown _1149175147.unknown _1149174698.unknown _1149172179.unknown _1149173860.unknown _1149173942.unknown _1149174065.unknown _1149173914.unknown _1149172873.doc _1149173048.unknown _1149172814.doc _1149171577.unknown _1149171827.unknown _1149172030.unknown _1149171750.unknown _1149171447.unknown _1149171474.unknown _1149171379.unknown _1148153290.unknown _1148153529.unknown _1148153717.unknown _1148153830.unknown _1148153879.unknown _1148154342.unknown _1148154361.unknown _1148154136.unknown _1148153876.unknown _1148153755.unknown _1148153808.unknown _1148153726.unknown _1148153560.unknown _1148153691.unknown _1148153533.unknown _1148153345.unknown _1148153393.unknown _1148153459.unknown _1148153380.unknown _1148153320.unknown _1148153329.unknown _1148153312.unknown _1148153065.unknown _1148153173.unknown _1148153202.unknown _1148153274.unknown _1148153192.unknown _1148153156.unknown _1148153165.unknown _1148153076.unknown _1148152988.unknown _1148153034.unknown _1148153056.unknown _1148153004.unknown _1148152952.unknown _1148152963.unknown _1148152782.unknown _1148152005.unknown _1148152280.unknown _1148152667.unknown _1148152699.unknown _1148152721.unknown _1148152693.unknown _1148152377.unknown _1148152379.unknown _1148152373.unknown _1148152163.unknown _1148152182.unknown _1148152204.unknown _1148152168.unknown _1148152095.unknown _1148152157.unknown _1148152026.unknown _1148151819.unknown _1148151951.unknown _1148151987.unknown _1148151999.unknown _1148151956.unknown _1148151887.unknown _1148151943.unknown _1148151850.unknown _1148151735.unknown _1148151793.unknown _1148151811.unknown _1148151783.unknown _1148151687.unknown _1148151718.unknown _1148151683.unknown _1148150393.unknown _1148151073.unknown _1148151331.unknown _1148151511.unknown _1148151547.unknown _1148151594.unknown _1148151521.unknown _1148151467.unknown _1148151500.unknown _1148151399.unknown _1148151145.unknown _1148151173.unknown _1148151231.unknown _1148151153.unknown _1148151119.unknown _1148151126.unknown _1148151112.unknown _1148150601.unknown _1148150822.unknown _1148151030.unknown _1148151039.unknown _1148151014.unknown _1148150764.unknown _1148150793.unknown _1148150602.unknown _1148150525.unknown _1148150599.unknown _1148150600.unknown _1148150570.unknown _1148150582.unknown _1148150506.unknown _1148150521.unknown _1148150460.unknown _1148149697.unknown _1148150043.unknown _1148150117.unknown _1148150160.unknown _1148150272.unknown _1148150126.unknown _1148150096.unknown _1148150109.unknown _1148150089.unknown _1148149880.unknown _1148149930.unknown _1148150036.unknown _1148149922.unknown _1148149754.unknown _1148149803.unknown _1148149752.unknown _1148149519.unknown _1148149640.unknown _1148149670.unknown _1148149676.unknown _1148149662.unknown _1148149555.unknown _1148149556.unknown _1148149525.unknown _1148149540.unknown _1148149456.unknown _1148149479.unknown _1148149484.unknown _1148149474.unknown _1148149420.unknown _1148149436.unknown _1148149413.unknown _1148148595.unknown _1148149097.unknown _1148149300.unknown _1148149328.unknown _1148149349.unknown _1148149360.unknown _1148149344.unknown _1148149311.unknown _1148149322.unknown _1148149306.unknown _1148149184.unknown _1148149287.unknown _1148149295.unknown _1148149269.unknown _1148149151.unknown _1148149157.unknown _1148149117.unknown _1148148801.unknown _1148149064.unknown _1148149084.unknown _1148149089.unknown _1148149071.unknown _1148149082.unknown _1148149018.unknown _1148149057.unknown _1148149025.unknown _1148148911.unknown _1148148732.unknown _1148148765.unknown _1148148793.unknown _1148148750.unknown _1148148670.unknown _1148148722.unknown _1148148638.unknown _1147812784.unknown _1147812984.unknown _1147813147.unknown _1148148517.unknown _1148148549.unknown _1147813148.unknown _1147813033.unknown _1147813146.unknown _1147813145.unknown _1147813003.unknown _1147812892.unknown _1147812943.unknown _1147812944.unknown _1147812904.unknown _1147812856.unknown _1147812879.unknown _1147812859.unknown _1147812820.unknown _1147812541.unknown _1147812588.unknown _1147812646.unknown _1147812715.unknown _1147812621.unknown _1147812572.unknown _1147812578.unknown _1147812565.unknown _1147812464.unknown _1147812484.unknown _1147812531.unknown _1147812472.unknown _1147812440.unknown _1147812446.unknown _1147812433.unknown _1147810988.unknown _1147811700.unknown _1147812089.unknown _1147812282.unknown _1147812336.unknown _1147812365.unknown _1147812385.unknown _1147812354.unknown _1147812316.unknown _1147812323.unknown _1147812311.unknown _1147812210.unknown _1147812252.unknown _1147812262.unknown _1147812241.unknown _1147812186.unknown _1147812197.unknown _1147812112.unknown _1147811976.unknown _1147812023.unknown _1147812058.unknown _1147812071.unknown _1147812049.unknown _1147812012.unknown _1147812018.unknown _1147811993.unknown _1147811798.unknown _1147811945.unknown _1147811954.unknown _1147811841.unknown _1147811711.unknown _1147811734.unknown _1147811705.unknown _1147811321.unknown _1147811536.unknown _1147811641.unknown _1147811664.unknown _1147811675.unknown _1147811656.unknown _1147811561.unknown _1147811627.unknown _1147811543.unknown _1147811479.unknown _1147811498.unknown _1147811505.unknown _1147811488.unknown _1147811406.unknown _1147811430.unknown _1147811368.unknown _1147811132.unknown _1147811226.unknown _1147811265.unknown _1147811296.unknown _1147811253.unknown _1147811172.unknown _1147811179.unknown _1147811163.unknown _1147811045.unknown _1147811067.unknown _1147811115.unknown _1147811051.unknown _1147811008.unknown _1147811023.unknown _1147810998.unknown _1147810465.unknown _1147810693.unknown _1147810927.unknown _1147810963.unknown _1147810976.unknown _1147810982.unknown _1147810970.unknown _1147810951.unknown _1147810958.unknown _1147810945.unknown _1147810873.unknown _1147810906.unknown _1147810916.unknown _1147810898.unknown _1147810849.unknown _1147810866.unknown _1147810752.unknown _1147810605.unknown _1147810650.unknown _1147810663.unknown _1147810665.unknown _1147810691.unknown _1147810658.unknown _1147810636.unknown _1147810641.unknown _1147810629.unknown _1147810535.unknown _1147810577.unknown _1147810599.unknown _1147810548.unknown _1147810488.unknown _1147810497.unknown _1147810477.unknown _1147810137.unknown _1147810287.unknown _1147810384.unknown _1147810403.unknown _1147810439.unknown _1147810398.unknown _1147810333.unknown _1147810356.unknown _1147810305.unknown _1147810202.unknown _1147810230.unknown _1147810274.unknown _1147810225.unknown _1147810182.unknown _1147810188.unknown _1147810176.unknown _1147809672.unknown _1147809797.unknown _1147810061.unknown _1147810131.unknown _1147809802.unknown _1147809723.unknown _1147809758.unknown _1147809711.unknown _1147809607.unknown _1147809640.unknown _1147809650.unknown _1147809613.unknown _1147809572.unknown _1147809601.unknown _1147809562.unknown _1147807901.unknown _1147808549.unknown _1147808921.unknown _1147809140.unknown _1147809331.unknown _1147809491.unknown _1147809529.unknown _1147809341.unknown _1147809227.unknown _1147809247.unknown _1147809177.unknown _1147809032.unknown _1147809066.unknown _1147809075.unknown _1147809041.unknown _1147808981.unknown _1147808988.unknown _1147808933.unknown _1147808797.unknown _1147808864.unknown _1147808876.unknown _1147808881.unknown _1147808870.unknown _1147808813.unknown _1147808819.unknown _1147808808.unknown _1147808691.unknown _1147808776.unknown _1147808785.unknown _1147808755.unknown _1147808673.unknown _1147808678.unknown _1147808637.unknown _1147808313.unknown _1147808452.unknown _1147808499.unknown _1147808535.unknown _1147808542.unknown _1147808506.unknown _1147808463.unknown _1147808486.unknown _1147808457.unknown _1147808398.unknown _1147808433.unknown _1147808441.unknown _1147808428.unknown _1147808365.unknown _1147808374.unknown _1147808343.unknown _1147808140.unknown _1147808248.unknown _1147808274.unknown _1147808290.unknown _1147808266.unknown _1147808155.unknown _1147808172.unknown _1147808149.unknown _1147808020.unknown _1147808083.unknown _1147808110.unknown _1147808056.unknown _1147807976.unknown _1147808002.unknown _1147807903.unknown _1147807226.unknown _1147807457.unknown _1147807689.unknown _1147807738.unknown _1147807800.unknown _1147807847.unknown _1147807746.unknown _1147807712.unknown _1147807729.unknown _1147807720.unknown _1147807706.unknown _1147807661.unknown _1147807674.unknown _1147807680.unknown _1147807667.unknown _1147807671.unknown _1147807587.unknown _1147807600.unknown _1147807502.unknown _1147807368.unknown _1147807417.unknown _1147807431.unknown _1147807441.unknown _1147807421.unknown _1147807397.unknown _1147807403.unknown _1147807388.unknown _1147807285.unknown _1147807352.unknown _1147807359.unknown _1147807301.unknown _1147807257.unknown _1147807277.unknown _1147807251.unknown _1143530670.unknown _1143553341.unknown _1143617747.unknown _1143636850.unknown _1143896858.unknown _1147508812.unknown _1147509071.unknown _1147807192.unknown _1147509081.unknown _1147509107.unknown _1147508882.unknown _1147509007.unknown _1147509028.unknown _1147508944.unknown _1147508864.unknown _1143958606.unknown _1143959088.unknown _1143979231.unknown _1144047304.unknown _1144048369.unknown _1147508749.unknown _1144048377.unknown _1144048362.unknown _1144046877.unknown _1144047256.unknown _1143979295.unknown _1143979158.unknown _1143979167.unknown _1143961672.unknown _1143958648.unknown _1143959029.unknown _1143897984.unknown _1143898725.unknown _1143898011.unknown _1143897328.unknown _1143897496.unknown _1143896921.unknown _1143877096.unknown _1143878509.unknown _1143895223.unknown _1143895347.unknown _1143878792.unknown _1143877942.unknown _1143878045.unknown _1143877327.unknown _1143876155.unknown _1143876218.unknown _1143876929.unknown _1143876213.unknown _1143637233.unknown _1143876136.unknown _1143637226.unknown _1143619610.unknown _1143636076.unknown _1143636190.unknown _1143636719.unknown _1143636842.unknown _1143636458.unknown _1143636143.unknown _1143636178.unknown _1143636079.unknown _1143634287.unknown _1143635942.unknown _1143636065.unknown _1143634332.unknown _1143634266.unknown _1143619916.unknown _1143634205.unknown _1143619419.unknown _1143619441.unknown _1143619503.unknown _1143619526.unknown _1143619486.unknown _1143619456.unknown _1143619437.unknown _1143618310.unknown _1143618317.unknown _1143618319.unknown _1143617774.unknown _1143617926.unknown _1143618211.unknown _1143617762.unknown _1143556894.unknown _1143558947.unknown _1143617365.unknown _1143617497.unknown _1143617502.unknown _1143617515.unknown _1143617498.unknown _1143617423.unknown _1143617450.unknown _1143617391.unknown _1143617105.unknown _1143617184.unknown _1143617348.unknown _1143617119.unknown _1143617028.unknown _1143617042.unknown _1143616972.unknown _1143558015.unknown _1143558382.unknown _1143558683.unknown _1143558738.unknown _1143558835.unknown _1143558604.unknown _1143558269.unknown _1143558354.unknown _1143558123.unknown _1143557757.unknown _1143557870.unknown _1143557969.unknown _1143557841.unknown _1143557521.unknown _1143557642.unknown _1143557532.unknown _1143557006.unknown _1143555554.unknown _1143556279.unknown _1143556588.unknown _1143556675.unknown _1143556771.unknown _1143556787.unknown _1143556701.unknown _1143556605.unknown _1143556440.unknown _1143556450.unknown _1143556413.unknown _1143555871.unknown _1143555954.unknown _1143555974.unknown _1143555899.unknown _1143555576.unknown _1143555600.unknown _1143555560.unknown _1143554894.unknown _1143554970.unknown _1143555458.unknown _1143555513.unknown _1143555436.unknown _1143554918.unknown _1143554963.unknown _1143554903.unknown _1143553862.unknown _1143554484.unknown _1143554858.unknown _1143554368.unknown _1143553775.unknown _1143553816.unknown _1143553696.unknown _1143532342.unknown _1143533375.unknown _1143553064.unknown _1143553158.unknown _1143553209.unknown _1143553330.unknown _1143553185.unknown _1143553095.unknown _1143553102.unknown _1143553068.unknown _1143551381.unknown _1143551777.unknown _1143552227.unknown _1143551636.unknown _1143551164.unknown _1143551211.unknown _1143533385.unknown _1143532584.unknown _1143532692.unknown _1143533329.unknown _1143532617.unknown _1143532372.unknown _1143532441.unknown _1143532358.unknown _1143531439.unknown _1143532182.unknown _1143532318.unknown _1143532328.unknown _1143532206.unknown _1143532042.unknown _1143532167.unknown _1143531462.unknown _1143531512.unknown _1143531228.unknown _1143531414.unknown _1143531434.unknown _1143531262.unknown _1143531038.unknown _1143531169.unknown _1143530683.unknown _1143531031.unknown _1143529767.unknown _1143530197.unknown _1143530278.unknown _1143530627.unknown _1143530640.unknown _1143530370.unknown _1143530249.unknown _1143530262.unknown _1143530215.unknown _1143529947.unknown _1143530178.unknown _1143530188.unknown _1143529992.unknown _1143530139.unknown _1143529835.unknown _1143529936.unknown _1143529816.unknown _1143529496.unknown _1143529625.unknown _1143529705.unknown _1143529743.unknown _1143529754.unknown _1143529699.unknown _1143529565.unknown _1143529601.unknown _1143529398.unknown _1143529466.unknown _1143529425.unknown _1143529433.unknown _1143529445.unknown _1143529404.unknown _1143529370.unknown _1143529376.unknown _1143529350.unknown