Support vector machine via nonlinear rescaling method

In this paper we construct the linear support vector machine (SVM) based on the nonlinear rescaling (NR) methodology (see [Polyak in Math Program 54:177–222, 1992; Polyak in Math Program Ser A 92:197–235, 2002; Polyak and Teboulle in Math Program 76:265–284, 1997] and references therein). The formulation of the linear SVM based on the NR method leads to an algorithm which reduces the number of support vectors without compromising the classification performance compared to the linear soft-margin SVM formulation. The NR algorithm computes both the primal and the dual approximation at each step. The dual variables associated with the given data-set provide important information about each data point and play the key role in selecting the set of support vectors. Experimental results on ten benchmark classification problems show that the NR formulation is feasible. The quality of discrimination, in most instances, is comparable to the linear soft-margin SVM while the number of support vectors in several instances were substantially reduced.     

An embedding domain approach for a class of 2-d shape optimization problems: mathematical analysis

This contribution combines a shape optimization approach to free boundary value problems of Bernoulli type with an embedding domain technique. A theoretical framework is developed which allows to prove continuous dependence of the primal and dual variables in the resulting saddle point problems with respect to the domain. This ensures the existence of a solution of a related shape optimization problem in a sufficiently large class of admissible domains.     

Asymptotic Properties of Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.     

Branch and win: OR tree search algorithms for solving combinatorial optimisation problems

Currently, most combinatorial optimisation problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. We propose Branch and Win, a general formulation for understanding and synthesising the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. Several general ideas are also presented, whose application allows designing new hybrid search algorithms, in order to implement the procedure.     

Algorithms for Finite and Semi-Infinite Min–Max–Min Problems Using Adaptive Smoothing Techniques

We develop two implementable algorithms, the first for the solution of finite and the second for the solution of semi-infinite min-max-min problems. A smoothing technique (together with discretization for the semi-infinite case) is used to construct a sequence of approximating finite min-max problems, which are solved with increasing precision. The smoothing and discretization approximations are initially coarse, but are made progressively finer as the number of iterations is increased. This reduces the potential ill-conditioning due to high smoothing precision parameter values and computational cost due to high levels of discretization. The behavior of the algorithms is illustrated with three semi-infinite numerical examples.     

Logic-Based Modeling and Solution of Nonlinear Discrete/Continuous Optimization Problems

This paper presents a review of advances in the mathematical programming approach to discrete/continuous optimization problems. We first present a brief review of MILP and MINLP for the case when these problems are modeled with algebraic equations and inequalities. Since algebraic representations have some limitations such as difficulty of formulation and numerical singularities for the nonlinear case, we consider logic-based modeling as an alternative approach, particularly Generalized Disjunctive Programming (GDP), which the authors have extensively investigated over the last few years. Solution strategies for GDP models are reviewed, including the continuous relaxation of the disjunctive constraints. Also, we briefly review a hybrid model that integrates disjunctive programming and mixed-integer programming. Finally, the global optimization of nonconvex GDP problems is discussed through a two-level branch and bound procedure.     

On the Image Regularity Condition

In this paper, we continue the analysis of the image regularity condition (IRC) as introduced in a previous paper where we have proved that IRC implies the existence of generalized Lagrange-John multipliers with first component equal to 1. The term generalized is connected with the fact that the separation (in the image space) is not necessarily linear (when we have classic Lagrange-John multipliers), but it can be also nonlinear. Here, we prove that the IRC guarantees, also in the nondifferentiable case, the fact that 0 is a solution of the first-order homogeneized (linearized) problem obtained by means of the Dini-Hadamard derivatives.     

Finding Robust Solutions Using Local Search

This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature. This revised version was published online in August 2006 with corrections to the Cover Date.     

Proper Efficiency in Vector Optimization on Real Linear Spaces

In this paper, we use an algebraic type of closure, which is called vector closure, and through it we introduce some adaptations to the proper efficiency in the sense of Hurwicz, Benson, and Borwein in real linear spaces without any particular topology. Scalarization, multiplier rules, and saddle-point theorems are obtained in order to characterize the proper efficiency in vector optimization with and without constraints. The usual convexlikeness concepts used in such theorems are weakened through the vector closure.     

基于指数分布的进化策略

典型的进化策略受自然进化过程的启发而成为求解全局优化问题的重要方法。传统的ES变异算子作为一个主要的进化技术是建立在正态分布的随机变量基础上的，本文提出了基于指数分布的进化策略由于采用了新的变异算子有效地减少了产生探试解的成本，从而优于传统的进化策略。