-
作者：Chi, Eric C.; Zhou, Hua; Lange, Kenneth
作者单位：University of California System; University of California Los Angeles; North Carolina State University; University of California System; University of California Los Angeles; University of California System; University of California Los Angeles
摘要：The problem of minimizing a continuously differentiable convex function over an intersection of closed convex sets is ubiquitous in applied mathematics. It is particularly interesting when it is easy to project onto each separate set, but nontrivial to project onto their intersection. Algorithms based on Newton's method such as the interior point method are viable for small to medium-scale problems. However, modern applications in statistics, engineering, and machine learning are posing proble...
-
作者：Lin, Gui-Hua; Xu, Mengwei; Ye, Jane J.
作者单位：Dalian University of Technology; University of Victoria
摘要：In this paper, we consider a simple bilevel program where the lower level program is a nonconvex minimization problem with a convex set constraint and the upper level program has a convex set constraint. By using the value function of the lower level program, we reformulate the bilevel program as a single level optimization problem with a nonsmooth inequality constraint and a convex set constraint. To deal with such a nonsmooth and nonconvex optimization problem, we design a smoothing projecte...
-
作者：Kim, Edward D.
作者单位：Delft University of Technology
摘要：We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of polyhedra. Another variant has superlinear asymptotic diameter, and together with some combinatorial operations, gives a concrete ap...
-
作者：Wachsmuth, Gerd
作者单位：Technische Universitat Chemnitz
摘要：In this paper we consider Newton's problem of finding a convex body of least resistance. This problem could equivalently be written as a variational problem over concave functions in . We propose two different methods for solving it numerically. First, we discretize this problem by writing the concave solution function as a infimum over a finite number of affine functions. The discretized problem could be solved by standard optimization software efficiently. Second, we conjecture that the opti...
-
作者：Devolder, Olivier; Glineur, Francois; Nesterov, Yurii
作者单位：Universite Catholique Louvain
摘要：We introduce the notion of inexact first-order oracle and analyze the behavior of several first-order methods of smooth convex optimization used with such an oracle. This notion of inexact oracle naturally appears in the context of smoothing techniques, Moreau-Yosida regularization, Augmented Lagrangians and many other situations. We derive complexity estimates for primal, dual and fast gradient methods, and study in particular their dependence on the accuracy of the oracle and the desired acc...
-
作者：Keller, Philipp W.; Levi, Retsef; Perakis, Georgia
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We propose a modeling and optimization framework to cast a broad range of fundamental multi-product pricing problems as tractable convex optimization problems. We consider a retailer offering an assortment of differentiated substitutable products to a population of customers that are price-sensitive. The retailer selects prices to maximize profits, subject to constraints on sales arising from inventory and capacity availability, market share goals, bounds on allowable prices and other consider...
-
作者：Aybat, N. S.; Iyengar, G.
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Columbia University
摘要：We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem [GRAPHICS] where denotes the vector of singular values of , the matrix norm denotes either the Frobenius, the nuclear, or the -operator norm of , the vector norm denotes either the -norm, -norm or the -norm; is a closed convex set and , , are linear operators from to vector spaces of appropriate dimensions. Basis pursuit, matrix completion, robust principal component pursuit (PCP), a...
-
作者：Locatelli, Marco; Schoen, Fabio
作者单位：University of Parma; University of Florence
摘要：In this paper we discuss convex envelopes for bivariate functions, satisfying suitable assumptions, over polytopes. We first propose a technique to compute the value and a supporting hyperplane of the convex envelope over a general two-dimensional polytope through the solution of a three-dimensional convex subproblem with continuously differentiable constraint functions. Then, for quadratic functions as well as for some polynomial and rational ones, again satisfying suitable assumptions, we sh...
-
作者：Adly, Samir; Haddad, Tahar; Thibault, Lionel
作者单位：Universite de Limoges; Universite de Jijel; Universite de Montpellier
摘要：In this paper, we analyze and discuss the well-posedness of two new variants of the so-called sweeping process, introduced by Moreau in the early 70s (Moreau in S,m Anal Convexe Montpellier, 1971) with motivation in plasticity theory. The first new variant is concerned with the perturbation of the normal cone to the moving convex subset , supposed to have a bounded variation, by a Lipschitz mapping. Under some assumptions on the data, we show that the perturbed differential measure inclusion h...
-
作者：Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：Lasserre's hierarchy is a sequence of semidefinite relaxations for solving polynomial optimization problems globally. This paper studies the relationship between optimality conditions in nonlinear programming theory and finite convergence of Lasserre's hierarchy. Our main results are: (i) Lasserre's hierarchy has finite convergence when the constraint qualification, strict complementarity and second order sufficiency conditions hold at every global minimizer, under the standard archimedean con...
