-
作者：Orlin, James B.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider the problem of minimizing a submodular function f defined on a set V with n elements. We give a combinatorial algorithm that runs in O(n(5)EO + n(6)) time, where EO is the time to evaluate f (S) for some S subset of V. This improves the previous best strongly polynomial running time by more than a factor of n. We also extend our result to ring families.
-
作者：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...
-
作者：Correa, Rafael; Gajardo, Pedro; Thibault, Lionel
作者单位：Universidad Tecnica Federico Santa Maria; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile; Universite de Montpellier
摘要：We prove in the general setting of lower semicontinuous functions on Banach spaces the relation between the Rockafellar directional derivative and the mixed lower limit of the lower Dini derivatives. As a byproduct we derive the famous inclusions of tangent cones of closed sets in Banach spaces. The results are established using as principal tool multidirectional mean value inequalities [Aussel et al., SIAM J Optim 9(3), 690-706 (1999)].
-
作者：Mordukhovich, B. S.; Nam, N. M.; Yen, N. D.
作者单位：Wayne State University; Vietnam Academy of Science & Technology (VAST)
摘要：In this paper we derive new results for computing and estimating the so-called Frechet and limiting (basic and singular) subgradients of marginal functions in real Banach spaces and specify these results for important classes of problems in parametric optimization with smooth and nonsmooth data. Then we employ them to establish new calculus rules of generalized differentiation as well as efficient conditions for Lipschitzian stability and optimality in nonlinear and nondifferentiable programmi...
-
作者：Belloni, Alexandre; Sagastizabal, Claudia
作者单位：Duke University; Eletrobras Cepel
摘要：Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the dual point of view, this approach yields multipliers with varying dimensions and a dual objective function that changes along itera...
-
作者：Facchinei, Francisco; Fischer, Andreas; Piccialli, Veronica
作者单位：Sapienza University Rome; Technische Universitat Dresden
摘要：The generalized Nash equilibrium problem, where the feasible sets of the players may depend on the other players' strategies, is emerging as an important modeling tool. However, its use is limited by its great analytical complexity. We consider several Newton methods, analyze their features and compare their range of applicability. We illustrate in detail the results obtained by applying them to a model for internet switching.
-
作者：Daniilidis, A.; Jules, F.; Lassonde, M.
作者单位：Universite des Antilles; Autonomous University of Barcelona
摘要：It is known that a locally Lipschitz function is approximately convex if, and only if, its Clarke subdifferential is a submonotone operator. The main object of this work is to extend the above characterization to the class of lower semicontinuous functions. To this end, we establish a new approximate mean value inequality involving three points. We also show that an analogue of the Rockafellar maximal monotonicity theorem holds for this class of functions and we discuss the case of arbitrary s...
-
作者：Anitescu, Mihai; Negrut, Dan; Zapol, Peter; El-Azab, Anter
作者单位：United States Department of Energy (DOE); Argonne National Laboratory; United States Department of Energy (DOE); Argonne National Laboratory; United States Department of Energy (DOE); Argonne National Laboratory; State University System of Florida; Florida State University
摘要：The paper investigates model reduction techniques that are based on a nonlocal quasi-continuum-like approach. These techniques reduce a large optimization problem to either a system of nonlinear equations or another optimization problem that are expressed in a smaller number of degrees of freedom. The reduction is based on the observation that many of the components of the solution of the original optimization problem are well approximated by certain interpolation operators with respect to a r...
-
作者：Heitsch, Holger; Roemisch, Werner
作者单位：Humboldt University of Berlin
摘要：An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, we develop (stability) theory-based heuristics for generating scenario trees out of an initial set of scenarios. They are based on forward or backward algorithms for tree generation consisting of recursive scenario reduction and bundling steps. Conditions are established implying closeness of optim...
-
作者：Goberna, Miguel A.; Todorov, Maxim I.
作者单位：Universitat d'Alacant; Universidad Americas Puebla (UDLAP)
摘要：Any linear (ordinary or semi-infinite) optimization problem, and also its dual problem, can be classified as either inconsistent or bounded or unbounded, giving rise to nine duality states, three of them being precluded by the weak duality theorem. The remaining six duality states are possible in linear semi-infinite programming whereas two of them are precluded in linear programming as a consequence of the existence theorem and the non-homogeneous Farkas Lemma. This paper characterizes the li...
