A Unified Approach to the Global Exactness of Penalty and Augmented Lagrangian Functions I: Parametric Exactness

In this two-part study, we develop a unified approach to the analysis of the global exactness of various penalty and augmented Lagrangian functions for constrained optimization problems in finite-dimensional spaces. This approach allows one to verify in a simple and straightforward manner whether a given penalty/augmented Lagrangian function is exact, i.e., whether the problem of unconstrained minimization of this function is equivalent (in some sense) to the original constrained problem, provided the penalty parameter is sufficiently large. Our approach is based on the so-called localization principle that reduces the study of global exactness to a local analysis of a chosen merit function near globally optimal solutions. In turn, such local analysis can be performed with the use of optimality conditions and constraint qualifications. In the first paper, we introduce the concept of global parametric exactness and derive the localization principle in the parametric form. With the use of this version of the localization principle, we recover existing simple, necessary, and sufficient conditions for the global exactness of linear penalty functions and for the existence of augmented Lagrange multipliers of Rockafellar–Wets’ augmented Lagrangian. We also present completely new necessary and sufficient conditions for the global exactness of general nonlinear penalty functions and for the global exactness of a continuously differentiable penalty function for nonlinear second-order cone programming problems. We briefly discuss how one can construct a continuously differentiable exact penalty function for nonlinear semidefinite programming problems as well.     

Convergence and Error Bound for Perturbation of Linear Programs

In various penalty/smoothing approaches to solving a linear program, one regularizes the problem by adding to the linear cost function a separable nonlinear function multiplied by a small positive parameter. Popular choices of this nonlinear function include the quadratic function, the logarithm function, and the x ln(x)-entropy function. Furthermore, the solutions generated by such approaches may satisfy the linear constraints only inexactly and thus are optimal solutions of the regularized problem with a perturbed right-hand side. We give a general condition for such an optimal solution to converge to an optimal solution of the original problem as the perturbation parameter tends to zero. In the case where the nonlinear function is strictly convex, we further derive a local (error) bound on the distance from such an optimal solution to the limiting optimal solution of the original problem, expressed in terms of the perturbation parameter.     

An Approximation Scheme for Uncertain Minimax Optimal Control Problems

In this work, we address an uncertain minimax optimal control problem with linear dynamics where the objective functional is the expected value of the supremum of the running cost over a time interval. By taking an independently drawn random sample, the expected value function is approximated by the corresponding sample average function. We study the epi-convergence of the approximated objective functionals as well as the convergence of their global minimizers. Then we define an Euler discretization in time of the sample average problem and prove that the value of the discrete time problem converges to the value of the sample average approximation. In addition, we show that there exists a sequence of discrete problems such that the accumulation points of their minimizers are optimal solutions of the original problem. Finally, we propose a convergent descent method to solve the discrete time problem, and show some preliminary numerical results for two simple examples.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

Uniform blow-up rates and asymptotic estimates of solutions for diffusion systems with weighted localized sources

This paper investigates the global existence of the nonnegative solution and the finite time blow-up of solutions of nonlinear parabolic equation with a more complicated source term, which is a product of localized source, local source, and weight function; we also study the blow-up rate of solution to this problem.     

组稀疏优化问题精确连续Capped-L_(1)松弛北大核心CSCD

本文主要研究损失函数为凸函数且带有约束的组稀疏正则回归问题及组稀疏正则项的精确连续Capped-L_(1)松弛问题.首先对组Capped-L_(1)松弛问题定义了三类稳定点:D(irectional)-稳定点、C(ritical)-稳定点、L(ifted)-稳定点,然后刻画了这三类稳定点之间的关系.进一步,给出了组Capped-L_(1)松弛问题和原始组稀疏正则问题的最优性条件,并从全局解和局部解角度讨论了松弛问题和原问题解的等价关系.     

A parametric successive underestimation method for convex multiplicative programming problems

This paper addresses itself to the algorithm for minimizing the product of two nonnegative convex functions over a convex set. It is shown that the global minimum of this nonconvex problem can be obtained by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in a higher dimensional space and to apply a branch-and-bound algorithm using an underestimating function. Computational results indicate that our algorithm is efficient when the objective function is the product of a linear and a quadratic functions and the constraints are linear. An extension of our algorithm for minimizing the sum of a convex function and a product of two convex functions is also discussed.     

Asymmetric variational inequality problems over product sets: Applications and iterative methods

In this paper, we (i) describe how several equilibrium problems can be uniformly modelled by a finite-dimensional asymmetric variational inequality defined over a Cartesian product of sets, and (ii) investigate the local and global convergence of various iterative methods for solving such a variational inequality problem. Because of the special Cartesian product structure, these iterative methods decompose the original variational inequality problem into a sequence of simpler variational inequality subproblems in lower dimensions. The resulting decomposition schemes often have a natural interpretation as some adjustment processes. This research was based on work supported by the National Science Foundation under grant ECS 811–4571.     

Nonlinear Transmission Problem for Wave Equation with?Boundary Condition of Memory Type

In this paper we consider a transmission problem with a boundary damping condition of memory type, that is, the wave propagation over bodies consisting of two physically different types of materials. One component is clamped, while the other is in a viscoelastic fluid producing a dissipative mechanism on the boundary. We will study the global existence of solutions for the transmission problem, and moreover we show that if the relaxation function decays exponentially or polynomially, then the solutions for the problem have the same decay rates.     

Convergence of local variational spline interpolation

In this paper we first revisit a classical problem of computing variational splines. We propose to compute local variational splines in the sense that they are interpolatory splines which minimize the energy norm over a subinterval. We shall show that the error between local and global variational spline interpolants decays exponentially over a fixed subinterval as the support of the local variational spline increases. By piecing together these locally defined splines, one can obtain a very good C⁰ approximation of the global variational spline. Finally we generalize this idea to approximate global tensor product B-spline interpolatory surfaces.     

Bicyclic algebras of prime exponent over function fields

We examine some properties of bicyclic algebras, i.e. the tensor product of two cyclic algebras, defined over a purely transcendental function field in one variable. We focus on the following problem: When does the set of local invariants of such an algebra coincide with the set of local invariants of some cyclic algebra? Although we show this is not always the case, we determine when it happens for the case where all degeneration points are defined over the ground field. Our main tool is Faddeev's theory. We also study a geometric counterpart of this problem (pencils of Severi-Brauer varieties with prescribed degeneration data).

     

A local superconvergence analysis of the finite element method for the Stokes equations by local projections

In this paper, we focus on a local superconvergence analysis of the finite element method for the Stokes equations by local projections. The local and global superconvergence results of finite element solutions are provided for the Stokes problem under some corresponding regularity assumptions. Conclusion can be drawn that the local superconvergence has advantages over the global superconvergence in two important aspects. On the one hand, it offsets theoretical limitation in practical applications. On the other hand, interior estimates are derived on the base of local properties of the domain without global smoothness for the exact solution and prior regularity of the problem globally over the whole domain.     

A method for approximating pairwise comparison matrices by consistent matrices

In several methods of multiattribute decision making, pairwise comparison matrices are applied to derive implicit weights for a given set of decision alternatives. A class of the approaches is based on the approximation of the pairwise comparison matrix by a consistent matrix. In the paper this approximation problem is considered in the least-squares sense. In general, the problem is nonconvex and difficult to solve, since it may have several local optima. In the paper the classic logarithmic transformation is applied and the problem is transcribed into the form of a separable programming problem based on a univariate function with special properties. We give sufficient conditions of the convexity of the objective function over the feasible set. If such a sufficient condition holds, the global optimum of the original problem can be obtained by local search, as well. For the general case, we propose a branch-and-bound method. Computational experiments are also presented.     

Global convergence of modified multiplicative updates for nonnegative matrix factorization

Nonnegative matrix factorization (NMF) is the problem of approximating a given nonnegative matrix by the product of two nonnegative matrices. The multiplicative updates proposed by Lee and Seung are widely used as efficient computational methods for NMF. However, the global convergence of these updates is not formally guaranteed because they are not defined for all pairs of nonnegative matrices. In this paper, we consider slightly modified versions of the original multiplicative updates and study their global convergence properties. The only difference between the modified updates and the original ones is that the former do not allow variables to take values less than a user-specified positive constant. Using Zangwill’s global convergence theorem, we prove that any sequence of solutions generated by either of those modified updates has at least one convergent subsequence and the limit of any convergent subsequence is a stationary point of the corresponding optimization problem. Furthermore, we propose algorithms based on the modified updates that always stop within a finite number of iterations.     

Proximal Point Methods for Lipschitz Functions on Hadamard Manifolds: Scalar and Vectorial Cases

In the second part of our study, we introduce the concept of global extended exactness of penalty and augmented Lagrangian functions, and derive the localization principle in the extended form. The main idea behind the extended exactness consists in an extension of the original constrained optimization problem by adding some extra variables, and then construction of a penalty/augmented Lagrangian function for the extended problem. This approach allows one to design extended penalty/augmented Lagrangian functions having some useful properties (such as smoothness), which their counterparts for the original problem might not possess. In turn, the global exactness of such extended merit functions can be easily proved with the use of the localization principle presented in this paper, which reduces the study of global exactness to a local analysis of a merit function based on sufficient optimality conditions and constraint qualifications. We utilize the localization principle in order to obtain simple necessary and sufficient conditions for the global exactness of the extended penalty function introduced by Huyer and Neumaier, and in order to construct a globally exact continuously differentiable augmented Lagrangian function for nonlinear semidefinite programming problems.     

一个修正的罚函数方法

本文通过给出的一个修正的罚函数,把约束非线性规划问题转化为无约束非线性规划问题.我们讨论了原问题与相应的罚问题局部最优解和全局最优解之间的关系,并给出了乘子参数和罚参数与迭代点之间的关系,最后给出了一个简单算法,数值试验表明算法是有效的.     

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.     

Expected Value and Sample Average Approximation Method for Solving Stochastic Second-Order Cone Complementarity Problems

In this paper, we consider the stochastic second-order cone complementarity problems (SSOCCP). We first formulate the SSOCCP contained expectation as an optimization problem using the so-called second-order cone complementarity function. We then use sample average approximation method and smoothing technique to obtain the approximation problems for solving this reformulation. In theory, we show that any accumulation point of the global optimal solutions or stationary points of the approximation problems are global optimal solution or stationary point of the original problem under suitable conditions. Finally, some numerical examples are given to explain that the proposed methods are feasible.     

Lower-Order Penalization Approach to Nonlinear Semidefinite Programming

In this paper, we reformulate a nonlinear semidefinite programming problem into an optimization problem with a matrix equality constraint. We apply a lower-order penalization approach to the reformulated problem. Necessary and sufficient conditions that guarantee the global (local) exactness of the lower-order penalty functions are derived. Convergence results of the optimal values and optimal solutions of the penalty problems to those of the original semidefinite program are established. Since the penalty functions may not be smooth or even locally Lipschitz, we invoke the Ekeland variational principle to derive necessary optimality conditions for the penalty problems. Under certain conditions, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original semidefinite program. Communicated by Y. Zhang This work was supported by a Postdoctoral Fellowship of Hong Kong Polytechnic University and by the Research Grants Council of Hong Kong.     

A Perturbation approach for an inverse quadratic programming problem

We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC¹) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC¹ function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.