-
作者：Ryan, Christopher Thomas; Smith, Robert L.
作者单位：University of British Columbia; University of Michigan System; University of Michigan
摘要：We develop novel dual-ascent and primal-dual methods to solve infinite-horizon nonstationary deterministic dynamic programs. These methods are finitely implementable and converge in value to optimality. Moreover, the dual-ascent method produces a sequence of improving dual solutions that pointwise converge to an optimal dual solution, while the primal-dual algorithm provides a sequence of primal basic feasible solutions with value error bounds from optimality that converge to zero. Our dual-ba...
-
作者：Correa, R.; Hantoute, A.; Lopez, M. A.
作者单位：Universidad de O'Higgins; Universidad de Chile; Universidad de Chile; Universitat d'Alacant; Federation University Australia
摘要：In this paper we establish general formulas for the subdifferential of the pointwise supremum of convex functions, which cover and unify both the compact continuous and the non-compact non-continuous settings. From the non-continuous to the continuous setting, we proceed by a compactification-based approach which leads us to problems having compact index sets and upper semi-continuously indexed mappings, giving rise to new characterizations of the subdifferential of the supremum by means of up...
-
作者：Pena, Javier; Vera, Juan C.; Zuluaga, Luis F.
作者单位：Carnegie Mellon University; Tilburg University; Lehigh University
摘要：We give a characterization of the Hoffman constant of a system of linear constraints in Rn relative to a reference polyhedron R. Rn. The reference polyhedron R represents constraints that are easy to satisfy such as box constraints. In the special case R = Rn, we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose R. Rn is a reference polyhedron, A. Rmxn, and A( R) := {Ax : x. R}. We characterize the sharpest constant H( A| R) such that for all b. A( R) +...
-
作者：Bartz, Sedi; Bauschke, Heinz H.; Phan, Hung M.; Wang, Xianfu
作者单位：University of Massachusetts System; University of Massachusetts Lowell; University of British Columbia
摘要：Monotonicity and convex analysis arise naturally in the framework of multi-marginal optimal transport theory. However, a comprehensive multi-marginal monotonicity and convex analysis theory is still missing. To this end we study extensions of classical monotone operator theory and convex analysis into the multi-marginal setting. We characterize multi-marginal c-monotonicity in terms of classical monotonicity and firmly nonexpansive mappings. We provide Minty type, continuity and conjugacy crit...
-
作者：van der Laan, Niels; Romeijnders, Ward
作者单位：University of Groningen
摘要：We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total...
-
作者：Letchford, Adam N.; Ni, Qiang; Zhong, Zhaoyu
作者单位：Lancaster University; Lancaster University
摘要：Perspective functions have long been used to convert fractional programs into convex programs. More recently, they have been used to form tight relaxations of mixed-integer nonlinear programs with so-called indicator variables. Motivated by a practical application (maximising energy efficiency in an OFDMA system), we consider problems that have a fractional objective and indicator variables simultaneously. To obtain a tight relaxation of such problems, one must consider what we call a bi-persp...
-
作者：Kunisky, Dmitriy; Bandeira, Afonso S.
作者单位：New York University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We show that, if W is an N xN matrix drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares relaxation cannot certify an upper bound on the objective N-1 center dot x(perpendicular to) Wx under the constraints x(i)(2) - 1 = 0 (i.e. x is an element of {+/- 1}(N)) that is asymptotically smaller than lambda(max)(W) approximate to 2. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as N...
-
作者：Borges, Pedro; Sagastizabal, Claudia; Solodov, Mikhail
作者单位：Universidade Estadual de Campinas
摘要：We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions with Tikhonov regularization. Because the regularized mappings are single-valued and smooth under reasonable conditions, they can be used to build a computationally practical smoothing for the associated optimal value function. The value function in question, while resulting from parameterized convex problems, need not be conve...
-
作者：Do Sang Kim; Mordukhovich, Boris S.; Tien-Son Pham; Nguyen Van Tuyen
作者单位：Pukyong National University; Wayne State University; Peoples Friendship University of Russia; Hanoi Pedagogical University 2 (HPU2); University of Electronic Science & Technology of China
摘要：The paper is devoted to the existence of global optimal solutions for a general class of nonsmooth problems of constrained vector optimization without boundedness assumptions on constraint set. The main attention is paid to the two major notions of optimality in vector problems: Pareto efficiency and proper efficiency in the sense of Geoffrion. Employing adequate tools of variational analysis and generalized differentiation, we first establish relationships between the notions of properness,M-...
-
作者：Bauschke, Heinz H.; Moursi, Walaa M.; Wang, Xianfu
作者单位：University of British Columbia; University of Waterloo
摘要：The correspondence between the monotonicity of a (possibly) set-valued operator and the firm nonexpansiveness of its resolvent is a key ingredient in the convergence analysis of many optimization algorithms. Firmly nonexpansive operators form a proper subclass of the more general-but still pleasant from an algorithmic perspective-class of averaged operators. In this paper, we introduce the new notion of conically nonexpansive operators which generalize nonexpansive mappings. We characterize av...
