A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training

Support vector machines (SVMs) training may be posed as a large quadratic program (QP) with bound constraints and a single linear equality constraint. We propose a (block) coordinate gradient descent method for solving this problem and, more generally, linearly constrained smooth optimization. Our method is closely related to decomposition methods currently popular for SVM training. We establish global convergence and, under a local error bound assumption (which is satisfied by the SVM QP), linear rate of convergence for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We show that, for the SVM QP with n variables, this rule can be implemented in O(n) operations using Rockafellar’s notion of conformal realization. Thus, for SVM training, our method requires only O(n) operations per iteration and, in contrast to existing decomposition methods, achieves linear convergence without additional assumptions. We report our numerical experience with the method on some large SVM QP arising from two-class data classification. Our experience suggests that the method can be efficient for SVM training with nonlinear kernel.     

使用自正则度量的凸二次规划的原始对偶内点法的多项式复杂性

最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(n√log n log (n/ε)).     

Learning the coordinate gradients

In this paper we study the problem of learning the gradient function with application to variable selection and determining variable covariation. Firstly, we propose a novel unifying framework for coordinate gradient learning from the perspective of multi-task learning. Various variable selection methods can be regarded as special instances of this framework. Secondly, we formulate the dual problems of gradient learning with general loss functions. This enables the direct application of standard optimization toolboxes to the case of gradient learning. For instance, gradient learning with SVM loss can be solved by quadratic programming (QP) routines. Thirdly, we propose a novel gradient learning formulation which can be cast as a learning the kernel matrix problem. Its relation with sparse regularization is highlighted. A semi-infinite linear programming (SILP) approach and an iterative optimization approach are proposed to efficiently solve this problem. Finally, we validate our proposed approaches on both synthetic and real datasets.     

The projection method of optimization applied to engineering plasticity problems

In engineering plasticity, the behavior of a structure (e.g., a frame or truss) under a variety of loading conditions is studied. Two primary types of analysis are generally conducted. Limit analysis determines the rigid plastic collapse load for a structure and can be formulated as a linear program (LP). Deformation analysis at plastic collapse can be formulated as a quadratic program (QP). The constraints of the two optimization problems are closely related. This paper presents a specialization of the projection method for linear programming for the limit-load analysis problem. The algorithm takes advantage of the relationship between the LP constraints and QP constraints to provide advantageous starting data for the projection method applied to the QP problem. An important feature of the method is that it avoids problems of apparent infeasibility due to roundoff errors. Experimental results are given for two medium-sized problems.This work was supported by the National Research Council of Canada under Research Grant No. A8189.     

Reducing quadratic programming problem to regression problem: Stepwise algorithm

Quadratic programming is concerned with minimizing a convex quadratic function subject to linear inequality constraints. The variables are assumed to be nonnegative. The unique solution of quadratic programming (QP) problem (QPP) exists provided that a feasible region is non-empty (the QP has a feasible space).A method for searching for the solution to a QP is provided on the basis of statistical theory. It is shown that QPP can be reduced to an appropriately formulated least squares (LS) problem (LSP) with equality constraints and nonnegative variables. This approach allows us to obtain a simple algorithm to solve QPP. The applicability of the suggested method is illustrated with numerical examples.     

一类全局优化问题的线性化方法

本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解.     

On an inverse linear programming problem

A method for solving the following inverse linear programming (LP) problem is proposed. For a given LP problem and one of its feasible vectors, it is required to adjust the objective function vector as little as possible so that the given vector becomes optimal. The closeness of vectors is estimated by means of the Euclidean vector norm. The inverse LP problem is reduced to a problem of unconstrained minimization for a convex piecewise quadratic function. This minimization problem is solved by means of the generalized Newton method.     

A Perturbation approach for an inverse quadratic programming problem

We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC¹) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC¹ function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.     

A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations

Existing global optimization techniques for nonconvex quadratic programming (QP) branch by recursively partitioning the convex feasible set and thus generate an infinite number of branch-and-bound nodes. An open question of theoretical interest is how to develop a finite branch-and-bound algorithm for nonconvex QP. One idea, which guarantees a finite number of branching decisions, is to enforce the first-order Karush-Kuhn-Tucker (KKT) conditions through branching. In addition, such an approach naturally yields linear programming (LP) relaxations at each node. However, the LP relaxations are unbounded, a fact that precludes their use. In this paper, we propose and study semidefinite programming relaxations, which are bounded and hence suitable for use with finite KKT-branching. Computational results demonstrate the practical effectiveness of the method, with a particular highlight being that only a small number of nodes are required. This author was supported in part by NSF Grants CCR-0203426 and CCF-0545514.     

解带有二次约束二次规划的一个整体优化方法

在本文中，我们提出了一种解带有二次约束二次规划问题（QP）的新算法，这种方法是基于单纯形分枝定界技术，其中包括极小极大问题和线性规划问题作为子问题，利用拉格朗日松弛和投影次梯度方法来确定问题（QP）最优值的下界，在问题（QP）的可行域是n维的条件下，如果这个算法有限步后终止，得到的点必是问题（QP）的整体最优解；否则，该算法产生的点的序列{v^k}的每一个聚点也必是问题（QP）的整体最优解。     

A feasible filter SQP algorithm with global and local convergence

A feasible sequential quadratic programming (SQP) filter algorithm is proposed for general nonlinear programming. It is based on the modified quadratic programming (QP) subproblem in which each iteration proceeds in two phases. The first phase solves a general convex QP problem which does not require any feasibility restoration phase whose computation may be expensive. And, under some mild conditions, the global convergence is proved. The second phase can make the presented SQP method derive quadratic convergence by employing exact Hessian information.     

MOP/GP models for machine learning

Techniques for machine learning have been extensively studied in recent years as effective tools in data mining. Although there have been several approaches to machine learning, we focus on the mathematical programming (in particular, multi-objective and goal programming; MOP/GP) approaches in this paper. Among them, Support Vector Machine (SVM) is gaining much popularity recently. In pattern classification problems with two class sets, its idea is to find a maximal margin separating hyperplane which gives the greatest separation between the classes in a high dimensional feature space. This task is performed by solving a quadratic programming problem in a traditional formulation, and can be reduced to solving a linear programming in another formulation. However, the idea of maximal margin separation is not quite new: in the 1960s the multi-surface method (MSM) was suggested by Mangasarian. In the 1980s, linear classifiers using goal programming were developed extensively.This paper presents an overview on how effectively MOP/GP techniques can be applied to machine learning such as SVM, and discusses their problems.     

Globally solving nonconvex quadratic programming problems via completely positive programming

Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.     

Identifying the optimal partition in convex quadratic programming

Given an optimal solution for a convex quadratic programming (QP) problem, the optimal partition of the QP can be computed by solving a pair of linear or QP problems for which nearly optimal solutions are known.     

Linear programming approaches for multicategory support vector machines

We consider linear programming approaches for support vector machines (SVM). The linear programming problems are introduced as an approximation of the quadratic programming problems commonly used in SVM. When we consider the kernel based nonlinear discriminators, the approximation can be viewed as kernel principle component analysis which generates an important subspace from the feature space characterized the kernel function. We show that any data points nonlinearly, and implicitly, projected into the feature space by kernel functions can be approximately expressed as points lying a low dimensional Euclidean space explicitly, which enables us to develop linear programming formulations for nonlinear discriminators. We also introduce linear programming formulations for multicategory classification problems. We show that the same maximal margin principle exploited in SVM can be involved into the linear programming formulations. Moreover, considering the low dimensional feature subspace extraction, we can generate nonlinear multicategory discriminators by solving linear programming problems.Numerical experiments on real world datasets are presented. We show that the fairly low dimensional feature subspace can achieve a reasonable accuracy, and that the linear programming formulations calculate discriminators efficiently. We also discuss a sampling strategy which might be crucial for huge datasets.     

Kernel Logistic Regression and the Import Vector Machine

The support vector machine (SVM) is known for its good performance in two-class classification, but its extension to multiclass classification is still an ongoing research issue. In this article, we propose a new approach for classification, called the import vector machine (IVM), which is built on kernel logistic regression (KLR). We show that the IVM not only performs as well as the SVM in two-class classification, but also can naturally be generalized to the multiclass case. Furthermore, the IVM provides an estimate of the underlying probability. Similar to the support points of the SVM, the IVM model uses only a fraction of the training data to index kernel basis functions, typically a much smaller fraction than the SVM. This gives the IVM a potential computational advantage over the SVM.     

An Exterior Newton Method for Strictly Convex Quadratic Programming

We propose an exterior Newton method for strictly convex quadratic programming (QP) problems. This method is based on a dual formulation: a sequence of points is generated which monotonically decreases the dual objective function. We show that the generated sequence converges globally and quadratically to the solution (if the QP is feasible and certain nondegeneracy assumptions are satisfied). Measures for detecting infeasibility are provided. The major computation in each iteration is to solve a KKT-like system. Therefore, given an effective symmetric sparse linear solver, the proposed method is suitable for large sparse problems. Preliminary numerical results are reported.     

A Predictor-corrector algorithm with multiple corrections for convex quadratic programming

Recently an infeasible interior-point algorithm for linear programming (LP) was presented by Liu and Sun. By using similar predictor steps, we give a (feasible) predictor-corrector algorithm for convex quadratic programming (QP). We introduce a (scaled) proximity measure and a dynamical forcing factor (centering parameter). The latter is used to force the duality gap to decrease. The algorithm can decrease the duality gap monotonically. Polynomial complexity can be proved and the result coincides with the best one for LP, namely, $O(\sqrt{n}\log n\mu^{0}/\varepsilon)$ .     

An Effective Decomposition Procedure for Computing Equilibrium Single Commodity Trade Flows

The objective is to compute equilibrium interregional trade flows in relation to approximately linear supply and demand curves for a single commodity. There are n regions on a network characterized by approximately linear interregional transportation costs. Quadratic programming approaches can be greatly simplified by exploiting the special structure of the problem. This paper shows how the reduced quadratic program can then be partitioned using Benders decomposition. The computation then involves solving relatively small transportation problems and quadratic programming problems. Numerical experiments show the method to be effective in reducing computational requirements.     

基于支持向量机的磨粒识别

由于神经网络的局限性,上个世纪末,支持向量机被提出和发展,它在模式识别方面有广泛的应用发展前途,并由最初的二元分类发展到现在的多元分类.本文根据支持向量机的最新发展,把最小二乘支持向量机应用在磨粒识别上,并取得了好的结果.