Some duality relationships for the generalized Neyman-Pearson problem

In 1963, Kuhn presented a dual problem to a relatively well-known location problem, variously referred to as the generalized Fermat problem and the Steiner-Weber problem. The purpose of this paper is to point out how Kuhn's results can be adapted to provide a dual to the generalized Neyman-Pearson problem, a problem of fundamental interest in statistics, which has applications in control theory and a number of other areas. The Neyman-Pearson problem, termed the dual problem, is a constrained maximization problem and may be considered to be a calculus-of-variations analog to the bounded-variable problem of linear programming. When the dual problem has equality constraints, the primal problem is an unconstrained minimization problem. Duality results are also obtained for the case where the dual problem has inequality constraints.This work was partially supported by the National Science Foundation, Grant Nos. NSF-GK-1571 and NSF-GK-3038. The authors would like to acknowledge the very useful comments of one of the referees, which led to more direct and general proofs of Properties 2.3 and 2.6.     

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)     

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 the duality between locally optimal tests and optimal experimental designs

Locally unbiased tests with maximal power curvature are determined as the solutions of an optimization problem which turns out to be of dual type as compared to the optimal design problem. In both cases the proper optimization problem is concerned with matrices only, and the transition from the matrix problem to the original variables is a separate second step. This approach provides a novel, statistical interpretation of the dual problem that arises with the optimal design problem.     

Parametric Disjunctive Programming: One-Sided Differentiability of the Value Function

We consider a countable family of one-parameter convex programs and give sufficient conditions for the one-sided differentiability of its optimal value function. The analysis is based on the Borwein dual problem for a family of convex programs (a convex disjunctive program). We give conditions that assure stability of the situation of perfect duality in the Borwein theory.For the reader's convenience, we start with a review of duality results for families of convex programs. A parametric family of dual problems is introduced that contains the dual problems of Balas and Borwein as special cases. In addition, a vector optimization problem is defined as a dual problem. This generalizes a result by Helbig about families of linear programs.     

A hybrid algorithm for the minimum bounding sphere problem

Two primal approaches, the shrinking approach and the dual approach, have been studied for the exact Minimum Bounding Sphere (MBS) problem. In this paper, we present a dual algorithm that uses the shrinking approach to solve subproblems. The experiments show our hybrid algorithm is faster than the dedicated shrinking algorithm and dual algorithm for solving the exact MBS problem in large point sets.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.     

A dual algorithm for the one-machine scheduling problem

A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn ² and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.     

A characterization of a minimax test in the problem of testing two composite hypotheses

We obtain a characterization of a minimax test in the problem of testing two composite hypotheses via a solution of a dual problem. In comparison to previous results, our characterization is valid under much weaker assumptions, which became possible, in particular, due to a modification of a dual problem.     

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.     

On the global optimality of generalized trust region subproblems

Quadratically constrained quadratic programming is an important class of optimization problems. We consider the case with one quadratic constraint. Since both the objective function and its constraint can be neither convex nor concave, it is also known as the ‘generalized trust region subproblem.’ The theory and algorithms for this problem have been well studied under the Slater condition. In this article, we analyse the duality property between the primal problem and its Lagrangian dual problem, and discuss the attainability of the optimal primal solution without the Slater condition. The relations between the Lagrangian dual and semidefinite programming dual is also given.     

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

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

Approximate solution to a time optimal boundary control problem for the wave equation

The paper provides some examples of mutually dual unconstrained optimization problems originating from regularization problems for systems of linear equations and/or inequalities. The solution of each of these mutually dual problems can be found from the solution of the other problem by means of simple formulas. Since mutually dual problems have different dimensions, it is natural to solve the unconstrained optimization problem of the smaller dimension.     

Implementation and analysis of a variant of the dual method for the capacitated transshipment problem

This paper presents a variant of the dual simplex method for the capacitated pure network problem and a computational analysis of this algorithm. This work includes the considerations of different list structures to store the original problem data and the basis and the testing of various procedures to select the leaving basic variable. This study also examines the sensitivity of the implementation to changes in problem parameters. The results show that the algorithm which is presented here is superior to earlier dual implementations.     

Lagrangian relaxation and its application to the unit-commitment-economic-dispatch problem

This study is concerned with the optimal scheduling of an electricitypower system consisting of both hydro and thermal units. UsingLagrangian relaxation, the original (primal) problem may bewritten in a dual formulation; the problem then admits decompositioninto more tractable sub-problems. Furthermore, the primal solutioncan be approximated closely by the dual solution, by using theduality gap as a termination criterion. A heuristic has beenused to construct nearly optimal solutions to the primal problembased on the information provided by the dual problem. Thispaper highlights three main points: improved computational times,the economic significance of the Lagrange multipliers, and theimplicit parallelism of this algorithm.     

Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints

A strongly convex function of simple structure (for example, separable) is minimized under affine constraints. A dual problem is constructed and solved by applying a fast gradient method. The necessary properties of this method are established relying on which, under rather general conditions, the solution of the primal problem can be recovered with the same accuracy as the dual solution from the sequence generated by this method in the dual space of the problem. Although this approach seems natural, some previously unpublished rather subtle results necessary for its rigorous and complete theoretical substantiation in the required generality are presented.     

On the acceleration of the double smoothing technique for unconstrained convex optimization problems

In this article, we investigate the possibilities of accelerating the double smoothing (DS) technique when solving unconstrained nondifferentiable convex optimization problems. This approach relies on the regularization in two steps of the Fenchel dual problem associated with the problem to be solved into an optimization problem having a differentiable strongly convex objective function with Lipschitz continuous gradient. The doubly regularized dual problem is then solved via a fast gradient method. The aim of this article is to show how the properties of the functions in the objective of the primal problem influence the implementation of the DS approach and its rate of convergence. The theoretical results are applied to linear inverse problems by making use of different regularization functionals.     

Using the Dinkelbach-type algorithm to solve the continuous-time linear fractional programming problems

A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

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.