The Penalty Functions Method and Multiplier Rules Based on the Mordukhovich Subdifferential

We show that the finite-dimensional Fritz John multiplier rule, which is based on the limiting/Mordukhovich subdifferential, can be proved by using differentiable penalty functions and the basic calculus tools in variational analysis. The corresponding Kuhn–Tucker multiplier rule is derived from the Fritz John multiplier rule by imposing a constraint qualification condition or the exactness of an ?₁ penalty function. Complementing the existing proofs, our proofs provide another viewpoint on the fundamental multiplier rules employing the Mordukhovich subdifferential.     

Variational Analysis on Local Sharp Minima via Exact Penalization

In this paper we study local sharp minima of the nonlinear programming problem via exact penalization. Utilizing generalized differentiation tools in variational analysis such as subderivatives and regular subdifferentials, we obtain some primal and dual characterizations for a penalty function associated with the nonlinear programming problem to have a local sharp minimum. These general results are then applied to the ? _p penalty function with 0 ≤ p ≤ 1. In particular, we present primal and dual equivalent conditions in terms of the original data of the nonlinear programming problem, which guarantee that the ? _p penalty function has a local sharp minimum with a finite penalty parameter in the case of \(p\in (\frac {1}{2}, 1]\) and \(p=\frac {1}{2}\) respectively. By assuming the Guignard constraint qualification (resp. the generalized Guignard constraint qualification), we also show that a local sharp minimum of the nonlinear programming problem can be an exact local sharp minimum of the ? _p penalty function with p ∈ [0, 1] (resp. \(p\in [0, \frac {1}{2}]\)). Finally, we give some formulas for calculating the smallest penalty parameter for a penalty function to have a local sharp minimum.     

An interior-point piecewise linear penalty method for nonlinear programming

We present an interior-point penalty method for nonlinear programming (NLP), where the merit function consists of a piecewise linear penalty function and an ? ₂-penalty function. The piecewise linear penalty function is defined by a set of break points that correspond to pairs of values of the barrier function and the infeasibility measure at a subset of previous iterates and this set is updated at every iteration. The ? ₂-penalty function is a traditional penalty function defined by a single penalty parameter. At every iteration the step direction is computed from a regularized Newton system of the first-order equations of the barrier problem proposed in Chen and Goldfarb (Math Program 108:1?C36, 2006). Iterates are updated using a line search. In particular, a trial point is accepted if it provides a sufficient reduction in either of the penalty functions. We show that the proposed method has the same strong global convergence properties as those established in Chen and Goldfarb (Math Program 108:1?C36, 2006). Moreover, our method enjoys fast local convergence. Specifically, for each fixed small barrier parameter???, iterates in a small neighborhood (roughly within o(??)) of the minimizer of the barrier problem converge Q-quadratically to the minimizer. The overall convergence rate of the iterates to the solution of the nonlinear program is Q-superlinear.     

One-Step Estimator Paths for Concave Regularization

The statistics literature of the past 15 years has established many favorable properties for sparse diminishing-bias regularization: techniques that can roughly be understood as providing estimation under penalty functions spanning the range of concavity between ?₀ and ?₁ norms. However, lasso ?₁-regularized estimation remains the standard tool for industrial Big Data applications because of its minimal computational cost and the presence of easy-to-apply rules for penalty selection. In response, this article proposes a simple new algorithm framework that requires no more computation than a lasso path: the path of one-step estimators (POSE) does ?₁ penalized regression estimation on a grid of decreasing penalties, but adapts coefficient-specific weights to decrease as a function of the coefficient estimated in the previous path step. This provides sparse diminishing-bias regularization at no extra cost over the fastest lasso algorithms. Moreover, our gamma lasso implementation of POSE is accompanied by a reliable heuristic for the fit degrees of freedom, so that standard information criteria can be applied in penalty selection. We also provide novel results on the distance between weighted-?₁ and ?₀ penalized predictors; this allows us to build intuition about POSE and other diminishing-bias regularization schemes. The methods and results are illustrated in extensive simulations and in application of logistic regression to evaluating the performance of hockey players. Supplementary materials for this article are available online.     

Sparse Steinian Covariance Estimation

We consider a new method for sparse covariance matrix estimation which is motivated by previous results for the so-called Stein-type estimators. Stein proposed a method for regularizing the sample covariance matrix by shrinking together the eigenvalues; the amount of shrinkage is chosen to minimize an unbiased estimate of the risk (UBEOR) under the entropy loss function. The resulting estimator has been shown in simulations to yield significant risk reductions over the maximum likelihood estimator. Our method extends the UBEOR minimization problem by adding an ?₁ penalty on the entries of the estimated covariance matrix, which encourages a sparse estimate. For a multivariate Gaussian distribution, zeros in the covariance matrix correspond to marginal independences between variables. Unlike the ?₁-penalized Gaussian likelihood function, our penalized UBEOR objective is convex and can be minimized via a simple block coordinate descent procedure. We demonstrate via numerical simulations and an analysis of microarray data from breast cancer patients that our proposed method generally outperforms other methods for sparse covariance matrix estimation and can be computed efficiently even in high dimensions.     

Interior-point ℓ 2-penalty methods for nonlinear programming with strong global convergence properties

We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an ℓ₂-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush-Kuhn-Tucker (KKT) point of the barrier subproblem, or a Fritz-John (FJ) point of the original problem that fails to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ); if the penalty parameter tends to infinity, there is a limit point that is either an infeasible FJ point of the inequality constrained feasibility problem (an infeasible stationary point of the infeasibility measure if slack variables are added) or a FJ point of the original problem at which the MFCQ fails to hold. Numerical results are given that illustrate these outcomes. Research supported by the Presidential Fellowship of Columbia University. Research supported in part by NSF Grant DMS 01-04282, DOE Grant DE-FG02-92EQ25126 and DNR Grant N00014-03-0514.     

Detecting Changes in Slope With an L0 Penalty

While there are many approaches to detecting changes in mean for a univariate time series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging: simple binary segmentation procedures do not work for this problem, while existing dynamic programming methods that work for the change in mean problem cannot be used for detecting changes in slope. We present a novel dynamic programming approach, CPOP, for finding the “best” continuous piecewise linear fit to data under a criterion that measures fit to data using the residual sum of squares, but penalizes complexity based on an L₀ penalty on changes in slope. We prove that detecting changes in this manner can lead to consistent estimation of the number of changepoints, and show empirically that using an L₀ penalty is more reliable at estimating changepoint locations than using an L₁ penalty. Empirically CPOP has good computational properties, and can analyze a time series with 10,000 observations and 100 changes in a few minutes. Our method is used to analyze data on the motion of bacteria, and provides better and more parsimonious fits than two competing approaches. Supplementary material for this article is available online.     

Dynamical bifurcation for the Kuramoto-Sivashinsky equation

In this paper, by using the center manifold reduction method, together with the eigenvalue analysis, we made bifurcation analysis for the Kuramoto-Sivashinsky equation, and proved that the Kuramoto-Sivashinsky equation with constraint condition bifurcates an attractor A_λ as λ crossed the first critical value λ₀=1 under the two cases. Our analysis was based on a new and mature attractor bifurcation theory developed by Ma and Wang (2005) [17] and [18].     

Variable Selection via A Combination of the L0 and L1 Penalties

Variable selection is an important aspect of high-dimensional statistical modeling, particularly in regression and classification. In the regularization framework, various penalty functions are used to perform variable selection by putting relatively large penalties on small coefficients. The L₁ penalty is a popular choice because of its convexity, but it produces biased estimates for the large coefficients. The L₀ penalty is attractive for variable selection because it directly penalizes the number of non zero coefficients. However, the optimization involved is discontinuous and non convex, and therefore it is very challenging to implement. Moreover, its solution may not be stable. In this article, we propose a new penalty that combines the L₀ and L₁ penalties. We implement this new penalty by developing a global optimization algorithm using mixed integer programming (MIP). We compare this combined penalty with several other penalties via simulated examples as well as real applications. The results show that the new penalty outperforms both the L₀ and L₁ penalties in terms of variable selection while maintaining good prediction accuracy.     

Nonlinear programming and nonsmooth optimization by successive linear programming

Methods are considered for solving nonlinear programming problems using an exactl ₁ penalty function. LP-like subproblems incorporating a trust region constraint are solved successively both to estimate the active set and to provide a foundation for proving global convergence. In one particular method, second order information is represented by approximating the reduced Hessian matrix, and Coleman-Conn steps are taken. A criterion for accepting these steps is given which enables the superlinear convergence properties of the Coleman-Conn method to be retained whilst preserving global convergence and avoiding the Maratos effect. The methods generalize to solve a wide range of composite nonsmooth optimization problems and the theory is presented in this general setting. A range of numerical experiments on small test problems is described.     

Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001     

Numerical quadratic energy minimization bound to convex constraints in thin-film micromagnetics

We analyze the reduced model for thin-film devices in stationary micromagnetics proposed in DeSimone et?al. (R Soc Lond Proc Ser A Math Phys Eng Sci 457(2016):2983?C2991, 2001). We introduce an appropriate functional analytic framework and prove well-posedness of the model in that setting. The scheme for the numerical approximation of solutions consists of two ingredients: The energy space is discretized in a conforming way using Raviart?CThomas finite elements; the non-linear but convex side constraint is treated with a penalty method. This strategy yields a convergent sequence of approximations as discretization and penalty parameter vanish. The proof generalizes to a large class of minimization problems and is of interest beyond the scope of thin-film micromagnetics.     

An efficient algorithm for structured sparse quantile regression

An efficient algorithm is derived for solving the quantile regression problem combined with a group sparsity promoting penalty. The group sparsity of the regression parameters is achieved by using a \(\ell _{1,\infty }\) -norm penalty (or constraint) on the regression parameters. The algorithm is efficient in the sense that it obtains the regression parameters for a wide range of penalty parameters, thus enabling easy application of a model selection criteria afterwards. A Matlab implementation of the proposed algorithm is provided and some applications of the methods are studied.     

Concentration of norms and eigenvalues of random matrices

We prove concentration results for ?_pⁿ operator norms of rectangular random matrices and eigenvalues of self-adjoint random matrices. The random matrices we consider have bounded entries which are independent, up to a possible self-adjointness constraint. Our results are based on an isoperimetric inequality for product spaces due to Talagrand.     

Linear Programming with Uncertain Data: Some Extensions to Robust Optimization

An optimization problem often has some uncertain data, and the optimum of a linear program can be very sensitive to small changes in the data. Such a problem can often be modified to a robust program, which is more stable to such changes. Various methods for this are compared, including requiring all versions of the data to be satisfied together (but they may be inconsistent), worst-case MAX?CMIN model, and various models where deviations incur penalty costs. Existing methods require substantial computation. It is shown here that smaller computations often suffice; not all cases need be considered. Other penalty methods are suggested, using different norms. Moreover, perturbations of constraint coefficients can be represented by suitable perturbations of a requirement vector.     

Stability of penalty finite-element methods for nonconforming problems

Penalty methods have been proposed as a viable method for enforcing interelement continuity constraints on nonconforming elements. Particularly for fourth-order problems in which C¹-continuity leads to elements of high degree or complex composite elements, the use of penalty methods to enforce the C¹-continuity constraint appears promising. In this study we demonstrate equivalence of the finite-element penalty method to a hybrid method and provide a stability analysis which implies that the penalty method is stable only if reduced integration of a certain order is used. Numerical experiments confirm that the penalty method fails if this condition is not met.     

Fused-MCP With Application to Signal Processing

ABSTRACT

Friedman et al. proposed the fused lasso signal approximator (FLSA) to denoise piecewise constant signals by penalizing the ?₁ differences between adjacent signal points. In this article, we propose a new method, referred to as the fused-MCP, by combining the minimax concave penalty (MCP) with the fusion penalty. The fused-MCP performs better than the FLSA in maintaining the profile of the original signal and preserving the edge structure. We show that, with a high probability, the fused-MCP selects the right change-points and has the oracle property, unlike the FLSA. We further show that the fused-MCP achieves the same l₂ error rate as the FLSA. We develop algorithms to solve fused-MCP problems, either by transforming them into MCP regression problems or by using an adjusted majorization-minimization algorithm. Simulation and experimental results show the effectiveness of our method. Supplementary material for this article is available online.     

Sparse Biclustering of Transposable Data

We consider the task of simultaneously clustering the rows and columns of a large transposable data matrix. We assume that the matrix elements are normally distributed with a bicluster-specific mean term and a common variance, and perform biclustering by maximizing the corresponding log-likelihood. We apply an ?₁ penalty to the means of the biclusters to obtain sparse and interpretable biclusters. Our proposal amounts to a sparse, symmetrized version of k-means clustering. We show that k-means clustering of the rows and of the columns of a data matrix can be seen as special cases of our proposal, and that a relaxation of our proposal yields the singular value decomposition. In addition, we propose a framework for biclustering based on the matrix-variate normal distribution. The performances of our proposals are demonstrated in a simulation study and on a gene expression dataset. This article has supplementary material online.     

Learning with coefficient-based regularization and ℓ1 −penalty

The least-square regression problem is considered by coefficient-based regularization schemes with ?¹??penalty. The learning algorithm is analyzed with samples drawn from unbounded sampling processes. The purpose of this paper is to present an elaborate concentration estimate for the algorithms by means of a novel stepping stone technique. The learning rates derived from our analysis can be achieved in a more general setting. Our refined analysis will lead to satisfactory learning rates even for non-smooth kernels.     

An exact penalty function algorithm for semi-infinite programmes

An algorithm for semi-inifinite programming using sequential quadratic programming techniques together with anL exact penalty function is presented, and global convergence is shown. An important feature of the convergence proof is that it does not require an implicit function theorem to be applicable to the semi-infinite constraints; a much weaker assumption concerning the finiteness of the number of global maximizers of each semi-infinite constraint is sufficient. In contrast to proofs based on an implicit function theorem, this result is also valid for a large class ofC ¹ problems.