【作者】 熊慧娟；

【导师】 于波；

【作者基本信息】 大连理工大学 ， 计算数学， 2009， 博士

【摘要】 min-max-min规划是一类重要的非光滑非凸优化问题,在工程优化设计、电子线路设计、数据挖掘等领域有着重要应用.本文的工作在已有的凝聚同伦算法的基础上进行.第一章主要介绍min-max-min规划模型及其应用背景,并回顾一些相关理论与算法.第二章提出了数值跟踪凝聚同伦的一个基于截断策略的高效率算法.在算法的每步迭代,只用到max-min函数的组成函数中的一小部分的凝聚函数,这一部分组成函数对应的下标集合在每步迭代过程中随着截断精度控制准则自适应调整.以尽可能地减少函数的梯度及海赛阵的计算量.我们给出保持校正算法的二次收敛性和预估步的有效性的截断凝聚精度控制准则,该精度控制准则不涉及梯度和海赛阵的计算.只与max-min函数的组成函数的函数值有关.基于该精度控制准则,我们证明了截断凝聚同伦算法的收敛性及每步校正的局部二次收敛性.第三章基于二次凝聚函数,对min-max-min规划构造了一种动约束函数,使得原问题的可行集可以由一个凸球约束连续形变过去,进而给出了一类新的凝聚形变同伦方法.新算法不要求可行集满足弱法锥条件,并且不要求初始点是内点.第四章基于离散化相容逼近的策略,将半无限min-max-min问题转化为有限min-max-min规划问题,再用截断凝聚同伦方法求解.可以证明:当离散点充分稠密时.离散化子问题的稳定点是原问题的6-次稳定点.第五章将半无限min-max-min问题写成一个双层规划问题.在底层问题严格凸的假设下,建立了原问题的一阶最优性条件,并构造凝聚同伦方法求解该问题.在一定条件下.可以证明通向原问题的广义KKT点的光滑同伦路径的存在性和收敛性.第六章考虑了截断凝聚同伦算法在数据挖掘的支持向量机模型求解中的一些应用.首先考虑了半监督分类问题.将已有的求解半监督分类问题的一个支持向量机模型加以变形,得到一个由max型以及max-min型的非光滑函数组合得到的无约束非光滑非凸优化问题,并构造了截断凝聚同伦算法求解该模型.其次考虑了多示例分类问题.该问题是线性min-max-min规划问题,即组成函数均为线性函数.我们证明该问题满足弱法锥条件,因此可以用截断凝聚同伦方法求解该问题.文中所有的算法,都用Matlab编程实现,并通过数值实验与已有的一些算法相比较,结果表明本文给出的算法是有效的.更多还原

【Abstract】 Min-max-min programming is a kind of important nonsmooth problem that appears in various fields such as engineering optimization design, circuit design and data mining. The thesis is based on the existing aggregate homotopy method, it consists of the following sections:In Chapter 1. min-max-min programming problem with its application ground is formulated, and some results on related theory and algorithms are recalled.In Chapter 2, by giving a truncated aggregate strategy, an efficient truncate aggregate method for numerically tracing aggregate homotopy path is introduced. At every iteration, only a part of component functions are used to make aggregate smoothing approximation, whose index set is updated adaptively with a truncated aggregate criterion. The criterion concerns only with computation of component functions value, not their gradients or Hessian. Based on the criterion, the convergence of the truncated aggregate homotopy method and locally quadratic convergence of the corrector iterations at every step are discussed.In Chapter 3, using twice aggregate function, a new aggregate deformation homotopy method is established to solve min-max-min programming. Compared to aggregate homotopy method, the new method doesn’t require the weak normal cone condition and doesn’t require an interior initial point.In Chapter 4. based on the well known discretized consistent approximate strategy, a semi-infinite min-max-min programming is approximated by finite min-max-min problems. It’s proven that anε-substationary point can be obtained by solving some dense enough min-max-min programming with truncated aggregate homotopy method.In Chapter 5, a semi-infinite min-max-min problem is reformulated into a special bi-level problem. Under an assumption that the lower level problem is a strictly convex problem, a first-order Optimality condition of the original problem is given. An aggregate homotopy is established for solving the problem. It’s proven that the homotopy determines a smooth path, which approaching to a solution of a generalized KKT point of the original problem.In the last section, some applications of the aggregate homotopy method arc discussed. Firstly, a reformulation of the semi-supervised support vector machines is given. An uncon- strained nonsmooth problem with max type and max-min type is obtained. Utilizing the truncated aggregate technique, an implementation procedure is presented. Secondly, some considerations on the weak normal cone condition are given. It’s proven that multiple-instance support vector machines satisfies the condition. As a result, truncated aggregate homotopy method is feasible for it.All methods in the thesis are implemented by Matlab software. Some numerical comparisons are given to show the efficiency of the methods.更多还原