Decomposition in large system optimization using the method of multipliers

Although the method of multipliers can resolve the dual gaps which will often appear between the true optimum point and the saddle point of the Lagrangian in large system optimization using the Lagrangian approach, it is impossible to decompose the generalized Lagrangian in a straightforward manner because of its quadratic character. A technique using the linear approximation of the perturbed generalized Lagrangian has recently been proposed by Stephanopoulos and Westerberg for the decomposition. In this paper, another attractive decomposition technique which transforms the nonseparable crossproduct terms into the minimum of sum of separable terms is proposed. The computational efforts required for large system optimization can be much reduced by adopting the latter technique in place of the former, as illustrated by application of these two techniques to an optimization problem of a chemical reactor system.The authors would like to acknowledge the valuable comments given by Professor D. G. Luenberger of Stanford University.     

The projection method of optimization applied to engineering plasticity problems

In engineering plasticity, the behavior of a structure (e.g., a frame or truss) under a variety of loading conditions is studied. Two primary types of analysis are generally conducted. Limit analysis determines the rigid plastic collapse load for a structure and can be formulated as a linear program (LP). Deformation analysis at plastic collapse can be formulated as a quadratic program (QP). The constraints of the two optimization problems are closely related. This paper presents a specialization of the projection method for linear programming for the limit-load analysis problem. The algorithm takes advantage of the relationship between the LP constraints and QP constraints to provide advantageous starting data for the projection method applied to the QP problem. An important feature of the method is that it avoids problems of apparent infeasibility due to roundoff errors. Experimental results are given for two medium-sized problems.This work was supported by the National Research Council of Canada under Research Grant No. A8189.     

On the limiting properties of dual trajectories in the Lagrange multipliers method

For the method of Lagrange multipliers (i.e., augmented Lagrangians), possible and typical scenarios for the asymptotic behavior of dual trajectories are examined in the case where the Lagrange multiplier is nonunique. The influence of these scenarios on the convergence rate is also investigated.     

Inertial alternating direction method of multipliers for non-convex non-smooth optimization

Computational Optimization and Applications - In this paper, we propose an algorithmic framework, dubbed inertial alternating direction methods of multipliers (iADMM), for solving a class of...     

A dual symmetric Gauss-Seidel alternating direction method of multipliers for hyperspectral sparse unmixing

Numerical Algorithms - Since sparse unmixing has emerged as a promising approach to hyperspectral unmixing, some spatial-contextual information in the hyperspectral images has been exploited to...     

An alternating direction method of multipliers for elliptic equation constrained optimization problem

We propose an alternating direction method of multipliers (ADMM) for solving the state constrained optimization problems governed by elliptic equations. The unconstrained as well as box-constrained cases of the Dirichlet boundary control, Robin boundary control, and right-hand side control problems are considered here. These continuous optimization problems are transformed into discrete optimization problems by the finite element method discretization, then are solved by ADMM. The ADMM is an efficient first order algorithm with global convergence, which combines the decomposability of dual ascent with the superior convergence properties of the method of multipliers. We shall present exhaustive convergence analysis of ADMM for these different type optimization problems. The numerical experiments are performed to verify the efficiency of the method.     

The role of the multipliers in the multiplier method

The paper studies the role of the multipliers when the multiplier method is applied as a computational technique for minimizing penalized cost functionals for optimal control problems characterized by linear systems and integral quadratic costs.Theauthor would like to gratefully thank two anonymous referees for many helpful suggestions which led to a major improvement in both the quality and clarity of the paper, and to Professor Angelo Miele for his encouragement.     

Further properties of Lagrange multipliers in nonsmooth optimization

We compute the Clarke generalized gradient of the marginal function of a nonconvex optimization problem with respect to usual and non usual parameters and we show how Lagrange multipliers are involved in this formula.     

Bounded sets of KKT multipliers in vector optimization

In this article we discuss the conditions required to guarantee the non-emptiness and the boundedness of certain subsets of the set of Lagrange multipliers for an inequality and equality constrained vector minimization problem.     

Duality gaps in nonconvex stochastic optimization

We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal decomposition. The second group of results concerns large stochastic optimization models with loosely coupled components. The results provide conditions implying relations between the duality gaps of geographical decomposition and the duality gaps for scenario and nodal decomposition, respectively.Mathematics Subject Classification (1991): 90C15Acknowledgments. This work was supported by the Priority Programme Online Optimization of Large Scale Systems of the Deutsche Forschungsgemeinschaft. The authors wish to thank Andrzej Ruszczyski (Rutgers University) for helpful discussions.     

A computation study on an integrated alternating direction method of multipliers for large scale optimization

The alternating direction method of multipliers (ADMM) has recently received a lot of attention especially due to its capability to harness the power of the new parallel and distributed computing environments. However, ADMM could be notoriously slow especially if the penalty parameter, assigned to the augmented term in the objective function, is not properly chosen. This paper aims to accelerate ADMM by integrating that with the Barzilai–Borwein gradient method and an acceleration technique known as line search. Line search accelerates an iterative method by performing a one-dimensional search along the line segment connecting two successive iterations. We pay a special attention to the large-scale nonnegative least squares problems, and our experiments using real datasets indicate that the integration not only accelerate ADMM but also robustifies that against the penalty parameter.     

Local convergence of the method of multipliers for variational and optimization problems under the noncriticality assumption

We present an efficient algorithm to find an optimal fiber orientation in composite materials. Within a two-scale setting fiber orientation is regarded as a function in space on the macrolevel. The optimization problem is formulated within a function space setting which makes the imposition of smoothness requirements straightforward and allows for rather general convex objective functionals. We show the existence of a global optimum in the Sobolev space H ¹(Ω). The algorithm we use is a one level optimization algorithm which optimizes with respect to the fiber orientation directly. The costly solve of a big number of microlevel problems is avoided using coordinate transformation formulas. We use an adjoint-based gradient type algorithm, but generalizations to higher-order schemes are straightforward. The algorithm is tested for a prototypical numerical example and its behaviour with respect to mesh independence and dependence on the regularization parameter is studied.     

真实利率波动对长期资产配置的影响(英)

对于单期的投资者而言,无违约风险的固定收益证券被视为无风险资产.这是因为固定收益证券的收益率在投资的初期就能确定.然而在考虑长期的投资时,投资者可以调整资产配置,固定收益证券也将面临再投资的利率波动风险,因此不能再被视为无风险资产.本文在一类特殊的``习惯形成"效用函数的框架下讨论长期资产配置.在一系列为简化问题而作的假设之下,本文推导出了真实利率波动对风险资产配置权重的影响,并且为计算实际长期资产配置的最优比例提供了理论依据和算法.     

Global optimization method using adaptive and parallel ensemble of surrogates for engineering design optimization

As a robust and efficient technique for global optimization, surrogate-based optimization method has been widely used in dealing with the complicated and computation-intensive engineering design optimization problems. It’s hard to select an appropriate surrogate model without knowing the behaviour of the real system a priori in most cases. To overcome this difficulty, a global optimization method using an adaptive and parallel ensemble of surrogates combining three representative surrogate models with optimized weight factors has been proposed. The selection of weight factors is treated as an optimization problem with the desired solution being one that minimizes the generalized mean square cross-validation error. The proposed optimization method is tested by considering several well-known numerical examples and one industrial problem compared with other optimization methods. The results show that the proposed optimization method can be a robust and efficient approach in surrogate-based optimization for locating the global optimum.     

A note on the method of multipliers

Implementation of the penalty function method for constrained optimization poses numerical difficulties as the penalty parameter increases. To offset this problem, one often resorts to Newton's method. In this note, working in the context of the penalty function method, we establish an intimate connection between the second-order updating formulas which result from Newton's method on the primal problem and Newton's method on the dual problem.The author wishes to thank Professor R. A. Tapia for his careful review of this note. He has contributed significantly to its content through several crucial observations.     

Newton’s method and its use in optimization

Newton’s method is a basic tool in numerical analysis and numerous applications, including operations research and data mining. We survey the history of the method, its main ideas, convergence results, modifications, its global behavior. We focus on applications of the method for various classes of optimization problems, such as unconstrained minimization, equality constrained problems, convex programming and interior point methods. Some extensions (non-smooth problems, continuous analog, Smale’s results, etc.) are discussed briefly, while some others (e.g., versions of the method to achieve global convergence) are addressed in more details.     

Existence of augmented Lagrange multipliers for cone constrained optimization problems

In this paper, by using an augmented Lagrangian approach, we obtain several sufficient conditions for the existence of augmented Lagrange multipliers of a cone constrained optimization problem in Banach spaces, where the corresponding augmenting function is assumed to have a valley at zero. Furthermore, we deal with the relationship of saddle points, augmented Lagrange multipliers, and zero duality gap property between the cone constrained optimization problem and its augmented Lagrangian dual problem.     

On the use of the table method in constrained optimization

In this paper, we take advantage of the availability of higher-order derivatives through the table method (see Ref. 1) and suggest a simple variant of the Lagrangian method for constrained optimization. Our method, and the software that we currently have can be used to minimize functions with many variables subject to an arbitrary number of constraints.On leave from the Faculty of Management, Tel Aviv University, Tel Aviv, Israel.