线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

Computational Sensitivity Analysis for State Constrained Optimal Control Problems

A theoretical sensitivity analysis for parametric optimal control problems subject to pure state constraints has recently been elaborated in [7,8]. The articles consider both first and higher order state constraints and develop conditions for solution differentiability of optimal solutions with respect to parameters. In this paper, we treat the numerical aspects of computing sensitivity differentials via appropriate boundary value problems. In particular, numerical methods are proposed that allow to verify all assumptions underlying solution differentiability. Three numerical examples with state constraints of order one, two and four are discussed in detail.     

Numerische Methoden zur Behandlung einiger Problemklassen der nichtlinearen Tschebyscheff-Approximation mit Nebenbedingungen

Summary The numerical treatment of Chebyshev approximation problems is often difficult in practice because of complicated constraints. These are common in applications, for instance in differential equations. In this paper algorithms are derived for a constructive treatment of several classes of approximation problems, including parameter restrictions by Fréchet-differentiable mappings and inequality constraints in the space of approximating functions. The convergence properties of these methods are discussed and applications to practical problems are given.     

An efficient method for nonlinearly constrained networks

Many nonlinear network flow problems (in addition to the balance constraints in the nodes and capacity constraints on the arc flows) have nonlinear side constraints, which specify a flow relationship between several of the arcs in the network flow model. The short-term hydrothermal coordination of electric power generation is an example of this type. In this work we solve this kind of problem using an approach in which the efficiency of the well-known techniques for network flow can be preserved. It lies in relaxing the side constraints in an augmented Lagrangian function, and minimizing a sequence of these functions subject only to the network constraints for different estimates of the Lagrange multipliers of the side constraints. This method gives rise to an algorithm, which combines first- and superlinear-order multiplier methods to estimate these multipliers. When the number of free variables is very high we can obtain a superlinear-order estimate by means of the limited memory BFGS method fitted to our problem. An extensive computational comparison with other methods has been performed. The numerical results reported indicate that the algorithm described may be employed advantageously to solve large-scale network flow problems with nonlinear side constraints.     

A semismooth sequential quadratic programming method for lifted mathematical programs with vanishing constraints

Mathematical programs with vanishing constraints are a difficult class of optimization problems with important applications to optimal topology design problems of mechanical structures. Recently, they have attracted increasingly more attention of experts. The basic difficulty in the analysis and numerical solution of such problems is that their constraints are usually nonregular at the solution. In this paper, a new approach to the numerical solution of these problems is proposed. It is based on their reduction to the so-called lifted mathematical programs with conventional equality and inequality constraints. Special versions of the sequential quadratic programming method are proposed for solving lifted problems. Preliminary numerical results indicate the competitiveness of this approach.     

Efficient numerical methods for entropy-linear programming problems

Entropy-linear programming (ELP) problems arise in various applications. They are usually written as the maximization of entropy (minimization of minus entropy) under affine constraints. In this work, new numerical methods for solving ELP problems are proposed. Sharp estimates for the convergence rates of the proposed methods are established. The approach described applies to a broader class of minimization problems for strongly convex functionals with affine constraints.     

Convergence of algorithms for perturbed optimization problems

Infinite-dimensional optimization problems occur in various applications such as optimal control problems and parameter identification problems. If these problems are solved numerically the methods require a discretization which can be viewed as a perturbation of the data of the optimization problem. In this case the expected convergence behavior of the numerical method used to solve the problem does not only depend on the discretized problem but also on the original one. Algorithms which are analyzed include the gradient projection method, conditional gradient method, Newton's method and quasi-Newton methods for unconstrained and constrained problems with simple constraints.     

Interior-Point Algorithms,Penalty Methods and Equilibrium Problems

In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPECs)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties and provide substantial numerical results. We go on to show that penalty methods can resolve some problems that interior-point algorithms encounter in general. An erratum to this article is available at .     

Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints

Mathematical programs with equilibrium constraints (MPECs) are difficult optimization problems whose feasible sets do not satisfy most of the standard constraint qualifications. Hence MPECs cause difficulties both from a theoretical and a numerical point of view. As a consequence, a number of MPEC-tailored solution methods have been suggested during the last decade which are known to converge under suitable assumptions. Among these MPEC-tailored solution schemes, the relaxation methods are certainly one of the most prominent class of solution methods. Several different relaxation schemes are available in the meantime, and the aim of this paper is to provide a theoretical and numerical comparison of these schemes. More precisely, in the theoretical part, we improve the convergence theorems of several existing relaxation methods. There, we also take a closer look at the properties of the feasible sets of the relaxed problems and show which standard constraint qualifications are satisfied for these relaxed problems. Finally, the numerical comparison is based on the MacMPEC test problem collection.     

On a class of constrained functional minimization problems and their numerical solution

We investigate a class of functional minimization problems with constraints. By means of variational principles, optimal control theory, and numerical methods for nonlinear equations, numerical methods and the corresponding computer software are established to solve the problems. These tools can be used in fitting curves with arbitrary smoothness, different boundary conditions, and constraints. For special boundary conditions, analytical expressions of the curves are derived. Numerical examples are given to demonstrate the effectiveness of the algorithms by the means of curve fitting.     

An augmented Lagrangian method for optimization problems with structured geometric constraints

This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach.

     

Response surface methodology with stochastic constraints for expensive simulation

This article investigates simulation-based optimization problems with a stochastic objective function, stochastic output constraints, and deterministic input constraints. More specifically, it generalizes classic response surface methodology (RSM) to account for these constraints. This Generalized RSM—abbreviated to GRSM—generalizes the estimated steepest descent—used in classic RSM—applying ideas from interior point methods, especially affine scaling. This new search direction is scale independent, which is important for practitioners because it avoids some numerical complications and problems commonly encountered. Furthermore, the article derives a heuristic that uses this search direction iteratively. This heuristic is intended for problems in which simulation runs are expensive, so that the search needs to reach a neighbourhood of the true optimum quickly. The new heuristic is compared with OptQuest, which is the most popular heuristic available with several simulation software packages. Numerical illustrations give encouraging results.     

Numerical methods for solving some matrix feasibility problems

In this paper, we design two numerical methods for solving some matrix feasibility problems, which arise in the quantum information science. By making use of the structured properties of linear constraints and the minimization theorem of symmetric matrix on manifold, the projection formulas of a matrix onto the feasible sets are given, and then the relaxed alternating projection algorithm and alternating projection algorithm on manifolds are designed to solve these problems. Numerical examples show that the new methods are feasible and effective.     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

Spectral projected gradient and variable metric methods for optimization with linear inequalities

A family of variable metric methods for convex constrained optimizationwas introduced recently by Birgin, Martínez and Raydan.One of the members of this family is the inexact spectral projectedgradient (ISPG) method for minimization with convex constraints.At each iteration of these methods a strictly convex quadraticfunction with convex constraints must be (inexactly) minimized.In the case of the ISPG method it was shown that, in some importantapplications, iterative projection methods can be used for thisminimization. In this paper the particular case in which theconvex domain is a polytope described by a finite set of linearinequalities is considered. For solving the linearly constrainedconvex quadratic subproblem a dual approach is adopted, by meansof which subproblems become (not necessarily strictly) convexquadratic minimization problems with box constraints. Thesesubproblems are solved by means of an active-set box-constraintquadratic optimizer with a proximal-point type unconstrainedalgorithm for minimization within the current faces. Convergenceresults and numerical experiments are presented.     

Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization

Interior-point methods are among the most efficient approaches for solving large-scale nonlinear programming problems. At the core of these methods, highly ill-conditioned symmetric saddle-point problems have to be solved. We present combinatorial methods to preprocess these matrices in order to establish more favorable numerical properties for the subsequent factorization. Our approach is based on symmetric weighted matchings and is used in a sparse direct LDL ^T factorization method where the pivoting is restricted to static supernode data structures. In addition, we will dynamically expand the supernode data structure in cases where additional fill-in helps to select better numerical pivot elements. This technique can be seen as an alternative to the more traditional threshold pivoting techniques. We demonstrate the competitiveness of this approach within an interior-point method on a large set of test problems from the CUTE and COPS sets, as well as large optimal control problems based on partial differential equations. The largest nonlinear optimization problem solved has more than 12 million variables and 6 million constraints.     

Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra

 We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example. Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002 Key words. stochastic programming – integer programming – valid inequalities     

Matrix correction of a dual pair of improper linear programming problems with a block structure

The following problem is considered: how to modify the coefficient matrix of a dual pair of improper linear programs with a block structure so as to make these problems proper and minimize the sum of the squares of the Euclidean norms of the blocks in the correction matrix? Two variants of this problem are examined: (1) all the blocks in the coefficient matrix are modified, and (2) the upper block, which constraints all the primal variables, is left unchanged. Methods are presented for reducing these problems to minimizing quadratic fractional functions subject to linear equality and inequality constraints. The latter problem allows the use of conventional methods for constrained minimization. A numerical example is given.     

Simultaneous pseudo-time stepping for aerodynamic shape optimization

In this paper we discuss about numerical methods for aerodynamic shape optimization problems. These problems require efficient CFD techniques to solve the state (as well as costate) equations and fast algorithms for solving the optimization problems. Both of these are independent active areas of research since long time. Wide range of applications in science and engineering involve solution of optimization problems where the governing PDEs appear as constraints. Therefore, merging the two for the purpose of practical applicability is relatively new. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Self-adaptive projection-based prediction-correction method for constrained variational inequalities

The problems studied in this paper are a class of monotone constrained variational inequalities VI (S, f) in which S is a convex set with some linear constraints. By introducing Lagrangian multipliers to the linear constraints, such problems can be solved by some projection type prediction-correction methods. We focus on the mapping f that does not have an explicit form. Therefore, only its function values can be employed in the numerical methods. The number of iterations is significantly dependent on a parameter that balances the primal and dual variables. To overcome potential difficulties, we present a self-adaptive prediction-correction method that adjusts the scalar parameter automatically. Convergence of the proposed method is proved under mild conditions. Preliminary numerical experiments including some traffic equilibrium problems indicate the effectiveness of the proposed methods.