-
作者：Cartis, Coralia; Gould, Nicholas I. M.; Toint, Philippe L.
作者单位：University of Edinburgh; UK Research & Innovation (UKRI); Science & Technology Facilities Council (STFC); STFC Rutherford Appleton Laboratory; University of Namur
摘要：The complexity of finding -approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for t...
-
作者：Richtarik, Peter; Takac, Martin
作者单位：University of Edinburgh
摘要：In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an -accurate solution with probability at least in at most iterations, where is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341-362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removi...
-
作者：Ding, Chao; Sun, Defeng; Ye, Jane J.
作者单位：Chinese Academy of Sciences; National University of Singapore; National University of Singapore; University of Victoria
摘要：In this paper we consider a mathematical program with semidefinite cone complementarity constraints (SDCMPCC). Such a problem is a matrix analogue of the mathematical program with (vector) complementarity constraints (MPCC) and includes MPCC as a special case. We first derive explicit formulas for the proximal and limiting normal cone of the graph of the normal cone to the positive semidefinite cone. Using these formulas and classical nonsmooth first order necessary optimality conditions we de...
-
作者：Lu, Zhaosong
作者单位：Simon Fraser University
摘要：In this paper we consider regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the IHT method for finding an -local-optimal solution. We then propose a method for solving regularized convex cone programming by applying th...
-
作者：Lasserre, Jean B.
作者单位：Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse
摘要：We provide convergent hierarchies for the convex cone of copositive matrices and its dual , the cone of completely positive matrices. In both cases the corresponding hierarchy consists of nested spectrahedra and provide outer (resp. inner) approximations for (resp. for its dual ), thus complementing previous inner (resp. outer) approximations for (for ). In particular, both inner and outer approximations have a very simple interpretation. Finally, extension to -copositivity and -complete posit...
-
作者：Louveaux, Quentin; Poirrier, Laurent
作者单位：University of Liege
摘要：We consider the question of finding deep cuts from a model with two rows of the type . To do that, we show how to reduce the complexity of setting up the polar of from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore, we present an algorithm that avoids computing all integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice.
-
作者：Cominetti, Roberto; Guzman, Cristobal
作者单位：Universidad de Chile; University System of Georgia; Georgia Institute of Technology
摘要：In this paper we consider an integrated model for TCP/IP protocols with multipath routing. The model combines a Network Utility Maximization for rate control based on end-to-end queueing delays, with a Markovian Traffic Equilibrium for routing based on total expected delays. We prove the existence of a unique equilibrium state which is characterized as the solution of an unconstrained strictly convex program. A distributed algorithm for solving this optimization problem is proposed, with a bri...
-
作者：Ben-Tal, Aharon; den Hertog, Dick
作者单位：Technion Israel Institute of Technology; Tilburg University; Tilburg University
摘要：The problem of minimizing a quadratic objective function subject to one or two quadratic constraints is known to have a hidden convexity property, even when the quadratic forms are indefinite. The equivalent convex problem is a semidefinite one, and the equivalence is based on the celebrated S-lemma. In this paper, we show that when the quadratic forms are simultaneously diagonalizable (SD), it is possible to derive an equivalent convex problem, which is a conic quadratic (CQ) one, and as such...
-
作者：Artacho, Francisco J. Aragon; Borwein, Jonathan M.; Martin-Marquez, Victoria; Yao, Liangjin
作者单位：University of Newcastle; King Abdulaziz University; University of Sevilla
摘要：In this paper, we study convex analysis and its theoretical applications. We first apply important tools of convex analysis to Optimization and to Analysis. We then show various deep applications of convex analysis and especially infimal convolution in Monotone Operator Theory. Among other things, we recapture the Minty surjectivity theorem in Hilbert space, and present a new proof of the sum theorem in reflexive spaces. More technically, we also discuss autoconjugate representers for maximall...
-
作者：Frank, Andras; Kiraly, Tamas; Pap, Julia; Pritchard, David
作者单位：Eotvos Lorand University; Princeton University
摘要：Generalized polymatroids are a family of polyhedra with several nice properties and applications. One property of generalized polymatroids used widely in existing literature is total dual laminarity; we make this notion explicit and show that only generalized polymatroids have this property. Using this we give a polynomial-time algorithm to check whether a given linear program defines a generalized polymatroid, and whether it is integral if so. Additionally, whereas it is known that the inters...
