-
作者：Lu, Shu
作者单位：University of North Carolina; University of North Carolina Chapel Hill
摘要：This paper investigates properties of a parametric set defined by finitely many equality and inequality constraints under the constant rank constraint qualification (CRCQ). We show, under the CRCQ, that the indicator function of this set is prox-regular with compatible parametrization, that the set-valued map that assigns each parameter to the set defined by that parameter satisfies a continuity property similar to the Aubin property, and that the Euclidean projector onto this set is a piecewi...
-
作者：Zheng, Xi Yin; Ng, Kung Fu
作者单位：Yunnan University; Chinese University of Hong Kong
摘要：Using variational analysis techniques, we study convex-composite optimization problems. In connection with such a problem, we introduce several new notions as variances of the classical KKT conditions. These notions are shown to be closely related to the notions of sharp or weak sharp solutions. As applications, we extend some results on metric regularity of inequalities from the convex case to the convex-composite case.
-
作者：Razaviyayn, Meisam; Luo, Zhi-Quan; Tseng, Paul; Pang, Jong-Shi
作者单位：University of Minnesota System; University of Minnesota Twin Cities; University of Washington; University of Washington Seattle; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider a cognitive radio system with one primary (licensed) user and multiple secondary (unlicensed) users. Given the interference temperature constraint, the secondary users compete for the available spectrum to fulfill their own communication need. Borrowing the concept of price from market theory, we develop a decentralized Stackelberg game formulation for power allocation. In this scheme, the primary user (leader) announces prices for the available tones such that a system utility is ...
-
作者：Colombo, Marco; Gondzio, Jacek; Grothey, Andreas
作者单位：University of Edinburgh; Heriot Watt University
摘要：We describe a way of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree and use the solution to generate an advanced starting point for the complete problem. The way we produce a reduced tree tries to capture the impo...
-
作者：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...
-
作者：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...
-
作者：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...
