-
作者：Jiang, Xiaoye; Lim, Lek-Heng; Yao, Yuan; Ye, Yinyu
作者单位：University of California System; University of California Berkeley; Stanford University; Peking University; Peking University; Stanford University
摘要：We propose a technique that we call HodgeRank for ranking data that may be incomplete and imbalanced, characteristics common in modern datasets coming from e-commerce and internet applications. We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method exploits the graph Helmholtzian...
-
作者：Rudolf, Gabor; Noyan, Nilay; Papp, David; Alizadeh, Farid
作者单位：Virginia Commonwealth University; Sabanci University; Northwestern University; Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：For a proper cone K subset of R-n and its dual cone K* the complementary slackness condition < x, s > = 0 defines an n-dimensional manifold C(K) in the space R-2n. When K is a symmetric cone, points in C(K) must satisfy at least n linearly independent bilinear identities. This fact proves to be useful when optimizing over such cones, therefore it is natural to look for similar bilinear relations for non-symmetric cones. In this paper we define the bilinearity rank of a cone, which is the numbe...
-
作者：Lan, Guanghui; Lu, Zhaosong; Monteiro, Renato D. C.
作者单位：University System of Georgia; Georgia Institute of Technology; Simon Fraser University; University System of Georgia; Georgia Institute of Technology
摘要：In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov's optimal method (Nesterov in Doklady AN SSSR 269:543-547, 1983; Math Program 103:127-152, 2005), Nesterov's smooth approximation scheme (Nesterov in Math Program 103: 127-152, 2005), and Nemirovski's prox-method (Nemirovski in SIAM J Opt 15: 22...
-
作者：Sharkey, Thomas C.; Romeijn, H. Edwin; Geunes, Joseph
作者单位：Rensselaer Polytechnic Institute; University of Michigan System; University of Michigan; State University System of Florida; University of Florida
摘要：This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a par...
-
作者：Gaur, Daya Ram; Krishnamurti, Ramesh; Kohli, Rajeev
作者单位：Columbia University; University of Lethbridge; Simon Fraser University
-
作者：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.
-
作者：Ben-Tal, Aharon; Bhadra, Sahely; Bhattacharyya, Chiranjib; Nath, J. Saketha
作者单位：Indian Institute of Science (IISC) - Bangalore; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
摘要：This paper studies the problem of constructing robust classifiers when the training is plagued with uncertainty. The problem is posed as a Chance-Constrained Program (CCP) which ensures that the uncertain data points are classified correctly with high probability. Unfortunately such a CCP turns out to be intractable. The key novelty is in employing Bernstein bounding schemes to relax the CCP as a convex second order cone program whose solution is guaranteed to satisfy the probabilistic constra...
-
作者：Grippo, Luigi; Palagi, Laura; Piccialli, Veronica
作者单位：University of Rome Tor Vergata; Sapienza University Rome
摘要：In this paper we consider low-rank semidefinite programming (LRSDP) relaxations of combinatorial quadratic problems that are equivalent to the maxcut problem. Using the Gramian representation of a positive semidefinite matrix, the LRSDP problem can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function with quadratic equality constraints. For the solution of this problem we propose a continuously differentiable exact merit function that exploits the spe...
-
作者：de Klerk, Etienne; Dobre, Cristian; Pasechnik, Dmitrii V.
作者单位：Tilburg University; Tilburg University; Nanyang Technological University
摘要：Semidefinite programming (SDP) is one of the most active areas in mathematical programming, due to varied applications and the availability of interior point algorithms. In this paper we propose a new pre-processing technique for SDP instances that exhibit algebraic symmetry. We present computational results to show that the solution times of certain SDP instances may be greatly reduced via the new approach.
-
作者：So, Anthony Man-Cho
作者单位：Chinese University of Hong Kong
摘要：In this paper, we consider various moment inequalities for sums of random matrices-which are well-studied in the functional analysis and probability theory literature-and demonstrate how they can be used to obtain the best known performance guarantees for several problems in optimization. First, we show that the validity of a recent conjecture of Nemirovski is actually a direct consequence of the so-called non-commutative Khintchine's inequality in functional analysis. Using this result, we sh...
