In this note we establish a relation between two bounds for convex maximization problems, the one based on a concavity cut, and the surrogate dual bound. Both bounds have been known in the literature for a few decades but, to the authors’ knowledge, the relation between them has not been previously observed in the literature. … Read more
Combinatorial and logic constraints arising in a number of challenging optimization applications can be formulated as vanishing constraints. Quadratic programs with vanishing constraints (QPVCs) then arise as subproblems during the numerical solution of such problems using algorithms of the Sequential Quadratic Programming type. QPVCs are nonconvex problems violating standard constraint qualifications. In this paper, we … Read more
This paper introduces a new method for proving global stability of fluid flows through the construction of Lyapunov functionals. For finite dimensional approximations of fluid systems, we show how one can exploit recently developed optimization methods based on sum-of-squares decomposition to construct a polynomial Lyapunov function. We then show how these methods can be extended … Read more
Multi-homing is used by Internet Service Provider (ISP) to connect to the Internet via different network providers. This study investigates the optimal routing strategy under multi-homing in the case where network providers charge ISPs according to top-percentile pricing (i.e. based on the $\theta$-th highest volume of traffic shipped). We call this problem the Top-percentile Traffic … Read more
In this paper we study relations between the minimax, risk averse and nested formulations of multistage stochastic programming problems. In particular, we discuss conditions for time consistency of such formulations of stochastic problems. We also describe a connection between law invariant coherent risk measures and the corresponding sets of probability measures in their dual representation. … Read more
Kitahara and Mizuno (2010) get two upper bounds for the number of different basic feasible solutions generated by Dantzig’s simplex method. The size of the bounds highly depends on the ratio between the maximum and minimum values of all the positive elements of basic feasible solutions. In this paper, we show some relations between the … Read more
In 1979, L. Lovasz defined the theta number, a spectral/semidefinite upper bound on the stability number of a graph, which has several remarkable properties (e.g. it is exact for perfect graphs). The definition of Lovasz’s theta number relies on the notion of orthonormal representation of the graph, and, dually, can be obtained by optimizing over … Read more
We extend the target map, together with the weighted barriers and the notions of weighted analytic centers, from linear programming to general convex conic programming. This extension is obtained from a novel geometrical perspective of the weighted barriers, that views a weighted barrier as a weighted sum of barriers for a strictly decreasing sequence of … Read more
We consider the linearly constrained separable convex programming whose objective function is separable into m individual convex functions without crossed variables. The alternating direction method (ADM) has been well studied in the literature for the special case m=2. But the convergence of extending ADM to the general case m>=3 is still open. In this paper, … Read more
The Time Dependent Traveling Salesman Problem (TDTSP) is a generalization of the classical Traveling Salesman Problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. … Read more