-
作者：Lodi, Andrea; Nagarajan, Viswanath
-
作者：Permenter, Frank; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies certain invariance conditions, restricting to its range yields an equivalent primal-dual pair over a lower-dimensional symmetric cone-namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices. We present a simple algorithm for minimizing the rank of this projection and hence the dimension of this subalgebra. We also s...
-
作者：Andreani, Roberto; Haeser, Gabriel; Viana, Daiana S.
作者单位：Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidade Federal do Acre (UFAC)
摘要：Sequential optimality conditions have played a major role in unifying and extending global convergence results for several classes of algorithms for general nonlinear optimization. In this paper, we extend theses concepts for nonlinear semidefinite programming. We define two sequential optimality conditions for nonlinear semidefinite programming. The first is a natural extension of the so-called Approximate-Karush-Kuhn-Tucker (AKKT), well known in nonlinear optimization. The second one, called...
-
作者：Chen, Lin; Eberle, Franziska; Megow, Nicole; Schewior, Kevin; Stein, Cliff
作者单位：Texas Tech University System; Texas Tech University; University of Bremen; University of Cologne; Columbia University
摘要：We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least 1+epsilon times its processing time, for some epsilon>0. We quantify the impact that different prov...
-
作者：Qian, Xun; Liao, Li-Zhi; Sun, Jie
作者单位：Hong Kong Baptist University; Curtin University; National University of Singapore
摘要：The affine scaling algorithm is one of the earliest interior point methods developed for linear programming. This algorithm is simple and elegant in terms of its geometric interpretation, but it is notoriously difficult to prove its convergence. It often requires additional restrictive conditions such as nondegeneracy, specific initial solutions, and/or small step length to guarantee its global convergence. This situation is made worse when it comes to applying the affine scaling idea to the s...
-
作者：Attouch, Hedy; Cabot, Alexandre
作者单位：Universite de Montpellier; Universite Bourgogne Europe; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：In a Hilbert spaceHgivenA:H -> 2Ha maximally monotone operator, we study the convergence properties of a general class of relaxed inertial proximal algorithms. This study aims to extend to the case of the general monotone inclusionAxCONTAINS AS MEMBER0the acceleration techniques initially introduced by Nesterov in the case of convex minimization. The relaxed form of the proximal algorithms plays a central role. It comes naturally with the regularization of the operatorAby its Yosida approximat...
-
作者：Fernandez, Damian; Solodov, Mikhail
作者单位：Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); National University of Cordoba; National University of Cordoba
摘要：At each iteration of the augmented Lagrangian algorithm, a nonlinear subproblem is being solved. The number of inner iterations (of some/any method) needed to obtain a solution of the subproblem, or even a suitable approximate stationary point, is in principle unknown. In this paper we show that to compute an approximate stationary point sufficient to guarantee local superlinear convergence of the augmented Lagrangian iterations, it is enough to solve two quadratic programming problems (or two...
-
作者：Royset, Johannes O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Upper semicontinuous (usc) functions arise in the analysis of maximization problems, distributionally robust optimization, and function identification, which includes many problems of nonparametric statistics. We establish that every usc function is the limit of a hypo-converging sequence of piecewise affine functions of the difference-of-max type and illustrate resulting algorithmic possibilities in the context of approximate solution of infinite-dimensional optimization problems. In an effor...
-
作者：Cheriyan, J.; Dippel, J.; Grandoni, F.; Khan, A.; Narayan, V. V.
作者单位：University of Waterloo; Universita della Svizzera Italiana; Indian Institute of Science (IISC) - Bangalore; McGill University
摘要：We present a 7/4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any givenMAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7/4 approximation algorithm for awell-structuredMAPinstance. Th...
-
作者：Embrechts, Paul; Liu, Haiyan; Mao, Tiantian; Wang, Ruodu
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Geneva; Michigan State University; Michigan State University; Chinese Academy of Sciences; University of Science & Technology of China, CAS; University of Waterloo
摘要：We study risk sharing problems with quantile-based risk measures and heterogeneous beliefs, motivated by the use of internal models in finance and insurance. Explicit forms of Pareto-optimal allocations and competitive equilibria are obtained by solving various optimization problems. For Expected Shortfall (ES) agents, Pareto-optimal allocations are shown to be equivalent to equilibrium allocations, and the equilibrium pricing measure is unique. For Value-at-Risk (VaR) agents or mixed VaR and ...
