Nondegenerate piecewise linear systems: a finite Newton algorithm and applications in machine learning

We investigate Newton-type optimization methods for solving piecewise linear systems (PLSs) with nondegenerate coefficient matrix. Such systems arise, for example, from the numerical solution of linear complementarity problem, which is useful to model several learning and optimization problems. In this letter, we propose an effective damped Newton method, PLS-DN, to find the exact (up to machine precision) solution of nondegenerate PLSs. PLS-DN exhibits provable semiiterative property, that is, the algorithm converges globally to the exact solution in a finite number of iterations. The rate of convergence is shown to be at least linear before termination. We emphasize the applications of our method in modeling, from a novel perspective of PLSs, some statistical learning problems such as box-constrained least squares, elitist Lasso (Kowalski & Torreesani, 2008), and support vector machines (Cortes & Vapnik, 1995). Numerical results on synthetic and benchmark data sets are presented to demonstrate the effectiveness and efficiency of PLS-DN on these problems.     

Dual coordinate descent methods for logistic regression and maximum entropy models

Most optimization methods for logistic regression or maximum entropy solve the primal problem. They range from iterative scaling, coordinate descent, quasi-Newton, and truncated Newton. Less efforts have been made to solve the dual problem. In contrast, for linear support vector machines (SVM), methods have been shown to be very effective for solving the dual problem. In this paper, we apply coordinate descent methods to solve the dual form of logistic regression and maximum entropy. Interestingly, many details are different from the situation in linear SVM. We carefully study the theoretical convergence as well as numerical issues. The proposed method is shown to be faster than most state of the art methods for training logistic regression and maximum entropy.     

On extreme learning machine for ε-insensitive regression in the primal by Newton method

In this paper, extreme learning machine (ELM) for ε-insensitive error loss function-based regression problem formulated in 2-norm as an unconstrained optimization problem in primal variables is proposed. Since the objective function of this unconstrained optimization problem is not twice differentiable, the popular generalized Hessian matrix and smoothing approaches are considered which lead to optimization problems whose solutions are determined using fast Newton–Armijo algorithm. The main advantage of the algorithm is that at each iteration, a system of linear equations is solved. By performing numerical experiments on a number of interesting synthetic and real-world datasets, the results of the proposed method are compared with that of ELM using additive and radial basis function hidden nodes and of support vector regression (SVR) using Gaussian kernel. Similar or better generalization performance of the proposed method on the test data in comparable computational time over ELM and SVR clearly illustrates its efficiency and applicability.     

拉格朗日支持向量回归的有限牛顿算法

拉格朗日支持向量回归是一种有效的快速回归算法,求解时需要对维数等于样本数加一的矩阵求逆,求解需要较多的迭代次数才能收敛。采用一种Armijo步长有限牛顿迭代算法求解拉格朗日支持向量回归的优化问题,只需有限次求解一组线性等式而不需要求解二次规划问题,该方法具有全局收敛和有限步终止的性质。在多个标准数据集上的实验验证了所提算法的有效性和快速性。     

An improved robust and sparse twin support vector regression via linear programming

Twin support vector regression (TSVR) was proposed recently as a novel regressor that tries to find a pair of nonparallel planes, i.e. \(\epsilon \) -insensitive up- and down-bounds, by solving two related SVM-type problems. Though TSVR exhibits good performance compared with conventional methods like SVR, it suffers from the following issues: (1) it lacks model complexity control and thus may incur overfitting and suboptimal solution; (2) it needs to solve a pair of quadratic programming problems which are relatively complex to implement; (3) it is sensitive to outliers; and (4) its solution is not sparse. To address these problems, we propose in this paper a novel regression algorithm termed as robust and sparse twin support vector regression. The central idea is to reformulate TSVR as a convex problem by introducing regularization technique first and then derive a linear programming (LP) formulation which is not only simple but also allows robustness and sparseness. Instead of solving the resulting LP problem in the primal, we present a Newton algorithm with Armijo step-size to resolve the corresponding exact exterior penalty problem. The experimental results on several publicly available benchmark data sets show the feasibility and effectiveness of the proposed method.     

An adaptive nonmonotone truncated Newton method for optimal control of a class of parabolic distributed parameter systems

A black-box method using the finite elements, the Crank–Nicolson and a nonmonotone truncated Newton (TN) method is presented for solving optimal control problems (OCPs) governed by partial differential equations (PDEs). The proposed method finds the optimal control of a class of linear and nonlinear parabolic distributed parameter systems with a quadratic cost functional. To this end, the piecewise linear finite elements method and the well-known Crank–Nicolson method are used for discretizing in space and in time, respectively. Afterwards, regarding the implicit function theorem (IFT), the optimal control problem is transformed into an unconstrained nonlinear optimization problem. Considering that in a gradient-based method for solving optimal control problems, the evaluations of gradients and Hessians of the cost functional is important, hence, an adjoint technique is used to evaluate them effectively. In addition, to make a globalization strategy, we first introduce an adaptive nonmonotone strategy which properly controls the degree of nonmonotonicity and then incorporate it into an inexact Armijo-type line search approach to construct a more relaxed line search procedure. Finally, the obtained unconstrained nonlinear optimization problem is solved by utilizing the proposed nonmonotone truncated Newton method. Results gained from the new offered method compared with existing methods show that the new method is promising.     

无偏置支持向量回归优化问题

为了研究偏置对支持向量回归(support vector regression,简称SVR)问题泛化性能的影响,首先提出了无偏置SVR(NBSVR)的优化问题及其对偶问题.推导出了NBSVR优化问题全局最优解的必要条件,然后证明了SVR的对偶问题只能得到NBSVR对偶问题的次优解.同时提出了NBSVR的有效集求解算法,并证明了它是线性收敛的.基于21个标准数据集的实验结果表明,在对偶问题解空间上,有偏置支持向量回归算法只能得到无偏置支持向量回归算法的次优解,NBSVR的均方根误差要低于SVR.NBSVR的训练时间不仅低于SVR,而且对核参数变化不太敏感.     

基于支持向量机的股市预测

针对股票市场高燥声、强非线性和不确定性等特点和以往传统神经网络预测方法存在的不足,提出了一种基于支持向量机的股市预测方法。该方法主要运用了支持向量机回归的方法结合滚动时间窗来学习建摸。首先通过把低维输入空间的输入向量映射到高维特征空间,将非线性问题转化为线性,然后在结构风险最小化原则下进行二次规划,并求得最优解,从而建立模型。从仿真实验中可以看到,该方法建立的模型较为准确地预测了600009、000815两只股票的日均价,表现出了较强的泛化能力。     

Iterative support vector machine with guaranteed accuracy and run time

Abstract: Using a conjugate gradient method, a novel iterative support vector machine (FISVM) is proposed, which is capable of generating a new non‐linear classifier. We attempt to solve a modified primal problem of proximal support vector machine (PSVM) and show that the solution of the modified primal problem reduces to solving just a system of linear equations as opposed to a quadratic programming problem in SVM. This algorithm not only has no requirement for special optimization solvers, such as linear or quadratic programming tools, but also guarantees fast convergence. The full algorithm merely needs four lines of MATLAB codes, which gives results that are similar to or better than that of several new learning algorithms, in terms of classification accuracy. Besides, the proposed stand‐alone approach is capable of dealing with instability of classification performance of smooth support vector machine, generalized proximal support vector machine, PSVM and reduced support vector machine. Experiments carried out on UCI datasets show the effectiveness of our approach.     

基于线性规划支持向量回归的混沌系统预测

支持向量机是一种基于统计学习理论的新颖的机器学习方法,该方法已经广泛用于解决分类与回归问题。标准的支持向量机算法需要解一个二次规划问题,当训练样本较多时,其运算速度一般很慢。为了提高运算速度,介绍了一种基于线性规划的支持向量回归算法,并由此提出几种新的回归模型,同时将它们应用到混沌时间序列预测中,并比较了它们的预测性能。在实际应用中,可以根据具体情况灵活地选择所需模型。     

求解非线性回归问题的Newton算法

针对大规模非线性回归问题,提出基于静态储备池的Newton算法.利用储备池搭建高维特征空间,将原始问题转化成与储备池维数相关的线性支持向量回归问题,并应用Newton算法求解.鲁棒损失函数的应用可抑制异常点对预测结果的干扰.通过与SVR(Support Vector Regression)及储备池Tikhonov正则化方法比较,验证了所提方法的快速性、较高的预测精度和较好的鲁棒性.     

Least squares support vector regression for solving Volterra integral equations

In this paper, a numerical approach is proposed based on least squares support vector regression for solving Volterra integral equations of the first and second kind. The proposed method is based on using a hybrid of support vector regression with an orthogonal kernel and Galerkin and collocation spectral methods. An optimization problem is derived and transformed to solving a system of algebraic equations. The resulting system is discussed in terms of the structure of the involving matrices and the error propagation. Numerical results are presented to show the sparsity of resulting system as well as the efficiency of the method.

     

基于向量集约简的精简支持向量机

目前的支持向量集约简法在寻找约简向量的过程中需要求解一个无约束的多参数优化问题,这样,像其他非线性优化问题一样,求解过程需要面对数值不稳定或局部最小值问题.为此,提出了一种基于核聚类的SVM(support vector machine)简化方法.此方法首先在特征空间中对支持向量进行聚类,然后寻找特征空间中的聚类中心在输入空间中的原像以形成约简向量集.该方法概念简单,在简化过程中只需求解线性代数问题,从而解决了现存方法存在的瓶颈问题.实验结果表明,该简化法能够在基本保持SVM泛化性能的情况下极大地约简支持向量,从而提高SVM的分类速度.     

State waypoint approach to continuous‐time nonlinear optimal control problems

In this paper, we propose an optimal control technique for a class of continuous‐time nonlinear systems. The key idea of the proposed approach is to parametrize continuous state trajectories by sequences of a finite number of intermediate target states; namely, waypoint sequences. It is shown that the optimal control problem for transferring the state from one waypoint to the next is given an explicit‐form suboptimal solution, by means of linear approximation. Thus the original continuous‐time nonlinear control problem reduces to a finite‐dimensional optimization problem of waypoint sequences. Any efficient numerical optimization method, such as the interior‐reflection Newton method, can be applied to solve this optimization problem. Finally, we solve the optimal control problem for a simple nonlinear system example to illustrate the effectiveness of this approach. Copyright © 2009 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

基于多项式光滑的支持向量回归机

把支持向量回归机中的原始凸二次规划问题转化为光滑的无约束问题．构建了无约束支持向量回归机．使得许多成熟有效的无约束最优化算法能够应用到支持向量回归机中去。提出了一种光滑支持向量回归算法．实验结果表明．它相对于其它回归训练方法有较快的收敛速度和较高的拟合精度．     

基于多项式光滑的支持向量回归机

把支持向量回归机中的原始凸二次规划问题转化为光滑的无约束问题,构建了无约束支持向量回归机,使得许多成熟有效的无约束最优化算法能够应用到支持向量回归机中去。提出了一种光滑支持向量回归算法,实验结果表明,它相对于其它回归训练方法有较快的收敛速度和较高的拟合精度。     

KPCA-LSSVM建模方法及在钢材淬透性中的应用研究

通过等式约束条件修改普通的支持向量机可以得到最小二乘支持向量机，不需要再次求解复杂的二次规划问题,提出了利用核主元分析进行特征提取，在高维特征空间中计算主元，降低样本的维数，然后用最小二乘支持向量机进行建模．仿真结果表明了该方法的有效性和优越性．     

A Fast 2D Shape Recovery Approach by Fusing Features and Appearance

In this paper, we present a fusion approach to solve the nonrigid shape recovery problem, which takes advantage of both the appearance information and the local features. We have two major contributions. First, we propose a novel progressive finite Newton optimization scheme for the feature-based nonrigid surface detection problem, which is reduced to only solving a set of linear equations. The key is to formulate the nonrigid surface detection as an unconstrained quadratic optimization problem that has a closed-form solution for a given set of observations. Second, we propose a deformable Lucas-Kanade algorithm that triangulates the template image into small patches and constrains the deformation through the second-order derivatives of the mesh vertices. We formulate it into a sparse regularized least squares problem, which is able to reduce the computational cost and the memory requirement. The inverse compositional algorithm is applied to efficiently solve the optimization problem. We have conducted extensive experiments for performance evaluation on various environments, whose promising results show that the proposed algorithm is both efficient and effective.     

Newton-conjugate gradient （CG） augmented Lagrangian method for path constrained dynamic process optimization

In this paper, a Newton-conjugate gradient (CG) augmented Lagrangian method is proposed for solving the path constrained dynamic process optimization problems. The path constraints are simplified as a single final time constraint by using a novel constraint aggregation function. Then, a control vector parameterization (CVP) approach is applied to convert the constraints simplified dynamic optimization problem into a nonlinear programming (NLP) problem with inequality constraints. By constructing an augmented Lagrangian function, the inequality constraints are introduced into the augmented objective function, and a box constrained NLP problem is generated. Then, a linear search Newton-CG approach, also known as truncated Newton (TN) approach, is applied to solve the problem. By constructing the Hamiltonian functions of objective and constraint functions, two adjoint systems are generated to calculate the gradients which are needed in the process of NLP solution. Simulation examples demonstrate the effectiveness of the algorithm.     

无约束最优化问题的BFGS松弛异步并行算法

为解决大规模非线性最优化问题的串行求解速度慢的问题,提出应用松弛异步并行算法求解无约束最优化问题。根据无约束最优化问题的BFGS串行算法,在PC机群环境下将其并行化。利用CHOLESKY方法分解系数为对称正定矩阵的线性方程组,运用无序松弛异步并行方法求解解向量和Wolfe-Powell非线性搜索步长,并行求解BFGS修正公式,构建BFGS松弛异步并行算法,并对算法的时间复杂性、加速比进行分析。在PC机群的实验结果表明,该算法提高了无约束最优化问题的求解速度且负载均衡,算法具有线性加速比。