A class of problems where dual bounds beat underestimation bounds

We investigate the problem of minimizing a nonconvex function with respect to convex constraints, and we study different techniques to compute a lower bound on the optimal value: The method of using convex envelope functions on one hand, and the method of exploiting nonconvex duality on the other hand. We investigate which technique gives the better bound and develop conditions under which the dual bound is strictly better than the convex envelope bound. As a byproduct, we derive some interesting results on nonconvex duality.     

On the dual formulation of obstacle problems for the total variation and the area functional

We investigate the Dirichlet minimization problem for the total variation and the area functional with a one-sided obstacle. Relying on techniques of convex analysis, we identify certain dual maximization problems for bounded divergence-measure fields, and we establish duality formulas and pointwise relations between (generalized) BV minimizers and dual maximizers. As a particular case, these considerations yield a full characterization of BV minimizers in terms of Euler equations with a measure datum. Notably, our results apply to very general obstacles such as BV obstacles, thin obstacles, and boundary obstacles, and they include information on exceptional sets and up to the boundary. As a side benefit, in some cases we also obtain assertions on the limit behavior of p-Laplace type obstacle problems for $p\searrow 1$.On the technical side, the statements and proofs of our results crucially depend on new versions of Anzellotti type pairings which involve general divergence-measure fields and specific representatives of BV functions. In addition, in the proofs we employ several fine results on (BV) capacities and one-sided approximation.     

Conjugate dual problems in constrained set-valued optimization and applications

In this paper, two conjugate dual problems are proposed by considering the different perturbations to a set-valued vector optimization problem with explicit constraints. The weak duality, inclusion relations between the image sets of dual problems, strong duality and stability criteria are investigated. Some applications to so-called variational principles for a generalized vector equilibrium problem are shown.     

On the relationship between fenchel and Lagrange duality for optimization problems in general spaces

In this paper, the equivalence between a Fenchel and Lagrange duality theorem for optimization problems in dual pairs of real vector spaces is proved in a direct way.     

Auxiliary problem principle and decomposition of optimization problems

The auxiliary problem principle allows one to find the solution of a problem (minimization problem, saddle-point problem, etc.) by solving a sequence of auxiliary problems. There is a wide range of possible choices for these problems, so that one can give special features to them in order to make them easier to solve. We introduced this principle in Ref. 1 and showed its relevance to decomposing a problem into subproblems and to coordinating the subproblems. Here, we derive several basic or abstract algorithms, already given in Ref. 1, and we study their convergence properties in the framework of i infinite-dimensional convex programming.     

A decomposition method for convex minimization problems and its application

1. IntroductionConsider the following special convex programming problem(P) adn{f(~) g(z); Ax = z},where f: Re - (--co, co] and g: Re - (--co, co] are closed proper convex functions andA is an m x n matrix. The Lagrangian for problem (P) is defined by L: Rad x Re x Re -- (~co, co] as follows:L(x, z, y) = f(x) g(z) (y, Ax ~ z), (1.1)where (., .) denotes the inner product in the general sense and 'y is the Lagrangian multiplierassociated with the constraint Ax = z. The augmented L…     

A fast dual proximal gradient algorithm for convex minimization and applications

We consider the convex composite problem of minimizing the sum of a strongly convex function and a general extended valued convex function. We present a dual-based proximal gradient scheme for solving this problem. We show that although the rate of convergence of the dual objective function sequence converges to the optimal value with the rate O(1/k²)$O(1/k^2)$, the rate of convergence of the primal sequence is of the order O(1/k)$O(1/k)$.     

A Gauss-Seidel type solver for special convex programs,with application to frictional contact mechanics

An iterative method is described that solves the constrained minimization of a convex function, when the constraintsg _j(x ₁,...,x _n)0 are functions of only a few variables and can be partitioned in some way. A proof of convergence is given which is based on the fact that the function values that are generated decrease. The relation to the nonlinear equation solver TanGS is shown (Ref. 1), together with some new results for TanGS. Finally, the solver is applied to the solution of tangential traction in contact mechanics.     

Calculus rules for global approximate minima and applications to approximate subdifferential calculus

We provide calculus rules for global approximate minima concerning usual operations on functions. The formulas we obtain are then applied to approximate subdifferential calculus. In this way, new results are presented, for example on the approximate subdifferential of a deconvolution, or on the subdifferential of an upper envelope of convex functions.     

Some properties on G-evaluation and its applications to G-martingale decomposition

In this article, a sublinear expectation induced by G-expectation is introduced, which is called G- evaluation for convenience. As an application, we prove that for any ξ ∈ L β G (Ω T ) with some β > 1 the martingale decomposition theorem under G-expectaion holds, and that any β > 1 integrable symmetric G-martingale can be represented as an Ito integral w.r.t. G-Brownian motion. As a byproduct, we prove a regularity property for G-martingales: Any G-martingale {M t } has a quasi-continuous version.     

Asymptotic properties of projections with applications to stochastic regression problems

Almost sure convergence properties of least-squares estimates in stochastic regression models and an asymptotic theory of related Euclidean projections are developed herein. Applications to autoregressive processes and to dynamic input-output systems are also discussed.     

Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.     

两个泛函优化定理的证明

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

Convexification procedures and decomposition methods for nonconvex optimization problems

In order for primal-dual methods to be applicable to a constrained minimization problem, it is necessary that restrictive convexity conditions are satisfied. In this paper, we consider a procedure by means of which a nonconvex problem is convexified and transformed into one which can be solved with the aid of primal-dual methods. Under this transformation, separability of the type necessary for application of decomposition algorithms is preserved. This feature extends the range of applicability of such algorithms to nonconvex problems. Relations with multiplier methods are explored with the aid of a local version of the notion of a conjugate convex function.This work was carried out at the Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, and was supported by the National Science Foundation under Grant ENG 74-19332.     

On the relations between different duals assigned to composed optimization problems

For an optimization problem with a composed objective function and composed constraint functions we determine, by means of the conjugacy approach based on the perturbation theory, some dual problems to it. The relations between the optimal objective values of these duals are studied. Moreover, sufficient conditions are given in order to achieve equality between the optimal objective values of the duals and strong duality between the primal and the dual problems, respectively. Finally, some special cases of this problem are presented.      

Dual extrapolation and its applications to solving variational inequalities and related problems

In this paper we suggest new dual methods for solving variational inequalities with monotone operators. We show that with an appropriate step-size strategy, our method is optimal both for Lipschitz continuous operators ( $O({1 \over \epsilon})In this paper we suggest new dual methods for solving variational inequalities with monotone operators. We show that with an appropriate step-size strategy, our method is optimal both for Lipschitz continuous operators ( iterations), and for the operators with bounded variations ( iterations). Our technique can be applied for solving non-smooth convex minimization problems with known structure. In this case the worst-case complexity bound is iterations. The research results presented in this paper have been supported by a grant “Action de recherche concertè ARC 04/09-315” from the “Direction de la recherche scientifique, Communautè fran?aise de Belgique”. The scientific responsibility rests with its author(s).     

Solving multiple criteria problems by interactive decomposition

An interactive decomposition method is developed for solving the multiple criteria (MC) problem. Based on nonlinear programming duality theory, the MC problem is decomposed into a series of subproblems and relaxed master problems. Each subproblem is a bicriterion problem, and each relaxed master problem is a standard linear program. The prime objective of the decomposition is to simplify and facilitate the process of making preference assessments and tradeoffs across many conflicting objectives. Therefore, the decision-maker's preference function is not assumed to be known explicitly; rather, the decision maker is required to make only limited local preference assessments in the context of feasible and nondominated alternatives. Also, the preference assessments are of the form of ordinal paired comparisons, and in most of them only two criteria are allowed to change their values simultaneously, while the remaining (l–2) criteria are held fixed at certain levels.     

Relaxation methods for problems with strictly convex separable costs and linear constraints

We consider the minimization problem with strictly convex, possibly nondifferentiable, separable cost and linear constraints. The dual of this problem is an unconstrained minimization problem with differentiable cost which is well suited for solution by parallel methods based on Gauss-Seidel relaxation. We show that these methods yield the optimal primal solution and, under additional assumptions, an optimal dual solution. To do this it is necessary to extend the classical Gauss-Seidel convergence results because the dual cost may not be strictly convex, and may have unbounded level sets. Work supported by the National Science Foundation under grant NSF-ECS-3217668.     

Two-point boundary value problems by the extended Adomian decomposition method

In this paper, we present an efficient numerical algorithm for solving two-point linear and nonlinear boundary value problems, which is based on the Adomian decomposition method (ADM), namely, the extended ADM (EADM). The proposed method is examined by comparing the results with other methods. Numerical results show that the proposed method is much more efficient and accurate than other methods with less computational work.