Convex and Nonsmooth Optimization

An optimal first-order primal-dual gap reduction framework for constrained convex optimization

Categories Convex and Nonsmooth Optimization

We introduce an analysis framework for constructing optimal first-order primal-dual methods for the prototypical constrained convex optimization tem- plate. While this class of methods offers scalability advantages in obtaining nu- merical solutions, they have the disadvantage of producing sequences that are only approximately feasible to the problem constraints. As a result, it is theoretically challenging … Read more

Techniques in Iterative Proton CT Image Reconstruction

Categories Biomedical Applications, Convex Optimization Tags , , , , , ,

This is a review paper on some of the physics, modeling, and iterative algorithms in proton computed tomography (pCT) image reconstruction. The primary challenge in pCT image reconstruction lies in the degraded spatial resolution resulting from multiple Coulomb scattering within the imaged object. Analytical models such as the most likely path (MLP) have been proposed … Read more

A composition projection method for convex feasibility problems

Categories Convex and Nonsmooth Optimization

In this article, we propose a composition projection algorithm for solving feasibility problem in Hilbert space. The convergence of the proposed algorithm are established by using gap vector which does not involve the nonempty intersection assumption. Moreover, we provide the sufficient and necessary condition for the convergence of the proposed method. ArticleDownload View PDF

Manifold Sampling for L1 Nonconvex Optimization

Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

We present a new algorithm, called manifold sampling, for the unconstrained minimization of a nonsmooth composite function $h\circ F$ when $h$ has known structure. In particular, by classifying points in the domain of the nonsmooth function $h$ into manifolds, we adapt search directions within a trust-region framework based on knowledge of manifolds intersecting the current … Read more

On Cournot-Nash-Walras equilibria and their computation

Categories Nonsmooth Optimization Tags , , , , ,

This paper considers a model of Cournot-Nash-Walras (CNW) equilibrium where the Cournot-Nash concept is used to capture equilibrium of an oligopolistic market with non-cooperative players/ rms who share a certain amount of a so-called rare resource needed for their production, and the Walras equilibrium determines the price of that rare resource. We prove the existence of … Read more

Degeneracy in Maximal Clique Decomposition for Semidefinite Programs

Categories Convex and Nonsmooth Optimization, Semi-definite Programming Tags , , , ,

Exploiting sparsity in Semidefinite Programs (SDP) is critical to solving large-scale problems. The chordal completion based maximal clique decomposition is the preferred approach for exploiting sparsity in SDPs. In this paper, we show that the maximal clique-based SDP decomposition is primal degenerate when the SDP has a low rank solution. We also derive conditions under … Read more

Quantitative recovery conditions for tree-based compressed sensing

Categories Applications - Science and Engineering, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

As shown in [9, 1], signals whose wavelet coefficients exhibit a rooted tree structure can be recovered — using specially-adapted compressed sensing algorithms — from just $n=\mathcal{O}(k)$ measurements, where $k$ is the sparsity of the signal. Motivated by these results, we introduce a simplified proportional-dimensional asymptotic framework which enables the quantitative evaluation of recovery guarantees … Read more

An accelerated non-Euclidean hybrid proximal extragradient-type Algorithm for convex-concave saddle-point Problems

Categories Convex Optimization Tags , , , , , , , ,

This paper describes an accelerated HPE-type method based on general Bregman distances for solving monotone saddle-point (SP) problems. The algorithm is a special instance of a non-Euclidean hybrid proximal extragradient framework introduced by Svaiter and Solodov [28] where the prox sub-inclusions are solved using an accelerated gradient method. It generalizes the accelerated HPE algorithm presented … Read more

New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more

Regularized HPE-type methods for solving monotone inclusions with improved pointwise iteration-complexity bounds

Categories Convex and Nonsmooth Optimization Tags , , ,

This paper studies the iteration-complexity of new regularized hybrid proximal extragradient (HPE)-type methods for solving monotone inclusion problems (MIPs). The new (regularized HPE-type) methods essentially consist of instances of the standard HPE method applied to regularizations of the original MIP. It is shown that its pointwise iteration-complexity considerably improves the one of the HPE method … Read more