-
作者：Beck, Amir; Teboulle, Marc
作者单位：Technion Israel Institute of Technology; Tel Aviv University
摘要：We consider the nonconvex problem (RQ) of minimizing the ratio of two nonconvex quadratic functions over a possibly degenerate ellipsoid. This formulation is motivated by the so-called regularized total least squares problem (RTLS), which is a special case of the problem's class we study. We prove that under a certain mild assumption on the problem's data, problem (RQ) admits an exact semidefinite programming relaxation. We then study a simple iterative procedure which is proven to converge su...
-
作者：Anily, Shoshana; Tzur, Michal; Wolsey, Laurence A.
作者单位：Universite Catholique Louvain; Tel Aviv University; Tel Aviv University
摘要：We consider a multi-item lot-sizing problem with joint set-up costs and constant capacities. Apart from the usual per unit production and storage costs for each item, a set-up cost is incurred for each batch of production, where a batch consists of up to C units of any mix of the items. In addition, an upper bound on the number of batches may be imposed. Under widely applicable conditions on the storage costs, namely that the production and storage costs are nonspeculative, and for any two ite...
-
作者：Belloni, Alexandre; Freund, Robert M.
作者单位：Massachusetts Institute of Technology (MIT); Duke University
摘要：For a conic linear system of the form Ax is an element of K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Among these, Renegar's condition number C(A) is arguably the most prominent for its relation to data perturbation, error bounds, problem geometry, and computational complexity of algorithms. Nonetheless, C(A) is a representation-dependent measure which is usually difficult to interpret and may lead to overly conservative bounds of compu...
-
作者：Restrepo, Mateo; Williamson, David P.
作者单位：Cornell University; Cornell University
摘要：We give a simple primal algorithm for the generalized maximum flow problem that repeatedly finds and cancels generalized augmenting paths (GAPs). We use ideas of Wallacher (A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms, 1991) to find GAPs that have a good trade-off between the gain of the GAP and the residual capacity of its arcs; our algorithm may be viewed as a special case of Wayne's algorithm for the generalized minimum-cost circulation problem (Wa...
