Exact penalty functions method for mathematical programming problems involving invex functions

In this paper, some new results on the exact penalty function method are presented. Simple optimality characterizations are given for the differentiable nonconvex optimization problems with both inequality and equality constraints via exact penalty function method. The equivalence between sets of optimal solutions in the original mathematical programming problem and its associated exact penalized optimization problem is established under suitable invexity assumption. Furthermore, the equivalence between a saddle point in the invex mathematical programming problem and an optimal point in its exact penalized optimization problem is also proved.     

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.     

Optimality criteria and duality in multiple-objective optimization involving generalized invexity

A multiple-objective optimization problem involving generalized invex functions is considered. Kuhn-Tucker type necessary and sufficient conditions are obtained for a feasible point to be an efficient or properly efficient solution. Two dual programs are obtained. The results are given under weaker invexity assumptions.     

ε-optimality criteria for convex programming problems via exact penalty functions

In this paper, we present-optimality criteria for convex programming problems associated with exact penalty functions. Several authors have given various criteria under the assumption that such convex problems and the associated dual problems can be solved. We assume the solvability of neither the convex problem nor the dual problem. To derive our criteria, we estimate the size of the penalty parameter in terms of an-solution for the dual problem.     

Nonlinear Lagrangians for Nonlinear Programming Based on Modified Fischer-Burmeister NCP Functions

This paper proposes nonlinear Lagrangians based on modified Fischer-Burmeister NCP functions for solving nonlinear programming problems with inequality constraints. The convergence theorem shows that the sequence of points generated by this nonlinear Lagrange algorithm is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions, and the error bound of solution, depending on the penalty parameter, is also established. It is shown that the condition number of the nonlinear Lagrangian Hessian at the optimal solution is proportional to the controlling penalty parameter. Moreover, the paper develops the dual algorithm associated with the proposed nonlinear Lagrangians. Numerical results reported suggest that the dual algorithm based on proposed nonlinear Lagrangians is effective for solving some nonlinear optimization problems.     

A Lower Bound for the Penalty Parameter in the Exact Minimax Penalty Function Method for Solving Nondifferentiable Extremum Problems

In the paper, we consider the exact minimax penalty function method used for solving a general nondifferentiable extremum problem with both inequality and equality constraints. We analyze the relationship between an optimal solution in the given constrained extremum problem and a minimizer in its associated penalized optimization problem with the exact minimax penalty function under the assumption of convexity of the functions constituting the considered optimization problem (with the exception of those equality constraint functions for which the associated Lagrange multipliers are negative—these functions should be assumed to be concave). The lower bound of the penalty parameter is given such that, for every value of the penalty parameter above the threshold, the equivalence holds between the set of optimal solutions in the given extremum problem and the set of minimizers in its associated penalized optimization problem with the exact minimax penalty function.     

不等式约束优化问题的低阶精确罚函数的光滑化算法

对不等式约束优化问题提出了一个低阶精确罚函数的光滑化算法. 首先给出了光滑罚问题、非光滑罚问题及原问题的目标函数值之间的误差估计,进而在弱的假
设之下证明了光滑罚问题的全局最优解是原问题的近似全局最优解. 最后给出了一个基于光滑罚函数的求解原问题的算法,证明了算法的收敛性,并给出数值算例说明算法的可行性.     

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.     

Approximation in multiobjective optimization

Some results of approximation type for multiobjective optimization problems with a finite number of objective functions are presented. Namely, for a sequence of multiobjective optimization problems P _n which converges in a suitable sense to a limit problem P, properties of the sequence of approximate Pareto efficient sets of the P _n 's, are studied with respect to the Pareto efficient set of P. The exterior penalty method as well as the variational approximation method appear to be particular cases of this framework.     

A unifying theory of exactness of linear penalty functions II: parametric penalty functions

In this article, we develop a general theory of exact parametric penalty functions for constrained optimization problems. The main advantage of the method of parametric penalty functions is the fact that a parametric penalty function can be both smooth and exact unlike the standard (i.e. non-parametric) exact penalty functions that are always nonsmooth. We obtain several necessary and/or sufficient conditions for the exactness of parametric penalty functions, and for the zero duality gap property to hold true for these functions. We also prove some convergence results for the method of parametric penalty functions, and derive necessary and sufficient conditions for a parametric penalty function to not have any stationary points outside the set of feasible points of the constrained optimization problem under consideration. In the second part of the paper, we apply the general theory of exact parametric penalty functions to a class of parametric penalty functions introduced by Huyer and Neumaier, and to smoothing approximations of nonsmooth exact penalty functions. The general approach adopted in this article allowed us to unify and significantly sharpen many existing results on parametric penalty functions.     

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.     

非线性二层规划问题的全局优化方法

对于下层为线性规划问题的一类非线性二层规划问题,利用线性规划的对偶理论,将其转化为一个单层优化问题,同时取下层问题的对偶间隙作为惩罚项,构造了一个相应的罚问题,然后提出了一个求解该类二层规划问题的全局优化方法。最后,数值结果表明,所提出的方法是可行的。     

On the Smoothing of the Square-Root Exact Penalty Function for Inequality Constrained Optimization

In this paper we propose two methods for smoothing a nonsmooth square-root exact penalty function for inequality constrained optimization. Error estimations are obtained among the optimal objective function values of the smoothed penalty problem, of the nonsmooth penalty problem and of the original optimization problem. We develop an algorithm for solving the optimization problem based on the smoothed penalty function and prove the convergence of the algorithm. The efficiency of the smoothed penalty function is illustrated with some numerical examples, which show that the algorithm seems efficient.     

A geometric framework for nonconvex optimization duality using augmented lagrangian functions

We provide a unifying geometric framework for the analysis of general classes of duality schemes and penalty methods for nonconvex constrained optimization problems. We present a separation result for nonconvex sets via general concave surfaces. We use this separation result to provide necessary and sufficient conditions for establishing strong duality between geometric primal and dual problems. Using the primal function of a constrained optimization problem, we apply our results both in the analysis of duality schemes constructed using augmented Lagrangian functions, and in establishing necessary and sufficient conditions for the convergence of penalty methods.     

Further Study on Augmented Lagrangian Duality Theory

In this paper, we present a necessary and sufficient condition for a zero duality gap between a primal optimization problem and its generalized augmented Lagrangian dual problems. The condition is mainly expressed in the form of the lower semicontinuity of a perturbation function at the origin. For a constrained optimization problem, a general equivalence is established for zero duality gap properties defined by a general nonlinear Lagrangian dual problem and a generalized augmented Lagrangian dual problem, respectively. For a constrained optimization problem with both equality and inequality constraints, we prove that first-order and second-order necessary optimality conditions of the augmented Lagrangian problems with a convex quadratic augmenting function converge to that of the original constrained program. For a mathematical program with only equality constraints, we show that the second-order necessary conditions of general augmented Lagrangian problems with a convex augmenting function converge to that of the original constrained program.This research is supported by the Research Grants Council of Hong Kong (PolyU B-Q359.)     

An entire space polynomial-time algorithm for linear programming

We propose an entire space polynomial-time algorithm for linear programming. First, we give a class of penalty functions on entire space for linear programming by which the dual of a linear program of standard form can be converted into an unconstrained optimization problem. The relevant properties on the unconstrained optimization problem such as the duality, the boundedness of the solution and the path-following lemma, etc, are proved. Second, a self-concordant function on entire space which can be used as penalty for linear programming is constructed. For this specific function, more results are obtained. In particular, we show that, by taking a parameter large enough, the optimal solution for the unconstrained optimization problem is located in the increasing interval of the self-concordant function, which ensures the feasibility of solutions. Then by means of the self-concordant penalty function on entire space, a path-following algorithm on entire space for linear programming is presented. The number of Newton steps of the algorithm is no more than $O(nL\log (nL/ {\varepsilon }))$ , and moreover, in short step, it is no more than $O(\sqrt{n}\log (nL/{\varepsilon }))$ .     

A new exact exponential penalty function method and nonconvex mathematical programming

A new exact penalty function method, called the l₁ exact exponential penalty function method, is introduced. In this approach, the so-called the exponential penalized optimization problem with the l₁ exact exponential penalty function is associated with the original optimization problem with both inequality and equality constraints. The l₁ exact exponential penalty function method is used to solve nonconvex mathematical programming problems with r-invex functions (with respect to the same function η). The equivalence between sets of optimal solutions of the original mathematical programming problem and of its associated exponential penalized optimization problem is established under suitable r-invexity assumption. Also lower bounds on the penalty parameter are given, for which above these values, this result is true.     

A successive quadratic programming method for a class of constrained nonsmooth optimization problems

In this paper we present an algorithm for solving nonlinear programming problems where the objective function contains a possibly nonsmooth convex term. The algorithm successively solves direction finding subproblems which are quadratic programming problems constructed by exploiting the special feature of the objective function. An exact penalty function is used to determine a step-size, once a search direction thus obtained is judged to yield a sufficient reduction in the penalty function value. The penalty parameter is adjusted to a suitable value automatically. Under appropriate assumptions, the algorithm is shown to produce an approximate optimal solution to the problem with any desirable accuracy in a finite number of iterations.     

Second-Order Smoothing Objective Penalty Function for Constrained Optimization Problems

In this article, a novel objective penalty function as well as its second-order smoothing is introduced for constrained optimization problems (COP). It is shown that an optimal solution to the second-order smoothing objective penalty optimization problem is an optimal solution to the original optimization problem under some mild conditions. Based on the second-order smoothing objective penalty function, an algorithm that has better convergence is introduced. Numerical examples illustrate that this algorithm is efficient in solving COP.     

基于二次函数光滑化逼近的修正低阶罚函数

针对不等式约束优化问题, 给出了通过二次函数对低阶精确罚函数进行光滑化逼近的两种函数形式, 得到修正的光滑罚函数. 证明了在一定条件下, 当罚参数充分大, 修正的光滑罚问题的全局最优解是原优化问题的全局最优解. 给出的两个数值例子说明了所提出的光滑化方法的有效性.