A sequential quadratic penalty method for nonlinear semidefinite programming

In this article, a nonlinear semidefinite program is reformulated into a mathematical program with a matrix equality constraint and a sequential quadratic penalty method is proposed to solve the latter problem. We discuss the differentiability and convexity of the penalty function. Necessary and sufficient conditions for the convergence of optimal values of penalty problems to that of the original semidefinite program are obtained. The convergence of optimal solutions of penalty problems to that of the original semidefinite program is also investigated. We show that any limit point of a sequence of stationary points of penalty problems satisfies the KKT optimality condition of the semidefinite program. Smoothed penalty problems that have the same order of smothness as the original semidefinite program are adopted. Corresponding results such as the convexity of the smoothed penalty function, the convergence of optimal values, optimal solutions and the stationary points of the smoothed penalty problems are obtained.     

A Path Algorithm for Constrained Estimation

Many least-square problems involve affine equality and inequality constraints. Although there are a variety of methods for solving such problems, most statisticians find constrained estimation challenging. The current article proposes a new path-following algorithm for quadratic programming that replaces hard constraints by what are called exact penalties. Similar penalties arise in l ₁ regularization in model selection. In the regularization setting, penalties encapsulate prior knowledge, and penalized parameter estimates represent a trade-off between the observed data and the prior knowledge. Classical penalty methods of optimization, such as the quadratic penalty method, solve a sequence of unconstrained problems that put greater and greater stress on meeting the constraints. In the limit as the penalty constant tends to ∞, one recovers the constrained solution. In the exact penalty method, squared penalties are replaced by absolute value penalties, and the solution is recovered for a finite value of the penalty constant. The exact path-following method starts at the unconstrained solution and follows the solution path as the penalty constant increases. In the process, the solution path hits, slides along, and exits from the various constraints. Path following in Lasso penalized regression, in contrast, starts with a large value of the penalty constant and works its way downward. In both settings, inspection of the entire solution path is revealing. Just as with the Lasso and generalized Lasso, it is possible to plot the effective degrees of freedom along the solution path. For a strictly convex quadratic program, the exact penalty algorithm can be framed entirely in terms of the sweep operator of regression analysis. A few well-chosen examples illustrate the mechanics and potential of path following. This article has supplementary materials available online.     

Superconvergence and stability for boundary penalty techniques of finite difference methods

The finite difference method (FDM) is used for Dirichlet problems of Poisson's equation, and the Dirichlet boundary condition is dealt with by boundary penalty techniques. Two penalty techniques, penalty‐integrals and penalty‐collocations (i.e., fixing), are proposed in this paper. The error bounds in the discrete H¹ norm and the infinite norms are derived. The stability analysis is based on the new effective condition number (Cond_eff) but not on the traditional condition number (Cond). The bounds of Cond_eff are explored to display that both the penalty‐integral and the penalty‐collocation techniques have good stability; the huge Cond is misleading. Since the penalty‐collocation technique (i.e., the fixing technique) is simpler, it has been applied in engineering problem for a long time. It is worthy to point out that this paper is the first time to provide a theoretical justification for such a popular penalty‐collocation (fixing) technique. Hence the penalty‐collocation is recommended for dealing with the complicated constraint conditions such as the clamped and the simply support boundary conditions of biharmonic equations. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

On penalty method for equilibrium problems in lexicographic order

In this paper, we consider lexicographic vector equilibrium problems. We propose a penalty function method for solving such problems. We show that every penalty trajectory of the penalized lexicographic equilibrium problem tends to the solution of the original problem. Using the regularized gap function to obtain an error bound result for such penalized problems is given.     

A class of generalized variable penalty methods for nonlinear programming

A class of generalized variable penalty formulations for solving nonlinear programming problems is presented. The method poses a sequence of unconstrained optimization problems with mechanisms to control the quality of the approximation for the Hessian matrix, which is expressed in terms of the constraint functions and their first derivatives. The unconstrained problems are solved using a modified Newton's algorithm. The method is particularly applicable to solution techniques where an approximate analysis step has to be used (e.g., constraint approximations, etc.), which often results in the violation of the constraints. The generalized penalty formulation contains two floating parameters, which are used to meet the penalty requirements and to control the errors in the approximation of the Hessian matrix. A third parameter is used to vary the class of standard barrier or quasibarrier functions, forming a branch of the variable penalty formulation. Several possibilities for choosing such floating parameters are discussed. The numerical effectiveness of this algorithm is demonstrated on a relatively large set of test examples.The author is thankful for the constructive suggestions of the referees.     

The island confinement method for reducing search space in local search methods

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a “better” neighbour valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as “hard” constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neighbours in each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is “connected” in order to guarantee that a solution can be found from any starting position within the region; thus the concept of islands and the name “island confinement method” arises. Treating some constraints as hard provides new difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. To demonstrate the feasibility and generality of our approach, we show how the island confinement method can be incorporated in, and significantly improve, the search performance of two successful local search procedures, DLM and ESG, on SAT problems arising from binary CSPs. A preliminary version of this paper appeared in AAAI’2002.     

A numerical study of augmented penalty function algorithms for terminally constrained optimal control problems

Three augmented penalty function algorithms are tested and compared with an ordinary penalty function algorithm for two demonstration optimal control problems. Although the augmented penalty function is quite helpful in solving control problems with terminal state constraints, the convergence can be improved significantly by providing systematic increases in the penalty constant.     

A regularized Newton method for solving equilibrium programming problems with an inexactly specified set

Unstable equilibrium problems are examined in which the objective function and the set where the equilibrium point is sought are specified inexactly. A regularized Newton method, combined with penalty functions, is proposed for solving such problems, and its convergence is analyzed. A regularizing operator is constructed.     

Quantile regression with group lasso for classification

Applications of regression models for binary response are very common and models specific to these problems are widely used. Quantile regression for binary response data has recently attracted attention and regularized quantile regression methods have been proposed for high dimensional problems. When the predictors have a natural group structure, such as in the case of categorical predictors converted into dummy variables, then a group lasso penalty is used in regularized methods. In this paper, we present a Bayesian Gibbs sampling procedure to estimate the parameters of a quantile regression model under a group lasso penalty for classification problems with a binary response. Simulated and real data show a good performance of the proposed method in comparison to mean-based approaches and to quantile-based approaches which do not exploit the group structure of the predictors.     

Partially Strictly Monotone and Nonlinear Penalty Functions for Constrained Mathematical Programs

We introduce the concept of partially strictly monotone functions and apply it to construct a class of nonlinear penalty functions for a constrained optimization problem. This class of nonlinear penalty functions includes some (nonlinear) penalty functions currently used in the literature as special cases. Assuming that the perturbation function is lower semi-continuous, we prove that the sequence of optimal values of nonlinear penalty problems converges to that of the original constrained optimization problem. First-order and second-order necessary optimality conditions of nonlinear penalty problems are derived by converting the optimality of penalty problems into that of a smooth constrained vector optimization problem. This approach allows for a concise derivation of optimality conditions of nonlinear penalty problems. Finally, we prove that each limit point of the second-order stationary points of the nonlinear penalty problems is a second-order stationary point of the original constrained optimization problem.     

带等式约束的光滑优化问题的一类新的精确罚函数

罚函数方法是将约束优化问题转化为无约束优化问题的主要方法之一. 不包含目标函数和约束函数梯度信息的罚函数, 称为简单罚函数. 对传统精确罚函数而言, 如果它是简单的就一定是非光滑的; 如果它是光滑的, 就一定不是简单的. 针对等式约束优化问题, 提出一类新的简单罚函数, 该罚函数通过增加一个新的变量来控制罚项. 证明了此罚函数的光滑性和精确性, 并给出了一种解决等式约束优化问题的罚函数算法. 数值结果表明, 该算法对于求解等式约束优化问题是可行的.     

Exact penalty functions in nonlinear programming

In this paper some new theoretic results on piecewise differentiable exact penalty functions are presented. Sufficient conditions are given for the existence of exact penalty functions for inequality constrained problems more general than concave and several classes of such functions are presented.This research was partially supported by a grant from the Office of Naval Research; contract number N00014-67-A-0321-0003 (NR047-095).     

Weak linear bilevel programming problems: existence of solutions via a penalty method

We are concerned with a class of weak linear bilevel programs with nonunique lower level solutions. For such problems, we give via an exact penalty method an existence theorem of solutions. Then, we propose an algorithm.     

Penalty function theory for general convex programming problems

A class of penalty functions for solving convex programming problems with general constraint sets is considered. Convergence theorems for penalty methods are established by utilizing the concept of infimal convergence of a sequence of functions. It is shown that most existing penalty functions are included in our class of penalty functions.     

An Approximate Exact Penalty in Constrained Vector Optimization on Metric Spaces

In this paper, we use the penalty approach in order to study a class of constrained vector minimization problems on complete metric spaces. A penalty function is said to have the generalized exact penalty property iff there is a penalty coefficient for which approximate solutions of the unconstrained penalized problem are close enough to approximate solutions of the corresponding constrained problem. For our class of problems, we establish the generalized exact penalty property and obtain an estimation of the exact penalty.     

An Estimation of Exact Penalty for Infinite-Dimensional Inequality-Constrained Minimization Problems

We use the penalty approach in order to study inequality-constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we consider a large class of inequality-constrained minimization problems for which a constraint is a mapping with values in a normed ordered space. For this class of problems we introduce a new type of penalty functions, establish the exact penalty property and obtain an estimation of the exact penalty. Using this exact penalty property we obtain necessary and sufficient optimality conditions for the constrained minimization problems.     

An exact penalty approach for solving a class of minimization problems with boolean variables

An exact penalty approach for solving minimization problems with a concave objective function, linear constraints and Boolean variables is proposed. The penalty problems have continuous variables. An estimation of the penalty parameter which guarantees the exactness can be calculated on the base of an auxiliary problem. The results are applied to problems with an arbitrary quadratic objective function, linear constraints and Boolean variables. This leads to a modified Lagrangean approach for the latter problems. In the general case, the penalty approach is compared with a direct application of results of global optimization to a modification of the initial problem.     

An exact penalty function approach for nonlinear integer programming problems

Nonlinear integer programming problems with bounded feasible sets are considered. It is shown how the number of constraints in such problems can be reduced with the aid of an exact penalty function approach. This approach can be used to construct an equivalent unconstrained problem, or a problem with a constraint set which makes it easier to solve. The application of this approach to various nonlinear integer programming problems is discussed.     

Solving Fuzzy Variational Inequalities

This paper studies the variational inequality problem over a fuzzy domain and variational inequalities for fuzzy mappings over a fuzzy domain. It is shown that such problems can be reduced to bilevel programming problems. A penalty function algorithm is introduced with a convergence proof. Numerical examples are also included to illustrate the solution procedure.     

Gradient-based Regularization Parameter Selection for Problems With Nonsmooth Penalty Functions

In high-dimensional and/or nonparametric regression problems , regularization (or penalization) is used to control model complexity and induce desired structure. Each penalty has a weight parameter that indicates how strongly the structure corresponding to that penalty should be enforced. Typically, the parameters are chosen to minimize the error on a separate validation set using a simple grid search or a gradient-free optimization method. It is more efficient to tune parameters if the gradient can be determined, but this is often difficult for problems with nonsmooth penalty functions. Here, we show that for many penalized regression problems, the validation loss is actually smooth almost-everywhere with respect to the penalty parameters. We can, therefore, apply a modified gradient descent algorithm to tune parameters. Through simulation studies on example regression problems, we find that increasing the number of penalty parameters and tuning them using our method can decrease the generalization error.