Variable Programming: A Generalized Minimax Problem. Part II: Algorithms

In this part of the two-part series of papers, algorithms for solving some variable programming (VP) problems proposed in Part I are investigated. It is demonstrated that the non-differentiability and the discontinuity of the maximum objective function, as well as the summation objective function in the VP problems constitute difficulty in finding their solutions. Based on the principle of statistical mechanics, we derive smooth functions to approximate these non-smooth objective functions with specific activated feasible sets. By transforming the minimax problem and the corresponding variable programming problems into their smooth versions we can solve the resulting problems by some efficient algorithms for smooth functions. Relevant theoretical underpinnings about the smoothing techniques are established. The algorithms, in which the minimization of the smooth functions is carried out by the standard quasi-Newton method with BFGS formula, are tested on some standard minimax and variable programming problems. The numerical results show that the smoothing techniques yield accurate optimal solutions and that the algorithms proposed are feasible and efficient.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

Extremal points and optimal solutions for general capacity problems

This paper studies the infinite dimensional linear programming problems in the integration type. The variable is taken in the space of bounded regular Borel measures on compact Hausdorff spaces. It will find an optimal measure for a constrained optimization problem, namely a capacity problem. Relations between extremal points of the feasible region and optimal solutions of the optimization problem are investigated. The necessary/sufficient conditions for a measure to be optimal are established. The algorithm for optimal solution of the general capacity problem onX = Y = [0, 1] is formulated.     

Second-order variational analysis and characterizations of tilt-stable optimal solutions in infinite-dimensional spaces

The paper is devoted to developing second-order tools of variational analysis and their applications to characterizing tilt-stable local minimizers of constrained optimization problems infinite-dimensional spaces with many results new also in finite-dimensional settings. The importance of tilt stability has been well recognized from both theoretical and numerical aspects of optimization. Based on second-order generalized differentiation, we obtain qualitative and quantitative characterizations of tilt stability in general frameworks of constrained optimization and establish its relationships with strong metric regularity of subgradient mappings and uniform second-order growth. The results obtained are applied to deriving new necessary and sufficient conditions for tilt-stable minimizers in problems of nonlinear programming with twice continuously differentiable data in Hilbert spaces.     

A ROBUST TRUST REGION ALGORITHM FOR SOLVING GENERAL NONLINEAR PROGRAMMING

1. Introductioncrust region methods are iterative. As a strategy of globalization, the trust region approach was introduced into solving unconstrained optimization and proved to be efficient androbust. An excellent survey was given by Mor6(1983). The associated research with trustregion methods for unconstrained optimization can be found in Fletcher(1980), Powell(1975),Sorensen(1981), Shultz, Schnabel and Byrd(1985), Yuan(1985). The solution of the trust region subproblem is still an activ…     

Mesh adaptive direct search algorithms for mixed variable optimization

This paper introduces a new derivative-free class of mesh adaptive direct search (MADS) algorithms for solving constrained mixed variable optimization problems, in which the variables may be continuous or categorical. This new class of algorithms, called mixed variable MADS (MV-MADS), generalizes both mixed variable pattern search (MVPS) algorithms for linearly constrained mixed variable problems and MADS algorithms for general constrained problems with only continuous variables. The convergence analysis, which makes use of the Clarke nonsmooth calculus, similarly generalizes the existing theory for both MVPS and MADS algorithms, and reasonable conditions are established for ensuring convergence of a subsequence of iterates to a suitably defined stationary point in the nonsmooth and mixed variable sense.     

Convex composite multi-objective nonsmooth programming

This paper examines nonsmooth constrained multi-objective optimization problems where the objective function and the constraints are compositions of convex functions, and locally Lipschitz and Gâteaux differentiable functions. Lagrangian necessary conditions, and new sufficient optimality conditions for efficient and properly efficient solutions are presented. Multi-objective duality results are given for convex composite problems which are not necessarily convex programming problems. Applications of the results to new and some special classes of nonlinear programming problems are discussed. A scalarization result and a characterization of the set of all properly efficient solutions for convex composite problems are also discussed under appropriate conditions.This research was partially supported by the Australian Research Council grant A68930162.This author wishes to acknowledge the financial support of the Australian Research Council.     

拓扑向量空间中非光滑向量极值问题的最优性条件与对偶

本文提出了向量值函数的锥D-s凸，锥D-s拟凸，s右导数及锥D-s伪凸等新概念，探讨了锥D-s凸函数的有关性质，建立了带约束非光滑向量极值问题(VP)的最优性必要条件与涉及锥D-s凸(拟凸，伪凸)函数的约束极值问题(VP)的最优性充分条件，给出了原问题(VP)与其Mond-Weir型对偶问题的弱对偶与强对偶结论，揭示了(VP)的局部锥D-(弱)有效解与整体锥D-(弱)有效解，(VP)的锥D-弱有效解与锥D-有效解的关系，所得结果拓广了凸规划及部分广义凸规划的有关结论．     

Optimality Conditions and Geometric Properties of a Linear Multilevel Programming Problem with Dominated Objective Functions

In this paper, a model of a linear multilevel programming problem with dominated objective functions (LMPPD(l)) is proposed, where multiple reactions of the lower levels do not lead to any uncertainty in the upper-level decision making. Under the assumption that the constrained set is nonempty and bounded, a necessary optimality condition is obtained. Two types of geometric properties of the solution sets are studied. It is demonstrated that the feasible set of LMPPD(l) is neither necessarily composed of faces of the constrained set nor necessarily connected. These properties are different from the existing theoretical results for linear multilevel programming problems.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

区间值函数的可微性及其在区间值规划中的应用

利用实值函数的全微分思想,讨论了区间值函数的可微性,建立了区间值函数的$D$-可微性的概念及其一些基本性质. 通过讨论无约束区间规划的最优性条件,给出了一类约束函数为实值函数的约束区间值规划问题取得最优解的必要条件. 同时给出了具有实值函数约束的凸区间值规划问题取得最优解的充分条件.     

Infinite-dimensional convex programming with applications to constrained approximation

In this paper, existence and characterization of solutions and duality aspects of infinite-dimensional convex programming problems are examined. Applications of the results to constrained approximation problems are considered. Various duality properties for constrained interpolation problems over convex sets are established under general regularity conditions. The regularity conditions are shown to hold for many constrained interpolation problems. Characterizations of local proximinal sets and the set of best approximations are also given in normed linear spaces.The author is grateful to the referee for helpful suggestions which have contributed to the final preparation of this paper. This research was partially supported by Grant A68930162 from the Australian Research Council.     

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.)     

多目标半定规划的最优性条件及对偶理论

在不变凸的假设下来讨论多目标半定规划的最优性条件、对偶理论以及非凸半定规划的最优性条件．首先给出了非凸半定规划的一个KKT条件成立的充分必要条件, 并利用此定理证明了其最优性必要条件．其次讨论了多目标半定规划的最优性必要条件、充分条件, 并对其建立Wolfe对偶模型, 证明了弱对偶定理和强对偶定理．     

A sequential quadratically constrained quadratic programming method with an augmented Lagrangian line search function

Based on an augmented Lagrangian line search function, a sequential quadratically constrained quadratic programming method is proposed for solving nonlinearly constrained optimization problems. Compared to quadratic programming solved in the traditional SQP methods, a convex quadratically constrained quadratic programming is solved here to obtain a search direction, and the Maratos effect does not occur without any other corrections. The “active set” strategy used in this subproblem can avoid recalculating the unnecessary gradients and (approximate) Hessian matrices of the constraints. Under certain assumptions, the proposed method is proved to be globally, superlinearly, and quadratically convergent. As an extension, general problems with inequality and equality constraints as well as nonmonotone line search are also considered.     

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.     

求解MINLP的几类罚函数方法的分析和探讨

针对混合整数非线性约束优化问题(MINLP)的一般形式,通过罚函数的方法,给出了它的几种等价形式,并证明了最优解的等价性.将约束优化问题转化成更容易求解的无约束非线性优化问题,并把混合整数规划转化成非整数优化问题,从而将MINLP的求解简化为求解一个连续的无约束非线性优化问题,进而可用已有的一般无约束优化算法进行求解.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

解非线性约束优化问题的依赖域算法

本文对一般非线性约束优化问题提出了一个信赖域算法,导出了等价的KKT条件.在试探步满足适当条件下,证明了算法的全局收敛性,并进行了数值试验.     

On optimality and duality theorems of nonlinear disjunctive fractional minmax programs

This paper is concerned with the study of optimality conditions for disjunctive fractional minmax programming problems in which the decision set can be considered as a union of a family of convex sets. Dinkelbach’s global optimization approach for finding the global maximum of the fractional programming problem is discussed. Using the Lagrangian function definition for this type of problem, the Kuhn–Tucker saddle point and stationary-point problems are established. In addition, via the concepts of Mond–Weir type duality and Schaible type duality, a general dual problem is formulated and some weak, strong and converse duality theorems are proven.