【作者】 刘丙状；

【导师】 张连生；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2008， 博士

【摘要】 在工程、国防、经济、金融等领域中许多需要解答的问题可以建模为欧几里德空间中的约束最优化问题。求解约束最优化问题的主要方法之一是将它转化为无约束或带有简单约束的最优化问题,比较常用的两种方法是罚函数方法和拉格朗日函数方法。罚函数方法通过求解有限个或一系列的罚问题来得到约束最优化问题的解。通过精确罚函数可以将原约束最优化问题转化为一个无约束或带有简单约束的最优化问题,这样就避免了当罚参数太大时容易出现的病态情况,即罚函数的Hessian矩阵不适定。但是由于传统的精确罚函数不是可微的,这使得一些以梯度为基础的快速无约束算法难以得到应用,同时可能会在一些快速算法中引起阻止快速收敛的现象-Maratos效应。因此,构造既精确又光滑的罚函数是很有意义的。本文首先对几类约束最优化问题分别给出新的光滑精确罚函数,其次是对l₁精确罚函数光滑化,得到了几类光滑的近似精确罚函数。本文结构安排如下。第一章简要介绍了目前国内外关于罚函数以及序列二次规划方法的研究工作,重点介绍精确罚函数以及光滑精确罚函数的已有成果。第二章主要考虑构造新的简单光滑精确罚函数,这里“简单”是指所构造的罚函数只包含原约束最优化问题的目标函数以及约束函数的原始信息,而不包含它们的导数的信息。主要的想法是通过增加一个新的有限维甚至一维决策变量来构造罚函数。在第二节中对带有等式约束以及箱约束的最优化问题,通过增加一个一维变量,提出一类罚函数,将原问题转化为只带有简单箱约束的罚问题,在一定的条件下讨论了此类罚函数的光滑性、下有界性,并证明了原问题的最优解与罚问题的最优解是等价的,从而得出此类罚函数的精确性。一个简单的算法及数值例子说明通过解光滑的罚问题以求解原问题的方法是切实可行的。第三节对于只带有等式约束的最优化问题,通过增加一个一维变量给出了一类光滑罚函数,并讨论了其精确性。数值结果说明了算法的可行性。在第四节中,对带有不等式约束的最优化问题,通过增加一个一维变量提出了一类带有障碍的光滑罚函数,讨论了它的精确性。不同于一般的障碍函数方法,此光滑罚方法不需要以一个严格可行的内点作为初始点。另外,在实际的计算中,通常只需要求原约束最优化问题的近似解,因此第三章通过光滑逼近l₁精确罚函数,考虑几类光滑的且近似精确的罚函数。第二节对不等式约束最优化问题给出了一类光滑罚函数,并讨论了罚问题的最优解、最优值与原问题的最优解、最优值之间的误差估计。给出了一类近似算法,并讨论了与计算有关的问题。数值结果表明了此近似算法的可行性。第三节对于带有等式及不等式约束的一般最优化问题,提出了一类光滑近似精确罚函数,给出了罚问题的最优解、最优值与原问题的最优解、最优值之间的误差估计,并考虑一类近似算法。第四节以不等式约束优化问题为例,讨论了一族光滑近似精确罚函数,其中第二节中的罚函数可以作为此族罚函数的一个特例。给出了一种通过光滑罚问题来求原问题的精确解的算法,讨论了此算法的收敛性。第四章对全文的主要内容作出总结,并对未来的工作作出展望。更多还原

【Abstract】 Many important problems arising in the fields such as engineering,national defence, economy,and finance etc,can be modeled as constrained optimization problems. One of the main approaches for solving constrained optimization problems is to transform them into unconstrained optimization problems.Penalty function methods and Lagrangian duality methods are two prevailing approaches to implement the transformation.Penalty methods seek to obtain the solutions of the original constrained optimization problem by solving one or a sequence of penalty problems.By exact penalty function,a constrained optimization problem can be transformed into a single unconstrained or simple constrained optimization problem, which can avoid the appearance of the ill-conditioning case that the Hessian of the penalty function is seriously indefinite when the penalty parameter is too large.However,the traditional exact penalty function is non-differentiable,which makes it difficult to apply fast unconstrained algorithms based on the gradients and may cause the Maratos phenomena to appear in some fast algorithms such as the Sequential Quadratic Programming methods.So it is very meaningful to construct smooth and exact penalty function by some means.In this thesis,we firstly propose new smooth exact penalty functions for several kinds of constrained optimization problems;secondly,we obtain several classes of smooth and approximately exact penalty functions by smoothing the classical exact penalty functions.The present thesis is organized as follows.In Chapter 1,we give a brief introduction to the existed research work on the penalty functions and Sequential Quadratic Programming methods,with an emphasis on exact penalty functions and smooth exact penalty functions.In Chapter 2,we construct new simple smooth exact penalty functions,where the term "simple" means that the constructed penalty function only contains the original information of the objective function and the constraint functions in the constrained optimization problem,but doesn’t contain the information of their differentials. The main idea is to construct the penalty function by adding a new finite dimensional or even one dimensional decision variable.In Section 2.2,we propose a class of penalty function by adding a one-dimensional variable for the constrained optimization problem with equality constraints and simple bound constraints, and transform the original problem into a penalty problem with simple bound constraints.We discuss the smoothness of the new penalty function as well as other properties such as being bounded below.The equivalence between the optimal solutions of the original problem and those of the corresponding smoothed penalty problem is showed when the penalty parameter is sufficiently large,which implies the penalty function is exact.A simple algorithm and some numerical examples show that it is applicable to solve the smoothed penalty problem in order to solve the original problem.In Section 2.3,another smooth penalty function is proposed by adding a one-dimensional variable for the constrained optimization problem with only equality constraints,and its exactness is discussed.Numerical results show the performance of this penalty function.In Section 2.4,for inequality constrained optimization problem,a class of smooth penalty function with barrier property is proposed,and its exactness is also discussed.Compared with other barrier function methods,this smooth penalty method does not need a strict feasible interior point as the starting point.Since in the practical computation an approximate solution within the error bound is always needed,in Chapter 3 three kinds of smooth and approximately exact penalty functions are proposed.In Section 3.2 a class of smooth penalty function is proposed for inequality constrained optimization problem by adding a parameter to control its exactness.The error estimates between the optimal solutions of the original problem and of the penalty problem are discussed.An exact algorithm and an approximate algorithm are given,respectively.And some numerical results show the effect of the approximate algorithm.In Section 3.3,for general optimization problem with equality and inequality constraints,a class of smooth and approximately exact penalty function is given,and the error estimates are also discussed,with which an approximate algorithm is then proposed to solve the original problem.In Section 3.4,taking the inequality constrained optimization as an example,we give a family of smooth and approximately exact penalty functions which include the smooth penalty function given in Section 3.2.An algorithm that computes the exact solution of the original problem by solving the smoothed penalty problem is given and its convergence properties are discussed.In Chapter 4,we conclude the main contents in this thesis,and make some prospects for future works.更多还原