Sufficient optimality conditions for multidimensional optimal control problems with mixed constraints governed by an elliptic PDE

In this article, the idea of a dual dynamic programming is applied to the optimal control problems with multiple integrals governed by a semi-linear elliptic PDE and mixed state-control constraints. The main result called a verification theorem provides the new sufficient conditions for optimality in terms of a solution to the dual equation of a multidimensional dynamic programming. The optimality conditions are also obtained by using the concept of an optimal dual feedback control. Besides seeking the exact minimizers of problems considered some kind of an approximation is given and the sufficient conditions for an approximated optimal pair are derived.     

Multidimensional Dual Dynamic Programming

In this paper, we develop a dual approach to the dynamic programming for the optimal control problem in a multidimensional case. The idea of our method consists in defining, instead of the value function, a new function which satisfies a dual first-order partial differential equation of dynamic programming. We then prove a suitable verification theorem and introduce the concept of a dual feedback control. The sufficient optimality conditions thus obtained are analogous to their one-dimensional counterparts.     

A dual dynamic programming for minimax optimal control problems governed by parabolic equation

In the article, minimax optimal control problems governed by parabolic equations are considered. We apply a new dual dynamic programming approach to derive sufficient optimality conditions for such problems. The idea is to move all the notions from a state space to a dual space and to obtain a new verification theorem providing the conditions, which should be satisfied by a solution of the dual partial differential equation of dynamic programming. We also give sufficient optimality conditions for the existence of an optimal dual feedback control and some approximation of the problem considered, which seems to be very useful from a practical point of view.     

Proving total dual integrality with cross-free families—A general framework

We present a theorem stating that certain classes of linear programming problems have integer optimal (primal and dual) solutions. The theorem includes as special cases earlier results of Johnson, Edmonds and Giles, Frank, Hoffman and Schwartz, Gröflin and Hoffman, and Lawler and Martel. The proof method consists of deriving total dual integrality for the corresponding system of linear inequalities from the total unimodularity of certain ‘cross-free’ subsystems. The scheme presented here differs from the one proposed earlier by Grishuhin in that Grishuhin requires the total unimodularity of cross-free subsystems in the axioms, whereas here this follows from easier verifiable axioms.     

Optimal investment of DC pension plan under short-selling constraints and portfolio insurance

In this paper we investigate an optimal investment problem under short-selling and portfolio insurance constraints faced by a defined contribution pension fund manager who is loss averse. The financial market consists of a cash bond, an indexed bond and a stock. The manager aims to maximize the expected S-shaped utility of the terminal wealth exceeding a minimum guarantee. We apply the dual control method to solve the problem and derive the representations of the optimal wealth process and trading strategies in terms of the dual controlled process and the dual value function. We also perform some numerical tests and show how the S-shaped utility, the short-selling constraints and the portfolio insurance impact the optimal terminal wealth.     

Duality and existence theory for nondifferentiable programming

Necessary and sufficient conditions of optimality are given for a nonlinear nondifferentiable program, where the constraints are defined via closed convex cones and their polars. These results are then used to obtain an existence theorem for the corresponding stationary point problem, under some convexity and regularity conditions on the functions involved, which also guarantee an optimal solution to the programming problem. Furthermore, a dual problem is defined, and a strong duality theorem is obtained under the assumption that the constraint sets of the primal and dual problems are nonempty.     

Existence of Optimal Controls for Semilinear Parabolic Equations without Cesari-Type Conditions

Abstract. Optimal control problems governed by semilinear parabolic partial differential equations are considered. No Cesari-type conditions are assumed. By proving the existence theorem and the Pontryagin maximum principle of optimal ``state-control" pairs for the corresponding relaxed problems, an existence theorem of optimal pairs for the original problem is established.     

Projection and restriction methods in geometric programming and related problems

Mathematical programming problems with unattained infima or unbounded optimal solution sets are dual to problems which lackinterior points, e.g., problems for which the Slater condition fails to hold or for which the hypothesis of Fenchel's theorem fails to hold. In such cases, it is possible to project the unbounded problem onto a subspace and to restrict the dual problem to an affine set so that the infima are not altered. After a finite sequence of such projections and restrictions, dual problems are obtained which have bounded optimal solution sets andinterior points. Although results of this kind have occasionally been used in other contexts, it is in geometric programming (both in the original psynomial form and the generalized form) where such methods appear most useful. In this paper, we present a treatment of dual projection and restriction methods developed in terms of dual generalized geometric programming problems. Analogous results are given for Fenchel and ordinary dual problems.This research was supported in part by Grant No. AFOSR-73-2516 from the Air Force Office of Scientific Research and by Grant No. NSF-ENG-76-10260 from the National Science Foundation.The authors wish to express their appreciation to the referees for several helpful comments.     

On the existence of dual solutions for Lorentzian cost functions

The dual problem of optimal transportation in Lorentz-Finsler geometry is studied. It is shown that in general no solution exists even in the presence of an optimal coupling. Under natural assumptions dual solutions are established. It is further shown that the existence of a dual solution implies that the optimal transport is timelike on a set of full measure. In the second part the persistence of absolute continuity along an optimal transportation under obvious assumptions is proven and a solution to the relativistic Monge problem is provided.     

Existence of Optimal Controls for Semilinear Parabolic Equations without Cesari-Type Conditions

   Abstract. Optimal control problems governed by semilinear parabolic partial differential equations are considered. No Cesari-type conditions are assumed. By proving the existence theorem and the Pontryagin maximum principle of optimal ``state-control" pairs for the corresponding relaxed problems, an existence theorem of optimal pairs for the original problem is established.     

Dual multilevel optimization

We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming test problems.      

Convex risk functionals: Representation and applications

We introduce the family of law-invariant convex risk functionals, which includes a wide majority of practically used convex risk measures and deviation measures. We obtain a unified representation theorem for this family of functionals. Two related optimization problems are studied. In the first application, we determine worst-case values of a law-invariant convex risk functional when the mean and a higher moment such as the variance of a risk are known. Second, we consider its application in optimal reinsurance design for an insurer. With the help of the representation theorem, we can show the existence and the form of optimal solutions.     

On a Dual Risk Model Perturbed by Diffusion with Dividend Threshold

In the dual risk model, the surplus process of a company is a L′evy process with sample paths that are skip-free downwards. In this paper, the authors assume that the surplus process is the sum of a compound Poisson process and an independent Wiener process. The dual of the jump-diffusion risk model under a threshold dividend strategy is discussed. The authors derive a set of two integro-differential equations satisfied by the expected total discounted dividend until ruin. The cases where profits follow an exponential or mixtures of exponential distributions are solved. Applying the key method of the Laplace transform, the authors show how the integro-differential equations are solved. The authors also discuss the conditions for optimality and show how an optimal dividend threshold can be calculated as well.     

Success Guarantee of Dual Search in Integer Programming: p-th Power Lagrangian Method

Although the Lagrangian method is a powerful dual search approach in integer programming, it often fails to identify an optimal solution of the primal problem. The p-th power Lagrangian method developed in this paper offers a success guarantee for the dual search in generating an optimal solution of the primal integer programming problem in an equivalent setting via two key transformations. One other prominent feature of the p-th power Lagrangian method is that the dual search only involves a one-dimensional search within [0,1]. Some potential applications of the method as well as the issue of its implementation are discussed.     

广义框架的不相交性

Hilbert空间中框架的不相交性是由Han和Larson首先提出的,它与超框架有着密切的联系,在超框架及框架的构造中扮演重要的角色.广义框架是通常框架的推广.该文利用超广义框架刻画了广义框架的不相交性、强不相交性及弱不相交性;借助所得结果,给出了已知定理的不同证明方法;建立了对偶广义框架之间强不相交相和弱不相交性之间的关系;最后利用给定的强不相交的广义框架构造新的(超)对偶广义框架,所得结论恢复已有结果.     

A General Nonconvex Multiduality Principle

We introduce a (possibly infinite) collection of mutually dual nonconvex optimization problems, which share a common optimal value, and give a characterization of their global optimal solutions. As immediate consequences of our general multiduality principle, we obtain Toland–Singer duality theorem as well as an analogous result involving generalized perspective functions. Based on our duality theory, we propose an extension of an existing algorithm for the minimization of d.c. functions, which exploits Toland–Singer duality, to a more general class of nonconvex optimization problems.     

Energy distribution view for monotonic dual decomposition

We consider the problem of finding the most probable explanation (also known as the MAP assignment) on probabilistic graphical models. The dual decomposition algorithms based on coordinate descent are efficient approximate techniques for this problem, where the local dual functions are constructed and optimized to monotonically increase the cost of the dual function. In this paper, we present a unifying framework for constructing and optimizing these local dual functions, and introduce an energy distribution view to analyze the convergence rates of these algorithms. To optimize the local dual functions, we first propose a new concept—the energy distribution ratio—to describe the features of the solutions, and then derive an explicit optimal solution, which covers most of the monotonic dual decomposition algorithms. It is shown that the differences of these algorithms lie in both the forms of the local dual functions and the settings of the energy distribution ratios, and the existing algorithms mainly focus on constructing compact and solvable local dual functions. In contrast, we study the impact of the energy distribution ratios and introduce two energy distribution criteria for fast convergence. Moreover, we exploit dynamic energy distribution ratios to optimize the local dual functions, and propose a series of improved algorithms. The experimental results on synthetic and real problems show the improved algorithms outperform the existing ones on the convergence performance.     

集对代数软代数的集对表示

指出文[1]中的软代数表示定理（定理2．2）的错误,给出修改后的软代数表示定理。另外,讨论了集对代数的理想、同余关系和同余理想。     

Fenchel-Rockafellar type duality for a non-convex non-differential optimization problem

A Fenchel-Rockafellar type duality theorem is obtained for a non-convex and non-differentiable maximization problem by embedding the original problem in a family of perturbed problems. The recent results of Ivan Singer are developed in this more general framework. A relationship is also established between the solutions and optimal values of the primal and dual problems using the theory of subdifferential calculus.     

Solving dual problems using a coevolutionary optimization algorithm

In solving certain optimization problems, the corresponding Lagrangian dual problem is often solved simply because in these problems the dual problem is easier to solve than the original primal problem. Another reason for their solution is the implication of the weak duality theorem which suggests that under certain conditions the optimal dual function value is smaller than or equal to the optimal primal objective value. The dual problem is a special case of a bilevel programming problem involving Lagrange multipliers as upper-level variables and decision variables as lower-level variables. Another interesting aspect of dual problems is that both lower and upper-level optimization problems involve only box constraints and no other equality of inequality constraints. In this paper, we propose a coevolutionary dual optimization (CEDO) algorithm for co-evolving two populations—one involving Lagrange multipliers and other involving decision variables—to find the dual solution. On 11 test problems taken from the optimization literature, we demonstrate the efficacy of CEDO algorithm by comparing it with a couple of nested smooth and nonsmooth algorithms and a couple of previously suggested coevolutionary algorithms. The performance of CEDO algorithm is also compared with two classical methods involving nonsmooth (bundle) optimization methods. As a by-product, we analyze the test problems to find their associated duality gap and classify them into three categories having zero, finite or infinite duality gaps. The development of a coevolutionary approach, revealing the presence or absence of duality gap in a number of commonly-used test problems, and efficacy of the proposed coevolutionary algorithm compared to usual nested smooth and nonsmooth algorithms and other existing coevolutionary approaches remain as the hallmark of the current study.