Andrés Gómez

Strong formulations for quadratic optimization with M-matrices and semi-continuous variables

Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

We study quadratic optimization with semi-continuous variables and an M-matrix, i.e., PSD with non-positive off-diagonal entries. This structure arises in image segmentation, portfolio optimization, as well as a substructure of general quadratic optimization problems. We prove, under mild assumptions, that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular … Read more

Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra

Categories Quadratic Programming, Robust Optimization, Second-Order Cone Programming Tags ,

We consider minimizing a conic quadratic objective over a polyhedron. Such problems arise in parametric value-at-risk minimization, portfolio optimization, and robust optimization with ellipsoidal objective uncertainty; and they can be solved by polynomial interior point algorithms for conic quadratic optimization. However, interior point algorithms are not well-suited for branch-and-bound algorithms for the discrete counterparts of … Read more

Maximizing a class of utility functions over the vertices of a polytope

Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Stochastic Programming Tags , , , , , , , ,

Given a polytope X, a monotone concave univariate function g, and two vectors c and d, we study the discrete optimization problem of finding a vertex of X that maximizes the utility function c’x + g(d’x). This problem has numerous applications in combinatorial optimization with a probabilistic objective, including estimation of project duration with stochastic … Read more