Goal-oriented r-adaptivity based on the evaluation of the physical and material residual

This contribution is concerned with goal–oriented r-adaptivity based on energy minimization principles for the primal and the dual problem. We obtain a material residual of the primal and of the dual problem, which are indicators for non–optimal finite element meshes. For goal–oriented r-adaptivity we have to optimize the mesh with respect to the dual solution, because the error of a local quantity of interest depends on the error in the corresponding dual solution. We use the material residual of the primal and dual problem in order to obtain a procedure for mesh optimization with respect to a local quantity of interest. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Efficient algorithms for buffer space allocation

This paper describes efficient algorithms for determining how buffer space should be allocated in a flow line. We analyze two problems: a primal problem, which minimizes total buffer space subject to a production rate constraint; and a dual problem, which maximizes production rate subject to a total buffer space constraint. The dual problem is solved by means of a gradient method, and the primal problem is solved using the dual solution. Numerical results are presented. Profit optimization problems are natural generalizations of the primal and dual problems, and we show how they can be solved using essentially the same algorithms.     

Strong Duality with Proper Efficiency in Multiobjective Optimization Involving Nonconvex Set-Valued Maps

In this paper, we consider some dual problems of a primal multiobjective problem involving nonconvex set-valued maps. For each dual problem, we give conditions under which strong duality between the primal and dual problems holds in the sense that, starting from a Benson properly efficient solution of the primal problem, we can construct a Benson properly efficient solution of the dual problem such that the corresponding objective values of both problems are equal. The notion of generalized convexity of set-valued maps we use in this paper is that of near-subconvexlikeness.     

Using Duality Theory for Identification of Primal Efficient Points and for Sensitivity Analysis in Multiple Objective Linear Programming

The dual of the multiple objective linear programming problem is defined as a multiparametric LP problem for the right-hand sides. The resulting dual variables are multidimensional and are related to the indifference regions in the primal problem. The formulation of the dual is shown to be preferable to the vector minimization formulation in terms of (a) identifying primal efficient points and indifference regions, and (b) sensitivity analysis.     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数一对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

Strictly feasible solutions and strict complementarity in multiple objective linear optimization

Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification.     

Johri's general dual,the Lagrangian dual,and the surrogate dual

Duality formulations can be derived from a nonlinear primal optimization problem in several ways. One abstract theoretical concept presented by Johri is the framework of general dual problems. They provide the tightest of specific bounds on the primal optimum generated by dual subproblems which relax the primal problem with respect to the objective function or to the feasible set or even to both. The well-known Lagrangian dual and surrogate dual are shown to be special cases. Dominating functions and including sets which are the two relaxation devices of Johri's general dual turn out to be the most general formulations of augmented Lagrangian functions and augmented surrogate regions.     

ON SOME PROPERTIES OF SOLUTIONS TO SEMIDEFINITE PROGRAMMING

It is well known that for symmetric linear programming there exists a strictly complementary solution if the primal and the dual problems are both feasible. However, this is not necessary true for symmetric or general semide finite programming even if both the primal problem and its dual problem are strictly feasible. Some other properties are also concerned.     

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.     

The exact penalty map for nonsmooth and nonconvex optimization

Augmented Lagrangian duality provides zero duality gap and saddle point properties for nonconvex optimization. On the basis of this duality, subgradient-like methods can be applied to the (convex) dual of the original problem. These methods usually recover the optimal value of the problem, but may fail to provide a primal solution. We prove that the recovery of a primal solution by such methods can be characterized in terms of (i) the differentiability properties of the dual function and (ii) the exact penalty properties of the primal-dual pair. We also connect the property of finite termination with exact penalty properties of the dual pair. In order to establish these facts, we associate the primal-dual pair to a penalty map. This map, which we introduce here, is a convex and globally Lipschitz function and its epigraph encapsulates information on both primal and dual solution sets.     

Single machine scheduling with symmetric earliness and tardiness penalties

This research focuses on scheduling jobs with varying processing times and distinct due dates on a single machine subject to earliness and tardiness penalties. Hence, this work will find application in a just-in-time (JIT) production environment. The scheduling problem is formulated as a 0–1 linear integer program with three sets of constraints, where the objective is to minimize the sum of the absolute deviations between job completion times and their respective due dates. The first two sets of constraints are equivalent to the supply and demand constraints of an assignment problem. The third set, which represents the process time non-overlap constraints, is relaxed to form the Lagrangian dual problem. The dual problem is then solved using the subgradient algorithm. Efficient heuristics have also been developed in this work to yield initial primal feasible solutions and to convert primal infeasible solutions to feasibility. The computational results show that the relative deviation from optimality obtained by the subgradient algorithm is less than 3% for problem sizes varying from 10 to 100 jobs.     

On the convergence of the entropy-exponential penalty trajectories and generalized proximal point methods in semidefinite optimization

The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite programming problem are studied in this paper. It is proved that the primal path converges to the analytic center of the primal optimal set with respect to the entropy function, the dual path converges to a point in the dual optimal set and the primal-dual path associated to this paths converges to a point in the primal-dual optimal set. As an application, the generalized proximal point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered. The convergence of the primal proximal sequence to the analytic center of the primal optimal set with respect to the entropy function is established and the convergence of a particular weighted dual proximal sequence to a point in the dual optimal set is obtained.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

Duality theory in fuzzy optimization problems formulated by the Wolfe’s primal and dual pair

The weak and strong duality theorems in fuzzy optimization problem based on the formulation of Wolfe’s primal and dual pair problems are derived in this paper. The solution concepts of primal and dual problems are inspired by the nondominated solution concept employed in multiobjective programming problems, since the ordering among the fuzzy numbers introduced in this paper is a partial ordering. In order to consider the differentiation of a fuzzy-valued function, we invoke the Hausdorff metric to define the distance between two fuzzy numbers and the Hukuhara difference to define the difference of two fuzzy numbers. Under these settings, the Wolfe’s dual problem can be formulated by considering the gradients of differentiable fuzzy- valued functions. The concept of having no duality gap in weak and strong sense are also introduced, and the strong duality theorems in weak and strong sense are then derived naturally.     

Solutions and optimality criteria for nonconvex quadratic-exponential minimization problem

This paper presents a set of complete solutions and optimality conditions for a nonconvex quadratic-exponential optimization problem. By using the canonical duality theory developed by the first author, the nonconvex primal problem in n-dimensional space can be converted into an one-dimensional canonical dual problem with zero duality gap, which can be solved easily to obtain all dual solutions. Each dual solution leads to a primal solution. Both global and local extremality conditions of these primal solutions can be identified by the triality theory associated with the canonical duality theory. Several examples are illustrated.     

Computational Experience with Ill-Posed Problems in Semidefinite Programming

Many theoretical and algorithmic results in semidefinite programming are based on the assumption that Slater's constraint qualification is satisfied for the primal and the associated dual problem. We consider semidefinite problems with zero duality gap for which Slater's condition fails for at least one of the primal and dual problem. We propose a numerically reasonable way of dealing with such semidefinite programs. The new method is based on a standard search direction with damped Newton steps towards primal and dual feasibility.     

非凸集值优化问题严有效解的强对偶定理

本文研究了非凸集值向量优化的严有效解在两种对偶模型的强对偶问题.利用Lagrange对偶和Mond-Weir对偶原理,获得了如下结果：原集值优化问题的严有效解,在一些条件下是对偶问题的强有效解,并且原问题和对偶问题的目标函数值相等;推广了集值优化对偶理论在锥-凸假设下的相应结果.     

Lower bounds and duality in the optimal control of distributed systems

We develop a duality theory for problems of minimization of a convex functional on a convex set and apply this theory to optimal control problems with non-differentiable functional and state as well as control constraints. The dual problem is sometimes found to be simpler than the primal problem. The equivalence of the primal and the dual problem is established for problems in which the functional is strongly convex. A posteriori error are also given for such problems.     

An Inexact Modified Subgradient Algorithm for Primal-Dual Problems via Augmented Lagrangians

We consider a primal optimization problem in a reflexive Banach space and a duality scheme via generalized augmented Lagrangians. For solving the dual problem (in a Hilbert space), we introduce and analyze a new parameterized Inexact Modified Subgradient (IMSg) algorithm. The IMSg generates a primal-dual sequence, and we focus on two simple new choices of the stepsize. We prove that every weak accumulation point of the primal sequence is a primal solution and the dual sequence converges weakly to a dual solution, as long as the dual optimal set is nonempty. Moreover, we establish primal convergence even when the dual optimal set is empty. Our second choice of the stepsize gives rise to a variant of IMSg which has finite termination.     

Average behavior of greedy algorithms for the minimization knapsack problem: General coefficient distributions

For the minimization knapsack problem with Boolean variables, primal and dual greedy algorithms are formally described. Their relations to the corresponding algorithms for the maximization knapsack problem are shown. The average behavior of primal and dual algorithms for the minimization problem is analyzed. It is assumed that the coefficients of the objective function and the constraint are independent identically distributed random variables on [0, 1] with an arbitrary distribution having a density and that the right-hand side d is deterministic and proportional to the number of variables (i.e., d = μn). A condition on μ is found under which the primal and dual greedy algorithms have an asymptotic error of t.