带稀疏约束非线性最优化问题的最优性条件_马杨.pdf

（）（，），带稀疏约束非线性最优化问题的最优性条件马杨李明华薛 小 维（重庆 交通大学数学与统计学院，重庆 ；重庆文理学院数学与大 数据学院，重庆）摘 要文章研究单稀疏约束和 混合稀疏约束两类 优化问题，均 采用直接处理法，即把约束条件 放在目标函数中，使约束优化问题转化为无约束优化问题文章研究了稀疏集 生成的正部函数的极限次微分表达式对于第一类问题，先建立稀疏集的误差界不等 式，利用该不等式的 系数和目标函数的常数，将原问题转化为无约束问题，建立了两个问题的最优 解之间 的等 价关系，并得到了一阶必要和 充分最优性 条件第二类问题 是第一类问题的推广，在可行集的误差界假设条件下，利用该不等式的 系数和目标函数的常数，将原问题转化为无约束问题，建立了两个问题的最优 解之间 的等 价关系，并得到了一阶必要和 充分最优性 条件关键词稀疏优化，最优性 条件，极限次微分，误差界（）主题分类号，（，；，），：国家自然科学基金（），重庆 市自然科学基金（，），重庆 市 教委 科学技术研究项目（，），重庆 市研究 生联合墙养基 地建设项目（），重庆 市高 校铜新研究群体项目（）资助课题收稿日期：，收到修改稿日期：通信作者：薛 小维，：编 委：杨新民马杨等：带 稀疏约束非线性最优化问题的最优性 条件，引言稀疏约束优化问题是指对受 到稀疏性约束的目标函数进行最小化，在 压 缩 感知、投资组合、高维 统计 分析中的变量选择和稀疏主成分 分析等方面都 有广泛的应用由于零范数是非凸非光 滑的下 半 连 续函数，故传统的连 续优化理论与算法不 能直接 应用到稀疏约束优化问题的模型中，这就给研究者带 来了极大挑战，也使 得 稀疏优化的研究成为近年来的一个重 要研究热点借 助零范数的特殊结构与变 分 性质，稀疏优化的最优 性理论结 果不断涌现近年来，对稀疏约束优化问题，很多学 者选择直 接处理模型，借 助稀疏集的投影和 切锥法锥，给出了各种最优性条件这 些 最优性条件不仅丰 富了稀疏优化的理论成果，还给算法设计和 收敛性分析 提供了支 撑针 对单 稀疏约束优化问题，和介绍并 分析了该问题的三类一阶必要 最优性 条件随 后，等继续研究该 类问题，建立了稀疏集的 和切锥、法锥表达式，介绍了光 滑 假设 下的平稳和平稳的概念，分析了基本可行、平稳、平稳和平稳之间的关系，建立了两类一阶必要 最优性条件及二阶必要和充分最优性条件接着，等利用稀疏集的法锥和 切锥，给出了一阶和二阶充分必要 最优性条件；在 此基础上，给出了稀疏集的二阶切集，建立了新的二阶必要 最优性条 件，蔡园 园和李国成给出基本可行和平稳的两个必要 最优 性条 件针对带 有抽象集约束的稀疏优化问题，和 研究了稀疏集的法锥表达式，在 此基础上，给出了一阶必要 最优性 条件随后，和 推 广了文献中的三类 最优性 条件针 对带 有 等式约束的稀疏优化问题，等研究了限制的约束规范下的一阶充分和必要最优性 条件针 对带 有 等式和不等式约束的稀疏优化问题，和 通过 把 稀疏集分解成多个子空间的并，给出了新问题在约束规范下的一阶必要 最优性 条 件随 后不 久，和利用稀疏约束优化问题与一个合适的非线性规划 之间的关系，定义了一些问题的 约束规格，并在更弱 的条 件下证明了 型最优 性条 件等系统科学与数学卷基于稀疏集的，和法锥的分解性质，给出了该模型的三类 条 件；又基于稀疏集的 切锥，给出了二阶必要和充分最优 性 条 件针 对带 有 锥约束的稀疏优化问题，等利用限制的严格约束规范，基于正则法锥和法锥 给出了两种拉格朗日乘子 集，并研究了一阶必要 最优 性条 件及二阶必要和充分最优 性条件代明成利用可行集的正则法锥的等价形 式得到了优化问题的强一阶必要条件；通过否定集值映射混合方向正则次正则的充分条 件得到了优化问题的最优 性 条 件针 对函数稀疏约束的优化问题，冷雪借 助变分 分析的知识，探究了集值映射 方向度 量 次正则性、混合正则次正则性的一阶和二阶充分条 件，并借 助此条件得到了该问题的一阶和二阶必要 最优 性条 件同年，等通过定义一个新的广义凸的概念，不仅给出了该问题的一阶充分最优 性条 件，而且 还给出了二阶必要和充分最优性条 件文章 给出了两类非线性稀疏约束优化问题的一阶必要和充分最优 性条 件对于文中的两类 稀疏优化问题，均采用直接处理法，把约束条件 放在目标函数中，使约束优化问题转化为无约束优化问题第一类问题，先建立稀疏集的误差 界不等式，再利用该不等式的系数和目标函数的常数，将原问题转化为无约束问题，借 助稀疏集生成的正部函数的极限次微分，得到该 类问题的一阶必要和充分最优 性 条 件该问题的必要 最优性 条件与文 献中在法锥 下的平稳结 果 类 似第二类问题是第一类问题的推 广，在 可行集的误差界 假设条件下，利用该不等式的系数和目标函数的常数，将原问题转化为无约束问题，借 助稀疏集生成的正部函数的极限次微分，得到该类问题的一阶必要和充分最优性条件对比 型的最优性 条件，文章 最优 性条 件的系数 是具 体的而 不仅仅 是存在，其系数就 是可行集的误差 界不等式系数与目标函数的常数的乘积文章 结构框 架如下第节介绍了一些符 号的定义，回顾了一些后面要用的基础知识第节研究单 稀疏约束优化问题，建立了原问题和对 应的无约束问题的最优 解之间的等价关系，给出了一阶必要和充分最优性 条件第节 对第节的内容进行推 广，研究有 等式和不等式约束的混合 稀疏优化问题，同样建立了原问题和对 应的无约束问题的最优 解之间的等价 关系，给出了一阶必要和充分最优 性条 件第节，对 文章做了一个简单的 总结预备知识在文中，？为维欧式空间，这 里的符 号借 鉴文 献，对于给定的？，表示为以为中心，半径为的开球卜是向量的零范数，表示中非零分量的个数奶表示零向量记：？：而，其中而表示；的第个分量；：，：而，（）：？：，（）（：，定义 对下 半连 续函数：？，如果存在（和（使得（）（），），（，）成立，那么称为在的邻近次梯度，所有组成的集 合叫做在的邻近次微 分，记做（）函数在的极限次微分定义为知（）：，）马杨等：带 稀疏约束非线性最优化问题的最优性 条件 期其中丄表示当时，且（而）（）注极限次微分 满足正齐次性，即（：）（：），十定义！函数：？，？，的正部定义为（），（）、，（）记稀疏集：？：，其中？是正整数下面我们研究了正部函数（）十在处的极限次微 分，这 里的证明过 程借 鉴了文献，定理引理对任意的？，（）（）（）当。时，（）（）（）证首先证明（）（：）设（）（根据 极限次微 分的定义，存在（）和（）（）使 得由邻近次梯度的定义知，存在和使 得（）（）（，），（）（）对任意的（），当充分小时（），（奶，），且，此时（？）（；？）？将切代入（）式，经过化简得到，）对上式两端同时 除以，再取 下极限，有，！，即（，）？（）由于对任意的（：），（：），代入（）式，得（，）？（）结 合（）和（）式得，在时，那么就有，从而丄（抑）由叫，根 据丄（）的定义可 得丄（叫）丄（），从而（）故（）（）（）在工时，只需证明（）（）因为？中任意点都是函数的局部 最小点，所以存在，对任意的（），都 有 系统科学与数学卷设无丄（），（，（）记（）：（）十，（）：无，；工，）（？），）通过定义，容易得到（）现在讨论的情形令？（，下面分两种情况来讨论：若（工，）门，则工？，即（工）由（）的定义知（，）从而（）（）（）（）若（，），则（旧）（），从而（）（）（）（，）（：）：（）因此为函数化的局部 最小点，故￥）根 据文 献，命题可得（）（）因为（）无，所以无（）从而（）故丄（）（）（）综上所 述，在？时，（）（：）注在卜。时，仅有（。也 办）义（？），反包含关系不一定成立下例可以说明这一情况例在空间？中，此时？，（）（：），显然马杨等：带 稀疏约束非线性最优化问题的最优性 条件期单稀疏约束优化本节 研究？空间 中单 稀疏约束优化问题的最优性条 件考虑 如下问题（）（），其中为？到？的 实值函数，是正整数记：？：，（：，表示到集 合的距离处理约束优化问题，常见的方法 就是使用惩罚 函数 将约束优化问题转 换为无约束优化问题，进而来求解下面这一定理就是利用稀疏集的误差 界，将约束优化问题转化为无约束优化问题与文献，定理相比，这 里只是局部性质定理考虑问题（），设，则存在的一半径为的邻域，使 得（：）（），（）如果在附近是的，其常数为，那么为问题（）的局部 最优 解当且仅当为函数（的局部 最小点证设是的一半径为的邻域，对任意的，有卜：若（，则（，（）（）若：，则（：。也，从而（，）（）现设为问题（）的局部 最优解，则存在的邻域（？，），使 得对任意的：都 有（）（）函数在？附近是的，记其邻域为（？，）（），则对任意的（，脊）（，鲁），存在吏得（：）；，（）其中显然 是一闭集由，根据投影的定义知由三角不等式可 得卜，从而，）（，）对任意的鲁）鲁），结 合（）和（）式及在附近的性脱有（）（）（）（，）（）（）（）（）系统科学与数学卷故为函数（）（）的局部 最小点反之，设？为函数（：也的局部 最小点，则存在，对任意的都 有（）（）（）（）从而对任意的，由（）（），可 得（）（）故为问题（）的局部 最优解基于上述定理，我们首先建立问题（）的一阶必要 最优 性条 件定理设，函数在附近是的如果存在？使 得为函数（）（）十的局部 最小点，那么（）（）证由于为函数（：）（）十的局部 最小点，故（）（？）（）又函数是在附近是的，根 据文 献，命题，有（）（？）（）（）（？）（）由引理可得（）丄（）注根据文献，定理，集合在处的法锥（？）（）文献的定理是在目标函数为连 续 可微的假设 下，得到了一阶必要 最优 性条 件而定理在目标函数是局部的假 设 下，得到了类 似的一阶必要 最优 性条 件下面建立问题（）的一阶充分最优性 条件，这 里需要的凸性定理设为凸函数，且。如果奶（）那么为问题（）的局部 最优 解证设奶知（）丄（），则存在知（）和￥丄（）使 得？那么对任意的？，有（，：）？（）因为？中任意点都是函数的局部 最小点，所以存在，对任意的（：，（），都有由题设，对任意的（：，（），有卜卜，即（）此时根 据义（：）及义（）的定义，有（）结 合（）和（）式得（，）（）马杨等：带 稀疏约束非线性最优化问题的最优性 条件 期由为凸函数，结 合（）式，对任意的（？，），都 有（）（）故为问题（）的局部 最优解注上述定理在：的情形下成立，在：的情形下却 不一定成立下例可以说明这种情况例在空间？中，考虑问题（）：设（，），有（）（，），丄（）？，从而（）丄（）在的一邻域内，对充分大的，点（士，）处的函数值（）（），显然不是问题的局部最优解混合稀疏约束优化本节内容是对第节的推 广，研究？空间 中混合 稀疏约束优化问题的最优性 条件考虑 如下问题（）（）（），（），其中，和均为？到？的 实值函数，是正整数记集 合：？，（），（：；下面利用可行集的误差 界，将约束优化问题转化为无约束优化问题，得到类 似定理的局部性质定理考虑问题（），设仏函数在附近是的，记其常数为假设存在常数，及的一邻域使 得（，）（）（）（），（）那么为问题）的局部最优解当且仅当为函数（）会（）十知十（）会工）的局部 最小点证设为问题（）的局部 最优解，则存在的邻域）（心），使 得对任意的仏都 有（）（）在附近是的，记其邻域为（：）（和）则对任意的鲁）（工，警），存在之使 得（：）；，（）其中显然是一闭集由仏根 据投影的定义知由三角不等式可 得卜，从而（，）系统科学与数学卷对任意的）夸），结 合（）和（）式及在附近的性脱有（）（）（）（）（，）（）（）（）（）故为函数卽。）十会抖引）的局部 最小点反之，设为函数会（）十知十会的局部最小点，则存在，对任意的（：；（），都 有（）（）（）（）（）从而对任意的仏都 有（）（）故为问题（）的局部 最优 解基于上述定理，我们首先建立问题（的一阶必要 最优性 条件定理