In this paper, we show that for a large class of optimization problems, the Lagrange multiplier rule can be derived from the so-called approximate multiplier rule. In establishing the link between the approximate and the exact multiplier rule we first derive an approximate multiplier rule for a very general class of optimization problems using the … Read more
This paper reviews the Bregman methods, analyzes the linearized Bregman method, and proposes fast generalization of the latter for solving the basis pursuit and related problems. The analysis shows that the linearized Bregman method has the exact penalty property, namely, it converges to an exact solution of the basis pursuit problem if and only if … Read more
We describe techniques combining the S-lemma and computation of projected quadratics which experimentally yield strong bounds on the value of convex quadratic programs with nonconvex constraints Citationunpublished report, Columbia University, March 2009ArticleDownload View PDF
This paper presents a Nash equilibrium model where the underlying objective functions involve uncertainty and nonsmoothness. The well known sample average approximation method is applied to solve the problem and the first order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a … Read more
This paper considers a special class of convex programming (CP) problems whose feasible regions consist of a simple compact convex set intersected with an affine manifold. We present first-order methods for this class of problems based on an inexact version of the classical augmented Lagrangian (AL) approach, where the subproblems are approximately solved by means … Read more
Interior point methods have proven very successful at solving linear programming problems. When an explicit linear programming formulation is either not available or is too large to employ directly, a column generation approach can be used. Examples of column generation approaches include cutting plane methods for integer programming and decomposition methods for many classes of … Read more
Continuity of set-valued maps is hereby revisited: after recalling some basic concepts of variational analysis and a short description of the State-of-the-Art, we obtain as by-product two Sard type results concerning local minima of scalar and vector valued functions. Our main result though, is inscribed in the framework of tame geometry, stating that a closed-valued … Read more
We present a row-by-row (RBR) method for solving semidefinite programming (SDP) problem based on solving a sequence of problems obtained by restricting the n-dimensional positive semidefinite constraint on the matrix X. By fixing any (n-1)-dimensional principal submatrix of X and using its (generalized) Schur complement, the positive semidefinite constraint is reduced to a simple second-order … Read more
Accurate signal recovery or image reconstruction from indirect and possibly under- sampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. Inspired by recent breakthroughs in the development of novel fi rst-order methods in convex optimization, most notably Nesterov’s smoothing technique, this paper … Read more
We study a first-order method to find the minimum cross-sectional area ellipsoidal cylinder containing a finite set of points. This problem arises in optimal design in statistics when one is interested in a subset of the parameters. We provide convex formulations of this problem and its dual, and analyze a method based on the Frank-Wolfe … Read more