Augmented Lagrangian Objective Penalty Function

Augmented Lagrangian function is one of the most important tools used in solving some constrained optimization problems. In this article, we study an augmented Lagrangian objective penalty function and a modified augmented Lagrangian objective penalty function for inequality constrained optimization problems. First, we prove the dual properties of the augmented Lagrangian objective penalty function, which are at least as good as the traditional Lagrangian function's. Under some conditions, the saddle point of the augmented Lagrangian objective penalty function satisfies the first-order Karush-Kuhn-Tucker condition. This is especially so when the Karush-Kuhn-Tucker condition holds for convex programming of its saddle point existence. Second, we prove the dual properties of the modified augmented Lagrangian objective penalty function. For a global optimal solution, when the exactness of the modified augmented Lagrangian objective penalty function holds, its saddle point exists. The sufficient and necessary stability conditions used to determine whether the modified augmented Lagrangian objective penalty function is exact for a global solution is proved. Based on the modified augmented Lagrangian objective penalty function, an algorithm is developed to find a global solution to an inequality constrained optimization problem, and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the modified augmented Lagrangian objective penalty function is proved for a local solution. An algorithm is presented in finding a local solution, with its convergence proved under some conditions.     

Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs

In this paper, an approximate augmented Lagrangian function for nonlinear semidefinite programs is introduced. Some basic properties of the approximate augmented Lagrange function such as monotonicity and convexity are discussed. Necessary and sufficient conditions for approximate strong duality results are derived. Conditions for an approximate exact penalty representation in the framework of augmented Lagrangian are given. Under certain conditions, it is shown that any limit point of a sequence of stationary points of approximate augmented Lagrangian problems is a KKT point of the original semidefinite program and that a sequence of optimal solutions to augmented Lagrangian problems converges to a solution of the original semidefinite program.     

Existence of augmented Lagrange multipliers for cone constrained optimization problems

In this paper, by using an augmented Lagrangian approach, we obtain several sufficient conditions for the existence of augmented Lagrange multipliers of a cone constrained optimization problem in Banach spaces, where the corresponding augmenting function is assumed to have a valley at zero. Furthermore, we deal with the relationship of saddle points, augmented Lagrange multipliers, and zero duality gap property between the cone constrained optimization problem and its augmented Lagrangian dual problem.     

Using a factored dual in augmented Lagrangian methods for semidefinite programming

In the context of augmented Lagrangian approaches for solving semidefinite programming problems, we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. Hints on how to deal with the resulting unconstrained maximization of the augmented Lagrangian are given. We further use the approximate maximum of the augmented Lagrangian with the aim of improving the convergence rate of alternating direction augmented Lagrangian frameworks. Numerical results are reported, showing the benefits of the approach.     

从常步长梯度方法的视角看不可微凸优化增广Lagrange方法的收敛性

增广Lagrange方法是求解非线性规划的一种有效方法.从一新的角度证明不等式约束非线性非光滑凸优化问题的增广Lagrange方法的收敛性.用常步长梯度法的收敛性定理证明基于增广Lagrange函数的对偶问题的常步长梯度方法的收敛性,由此得到增广Lagrange方法乘子迭代的全局收敛性.     

A new augmented immersed finite element method without using SVD interpolations

Augmented immersed interface methods have been developed recently for interface problems and problems on irregular domains including CFD applications with free boundaries and moving interfaces. In an augmented method, one or several augmented variables are introduced along the interface or boundary so that one can get efficient discretizations. The augmented variables should be chosen such that the interface or boundary conditions are satisfied. The key to the success of the augmented methods often relies on the interpolation scheme to couple the augmented variables with the governing differential equations through the interface or boundary conditions. This has been done using a least squares interpolation (under-determined) for which the singular value decomposition (SVD) is used to solve for the interpolation coefficients. In this paper, based on properties of the finite element method, a new augmented immersed finite element method (IFEM) that does not need the interpolations is proposed for elliptic interface problems that have a piecewise constant coefficient. Thus the new augmented method is more efficient and simple than the old one that uses interpolations. The method then is extended to Poisson equations on irregular domains with a Dirichlet boundary condition. Numerical experiments with arbitrary interfaces/irregular domains and large jump ratios are provided to demonstrate the accuracy and the efficiency of the new augmented methods. Numerical results also show that the number of GMRES iterations is independent of the mesh size and nearly independent of the jump in the coefficient.     

Some Results about Duality and Exact Penalization

In this paper, we introduce the concept of the valley at 0 augmenting function and apply it to construct a class of valley at 0 augmented Lagrangian functions. We establish the existence of a path of optimal solutions generated by valley at 0 augmented Lagrangian problems and its convergence toward the optimal set of the original problem and obtain the zero duality gap property between the primal problem and the valley at 0 augmented Lagrangian dual problem. Moreover, we establish the exact penalization representation results in the framework of valley at 0 augmented Lagrangian.     

Existence of Augmented Lagrange Multipliers for Semi-infinite Programming Problems

Using an augmented Lagrangian approach, we study the existence of augmented Lagrange multipliers of a semi-infinite programming problem and discuss their characterizations in terms of saddle points. In the case of a sharp Lagrangian, we obtain a first-order necessary condition for the existence of an augmented Lagrange multiplier for the semi-infinite programming problem and some first-order sufficient conditions by assuming inf-compactness of the data functions and the extended Mangasarian–Fromovitz constraint qualification. Using a valley at 0 augmenting function and assuming suitable second-order sufficient conditions, we obtain the existence of an augmented Lagrange multiplier for the semi-infinite programming problem.     

Duality in nonlinear programs using augmented Lagrangian functions

A generally nonconvex optimization problem with equality constraints is studied. The problem is introduced as an “inf sup” of a generalized augmented Lagrangian function. A dual problem is defined as the “sup inf” of the same generalized augmented Lagrangian. Sufficient conditions are derived for constructing the augmented Lagrangian function such that the extremal values of the primal and dual problems are equal. Characterization of a class of augmented Lagrangian functions which satisfy the sufficient conditions for strong duality is presented. Finally, some examples of functions and primal-dual problems in the above-mentioned class are presented.     

On augmented Lagrangians for Optimization Problems with a Single Constraint

We examine augmented Lagrangians for optimization problems with a single (either inequality or equality) constraint. We establish some links between augmented Lagrangians and Lagrange-type functions and propose a new kind of Lagrange-type functions for a problem with a single inequality constraint. Finally, we discuss a supergradient algorithm for calculating optimal values of dual problems corresponding to some class of augmented Lagrangians.     

An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions

In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the subproblem is solved by Barzilai–Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time.     

Convergence of an augmented Lagrange algorithm for nonlinear optimizations with second-order cone constraints

An augmented Lagrange algorithm for nonlinear optimizations with second-order cone constraints is proposed based on a Löwner operator associated with a potential function for the optimization problems with inequality constraints. The favorable properties of both the Löwner operator and the corresponding augmented Lagrangian are discussed. And under some mild assumptions, the rate of convergence of the augmented Lagrange algorithm is studied in detail.     

A modified SSOR iterative method for augmented systems

Golub, Wu and Yuan [G.H. Golub, X. Wu, J.Y. Yuan, SOR-like methods for augmented systems, BIT 41 (2001) 71–85] have presented the SOR-like algorithm to solve augmented systems. In this paper, we present the modified symmetric successive overrelaxation (MSSOR) method for solving augmented systems, which is based on Darvishi and Hessari’s work above. We derive its convergence under suitable restrictions on the iteration parameter, determine its optimal iteration parameter and the corresponding optimal convergence factor under certain conditions. Finally, we apply the MSSOR method to solve augmented systems.     

An Exact Augmented Lagrangian Function for Nonlinear Programming with Two-Sided Constraints

This paper is aimed toward the definition of a new exact augmented Lagrangian function for two-sided inequality constrained problems. The distinguishing feature of this augmented Lagrangian function is that it employs only one multiplier for each two-sided constraint. We prove that stationary points, local minimizers and global minimizers of the exact augmented Lagrangian function correspond exactly to KKT pairs, local solutions and global solutions of the constrained problem.     

An augmented penalty function method with penalty parameter updates for nonconvex optimization

Given an augmented Lagrangian scheme for a general optimization problem, we use an epsilon subgradient step for improving the dual function. This can be seen as an update for an augmented penalty method, which is more stable because it does not force the penalty parameter to tend to infinity. We establish for this update primal-dual convergence for our augmented penalty method. As illustration, we apply our method to the test-bed kissing number problem.     

带有不等式约束的非线性规划问题的一个精确增广Lagrange函数

对求解带有不等式约束的非线性非凸规划问题的一个精确增广Lagrange函数进行了研究．在适当的假设下,给出了原约束问题的局部极小点与增广Lagrange函数,在原问题变量空间上的无约束局部极小点之间的对应关系．进一步地,在对全局解的一定假设下,还提供了原约束问题的全局最优解与增广Lagrange函数,在原问题变量空间的一个紧子集上的全局最优解之间的一些对应关系．因此,从理论上讲,采用该文给出的增广Lagrange函数作为辅助函数的乘子法,可以求得不等式约束非线性规划问题的最优解和对应的Lagrange乘子．     

成交量信息有助于预测中国股票市场的波动吗?

就成交量信息是否有助于预测股票市场的波动率这一问题,目前学术界有两种截然相反的观点存在。本文以中国股票市场代表性指数的代表性波动周期为例,对上述问题进行了实证研究。通过采用较以往研究更为严谨和稳健的样本外滚动时间窗预测法和高级预测能力检验法(Superiorpredictive ability,SPA),本文得到的分析结论包括:(1)成交量信息对中国股票市场的波动过程有显著影响;(2)将成交量纳入GARCH族模型会导致条件方差方程中的波动持续性出现明显下降;(3)引入成交量作为附加解释变量的GARCH族模型并未表现出比一般GARCH族模型更优的波动率预测能力。最后对实证结果给出了理论解释。     

A nonlinear augmented Lagrangian for constrained minimax problems

A novel smooth nonlinear augmented Lagrangian for solving minimax problems with inequality constraints, is proposed in this paper, which has the positive properties that the classical Lagrangian and the penalty function fail to possess. The corresponding algorithm mainly consists of minimizing the nonlinear augmented Lagrangian function and updating the Lagrange multipliers and controlling parameter. It is demonstrated that the algorithm converges Q-superlinearly when the controlling parameter is less than a threshold under the mild conditions. Furthermore, the condition number of the Hessian of the nonlinear augmented Lagrangian function is studied, which is very important for the efficiency of the algorithm. The theoretical results are validated further by the preliminary numerical experiments for several testing problems reported at last, which show that the nonlinear augmented Lagrangian is promising.     

k-均值问题的差分隐私算法综述

$k$-均值问题是机器学习和组合优化领域十分重要的问题。它是经典的NP-难问题, 被广泛的应用于数据挖掘、企业生产决策、图像处理、生物医疗科技等领域。随着时代的发展, 人们越来越注重于个人的隐私保护:在决策通常由人工智能算法做出的情况下, 如何保证尽可能多地从数据中挖掘更多信息,同时不泄露个人隐私。近十年来不断有专家学者研究探索带隐私保护的$k$-均值问题, 得到了许多具有理论指导意义和实际应用价值的结果, 本文主要介绍关于$k$-均值问题的差分隐私算法供读者参考。     

非凸半定规划的增广Lagrangian的微分的计算

迄今为止，还未见出版过有关求解非凸半定规划的算法，但在最近，Chen，et.al(2000)和Sun＆Sun(1999)关于非凸半定规划(SDP)的增广Lagrangian的研究是非常有用的，在本文中，我们证明非凸半定规划的增广Lagrangian是可微的，并且给出它的可微表达式．