Two-level primal-dual decomposition technique for large-scale nonconvex optimization problems with constraints

A two-level decomposition method for nonconvex separable optimization problems with additional local constraints of general inequality type is presented and thoroughly analyzed in the paper. The method is of primal-dual type, based on an augmentation of the Lagrange function. Previous methods of this type were in fact three-level, with adjustment of the Lagrange multipliers at one of the levels. This level is eliminated in the present approach by replacing the multipliers by a formula depending only on primal variables and Kuhn-Tucker multipliers for the local constraints. The primal variables and the Kuhn-Tucker multipliers are together the higher-level variables, which are updated simultaneously. Algorithms for this updating are proposed in the paper, together with their convergence analysis, which gives also indications on how to choose penalty coefficients of the augmented Lagrangian. Finally, numerical examples are presented.     

Maximal vectors and multi-objective optimization

Maximal vector andweak-maximal vector are the two basic notions underlying the various broader definitions (like efficiency, admissibility, vector maximum, noninferiority, Pareto's optimum, etc.) for optimal solutions of multi-objective optimization problems. Moreover, the understanding and characterization of maximal and weak-maximal vectors on the space of index vectors (vectors of values of the multiple objective functions) is fundamental and useful to the understanding and characterization of Pareto-optimal and weak-optimal solutions on the space of solutions.This paper is concerned with various characterizations of maximal and weak-maximal vectors in a general subset of the EuclideanN-space, and with necessary conditions for Pareto-optimal and weak-optimal solutions to a generalN-objective optimization problem having inequality, equality, and open-set constraints on then-space. A geometric method is described; the validity of scalarization by linear combination is studied, and weak conditioning by directional convexity is considered; local properties and a fundamental necessary condition are given. A necessary and sufficient condition for maximal vectors in a simplex or a polyhedral cone is derived. Necessary conditions for Pareto-optimal and weak-optimal solutions are given in terms of Lagrange multipliers, linearly independent gradients, Jacobian and Gramian matrices, and Jacobian determinants.Several advantages in approaching the multi-objective optimization problem in two steps (investigate optimal index vectors on the space of index vectors first, and study optimal solutions on the specific space of solutions next) are demonstrated in this paper.This work was supported by the National Science Foundation under Grant No. GK-32701.     

对合变换和薄板弯曲问题的多变量变分原理

本文利用拉氏乘子法把薄板弯曲问题的最小位能原理和最小余能原理的变分约束条件解除.从而导出了常见的广义变分原理.为了降低泛函中变量导数的阶次.我们用对合变换引进新的正则变量.于是,我们可以进一步利用拉氏乘子法,把这些对合变换当作变分约束而予以消除,从而导出了各种多变量的薄板弯曲广义变分原理.事实证明,使用上述拉氏乘子法,并不能消除一切变分约束;为此,我们进一步引用高阶拉氏乘子法消除这些剩下来的约束条件,从而导得了薄板弯曲问题的更一般的广义变分原理.     

On differentiability with respect to parameter of solutions to convex optimal control problems subject to state space constraints

A family of convex optimal control problems that depend on a real parameterh is considered. The optimal control problems are subject to state space constraints.It is shown that under some regularity conditions on data the solutions of these problems as well as the associated Lagrange multipliers are directionally-differentiable functions of the parameter.The respective right-derivatives are given as the solution and respective Lagrange multipliers for an auxiliary quadratic optimal control problem subject to linear state space constraints.If a condition of strict complementarity type holds, then directional derivatives become continuous ones.     

An economical method of calculating Lagrange multiplier estimates for nonlinear programming problems when many of the constraints are bounds on the variables

Some recent methods for solving nonlinear programming problems make use of estimates of the Lagrange multipliers. These estimates are usually calculated by solving a system oft linear equations, wheret is the number of active constraints. It is shown that, when a large proportion of the active constraints consists of simple upper or lower bounds on the variables, then computational effort can be saved by means of a reorganization of this linear system.     

Lagrange Multiplier Conditions Characterizing the Optimal Solution Sets of Cone-Constrained Convex Programs

Various characterizations of optimal solution sets of cone-constrained convex optimization problems are given. The results are expressed in terms of subgradients and Lagrange multipliers. We establish first that the Lagrangian function of a convex program is constant on the optimal solution set. This elementary property is then used to derive various simple Lagrange multiplier-based characterizations of the solution set. For a finite-dimensional convex program with inequality constraints, the characterizations illustrate that the active constraints with positive Lagrange multipliers at an optimal solution remain active at all optimal solutions of the program. The results are applied to derive corresponding Lagrange multiplier characterizations of the solution sets of semidefinite programs and fractional programs. Specific examples are given to illustrate the nature of the results.     

The Singular Function Boundary Integral Method for singular Laplacian problems over circular sections

The Singular Function Boundary Integral Method (SFBIM) for solving two-dimensional elliptic problems with boundary singularities is revisited. In this method the solution is approximated by the leading terms of the asymptotic expansion of the local solution, which are also used to weight the governing partial differential equation. The singular coefficients, i.e., the coefficients of the local asymptotic expansion, are thus primary unknowns. By means of the divergence theorem, the discretized equations are reduced to boundary integrals and integration is needed only far from the singularity. The Dirichlet boundary conditions are then weakly enforced by means of Lagrange multipliers, the discrete values of which are additional unknowns. In the case of two-dimensional Laplacian problems, the SFBIM converges exponentially with respect to the numbers of singular functions and Lagrange multipliers. In the present work the method is applied to Laplacian test problems over circular sectors, the analytical solution of which is known. The convergence of the method is studied for various values of the order p of the polynomial approximation of the Lagrange multipliers (i.e., constant, linear, quadratic, and cubic), and the exact approximation errors are calculated. These are compared to the theoretical results provided in the literature and their agreement is demonstrated.     

On Normality of Lagrange Multipliers for State Constrained Optimal Control Problems

An optimal control problem for nonlinear ODEs, subject to mixed control-state and pure state constraints is considered. Sufficient conditions are formulated, under which unique normal Lagrange multipliers exist and are given by regular functions. These conditions include pointwise linear independence of gradients of f -active constraints and controllability of the linearized state equation. Under some additional assumptions, further regularity of the multipliers is shown.     

Stabilized SQP revisited

The stabilized version of the sequential quadratic programming algorithm (sSQP) had been developed in order to achieve superlinear convergence in situations when the Lagrange multipliers associated to a solution are not unique. Within the framework of Fischer (Math Program 94:91–124, 2002), the key to local superlinear convergence of sSQP are the following two properties: upper Lipschitzian behavior of solutions of the Karush-Kuhn-Tucker (KKT) system under canonical perturbations and local solvability of sSQP subproblems with the associated primal-dual step being of the order of the distance from the current iterate to the solution set of the unperturbed KKT system. According to Fernández and Solodov (Math Program 125:47–73, 2010), both of these properties are ensured by the second-order sufficient optimality condition (SOSC) without any constraint qualification assumptions. In this paper, we state precise relationships between the upper Lipschitzian property of solutions of KKT systems, error bounds for KKT systems, the notion of critical Lagrange multipliers (a subclass of multipliers that violate SOSC in a very special way), the second-order necessary condition for optimality, and solvability of sSQP subproblems. Moreover, for the problem with equality constraints only, we prove superlinear convergence of sSQP under the assumption that the dual starting point is close to a noncritical multiplier. Since noncritical multipliers include all those satisfying SOSC but are not limited to them, we believe this gives the first superlinear convergence result for any Newtonian method for constrained optimization under assumptions that do not include any constraint qualifications and are weaker than SOSC. In the general case when inequality constraints are present, we show that such a relaxation of assumptions is not possible. We also consider applying sSQP to the problem where inequality constraints are reformulated into equalities using slack variables, and discuss the assumptions needed for convergence in this approach. We conclude with consequences for local regularization methods proposed in (Izmailov and Solodov SIAM J Optim 16:210–228, 2004; Wright SIAM J. Optim. 15:673–676, 2005). In particular, we show that these methods are still locally superlinearly convergent under the noncritical multiplier assumption, weaker than SOSC employed originally.     

Approximate Greatest Descent Methods for Optimization with Equality Constraints

In an optimization problem with equality constraints the optimal value function divides the state space into two parts. At a point where the objective function is less than the optimal value, a good iteration must increase the value of the objective function. Thus, a good iteration must be a balance between increasing or decreasing the objective function and decreasing a constraint violation function. This implies that at a point where the constraint violation function is large, we should construct noninferior solutions relative to points in a local search region. By definition, an accessory function is a linear combination of the objective function and a constraint violation function. We show that a way to construct an acceptable iteration, at a point where the constraint violation function is large, is to minimize an accessory function. We develop a two-phases method. In Phase I some constraints may not be approximately satisfied or the current point is not close to the solution. Iterations are generated by minimizing an accessory function. Once all the constraints are approximately satisfied, the initial values of the Lagrange multipliers are defined. A test with a merit function is used to determine whether or not the current point and the Lagrange multipliers are both close to the optimal solution. If not, Phase I is continued. If otherwise, Phase II is activated and the Newton method is used to compute the optimal solution and fast convergence is achieved.     

New formulation of iterative substructuring methods without Lagrange multipliers: Neumann–Neumann and FETI

This article is devoted to introduce a new approach to iterative substructuring methods that, without recourse to Lagrange multipliers, yields positive definite preconditioned formulations of the Neumann–Neumann and FETI types. To my knowledge, this is the first time that such formulations have been made without resource to Lagrange multipliers. A numerical advantage that is concomitant to such multipliers‐free formulations is the reduction of the degrees of freedom associated with the Lagrange multipliers. Other attractive features are their generality, directness, and simplicity. The general framework of the new approach is rather simple and stems directly from the discretization procedures that are applied; in it, the differential operators act on discontinuous piecewise‐defined functions. Then, the Lagrange multipliers are not required because in such an environment the functions‐discontinuities are not an anomaly that need to be corrected. The resulting algorithms and equations‐systems are also derived with considerable detail. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

Computable numerical bounds for lagrange multipliers of stationary points of non-convex differentiable non-linear programs

It is shown that the satisfaction of a standard constraint qualification of mathematical programming [5] at a stationary point of a non-convex differentiable non-linear program provides explicit numerical bounds for the set of all Lagrange multipliers associated with the stationary point. Solution of a single linear program gives a sharper bound together with an achievable bound on the 1-norm of the multipliers associated with the inequality constraints. The simplicity of obtaining these bounds contrasts sharply with the intractable NP-complete problem of computing an achievable upper bound on the p-norm of the multipliers associated with the equality constraints for integer $\text{p ≧ 1}$.     

A Discrete Lagrangian-Based Global-Search Method for Solving Satisfiability Problems

Satisfiability is a class of NP-complete problems that model a wide range of real-world applications. These problems are difficult to solve because they have many local minima in their search space, often trapping greedy search methods that utilize some form of descent. In this paper, we propose a new discrete Lagrange-multiplier-based global-search method (DLM) for solving satisfiability problems. We derive new approaches for applying Lagrangian methods in discrete space, we show that an equilibrium is reached when a feasible assignment to the original problem is found and present heuristic algorithms to look for equilibrium points. Our method and analysis provides a theoretical foundation and generalization of local search schemes that optimize the objective alone and penalty-based schemes that optimize the constraints alone. In contrast to local search methods that restart from a new starting point when a search reaches a local trap, the Lagrange multipliers in DLM provide a force to lead the search out of a local minimum and move it in the direction provided by the Lagrange multipliers. In contrast to penalty-based schemes that rely only on the weights of violated constraints to escape from local minima, DLM also uses the value of an objective function (in this case the number of violated constraints) to provide further guidance. The dynamic shift in emphasis between the objective and the constraints, depending on their relative values, is the key of Lagrangian methods. One of the major advantages of DLM is that it has very few algorithmic parameters to be tuned by users. Besides the search procedure can be made deterministic and the results reproducible. We demonstrate our method by applying it to solve an extensive set of benchmark problems archived in DIMACS of Rutgers University. DLM often performs better than the best existing methods and can achieve an order-of-magnitude speed-up for some problems.     

两个泛函优化定理的证明

在泛函优化理论中,Lagrange乘子定理、对偶定理占有重要地位.建立了带有等式和不等式约束的泛函优化问题,并给出了广义Lagrange乘子定理、广义Lagrange对偶定理的证明.     

Analysis and approximation of optimal control problems for a simplified Ginzburg-Landau model of superconductivity

Summary. This paper is concerned with optimal control problems for a Ginzburg-Landau model of superconductivity that is valid for high values of the Ginzburg-Landau parameter and high external fields. The control is of Neumann type. We first show that optimal solutions exist. We then show that Lagrange multipliers may be used to enforce the constraints and derive an optimality system from which optimal states and controls may be deduced. Then we define finite element approximations of solutions for the optimality system and derive error estimates for the approximations. Finally, we report on some numerical results. Received May 3, 1994 / Revised version received November 28, 1995     

Error analysis of variable degree mixed methods for elliptic problems via hybridization

A new approach to error analysis of hybridized mixed methods is proposed and applied to study a new hybridized variable degree Raviart-Thomas method for second order elliptic problems. The approach gives error estimates for the Lagrange multipliers without using error estimates for the other variables. Error estimates for the primal and flux variables then follow from those for the Lagrange multipliers. In contrast, traditional error analyses obtain error estimates for the flux and primal variables first and then use it to get error estimates for the Lagrange multipliers. The new approach not only gives new error estimates for the new variable degree Raviart-Thomas method, but also new error estimates for the classical uniform degree method with less stringent regularity requirements than previously known estimates. The error analysis is achieved by using a variational characterization of the Lagrange multipliers wherein the other unknowns do not appear. This approach can be applied to other hybridized mixed methods as well.

     

On the perturbation of least squares problems with equality constraints

Some new perturbation results are presented for least squares problems with equality constraints, in which relative errors are obtained on perturbed solutions, least squares residuals, and vectors of Lagrange multipliers of the problem, based on the equivalence of the problem to a usual least squares problem and optimal perturbation results for orthogonal projections.     

Lagrangian Relaxation and the Single-Source Capacitated Facility-Location Problem

Lagrangian relaxation has been widely used in solving a number of hard combinatorial optimization problems. The success of the approach depends on the structure of the problem and on the values assigned to the Lagrange multipliers. A recent paper on the single-source capacitated facility-location problem proposed the use of Lagrangian relaxation in which the capacity constraints were relaxed. In this paper, a class of such problems is defined for which the proposed relaxation is guaranteed to result in an infeasible solution, irrespective of the values assigned to the Lagrange multipliers. In these cases, the bounds on the optimal solution, obtained from the relaxation, are generally poor. It is concluded that, when using Lagrangian relaxation, it may be worthwhile carrying out a preliminary analysis to determine the potential viability of the approach before extensive development takes place.     

Modified Legendre–Gauss–Radau Collocation Method for Optimal Control Problems with Nonsmooth Solutions

A new method is developed for solving optimal control problems whose solutions are nonsmooth. The method developed in this paper employs a modified form of the Legendre–Gauss–Radau orthogonal direct collocation method. This modified Legendre–Gauss–Radau method adds two variables and two constraints at the end of a mesh interval when compared with a previously developed standard Legendre–Gauss–Radau collocation method. The two additional variables are the time at the interface between two mesh intervals and the control at the end of each mesh interval. The two additional constraints are a collocation condition for those differential equations that depend upon the control and an inequality constraint on the control at the endpoint of each mesh interval. The additional constraints modify the search space of the nonlinear programming problem such that an accurate approximation to the location of the nonsmoothness is obtained. The transformed adjoint system of the modified Legendre–Gauss–Radau method is then developed. Using this transformed adjoint system, a method is developed to transform the Lagrange multipliers of the nonlinear programming problem to the costate of the optimal control problem. Furthermore, it is shown that the costate estimate satisfies one of the Weierstrass–Erdmann optimality conditions. Finally, the method developed in this paper is demonstrated on an example whose solution is nonsmooth.

     

Implementation of the Nitsche approach for various contact kinematics

Numerical approaches are in case of contact problems mainly dealing with additional terms enforcing constraints. Within the Nitsche approach the inclusion of constraints for the non-penetration and equilibrium of stresses of the contacting bodies is carried out in a fully variational sense. Taking into account a specific choice and the physical meaning of the encountered Lagrange multipliers two different schemes for the Nitsche formulation are obtained. Both types of the Nitsche approach are implemented in a nonlinear element and verification with numerical examples is done. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)