Massive Data Classification via Unconstrained Support Vector Machines

A highly accurate algorithm, based on support vector machines formulated as linear programs (Refs. 1–2), is proposed here as a completely unconstrained minimization problem (Ref. 3). Combined with a chunking procedure (Ref. 4), this approach, which requires nothing more complex than a linear equation solver, leads to a simple and accurate method for classifying million-point datasets. Because a 1-norm support vector machine underlies the proposed approach, the method suppresses input space features as well. A state-of-the-art linear programming package (CPLEX, Ref. 5) fails to solve problems handled by the proposed algorithm.This research was supported by National Science Foundation Grants CCR-0138308 and IIS-0511905.     

Sufficient Optimality Criterion for Linearly Constrained,Separable Concave Minimization Problems

A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimality criterion is based on the sensitivity analysis of the relaxed linear programming problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our proofs are simpler and constructive.In the Phillips and Rosen paper (Ref. 1), they derived a sufficient optimality criterion for a slightly different linearly-constrained concave minimization problem using exponentially many linear programming problems. We introduce special test points and, using these for several cases, we are able to show optimality of the current basic solution.The sufficient optimality criterion described in this paper can be used as a stopping criterion for branch-and-bound algorithms developed for linearly-constrained concave minimization problems.This research was supported by a Bolyai János Research Fellowship BO/00334/00 of the Hungarian Academy of Science and by the Hungarian Scientific Research Foundation, Grant OTKA T038027.     

Relation between the memory gradient method and the Fletcher-Reeves method

The minimization of a function of unconstrained variables is considered using the memory gradient method. It is shown that, for the particular case of a quadratic function, the memory gradient algorithm and the Fletcher-Reeves algorithm are identical.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-828-67. In more expanded form, it can be found in Ref. 1.     

Unconstrained optimization reformulations of equilibrium problems

We generalize the D-gap function developed in the literature for variational inequalities to a general equilibrium problem （EP）. Through the D-gap function, the equilibrium problem is cast as an unconstrained minimization problem. We give conditions under which any stationary point of the D-gap function is a solution of EP and conditions under which it provides a global error bound for EP. Finally, these results are applied to box-constrained EP and then weaker conditions are established to obtain the desired results for box-constrained EP.     

Convexity of the Implicit Lagrangian

The implicit Lagrangian has attracted much attention recently because of its utility in reformulating complementarity and variational inequality problems as unconstrained minimization problems. It was first proposed by Mangasarian and Solodov as a merit function for the nonlinear complementarity problem (Ref. 1). Three open problems were also raised in the same paper. This paper addresses, among other issues, one of these problems by giving the properties of the implicit Lagrangian and establishing its convexity under appropriate assumptions.     

On Unconstrained and Constrained Stationary Points of the Implicit Lagrangian

Mangasarian and Solodov (Ref. 1) proposed to solve nonlinear complementarity problems by seeking the unconstrained global minima of a new merit function, which they called implicit Lagrangian. A crucial point in such an approach is to determine conditions which guarantee that every unconstrained stationary point of the implicit Lagrangian is a global solution, since standard unconstrained minimization techniques are only able to locate stationary points. Some authors partially answered this question by giving sufficient conditions which guarantee this key property. In this paper, we settle the issue by giving a necessary and sufficient condition for a stationary point of the implicit Lagrangian to be a global solution and, hence, a solution of the nonlinear complementarity problem. We show that this new condition easily allows us to recover all previous results and to establish new sufficient conditions. We then consider a constrained reformulation based on the implicit Lagrangian in which nonnegative constraints on the variables are added to the original unconstrained reformulation. This is motivated by the fact that often, in applications, the function which defines the complementarity problem is defined only on the nonnegative orthant. We consider the KKT-points of this new reformulation and show that the same necessary and sufficient condition which guarantees, in the unconstrained case, that every unconstrained stationary point is a global solution, also guarantees that every KKT-point of the new problem is a global solution.     

Nonlinear complementarity as unconstrained and constrained minimization

The nonlinear complementarity problem is cast as an unconstrained minimization problem that is obtained from an augmented Lagrangian formulation. The dimensionality of the unconstrained problem is the same as that of the original problem, and the penalty parameter need only be greater than one. Another feature of the unconstrained problem is that it has global minima of zero at precisely all the solution points of the complementarity problem without any monotonicity assumption. If the mapping of the complementarity problem is differentiable, then so is the objective of the unconstrained problem, and its gradient vanishes at all solution points of the complementarity problem. Under assumptions of nondegeneracy and linear independence of gradients of active constraints at a complementarity problem solution, the corresponding global unconstrained minimum point is locally unique. A Wolfe dual to a standard constrained optimization problem associated with the nonlinear complementarity problem is also formulated under a monotonicity and differentiability assumption. Most of the standard duality results are established even though the underlying constrained optimization problem may be nonconvex. Preliminary numerical tests on two small nonmonotone problems from the published literature converged to degenerate or nondegenerate solutions from all attempted starting points in 7 to 28 steps of a BFGS quasi-Newton method for unconstrained optimization.Dedicated to Phil Wolfe on his 65th birthday, in appreciation of his major contributions to mathematical programming.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.     

Decomposition in separable geometric programming

Optimization of a special class of geometric programs is achieved by a decomposition technique. Optimal vectors to certain subproblems are obtained by solving a single unconstrained minimization problem involving a strictly convex function. These optimal vector readily yield an optimal vector to the original program.This research was supported in part by funds from NSF Grant No. GP-15031.     

Direct transformation of variational problems into Cauchy systems. I. Scalar-quadratic case

This series of papers addresses three interrelated problems: the solution of a variational minimization problem, the solution of integral equations, and the solution of an initial-valued system of integro-differential equations. It will be shown that a large class of minimization problems requires the solution of linear Fredholm integral equations. It has also been shown that the solution of a linear Fredholm integral equation is identical to the solution of a Cauchy system. In this paper, we bypass the Fredholm integral equations and show that the minimization problem directly implies a solution of a Cauchy system. This first paper in the series looks only at quadratic functionals and scalar functions.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-77-3383.     

A conjugate gradient method for the unconstrained minimization of strictly convex quadratic splines

In this paper, we show that an analogue of the classical conjugate gradient method converges linearly when applied to solving the problem of unconstrained minimization of a strictly convex quadratic spline. Since a strictly convex quadratic program with simple bound constraints can be reformulated as unconstrained minimization of a strictly convex quadratic spline, the conjugate gradient method is used to solve the unconstrained reformulation and find the solution of the original quadratic program. In particular, if the solution of the original quadratic program is nondegenerate, then the conjugate gradient method finds the solution in a finite number of iterations. This author's research is partially supported by the NASA/Langley Research Center under grant NCC-1-68 Supplement-15.     

Variational principles with integrands defined through a minimum

We revisit a systematic approach for the computation and analysis of the convex hull of non-convex integrands defined through the minimum of convex densities. It consists in reformulating the non-convex variational problem as a double minimization and exploiting appropriately the nature of optimality of the inner minimization. This requires gradient Young measures in the vector case, even if the initial problem was scalar, as the full problem is recast through the computation of a certain quasiconvexification. We illustrate this strategy by looking at two typical non-convex scalar problems. We hope to address vector problems in the near future.     

A family of variable metric methods in function space,without exact line searches

The purpose of this paper is to extend a family of variable metric methods, of which the BFGS algorithm (Ref. 1) is a member, into function space, in particular, for the solution of unconstrained optimal control problems. An inexact one-dimensional minimization as suggested by Fletcher (ref. 2) is used. It is shown that, with this stepsize rule and under some mild assumptions, the sequence constructed by this family of methods converges superlinearly for a strictly convex functional defined on a suitable Banach space. This result is shown to remain valid on a Hilbert space and on a Euclidean space under more relaxed assumptions. The BFGS method without line searches is used to solve several standard numerical examples, and excellent performance is observed.This work was supported by the Consejo Nacional de Ciencia y Tecnologia de Mexico, and by the National Research Council of Canada, Grant No. A-8835. The authors are indebted to Dr. C. Charalambous for suggesting the topic and stimulating discussions.     

A method for solving a quadratic optimal control problem

Hestenes' method of multipliers is used to approximate a quadratic optimal control problem. The global existence of a family of unconstrained problems is established. Given an initial estimate of the Lagrange multipliers, a convergent sequence of arcs is generated. They are minimizing with respect to members of the above family, and their limit is the solution to the original differentially constrained problem.The preparation of this paper was sponsored in part by the U.S. Army Research Office under Grant No. DA-31-124-ARO(D)-355.     

对等式约束非线性规划问题的Hestenes-Powell增广拉格朗日函数的进一步研究

本文对用无约束极小化方法求解等式约束非线性规划问题的Hestenes-Powell 增广拉格朗日函数作了进一步研究．在适当的条件下,我们建立了Hestenes-Powell增广拉格朗日函数在原问题变量空间上的无约束极小与原约束问题的解之间的关系,并且也给出了Hestenes-Powell增广拉格朗日函数在原问题变量和乘子变量的积空间上的无约束极小与原约束问题的解之间的一个关系．因此,从理论的观点来看,原约束问题的解和对应的拉格朗日乘子值不仅可以用众所周知的乘子法求得,而且可以通过对Hestenes-Powell 增广拉格朗日函数在原问题变量和乘子变量的积空间上执行一个单一的无约束极小化来获得．     

带新NCP函数的Lagrangian乘子方法

在经营管理、工程设计、科学研究、军事指挥等方面普遍存在着最优化问题,而实际问题中出现的绝大多数问题都被归纳为非线性规划问题之中。作为带等式、不等式约束的复杂事例,最优化问题的求解向来较为繁琐、困难。适当条件下,非线性互补函数(NCP)可以与约束优化问题相结合,其中NCP函数的无约束极小解对应原约束问题的解及其乘子。本文提出了一类新的NCP函数用于解决等式和不等式约束非线性规划问题,结合新的NCP函数构造了增广Lagrangian函数。在适当假设条件下,证明了增广Lagrangian函数与原问题的解之间的一一对应关系。同时构造了相应算法,并证明了该算法的收敛性和有效性。     

A saddle-point theorem with application to structural optimization

The relaxation for optimal complicance design is independent of whether the underlying elastic problem is formulated in terms of displacements or strains. For the purposes of numerical experimentation and computation, it may be advantageous to formulate optimal design problems in terms of displacements as is done in Ref. 1. The relaxed problem delivered by the displacement-based formulation is of min-min-max type. Because of this, efficient numerical implementation is hampered by the order of the last two min-max operations. We show here that the last two min-max operations may be exchanged, facilitating an efficient numerical algorithm. We remark that the rigorous results given here corroborate the numerical methods and experiments given in Ref. 1.This work was supported by NSF Grant DMS-92-05158.     

Expected Residual Minimization Formulation for a Class of Stochastic Vector Variational Inequalities

This paper considers a class of vector variational inequalities. First, we present an equivalent formulation, which is a scalar variational inequality, for the deterministic vector variational inequality. Then we concentrate on the stochastic circumstance. By noting that the stochastic vector variational inequality may not have a solution feasible for all realizations of the random variable in general, for tractability, we employ the expected residual minimization approach, which aims at minimizing the expected residual of the so-called regularized gap function. We investigate the properties of the expected residual minimization problem, and furthermore, we propose a sample average approximation method for solving the expected residual minimization problem. Comprehensive convergence analysis for the approximation approach is established as well.     

Periodic Solutions for a Class of Second-Order Ordinary Differential Equations

This paper is devoted to the study of periodic solutions for a class of second-order ordinary differential equations by utilizing a technique for obtaining solutions to free problems in the calculus of variations originating in the work of Carathéodory (Ref. 1, 1935). The key of this technique is to find some suitable transformation which transfers the periodic solution problem to an equivalent variational problem in which the minimizer is more easily determined. Some applications are presented to illustrate the utility of this technique.Supported by NSFC Grant 10401013, 985 Project of Jilin University and Graduate Innovation Lab of Jilin University. The authors thank Professor D. A. Carlson and the anonymous referees for valuable suggestions and helpful comments.     

On the Index of Solvability for Variational Inequalities in Banach Spaces

We define the index of solvability, a topological characteristic, whose difference from zero provides the existence of a solution for variational inequalities of Stampacchia’s type with S ⁺-type and pseudo-monotone multimaps on reflexive separable Banach spaces. Some applications to a minimization problem and to a problem of economical dynamics are presented. The work is supported by the Russian FBR Grants 05-01-00100 and 07-01-00137 and by the NATO Grant ICS.NR.CLG 981757.     

Penalty methods for mathematical programming inE nwith general constraint sets

This paper extends the principal supporting results and the general convergence theorems for penalty methods, obtained by Fiacco and McCormick (Ref. 1) for the continuous mathematical programming problem, to the problem of minimizing a mildly regulated objective function over any nonempty subset ofE ⁿ.The constraint set need not be defined through a collection of inequalities. A general auxiliary function is defined, and the desired minimizing sequence is shown to exist, without additional assumptions (i.e., assumptions other than those invoked in the principal convergence theorem of Ref. 1). A particularly interesting consequence is the fact that a discrete (e.g., integer) programming problem can be solved by asingle unconstrained minimization of the auxiliary function.