Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

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.     

Minimizing a Sum of Norms Subject to Linear Equality Constraints

Numerical analysis of a class of nonlinear duality problems is presented. One side of the duality is to minimize a sum of Euclidean norms subject to linear equality constraints (the constrained MSN problem). The other side is to maximize a linear objective function subject to homogeneous linear equality constraints and quadratic inequalities. Large sparse problems of this form result from the discretization of infinite dimensional duality problems in plastic collapse analysis.The solution method is based on the l ₁ penalty function approach to the constrained MSN problem. This can be formulated as an unconstrained MSN problem for which the first author has recently published an efficient Newton barrier method, and for which new methods are still being developed.Numerical results are presented for plastic collapse problems with up to 180000 variables, 90000 terms in the sum of norms and 90000 linear constraints. The obtained accuracy is of order 10^-8 measured in feasibility and duality gap.     

Characterizations of proximinal,semichebychevian and chebychevian subspaces in real normed spaces

A simple model optimal control problem for continuous casting with state-space constraints is approximated, as usual, by a penalty method and by a numerical discretization of the nonlinear heat equation. The convergence of the approximate problems directly to the original problem is proven under a stability criterion linking the penalty parameter with the discretization parameters. For this purpose, known discretization error estimates for the Stefan problem are extended for the case of time varying boundary conditions.     

Convergence Analysis of a Class of Penalty Methods for Vector Optimization Problems with Cone Constraints

In this paper, we consider convergence properties of a class of penalization methods for a general vector optimization problem with cone constraints in infinite dimensional spaces. Under certain assumptions, we show that any efficient point of the cone constrained vector optimization problem can be approached by a sequence of efficient points of the penalty problems. We also show, on the other hand, that any limit point of a sequence of approximate efficient solutions to the penalty problems is a weekly efficient solution of the original cone constrained vector optimization problem. Finally, when the constrained space is of finite dimension, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original cone constrained vector optimization problem if Mangasarian–Fromovitz constraint qualification holds at the limit point.This work is supported by the Postdoctoral Fellowship of Hong Kong Polytechnic University.     

Convergence rate of a penalty-function scheme

The penalty-function approach is an attractive method for solving constrained nonlinear programming problems, since it brings into play all of the well-developed unconstrained optimization techniques, If, however, the classical steepest-descent method is applied to the standard penalty-function objective, the rate of convergence approaches zero as the penalty coefficient is increased to yield a close approximation to the true solution.In this paper, it is shown that, ifm+1 steps of the conjugate-gradient method are successively repeated (wherem is the number of constraints), the convergence rate when applied to the penalty-function objective conveges at a rate predicted by the second derivative of the Lagrangian. This rate is independent of the penalty coefficient and, hence, the scheme yields reasonable convergence for a first-order method.This research was supported by National Science Foundation, Grant No. NSF-GK-1683.     

Augmented Lagrangian Objective Penalty Function

Augmented Lagrangian function is one of the most important tools used in solving some constrained optimization problems. In this article, we study an augmented Lagrangian objective penalty function and a modified augmented Lagrangian objective penalty function for inequality constrained optimization problems. First, we prove the dual properties of the augmented Lagrangian objective penalty function, which are at least as good as the traditional Lagrangian function's. Under some conditions, the saddle point of the augmented Lagrangian objective penalty function satisfies the first-order Karush-Kuhn-Tucker condition. This is especially so when the Karush-Kuhn-Tucker condition holds for convex programming of its saddle point existence. Second, we prove the dual properties of the modified augmented Lagrangian objective penalty function. For a global optimal solution, when the exactness of the modified augmented Lagrangian objective penalty function holds, its saddle point exists. The sufficient and necessary stability conditions used to determine whether the modified augmented Lagrangian objective penalty function is exact for a global solution is proved. Based on the modified augmented Lagrangian objective penalty function, an algorithm is developed to find a global solution to an inequality constrained optimization problem, and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the modified augmented Lagrangian objective penalty function is proved for a local solution. An algorithm is presented in finding a local solution, with its convergence proved under some conditions.     

An Ideal Penalty Function for Constrained Optimization

A well known approach to constrained optimization is via a sequenceof unconstrained minimization calculations applied to a penaltyfunction. This paper shown how it is posiible to generalizePowell's penelty function to solve constrained problems withboth equality and inequality constraints. The resulting methodsare equivalent to the Hestenes' method of multipliers, and ageneralization of this to inequality constraints suggested byRockafellar. Local duality results (not all of which have appearedbefore) for these methods are reviewed, with particular emphasison those of practical importance. It is shown that various strategiesfor varying control parameters are possible, all of which canbe viewed as Newton or Newton-like iterations applied to thedual problem. Practical strategies for guaranteeing convergenceare also discussed. A wide selection of numerical evidence isreported, and the algorithms are compared both amongst themselvesand with other penalty function methods. The new penalty functionis well conditioned, without singularities, and it is not necessaryfor the control parameters to tend to infinity in order to forceconvergence. The rate of convergence is rapid and high accuracyis achieved in few unconstrained minimizations.; furthermorethe computational effort for successive minimizations goes downrapidly. The methods are very easy to program efficiently, usingan established quasi-Newton subroutine for unconstrained minimization.     

Theoretical and Practical Convergence of a Self-Adaptive Penalty Algorithm for Constrained Global Optimization

This paper proposes a self-adaptive penalty function and presents a penalty-based algorithm for solving nonsmooth and nonconvex constrained optimization problems. We prove that the general constrained optimization problem is equivalent to a bound constrained problem in the sense that they have the same global solutions. The global minimizer of the penalty function subject to a set of bound constraints may be obtained by a population-based meta-heuristic. Further, a hybrid self-adaptive penalty firefly algorithm, with a local intensification search, is designed, and its convergence analysis is established. The numerical experiments and a comparison with other penalty-based approaches show the effectiveness of the new self-adaptive penalty algorithm in solving constrained global optimization problems.     

Implementation of a proximal algorithm for linearly constrained nonsmooth optimization problems and computational results

This paper describes an implementation of the so-calledproximal point algorithm for solving convex linearly constrained nonsmooth optimization problems. Contrary to other previous implementations of the same approach (which solve constrained nonsmooth problems as unconstrained problems via exact penalty function techniques), our implementation handles linear constraints explicitly (linear constraints being incorporated into the direction-finding subproblem). The relevance and efficiency of the approach is demonstrated through comparative computational experiments on many classical test problems from the literature, as well as on a series of large constrained dual transportation problems introduced and studied here for the first time.     

Calmness and Exact Penalization in Constrained Scalar Set-Valued Optimization

In this paper, we study a class of constrained scalar set-valued optimization problems, which includes scalar optimization problems with cone constraints as special cases. We introduce (local) calmness of order??? for this class of constrained scalar set-valued optimization problems. We show that the (local) calmness of order??? is equivalent to the existence of a (local) exact set-valued penalty map.     

Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function

 We propose and analyze a class of penalty-function-free nonmonotone trust-region methods for nonlinear equality constrained optimization problems. The algorithmic framework yields global convergence without using a merit function and allows nonmonotonicity independently for both, the constraint violation and the value of the Lagrangian function. Similar to the Byrd–Omojokun class of algorithms, each step is composed of a quasi-normal and a tangential step. Both steps are required to satisfy a decrease condition for their respective trust-region subproblems. The proposed mechanism for accepting steps combines nonmonotone decrease conditions on the constraint violation and/or the Lagrangian function, which leads to a flexibility and acceptance behavior comparable to filter-based methods. We establish the global convergence of the method. Furthermore, transition to quadratic local convergence is proved. Numerical tests are presented that confirm the robustness and efficiency of the approach. Received: December 14, 2000 / Accepted: August 30, 2001 Published online: September 27, 2002 Key words. nonmonotone trust-region methods – sequential quadratic programming – penalty function – global convergence – equality constraints – local convergence – large-scale optimization Mathematics Subject Classification (2000): 65K05, 90C30     

An Exact Penalty Function Method for Continuous Inequality Constrained Optimal Control Problem

In this paper, we consider a class of optimal control problems subject to equality terminal state constraints and continuous state and control inequality constraints. By using the control parametrization technique and a time scaling transformation, the constrained optimal control problem is approximated by a sequence of optimal parameter selection problems with equality terminal state constraints and continuous state inequality constraints. Each of these constrained optimal parameter selection problems can be regarded as an optimization problem subject to equality constraints and continuous inequality constraints. On this basis, an exact penalty function method is used to devise a computational method to solve these optimization problems with equality constraints and continuous inequality constraints. The main idea is to augment the exact penalty function constructed from the equality constraints and continuous inequality constraints to the objective function, forming a new one. This gives rise to a sequence of unconstrained optimization problems. It is shown that, for sufficiently large penalty parameter value, any local minimizer of the unconstrained optimization problem is a local minimizer of the optimization problem with equality constraints and continuous inequality constraints. The convergent properties of the optimal parameter selection problems with equality constraints and continuous inequality constraints to the original optimal control problem are also discussed. For illustration, three examples are solved showing the effectiveness and applicability of the approach proposed.     

Relaxation Methods for Strictly Convex Regularizations of Piecewise Linear Programs

We give an algorithm for minimizing the sum of a strictly convex function and a convex piecewise linear function. It extends several dual coordinate ascent methods for large-scale linearly constrained problems that occur in entropy maximization, quadratic programming, and network flows. In particular, it may solve exact penalty versions of such (possibly inconsistent) problems, and subproblems of bundle methods for nondifferentiable optimization. It is simple, can exploit sparsity, and in certain cases is highly parallelizable. Its global convergence is established in the recent framework of B -functions (generalized Bregman functions). Accepted 29 October 1996     

Viscosity methods for common solutions for equilibrium and hierarchical fixed point problems

Implicit and explicit viscosity methods for finding common solutions of equilibrium and hierarchical fixed points are presented. These methods are used to solve systems of equilibrium problems and variational inequalities where the involving operators are complements of nonexpansive mappings. The results here are situated on the lines of the research of the corresponding results of Moudafi [Krasnoselski-Mann iteration for hierarchical fixed-point problems, Inverse Probl. 23 (2007), pp. 1635–1640; Weak convergence theorems for nonexpansive mappings and equilibrium problems, to appear in JNCA], Moudafi and Maingé [Towards viscosity approximations of hierarchical fixed-points problems, Fixed Point Theory Appl. Art ID 95453 (2006), 10 pp.; Strong convergence of an iterative method for hierarchical fixed point problems, Pac. J. Optim. 3 (2007), pp. 529–538; Coupling viscosity methods with the extragradient algorithm for solving equilibrium problems, to appear in JNCA], Yao and Liou [Weak and strong convergence of Krasnosel'ski?–Mann iteration for hierarchical fixed point problems, Inverse Probl. 24 (2008), 015015 8 pp.], S. Takahashi and W. Takahashi [Viscosity approximation methods for equilibrium problems and fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 331 (2006), pp. 506–515], Xu [Viscosity method for hierarchical fixed point approach to variational inequalities, preprint.], Combettes and Hirstoaga [Equilibrium programming in Hilbert spaces, J. Nonlinear Convex Anal. 6 (2005), pp. 117–136] and Plubtieng and Pumbaeang [A general iterative method for equilibrium problems and fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 336 (2007), pp. 455–469.].     

A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Path-following barrier and penalty methods for linearly constrained problems

In the present paper some barrier and penalty methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a continuously differentiable primal and dual path, applied to linearly constrained convex problems are studied, in particular, the radius of convergence of Newton’s method depending on the barrier and penalty para-meter is estimated, Unlike using self-concordance properties the convergence bounds are derived by direct estimations of the solutions of the Newton equations. The obtained results establish parameter selection rules which guarantee the overall convergence of the considered barrier and penalty techniques with only a finite number of Newton steps at each parameter level. Moreover, the obtained estimates support scaling method which uses approximate dual multipliers as available in barrier and penalty methods     

Optimization methods for Dirichlet control problems

We discuss several optimization procedures to solve finite element approximations of linear-quadratic Dirichlet optimal control problems governed by an elliptic partial differential equation posed on a 2D or 3D Lipschitz domain. The control is discretized explicitly using continuous piecewise linear approximations. Unconstrained, control-constrained, state-constrained and control-and-state constrained problems are analysed. A preconditioned conjugate method for a reduced problem in the control variable is proposed to solve the unconstrained problem, whereas semismooth Newton methods are discussed for the solution of constrained problems. State constraints are treated via a Moreau–Yosida penalization. Convergence is studied for both the continuous problems and the finite dimensional approximations. In the finite dimensional case, we are able to show convergence of the optimization procedures even in the absence of Tikhonov regularization parameter. Computational aspects are also treated and several numerical examples are included to illustrate the theoretical results.     

A Joint Tikhonov Regularization and Augmented Lagrange Approach for Ill-Posed State Constrained Control Problems with Sparse Controls

Abstract

We provide a modified augmented Lagrange method coupled with a Tikhonov regularization for solving ill-posed state constrained elliptic optimal control problems with sparse controls. We consider a linear quadratic optimal control problem without any additional L² regularization terms. The sparsity is guaranteed by an additional L¹ term. Here, the modification of the classical augmented Lagrange method guarantees us uniform boundedness of the multiplier that corresponds to the state constraints. We present a coupling between the regularization parameter introduced by the Tikhonov regularization and the penalty parameter from the augmented Lagrange method, which allows us to prove strong convergence of the controls and their corresponding states. Moreover, convergence results proving the weak convergence of the adjoint state and weak*-convergence of the multiplier are provided. Finally, we demonstrate our method in several numerical examples.     

Comparison principles applied to obstacle problems with penalties

Penalty methods form a well known technique to embed elliptic variational inequality problems into a family of variational equations (cf. [6], [13], [17]). Using the specific inverse monotonicity properties of these problems L _∞-bounds for the convergence can be derived by means of comparison solutions. Lagrange duality is applied to estimate parameters involved.

For piecewise linear finite elements applied on weakly acute triangulations in combination with mass lumping the inverse monotonicity of the obstacle problems can be transferred to its discretization. This forms the base of similar error estimations in the maximum norm for the penalty method applied to the discrete problem.

The technique of comparison solutions combined with the uniform boundedness of the Lagrange multipliers leads to decoupled convergence estimations with respect to the discretization and penalization parameters.