Lagrangian Relaxations on Networks by <Emphasis Type="Italic">ε</Emphasis>-Subgradient Methods

The efficiency of the network flow techniques can be exploited in the solution of nonlinearly constrained network flow problems by means of approximate subgradient methods. The idea is to solve the dual problem by using ε-subgradient methods, where the dual function is estimated by minimizing approximately a Lagrangian function, which relaxes the side constraints and is subject only to network constraints. In this paper, convergence results for some kind of ε-subgradient methods are put forward. Moreover, in order to evaluate the quality of the solution and the efficiency of these methods some of them have been implemented and their performances computationally compared with codes that are able to solve the proposed test problems.     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

A descent algorithm for nonsmooth convex optimization

This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The algorithm can be implemented and may be considered a modification of the ε-subgradient algorithm and Lemarechal's descent algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below. Limited computational experience with the algorithm is also reported.     

Augmented Lagrangian Duality and Nondifferentiable Optimization Methods in Nonconvex Programming

In this paper we present augmented Lagrangians for nonconvex minimization problems with equality constraints. We construct a dual problem with respect to the presented here Lagrangian, give the saddle point optimality conditions and obtain strong duality results. We use these results and modify the subgradient and cutting plane methods for solving the dual problem constructed. Algorithms proposed in this paper have some advantages. We do not use any convexity and differentiability conditions, and show that the dual problem is always concave regardless of properties the primal problem satisfies. The subgradient of the dual function along which its value increases is calculated without solving any additional problem. In contrast with the penalty or multiplier methods, for improving the value of the dual function, one need not to take the penalty like parameter to infinity in the new methods. In both methods the value of the dual function strongly increases at each iteration. In the contrast, by using the primal-dual gap, the proposed algorithms possess a natural stopping criteria. The convergence theorem for the subgradient method is also presented.     

Ergodic,primal convergence in dual subgradient schemes for convex programming,II: the case of inconsistent primal problems

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.     

Cutting Plane Algorithms and Approximate Lower Subdifferentiability

A notion of boundedly ε-lower subdifferentiable functions is introduced and investigated. It is shown that a bounded from below, continuous, quasiconvex function is locally boundedly ε-lower subdifferentiable for every ε>0. Some algorithms of cutting plane type are constructed to solve minimization problems with approximately lower subdifferentiable objective and constraints. In those algorithms an approximate minimizer on a compact set is obtained in a finite number of iterations provided some boundedness assumption be satisfied.     

<Emphasis Type="Italic">ε</Emphasis>-Optimality and <Emphasis Type="Italic">ε</Emphasis>-Lagrangian Duality for a Nonconvex Programming Problem with an Infinite Number of Constraints

In this paper, ε-optimality conditions are given for a nonconvex programming problem which has an infinite number of constraints. The objective function and the constraint functions are supposed to be locally Lipschitz on a Banach space. In a first part, we introduce the concept of regular ε-solution and propose a generalization of the Karush-Kuhn-Tucker conditions. These conditions are up to ε and are obtained by weakening the classical complementarity conditions. Furthermore, they are satisfied without assuming any constraint qualification. Then, we prove that these conditions are also sufficient for ε-optimality when the constraints are convex and the objective function is ε-semiconvex. In a second part, we define quasisaddlepoints associated with an ε-Lagrangian functional and we investigate their relationships with the generalized KKT conditions. In particular, we formulate a Wolfe-type dual problem which allows us to present ε-duality theorems and relationships between the KKT conditions and regular ε-solutions for the dual. Finally, we apply these results to two important infinite programming problems: the cone-constrained convex problem and the semidefinite programming problem.     

Strong formulations for quadratic optimization with M-matrices and indicator variables

We propose a DC (Difference of two Convex functions) formulation approach for sparse optimization problems having a cardinality or rank constraint. With the largest-k norm, an exact DC representation of the cardinality constraint is provided. We then transform the cardinality-constrained problem into a penalty function form and derive exact penalty parameter values for some optimization problems, especially for quadratic minimization problems which often appear in practice. A DC Algorithm (DCA) is presented, where the dual step at each iteration can be efficiently carried out due to the accessible subgradient of the largest-k norm. Furthermore, we can solve each DCA subproblem in linear time via a soft thresholding operation if there are no additional constraints. The framework is extended to the rank-constrained problem as well as the cardinality- and the rank-minimization problems. Numerical experiments demonstrate the efficiency of the proposed DCA in comparison with existing methods which have other penalty terms.     

Subgradient projection algorithms for constrained nonsmooth optimization II: nonlinear constraints†

In this paper, a kind of subgradient projection algorithms is established for minimizing a locally Lipschitz continuous function subject to nonlinearly smooth constraints, which is based on the idea to get a feasible and strictly descent direction by combining the ?-subgradient projection direction that attempts to satisfy the Kuhn-Tucker conditions with one corrected direction produced by a linear programming subproblem. The algorithm avoids the zigzagging phenomenon and converges to Kuhn-Tucker points, due to using the c.d.f. maps of Polak and Mayne (1985), ?active constraints and ?adjusted rules     

Subgradient Methods for Saddle-Point Problems

We study subgradient methods for computing the saddle points of a convex-concave function. Our motivation comes from networking applications where dual and primal-dual subgradient methods have attracted much attention in the design of decentralized network protocols. We first present a subgradient algorithm for generating approximate saddle points and provide per-iteration convergence rate estimates on the constructed solutions. We then focus on Lagrangian duality, where we consider a convex primal optimization problem and its Lagrangian dual problem, and generate approximate primal-dual optimal solutions as approximate saddle points of the Lagrangian function. We present a variation of our subgradient method under the Slater constraint qualification and provide stronger estimates on the convergence rate of the generated primal sequences. In particular, we provide bounds on the amount of feasibility violation and on the primal objective function values at the approximate solutions. Our algorithm is particularly well-suited for problems where the subgradient of the dual function cannot be evaluated easily (equivalently, the minimum of the Lagrangian function at a dual solution cannot be computed efficiently), thus impeding the use of dual subgradient methods.     

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.     

Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem

For optimization problems that are structured both with respect to the constraints and with respect to the variables, it is possible to use primal–dual solution approaches, based on decomposition principles. One can construct a primal subproblem, by fixing some variables, and a dual subproblem, by relaxing some constraints and king their Lagrange multipliers, so that both these problems are much easier to solve than the original problem. We study methods based on these subproblems, that do not include the difficult Benders or Dantzig-Wolfe master problems, namely primal–dual subgradient optimization methods, mean value cross decomposition, and several comtbinations of the different techniques. In this paper, these solution approaches are applied to the well-known uncapacitated facility location problem. Computational tests show that some combination methods yield near-optimal solutions quicker than the classical dual ascent method of Erlenkotter     

Nonlinear programming methods in the presence of noise

The problem of minimizing a nonlinear function with nonlinear constraints when the values of the objective, the constraints and their gradients have errors, is studied. This noise may be due to the stochastic nature of the problem or to numerical error.Various previously proposed methods are reviewed. Generally, the minimization algorithms involve methods of subgradient optimization, with the constraints introduced through penalty, Lagrange, or extended Lagrange functions. Probabilistic convergence theorems are obtained. Finally, an algorithm to solve the general convex (nondifferentiable) programming problem with noise is proposed.Originally written for presentation at the 1976 Budapest Symposium on Mathematical Programming.     

Dual approaches to finite element model updating

The problem of finding the least change adjustment to a stiffness matrix modeled by finite element method is considered in this paper. Desired stiffness matrix properties such as symmetry, sparsity, positive semidefiniteness, and satisfaction of the characteristic equation are imposed as side constraints of the constructed optimal matrix approximation for updating the stiffness matrix, which matches measured data better. The dual problems of the original constrained minimization are presented and solved by subgradient algorithms with different line search strategies. Some numerical results are included to illustrate the performance and application of the proposed methods.     

Optimization of Optimal Power Flow Problems

Optimal power flow problems arise in the context of the optimization and secure exploitation of electrical power in alternating current (AC) networks. This optimization problem evaluates the flow on each line and to ensure that they are under line thermal limits. To improve the reliability of the power supply, a secure network is necessary, i.e., it has to be able to cope with some contingencies. Nowadays high performance solution methods, that are based on nonlinear programming algorithms, search for an optimal state while considering certain contingencies. According to the number of contingencies the problem size increases linearly. As the base case can already be large-scaled, the optimization time computation increases quickly. Parallelization seems to be a good way to solve quickly this kind of problem. This paper considers the minimization of an objective function and at least two constraints at each node. This optimization problem is solved by IPOPT, an interior point method, coupled with ADOL-C, an algorithmic differentiation tool, and MA27, a linear solver. Several results on employed parallelizing strategies will be discussed. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A practical general approximation criterion for methods of multipliers based on Bregman distances

 This paper demonstrates that for generalized methods of multipliers for convex programming based on Bregman distance kernels – including the classical quadratic method of multipliers – the minimization of the augmented Lagrangian can be truncated using a simple, generally implementable stopping criterion based only on the norms of the primal iterate and the gradient (or a subgradient) of the augmented Lagrangian at that iterate. Previous results in this and related areas have required conditions that are much harder to verify, such as ε-optimality with respect to the augmented Lagrangian, or strong conditions on the convex program to be solved. Here, only existence of a KKT pair is required, and the convergence properties of the exact form of the method are preserved. The key new element in the analysis is the use of a full conjugate duality framework, as opposed to mainly examining the action of the method on the standard dual function of the convex program. An existence result for the iterates, stronger than those possible for the exact form of the algorithm, is also included. Received: February 6, 2001 / Accepted: January 25, 2003 Published online: March 21, 2003 Mathematics Subject Classification (1991): 90C25, 90C46, 47H05     

Dual extragradient algorithms extended to equilibrium problems

In this paper we propose two iterative schemes for solving equilibrium problems which are called dual extragradient algorithms. In contrast with the primal extragradient methods in Quoc et al. (Optimization 57(6):749–776, 2008) which require to solve two general strongly convex programs at each iteration, the dual extragradient algorithms proposed in this paper only need to solve, at each iteration, one general strongly convex program, one projection problem and one subgradient calculation. Moreover, we provide the worst case complexity bounds of these algorithms, which have not been done in the primal extragradient methods yet. An application to Nash-Cournot equilibrium models of electricity markets is presented and implemented to examine the performance of the proposed algorithms.     

The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in Rⁿ is presented. After obtaining separability between integer and continuous variables in the objective function, a Lagrange dual program is proposed. To solve this dual problem (and obtaining a lower bound for ESTP) we use subgradient techniques. In order to evaluate a subgradient at each iteration we have to solve three optimization problems, two in polynomial time, and one is a special convex nondifferentiable programming problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

NONDESCENT SUBGRADIENT METHOD FOR NONSMOOTH CONSTRAINED MINIMIZATION

A kind of nondecreasing subgradient algorithm with appropriate stopping rule has been proposed for nonsmooth constrained minimization problem. The dual theory is invoked in dealing with the stopping rule and general global minimiizing algorithm is employed as a subroutine of the algorithm. The method is expected to tackle a large class of nonsmooth constrained minimization problem.     

Application of the dual active set algorithm to quadratic network optimization

A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature.