用非线性方程组求解等式约束非线性规划问题的降维算法

本文研究线性和非线性等式约束非线性规划问题的降维算法.首先,利用一般等式约束问题的降维方法,将线性等式约束非线性规划问题转换成一个非线性方程组,解非线性方程组即得其解;然后,对线性和非线性等式约束非线性规划问题用Lagrange乘子法,将非线性约束部分和目标函数构成增广的Lagrange函数,并保留线性等式约束,这样便得到一个线性等式约束非线性规划序列,从而,又将问题转化为求解只含线性等式约束的非线性规划问题.     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

不等式约束优化全局收敛的滤子线性方程组算法

设计了求解不等式约束非线性规划问题的一种新的滤子序列线性方程组算法,该算法每步迭代由减小约束违反度和目标函数值两部分构成.利用约束函数在某个中介点线性化的方法产生搜索方向.每步迭代仅需求解两个线性方程组,计算量较小.在一般条件下,证明了算法产生的无穷迭代点列所有聚点都是可行点并且所有聚点都是所求解问题的KKT点.     

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

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

一类求解线性约束非线性规划问题的可行方向法

Wilson,Han和Powell提出的序列二次规划方法(简称SQP方法)是求解非线性规划问题的一个著名方法,这种方法每次迭代的搜索方向是通过求解一个二次规划子问题得到的,本文受[1]启发,得到二次规划子问题的一个近似解,进而给出了一类求解线性约束非线性规划问题的可行方向法,在约束集合满足正则性的条件下,证明了该算法对五种常用线性搜索方法具有全局收敛性。     

对等式约束非线性规划问题的Hestenes-Powell增广拉格朗日函数的进一步研究

本文对用无约束极小化方法求解等式约束非线性规划问题的Hestenes-Powell 增广拉格朗日函数作了进一步研究．在适当的条件下,我们建立了Hestenes-Powell增广拉格朗日函数在原问题变量空间上的无约束极小与原约束问题的解之间的关系,并且也给出了Hestenes-Powell增广拉格朗日函数在原问题变量和乘子变量的积空间上的无约束极小与原约束问题的解之间的一个关系．因此,从理论的观点来看,原约束问题的解和对应的拉格朗日乘子值不仅可以用众所周知的乘子法求得,而且可以通过对Hestenes-Powell 增广拉格朗日函数在原问题变量和乘子变量的积空间上执行一个单一的无约束极小化来获得．     

多目标条件风险值的一种近似求解方法

本文研究了一种求解多目标条件风险值问题的近似方法,首先引入了多个损失函数在对应的置信水平下关于一个证券组合的α-VaR损失值,以及α-CVaR损失值概念．α-CVaR损失值表明了在给定的证券组合于置信水平对应的最小信用风险值的条件期望损失值,那么求出这样的最小条件期望损失值的模型构成了一个求解α-CVaR损失值的多目标问题,它的解就是最小条件期望损失值的有效证券组合,即Pareto弱有效解．为了求解它的Pareto弱有效解,我们引进了损失函数对应的优化问题(SCVaR),可以通过求解非线性规划问题(SCVaR)的最优解近似地刻画α—CVaR损失值,这样使得求解α-CVaR损失值变得容易．     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数-对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数一对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

多目标线性规划的一种交互式单纯形算法

本文基于分析有效极点解的有效变量的特点以及在有效点处各个目标函数的数值来得到改进的搜索方向的研究思想,提出了求解目标函数和约束均为线性的多目标线性规划问题的一种交互式算法。该方法可以保证每一步得到的解均为有效极点解,且根据决策者的偏好不断得到改进,直至最终得到满意的最终解。     

GOSAC: global optimization with surrogate approximation of constraints

We introduce GOSAC, a global optimization algorithm for problems with computationally expensive black-box constraints and computationally cheap objective functions. The variables may be continuous, integer, or mixed-integer. GOSAC uses a two-phase optimization approach. The first phase aims at finding a feasible point by solving a multi-objective optimization problem in which the constraints are minimized simultaneously. The second phase aims at improving the feasible solution. In both phases, we use cubic radial basis function surrogate models to approximate the computationally expensive constraints. We iteratively select sample points by minimizing the computationally cheap objective function subject to the constraint function approximations. We assess GOSAC’s efficiency on computationally cheap test problems with integer, mixed-integer, and continuous variables and two environmental applications. We compare GOSAC to NOMAD and a genetic algorithm (GA). The results of the numerical experiments show that for a given budget of allowed expensive constraint evaluations, GOSAC finds better feasible solutions more efficiently than NOMAD and GA for most benchmark problems and both applications. GOSAC finds feasible solutions with a higher probability than NOMAD and GOSAC.     

Solving mixed-integer robust optimization problems with interval uncertainty using Benders decomposition

Uncertainty and integer variables often exist together in economics and engineering design problems. The goal of robust optimization problems is to find an optimal solution that has acceptable sensitivity with respect to uncertain factors. Including integer variables with or without uncertainty can lead to formulations that are computationally expensive to solve. Previous approaches for robust optimization problems under interval uncertainty involve nested optimization or are not applicable to mixed-integer problems where the objective or constraint functions are neither quadratic, nor linear. The overall objective in this paper is to present an efficient robust optimization method that does not contain nested optimization and is applicable to mixed-integer problems with quasiconvex constraints (? type) and convex objective funtion. The proposed method is applied to a variety of numerical examples to test its applicability and numerical evidence is provided for convergence in general as well as some theoretical results for problems with linear constraints.     

A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

We study the set of 0–1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0–1 knapsack polytope and the 0–1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.     

Application of an anisotropic growth formulation to computational structural design

Common structural optimisation problems consist of problem-specific objective functions which have to be minimised mathematically with respect to design and state variables taking into account particular constraints. In contrast to this, we adopt a conceptually different approach for the design of a structure which is not based on a topology-optimisation technique. Instead, we apply a one-dimensional energy-driven constitutive evolution equation for the referential density–originally proposed for the simulation of remodelling effects in bones–and embed this into the micro-sphere-concept to end up with a three-dimensional anisotropic growth formulation. The objective of this contribution is to investigate this approach with emphasis on its application to structural design problems by means of two three-dimensional benchmark-type boundary value problems. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Reduced Functions, Gradients and Hessians from Fixed-Point Iterations for State Equations

In design optimization and parameter identification, the objective, or response function(s) are typically linked to the actually independent variables through equality constraints, which we will refer to as state equations. Our key assumption is that it is impossible to form and factor the corresponding constraint Jacobian, but one has instead some fixed-point algorithm for computing a feasible state, given any reasonable value of the independent variables. Assuming that this iteration is eventually contractive, we will show how reduced gradients (Jacobians) and Hessians (in other words, the total derivatives) of the response(s) with respect to the independent variables can be obtained via algorithmic, or automatic, differentiation (AD). In our approach the actual application of the so-called reverse, or adjoint differentiation mode is kept local to each iteration step. Consequently, the memory requirement is typically not unduly enlarged. The resulting approximating Lagrange multipliers are used to compute estimates of the reduced function values that can be shown to converge twice as fast as the underlying state space iteration. By a combination with the forward mode of AD, one can also obtain extra-accurate directional derivatives of the reduced functions as well as feasible state space directions and the corresponding reduced or projected Hessians of the Lagrangian. Our approach is verified by test calculations on an aircraft wing with two responses, namely, the lift and drag coefficient, and two variables, namely, the angle of attack and the Mach number. The state is a 2-dimensional flow field defined as solution of the discretized Euler equation under transonic conditions.     

Flux-splitting schemes for parabolic problems

Splitting with respect to space variables can be used in solving boundary value problems for second-order parabolic equations. Classical alternating direction methods and locally one-dimensional schemes could be examples of this approach. For problems with rapidly varying coefficients, a convenient tool is the use of fluxes (directional derivatives) as independent variables. The original equation is written as a system in which not only the desired solution but also directional derivatives (fluxes) are unknowns. In this paper, locally one-dimensional additional schemes (splitting schemes) for second-order parabolic equations are examined. By writing the original equation in flux variables, certain two-level locally one-dimensional schemes are derived. The unconditional stability of locally one-dimensional flux schemes of the first and second approximation order with respect to time is proved.     

带自由变量的广义几何规划全局求解的新算法

带自由变量的广义几何规划(FGGP)问题广泛出现在证券投资和工程设计等实际问题中.利用等价转换及对目标函数和约束函数的凸下界估计,提出一种求(FGGP)问题全局解的凸松弛方法.与已有方法相比,方法可处理符号项中含有更多变量的(FGGP)问题,且在最后形成的凸松弛问题中含有更少的变量和约束,从而在计算上更容易实现.最后数值实验表明文中方法是可行和有效的.     

求广义几何规划全局最优解的线性化方法

对广义几何规划问题(GGP)提出了一个确定型全局优化算法，这类优化问题能广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中，使用指数变换及对目标函数和约束函数的线性下界估计，建立了GGP的松弛线性规划(RLP)，通过对RLP可行域的细分以及一系列RLP的求解过程，从理论上证明了算法能收敛到GGP的全局最优解，对一个化学工程设计问题应用本文算法，数值实验表明本文方法是可行的。     

A comparative study of SQP-type algorithms for nonlinear and nonconvex mixed-integer optimization

We present numerical results of a comparative study of codes for nonlinear and nonconvex mixed-integer optimization. The underlying algorithms are based on sequential quadratic programming (SQP) with stabilization by trust-regions, linear outer approximations, and branch-and-bound techniques. The mixed-integer quadratic programming subproblems are solved by a branch-and-cut algorithm. Second order information is updated by a quasi-Newton update formula (BFGS) applied to the Lagrange function for continuous, but also for integer variables. We do not require that the model functions can be evaluated at fractional values of the integer variables. Thus, partial derivatives with respect to integer variables are replaced by descent directions obtained from function values at neighboring grid points, and the number of simulations or function evaluations, respectively, is our main performance criterion to measure the efficiency of a code. Numerical results are presented for a set of 100 academic mixed-integer test problems. Since not all of our test examples are convex, we reach the best-known solutions in about 90 % of the test runs, but at least feasible solutions in the other cases. The average number of function evaluations of the new mixed-integer SQP code is between 240 and 500 including those needed for one- or two-sided approximations of partial derivatives or descent directions, respectively. In addition, we present numerical results for a set of 55 test problems with some practical background in petroleum engineering.     

An algorithm for computing solutions of variational problems with global convexity constraints

We present an algorithm to approximate the solutions to variational problems where set of admissible functions consists of convex functions. The main motivation behind the numerical method is to compute solutions to Adverse Selection problems within a Principal-Agent framework. Problems such as product lines design, optimal taxation, structured derivatives design, etc. can be studied through the scope of these models. We develop a method to estimate their optimal pricing schedules.