带二元约束非凸三次优化问题的全局充分条件
- 格式：pdf
- 大小：183.60 KB
- 文档页数：4
下载文档原格式
合集下载
非线性规划
1. 非线性规划我们讨论过线性规划,其目标函数和约束条件都是自变量的线性函数。
如果目标函数是非线性函数或至少有一个约束条件是非线性等式(不等式),则这一类数学规划就称为非线性规划。
在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。
由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计,管理科学,风险管理,系统控制,求解均衡模型,以及数据拟合等领域得到越来越广泛的应用。
非线性规划的研究始于三十年代末,是由W.卡鲁什首次进行的，40年代后期进入系统研究，1951年.库恩和.塔克提出带约束条件非线性规划最优化的判别条件,从而奠定了非线性规划的理论基础,后来在理论研究和实用算法方面都有很大的发展。
非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。
无约束问题的求解方法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。
关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。
总的原则是设法将约束问题化为无约束问题；把非线性问题化为线性问题从而使复杂问题简单化。
求解方法有可行方向法、约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。
虽然这些方法都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。
非线性规划举例[库存管理问题] 考虑首都名酒专卖商店关于啤酒库存的年管理策略。
假设该商店啤酒的年销售量为A 箱,每箱啤酒的平均库存成本为H 元,每次订货成本都为F 元。
如果补货方式是可以在瞬间完成的,那么为了降低年库存管理费用,商店必须决定每年需要定多少次货,以及每次订货量。
我们以Q 表示每次定货数量,那么年定货次数可以为QA,年订货成本为Q A F ⨯。
由于平均库存量为2Q,所以,年持有成本为2Q H ⨯,年库存成本可以表示为:Q HQ A F Q C ⨯+⨯=2)( 将它表示为数学规划问题:min Q H Q A F Q C ⋅+⋅=2)( ..t s 0≥Q其中Q 为决策变量,因为目标函数是非线性的,约束条件是非负约束,所以这是带约束条件的非线性规划问题。
一类非凸二次规划问题的全局最优性条件
本 文 主 要 考 虑 如 下 非 凸 二 次 规 划 问题 ：
（ ＱＰ） ｎ ｏ ｚ） １ Ｔ ｍｉｇ （ 一 Ａ
ｓ ￡ ｇ （ 一 ． ． ｚ） １ ｏ ｘ＋ ａ。
ｚ
＋３Ｔ ｉ ｃ≤ ０， １ … ， ２ ａ＋ 一 ，
ｇ ｚ） 百 （ ： １
ｚ＋ Ｔ ＋ ｃ 一 。， ＆ ， 一 ｍ ＋ １， ， ＋ 户 …
本 文定 义集合 Ｌ：
， １ ＼
Ｌ 寺 ｚ ｌ＝ ｉ （ ， ｑ ， ∈ ， ， 卢 Ｒ ｝ 一｛ Ｑ ＋ ｄａ ｑ …， ）ｑ Ｒ ｉ …，，∈ Ｑ ｇ１ 一１
收稿 日期 ：２ １ ５ １ ０ ００—８
作 者简 介 ：张
甲 （ ５ ） 男 ， １ ８ 一 ， 山东 青 岛 人 ， 士 研 究 生 ， ９ 硕 研究 方 向 ： 优 化 理 论 与方 法 。 最
关 键 词 ： 局 最 优 性 ； 一 微 分 ；非 凸 二 次 规 划 ； 次 约 束 全 Ｌ次 二
中 图 分 类 号 ：Ｏ２ １ ２ 文 献 标 志 码 ：Ａ
主 题 分 类 号 ： ０ ３ ９Ｃ ０
１ 问 题
全局优 化是数 学规 划理论 中 的一 个重要 研究 领域 ， 主要 研究 非 线性 函数 在 某个 区域 上全 局最 优 点 的 它 特征 和数值方 法［６， 中全 局最优 性条件 对全 局优化 问题 的研 究 起着 至关重要 的作 用 。 １ 其 ＿ Ｉ 近年来 ， 如何刻 画一个 凸规划 问题 的解方 面 ， 在 特别 是在 可行域 为 凸集 的凸规划 问题 的研 究方 面 已经取 得 了许多进 展 。在如何 刻 画一个非 凸规划 问题 的全局最 优 解方 面 ， 已经 得到 了利 用 求非 凸优化 问 题全 局最 优性 条件 的 Ｌ 次微 分方法 建立 了带二次 约束 二次极小 化 问题 的全 局优 化 拉格 朗 日乘 子条 件 ， 一 ］ 而更 多 的是 在几 种特殊 的非 凸规划 问题 的全局 最优解 的刻 画方面有 一定 的进展 ９， 吸引 了许 多学者 的关 注 。本 文利 － 也 ｌ 用 Ｚ ．Ｙ．ｗｕ等人提 出 的方 法ｕ 研究 了一种 新 的非凸二 次规划 问题 的全局 最优性 充分条 件 。
（ ＱＰ） ｎ ｏ ｚ） １ Ｔ ｍｉｇ （ 一 Ａ
ｓ ￡ ｇ （ 一 ． ． ｚ） １ ｏ ｘ＋ ａ。
ｚ
＋３Ｔ ｉ ｃ≤ ０， １ … ， ２ ａ＋ 一 ，
ｇ ｚ） 百 （ ： １
ｚ＋ Ｔ ＋ ｃ 一 。， ＆ ， 一 ｍ ＋ １， ， ＋ 户 …
本 文定 义集合 Ｌ：
， １ ＼
Ｌ 寺 ｚ ｌ＝ ｉ （ ， ｑ ， ∈ ， ， 卢 Ｒ ｝ 一｛ Ｑ ＋ ｄａ ｑ …， ）ｑ Ｒ ｉ …，，∈ Ｑ ｇ１ 一１
收稿 日期 ：２ １ ５ １ ０ ００—８
作 者简 介 ：张
甲 （ ５ ） 男 ， １ ８ 一 ， 山东 青 岛 人 ， 士 研 究 生 ， ９ 硕 研究 方 向 ： 优 化 理 论 与方 法 。 最
关 键 词 ： 局 最 优 性 ； 一 微 分 ；非 凸 二 次 规 划 ； 次 约 束 全 Ｌ次 二
中 图 分 类 号 ：Ｏ２ １ ２ 文 献 标 志 码 ：Ａ
主 题 分 类 号 ： ０ ３ ９Ｃ ０
１ 问 题
全局优 化是数 学规 划理论 中 的一 个重要 研究 领域 ， 主要 研究 非 线性 函数 在 某个 区域 上全 局最 优 点 的 它 特征 和数值方 法［６， 中全 局最优 性条件 对全 局优化 问题 的研 究 起着 至关重要 的作 用 。 １ 其 ＿ Ｉ 近年来 ， 如何刻 画一个 凸规划 问题 的解方 面 ， 在 特别 是在 可行域 为 凸集 的凸规划 问题 的研 究方 面 已经取 得 了许多进 展 。在如何 刻 画一个非 凸规划 问题 的全局最 优 解方 面 ， 已经 得到 了利 用 求非 凸优化 问 题全 局最 优性 条件 的 Ｌ 次微 分方法 建立 了带二次 约束 二次极小 化 问题 的全 局优 化 拉格 朗 日乘 子条 件 ， 一 ］ 而更 多 的是 在几 种特殊 的非 凸规划 问题 的全局 最优解 的刻 画方面有 一定 的进展 ９， 吸引 了许 多学者 的关 注 。本 文利 － 也 ｌ 用 Ｚ ．Ｙ．ｗｕ等人提 出 的方 法ｕ 研究 了一种 新 的非凸二 次规划 问题 的全局 最优性 充分条 件 。
优化理论
有限维空间的优化理论与算法
引言
刘红英 数学与系统科学学院
1.1 数学描述与例子
• 目 标：系统性能的一种“量的度量”(利润、时间、 势能)－－任何数量或某些量的组合－－数
• 变 量：目标所依赖的系统的“某些可控的特征” • 约束条件：经常变量以某种方式受限制(分子中电子密度
的量、贷款利率的量，不能是负的)
故必要条件即对所有 p，有
等价地
(一阶条件)，G*半正定(二阶条件)
稳定点/驻点(stationary point)：使得 g(x*)=0 的 x*
局部极小点的充分条件
定理. x*是严格局部极小点的充分条件是 ，G*正定.
例.考虑Rosenbrock函数
在x*=(1, 1)处 严格局部极小点－全局极小点 充分非必要：
优化问题的一般模型－－数学规划问题
一个小例子
• 可行域/可行集 • 最优解/解 • 图解法
1
优化建模(modeling)： 识别出给定问题的目标、变量和约束的过程。
• 建立恰当模型：第一步、最重要的一步(太简单－不能给 实际问题提供有用的信息；太复杂－不易求解)
• 选择特定算法：很重要--决定求解速度及质量(无通用优化 算法，有求解特定类型优化问题的算法)
积极(约束指标)集 x2
x*
x1 Lagrange函数：
一阶条件：KKT条件
正则性假设1：
定理(一阶条件). 若 x* 是局部极小点且在 x* 处正则性假设1成立，则存在
Lagrange乘子 使得
满足
◎ Karush-Kuhn-Tucker条件, KKT条件/KKT点
局部极小的条件－充分条件(续)
定理.可微凸函数的稳定点是全局极小点
kkt条件求解凸问题的充分条件
kkt条件求解凸问题的充分条件
在凸优化问题中，KKT条件是一个重要的充分条件，用于确定一个解是否为最优解。
凸优化问题是指目标函数和约束条件都是凸函数的优化问题。
当一个凸优化问题满足KKT条件时，该问题存在一个最优解，并且该最优解是满足KKT条件的点。
具体来说，KKT条件包括以下五个方面：
1. 互补松弛条件：对于约束优化问题，如果一个变量在某个约束下被限制为非负，则该变量在最优解处应等于0。
即对于每个约束$g_j(x) \leq 0$，若$x_i > 0$，则$g_j(x) = 0$；若$x_i < 0$，则$g_j(x) > 0$。
2. 梯度条件：最优解处的梯度等于零，即$\nabla f(x) = 0$。
3. 拉格朗日乘子条件：对于每个约束$g_j(x) \leq 0$，存在一个拉格朗日乘子$\lambda_j$，使得$\lambda_j g_j(x) = 0$。
4. 非负性条件：所有拉格朗日乘子都应该非负，即$\lambda_j \geq 0$。
5. 鞍点条件：对于每个约束$g_j(x) \leq 0$，存在一个拉格朗日乘子$\lambda_j$，使得$\lambda_j = \min\{\lambda_k g_k(x)\}$。
因此，当一个凸优化问题满足KKT条件时，我们可以确定该问题存在最优解，并且可以使用这些条件来确定最优解的性质和位置。
最优性条件是指优化问题
智能优化算法
如遗传算法、粒子群算法等，通过模 拟自然界中的优化现象，寻找全局最 优解。
05 数值计算方法和实现技术
梯度下降法、牛顿法等经典数值计算方法回顾
梯度下降法
一种迭代优化算法，用于求解机器学习和深度学习中的优化问题。通过沿着目 标函数梯度的反方向进行参数更新，逐步逼近最优解。
牛顿法
一种在实数域和复数域上近似求解方程的方法。使用函数切线的斜率来寻找方 程的根，具有收敛速度快、精度高等优点。但需要计算二阶导数，计算量较大。
迭代终止条件
设定合适的迭代终止条件，如梯度范数小于 给定阈值等。
约束非凸优化问题处理方法
罚函数法
将约束条件转化为罚函数项，加入到 目标函数中，从而将约束问题转化为 无约束问题求解。
乘子法
引入拉格朗日乘子，构造拉格朗日函 数，通过求解拉格朗日函数的极值点 得到原问题的最优解。
投影梯度法
在每次迭代中，将搜索方向投影到可 行域内，以保证迭代点始终满足约束 条件。
启发式搜索算法在求解复杂问题时应用
遗传算法
一种模拟生物进化过程的优化算法， 通过选择、交叉、变异等操作来搜索 最优解。适用于求解离散、非线性、 多峰等复杂优化问题。
模拟退火算法
一种基于物理退火过程的优化算法，通 过模拟高温物体降温过程来搜索全局最 优解。具有跳出局部最优解的能力，适 用于求解大规模组合优化问题。
优化问题数学模型
01
02
03
目标函数
描述优化问题的目标，通 常是一个关于决策变量的 函数，需要最大化或最小 化。
约束条件
对决策变量的限制条件， 包括等式约束和不等式约 束。
决策变量
在优化问题中需要确定的 未知量，通常是多维的。
约束问题最优化方法
* * T * * * T * (1* , 2 ,, m ) 和 * ( 1 , 2 ,, m ) 使 Kuhn-Tucker 条 件 (9-6) 成 立 ，
且 对 满 足 下 述 (9-7) 、(9-8) 、(9-9) 三 条 件 的 任 意 非 零 向 量 z 有 (9-10) 成 立 ， 则 x* 是 问 题 (9-1) 的 严 格 局 部 极 小 点 ．
(1)
H ，定义集合
I ( x (1) ) {i g i ( x (1) ) 0,1 i l}
(1) x 为 点所有起作用约束的下标的集合．
可行下降方向的判定条件
g j ( x ) d 0 ( j I ( x ))
(1) T (1)
f ( x
(1)
) d 0
T
*
* j
必为零，在运用 K-T 条件求 K-T 点时，利用这一点可 以大大 地简化计算，另 外还要把约束条 件都加上．
2．求满足Kuhn-Tucker条件的点
例 9-1 求下列非线性规划问题的 Kuhn-Tucker 点．
min f ( x) 2x 2x1x2 x 10x1 10x2
线性无关．
若
* x* 是 (9-1) 的局部最优解，则比存在 * (1* , 2 ,, l* )T 和向量
* * T * (1* , 2 ,, m ) ，使下述条件成 立：
l m * * * * * f ( x ) j g j ( x ) i hi ( x ) 0 j 1 i 1 * * j g j ( x ) 0, j 1, 2, , l * j 0, i 1, 2, , l
2 1 2 2
且 对 满 足 下 述 (9-7) 、(9-8) 、(9-9) 三 条 件 的 任 意 非 零 向 量 z 有 (9-10) 成 立 ， 则 x* 是 问 题 (9-1) 的 严 格 局 部 极 小 点 ．
(1)
H ，定义集合
I ( x (1) ) {i g i ( x (1) ) 0,1 i l}
(1) x 为 点所有起作用约束的下标的集合．
可行下降方向的判定条件
g j ( x ) d 0 ( j I ( x ))
(1) T (1)
f ( x
(1)
) d 0
T
*
* j
必为零，在运用 K-T 条件求 K-T 点时，利用这一点可 以大大 地简化计算，另 外还要把约束条 件都加上．
2．求满足Kuhn-Tucker条件的点
例 9-1 求下列非线性规划问题的 Kuhn-Tucker 点．
min f ( x) 2x 2x1x2 x 10x1 10x2
线性无关．
若
* x* 是 (9-1) 的局部最优解，则比存在 * (1* , 2 ,, l* )T 和向量
* * T * (1* , 2 ,, m ) ，使下述条件成 立：
l m * * * * * f ( x ) j g j ( x ) i hi ( x ) 0 j 1 i 1 * * j g j ( x ) 0, j 1, 2, , l * j 0, i 1, 2, , l
2 1 2 2
最优化方法4-1第四章 约束最优化方法-KKT条件
（I） x*为问题的局部最优解且 I*={i| c i (x*)=0, 1≤i≤m };
(II) f(x)和 c i (x)（i∈I*）在 x*点可微；
（III）c i (x)（i∈I\ I*）在 x*点连续
则 S={p∈Rn | ▽f(x*)Tp<0}
与 G={ p∈Rn |▽c i(x* )Tp>0, i∈I*} 的交是空集，
（iii）▽ci(x*)(i=1,2,…,l)线性无关；
则存在一组不全为零的实数 1*… l*使得
l
▽f(x*)- i *▽c i(x*)=0 1
定义 n+l 元函数：
l
L(x, )=f(x)- Tc(x)=f(x)- ici(x) i1 为 lagrange 函数，
1
1 2
x1 x2 1 0
的 KT 点为 x* (0, 3)T,相应乘子为* (1 ,0)T。
6
例 2：验证(2,1)T 为下面约束优化问题的 K-T 点.
min
f ( x1 , x2 ) ( x1 3)2 ( x2 2)2
恰好给出等式约束问题的一阶必要条件
及 c i(x*)=0，i=1, …,l
点（X*, *）称为 lagrange 函数 L（x, ）的驻点。
几何意义是明显的：考虑一个约束的情况：
-▽f(x*)
-▽f(x ) x
▽c(x )
c(x)
▽c(x*)
这里 x* 是局部最优解，
▽f(x*)与▽c(x*) 共线，
称 为 lagrange 乘子向量。
lagrange 函数的梯度为
▽L(x, )=(▽xL,▽ L)T
(II) f(x)和 c i (x)（i∈I*）在 x*点可微；
（III）c i (x)（i∈I\ I*）在 x*点连续
则 S={p∈Rn | ▽f(x*)Tp<0}
与 G={ p∈Rn |▽c i(x* )Tp>0, i∈I*} 的交是空集，
（iii）▽ci(x*)(i=1,2,…,l)线性无关；
则存在一组不全为零的实数 1*… l*使得
l
▽f(x*)- i *▽c i(x*)=0 1
定义 n+l 元函数：
l
L(x, )=f(x)- Tc(x)=f(x)- ici(x) i1 为 lagrange 函数，
1
1 2
x1 x2 1 0
的 KT 点为 x* (0, 3)T,相应乘子为* (1 ,0)T。
6
例 2：验证(2,1)T 为下面约束优化问题的 K-T 点.
min
f ( x1 , x2 ) ( x1 3)2 ( x2 2)2
恰好给出等式约束问题的一阶必要条件
及 c i(x*)=0，i=1, …,l
点（X*, *）称为 lagrange 函数 L（x, ）的驻点。
几何意义是明显的：考虑一个约束的情况：
-▽f(x*)
-▽f(x ) x
▽c(x )
c(x)
▽c(x*)
这里 x* 是局部最优解，
▽f(x*)与▽c(x*) 共线，
称 为 lagrange 乘子向量。
lagrange 函数的梯度为
▽L(x, )=(▽xL,▽ L)T
带LMI约束的混合整数二次规划问题的全局最优性条件
Ｆ ｂ ｅ ．，２ １ ０１ Ｖｏ ＿ Ｏ Ｎｏ Ｉ３ ．１
第３ ０卷
第 １ 期
带 Ｌ 约 束 的 混 合 整 数 二 次 规 划 问 题 的 ＭＩ 全 局 最 优 性 条 件
秦 帅 ， 云峰 ， 祁 李
（ 庆师范大学 重
倩， 祁艳 妮
４ ０４ ） ００ ７
数 学 学 庆 文 理 学 院 学 报 （自然 科 学 版 ） Ｊｕ ａ ｏ ｈｎｑｎ ｎ ｅｓｙｏ ｒ ｎ ｃｅｃｓ（ ａ ｒｌ ｃ ｎｅＥ ｉｏ ） ｏｒ ｌ ｆＣ ｏ ｇｉｇＵ ｉ ｒｉ ｆＡ ｔａ ｄＳ ｉ ｅ Ｎ ｔ ａ Ｓｉ ｃ ｄｔ ｎ ｎ ｖ ｔ ｓ ｎ ｕ ｅ ｉ
对 角元素 为 ａ 一， 的对 角矩 阵 ， Ｌ 设 为所 有定 义在 Ｒ 上一 些实 值 函数 的集合 ．
定义 １ （ 一次微 分 ）
且Ｐ ＜ｑ 对 于 任何 ｅ∈ Ｎ 都 成 立．ａ ， ＝ （ ａ，
…
，
ａ ）， ∈Ｓ ， ∈Ｓ， ＝０ １ … ， 且 Ｓ 是 Ａ “Ｆ ， ， ｎ．
［ 收稿 日期】 ００一ｌ ２ ２１ １— １
［ 作者简介］ 秦帅 （９ ９一） 男 ， １７ ， 山东滕州人 ， 硕士 ， 主要从 事最优化理论与算法方面的研究
２ ９
设 － Ｒ“ Ｒ且 ０∈ Ｒ ， ∈ ， ｌ ）≥ 厂 一 ： 若 厂 （
／ 。 ）十Ｚ （ ）一￡ 。 ， ∈Ｒ ， ４ ｆ 厂 （ ）Ｖ 贝 称 为Ｉ在 。 处 的 一次微 分．
其 中 Ｚ ∈Ｓ 令 ，
： ＝
｛ Ｑ ：＝ｉ ｝ Ｑ ｄ（ ａ ｇ
对于（ ＭＭＩ ， Ｑ） 令
∈ Ｒ ）
命 题 ３ 设 ∈ ， 且 ＝Ａ— （ ｚ）＋（ Ａ
带约束的非线性优化问题解法小结
(1)带约束的非线性优化问题解法小结考虑形式如下的非线性最优化问题(NLP):min f(x)「g j (x )“ jI st 彳 g j (x)=O j L其 中， ^(x 1,x 2...x n )^ R n， f : R n > R ， g j :R n > R(j I L) ， I 二｛1,2,…m ｝， L ={m 1,m 2...m p}。
上述问题(1)是非线性约束优化问题的最一般模型，它在军事、经济、工程、管理以 及生产工程自动化等方面都有重要的作用。
非线性规划作为一个独立的学科是在上世纪 50年 代才开始形成的。
到70年代，这门学科开始处于兴旺发展时期。
在国际上，这方面的专门性 研究机构、刊物以及书籍犹如雨后春笋般地出现，国际会议召开的次数大大增加。
在我国， 随着电子计算机日益广泛地应用，非线性规划的理论和方法也逐渐地引起很多部门的重视。
关于非线性规划理论和应用方面的学术交流活动也日益频繁，我国的科学工作者在这一领域 也取得了可喜的成绩。
到目前为止，还没有特别有效的方法直接得到最优解，人们普遍采用迭代的方法求解： 首先选择一个初始点，利用当前迭代点的或已产生的迭代点的信息，产生下一个迭代点，一 步一步逼近最优解，进而得到一个迭代点列，这样便构成求解( 1)的迭代算法。
利用间接法求解最优化问题的途径一般有：一是利用目标函数和约束条件构造增广目标 函数，借此将约束最优化问题转化为无约束最优化问题，然后利用求解无约束最优化问题的 方法间接求解新目标函数的局部最优解或稳定点，如人们所熟悉的惩罚函数法和乘子法；另 一种途径是在可行域内使目标函数下降的迭代点法，如可行点法。
此外，近些年来形成的序 列二次规划算法和信赖域法也引起了人们极大的关注。
在文献［1］中，提出了很多解决非线性 规划的算法。
下面将这些算法以及近年来在此基础上改进的算法简单介绍一下。
1. 序列二次规划法序列二次规划法，简称SQ 方法.亦称约束变尺度法。
约束优化方法
约束优化方法
约束优化方法概述 约束优化问题的最优解及其必要条件 约束坐标轮换法 约束随机方向法 复合形法 惩罚函数法
教学要求： 1、掌握约束优化局部最优解的必要条件。 2、掌握复合形法得原理及程序设计。 3、掌握内点法和外点法的惩罚函数的构造原理及 程序设计。
约束优化方法概述
可行性：迭代点必须在约束条件所限制的可行域内，即满足 gu(x)0, u=1,2,…,p 适用性：当前迭代点的目标函数值较前一点是下降的，即 满 F(xk+1)<F(xk)
2、间接法
该方法可以求解等式约束优化问题和一般约束优化问题。 其基本思想是将约束优化问题通过一定的方法进行改变，将 约束优化问题转化为无约束优化问题，再采用无约束优化方 法进行求解。如：惩罚函数法
5.2 约束优化问题极小点的条件
约束优化问题极小点的条件，是指在满足约束条 件下，目标函数局部极小点的存在条件。 约束问题最优解的存在条件有两种：一是极小点在 可行域内部，二是极小点在可行域的一个或几个边界交 汇处。 5.2.1 不等式约束问题解的必要条件 第一种情况：如图所示， g1(x*)=0， g2(x*)>0， g3(x*)>0。所以g1(x)为起作用约束， g2(x)、 g3(x)为不 起作用约束。 由于约束最优点是目标函数与约束g1(x)边界的切点， 故目标函数与约束函数的梯度必共线，而且方向一致。
λu μv称为拉格朗日乘子 上式也称为约束优化问题局部最优点的必要条件。
在迭代点 为
处展开式的形式
一般情况下，其作用约束数J不大于问题的维数 其中 是待定系数矢量
……
解上式，得一组λj（j=1，2……J），如果λj（j=1， 2……J）均为非负，标志 满足K-T条件。该条件 是 为极小点的必要条件。 如果点 是最优点，则必须满足K-T条件； 反之，满足K-T条件的点则不一定是约束最优点。 只有当目标函数是凸函数，约束构成的可行域是凸集 时，则满足K-T条件的点 是全局极小点的必要而充 分条件。
约束优化方法概述 约束优化问题的最优解及其必要条件 约束坐标轮换法 约束随机方向法 复合形法 惩罚函数法
教学要求： 1、掌握约束优化局部最优解的必要条件。 2、掌握复合形法得原理及程序设计。 3、掌握内点法和外点法的惩罚函数的构造原理及 程序设计。
约束优化方法概述
可行性：迭代点必须在约束条件所限制的可行域内，即满足 gu(x)0, u=1,2,…,p 适用性：当前迭代点的目标函数值较前一点是下降的，即 满 F(xk+1)<F(xk)
2、间接法
该方法可以求解等式约束优化问题和一般约束优化问题。 其基本思想是将约束优化问题通过一定的方法进行改变，将 约束优化问题转化为无约束优化问题，再采用无约束优化方 法进行求解。如：惩罚函数法
5.2 约束优化问题极小点的条件
约束优化问题极小点的条件，是指在满足约束条 件下，目标函数局部极小点的存在条件。 约束问题最优解的存在条件有两种：一是极小点在 可行域内部，二是极小点在可行域的一个或几个边界交 汇处。 5.2.1 不等式约束问题解的必要条件 第一种情况：如图所示， g1(x*)=0， g2(x*)>0， g3(x*)>0。所以g1(x)为起作用约束， g2(x)、 g3(x)为不 起作用约束。 由于约束最优点是目标函数与约束g1(x)边界的切点， 故目标函数与约束函数的梯度必共线，而且方向一致。
λu μv称为拉格朗日乘子 上式也称为约束优化问题局部最优点的必要条件。
在迭代点 为
处展开式的形式
一般情况下，其作用约束数J不大于问题的维数 其中 是待定系数矢量
……
解上式，得一组λj（j=1，2……J），如果λj（j=1， 2……J）均为非负，标志 满足K-T条件。该条件 是 为极小点的必要条件。 如果点 是最优点，则必须满足K-T条件； 反之，满足K-T条件的点则不一定是约束最优点。 只有当目标函数是凸函数，约束构成的可行域是凸集 时，则满足K-T条件的点 是全局极小点的必要而充 分条件。
第2章 优化方法的数学基础
X ∈ D 对满足 ,
F ( X ) ( X X * ) ≥ 0
*
T
注意: 注意:
不论是无约束或有约束的优化问题,在实际应用中, 不论是无约束或有约束的优化问题,在实际应用中,要证明一个 优化问题是否为凸规划,一般比较困难, 优化问题是否为凸规划,一般比较困难,有时甚至比求解优化问题本 身还要麻烦.尤其对一些工程问题,由于其数学模型的性态都比较复 身还要麻烦.尤其对一些工程问题, 杂,更难实现.因此,在优化设计的求解中,就不必花精力进行求证, 更难实现.因此,在优化设计的求解中,就不必花精力进行求证, 而通常是从几个初始点出发,找出几个局部最优解, 而通常是从几个初始点出发,找出几个局部最优解,从中选择目标函 数值最好的解. 数值最好的解.
2 2
设: 则有
cos θ1 s≡ 为单位向量. 为单位向量. cos θ 2 F = F ( x0 )T s = F ( x0 ) cos(F , s ) x s 0
梯度方向是函数值变化最快的方向,而梯度的模 梯度方向是函数值变化最快的方向, 就是函数变化率的最大值 .
x2 x0
-f(x0) 最速下降方向 下降方向 变化率为零的方向 上升方向 f(x 0) 最速上升方向
凸规划的一些性质: 凸规划的一些性质: 1)可行域 D = X g j ( X ) ≤ 0
{
j = 1, 2, , m
}
为凸集; 为凸集;
2)凸规划问题中的任何局部最优解都是全局最优解; 凸规划问题中的任何局部最优解都是全局最优解; 为凸规划问题 最优解的充分必要条件 规划问题的 可微, 3 ) 若 F ( X ) 可微 , 则 X* 为凸规划问题的 最优解的充分必要条件 为: 对任意
0
凸目标函数,非凸约束
凸目标函数,非凸约束
凸目标函数和非凸约束是优化问题中的两个重要概念。
凸目标函数是指函数的图像是一个凸集，即对于任意两点，连接它们的线段都在函数图像的下方。
凸函数具有一些很好的性质，比如局部最小值也是全局最小值，这使得优化问题变得相对简单。
非凸约束则是指函数的图像不是凸集。
这种情况下，优化问题通常会变得更加复杂，因为局部最小值不一定是全局最小值。
在优化问题中，我们通常会尽量选择凸目标函数和凸约束，因为这样可以简化问题并更容易找到全局最优解。
然而，在某些情况下，我们可能无法避免使用非凸函数或非凸约束。
在这种情况下，我们需要使用一些特殊的方法来处理这些非凸问题，比如梯度下降法、牛顿法等。
13约束最优化条件KTT
g3(x) 0 ●
D
●
g1(x) 0
g2(x) 0
●
如图：观察不同点处 的有效约束
D内的点没有有效约束 仅边界上的点存在有 效约束
总结：x处的有效约束是指该约束对该点处的可行方 向起限制作用, 反之无效约束即对该点处的可行方向 没有任何影响.不同的可行点一般有不同的有效约束.
所有存在有效约束的点构成可行域的边界.
？？？ 约束品性对研究约束问题的最优性条件非常重要
约束品性（约束规格）
SFD(x*,D) LFD(x*,D)
最优解 x*
KKT点 x*
基本概念
定义9.1.1 设x D, d Rn.若存在数 0, 使得
x d D, (0, ],
则称d是D在x处的一个可行方向. 记x处所有可行方向的集合为FD( x, D)
xk x* kdk x* 其中k 0, dk d. 所以,当k充分大时, xk N (x*).
故 f (x*) f (xk ) f (x* kdk ) f (x*) kf (x*)T dk o(|| kdk ||)
在上式两端除以k , 然后令k 0, 取极限即可得
f (x* )T d 0
例9.1.1
考察如下约束问题：
x2
min f ( x) x12 x22
x2 3
x1 2x2 8
s.t. x1 2x2 8 0 x1 4 0 x2 3
x1 0 可行域
O
●
x(0) (0, 0)
x2 0
● x(1) (4, 2) x1 4 x1
标 g1(x) 8 - x1 - 2x2 0
定义9.1.4 设x D, 若向量组
{ gi (x),h j (x),i I (x), j E } 线性无关, 则称在x处线性无关约束品性成立, 简称为在 x处LICQ (Libear independence ConstraintQualification) 成立.
人工智能机器学习技术练习(习题卷8)
人工智能机器学习技术练习(习题卷8)第1部分：单项选择题，共62题，每题只有一个正确答案,多选或少选均不得分。
1.[单选题]基于二次准则函数的H-K算法较之于感知器算法的优点是()?A)计算量小B)可以判别问题是否线性可分C)其解完全适用于非线性可分的情况答案:B解析:2.[单选题]构建回归树的时间复杂度最重要的因素是()A)特征中类别的个数B)label列值域C)样本总量答案:A解析:3.[单选题]()是指为最小化总体风险,只需在每个样本上选择能使特定条件风险最小的类别标记。
A)支持向量机B)间隔最大化C)线性分类器D)贝叶斯判定准则答案:D解析:4.[单选题]下列选择 Logistic回归中的 One-Vs-All方法中,()是真实的。
A)我们需要在n类分类问题中适合n个模型B)我们需要适合n-1个模型来分类为n个类C)我们需要只适合1个模型来分类为n个类D)以上答案都不正确答案:A解析:如果存在n个类,那么n个单独的逻辑回归必须与之相适应,其中每个类的概率由剩余类的概率之和确定。
5.[单选题](__)不属于相关分析。
A)正相关B)负相关C)线性相关D)误差相关答案:D解析:6.[单选题]移动运营商对客户进行细分,设计套餐和营销活动可以使用下面哪种机器学习方法( )。
A)贝叶斯分类器B)关联方法C)聚类算法D)多层前馈网络7.[单选题]下面是三个散点图(A,B,C,从左到右)和和手绘的逻辑回归决策边界。
alt="" >上图中哪一个显示了决策边界过度拟合训练数据?A)AB)BC)CD)这些都没有答案:C解析:由于在图3中,决策边界不平滑,表明其过度拟合数据。
8.[单选题]半监督学习包括。
A)主动学习B)回归学习C)聚类学习D)直推学习答案:D解析:9.[单选题]在统计语言模型中,通常以概率的形式描述任意语句的可能性,利用最大相似度估计进行度量,对于一些低频词,无论如何扩大训练数据,出现的频度仍然很低,下列哪种方法可以解决这一问题()A)一元切分B)一元文法C)数据平滑D)N元文法答案:C解析:10.[单选题]将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?A)频繁模式挖掘B)分类和预测C)数据预处理D)数据流挖掘答案:C11.[单选题]图像数据分析的常用方法不包括（ ）A)图像变换B)图像编码和压缩C)图像增强和复原D)图像数据采集答案:D解析:12.[单选题]下列关于数据的说法，不正确的是（）A)数据的类别有多种多样B)数据库中的一列代表一个特征C)一组数据平均值不会受异常值影响D)数据点之间的距离满足d_ij+d_jk≥d_ik答案:C解析:13.[单选题]关于ZooKeeper的说法不正确是()A)采用层次化的数据结构B)采用类似于LINUX命令进行数据访问C)具备临时节点和永久节点D)永久节点会随客户端会话的结束而结束其生命周期答案:D解析:14.[单选题]下面数据结构能够支持随机的插入和删除操作、并具有较好的性能的是A)链表和哈希表B)数组和链表C)哈希表和队列D)堆栈和双向队列答案:A解析:15.[单选题]下面关于数据科学与统计学的关系描述不正确的有(__)。
约束优化算法PPT课件
令
，上述方程组即
给定初始点
，利用上面两式进行迭代
解等式约束问题的－ Lagrange-Newton法
定理 假设 x*是等式约束问题的满足二阶充分条件的局
部极小点, 且rank (A*)=m， 是惟一的Lagrange乘子.
则当
充分接近
时，Lagrange-Newton
法有定义，且由该方法产生的序列
二次
特点：在 x1=1 处不可微；进行整理，得
结论：对任一
罚函数的解与原问题的相同
第6讲 约束优化问题的算法
优化理论
数学与系统科学学院
精确罚函数法(续)
⊙ 先验确定惩罚参数很难；通常是计算一系列子问题， 并在计算过程中调整该参数
⊙ 与逐步二次规划法有密切联系；SQP的线搜索实现中 通常以 惩罚函数作为评价函数
则s*=0 (x*)是下列问题的惟一最优解
第6讲 约束优化问题的算法
优化理论
数学与系统科学学院
基本/局部逐步二次规划法(续)
算法9.2 基本SQP法
第6讲 约束优化问题的算法
优化理论
数学与系统科学学院
基本/局部逐步二次规划法(续)
例
第6讲 约束优化问题的算法
优化理论
数学与系统科学学院
基本/局部逐步二次规划法(续)
优化理论
数学与系统科学学院
二次惩罚函数法(续)
条件数
第6讲 约束优化问题的算法
优化理论
数学与系统科学学院
精确罚函数法 SQP中常用*****
一定条件下，
存在
，当
特点：不需要
时，求解 ；是非光滑的！
避免了无约束优化问题的病态性！
例
即可
二次等式约束非凸二次规划问题的全局最优性条件
参考文献
1.Jeyakumar,V.,Rubinov,A.M.,Wu,Z.Y.:Non-convex Quadratic Minimiation Problems with Quadratic Constraints:Global Optimality Conditions[J]. Math.Prog.,ser,A DOI 10,1007/S10107-006-0012-5. 2. Bar-on, J. R., and Grasse, K. A., Global Optimization of a Quadratic Functional with Quadratic Equality Constraints[J]. Journal of Optimization Theory and Applications,Vol. 82, No. 2, pp. 379-386, 1994. 3. Bar-on, J. R., and Grasse, K. A., :Global Optimization of a Quadratic Functional with Quadratic Equality Constraints[J], Part 2, Journal of Optimization Theory and Applications, Vol. 93, No. 3, pp. 547-556, 1997. 4. Ye Y Y.:Approximation quadratic Programming with Bound and Quadratic Constraints[J]. Math.Prog, 1999,84:216-226. 5.Shi Kuiran and Wang Cheng:Ona Class of Quadratic Programming Problem with Equality Constraints[J].Jonrnal of NanJing University Mathematical Biquarterly Vol.23,No.1 May,2006.
1.Jeyakumar,V.,Rubinov,A.M.,Wu,Z.Y.:Non-convex Quadratic Minimiation Problems with Quadratic Constraints:Global Optimality Conditions[J]. Math.Prog.,ser,A DOI 10,1007/S10107-006-0012-5. 2. Bar-on, J. R., and Grasse, K. A., Global Optimization of a Quadratic Functional with Quadratic Equality Constraints[J]. Journal of Optimization Theory and Applications,Vol. 82, No. 2, pp. 379-386, 1994. 3. Bar-on, J. R., and Grasse, K. A., :Global Optimization of a Quadratic Functional with Quadratic Equality Constraints[J], Part 2, Journal of Optimization Theory and Applications, Vol. 93, No. 3, pp. 547-556, 1997. 4. Ye Y Y.:Approximation quadratic Programming with Bound and Quadratic Constraints[J]. Math.Prog, 1999,84:216-226. 5.Shi Kuiran and Wang Cheng:Ona Class of Quadratic Programming Problem with Equality Constraints[J].Jonrnal of NanJing University Mathematical Biquarterly Vol.23,No.1 May,2006.
最优性条件
x是总体极小点的充分必要条件是g ( x ) 0.
证明: 必要性显然.证明充分性. 因为f是可微的凸函数,
g ( x*) 0,
所以 f ( x) f ( x*) g ( x*)T ( x x*) f ( x*), x D.
即x是 总体极小点.
考虑等式约束最优化问题
|| f ( x ) ||
(k )
适用于收敛速度 比较慢的算法.
依赖于函数在极小点领域内的性质.
x1 * x1
x2 * x2
一个理想的算法终止准则
|| x
(k )
x*||
然而x * 是未知的,
这样的准则并不具有任何实用价值.
但是 || x ( k 1) x* || || x ( k 1) x ( k ) x ( k ) x* || (k ) || x x* || || x ( k ) x* ||
0
定理（二阶必要条件）
设f : D R R 在开集D上二阶连续可微，若
n 1
x D是 min f ( x)的局部极小点，则 n
xR
g ( x ) 0, G( x ) 0(G( x*)正半定).
定理（二阶充分条件）
设f : D R R 在开集D上二阶连续可微，
n 1
(１) f xk (２ )
|| x
( k 1)
x
(k )
||
(k )
或 | f ( x( k 1) ) f ( x( k ) ) |
(３) || x
(k )
|| ,| f ( x ) |
|| x ( k 1) x ( k ) || | f ( x ( k ) ) f ( x ( k 1) ) | , (k ) (k ) || x || | f (x ) |
线性约束三次规划问题的全局最优性必要条件和最优化算法
２ ０ １ ５ 钲６ ｌ ｆ
Ｊ ｕ ｎ ｅ ， ２ ０１ ５
运 筹 学 学 报
Ｏｐ ｅ ｒ ａ ｔ ｉ ｏ ｎ ｓ Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ Ｔｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ
第１ ９ 卷 第２ 期
ＶＯ １ ． １ ９ Ｎ Ｏ． ２
Ｄ Ｏ Ｉ ： １ ０ ． １ ５ ９ ６ ０ ／ ｊ ． ｃ ｎ ｋ ｉ ． ｉ ｓ ｓ ｎ ． １ ０ ０ ７ — ６ ０ ９ ３ ． ２ ０ １ ５ ． ０ ２ ． ０ ０ ２
ｓ ａ ｒ ｙ ｇ ｌ ｏ ｂ ａ ｌ ｏ ｐ ｔ ｉ ｍａ ｌ ｉ ｔ ｙ ｃ ｏ ｎ ｄ ｉ ｔ ｉ ｏ ｎ ｓ ． Ａ ｇ ｌ ｏ ｂａ ｌ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈｏ ｄ ｉ ｓ ｐ ｒ ｏ ｐｏ ｓ ｅ ｄ ｏｒ ｆ ｃ ｕ ｂ ｉ ｃ ｐｏ ｌ ｙ ｎ ｏ ｍｉ ａ ｌ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｐ ｒ ｏ ｂｌ ｅ ｍｓ ｗｉ ｔ ｈ ｌ ｉ ｎ ｅ ａ ｒ ｉ ｎ ｅ ｑ ｕ ａ ｌ ｉ ｔ ｙ ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｔ ｓ ｂ ｙ ｃ ｏ ｍｂ ｉ ｎ ｉ ｎｇ ｔ ｈ ｅ ｎ ｅ ｗ ｌ ｏ ｃ ａ ｌ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｓ ｔ ｏ ｇ ｅ ｔ ｈ ｅ ｒ ｗｉ ｔ ｈ ｓ ｏ ｍｅ ａ ｕ ｘ ｉ ｌ ｉ ａ ｒ ｙ ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ｓ ． Ｆｉ ｎ ａ ｌ ｌ ｙ ，ｓ ｏ ｍｅ
线性约束三次规划 问题 的全局最优性 必要条件和最优化算法木
叶 敏１ 吴至友 ， 十 张 亮
摘 要 讨论 了带线性不等式约束三 次规划 问题 的最优 性条件和 最优化算法 ． 首先， 讨论 了 带有 线 性 不 等 式 约 束 三 次 规 划 问题 的全 局 最 优 性 必 要 条 件 ． 然后， 利 用 全 局 最优 性 必 要 条 件 ，
Ｊ ｕ ｎ ｅ ， ２ ０１ ５
运 筹 学 学 报
Ｏｐ ｅ ｒ ａ ｔ ｉ ｏ ｎ ｓ Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ Ｔｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ
第１ ９ 卷 第２ 期
ＶＯ １ ． １ ９ Ｎ Ｏ． ２
Ｄ Ｏ Ｉ ： １ ０ ． １ ５ ９ ６ ０ ／ ｊ ． ｃ ｎ ｋ ｉ ． ｉ ｓ ｓ ｎ ． １ ０ ０ ７ — ６ ０ ９ ３ ． ２ ０ １ ５ ． ０ ２ ． ０ ０ ２
ｓ ａ ｒ ｙ ｇ ｌ ｏ ｂ ａ ｌ ｏ ｐ ｔ ｉ ｍａ ｌ ｉ ｔ ｙ ｃ ｏ ｎ ｄ ｉ ｔ ｉ ｏ ｎ ｓ ． Ａ ｇ ｌ ｏ ｂａ ｌ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈｏ ｄ ｉ ｓ ｐ ｒ ｏ ｐｏ ｓ ｅ ｄ ｏｒ ｆ ｃ ｕ ｂ ｉ ｃ ｐｏ ｌ ｙ ｎ ｏ ｍｉ ａ ｌ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｐ ｒ ｏ ｂｌ ｅ ｍｓ ｗｉ ｔ ｈ ｌ ｉ ｎ ｅ ａ ｒ ｉ ｎ ｅ ｑ ｕ ａ ｌ ｉ ｔ ｙ ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｔ ｓ ｂ ｙ ｃ ｏ ｍｂ ｉ ｎ ｉ ｎｇ ｔ ｈ ｅ ｎ ｅ ｗ ｌ ｏ ｃ ａ ｌ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｓ ｔ ｏ ｇ ｅ ｔ ｈ ｅ ｒ ｗｉ ｔ ｈ ｓ ｏ ｍｅ ａ ｕ ｘ ｉ ｌ ｉ ａ ｒ ｙ ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ｓ ． Ｆｉ ｎ ａ ｌ ｌ ｙ ，ｓ ｏ ｍｅ
线性约束三次规划 问题 的全局最优性 必要条件和最优化算法木
叶 敏１ 吴至友 ， 十 张 亮
摘 要 讨论 了带线性不等式约束三 次规划 问题 的最优 性条件和 最优化算法 ． 首先， 讨论 了 带有 线 性 不 等 式 约 束 三 次 规 划 问题 的全 局 最 优 性 必 要 条 件 ． 然后， 利 用 全 局 最优 性 必 要 条 件 ，
关于凸函数的几个充分必要条件
关于凸函数的几个充分必要条件文{化I教I育科关于凸函数的几个充分必要条件葛丽萍(黑河学院数学系,黑龙江黑河164300)——黑龙江——技信息摘要:凸函数是一类非常重要的函数,在许多领域有广泛的应用.从不同角度举证了凸函数的六个充分必要条件,并给出了详细的证明.关键词:凸函数;充分必要条件;等价凸函数是一类非常重要的函数,应用函数的导数满足不等式凸性,不仅可以科学,准确的描述函数的图像,而且也有证明不等式的凸函数方法,同时,凸函数也是优化问题中重要的研究对象,它研究的内容非常丰富,研究的结果也在许多领域得到了广泛的应用,所以研究凸函数的性质以及充要条件也显得尤为重要.定义:设f为定义在区间上I的函数,若对I内的任意两点xI'x和任意实数(0,1),总有f(Axa+(1A))A,()+(1一A),()则f称为I上的凸函数.如果不等式改为严格不等式,则相应的函数称为严格凸函数.定理1:x)为区间(a'b)上的凸函数的充要条件是:对(a,b)内的任意三点xi<x2<x,皆有下列不等式:f(x.)一,()f(x,)f(x)x2一xlx3一x2f(x2),(),,f(x)一f(xOf(x3)一f(xD——=x2一xax3一工x3一xz定理2:设f(x)在(a.b)内可导,则下列论断等价:(1)fix)是(a,b)内凸函数;(2)f(x)在(a.b)内单调上升;(3)对a,b)内任意两点xl,x,恒有f(x)≥f(xI)+f(x1)(xr_x1)定理3:"x)为因司(a,b)上的凸函数的充要条件是:对任意自然数nl,成立下列不等式:,(∑)∑A#f(xe)=1k=lVXk∈(a,b),Vkt>0,l+'''+l证明:充分陛显然成立必要性应用数学归纳法:设f(x)为区l司(a,b)上的凸函数,当m=2时,此结论正好是凸函数的定义.设m=k时,结论成立,即对任意的X,X,…x,e (a.b)及/>0,i=l,2,'.'k,l+ (1)都有,(∑)∑^,)现在证明当m=k+l时结论也成立,为此,任取非负实数.,,…入,满足12+…¨=l,并取x1,x2,…,X"∈(a,b),不妨设0<h¨<1,令F=hl++k,=,i=l,2…k,贝01,+2,++_1,于是有_,(++^几)十十,),又因=1,再由x)的凸性的定义得,,f(A十十.)=,((++^)十^".+|),(xI十+)+",(+1))++九)]+")一^1,(1)++,()+～+1.厂(+1)二,()+…+,()+,(州)即当m=k+l时结论也成立,于是根据数学归纳法对任意自然数ill,结论都成立.定理4:"x)为区间(a,b)上的凸函数的充要条件是:fix)在(a.b)上处处左,右可导,并且其左,右()()上二(x2)一^(x0,,,x2∈(Ⅱ,),<x2证明:必要性设f(x)为区间(a.b)上的凸函数,对于固定的ye(a'b),作函数gy()f(x～)-f(y),x#y,x∈(a,b)l~t定理l知,岛(x)作为x的函数是增函数,于是任意的x,xz,y∈(a'b),且(】c卿),有…f(x)4(x9≥,从而二苎的增x-x,x2……一一一函数且有下界,丛是Y的减函数且有上界,从而存在极限,且():li生=>Ilm!=:,)'同理,当x勰u>x.时,有f(x)f(x~)>f(x)-f(xO因此,,f,:lim=>!Hx一>lim!二!苎2=()即有不等式()()兰()()x2一xI充分眭设x)在(a,b)上可导,首先证明对于任意的x.,x∈(a,b),xl<x:,有inf()生二坐sup()先证明第二个不等式.令M=sup(),inf()"'如果MI+,则第二个不等式成立.因此只考虑M为有限的情形,令g(x):Mx-fix),显然g(x)在(a'b)处可导,且g,.(x)/>0,Vx(XDX),现在证明g(x)是(x,xz)中的不减函数,即g(z)≤g(zz),Vz-,z2Ex1,x2),Zl<Z2事实上,'ix∈(xj'x),V e>0,存在8l,使得g(x+h)-g(x)~<-sh,Vh∈10,8I,现在设z=sup{x∈z,z~(x)-g(z1)≥(x—z1)l,我们来证明xmz.如果不然,则有z<z,从而由z的定义和x)的连续眭知g(z)-g(z,)≥_E(z-_zt),但对于z,又有8>J0,使得g(z+h)一g(z)-sh,Vh∈l0,8J,这显然与z的定义相矛盾.于是由e>O的任意性知g(z1)≤g(z2),VZDZ2∈(XDX2),Zl<Z2成立.根据g(x)的定义,上式也可以写成Mz:-f(z:)≥Mz.-fz1),VZI,Z2∈(x1,X2),ZI<Z2由此利用f(x)的连续l生得到=(x1)≤M:sup()T-X为了证明第一不等式,令P(x)--f(x)-mx即可.其次证明x)为区间(a,b)上的凸函数对(a,b)内的任意iX1<X2~3,由第一部分证明得到丛譬{…infqq…)<丛二,【型于是由定理1知fix)为区间(a,b)上的凸函数.定理5:x)为区间(a'b)上的凸函数的充要条件是:对(a,b)内的任意三点Xl<X~<X,恒有l1,(五)lA—l1x,()l0I1f(x3)l证明将此行列式按第一列展开,则有l1,)l△=l1,I一[xx3x3f(x2)Hx-f(x3x3f(x1)]l1,+【,()xzf(xa)]J1^_,){于是△=xa,1啪充分是f(x)I1x3,l为区间(a,b)上的凸函数.定理6:设"x)为区间(a,b)内连续,则x)是凸函数的充要条件是:不等式,()J,+)在任何含于(a,b)的闭区间【x-h,x+h](h>o)成立. 证明必要性VItk<h,因x)是凸函数,则,()=,("r)+(+f)),(xt)+,(+=(D+,0+r))于是,()(xt)+,+出即2hf(x)r(,(—t)+f(x+t))dt--2am则有似)J一)充分反证法:假设"x)不是(a,b)内的凸函数,由定理3,对hi=1,1,l1,存在x1,x(a,b),使得争xl+手x)>争陬x.)+f(x)】.不妨设xt<x:,作辅助函数g(x)_--f(x)_k(x_x.)x),其中k:尘.则s(_,(半)一(≠)f(xa)_,(警)一【,()+,(>0又因f(x)在(a,b)内连续,故g(x)也在(a,b)内连续,当然在Ix.,x内连续,因此在Ix.,内能够取到最大值,记g(x)在xI'x内取到最大值为g(xo), XoEIx.,x.取h>0,[xo-h,xo+h]C[x.,x,当Irish时,有g(xo)-g(xo+t)I>0,且不恒为0,因此,f[g(xo)-g(Xo+ t)]dt~O,即f.g(xo)dt>I.g(xo+t)dt,即2hg(xo)>{gJ_hJ- h(x0+t)dt,再由g(x)的定义得到2hf(xo)>Jf(x)dt,矛盾,假设不成立,故x)为(a,(下转32页)一193—科科l技I论l坛车载终端自主型智能公交管理系统介绍钱隐1,2(1,重庆大学计算机学院,重庆4041002,四川美术学院,重庆401331)摘要:针对车栽终端自主型智能公交管理系统,简要介绍了OPS这种新型的里程定位技术.关键词:智能公交;OPS;定位引言随着社会经济的发展,交通拥挤,线路阻塞和交通事故频繁发生正越来越严重的困扰着世界上的各大城市.汽车工业发展引发的道路交通不能满足需求的种种问题越来越突出.一般来说,解决车和路的矛盾不外乎两个办法:一是控制需求,最直接的办法就是限制车辆的增加;二是增加供给,也就是修路.然而有限的土地和经济制约等使得道路建设不可能达到相对满意的里程数,从而使这两个办法都有其局限性,不能从根本上解决交通拥挤的矛盾.为了在不扩张路网规模的前提下提高交通路网的通行能力,近年来,把道路,车辆等凡与交通有关的所有一切都归为一体,通过综合运用信息通信技术,电子技术以及其他的科学技术把它们联系起来提高交通运输的效率,并称之为智能交通系统(~teUigentTransportationSystem),简称ITSI".APTSf先进的公共交通系统,AdvancedPublicTransportationSystem)是ITS重要的子系统,它是将高度先进的信息化通信技术应用于传统的公共交通系统中,使公共交通系统智能化.APTS能够使交通供给满足实时,动态的交通需求,提高公共交通的吸引力,准时,快速和舒适,提供快速,便捷,经济的换乘服务,实现调度与运营的高效,公交管理智能化等目标121. 1系统总体设计框架设计公共交通智能调度系统总体设计与实现基本框架构想是:结合ITS对公共交通智能化的逻辑结构,物理结构以及公交智能化管理系统的总体设计要求,首先确定公共交通智能化管理系统与信息流程,再结合公交车辆的调度体制,确定定位方式,通信系统,计算机网络系统和调度系统的方案131.该系统能够优化公共交通运营管理模式,将极大提高公交系统的管理水平和运营效率.在现有交通设施的基础上,利用智能公共交通系统总体方案,优化公交运营管理模式,提高运营效率,节约能源,降低环境污染,形成一套具有高技术含量的适应于大中城市需求的技术方法和实现手段[41.2OPS技术的提出ITS的基础问题是定位,判断～种技术是否优越必须切实结合它的使用场合与需求.城市公共交通的特点主要是:(1)公交线路及沿线站点的设置由城市交通规划确定,不会经常发生变动;(2)公交车辆通常情况F应定线行驶,定点停靠;(3)大中城市的公交车辆在高楼林立,立交桥纵横的环境中运行.长期以来,业界的普遍观点是采用GPS(全球定位系统,GlobalPositions,rstein,l技术该技术是通过全球卫星信号测定的车辆所在位置经纬度,经分析处理后在电子地图上显示车辆位置.GPS虽然发展已久,是比较成熟的定位技术,但由于GPS卫星信号易被地形,地物遮挡, 导致定位精度大为降低,甚至无法实用,尤其在高楼林立,立交桥纵横的大城市车载终端接收到的卫星信号,很难准确测定出车辆所在位置的经纬度,导致电子地图上显示的车辆位置和实际情况有较大出入,而且GPS通信费用昂贵,因此并不适合公交系统.针对公共交通的特点,文献【5】提出了一种新型定位技术——0PS(0d0meterPositionSys—tern,里程定位技术).该技术紧紧抓住公交车辆"定线行驶,定点停靠"的特点,只需通过车载终端采集车辆在固定线路上的行驶里程和方向就可实现车辆定位,并且不受车辆运行环境的制约,有效客服GPS信号易受干扰,多径效应强, 使用费昂贵的弱点.3关键技术及原理3.1测量里程OPS测量里程的原理与出租车的计程器相同,即利用车辆转速传感器采集车轮转动原始数据.传感器与车辆转动轴相连,每转动一周输出一个脉冲.转动轴与车轮之间有对应的比例系数,不同车型的比值会有所不同.由于公交车辆车型有限,可以通过测量脉冲数和里程,计算得到各种车型转动轴和车轮间的比例系数.此后就可根据脉冲数和比例关系得到车辆行驶里程.3-2车辆定位传统的电子地图是由车辆的经纬度信息来定位的,而OPS是根据里程信息将公交线路沿线站点及站间抽样点的地理坐标映射为与起点站的距离.车辆在固定线路上行驶,根据车辆行驶的方向和里程就可知车辆的地理坐标,进而在电子地图上定位车辆.3-3车载终端原理车载终端的存储器预存每个站点对应的里程数,接通汽车电源并开机后,终端处于待机状态,里程和速度置零.车载终端接收到调度人员的发车指令后蜂鸣器响,开始语音报站,并由待机状态转为运行状态.由里程传感器获取车辆行驶里程,并由微处理器计算出速度.当车辆行驶里程与存储器内某站点的里程在许可范围内吻合时,微处理器控制启动语音报站.车辆是否超速,赖站,堵车,由OPS参数设置判断.车载终端采集的数据经无线网络传输给监控中心, 并定时检查网络通信状态.当发生紧急情况,如车辆事故,车辆故障,治安告警等,驾驶员按下对应按钮后,该信息立即发送到应急响应中心. 4设计原则及系统功能性特征可靠性原则:本系统涉及公交车辆实时动态慨挎和高教调度指挥,因此系统的稳定可靠运行是系统设计中的首要考虑因素.易于扩展性原则:随着时代的发展,会有越来越多的功能被纳入到此系统中来,因此,在系统的设计时,还应充分的考虑到今后系统的发展方向,使其能满足今后业务的扩展.节约成本原则:考虑到公交系统长期处于薄利甚至亏损的情况,在系统设计的时侯,多为用户考虑,使系统各项功能在软硬件实现方式上都能有机的结合,保证系统合理的性能价格比,尽量降低使用费.另外还包括完整性原则和先进性原则.系统功能性特性如下:实现车载终端信息采集,并保证终端与监控中心之间实时,可靠的信息交互;实现车辆动态监控和按不同条件进行查询车辆运营统计情况;实现车辆状态分;实现车辆自动调度;实现车辆运营情况分析统计和报表自动打印;班次和里程,车辆运营情况和告警信息统计以及实现公司各部门的不同管理权限.小结:这里对智能公交管理系统的框架作了总体介绍,对一种新型定位方式——0PS(里程定位),简要介绍了其关键技术,并对系统的设计原则和功能性特征作了总体说明.参考文献【l】王笑京.我国智能交通的发展现状与未来咖. 中国计算机用户,2002,3.【2】胡卉,申金升.I与城市交通可持续发展的探讨m.中国环境管理,20o3:6-8.[3]MasakiD.CSystemdesignforintelligent transportationsystems,Proceedingsofthe1996 IEEEIntelligentV ehiclesSymposium,1996: 323—326.[g]IntelligentTransportationSy~emsBenefits:1999UpdateMitmtekSystemIne.May,1999.『51陈继努.用里程表对定线车辆跟踪定位的装置【P】.中国专利03252843.4.2004.责任编辑:胡明月(上接193页Jb)内的凸函数.从以上关于凸函数的充:要条件可以看到凸函数具有良好的性质,但由于凸函数理论的广泛性和深刻性,对于凸函数理论的研究还需要进一步的深入和推广.参考文献【l】华东师范大学数学系.数学分析删].第三版北京: 高等教育出版社.2004.f2德祥,刘绍武.教学分析方法选讲阿哈尔滨:黑龙江教育出版社.199<[3德兴.凸分析基础IMl北京:科学出版社,1995.『4I刘鸿基,薛明志.关于凸函数的两个充分必要条件『Jl菏泽学院,2006.责任编辑:胡明月一32—。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Ｓ ： ＝｛ ∈Ｒ ： ＝１ ， ｉ ＝１ ， ２ ， …， ／ ７ ， ｝
下面 的 引理是 很显 然 的．
（ ２ ）
引理 １ 设 ∈｛ － １ ， １ ｝ ， 则 是 问题 （ Ｃ Ｐ） 的全局 最优 解 当且仅 当 是 问题 （ Ｂ Ｑ Ｐ ） 的全局 最优 解．
ｓ ． ｔ ．
∈｛ 一１ ， １ ｝ ／ ７ ，
由于 （ Ｃ Ｐ） 等 价 于 问题 （ Ｂ Ｑ Ｐ ） ， 所 以通过 研究 问题 （ Ｂ Ｑ Ｐ ） 的全局 最 优性 条 件 来 得 到 问题 （ ｃ Ｐ ） 的全 局 最 优 性
条件． 问题 （ Ｃ Ｐ ） 的可行集 ｛ － １ ， １ ｝ 可以等价地写成式（ ２ ） 的连续形式 ：
，
一 ， ） ’ ∈
用Ｘ ， ＝ｄ ｉ ａ ｇ （
． ． ， ）表示 对 角元 素为
一， 的对 角矩 阵 ， 因此 ＝Ｘ ｅ ．
定义 １ 设 ∈ ｛ － １ ， １ ｝ ， 如果． 厂 （ ） ≤ ） 对任 意 的 ∈｛ － １ ， １ ｝ 都成 立 ， 则 称 是 问题 （ Ｃ Ｐ ） 的一个
规划问题 的全局充分条件 ， 进 而得到 了刻画带 ｛ ＿ １ ， １ ｝ 二元约束的非 凸三次优化 问题全局充分条件．
关 键词 ： 三 次极 小化 问题 ； 全 局 最优 性 条件 ； 二元 约束 中图分类 号 ￣ ０ ２ ２ １ ． １ 文 献标 志码 ： Ａ
考虑下面的带有双值约束的非凸三次优化问题 ：
Ｓｅ ｐ ｔ ．２ ０１ ４
文章 编 号 ： １ ６ ７ ２ — ０ ５ ８ Ｘ（ ２ ０ １ ４ ） Ｏ ９ — ０ ０ ０ ６ — ０ ４
带 二 元 约束 非 凸 三次优 化 问题 的全 局 充分 条 件 术
张 亮
（ 重庆师范大学 数学学院 ， 重庆 ４ ０ １ ３ ３ １ ）
第３ １ 卷 第 ９期
Ｖｏ ｌ ＿ ３１ Ｎ０． ９
重庆 工 商大 学学报 （自然科 学版 ）
Ｊ Ｃ ｈ ｏ ｎ ｇ ｑ ｉ ｎ ｇ Ｔ ｅ ｅ ｈ ｎ ｏ ｌ Ｂ ｕ ｓ ｉ ｎ ｅ ｓ ｓ Ｕ ｎ ｉ ｖ ． （ Ｎ ａ ｔ Ｓ ｅ ｉ Ｅ ｄ ）
２ ０ １ ４年 ９月
第 ９期
张 亮 ： 带二元约束非凸三次优化 问题 的全 局充 分条 件
７
全局极 小 点．
对于问题 （ Ｃ Ｐ ） ， 因为 ∈｛ － １ ， １ ｝ ， 所以 ＝ ， 因此能够容易证明问题 （ ｃ Ｐ ） 等价于式 （ １ ） 的带有双值约 束的非凸二次优化 问题 ：
（ Ｂ Ｑ Ｐ） ） Ｑ ＋（ ＋卢） ｆ １ ）
三次规划数学模型（ Ｃ Ｐ ） 包含了一大类最优化问题 ， 包括二次优化 问题和组合优化问题等 ， 它在三次多 项 式近 似优 化 、 凸优化 、 工程 设计 和结 构优 化等 领域 有着广 泛 的应用． 此外 ， 由于二 次优 化 问题 是 三次 规优 化
问题 的特殊情 形 ， 所 以关 于三次 问题 的研究 成果 可 以 应用 到 二次 规 划 问题 ， 见文 献 ［ １ — １ ２ ］ ． 此 处 主 要考 虑 一
类带有双值约束的非凸三次优化问题 （ Ｃ Ｐ ） ， 利用该非凸三次优化问题 的特殊性将问题 （ Ｃ Ｐ ） 等价转化为带 有双值约束的非凸二次规划问题进行研究 ， 并利用 Ｒ ｏ ｃ ｋ ａ ｆ ｅ ｌ ｌ ａ ｒ 在文献 ［ １ １ ］ 中给出的经典对偶理论 ， 提 出了 等 价转 化后 的非 凸二 次规划 问题 的一 些全 局充 分条 件 ， 并 利 用 问题 的等 价 性得 到 了相 应 的 非 凸三 次 优化 问
ｆ ＝１
尺 “ 中的标 准正交 基 ， 所有分 量都 为 １ 的 向量 记作 ｅ ， 即ｅ ＝（ １ ， …， １ ） Ｔ ． 对于 尺 中 的任 意两 个 向量 ， ≥ ｙ Ｃ ： ￣ ｘ ｉ ≥
Ｙ ， ｉ ＝ １ ， ２ ， …， ｎ ， 对． ｓ 中的任意两个矩阵 ， 曰 ， Ａ± （ ＞） Ｂ ｃ ： ， Ａ— 是半正定 （ 正定 ） 矩 阵． 对 ＝ （
１
（ Ｃ Ｐ ）ｍ ｉ ｎ ， （ ） ＝
ｓ ．
∈｛ 一１ ， １ ｝
其中Ｏ ｌ ＝ （ Ｏ ｌ 一 ， Ｏ ｌ ） ∈ Ｒ ， ＝ （ 一 ， 卢 ） ∈ Ｒ ， ＝ （ ； ， …， ： ） ， Ｑ ∈ Ｓ ， 这里 ｓ 是所有 ｎ ｘ ｎ 阶实对称矩阵
题 全局 充分 条件．
１ 预 备 知 识
表示实线性空间， 表示 ｎ 维欧几里得空间（ Ｅ ｕ ｃ ｌ ｉ ｄ ｅ ａ ｎ ） ， Ｒ ｎ 表示 ｎ 维非负欧几里得空间． 对 向量 ∈
ｎ
Ｒ ， ｌ ｌ ： ＝ （ ： ） 和 ｌ Ｉ 。 。 ： ＝ ｍ ａ ｘ Ｉ ｌ 分别表示欧式范数（ 或ｆ 一 范数） 和ｚ 。 。 一 范数． ｛ ｅ ｎ ： 表示
收稿 日期 ： ２ ０ １ ４ － ０ ２ — ２ ５ ； 修回 日期 ： ２ ０ １ ４ － ０ ４ — １ ０ ． 基金项 目 ： 国家 自然科 学基金（ １ ０ ９ ７ １ ２ ４ １ ） ．
作者简 介 ： 张亮（ １ ９ ８ ８ ） ， 男， 硕士研究生 ， 四川南充人 ， 从 事最优化理论与方法研究
摘
要： 将一类特殊的带有 ｛ ＿ １ ， １ ｝ 二元约束的非凸三次优化 问题等价转化为带有 ｛ ＿ １ ， １ ｝ 二元约束的
非凸二 次规 划 问题 ， 并利 用 Ｒ ｏ ｃ ｋ ａ ｆ ｅ ｌ ｌ ａ ｒ 在 文 献《 ｃ ｏ ｎ ｖ ｅ ｘ Ａ ｎ ａ ｌ ｙ ｓ ｉ ｓ ）中给 出的经 典 对偶理 论 ， 提 出 了该 非 凸二 次
下面 的 引理是 很显 然 的．
（ ２ ）
引理 １ 设 ∈｛ － １ ， １ ｝ ， 则 是 问题 （ Ｃ Ｐ） 的全局 最优 解 当且仅 当 是 问题 （ Ｂ Ｑ Ｐ ） 的全局 最优 解．
ｓ ． ｔ ．
∈｛ 一１ ， １ ｝ ／ ７ ，
由于 （ Ｃ Ｐ） 等 价 于 问题 （ Ｂ Ｑ Ｐ ） ， 所 以通过 研究 问题 （ Ｂ Ｑ Ｐ ） 的全局 最 优性 条 件 来 得 到 问题 （ ｃ Ｐ ） 的全 局 最 优 性
条件． 问题 （ Ｃ Ｐ ） 的可行集 ｛ － １ ， １ ｝ 可以等价地写成式（ ２ ） 的连续形式 ：
，
一 ， ） ’ ∈
用Ｘ ， ＝ｄ ｉ ａ ｇ （
． ． ， ）表示 对 角元 素为
一， 的对 角矩 阵 ， 因此 ＝Ｘ ｅ ．
定义 １ 设 ∈ ｛ － １ ， １ ｝ ， 如果． 厂 （ ） ≤ ） 对任 意 的 ∈｛ － １ ， １ ｝ 都成 立 ， 则 称 是 问题 （ Ｃ Ｐ ） 的一个
规划问题 的全局充分条件 ， 进 而得到 了刻画带 ｛ ＿ １ ， １ ｝ 二元约束的非 凸三次优化 问题全局充分条件．
关 键词 ： 三 次极 小化 问题 ； 全 局 最优 性 条件 ； 二元 约束 中图分类 号 ￣ ０ ２ ２ １ ． １ 文 献标 志码 ： Ａ
考虑下面的带有双值约束的非凸三次优化问题 ：
Ｓｅ ｐ ｔ ．２ ０１ ４
文章 编 号 ： １ ６ ７ ２ — ０ ５ ８ Ｘ（ ２ ０ １ ４ ） Ｏ ９ — ０ ０ ０ ６ — ０ ４
带 二 元 约束 非 凸 三次优 化 问题 的全 局 充分 条 件 术
张 亮
（ 重庆师范大学 数学学院 ， 重庆 ４ ０ １ ３ ３ １ ）
第３ １ 卷 第 ９期
Ｖｏ ｌ ＿ ３１ Ｎ０． ９
重庆 工 商大 学学报 （自然科 学版 ）
Ｊ Ｃ ｈ ｏ ｎ ｇ ｑ ｉ ｎ ｇ Ｔ ｅ ｅ ｈ ｎ ｏ ｌ Ｂ ｕ ｓ ｉ ｎ ｅ ｓ ｓ Ｕ ｎ ｉ ｖ ． （ Ｎ ａ ｔ Ｓ ｅ ｉ Ｅ ｄ ）
２ ０ １ ４年 ９月
第 ９期
张 亮 ： 带二元约束非凸三次优化 问题 的全 局充 分条 件
７
全局极 小 点．
对于问题 （ Ｃ Ｐ ） ， 因为 ∈｛ － １ ， １ ｝ ， 所以 ＝ ， 因此能够容易证明问题 （ ｃ Ｐ ） 等价于式 （ １ ） 的带有双值约 束的非凸二次优化 问题 ：
（ Ｂ Ｑ Ｐ） ） Ｑ ＋（ ＋卢） ｆ １ ）
三次规划数学模型（ Ｃ Ｐ ） 包含了一大类最优化问题 ， 包括二次优化 问题和组合优化问题等 ， 它在三次多 项 式近 似优 化 、 凸优化 、 工程 设计 和结 构优 化等 领域 有着广 泛 的应用． 此外 ， 由于二 次优 化 问题 是 三次 规优 化
问题 的特殊情 形 ， 所 以关 于三次 问题 的研究 成果 可 以 应用 到 二次 规 划 问题 ， 见文 献 ［ １ — １ ２ ］ ． 此 处 主 要考 虑 一
类带有双值约束的非凸三次优化问题 （ Ｃ Ｐ ） ， 利用该非凸三次优化问题 的特殊性将问题 （ Ｃ Ｐ ） 等价转化为带 有双值约束的非凸二次规划问题进行研究 ， 并利用 Ｒ ｏ ｃ ｋ ａ ｆ ｅ ｌ ｌ ａ ｒ 在文献 ［ １ １ ］ 中给出的经典对偶理论 ， 提 出了 等 价转 化后 的非 凸二 次规划 问题 的一 些全 局充 分条 件 ， 并 利 用 问题 的等 价 性得 到 了相 应 的 非 凸三 次 优化 问
ｆ ＝１
尺 “ 中的标 准正交 基 ， 所有分 量都 为 １ 的 向量 记作 ｅ ， 即ｅ ＝（ １ ， …， １ ） Ｔ ． 对于 尺 中 的任 意两 个 向量 ， ≥ ｙ Ｃ ： ￣ ｘ ｉ ≥
Ｙ ， ｉ ＝ １ ， ２ ， …， ｎ ， 对． ｓ 中的任意两个矩阵 ， 曰 ， Ａ± （ ＞） Ｂ ｃ ： ， Ａ— 是半正定 （ 正定 ） 矩 阵． 对 ＝ （
１
（ Ｃ Ｐ ）ｍ ｉ ｎ ， （ ） ＝
ｓ ．
∈｛ 一１ ， １ ｝
其中Ｏ ｌ ＝ （ Ｏ ｌ 一 ， Ｏ ｌ ） ∈ Ｒ ， ＝ （ 一 ， 卢 ） ∈ Ｒ ， ＝ （ ； ， …， ： ） ， Ｑ ∈ Ｓ ， 这里 ｓ 是所有 ｎ ｘ ｎ 阶实对称矩阵
题 全局 充分 条件．
１ 预 备 知 识
表示实线性空间， 表示 ｎ 维欧几里得空间（ Ｅ ｕ ｃ ｌ ｉ ｄ ｅ ａ ｎ ） ， Ｒ ｎ 表示 ｎ 维非负欧几里得空间． 对 向量 ∈
ｎ
Ｒ ， ｌ ｌ ： ＝ （ ： ） 和 ｌ Ｉ 。 。 ： ＝ ｍ ａ ｘ Ｉ ｌ 分别表示欧式范数（ 或ｆ 一 范数） 和ｚ 。 。 一 范数． ｛ ｅ ｎ ： 表示
收稿 日期 ： ２ ０ １ ４ － ０ ２ — ２ ５ ； 修回 日期 ： ２ ０ １ ４ － ０ ４ — １ ０ ． 基金项 目 ： 国家 自然科 学基金（ １ ０ ９ ７ １ ２ ４ １ ） ．
作者简 介 ： 张亮（ １ ９ ８ ８ ） ， 男， 硕士研究生 ， 四川南充人 ， 从 事最优化理论与方法研究
摘
要： 将一类特殊的带有 ｛ ＿ １ ， １ ｝ 二元约束的非凸三次优化 问题等价转化为带有 ｛ ＿ １ ， １ ｝ 二元约束的
非凸二 次规 划 问题 ， 并利 用 Ｒ ｏ ｃ ｋ ａ ｆ ｅ ｌ ｌ ａ ｒ 在 文 献《 ｃ ｏ ｎ ｖ ｅ ｘ Ａ ｎ ａ ｌ ｙ ｓ ｉ ｓ ）中给 出的经 典 对偶理 论 ， 提 出 了该 非 凸二 次