基于演化计算的线性规划原对偶内点法中的初始点选取算法

贾伟; 雍龙泉; 李娜; JIA Wei; YONG Longquan; LI Na

2025年5月23日 10:37 星期五

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

基于演化计算的线性规划原对偶内点法中的初始点选取算法 PDF

- ORCID：
贾伟 ¹
- ORCID：
雍龙泉 ^1,2
- ORCID：
李娜 ¹

1. 陕西理工大学数学与计算机科学学院, 汉中, 723001； 2. 陕西省工业自动化重点实验室, 汉中，723001

中图分类号： TP18； O221

最近更新：2020-05-07

DOI：10.16356/j.1005-2615.2020.02.020

摘要

采用原对偶内点法求解线性规划问题，对初始点要求严格。根据初始可行内点的准则，定义了相应的达成度函数，并由达成度函数定义了适应值函数，从而提出了基于演化计算的线性规划原对偶内点法中的初始点选取算法。该算法基于和声搜索演化算法实现，经数值实验测试，结果表明，对所选取测试的典型线性规划问题，算法都能求得大部分问题的初始可行内点。

关键词

线性规划; 原对偶内点法; 初始点选取; 演化计算; 和声搜索

线性规划(Linear programming, LP)是一类重要的数学规划问题，它应用广泛、发展较快、方法较成熟，已成为辅助人们进行科学管理的一种数学方法。到目前为止，求解线性规划的常见方法有：单纯形法及对偶单纯形法^[

1,2,3]，可行内点法及不可行内点算法^{[参考文献 4
百度学术}4,5,6,7,8]。近年来，Bai等^{[参考文献 9
百度学术}9,10]对核函数内点法进行了深入的研究，并取得了系列研究成果；Ye等^{[参考文献 11
百度学术}11,12]把内点算法应用于物流选址及路径优化、库存管理、投资组合优化等问题，并获得了巨大的商业价值。近年来，采用高阶牛顿法求解线性规划也成为一个热点^{[参考文献 13
百度学术}13,14]。

单纯形算法的特点是从一个基可行解旋转到另一个基可行解，从几何上而言就是从可行域的一个顶点迭代到另一个顶点，直至到达最优顶点为止。单纯形方法简单、实用，针对小规模的线性规划求解非常有效。1972年，Klee和Minty举例说明了单纯形算法的时间复杂性是指数型，因此线性规划问题是否存在多项式型有效算法便成了计算机科学家和数学家迫切需要研究的问题。前苏联数学家Khachian在1979年给出了一个求解线性规划的椭球算法，计算复杂性为O(n⁶L²)；印度数学家Karmarkar在1984年给出了线性规划的一个新的多项式算法，其计算复杂性为O(n^3.5L²)， Monteiro 和Adler在1989年给出了求解线性规划一个原对偶内点算法，计算复杂性为O(n^3.5L)，其迭代次数为O(n^0.5L)。这些多项式算法的特点是从可行域内部一个适当的点出发，通过有限次迭代到达最优解，这便是内点算法的思想。

内点算法对初始点的要求比较严格，既要满足原可行性和对偶可行性、又要求在中心路径邻域内。文献[

5]中给出了寻找初始可行内点的方法：构造一个比原问题更为复杂的辅助线性规划(增加了若干复杂参数)，通过求解辅助线性规划而得到原问题的初始内点(事实上，求解辅助线性规划的难度比求解原问题还复杂)。文献[15]中初步给出了原对偶内点法的两个较为简单的线性规划算例，并通过改变参数研究了其收敛过程，但该方法不具有普适性，且对变量较多的线性规划难以找到初始可行内点。

本文依据文献[

5]中的初始可行内点的约束准则，设计了演化计算中种群个体的分量；定义了4个准则的达成度函数；建立了演化计算的适应值函数；给出了基于演化计算选取初始可行内点的算法描述，并采用和声搜索算法来进行实现。通过求解9个线性线性规划问题（包含6个唯一解、2个多个解、1个无解的算例），结果表明，针对存在解的8个线性规划问题，其中7个都找到了初始可行内点。

1 内点算法中初始点选取准则

考虑线性规划及对偶问题

$\begin{matrix} (L P) \{\begin{array}{l} m i n c^{T} x \\ s . t . A x = b x \geq 0 \end{array} \\ (D P) \{\begin{array}{l} m a x b^{T} y \\ s . t . A^{T} y + z = c z \geq 0 \end{array} \end{matrix}$

（1）

式中： $c \in R^{n}, x \in R^{n}, A \in R^{m \times n}, b \in R^{m}, z \in R^{n}, y \in R^{m},$ $m \leq n, r a n k (A) = m$ 。

采用文献[

5,15]中的原对偶内点法求解线性规划时，对初始点的要求较为严格。

要求初始点 $w^{(0)} = (θ, δ, x^{(0)}, y^{(0)}, z^{(0)})$ 及参数 $θ$ 与 $δ$ 满足以下准则：

准‌则‌0 $0 < θ < 0.5$ ； $0 < δ < \sqrt[]{n}$ ； $\frac{θ^{2} + δ^{2}}{2 (1 - θ)} \leq$ $θ (1 - \frac{δ}{\sqrt[]{n}})$ ； (对参数的要求)

准则‌1 $A x^{(0)} = b, x^{(0)} > 0$ ； (原可行性)

准‌则‌2 $A^{T} y^{(0)} + z^{(0)} = c, z^{(0)} > 0$ ; (对偶可行性)

准则‌3 $‖f (w^{(0)}) - μ_{0} e‖ \leq θ μ_{0}$ ； (在中心路径邻域内)

其中： $f (w^{(0)}) = X Z e$ , $X = d i a g (x_{1}, x_{2}, \dots, x_{n})$ , $Z = d i a g (z_{1}, z_{2}, \dots, z_{n})$ ， $e = {(1,1, \dots, 1)}^{T}$ , $μ_{0} = \frac{(x^{(0)})^{T} z^{(0)}}{n}$ ， $‖‖$ 表示2范数。

直接寻找满足上述准则的初始点较为困难，下面采用进化算法，建立适应值函数，利用和声搜索算法(Harmony search, HS)优化适应值函数，从而获得满足条件的初始点。

2 基于演化计算的初始点选取算法

对初始点的选取，若采用Monte Carlo随机产生的方式，是很难得到符合满足上述准则的初始点。演化计算(Evolutionary computation, EC)是一类受自然进化和演变启示而提出的各种计算方法。常见的演化计算有遗传算法(Genetic algorithm, GA)、粒子群优化算法(Particle swarm optimization, PSO)、蚁群算法（Ant colony optimization, ACO)、差分进化算法(Differential evolution, DE)及和声搜索算法等，更多的演化计算详见文献[

16]。演化计算能在可接受的时间内获得问题的近似最优解，且具有鲁棒性强等优势，已被广泛应用于旅行商问题、背包问题、生产调度等优化问题，通过种群内个体之间的学习逼近问题的最优解。

2.1　演化计算中种群个体的设计

采用演化计算选取初始点，首先考虑演化计算种群中个体的构成分量。一种方案可以将初始点 $w^{(0)} = (θ, δ, x^{(0)}, y^{(0)}, z^{(0)})$ 直接作为种群个体，但它们受到线性规划中矩阵A和向量b、c的有关等式约束（即满足原可行性及对偶可行性）。对种群中个体分量的选择，做如下分析。

对非齐次方程组 $A x = b, A \in R^{m \times n}, b \in R^{m},$ $m \leq n, r a n k (A) = m, r = n - m$ 中，设 $η_{0}$ 为其一个特解， $ξ_{1}, ξ_{2}, \dots, ξ_{r}$ 为其导出组 $A x = 0$ 的基础解系，则其通解为 $x = η_{0} + k_{1} ξ_{1} + k_{2} ξ_{2} + \dots + k_{r} ξ_{r}$ ，其中 $k_{1}, k_{2}, \dots, k_{r}$ 为任意常数。当 $k_{1}, k_{2}, \dots, k_{r}$ 取适当值时‌， $x = η_{0} + k_{1} ξ_{1} + k_{2} ξ_{2} + \dots + k_{r} ξ_{r} > 0$ ，从而满足准则1。

利用方程 $A^{T} y + z = c$ 构造 $B Y = c$ ，这里 $B = [A^{T}, I_{n \times n}], Y = [\begin{matrix} y \\ z \end{matrix}]$ 。对 $B Y = c$ ，设 $γ_{0}$ 为其一个特解， $γ_{1}, γ_{2}, \dots, γ_{s}$ 为其导出组 $B Y = 0$ 的基础解系，则其通解为 $Y = γ_{0} + l_{1} γ_{1} + l_{2} γ_{2} + \dots + l_{s} γ_{s}$ ，其中 $s = (m + n) - r a n k (B)$ ， $l_{1}, l_{2}, \dots, l_{s}$ 为任意常数，则 $Y$ 的前 $m$ 个分量就是 $y$ ，而 $Y$ 剩余的 $n$ 个分量就是 $z$ ；同理，当 $l_{1}, l_{2}, \dots, l_{s}$ 取适当的值时，就可使得 $z > 0$ ，及满足准则2。

定义种群优化算法中个体构成分量为 $(θ, δ, k_{1}, k_{2}, \dots, k_{r}, l_{1}, l_{2}, \dots, l_{s})$ 。其中 $0 < θ < 0.5,0 < δ < \sqrt[]{n}$ ， $k_{i} \in R, i = 1,2, \dots, r$ ， $l_{j} \in R, j = 1,2, \dots, s$ ，且个体分量维数为dim=2+r+s。

2.2　适应值函数的定义

在演化算法求解问题的过程中，演化算法依据个体适应值来挑选父代，采用不同的算子来产生新的种群子代，一般子代的适应值优于父代的适应值，在不断的迭代演化过程中，最终得到符合要求的个体子代，求得问题的解。可见，演化计算求解问题，关键问题之一就是将问题转换为一个最优化问题——设计合适的种群个体适应值函数。

为了构造演化计算的适应值函数，对上述4个准则，定义如下几个达成度函数

$f_{0} (w^{(0)}) = \{\begin{matrix} 1 & \frac{θ^{2} + δ^{2}}{2 (1 - θ)} \leq θ (1 - \frac{δ}{\sqrt[]{n}}) \\ 0 & 其他 \end{matrix}$

(2)

$f_{1} (w^{(0)}) = \overset{n}{\sum_{i = 1}} σ (x_{i})$

$σ (x_{i}) = \{\begin{matrix} 1 x_{i} > 0 \\ 0 其他 \end{matrix}$

(3)

$f_{2} (w^{(0)}) = \overset{n}{\sum_{i = 1}} χ (z_{i})$

$χ (z_{i}) = \{\begin{matrix} 1 z_{i} > 0 \\ 0 其他 \end{matrix}$

(4)

$f_{3} (w^{(0)}) = \{\begin{matrix} 1 & ‖f (w^{(0)}) - μ_{0} e‖ \leq θ μ_{0} \\ 0 & 其他 \end{matrix}$

(5)

如果上述条件都满足，则 $f_{0} (w^{(0)}) + f_{1} (w^{(0)}) + f_{2} (w^{(0)}) + f_{3} (w^{(0)}) = 1 + n + n + 1$ ，于是构造差项

$(1 + n + n + 1) - [f_{0} (w^{(0)}) + f_{1} (w^{(0)}) + f_{2} (w^{(0)}) + f_{3} (w^{(0)})]$ ，使其最小。

有了上面的分析，定义演化计算的适应值函数为

$m i n F (w^{(0)}) ≜ (1 + n + n + 1) - [f_{0} (w^{(0)}) + f_{1} (w^{(0)}) + f_{2} (w^{(0)}) + f_{3} (w^{(0)})]$

当且仅当 $F (w^{(0)}) = 0$ 时，则找到可行内点。

2.3　演化计算寻找初始点算法描述

通过演化计算求解对偶内点法的初始点选取问题的算法流程描述如下。

算法1 演化计算寻找可行初始内点算法

Step 1 问题数据A, b, c, m, n初始化。

Step 2 种群演化计算参数初始化，如种群大小popsize等。

Step 3 初始化种群。

Step 4 求种群中每个个体的适应值。

Step 5 选取种群中最优适应值bestfit和对应个体bestx。

Step 6 如果bestfit≤0(满足约束要求)或超过最大迭代次数，则迭代结束；转Step 12。

Step 7 依据种群优化算法，生成新个体。

Step 8 计算新个体的适应值。

Step 9 淘汰适应度差的个体。

Step 10 选取种群中最优适应值bestfit和对应个体bestx。

Step 11 返回 Step 6。

Step 12 如果bestfit≤0，则根据bestx构造可行初始点 $w^{(0)} = (θ, δ, x^{(0)}, y^{(0)}, z^{(0)})$ 。

3 和声搜索算法求解

和声搜索算法是 2001 年韩国学者Geem等人提出的一种新颖的智能优化算法，具有通用、简单、易于实现、群体协同搜索等优点^[

17,18,19,20]，故本文选取了和声搜索作为演化计算的实现实例，来实现算法1，具体步骤描述如下所示。

算法2 和声搜索求解初始点选取算法

Step 1 问题数据A_m×n,b,c初始化，问题维数dim。

Step 2 参数初始化:①和声记忆库的大小HMS；②和声记忆库取值概率HMCR；③音调微调概率PAR；④音调微调带宽b_w；⑤最大创作次数T_max。

Step 3 随机初始化和声记忆库 $H M_{H M S \times d i m}$ 。

Step 4 求种群中每个个体的适应度fitness。

Step 5 选取种群中最优适应值bestfit和其个体bestx。

Step 6 设当前迭代次数t=1。

Step 7 如果bestfit≤0或迭代次数t>T_max，则迭代结束；goto Step 28。

Step 8 i=1

Step 9 while i>dim,则goto Step 22。

Step 10 产生[0,1]之间的随机数rand1。

Step 11 如果 rand1≥HMCR，则goto Step 14。

Step 12 随机产生xnew(i)。

Step 13 Goto Step 20。

Step 14 产生[1,HMS]之间的随机整数d。

Step 15 xnew(i)=HM(d,i)。

Step 16 产生[0,1]之间的随机数rand2。

Step 17 如果 rand2≥PAR，则goto Step 20。

Step 18 产生[-1,1]之间的随机数rand3。

Step 19 xnew(i) = xnew(i)+b_w*rand3。

Step 20 i=i+1。

Step 21 Goto Step 9。

Step 22 计算新个体的适应值newfit=f(xnew)。

Step 23 选择HM中适应值最差的和声worstx和其适应值worstfit。

Step 24 如果newfit优于worstfit,则用newfit、xnew替换worstfit、worstx。

Step 25 选取种群中最优适应值bestfit和其个体bestx。

Step 26 t=t+1。

Step 27 返回 Step 7。

Step 28 如果bestfit<=0，则根据bestx构造可行初始点 $w^{(0)} = (θ, δ, x^{(0)}, y^{(0)}, z^{(0)})$ 。

4 数值实验

4.1　测试问题

对线性规划问题，选取了如下9个线性规划问题，如表1所示。

表1 测试算法的9个线性规划问题

Table 1 Nine linear programming problems tested for the algorithm

问题编号	矩阵A，向量b，向量c	备注
LP01	A=[1 0 0 1/4 -8 -1 9; 0 1 0 1/2 -1 2 -1/2 3; 0 0 1 0 0 1 0]; b=[1.25-82]';c=[1234567]'	唯一解
LP02	A=[2 -1 1 6 -5 -1 0; 1 1 2 1 2 0 -1]; b=[63]';c=[3467100]'	唯一解
LP03	A =[-4 -2 13 -2 1 0 0; 12 -1 1 2 0 1 0; 8 1 -1 -1 0 0 1]; b=[46243]'; c=[2-1-32.5-200]'	唯一解
LP04	A =[-1 2 1 0 0; 3 2 0 1 0; 1 -1 0 0 1]; b=[4143]'; c=[-3-2000]'	多个解
LP05	A =[1 -2 1 0 0; 0 1 -3 1 0; 0 1 -1 0 1]; b=[212]'; c=[0-1-200]'	无解
LP06	A =[ -1 2 -2 3 -3 1 0 1; 1 1 -3 2 -2 0 0 1; 0 0 -2 3 -3 0 1 1]; b=[142]'; c=[43512000]'	多个解
LP07	A =[ 1 1 1 0 0 0; 0 0 0 1 1 1; 1 0 1 0 1 0]; b=[15812]'; c=[523791]'	唯一解
LP08	A =[1 1 2; 2 1 3]; b=[35]'; c=[214]'	唯一解
LP09 (Klee⁃Minty问题,n=3, $δ = 1 / 4$ 时）	A =[1 0 0 1 0 0 0 0 0; 1/4 1 0 0 1 0 0 0 0; 0 1/4 1 0 0 1 0 0 0; 1 0 0 0 0 0 -1 0 0; -1/4 1 0 0 0 0 0 -1 0; 0 -1/4 1 0 0 0 0 0 -1]; b=[111000]’;c=[00-1000000]’	唯一解

4.2　算法参数设置

算法参数设置：①和声记忆库的大小HMS=10；②和声记忆库取值概率HMCR=0.9；③音调微调概率PAR=0.3；④音调微调带宽b_w=0.01；⑤最大创作次数T_max=10 000。

测试问题中，种群个体 $(θ, δ, k_{1}, k_{2}, \dots,$ $k_{r}, l_{1}, l_{2}, \dots, l_{s})$ 的搜索范围分别设为 $0 < θ < 0.5,$ $0 < δ < \sqrt[]{n},$ $- 10 < k_{i} < 10 (i = 1,2, 3, \dots, r),$ $- 10 < l_{j} < 10 (j = 1,2, 3, \dots, s)$ 。

4.3　实验结果数据统计

为了消除随机数对算法的影响，对每个问题，算法独立执行100次，表2中统计出了在100次中成功找到初始可行内点的次数，最小迭代次数、平均迭代次数及平均耗时。N表示没有找到可行内点。

表2 实验测试结果统计表

Table 2 Statistical table of experimental test results

问题编号	LP01	LP02	LP03	LP04	LP05	LP06	LP07	LP08	LP09
成功次数	100	95	0	89	0	86	28	99	97
最小迭代次数	75	98	N	70	N	237	196	12	184
平均迭代次数	408.70	879.03	N	444.92	N	1 997.23	719.64	967.66	1 183.53
平均耗时	0.32	0.63	N	0.22	N	1.76	0.44	0.27	1.16

实验结果表明，对8个存在最优解的线性规划问题，除了LP03外，其他7个问题都找到多个满足条件的初始可行内点，且大部分问题(除了LP03、LP07外)在100次独立运行中，都有超过80%的比例找到初始可行内点，且最小迭代次数和平均的迭代次数都远远小于T_max。

5 应用于Klee‑Minty问题

线性规划问题

$\{\begin{array}{l} m a x x_{n} \\ s . t . 0 \leq x_{1} \leq 1 \\ δ x_{i - 1} \leq x_{i} \leq 1 - δ x_{i - 1} i = 2,3, \dots, n \\ x_{i} \geq 0 i = 1,2, \dots, n \end{array}$

(6)

式中： $0 \leq δ \leq 0.5$ 。该问题特点是对具有 $n$ 个变量的问题，单纯形方法起点取为原点时，需要 $2^{n} - 1$ 次迭代才能找到其最优解，即遍历所有顶点才能到达最优解。

当 $n = 3$ 时，取 $δ = \frac{1}{4}$ ，即LP09，对应的线性规划为

$\{\begin{array}{l} m a x x_{3} \\ s . t . 0 \leq x_{1} \leq 1 \\ \frac{1}{4} x_{1} \leq x_{2} \leq 1 - \frac{1}{4} x_{1} \\ \frac{1}{4} x_{2} \leq x_{3} \leq 1 - \frac{1}{4} x_{2} x_{1}, x_{2}, x_{3} \geq 0 \end{array}$

$\Rightarrow$

$\{\begin{array}{l} m a x x_{3} \\ s . t . x_{1} \leq 1 x_{2} + \frac{1}{4} x_{1} \leq 1 \\ x_{2} - \frac{1}{4} x_{1} \geq 0 x_{3} + \frac{1}{4} x_{2} \leq 1 \\ x_{3} - \frac{1}{4} x_{2} \geq 0 x_{1}, x_{2}, x_{3} \geq 0 \end{array}$

(7)

其最优解为 $x_{1} = 0, x_{2} = 0, x_{3} = 1$ ,最优目标值为1。若初始点取为 $x_{1} = 0, x_{2} = 0, x_{3} = 0$ ，采用单纯形方法，则在可行域上的单纯形迭代过程为 $x^{(0)} \to x^{(1)} \to x^{(2)} \to x^{(3)} \to x^{(4)} \to x^{(5)} \to x^{(6)} \to x^{(7)}$ ，如图1所示。

图1 单纯形法迭代过程示意图

Fig.1 Schematic diagram of simplex iterative process

采用本文的方法，找到一组满足条件的初始可行内点为：

$θ = 0.498 601 355 657 197, δ = 0.388 126 553 590 515$ ‌，

$x^{(0)} = {(0.39,0.57,0.61,0.61,1.35,1.87,1.01,1.86)}^{T}$ ，

$y^{(0)} = {(- 9.47, - 4.06,3.12, - 4.58,2.77)}^{T}$ ，

z⁽⁰⁾=(16.64,11.12,6.27,9.47,4.06,3.12,4.58,2.77)^T。

采用文献[

5,15]中的原对偶内点算法求解，图2给出了部分变量的收敛图及目标函数的收敛图。

图2 原对偶内点算法求解的收敛图及目标函数的收敛图

Fig.2 Convergence graph of the primal-dual interior point algorithm

此外，对于Klee⁃Minty问题，当n分别取5、10、20， $δ = \frac{1}{4}$ 的情况，经程序运行测试，结果数据统计如表3所示。

表3 Klee‑Minty问题测试结果数据统计表

Table 3 Statistical table of test results of Klee‑Minty problem

n	$δ$ =0.25
n	5	10	20
成功次数	100	100	99
最小迭代次数	1 139	14 287	457 666
平均迭代次数	3 657.72	32 781.08	1 039 628
平均耗时	0.118 4	0.910 3	38.658 5

6 结论

线性规划内点法的难点在于初始可行内点要满足多个准则，本文对每一个准则分别构造了相应的达成度函数，建立了演化计算的适应值函数，通过优化该适应值函数获得线性规划原对偶内点算法的初始内点。计算结果表明，对8个存在最优解的线性规划问题，其中7个问题都找到了多个初始可行内点（1个问题没有找到）；并把该方法应用于求解Klee‑Minty问题。

基于演化计算的初始点选取，算法虽具有通用性，且可以找到大部分问题的初始可行内点，但由于演化算法本身具有的随机性，并不能保证算法的每一次运行都能找到满足全部准则的初始可行内点，而且问题规模越大，算法的迭代次数也较多，甚至可能寻找失败。可是，即使算法返回失败的结果，其寻找的初始点也符合准则中大部分要求。后继将对这些情况进行进一步的研究，以期获得更好的结果。

参考文献

潘平奇‌. 线性规划计算(上)[M]. 北京: 科学出版社, 2016. [百度学术]

PAN Pingqi. Linear programming calculation (Volume 1)[M]. Beijing: Science Press, 2016. [百度学术]

潘平奇‌. 线性规划计算(下)[M]. 北京: 科学出版社, 2016. [百度学术]

PAN Pingqi. Linear programming calculation (Volume 2)[M]. Beijing: Science Press, 2016. [百度学术]

张建中, 许绍吉‌. 线性规划[M]. 北京: 科学出版社, 1999. [百度学术]

ZHANG Jianzhong, XU Shaoji. Linear programming [M]. Beijing: Science Press, 1999. [百度学术]

方述诚, 普森普拉‌. 线性优化及扩展理论与算法[M]. 北京: 科学出版社,1994. [百度学术]

MONTEIRO R D C, ADLER I. Interior path following primal-dual algorithms. Part I: Linear programming[J]. Mathematical Programming, 1989, 44(1/2/3): 27-41. [百度学术]

DARVAY Z, TAKÁCS P R. New method for determining search directions for interior-point algorithms in linear optimization[J]. Optimization Letters, 2017(1): 1-18. [百度学术]

KOJIMA M, MEGIDDO N, Mizuno S. Primal-dual infeasible-interior-point algorithm for linear programming[J]. Mathematical Programming, 1993, 61(1/2/3): 263-280. [百度学术]

DANHUA Z, MINGWANG Z. A full-newton step infeasible interior-point algorithm for linear complementarity problem‌[J]. Nonlinear Analysis: Real World Applications, 2011, 12(1): 545-561. [百度学术]

BAI Y Q, LESAJA G, ROOS C, et al. A class of large-update and small-update primal-dual interior-point algorithms for linear optimization‌[J]. Journal of Optimization Theory & Applications, 2008, 138(3): 341-359. [百度学术]

BAI Y Q, GHAMI M E, ROOS C. A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization‌[J]. SIAM Journal on Optimization, 2004,15(1): 101-128. [百度学术]

YE Yinyu. An O(n³L) potential reduction algorithm for linear programming‌[J]. Math Programming, 1991(50): 239-258. [百度学术]

YE Yinyu. On the complexity of approximating a KKT point of quadratic programming‌[J]. Math Programming, 1998(80): 195-211. [百度学术]

FOUTAYENI Y E, BOUANANI H E, KHALADI M. An efficient fifth-order method for linear optimization[J]. Journal of Optimization Theory and Applications, 2016, 170(1): 189-204. [百度学术]

雍龙泉.基于上方一致光滑逼近函数的高阶牛顿法求解线性规划[J].吉林大学学报（理学版）,2019,57(2): 265-270. [百度学术]

YONG Longquan. High order newton method for solving linear programming based on uniform smooth approximation function from above‌[J]. Journal of Jilin University (Science Edition), 2019,57(2): 265-270. [百度学术]

雍龙泉.线性规划的原对偶内点算法数值实验初步[J].科学技术与工程,2007(18): 4576-4579. [百度学术]

YONG Longquan. Primary numerical experiment to the primal-dual interior point algorithm for linear programming[J]. Science Technology and Engineering, 2007(18): 4576-4579. [百度学术]

李士勇, 李研, 林永茂. 智能优化算法与涌现计算[M]. 北京: 清华大学出版社,2019. [百度学术]

LI Shiyong, LI Yan, LIN Yongmao. Intelligent optimization algorithms and emergent computation‌[M]. Beijing: Tsinghua University Press, 2019. [百度学术]

TUO Shouheng, ZHANG Junying, YONG Longquan, et al. A harmony search algorithm for high-dimensional multimodal optimization problems‌[J]. Digital Signal Processing: A Review Journal, 2015,46(11): 151-163. [百度学术]

YONG Longquan, TUO Shouheng, GAO Kai. Harmony search with teaching-learning algorithm for nonnegative linear least square‌[J]. Journal of Interdisciplinary Mathematics, 2017, 20(8): 1661-1677. [百度学术]

雍龙泉, 拓守恒, 史加荣. 约束处理技术及应用[J].计算机科学与探索, 2018,12(6): 1013-1020. [百度学术]

YONG Longquan, TUO Shouheng, SHI Jiarong. Constraint-handling technique and applications‌[J]. Journal of Frontiers of Computer Science and Technology, 2018,12(6): 1013-1020. [百度学术]

黎延海, 拓守恒, 雍龙泉. 动态选择策略的和声教与学混合算法[J]. 计算机应用研究, 2019,36(12): 3679-3684. [百度学术]

LI Yanhai, TUO Shouheng, YONG Longquan. Hybrid algorithm based on harmony search and teaching-learning-based optimization using dynamic selection strategies‌[J]. Application Research of Computers, 2019,36(12): 3679-3684. [百度学术]

请使用 Firefox、Chrome、IE10、IE11、360极速模式、搜狗极速模式、QQ极速模式等浏览器，其他浏览器不建议使用!

基于演化计算的线性规划原对偶内点法中的初始点选取算法 PDF

摘要

关键词

1 内点算法中初始点选取准则

2 基于演化计算的初始点选取算法

2.1 演化计算中种群个体的设计

2.2 适应值函数的定义

2.3 演化计算寻找初始点算法描述