Let $p(x_1,…,x_m) = \sum_{r_1 + \cdots + r_m = n} a_{r_1,…,r_m} \prod_{1 \leq i \leq m } x_i^{r_{i}}$ be a homogeneous polynomial of degree $n$ in $m$ variables. We call such polynomial {\bf H-Stable} if $p(z_1,…,z_m) \neq 0$ provided that the real parts $Re(z_i) > 0: 1 \leq i \leq m$. It can be assumed … Read more
This paper extends the full convergence of the proximal point method with Riemannian, Semi-Bregman and Bregman distances to solve minimization problems on Hadamard manifolds. For the unconstrained problem, under the assumptions that the optimal set is nonempty and the objective function is continuous and either quasiconvex or satisfies a generalized Lojasiewicz property, we prove the … Read more
We describe a rudimentary branch-and-cut algorithm for solving integer bilevel linear programs that extends existing techniques for standard integer linear programs to this very challenging computational setting. The algorithm improves on the branch-and-bound algorithm of Moore and Bard in that it uses cutting plane techniques to produce improved bounds, does not require specialized branching strategies, … Read more
In this paper, we analyze the limiting behavior of the weighted least squares problem $\min_{x\in\Re^n}\sum_{i=1}^p\|D_i(A_ix-b_i)\|^2$, where each $D_i$ is a positive definite diagonal matrix. We consider the situation where the magnitude of the weights are drastically different block-wisely so that $\max(D_1)\geq\min(D_1) \gg \max(D_2) \geq \min(D_2) \gg \max(D_3) \geq \ldots \gg \max(D_{p-1}) \geq \min(D_{p-1}) \gg \max(D_p)$. … Read more
Filling a gap in nonconvex quadratic programming, this paper shows that the global resolution of a feasible quadratic program (QP), which is not known a priori to be bounded or unbounded below, can be accomplished in finite time by solving a linear program with linear complementarity constraints, i.e., an LPCC. Alternatively, this task can be … Read more
The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. … Read more
We study selfish routing in ring networks with respect to minimizing the maximum latency. Our main result is an establishement of constant bounds on the price of stability (PoS) for routing unsplittable flows with linear latency. We show that the PoS is at most 6.83, which reduces to 4:57 when the linear latency functions are … Read more
Particle swarm optimization (PSO) has received increasing interest from the optimization community due to its simplicity in implementation and its inexpensive computational overhead. However, PSO has premature convergence, especially in complex multimodal functions. Extremal Optimization (EO) is a recently developed local-search heuristic method and has been successfully applied to a wide variety of hard optimization … Read more
We present a new derivative-free algorithm, ORBIT, for unconstrained local optimization of computationally expensive functions. A trust-region framework using interpolating Radial Basis Function (RBF) models is employed. The RBF models considered often allow ORBIT to interpolate nonlinear functions using fewer function evaluations than the polynomial models considered by present techniques. Approximation guarantees are obtained by … Read more
In 1988, Barzilai and Borwein presented a new choice of step size for the gradient method for solving unconstrained minimization problems. Their method aimed to accelerate the convergence of the steepest descent method. The Barzilai-Borwein method requires few storage locations and inexpensive computations. Therefore, several authors have paid attention to the Barzilai-Borwein method and have … Read more