Search

Sample average approximation (SAA) is a tractable approach for dealing with chance constrained programming, a challenging stochastic optimization problem. The constraint of SAA is characterized by the $0/1$ loss function which results in considerable complexities in devising numerical algorithms. Most existing methods have been devised based on reformulations of SAA, such as binary integer programming or relaxed problems. However, the development of viable methods to directly tackle SAA remains elusive, let alone providing theoretical guarantees. In this paper, we investigate a general $0/1$ constrained optimization, providing a new way to address SAA rather than its reformulations. Specifically, starting with deriving the Bouligand tangent and Fr$\acute{e}$chet normal cones of the $0/1$ constraint, we establish several optimality conditions. One of them can be equivalently expressed by a system of equations, enabling the development of a semismooth Newton-type algorithm. The algorithm demonstrates a locally superlinear or quadratic convergence rate under standard assumptions, along with nice numerical performance compared to several leading solvers.

It has been widely recognized that the 0/1 loss function is one of the most natural choices for modelling classification errors, and it has a wide range of applications including support vector machines and 1-bit compressed sensing. Due to the combinatorial nature of the 0/1 loss function, methods based on convex relaxations or smoothing approximations have dominated the existing research and are often able to provide approximate solutions of good quality. However, those methods are not optimizing the 0/1 loss function directly and hence no optimality has been established for the original problem. This paper aims to study the optimality conditions of the 0/1 function minimization, and for the first time to develop Newton's method that directly optimizes the 0/1 function with a local quadratic convergence under reasonable conditions. Extensive numerical experiments demonstrate its superior performance as one would expect from Newton-type methods.ions. Extensive numerical experiments demonstrate its superior performance as one would expect from Newton-type methods.

Data in the real world frequently involve binary status: truth or falsehood, positiveness or negativeness, similarity or dissimilarity, spam or non-spam, and to name a few, with applications into the regression, classification problems and so on. To characterize the binary status, one of the ideal functions is the Heaviside step function that returns one for one status and zero for the other. Hence, it is of dis-continuity. Because of this, the conventional approaches to deal with the binary status tremendously benefit from its continuous surrogates. In this paper, we target the Heaviside step function directly and study the Heaviside set constrained optimization: calculating the tangent and normal cones of the feasible set, establishing several first-order sufficient and necessary optimality conditions, as well as developing a Newton type method that enjoys locally quadratic convergence and excellent numerical performance.

As a tractable approach, regularization is frequently adopted in sparse optimization. This gives rise to the regularized optimization, aiming at minimizing the $\ell_0$ norm or its continuous surrogates that characterize the sparsity. From the continuity of surrogates to the discreteness of $\ell_0$ norm, the most challenging model is the $\ell_0$-regularized optimization. To conquer this hardness, there is a vast body of work on developing numerically effective methods. However, most of them only enjoy that either the (sub)sequence converges to a stationary point from the deterministic optimization perspective or the distance between each iterate and any given sparse reference point is bounded by an error bound in the sense of probability. In this paper, we develop a Newton-type method for the $\ell_0$-regularized optimization and prove that the generated sequence converges to a stationary point globally and quadratically under the standard assumptions, theoretically explaining that our method is able to perform surprisingly well.

Solutions to the linear complementarity problem (LCP) are naturally sparse in many applications such as bimatrix games and portfolio section problems. Despite that it gives rise to the hardness, sparsity makes optimization faster and enables relatively large scale computation. Motivated by this, we take the sparse LCP into consideration, investigating the existence and boundedness of its solution set as well as introducing a new merit function, which allows us to convert the problem into a sparsity constrained optimization. The function turns out to be continuously differentiable and twice continuously differentiable for some chosen parameters. Interestingly, it is also convex if the involved matrix is positive semidefinite. We then explore the relationship between the solution set to the sparse LCP and stationary points of the sparsity constrained optimization. Finally, Newton hard thresholding pursuit is adopted to solve the sparsity constrained model. Numerical experiments demonstrate that the problem can be efficiently solved through the new merit function.

Let $A$ be a real $M \times N$ measurement matrix and $b\in \mathbb{R}^M$ be an observations vector. The affine feasibility problem with sparsity and nonnegativity ($AFP_{SN}$ for short) is to find a sparse and nonnegative vector $x\in \mathbb{R}^N$ with $Ax=b$ if such $x$ exists. In this paper, we focus on establishment of optimization approach to solving the $AFP_{SN}$. By discussing tangent cone and normal cone of sparse constraint, we give the first necessary optimality conditions, $\alpha$-Stability, T-Stability and N-Stability, and the second necessary and sufficient optimality conditions for the related minimization problems with the $AFP_{SN}$. By adopting Armijo-type stepsize rule, we present a framework of gradient support projection algorithm for the $AFP_{SN}$ and prove its full convergence when matrix $A$ is $s$-regular. By doing some numerical experiments, we show the excellent performance of the new algorithm for the $AFP_{SN}$ without and with noise.