-
作者：Ahmed, Shabbir; Atamtuerk, Alper
作者单位：University of California System; University of California Berkeley; University System of Georgia; Georgia Institute of Technology
摘要：Given a finite ground set N and a value vector a is an element of R-N, we consider optimization problems involving maximization of a submodular set utility function of the form h(S) = f(Sigma(i is an element of S)a(i)), S subset of N, where f is a strictly concave, increasing, differentiable function. This utility function appears frequently in combinatorial optimization problems when modeling risk aversion and decreasing marginal preferences, for instance, in risk-averse capital budgeting und...
-
作者：Basu, Amitabh; Bonami, Pierre; Cornuejols, Gerard; Margot, Francois
作者单位：Carnegie Mellon University; Aix-Marseille Universite
摘要：Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. The same statement holds for quadri...
-
作者：Pong, Ting Kei; Tseng, Paul
作者单位：University of Washington; University of Washington Seattle
摘要：Recently Wang, Zheng, Boyd, and Ye (SIAM J Optim 19:655-673, 2008) proposed a further relaxation of the semidefinite programming (SDP) relaxation of the sensor network localization problem, named edge-based SDP (ESDP). In simulation, the ESDP is solved much faster by interior-point method than SDP relaxation, and the solutions found are comparable or better in approximation accuracy. We study some key properties of the ESDP relaxation, showing that, when distances are exact, zero individual tr...
-
作者：Gaur, Daya Ram; Krishnamurti, Ramesh; Kohli, Rajeev
作者单位：Columbia University; University of Lethbridge; Simon Fraser University
-
作者：Castro, Jordi; Cuesta, Jordi
作者单位：Universitat Politecnica de Catalunya; Universitat Rovira i Virgili
摘要：One of the most efficient interior-point methods for some classes of primal block-angular problems solves the normal equations by a combination of Cholesky factorizations and preconditioned conjugate gradient for, respectively, the block and linking constraints. Its efficiency depends on the spectral radius-in [0,1)- of a certain matrix in the definition of the preconditioner. Spectral radius close to 1 degrade the performance of the approach. The purpose of this work is twofold. First, to sho...
-
作者：Andreani, R.; Judice, J. J.; Martinez, J. M.; Patricio, J.
作者单位：Instituto Politecnico de Tomar; Universidade Estadual de Campinas; Universidade de Coimbra; Instituto de Telecomunicacoes; Institute of Telecommunications - Coimbra; Universidade de Coimbra
摘要：Complementarity problems may be formulated as nonlinear systems of equations with non-negativity constraints. The natural merit function is the sum of squares of the components of the system. Sufficient conditions are established which guarantee that stationary points are solutions of the complementarity problem. Algorithmic consequences are discussed.
-
作者：Nedic, Angelia
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：This paper deals with iterative gradient and subgradient methods with random feasibility steps for solving constrained convex minimization problems, where the constraint set is specified as the intersection of possibly infinitely many constraint sets. Each constraint set is assumed to be given as a level set of a convex but not necessarily differentiable function. The proposed algorithms are applicable to the situation where the whole constraint set of the problem is not known in advance, but ...
-
作者：Yun, Sangwoon; Tseng, Paul; Toh, Kim-Chuan
作者单位：Korea Institute for Advanced Study (KIAS); University of Washington; University of Washington Seattle; National University of Singapore
摘要：We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an l(1)-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth se...
-
作者：Zheng, Xiao Jin; Sun, Xiao Ling; Li, Duan
作者单位：Chinese University of Hong Kong; Fudan University
摘要：We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimat...
-
作者：Avelino, Catarina P.; Moguerza, Javier M.; Olivares, Alberto; Prieto, Francisco J.
作者单位：University of Tras-os-Montes & Alto Douro; Universidad Rey Juan Carlos; Universidad Carlos III de Madrid
摘要：The aim of this paper is the study of different approaches to combine and scale, in an efficient manner, descent information for the solution of unconstrained optimization problems. We consider the situation in which different directions are available in a given iteration, and we wish to analyze how to combine these directions in order to provide a method more efficient and robust than the standard Newton approach. In particular, we will focus on the scaling process that should be carried out ...
