Global Optimization

On proximal subgradient splitting method for minimizing the sum of two nonsmooth convex functions

Categories Convex and Nonsmooth Optimization, Global Optimization, Nonlinear Optimization

In this paper we present a variant of the proximal forward-backward splitting method for solving nonsmooth optimization problems in Hilbert spaces, when the objective function is the sum of two nondifferentiable convex functions. The proposed iteration, which will be call the Proximal Subgradient Splitting Method, extends the classical projected subgradient iteration for important classes of … Read more

On the Global Optimality for Linear Constrained Rank Minimization Problem

Categories Global Optimization, Nonlinear Optimization Tags , , , ,

The rank minimization with linear equality constraints has two closely related models, the low rank approximation model, that is to find the best rank-k approximation of a matrix satisfying the linear constraints, and its corresponding factorization model. The latter one is an unconstrained nonlinear least squares problem and hence enjoys a few fast first-order methods … Read more

Hedging Problem

Categories Finance and Economics, Global Optimization Applications

For index-based hedging design, the scatter plot of the hedging contract losses versus the losses to be hedged is generally used to visualize and quantify basis risk. While studying this scatter plot, which does not cluster along the diagonal as desired, a “bundled loss” phenomenon is found. In a setting where both the hedging and … Read more

Higher Order Maximum Persistency and Comparison Theorems

Categories 0-1 Programming, Global Optimization Theory, Polyhedra Tags , , , , ,

We address combinatorial problems that can be formulated as minimization of a partially separable function of discrete variables (energy minimization in graphical models, weighted constraint satisfaction, pseudo-Boolean optimization, 0-1 polynomial programming). For polyhedral relaxations of such problems it is generally not true that variables integer in the relaxed solution will retain the same values in … Read more

Inexactness of SDP Relaxation and Valid Inequalities for Optimal Power Flow

Categories Global Optimization Tags , , ,

It has been recently proven that the semidefinite programming (SDP) relaxation of the optimal power flow problem over radial networks is exact under technical conditions such as not including generation lower bounds or allowing load over-satisfaction. In this paper, we investigate the situation where generation lower bounds are present. We show that even for a … Read more

Optimal scheduling for replacing perimeter guarding unmanned aerial vehicles

Categories Civil and Environmental Engineering, Global Optimization, Scheduling

Guarding the perimeter of an area in order to detect potential intruders is an important task in a variety of security-related applications. This task can in many circumstances be performed by a set of camera-equipped unmanned aerial vehicles (UAVs). Such UAVs will occasionally require refueling or recharging, in which case they must temporarily be replaced … Read more

Relative Entropy Relaxations for Signomial Optimization

Categories Convex and Nonsmooth Optimization, Global Optimization

Signomial programs (SPs) are optimization problems specified in terms of signomials, which are weighted sums of exponentials composed with linear functionals of a decision variable. SPs are non convex optimization problems in general, and families of NP-hard problems can be reduced to SPs. In this paper we describe a hierarchy of convex relaxations to obtain … Read more

Maximal Covering Location Problems on networks with regional demand

Categories (Mixed) Integer Nonlinear Programming, Facility Planning and Design, Global Optimization Tags , , , ,

Covering problems are well studied in the Operations Research literature under the assumption that both the set of users and the set of potential facilities are finite. In this paper we address the following variant, which leads to a Mixed Integer Nonlinear Program (MINLP): locations of p facilities are sought along the edges of a … Read more

RBFOpt: an open-source library for black-box optimization with costly function evaluations

Categories Bound-constrained Optimization, Global Optimization, Optimization Software and Modeling Systems

We consider the problem of optimizing an unknown function given as an oracle over a mixed-integer box-constrained set. We assume that the oracle is expensive to evaluate, so that estimating partial derivatives by finite differences is impractical. In the literature, this is typically called a black-box optimization problem with costly evaluation. This paper describes the … Read more

On a nonconvex MINLP formulation of the Euclidean Steiner tree problems in n-space

Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Global Optimization Tags , ,

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