New RIC Bounds via l_q-minimization with 0
The restricted isometry constants (RICs) play an important role in exact recovery theory of sparse signals via l_q(0
Nonsmooth Optimization
New RIC Bounds via l_q-minimization with 0
A direct splitting method for nonsmooth variational inequalities
We propose a direct splitting method for solving nonsmooth variational inequality problems in Hilbert spaces. The weak convergence is established, when the operator is the sum of two point-to-set and monotone operators. The proposed method is a natural extension of the incremental subgradient method for nondifferentiable optimization, which explores strongly the structure of the operator … Read more
Full stability of locally optimal solutions in second-order cone programming
The paper presents complete characterizations of Lipschitzian full stability of locally optimal solutions to problems of second-order cone programming (SOCP) expressed entirely in terms of their initial data. These characterizations are obtained via appropriate versions of the quadratic growth and strong second-order sucient conditions under the corresponding constraint quali cations. We also establish close relationships between … Read more
On smoothness properties of optimal value functions at the boundary of their domain under complete convexity
This article studies continuity and directional differentiability properties of optimal value functions, in particular at boundary points of their domain. We extend and complement standard continuity results from W.W. Hogan, Point-to-set maps in mathematical programming, SIAM Review, Vol. 15 (1973), 591-603, for abstract feasible set mappings under complete convexity as well as standard differentiability results … Read more
KKT Reformulation and Necessary Conditions for Optimality in Nonsmooth Bilevel Optimization
For a long time, the bilevel programming problem has essentially been considered as a special case of mathematical programs with equilibrium constraints (MPECs), in particular when the so-called KKT reformulation is in question. Recently though, this widespread believe was shown to be false in general. In this paper, other aspects of the difference between both … Read more
Level Bundle Methods for Constrained Convex Optimization with Various Oracles
We propose restricted memory level bundle methods for minimizing constrained convex nonsmooth optimization problems whose objective and constraint functions are known through oracles (black-boxes) that might provide inexact information. Our approach is general and covers many instances of inexact oracles, such as upper, lower and on-demand oracles. We show that the proposed level bundle methods … Read more
Nonsmooth Optimization Using Uncontrolled Inexact Information
We consider convex nonsmooth optimization problems whose objective function is known through a (fine) oracle together with some additional (cheap but poor) information – formalized as a second coarse oracle with uncontrolled inexactness. It is the case when the objective function is itself the output of an optimization solver, using a branch-and-bound procedure, or decomposing … Read more
Robust convex relaxation for the planted clique and densest k-subgraph problems
We consider the problem of identifying the densest k-node subgraph in a given graph. We write this problem as an instance of rank-constrained cardinality minimization and then relax using the nuclear and l1 norms. Although the original combinatorial problem is NP-hard, we show that the densest k-subgraph can be recovered from the solution of our … Read more
GENERALIZATIONS OF THE DENNIS-MOR\’E THEOREM II
This paper is a continuation of our previous paper were we presented generalizations of the Dennis-Mor\’e theorem to characterize q-superliner convergences of quasi-Newton methods for solving equations and variational inequalities in Banach spaces. Here we prove Dennis-Mor\’e type theorems for inexact quasi-Newton methods applied to variational inequalities in finite dimensions. We first consider variational inequalities … Read more
Second-order growth, tilt stability, and metric regularity of the subdifferential
This paper sheds new light on several interrelated topics of second-order variational analysis, both in finite and infinite-dimensional settings. We establish new relationships between second-order growth conditions on functions, the basic properties of metric regularity and subregularity of the limiting subdifferential, tilt-stability of local minimizers, and positive definiteness/semidefiniteness properties of the second-order subdifferential (or generalized … Read more