The Euclidean Steiner Tree Problem in dimension greater than two is notoriously difficult. The successful methods for exact solution are not based on mathematical-optimization methods — rather, they involve very sophisticated enumeration. There are two types of mathematical-optimization formulations in the literature, and it is an understatement to say that neither scales well enough to … Read more
In this work we present a new feasible direction algorithm for solving smooth nonlinear second-order cone programs. These problems consist of minimizing a nonlinear di erentiable objective function subject to some nonlinear second-order cone constraints. Given a point interior to the feasible set de nfined by the nonlinear constraints, the proposed approach computes a feasible and descent … Read more
The MVE estimator is an important tool in robust regression and outlier detection in statistics. We develop fast and efficient algorithms for the MVE estimator problem and discuss how they can be implemented efficiently. The novelty of our approach stems from the recent developments in the first-order algorithms for solving the related Minimum Volume Enclosing … Read more
The stochastic gradient (SG) method can minimize an objective function composed of a large number of differentiable functions, or solve a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, handles problems with multiple blocks of variables by updating them one at a time; when the blocks … Read more
In this paper we consider a class of non-Lipschitz and non-convex minimization problems which generalize the L2−Lp minimization problem. We propose an iterative algorithm that decides the next iteration based on the local convexity/concavity/sparsity of its current position. We show that our algorithm finds an epsilon-KKT point within O(log(1/epsilon)) iterations. The same result is also … Read more
Many interesting properties of polynomials are closely related to the geometry of their Newton polytopes. In this article we analyze the coercivity on $\mathbb{R}^n$ of multivariate polynomials $f\in \mathbb{R}[x]$ in terms of their Newton polytopes. In fact, we introduce the broad class of so-called gem regular polynomials and characterize their coercivity via conditions imposed on … Read more
This paper presents a method for finding global optima to constrained nonlinear programs via slack variables. The method only applies if all functions involved are of class C1 but without any further qualification on the types of constraints allowed; it proceeds by reformulating the given program into a bi-objective program that is then solved for … Read more
Optimization problems with cardinality constraints are very dicult mathematical programs which are typically solved by global techniques from discrete optimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between the local minima is also discussed in … Read more
We study the minimization of fixed-degree polynomials over the simplex. This problem is well-known to be NP-hard, as it contains the maximum stable set problem in graph theory as a special case. In this paper, we consider a rational approximation by taking the minimum over the regular grid, which consists of rational points with denominator … Read more
This paper presents a relatively “unfettered” method for finding global optima to constrained nonlinear programs. The method reformulates the given program into a bi-objective mixed-integer program that is then solved for the Nash equilibrium. A numerical example (whose solution provides a new benchmark against which other algorithms may be assessed) is included to illustrate the … Read more