A discrete particle swarm optimization method for feature selection in binary classification problems

This paper investigates the feature subset selection problem for the binary classification problem using logistic regression model. We developed a modified discrete particle swarm optimization (PSO) algorithm for the feature subset selection problem. This approach embodies an adaptive feature selection procedure which dynamically accounts for the relevance and dependence of the features included the feature subset. We compare the proposed methodology with the tabu search and scatter search algorithms using publicly available datasets. The results show that the proposed discrete PSO algorithm is competitive in terms of both classification accuracy and computational performance.     

半参数两样本密度比率模型估计问题的一点注记

In this paper,a semiparametric two-sample density ratio model is considered and the empirical likelihood method is applied to obtain the parameters estimation.A commonly occurring problem in computing is that the empirical likelihood function may be a concaveconvex function.Here a simple Lagrange saddle point algorithm is presented for computing the saddle point of the empirical likelihood function when the Lagrange multiplier has no explicit solution.So we can obtain the maximum empirical likelihood estimation (MELE) of parameters.Monte Carlo simulations are presented to illustrate the Lagrange saddle point algorithm.     

A Note on the Estimation of Semiparametric Two-Sample Density Ratio Models

In this paper,a semiparametric two-sample density ratio model is considered and the empirical likelihood method is applied to obtain the parameters estimation.A commonly occurring problem in computing is that the empirical likelihood function may be a concaveconvex function.Here a simple Lagrange saddle point algorithm is presented for computing the saddle point of the empirical likelihood function when the Lagrange multiplier has no explicit solution.So we can obtain the maximum empirical likelihood estimation (MELE) of parameters.Monte Carlo simulations are presented to illustrate the Lagrange saddle point algorithm.     

Saddle point methods,and alogorithms,for non-symmetric linear equations ∗

This paper describes methods for solving non-singular, non-symmetric linear equations whose symmetric part is positive definite. First, the solutions are characterized as saddle points of a convex-concave function. The associated primal and dual variational principles provide quadratic, strictly convex, functions whose minima are the solutions of the original equation and which generalize the energy function for symmetric problems.

Direct iterative methods for finding the saddle point are then developed and analyzed. A globally convergent algorithm for finding the saddle points is described. We show that requiring conjugacy of successive search directions with respect to the symmetric part of the equation is a poor strategy.     

The Saddle Point Problem of Polynomials

Foundations of Computational Mathematics - This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre’s...     

Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators

The majority of first-order methods for large-scale convex–concave saddle point problems and variational inequalities with monotone operators are proximal algorithms. To make such an algorithm practical, the problem’s domain should be proximal-friendly—admit a strongly convex function with easy to minimize linear perturbations. As a by-product, this domain admits a computationally cheap linear minimization oracle (LMO) capable to minimize linear forms. There are, however, important situations where a cheap LMO indeed is available, but the problem domain is not proximal-friendly, which motivates search for algorithms based solely on LMO. For smooth convex minimization, there exists a classical algorithm using LMO—conditional gradient. In contrast, known to us similar techniques for other problems with convex structure (nonsmooth convex minimization, convex–concave saddle point problems, even as simple as bilinear ones, and variational inequalities with monotone operators, even as simple as affine) are quite recent and utilize common approach based on Fenchel-type representations of the associated objectives/vector fields. The goal of this paper was to develop alternative (and seemingly much simpler) decomposition techniques based on LMO for bilinear saddle point problems and for variational inequalities with affine monotone operators.     

轴对称弹塑性扭转问题的数值解

在很多自由边界问题的研究中,变分不等式是一个有力的工具,它不但可以用来研究解的存在唯一性、正则性等理论问题,而且还提供了有效的数值方法(见[1-3]).对轴对称机轴的弹塑性扭转问题,[4,5]用变分不等式研究了解的存在唯一性和正则性,在此基础上,[6]建议用有限元法求解等价的障碍问题.该法的缺点是,事先要解一个一阶非线性偏微分方程的Cauchy问题以求出障碍函数,并且此Cauchy问题的解一般不唯一.本文的方法是直接将原来的变分不等式问题作有限元离散,再将离散问题化成鞍点问题,然后采用Uzawa型算法求解.这就避免了[6]中方法的上述困难.     

Searching the solution landscape by generalized high-index saddle dynamics

We introduce a generalized numerical algorithm to construct the solution landscape, which is a pathway map consisting of all the stationary points and their connections. Based on the high-index optimizationbased shrinking dimer(Hi OSD) method for gradient systems, a generalized high-index saddle dynamics(GHi SD)is proposed to compute any-index saddles of dynamical systems. Linear stability of the index-k saddle point can be proved for the GHi SD system. A combination of the downward search algorithm and the upward search algorithm is applied to systematically construct the solution landscape, which not only provides a powerful and efficient way to compute multiple solutions without tuning initial guesses, but also reveals the relationships between different solutions. Numerical examples, including a three-dimensional example and the phase field model, demonstrate the novel concept of the solution landscape by showing the connected pathway maps.     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

An exact feature selection algorithm based on rough set theory

Feature reduction based on rough set theory is an effective feature selection method in pattern recognition applications. Finding a minimal subset of the original features is inherent in rough set approach to feature selection. As feature reduction is a Nondeterministic Polynomial‐time‐hard problem, it is necessary to develop fast optimal or near‐optimal feature selection algorithms. This article aims to propose an exact feature selection algorithm in rough set that is efficient in terms of computation time. The proposed algorithm begins the examination of a solution tree by a breadth‐first strategy. The pruned nodes are held in a version of the trie data structure. Based on the monotonic property of dependency degree, all subsets of the pruned nodes cannot be optimal solutions. Thus, by detecting these subsets in trie, it is not necessary to calculate their dependency degree. The search on the tree continues until the optimal solution is found. This algorithm is improved by selecting an initial search level determined by the hill‐climbing method instead of searching the tree from the level below the root. The length of the minimal reduct and the size of data set can influence which starting search level is more efficient. The experimental results using some of the standard UCI data sets, demonstrate that the proposed algorithm is effective and efficient for data sets with more than 30 features. © 2014 Wiley Periodicals, Inc. Complexity 20: 50–62, 2015     

Convergence results for a self-dual regularization of convex problems

We study a one-parameter regularization technique for convex optimization problems whose main feature is self-duality with respect to the Legendre–Fenchel conjugation. The self-dual technique, introduced by Goebel, can be defined for both convex and saddle functions. When applied to the latter, we show that if a saddle function has at least one saddle point, then the sequence of saddle points of the regularized saddle functions converges to the saddle point of minimal norm of the original one. For convex problems with inequality and state constraints, we apply the regularization directly on the objective and constraint functions, and show that, under suitable conditions, the associated Lagrangians of the regularized problem hypo/epi-converge to the original Lagrangian, and that the associated value functions also epi-converge to the original one. Finally, we find explicit conditions ensuring that the regularized sequence satisfies Slater's condition.     

Mixed finite element analysis of semi-coercive unilateral contact problems with given friction

A unilateral contact 2D-problem is considered provided one of two elastic bodies can shift in a given direction as a rigid body. Using Lagrange multipliers for both normal and tangential constraints on the contact interface, we introduce a saddle point problem and prove its unique solvability. We discretize the problem by a standard finite element method and prove a convergence of approximations. We propose a numerical realization on the basis of an auxiliary “ bolted” problem and the algorithm of Uzawa.     

Higher Order Efficiency,Saddle Point Optimality,and Duality for Vector Optimization Problems

In this paper, we intend to characterize the strict local efficient solution of order m for a vector minimization problem in terms of the vector saddle point. A new notion of strict local saddle point of higher order of the vector-valued Lagrangian function is introduced. The relationship between strict local saddle point and strict local efficient solution is derived. Lagrange duality is formulated, and duality results are presented.     

Saddle points and scalarizing sets in multiple objective linear programming

The main purpose of this paper is to study saddle points of the vector Lagrangian function associated with a multiple objective linear programming problem. We introduce three concepts of saddle points and establish their characterizations by solving suitable systems of equalities and inequalities. We deduce dual programs and prove a relationship between saddle points and dual solutions, which enables us to obtain an explicit expression of the scalarizing set of a given saddle point in terms of normal vectors to the value set of the problem. Finally, we present an algorithm to compute saddle points associated with non-degenerate vertices and the corresponding scalarizing sets.     

An efficient method for feature selection in linear regression based on an extended Akaike’s information criterion

A method for feature selection in linear regression based on an extension of Akaike’s information criterion is proposed. The use of classical Akaike’s information criterion (AIC) for feature selection assumes the exhaustive search through all the subsets of features, which has unreasonably high computational and time cost. A new information criterion is proposed that is a continuous extension of AIC. As a result, the feature selection problem is reduced to a smooth optimization problem. An efficient procedure for solving this problem is derived. Experiments show that the proposed method enables one to efficiently select features in linear regression. In the experiments, the proposed procedure is compared with the relevance vector machine, which is a feature selection method based on Bayesian approach. It is shown that both procedures yield similar results. The main distinction of the proposed method is that certain regularization coefficients are identical zeros. This makes it possible to avoid the underfitting effect, which is a characteristic feature of the relevance vector machine. A special case (the so-called nondiagonal regularization) is considered in which both methods are identical.     

向量最优化问题的Lagrange对偶与择一定理

本文讨论无限维向量最优化问题的Lagrange对偶与弱对偶，建立了若干鞍点定理与弱鞍点定理．作为研究对偶问题的工具，建立了一个新的择一定理．     

Fast Iterative Solution of Saddle Point Problems in Optimal Control Based on Wavelets

In this paper, wavelet techniques are employed for the fast numerical solution of a control problem governed by an elliptic boundary value problem with boundary control. A quadratic cost functional involving natural norms of the state and the control is to be minimized. Firstly the constraint, the elliptic boundary value problem, is formulated in an appropriate weak form that allows to handle varying boundary conditions explicitly: the boundary conditions are treated by Lagrange multipliers, leading to a saddle point problem. This is combined with a fictitious domain approach in order to cover also more complicated boundaries.Deviating from standard approaches, we then use (biorthogonal) wavelets to derive an equivalent infinite discretized control problem which involves only ₂-norms and -operators. Classical methods from optimization yield the corresponding optimality conditions in terms of two weakly coupled (still infinite) saddle point problems for which a unique solution exists. For deriving finite-dimensional systems which are uniformly invertible, stability of the discretizations has to be ensured. This together with the ₂-setting circumvents the problem of preconditioning: all operators have uniformly bounded condition numbers independent of the discretization.In order to numerically solve the resulting (finite-dimensional) linear system of the weakly coupled saddle point problems, a fully iterative method is proposed which can be viewed as an inexact gradient scheme. It consists of a gradient algorithm as an outer iteration which alternatingly picks the two saddle point problems, and an inner iteration to solve each of the saddle point problems, exemplified in terms of the Uzawa algorithm. It is proved here that this strategy converges, provided that the inner systems are solved sufficiently well. Moreover, since the system matrix is well-conditioned, it is shown that in combination with a nested iteration strategy this iteration is asymptotically optimal in the sense that it provides the solution on discretization level J with an overall amount of arithmetic operations that is proportional to the number of unknows N _J on that level.Finally, numerical results are provided.     

精确罚函数和极小极大问题

在这篇文章中我们研究了对于不等式约束的非线性规划问题如何根据极小极大问题的鞍点来找精确罚问题的解。对于一个具有不等式约束的非线性规划问题,通过罚函数,我们构造出一个极小极大问题,应用交换“极小”或“极大”次序的策略,证明了罚问题的鞍点定理。研究结果显示极小极大问题的鞍点是精确罚问题的解。     

一种基于邻近点算法的变步长原始-对偶算法

本文考虑求解一种源于信号及图像处理问题的鞍点问题.基于邻近点算法的思想,我们对原始-对偶算法进行改进,构造一种对称正定且可变的邻近项矩阵,得到一种新的原始-对偶算法.新算法可以看成一种邻近点算法,因此它的收敛性易于分析,且无需较强的假设条件.初步实验结果表明,当新算法被应用于求解图像去模糊问题时,和其他几种主流的高效算法相比,新算法能得到较高质量的结果,且计算时间也是有竞争力的.     

An Interior Point Algorithm for Computing Saddle Points of Constrained Continuous Minimax

The aim of this paper is to present an algorithm for finding a saddle point to the constrained minimax problem. The initial problem is transformed into an equivalent equality constrained problem, and then the interior point approach is used. To satisfy the original inequality constraints a logarithmic barrier function is used and special care is given to step size parameter to keep the variables within permitted boundaries. Numerical results illustrating the method are given.