-
作者：Pena, Javier; Soheili, Negar
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
摘要：We propose a simple projection and rescaling algorithm to solve the feasibility problem find x is an element of L boolean AND Omega, where L and Omega are respectively a linear subspace and the interior of a symmetric cone in a finite-dimensional vector space V. This projection and rescaling algorithm is inspired by previous work on rescaled versions of the perceptron algorithm and by Chubanov's projection-based method for linear feasibility problems. As in these predecessors, each main iterat...
-
作者：Suda, Sho; Tanaka, Hajime; Tokushige, Norihide
作者单位：Aichi University Education; Tohoku University; University of the Ryukyus
摘要：We present a semidefinite programming approach to bound the measures of cross-independent pairs in a bipartite graph. This can be viewed as a far-reaching extension of Hoffman's ratio bound on the independence number of a graph. As an application, we solve a problem on the maximum measures of cross-intersecting families of subsets with two different product measures, which is a generalized measure version of the ErdAs-Ko-Rado theorem for cross-intersecting families with different uniformities.
-
作者：Buchheim, Christoph; Kurtz, Jannis
作者单位：Dortmund University of Technology
摘要：The idea of k-adaptability in two-stage robust optimization is to calculate a fixed number k of second-stage policies here-and-now. After the actual scenario is revealed, the best of these policies is selected. This idea leads to a min-max-min problem. In this paper, we consider the case where no first stage variables exist and propose to use this approach to solve combinatorial optimization problems with uncertainty in the objective function. We investigate the complexity of this special case...
-
作者：Hong, Mingyi; Luo, Zhi-Quan
作者单位：University of Minnesota System; University of Minnesota Twin Cities; The Chinese University of Hong Kong, Shenzhen; Iowa State University
摘要：We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analy...
-
作者：Beck, Amir; Shtern, Shimrit
作者单位：Technion Israel Institute of Technology
摘要：We consider the problem of minimizing the sum of a linear function and a composition of a strongly convex function with a linear transformation over a compact polyhedral set. Jaggi and Lacoste-Julien (An affine invariant linear convergence analysis for Frank-Wolfe algorithms. NIPS 2013 Workshop on Greedy Algorithms, Frank-Wolfe and Friends, 2014) show that the conditional gradient method with away steps - employed on the aforementioned problem without the additional linear term - has a linear ...
-
作者：Guigues, Vincent
摘要：We consider risk-averse convex stochastic programs expressed in terms of extended polyhedral risk measures. We derive computable confidence intervals on the optimal value of such stochastic programs using the Robust Stochastic Approximation and the Stochastic Mirror Descent (SMD) algorithms. When the objective functions are uniformly convex, we also propose a multistep extension of the Stochastic Mirror Descent algorithm and obtain confidence intervals on both the optimal values and optimal so...
-
作者：Del Pia, Alberto; Dey, Santanu S.; Molinaro, Marco
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Pontificia Universidade Catolica do Rio de Janeiro
摘要：Mixed-integer quadratic programming is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing that if the decision version of mixed-integer quadratic programming is feasible, then there exists a solution of polynomial size. This result generali...
-
作者：Dolgopolik, M. V.
作者单位：Saint Petersburg State University
摘要：In this article, we present new general results on existence of augmented Lagrange multipliers. We define a penalty function associated with an augmented Lagrangian, and prove that, under a certain growth assumption on the augmenting function, an augmented Lagrange multiplier exists if and only if this penalty function is exact. We also develop a new general approach to the study of augmented Lagrange multipliers called the localization principle. The localization principle allows one to study...
-
作者：Eaton, Julia; Grundel, Sara; Gurbuzbalaban, Mert; Overton, Michael L.
作者单位：University of Washington; University of Washington Tacoma; Max Planck Society; Rutgers University System; Rutgers University New Brunswick; New York University
摘要：The root radius of a polynomial is the maximum of the moduli of its roots (zeros). We consider the following optimization problem: minimize the root radius over monic polynomials of degree n, with either real or complex coefficients, subject to k linearly independent affine constraints on the coefficients. We show that there always exists an optimal polynomial with at most inactive roots, that is, roots whose moduli are strictly less than the optimal root radius. We illustrate our results usin...
-
作者：Goberna, Miguel A.; Kanzi, Nader
作者单位：Universitat d'Alacant; Payame Noor University
摘要：The purpose of this paper is to characterize the weak efficient solutions, the efficient solutions, and the isolated efficient solutions of a given vector optimization problem with finitely many convex objective functions and infinitely many convex constraints. To do this, we introduce new and already known data qualifications (conditions involving the constraints and/or the objectives) in order to get optimality conditions which are expressed in terms of either Karusk-Kuhn-Tucker multipliers ...
