Primal-Dual Interior-Point Method for an Optimization Problem Related to the Modeling of Atmospheric Organic Aerosols

A mathematical model for the computation of the phase equilibrium related to atmospheric organic aerosols is presented. The phase equilibrium is given by the global minimum of the Gibbs free energy for a system that involves water and organic components. This minimization problem is equivalent to the determination of the convex hull of the corresponding molar Gibbs free energy function. A geometrical notion of phase simplex related to the convex hull is introduced to characterize mathematically the phases at equilibrium. A primal-dual interior-point algorithm for the efficient solution of the phase equilibrium problem is presented. A novel initialization of the algorithm, based on the properties of the phase simplex, is proposed to ensure the convergence to a global minimum of the Gibbs free energy. For a finite termination of the interior-point method, an active phase identification procedure is incorporated. Numerical results show the robustness and efficiency of the approach for the prediction of liquid-liquid equilibrium in multicomponent mixtures.Communicated by R. GlowinskiThis work was supported by US Environmental Protection Grant X-83234201. The second author was partially supported by Swiss National Science Foundation Grant PBEL2-103152.     

Primal-Dual Active-Set Algorithm for Chemical Equilibrium Problems Related to the Modeling of Atmospheric Inorganic Aerosols

A general equilibrium model for multiphase multicomponent inorganic atmospheric aerosols is proposed. The thermodynamic equilibrium is given by the minimum of the Gibbs free energy for a system involving an aqueous phase, a gas phase, and solid salts. A primal-dual algorithm solving the Karush-Kuhn-Tucker conditions is detailed. An active set/Newton method permits to compute the minimum of the energy and tracks the presence or not of solid salts at the equilibrium. Numerical results show the efficiency of our algorithm for the prediction of multiphase multireaction chemical equilibria.Communicated by R. GlowinskiThis work has been partially supported by the United States Environmental Protection Agency through Cooperative Agreement X-83234201 to the University of Houston. The second author was supported by the Swiss National Science Foundation, Grant PBEL2-103152.     

An optimization problem related to the modeling of atmospheric inorganic aerosols

A mathematical model for the computation of chemical equilibrium of atmospheric inorganic aerosols is proposed. The equilibrium is given by the minimum of the Gibbs free energy for a system involving an aqueous phase, a gas phase and solid salts. A primal-dual method solving the Karush–Kuhn–Tucker conditions is detailed. An active set/Newton method permits the computation of the minimum and track solid salts at the equilibrium. To cite this article: N.R. Amundson et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

An optimization problem related to the modeling of atmospheric organic aerosols

A mathematical model for the computation of the phase equilibrium related to atmospheric organic aerosols is proposed. The equilibrium is given by the minimum of the Gibbs free energy and is characterized using the notion of phase simplex of its convex hull. A primal-dual interior-point method solving the Karush–Kuhn–Tucker conditions is detailed. Numerical results show the efficiency of our algorithm. To cite this article: N.R. Amundson et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

有限维逼近无限维总极值的积分型方法

本文用有限维逼近无限维的方法来讨论函数空间中的总体最优化问题．我们给出了新的最优性条件和用变测度方法求得的有限维解逼近总体最优解的算法．对于有约柬问题，我们用不连续罚函数法把有约束问题化为无约束问题来求解．最后，我们通过一个具有非凸状态约束的最优控制问可题的实例来说明算法的有效性．     

Minimum Principle of Complementary Energy for Nonlinear Elastic Cable Networks with Geometrical Nonlinearities

A minimum principle of complementary energy is established for cable networks involving only the stress components as variables with geometrical nonlinearities and nonlinear elastic materials. The minimization problem of total potential energy is reformulated as a variational problem with a convex objective functional and an infinite number of second-order cone constraints; its Fenchel dual problem is shown to coincide with the minimization problem of the complementary energy. It is of interest to note that the obtained complementary energy attains always its minimum value at the equilibrium state irrespective of the stability of the cable networks, contrary to the fact that only stationary principles have been presented for elastic trusses and continua, even in the case of a stable equilibrium state.     

A matrix-free implementation of Riemannian Newton’s method on the Stiefel manifold

Newton’s method for unconstrained optimization problems on the Euclidean space can be generalized to that on Riemannian manifolds. The truncated singular value problem is one particular problem defined on the product of two Stiefel manifolds, and an algorithm of the Riemannian Newton’s method for this problem has been designed. However, this algorithm is not easy to implement in its original form because the Newton equation is expressed by a system of matrix equations which is difficult to solve directly. In the present paper, we propose an effective implementation of the Newton algorithm. A matrix-free Krylov subspace method is used to solve a symmetric linear system into which the Newton equation is rewritten. The presented approach can be used on other problems as well. Numerical experiments demonstrate that the proposed method is effective for the above optimization problem.     

A globally convergent semi-smooth Newton method for control-state constrained DAE optimal control problems

We investigate a semi-smooth Newton method for the numerical solution of optimal control problems subject to differential-algebraic equations (DAEs) and mixed control-state constraints. The necessary conditions are stated in terms of a local minimum principle. By use of the Fischer-Burmeister function the local minimum principle is transformed into an equivalent nonlinear and semi-smooth equation in appropriate Banach spaces. This nonlinear and semi-smooth equation is solved by a semi-smooth Newton method. We extend known local and global convergence results for ODE optimal control problems to the DAE optimal control problems under consideration. Special emphasis is laid on the calculation of Newton steps which are given by a linear DAE boundary value problem. Regularity conditions which ensure the existence of solutions are provided. A regularization strategy for inconsistent boundary value problems is suggested. Numerical illustrations for the optimal control of a pendulum and for the optimal control of discretized Navier-Stokes equations conclude the article.     

Interpolating clothoid splines with curvature continuity

An efficient algorithm for the computation of a C² interpolating clothoid spline is herein presented. The spline is obtained following an optimisation process, subject to continuity constraints. Among the 9 various targets/problems considered, there are boundary conditions, minimum length path, minimum jerk, and minimum curvature (energy). Some of these problems are solved with just a couple of Newton iterations, whereas the more complex minimisations are solved with few iterations of a nonlinear solver. The solvers are warmly started with a suitable initial guess, which is extensively discussed, making the algorithm fast. Applications of the algorithm are shown relating to fonts, path planning for human walkers, and as a tool for the time‐optimal lap on a Formula 1 circuit track.     

非线性互补约束规划问题的一个新的QP-free算法

本文研究了非线性互补约束均衡问题.利用互补函数以及光滑近似法,把非线性互补约束均衡问题转化为一个光滑非线性规划问题,得到了超线性收敛速度,数值实验结果表明本文提出的算法是可行的.     

A column generation algorithm for the estimation of origin–destination matrices in congested traffic networks

The general problem of estimating origin–destination (O–D) matrices in congested traffic networks is formulated as a mathematical programme with equilibrium constraints, referred to as the demand adjustment problem (DAP). This approach integrates the O–D matrix estimation and the network equilibrium assignment into one process. In this paper, a column generation algorithm for the DAP is presented. This algorithm iteratively solves a deterministic user equilibrium model for a given O–D matrix and a DAP restricted to the previously generated paths, whose solution generates a new O–D trip matrix estimation. The restricted DAP is formulated via a single level optimization problem. The convergence on local minimum of the proposed algorithm requires only the continuity of the link travel cost functions and the gauges used in the definition of the DAP.     

Numerical method for a dynamic optimization problem arising in the modeling of a population of aerosol particles

A model coupling differential equations and a sequence of constrained optimization problems is proposed for the simulation of the evolution of a population of particles at equilibrium interacting through a common medium.The first order optimality conditions of the optimization problems relaxed with barrier functions are coupled with the differential equations into a system of differential-algebraic equations that is discretized in time with an implicit first order scheme. The resulting system of nonlinear algebraic equations is solved at each time step with an interior-point/Newton method. The Newton system is block-structured and solved with Schur complement techniques, in order to take advantage of its sparsity. Application to the dynamics of a population of organic atmospheric aerosol particles is given to illustrate the evolution of particles of different sizes. To cite this article: A. Caboussat, A. Leonard, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

基于非线性相位恢复的X射线相位衬度断层成像算法

对全息测量下的X射线相位衬度断层成像问题提出了一种新的重建算法．该算法的主要想法是利用牛顿迭代法求解非线性的相位恢复问题．我们证明了牛顿方向满足的线性方程是非适定的,并利用共轭梯度法得到方程的正则化解．最后利用模拟数据进行了数值实验,数值结果验证了算法的合理性以及对噪声数据的数值稳定性,同时通过与线性化相位恢复算法的数值结果比较说明了新算法对探测数据不要求限制在Fresnel区域的近场,适用范围更广．     

Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming

When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida.     

互补约束均衡问题一个新的磨光技术

研究了一类带非线性互补约束的均衡问题．借助于逐步逼近思想,构造了一个在求解意义上与原问题等价的磨光非线性规划．从而保证一些经典的标准优化算法可以应用到该类优化问题上．最后提出了两个算法模型并分析了其全局收敛性．     

一类比式和问题的全局优化方法

对于一类比式和问题(P)给出一全局优化算法.首先利用线性约束的特征推导出问题(P)的等价问题(P1),然后利用新的线性松弛方法建立了问题(P1)的松弛线性规划(RLP),通过对目标函数可行域线性松弛的连续细分以及求解一系列线性规划,提出的分枝定界算法收敛到问题(P)的全局最优解.最终数值实验结果表明了该算法的可行性和高效性.     

Optimization Problem Coupled with Differential Equations: A Numerical Algorithm Mixing an Interior-Point Method and Event Detection

The numerical analysis of a dynamic constrained optimization problem is presented. It consists of a global minimization problem that is coupled with a system of ordinary differential equations. The activation and the deactivation of inequality constraints induce discontinuity points in the time evolution. A numerical method based on an operator splitting scheme and a fixed point algorithm is advocated. The ordinary differential equations are approximated by the Crank-Nicolson scheme, while a primal-dual interior-point method with warm-starts is used to solve the minimization problem. The computation of the discontinuity points is based on geometric arguments, extrapolation polynomials and sensitivity analysis. Second order convergence of the method is proved when an inequality constraint is activated. Numerical results for atmospheric particles confirm the theoretical investigations.     

Optimal control for elliptic systems with pointwise euclidean norm constraints on the controls

Optimal control for an elliptic system with pointwise Euclidean norm constraints on the control variables is investigated. First order optimality conditions are derived in a manner that is amenable for numerical realisation. An efficient semismooth Newton algorithm is proposed based on this optimality system. Numerical examples are given to validate the superlinear convergence of the semismooth Newton algorithm.     

A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique

This paper is concerned with the development of an algorithm to solve continuous polynomial programming problems for which the objective function and the constraints are specified polynomials. A linear programming relaxation is derived for the problem based on a Reformulation Linearization Technique (RLT), which generates nonlinear (polynomial) implied constraints to be included in the original problem, and subsequently linearizes the resulting problem by defining new variables, one for each distinct polynomial term. This construct is then used to obtain lower bounds in the context of a proposed branch and bound scheme, which is proven to converge to a global optimal solution. A numerical example is presented to illustrate the proposed algorithm.     

The Adjoint Newton Algorithm for Large-Scale Unconstrained Optimization in Meteorology Applications

A new algorithm is presented for carrying out large-scale unconstrained optimization required in variational data assimilation using the Newton method. The algorithm is referred to as the adjoint Newton algorithm. The adjoint Newton algorithm is based on the first- and second-order adjoint techniques allowing us to obtain the Newton line search direction by integrating a tangent linear equations model backwards in time (starting from a final condition with negative time steps). The error present in approximating the Hessian (the matrix of second-order derivatives) of the cost function with respect to the control variables in the quasi-Newton type algorithm is thus completely eliminated, while the storage problem related to the Hessian no longer exists since the explicit Hessian is not required in this algorithm. The adjoint Newton algorithm is applied to three one-dimensional models and to a two-dimensional limited-area shallow water equations model with both model generated and First Global Geophysical Experiment data. We compare the performance of the adjoint Newton algorithm with that of truncated Newton, adjoint truncated Newton, and LBFGS methods. Our numerical tests indicate that the adjoint Newton algorithm is very efficient and could find the minima within three or four iterations for problems tested here. In the case of the two-dimensional shallow water equations model, the adjoint Newton algorithm improves upon the efficiencies of the truncated Newton and LBFGS methods by a factor of at least 14 in terms of the CPU time required to satisfy the same convergence criterion.The Newton, truncated Newton and LBFGS methods are general purpose unconstrained minimization methods. The adjoint Newton algorithm is only useful for optimal control problems where the model equations serve as strong constraints and their corresponding tangent linear model may be integrated backwards in time. When the backwards integration of the tangent linear model is ill-posed in the sense of Hadamard, the adjoint Newton algorithm may not work. Thus, the adjoint Newton algorithm must be used with some caution. A possible solution to avoid the current weakness of the adjoint Newton algorithm is proposed.