Linear support vector machine training can be represented as a large quadratic program. We present an efficient and numerically stable algorithm for this problem using interior point methods, which requires only O(n) operations per iteration. Through exploiting the separability of the Hessian, we provide a unified approach, from an optimization perspective, to 1-norm classification, 2-norm … Read more
A direct search method for the class of problems considered by Lewis and Torczon [\textit{SIAM J. Optim.}, 12 (2002), pp. 1075-1089] is developed. Instead of using an augmented Lagrangian method, a simplicial approximation method to the feasible set is implicitly employed. This allows the points our algorithm considers to conveniently remain within an \textit{a priori} … Read more
We generalize the Nelder-Mead simplex and LTMADS algorithms and, the frame based methods for function minimization to Riemannian manifolds. Examples are given for functions defined on the special orthogonal Lie group $\mathcal{SO}(n)$ and the Grassmann manifold $\mathcal{G}(n,k)$. Our main examples are applying the generalized LTMADS algorithm to equality constrained optimization problems and, to the Whitney … Read more
We present a general procedure for handling equality constraints in optimization problems that is of particular use in direct search methods. First we will provide the necessary background in differential geometry. In particular, we will see what a Riemannian manifold is, what a tangent space is, how to move over a manifold and how to … Read more
We extend direct search methods to optimization problems that include equality constraints given by Lipschitz functions. The equality constraints are assumed to implicitly define a Lipschitz manifold. Numerically implementing the inverse (implicit) function theorem allows us to define a new problem on the tangent spaces of the manifold. We can then use a direct search … Read more
We consider the problem of locating a single radiating source from several noisy measurements using a maximum likelihood (ML) criteria. The resulting optimization problem is nonconvex and nonsmooth and thus finding its global solution is in principal a hard task. Exploiting the special structure of the objective function, we introduce and analyze two iterative schemes … Read more
We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multi-criteria optimization. We provide a combinatorial polynomial time algorithm for arbitrary oracle-presented matroids, that makes repeated use of matroid intersection, and an algebraic algorithm for vectorial matroids. Our work is … Read more
We present a new matrix-free method for the trust region subproblem, assuming that the approximate Hessian is updated by the limited memory BFGS formula with m = 2. The resulting updating scheme, called 2-BFGS, give us the ability to determine via simple formulas the eigenvalues of the resulting approximation. Thus, at each iteration, we can … Read more
An algorithm for solving large-scale nonlinear optimization problems with simple bounds is described. The algorithm is an $\ell_\infty$-norm trust-region method that uses both active set identification techniques as well as limited memory BFGS updating for the Hessian approximation. The trust-region subproblems are solved using primal-dual interior point techniques that exploit the structure of the limited … Read more
We present fourteen basic FORTRAN subroutines for large-scale unconstrained and box constrained optimization and large-scale systems of nonlinear equations. Subroutines {\tt PLIS} and {\tt PLIP}, intended for dense general optimization problems, are based on limited-memory variable metric methods. Subroutine {\tt PNET}, also intended for dense general optimization problems, is based on an inexact truncated Newton … Read more