On global optimizations of the rank and inertia of the matrix function $A_1- B_1XB^*_1$ subject to a pair of matrix equations $[\,B_2XB^*_2, \, B_3XB^*_3 \,] = [\,A_2, \, A_3\,]$

Categories Global Optimization Theory

For a given linear matrix function $A_1 – B_1XB^*_1$, where $X$ is a variable Hermitian matrix, this paper derives a group of closed-form formulas for calculating the global maximum and minimum ranks and inertias of the matrix function subject to a pair of consistent matrix equations $B_2XB^*_2 = A_2$ and $B_3XB_3^* = A_3$. As applications, … Read more

Concepts and Applications of Stochastically Weighted Stochastic Dominance

Categories Applications - OR and Management Sciences, Multi-Criteria Optimization, Stochastic Programming Tags , , , ,

Stochastic dominance theory provides tools to compare random entities. When comparing random vectors (say X and Y ), the problem can be viewed as one of multi-criterion decision making under uncertainty. One approach is to compare weighted sums of the components of these random vectors using univariate dominance. In this paper we propose new concepts … Read more

Efficient Solutions for the Far From Most String Problem

Categories Basic Sciences Applications, Combinatorial Optimization, Meta Heuristics Tags , , , ,

Computational molecular biology has emerged as one of the most exciting interdisciplinary fields. It has currently benefited from concepts and theoretical results obtained by different scientific research communities, including genetics, biochemistry, and computer science. In the past few years it has been shown that a large number of molecular biology problems can be formulated as … Read more

Approximation algorithms for trilinear optimization with nonconvex constraints and its extensions

Categories Semi-definite Programming Tags , , , ,

In this paper, we study trilinear optimization problems with nonconvex constraints under some assumptions. We first consider the semidefinite relaxation (SDR) of the original problem. Then motivated by So \cite{So2010}, we reduce the problem to that of determining the $L_2$-diameters of certain convex bodies, which can be approximately solved in deterministic polynomial-time. After the relaxed … Read more

On the Moreau-Yosida regularization of the vector k-norm related functions

Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

In this paper, we conduct a thorough study on the first and second order properties of the Moreau-Yosida regularization of the vector $k$-norm function, the indicator function of its epigraph, and the indicator function of the vector $k$-norm ball. We start with settling the vector $k$-norm case via applying the existing breakpoint searching algorithms to … Read more

Job-Shop Scheduling in a Body Shop

Categories Approximation Algorithms, Scheduling Tags , , ,

We study a generalized job-shop problem called the body shop scheduling problem (bssp). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. bssp corresponds to a job-shop problem where the operations of a job have to follow … Read more

Branch-and-Cut for Separable Piecewise Linear Optimization: New Inequalities and Intersection with Semi-Continuous Constraints

Categories Integer Programming Tags , , , , , ,

We give new facets and valid inequalities for the separable piecewise linear optimization knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. In a companion paper (de Farias, Gupta, Kozyreff, Zhao, 2011) we demonstrate the efficiency of the inequalities when used as cuts in a branch-and-cut … Read more

Branch-and-Cut for Separable Piecewise Linear Optimization: Computation

Categories Integer Programming Tags , , , , , ,

We report and analyze the results of our extensive computational testing of branch-and-cut for piecewise linear optimization using the cutting planes given recently by Zhao and de Farias. Besides analysis of the performance of the cuts, we also analyze the effect of formulation on the performance of branch-and-cut. Finally, we report and analyze initial results … Read more

Finding largest small polygons with GloptiPoly

Categories Global Optimization, Quadratic Programming, Semi-definite Programming Tags , , ,

A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices $n$. Many instances are already solved in the literature, namely for all odd $n$, and for $n=4, 6$ and $8$. Thus, for even $n\geq 10$, instances of this … Read more