Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConvex minimization problems with weak constraint qualifications
97
0
0.0
(
0
)
Authors
Christian Leonard
Ask ChatGPT about the research
No Arabic abstract
One revisits the standard saddle-point method based on conjugate duality for solving convex minimization problems. Our aim is to reduce or remove unnecessary topological restrictions on the constraint set. Dual equalities and characterizations of the minimizers are obtained with weak or without constraint qualifications. The main idea is to work with intrinsic topologies which reflect some geometry of the objective function. The abstract results of this article are applied in other papers to the Monge-Kantorovich optimal transport problem and the minimization of entropy functionals.
rate research
Read More
Shape-constrained convex regression problem deals with fitting a convex function to the observed data, where additional constraints are imposed, such as component-wise monotonicity and uniform Lipschitz continuity. This paper provides a unified framework for computing the least squares estimator of a multivariate shape-constrained convex regression function in $mathbb{R}^d$. We prove that the least squares estimator is computable via solving an essentially constrained convex quadratic programming (QP) problem with $(n+1)d$ variables, $n(n-1)$ linear inequality constraints and $n$ possibly non-polyhedral inequality constraints, where $n$ is the number of data points. To efficiently solve the generally very large-scale convex QP, we design a proximal augmented Lagrangian method (proxALM) whose subproblems are solved by the semismooth Newton method (SSN). To further accelerate the computation when $n$ is huge, we design a practical implementation of the constraint generation method such that each reduced problem is efficiently solved by our proposed proxALM. Comprehensive numerical experiments, including those in the pricing of basket options and estimation of production functions in economics, demonstrate that our proposed proxALM outperforms the state-of-the-art algorithms, and the proposed acceleration technique further shortens the computation time by a large margin.
The divergence minimization problem plays an important role in various fields. In this note, we focus on differentiable and strictly convex divergences. For some minimization problems, we show the minimizer conditions and the uniqueness of the minimizer without assuming a specific form of divergences. Furthermore, we show geometric properties related to the minimization problems.
We propose faster methods for unconstrained optimization of emph{structured convex quartics}, which are convex functions of the form begin{equation*} f(x) = c^top x + x^top mathbf{G} x + mathbf{T}[x,x,x] + frac{1}{24} mathopen| mathbf{A} x mathclose|_4^4 end{equation*} for $c in mathbb{R}^d$, $mathbf{G} in mathbb{R}^{d times d}$, $mathbf{T} in mathbb{R}^{d times d times d}$, and $mathbf{A} in mathbb{R}^{n times d}$ such that $mathbf{A}^top mathbf{A} succ 0$. In particular, we show how to achieve an $epsilon$-optimal minimizer for such functions with only $O(n^{1/5}log^{O(1)}(mathcal{Z}/epsilon))$ calls to a gradient oracle and linear system solver, where $mathcal{Z}$ is a problem-dependent parameter. Our work extends recent ideas on efficient tensor methods and higher-order acceleration techniques to develop a descent method for optimizing the relevant quartic functions. As a natural consequence of our method, we achieve an overall cost of $O(n^{1/5}log^{O(1)}(mathcal{Z} / epsilon))$ calls to a gradient oracle and (sparse) linear system solver for the problem of $ell_4$-regression when $mathbf{A}^top mathbf{A} succ 0$, providing additional insight into what may be achieved for general $ell_p$-regression. Our results show the benefit of combining efficient higher-order methods with recent acceleration techniques for improving convergence rates in fundamental convex optimization problems.
We propose a new framework for deriving screening rules for convex optimization problems. Our approach covers a large class of constrained and penalized optimization formulations, and works in two steps. First, given any approximate point, the structure of the objective function and the duality gap is used to gather information on the optimal solution. In the second step, this information is used to produce screening rules, i.e. safely identifying unimportant weight variables of the optimal solution. Our general framework leads to a large variety of useful existing as well as new screening rules for many applications. For example, we provide new screening rules for general simplex and $L_1$-constrained problems, Elastic Net, squared-loss Support Vector Machines, minimum enclosing ball, as well as structured norm regularized problems, such as group lasso.
We consider the problem of minimizing a block separable convex function (possibly nondifferentiable, and including constraints) plus Laplacian regularization, a problem that arises in applications including model fitting, regularizing stratified models, and multi-period portfolio optimization. We develop a distributed majorization-minimization method for this general problem, and derive a complete, self-contained, general, and simple proof of convergence. Our method is able to scale to very large problems, and we illustrate our approach on two applications, demonstrating its scalability and accuracy.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
