Font Size: a A A

Aggregate Homotopy Methods For Min-Max-Min Programming With Applications In Data Mining

Posted on:2010-07-04Degree:DoctorType:Dissertation
Country:ChinaCandidate:H J XiongFull Text:PDF
GTID:1100360302960465Subject:Computational Mathematics
Abstract/Summary:PDF Full Text Request
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.
Keywords/Search Tags:min-max-min programming, Aggregate function, Homotopy method, Non-smooth semi-infinite programming, Support vector machines
PDF Full Text Request
Related items