Nonsmooth Algorithms and Nesterov’s Smoothing Techniques for Generalized Fermat-Torricelli Problems

In this paper we present some algorithms for solving a number of new models of facility location involving sets which generalize the classical Fermat-Torricelli problem. Our approach uses subgradient-type algorithms to cope with nondi erentiabilty of the distance functions therein. Another approach involves approximating nonsmooth optimization problems by smooth optimizations problems using Nesterov’s smoothing techniques. Convergence … Read more

Sparse Recovery on Euclidean Jordan Algebras

We consider the sparse recovery problem on Euclidean Jordan algebra (SREJA), which includes sparse signal recovery and low-rank symmetric matrix recovery as special cases. We introduce the restricted isometry property, null space property (NSP), and $s$-goodness for linear transformations in $s$-sparse element recovery on Euclidean Jordan algebra (SREJA), all of which provide sufficient conditions for … Read more

S-semigoodness for Low-Rank Semidefinite Matrix Recovery

We extend and characterize the concept of $s$-semigoodness for a sensing matrix in sparse nonnegative recovery (proposed by Juditsky , Karzan and Nemirovski [Math Program, 2011]) to the linear transformations in low-rank semidefinite matrix recovery. We show that s-semigoodness is not only a necessary and sufficient condition for exact $s$-rank semidefinite matrix recovery by a … Read more

An Alternating Direction Method for Chance-Constrained Optimization Problems with Discrete Distributions

We consider a chance-constrained optimization problem (CCOP), where the random variables follow finite discrete distributions. The problem is in general nonconvex and can be reformulated as a mixed-integer program. By exploiting the special structure of the probabilistic constraint, we propose an alternating direction method for finding suboptimal solutions of CCOP. At each iteration, this method … Read more

Successive Convex Approximations to Cardinality-Constrained Quadratic Programs: A DC Approach

In this paper we consider a cardinality-constrained quadratic program that minimizes a convex quadratic function subject to a cardinality constraint and linear constraints. This class of problems has found many applications, including portfolio selection, subset selection and compressed sensing. We propose a successive convex approximation method for this class of problems in which the cardinality … Read more

From CVaR to Uncertainty Set: Implications in Joint Chance Constrained Optimization

In this paper we review the different tractable approximations of individual chance constraint problems using robust optimization on a varieties of uncertainty set, and show their interesting connections with bounds on the condition-value-at-risk CVaR measure popularized by Rockafellar and Uryasev. We also propose a new formulation for approximating joint chance constrained problems that improves upon … Read more

The Rate of Convergence of the Augmented Lagrangian Method for Nonlinear Semidefinite Programming

We analyze the rate of local convergence of the augmented Lagrangian method for nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and certain variational analysis on the projection operator in the symmetric-matrix space. Without … Read more

Lowner’s Operator and Spectral Functions in Euclidean Jordan Algebras

We study analyticity, differentiability, and semismoothness of Lowner’s operator and spectral functions under the framework of Euclidean Jordan algebras. In particular, we show that many optimization-related classical results in the symmetric matrix space can be generalized within this framework. For example, the metric projection operator over any symmetric cone defined in a Euclidean Jordan algebra … Read more

A robust SQP method for mathematical programs with linear complementarity constraints

The relationship between the mathematical program with linear complementarity constraints (MPCC) and its inequality relaxation is studied. A new sequential quadratic programming (SQP) method is presented for solving the MPCC based on this relationship. A certain SQP technique is introduced to deal with the possible infeasibility of quadratic programming subproblems. Global convergence results are derived … Read more

Nonsmooth Matrix Valued Functions Defined by Singular Values

A class of matrix valued functions defined by singular values of nonsymmetric matrices is shown to have many properties analogous to matrix valued functions defined by eigenvalues of symmetric matrices. In particular, the (smoothed) matrix valued Fischer-Burmeister function is proved to be strongly semismooth everywhere. This result is also used to show the strong semismoothness … Read more