In this work we consider the problem $\min_x \{ f(x) + P(x) \}$, where $f$ is $\mathcal{C}^2$ and $P$ is nonsmooth, but contains an underlying smooth substructure. Specifically, we assume the function $P$ is prox-regular partly smooth with respect to a active manifold $\M$. Recent work by Tseng and Yun \cite{tseng-yun-2009}, showed that such a … Read more
We consider the inversion of a linear operator with centered Gaussian white noise by MAP estimation with a Gaussian prior distribution on the solution. The actual estimator is computed approximately by a numerical method. We propose a relation between the stationarity measure of this approximate solution to the mean square error of the exact solution. … Read more
Recently, several optimization approaches for portfolio selection have been proposed in order to alleviate the estimation error in the optimal portfolio. Among such are the norm-constrained variance minimization and the robust portfolio models. In this paper, we examine the role of the norm constraint in the portfolio optimization from several directions. First, it is shown … Read more
To minimize or upper-bound the value of a function “robustly”, we might instead minimize or upper-bound the “epsilon-robust regularization”, defined as the map from a point to the maximum value of the function within an epsilon-radius. This regularization may be easy to compute: convex quadratics lead to semidefinite-representable regularizations, for example, and the spectral radius … Read more
The integration to steady state of many initial value ODEs and PDEs using the forward Euler method can alternatively be considered as gradient descent for an associated minimization problem. Greedy algorithms such as steepest descent for determining the step size are as slow to reach steady state as is forward Euler integration with the best … Read more
The basis pursuit problem seeks a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise (BPDN) fits the least-squares problem only approximately, and a single parameter determines a curve that traces the optimal trade-off between the least-squares fit and the one-norm of the solution. We prove that this curve is convex and continuously … Read more
This paper studies an alternative technique to interior point methods and nonlinear methods for semidefinite programming (SDP). The approach based on classical quadratic regularizations leads to an algorithm, generalizing a recent method called “boundary point method”. We study the theoretical properties of this algorithm and we show that in practice it behaves very well on … Read more
A regularized Newton-like method for solving nonnegative least-squares problems is proposed and analysed in this paper. A preconditioner for KKT systems arising in the method is introduced and spectral properties of the preconditioned matrix are analysed. A bound on the condition number of the preconditioned matrix is provided. The bound does not depend on the … Read more
We consider solving minimization problems with $\ell_1$-regularization: $$\min \|x\|_1 + \mu f(x),$$ particularly for $f(x) = \frac{1}{2}\|Ax-b\|_M^2$ where $A \in \R^{m \times n}$ with $m < n$. Our goal is to construct efficient and robust algorithms for solving large-scale problems with dense data, and our approach is based on two powerful algorithmic ideas, operator-splitting and ... Read more
The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a … Read more