-
作者：Yang, Wei Hong; Yuan, Xiaoming
作者单位：Fudan University; Hong Kong Baptist University
摘要：The globally uniquely solvable (GUS) property of the linear transformation of the linear complementarity problems over symmetric cones has been studied recently by Gowda et al. via the approach of Euclidean Jordan algebra. In this paper, we contribute a new approach to characterizing the GUS property of the linear transformation of the second-order cone linear complementarity problems (SOCLCP) via some basic linear algebra properties of the involved matrix of SOCLCP. Some more concrete and che...
-
作者：Gardiner, Bryan; Lucet, Yves
作者单位：University of British Columbia; University of British Columbia Okanagan
摘要：We present a new algorithm to compute the Legendre-Fenchel conjugate of convex piecewise linear-quadratic (PLQ) bivariate functions. The algorithm stores a function using a (primal) planar arrangement. It then computes the (dual) arrangement associated with the conjugate by looping through vertices, edges, and faces in the primal arrangement and building associated dual vertices, edges, and faces. Using optimal computational geometry data structures, the algorithm has a linear time worst-case ...
-
作者：Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：Consider the optimization problem of minimizing a polynomial function subject to polynomial constraints. Atypical approach for solving it globally is applying Lasserre's hierarchy of semidefinite relaxations, based on either Putinar's or Schmudgen's Positivstellensatz. A practical question in applications is: how to certify its convergence and get minimizers? In this paper, we propose flat truncation as a certificate for this purpose. Assume the set of global minimizers is nonempty and finite....
-
作者：Goldfarb, Donald; Ma, Shiqian; Scheinberg, Katya
作者单位：Columbia University; University of Minnesota System; University of Minnesota Twin Cities; Lehigh University
摘要：We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most iterations to obtain an -optimal solution, while our accelerated (i.e., fast) versions of them require at most iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smoot...
-
作者：Hungerlaender, P.; Rendl, F.
作者单位：University of Klagenfurt
摘要：Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element u is before v in the ordering. In the second case, the profit depends on whether u is before v and r is before s. The linear ordering problem is well studied, with exact solution methods based on polyhedral relaxations. The quadratic ordering problem does not seem to...
-
作者：Goberna, M. A.; Jeyakumar, V.; Li, G.; Lopez, M. A.
作者单位：Universitat d'Alacant; University of New South Wales Sydney
摘要：In this paper, we propose a duality theory for semi-infinite linear programming problems under uncertainty in the constraint functions, the objective function, or both, within the framework of robust optimization. We present robust duality by establishing strong duality between the robust counterpart of an uncertain semi-infinite linear program and the optimistic counterpart of its uncertain Lagrangian dual. We show that robust duality holds whenever a robust moment cone is closed and convex. ...
-
作者：Dong, Hongbo; Anstreicher, Kurt
作者单位：University of Iowa; University of Iowa
摘要：The cone of Completely Positive (CP) matrices can be used to exactly formulate a variety of NP-Hard optimization problems. A tractable relaxation for CP matrices is provided by the cone of Doubly Nonnegative (DNN) matrices; that is, matrices that are both positive semidefinite and componentwise nonnegative. A natural problem in the optimization setting is then to separate a given DNN but non-CP matrix from the cone of CP matrices. We describe two different constructions for such a separation t...
-
作者：Sagastizabal, Claudia
作者单位：Instituto Nacional de Matematica Pura e Aplicada (IMPA)
摘要：We consider minimization of nonsmooth functions which can be represented as the composition of a positively homogeneous convex function and a smooth mapping. This is a sufficiently rich class that includes max-functions, largest eigenvalue functions, and norm-1 regularized functions. The bundle method uses an oracle that is able to compute separately the function and subgradient information for the convex function, and the function and derivatives for the smooth mapping. With this information,...
-
作者：Lan, Guanghui; Monteiro, Renato D. C.
作者单位：State University System of Florida; University of Florida; University System of Georgia; Georgia Institute of Technology
摘要：This paper considers a special but broad class of convex programming problems whose feasible region is a simple compact convex set intersected with the inverse image of a closed convex cone under an affine transformation. It studies the computational complexity of quadratic penalty based methods for solving the above class of problems. An iteration of these methods, which is simply an iteration of Nesterov's optimal method (or one of its variants) for approximately solving a smooth penalizatio...
-
作者：Fernandez, Damian
作者单位：National University of Cordoba
摘要：The quasi-Newton strategy presented in this paper preserves one of the most important features of the stabilized Sequential Quadratic Programming method, the local convergence without constraint qualifications assumptions. It is known that the primal-dual sequence converges quadratically assuming only the second-order sufficient condition. In this work, we show that if the matrices are updated by performing a minimization of a Bregman distance (which includes the classic updates), the quasi-Ne...
