Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities

The alternating direction method is one of the attractive approaches for solving linearly constrained separate monotone variational inequalities. Experience on applications has shown that the number of iterations depends significantly on the penalty parameter for the system of linear constraint equations. While the penalty parameter is a constant in the original method, in this paper we present a modified alternating direction method that adjusts the penalty parameter per iteration based on the iterate message. Preliminary numerical tests show that the self-adaptive adjustment technique is effective in practice.     

Theoretical and Practical Convergence of a Self-Adaptive Penalty Algorithm for Constrained Global Optimization

This paper proposes a self-adaptive penalty function and presents a penalty-based algorithm for solving nonsmooth and nonconvex constrained optimization problems. We prove that the general constrained optimization problem is equivalent to a bound constrained problem in the sense that they have the same global solutions. The global minimizer of the penalty function subject to a set of bound constraints may be obtained by a population-based meta-heuristic. Further, a hybrid self-adaptive penalty firefly algorithm, with a local intensification search, is designed, and its convergence analysis is established. The numerical experiments and a comparison with other penalty-based approaches show the effectiveness of the new self-adaptive penalty algorithm in solving constrained global optimization problems.     

Path-following barrier and penalty methods for linearly constrained problems

In the present paper some barrier and penalty methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a continuously differentiable primal and dual path, applied to linearly constrained convex problems are studied, in particular, the radius of convergence of Newton’s method depending on the barrier and penalty para-meter is estimated, Unlike using self-concordance properties the convergence bounds are derived by direct estimations of the solutions of the Newton equations. The obtained results establish parameter selection rules which guarantee the overall convergence of the considered barrier and penalty techniques with only a finite number of Newton steps at each parameter level. Moreover, the obtained estimates support scaling method which uses approximate dual multipliers as available in barrier and penalty methods     

曲率障碍下四阶变分不等式的交替方向乘子法北大核心CSCD

对于重调和算子和曲率障碍表示的变分不等式,提出了自适应交替方向乘子数值解法(SADMM).对问题引入一个辅助变量表示曲率函数的增广Lagrange函数,导出一个约束极小值问题,并且该问题等价于一个鞍点问题.然后采用交替方向乘子法(ADMM)求解这个鞍点问题.通过采用平衡原理和迭代函数,得到了自动调整罚参数的自适应法则,从而提高了计算效率.证明了该方法的收敛性,并给出了利用迭代函数近似罚参数的具体方法.最后,用数值计算结果验证了该方法的有效性.     

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.     

Inexact Implicit Method with Variable Parameter for Mixed Monotone Variational Inequalities

In this paper, we focus on a useful modification of the implicit method by Noor (Ref. 1) for mixed variational inequalities. Experience on applications has shown that the number of iterations of the original method depends significantly on the penalty parameter. One of the contributions of the proposed method is that we allow the penalty parameter to be variable. By introducing a self-adaptive rule, we find that our method is more flexible and efficient than the original one. Another contribution is that we require only an inexact solution of the nonlinear equations at each iteration. A detailed convergence analysis of our method is also included.     

Decomposition Method with a Variable Parameter for a Class of Monotone Variational Inequality Problems

In this paper, we focus on a useful modification of the decomposition method by He et al. (Ref. 1). Experience on applications has shown that the number of iterations of the original method depends significantly on the penalty parameter. The main contribution of our method is that we allow the penalty parameter to vary automatically according to some self-adaptive rules. As our numerical simulations indicate, the modified method is more flexible and efficient in practice. A detailed convergence analysis of our method is also included.     

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.     

A Globally Convergent Method of Constrained Minimization by Solving Subproblems of the Conic Model

A new method for nonlinearly constrained optimization problems is proposed. The method consists of two steps. In the first step, we get a search direction by the linearly constrained subproblems based on conic functions. In the second step, we use a differentiable penalty function, and regard it as the metric function of the problem. From this, a new approximate solution is obtained. The global convergence of the given method is also proved.     

一种新的求解带约束的有限极大极小问题的精确罚函数

提出了一种新的精确光滑罚函数求解带约束的极大极小问题．仅仅添加一个额外的变量,利用这个精确光滑罚函数,将带约束的极大极小问题转化为无约束优化问题． 证明了在合理的假设条件下,当罚参数充分大,罚问题的极小值点就是原问题的极小值点．进一步,研究了局部精确性质．数值结果表明这种罚函数算法是求解带约束有限极大极小问题的一种有效算法．     

Firefly penalty-based algorithm for bound constrained mixed-integer nonlinear programming

In this article, we aim to extend the firefly algorithm (FA) to solve bound constrained mixed-integer nonlinear programming (MINLP) problems. An exact penalty continuous formulation of the MINLP problem is used. The continuous penalty problem comes out by relaxing the integrality constraints and by adding a penalty term to the objective function that aims to penalize integrality constraint violation. Two penalty terms are proposed, one is based on the hyperbolic tangent function and the other on the inverse hyperbolic sine function. We prove that both penalties can be used to define the continuous penalty problem, in the sense that it is equivalent to the MINLP problem. The solutions of the penalty problem are obtained using a variant of the metaheuristic FA for global optimization. Numerical experiments are given on a set of benchmark problems aiming to analyze the quality of the obtained solutions and the convergence speed. We show that the firefly penalty-based algorithm compares favourably with the penalty algorithm when the deterministic DIRECT or the simulated annealing solvers are invoked, in terms of convergence speed.     

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

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

An Exact Penalty Method for Free Terminal Time Optimal Control Problem with Continuous Inequality Constraints

In this paper, we consider a class of optimal control problems with free terminal time and continuous inequality constraints. First, the problem is approximated by representing the control function as a piecewise-constant function. Then the continuous inequality constraints are transformed into terminal equality constraints for an auxiliary differential system. After these two steps, we transform the constrained optimization problem into a penalized problem with only box constraints on the decision variables using a novel exact penalty function. This penalized problem is then solved by a gradient-based optimization technique. Theoretical analysis proves that this penalty function has continuous derivatives, and for a sufficiently large and finite penalty parameter, its local minimizer is feasible in the sense that the continuous inequality constraints are satisfied. Furthermore, this local minimizer is also the local minimizer of the constrained problem. Numerical simulations on the range maximization for a hypersonic vehicle reentering the atmosphere subject to a heating constraint demonstrate the effectiveness of our method.     

用L_1-罚函数作线性搜索函数的一种修正约束变尺度算法

本文对用Ｌ１－罚函数作线性搜索的约束变尺度算法，提出了一种新的修正方法，该方法的计算量小，可行性较好，并且仍能保持原有算法的收敛性．     

广义乘子交替方向法求解线性约束不可分非凸优化问题的收敛性

In this paper, we consider the convergence of the generalized alternating direction method of multipliers(GADMM) for solving linearly constrained nonconvex minimization model whose objective contains coupled functions. Under the assumption that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz inequality, we prove that the sequence generated by the GADMM converges to a critical point of the augmented Lagrangian function when the penalty parameter in the augmented Lagrangian function is sufficiently large. Moreover, we also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.     

Perturbation Lemma for the Newton Method with Application to the SQP Newton Method

We study the convergence of a general perturbation of the Newton method for solving a nonlinear system of equations. As an application, we show that the augmented Lagrangian successive quadratic programming is locally and q-quadratically convergent in the variable x to the solution of an equality constrained optimization problem, under a mild condition on the penalty parameter and the choice of the Lagrange multipliers.     

A new penalty parameter for linearly constrained 0–1 quadratic programming problems

The equivalence between the linearly constrained 0–1 quadratic programming problem and the continuous quadratic programming problem is studied in this note. Specifically, we show that the existing penalty parameter from the literature can be further improved.     

New inexact implicit method for general mixed quasi variational inequalities

In this paper, we suggest and analyze a new self-adaptive inexact implicit method with a variable parameter for general mixed quasi variational inequalities, where the skew-symmetry of the nonlinear bifunction plays a crucial part in the convergence analysis of this method. We use a self-adaptive technique to adjust parameter ρ at each iteration. The global convergence of the proposed method is proved under some mild conditions. Preliminary numerical results indicate that the self-adaptive adjustment rule is necessary in practice. Muhammad Aslam Noor is supported by the Higher Education Commission, Pakistan, through research grant No: 1-28/HEC/HRD/2005/90.     

The penalty method for grid matching in mixed finite element methods

In this paper we prove the possibility of the use of the penalty method for grid matching in mixed finite element methods. We consider the Hermann-Johnson scheme for biharmonic equation. The main idea is to construct a perturbed problem with two parameters which play roles of penalties. The perturbed problem is built by the replacement of essential conditions on the interface in the mixed variational statement with natural conditions that contain parameters. The perturbed problem is discretized by the finite element method. We estimate the norm of the difference between a solution of the discrete perturbed problem and a solution of the initial problem; the obtained estimates depend on the step and the penalties. We give recommendations for the choice of penalties depending on the step.     

Improved penalty calculations for a mixed integer branch-and-bound algorithm

This paper presents an extension of Tomlin's penalties for the branch-and-bound linear mixed integer programming algorithm of Beale and Small. Penalties which are uniformly stronger are obtained by jointly conditioning on a basic variable and the non-basic variable yielding the Tomlin penalty. It is shown that this penalty can be computed with a little additional arithmetic and some extra bookkeeping. The improvement is easy to incorporate for the normal case as well as when the variables are grouped into ordered sets with generalized upper bounds. Computational experience bears out the usefulness of the extra effort for predominantly integer problems.