Theorems of the Alternative and Duality

This paper investigates the relations between theorems of the alternative and the minimum norm duality theorem. A typical theorem of the alternative is associated with two systems of linear inequalities and/or equalities, a primal system and a dual one, asserting that either the primal system has a solution, or the dual system has a solution, but never both. On the other hand, the minimum norm duality theorem says that the minimum distance from a given point z to a convex set is equal to the maximum of the distances from z to the hyperplanes separating z and . We consider the theorems of Farkas, Gale, Gordan, and Motzkin, as well as new theorems that characterize the optimality conditions of discrete l ₁-approximation problems and multifacility location problems. It is shown that, with proper choices of , each of these theorems can be recast as a pair of dual problems: a primal steepest descent problem that resembles the original primal system, and a dual least–norm problem that resembles the original dual system. The norm that defines the least-norm problem is the dual norm with respect to that which defines the steepest descent problem. Moreover, let y solve the least norm problem and let r denote the corresponding residual vector. If r=0, which means that z , then y solves the dual system. Otherwise, when r0 and z , any dual vector of r solves both the steepest descent problem and the primal system. In other words, let x solve the steepest descent problem; then, r and x are aligned. These results hold for any norm on . If the norm is smooth and strictly convex, then there are explicit rules for retrieving x from r and vice versa.     

A New and Self-Contained Proof of Borwein’s Norm Duality Theorem

Borwein’s norm duality theorem establishes the equality between the outer (inner) norm of a sublinear mapping and the inner (outer) norm of its adjoint mappings. In this note we provide an extended version of this theorem with a new and self-contained proof relying only on the Hahn-Banach theorem. We also give examples showing that the assumptions of the theorem cannot be relaxed. This author is supported by Grant BES-2003-0188 from FPI Program of MEC (Spain).     

Minimum Distance to the Complement of a Convex Set: Duality Result

The subject of this paper is to study the problem of the minimum distance to the complement of a convex set. Nirenberg has stated a duality theorem treating the minimum norm problem for a convex set. We state a duality result which presents some analogy with the Nirenberg theorem, and we apply this result to polyhedral convex sets. First, we assume that the polyhedral set is expressed as the intersection of some finite collection of m given half-spaces. We show that a global solution is determined by solving m convex programs. If the polyhedral set is expressed as the convex hull of a given finite set of extreme points, we show that a global minimum for a polyhedral norm is obtained by solving a finite number of linear programs.     

On extremum properties of orthogonal quotients matrices

In this paper we explore the extremum properties of orthogonal quotients matrices. The orthogonal quotients equality that we prove expresses the Frobenius norm of a difference between two matrices as a difference between the norms of two matrices. This turns the Eckart-Young minimum norm problem into an equivalent maximum norm problem. The symmetric version of this equality involves traces of matrices, and adds new insight into Ky Fan’s extremum problems. A comparison of the two cases reveals a remarkable similarity between the Eckart-Young theorem and Ky Fan’s maximum principle. Returning to orthogonal quotients matrices we derive “rectangular” extensions of Ky Fan’s extremum principles, which consider maximizing (or minimizing) sums of powers of singular values.     

Metric Distance Function and Profit: Some Duality Results

In this paper, we intend to establish relations between the way efficiency is measured in the literature on efficiency analysis and the notion of distance in topology. To this effect, we are interested particularly in the Hölder norm concept, providing a duality result based upon the profit function. Along this line, we prove that the Luenberger shortage function and the directional distance function of Chambers, Chung, and Färe appear as special cases of some l _p distance (also called Hölder distance), under the assumption that the production set is convex. Under a weaker assumption (convexity of the input correspondence), we derive a duality result based on the cost function, providing several examples in which the functional form of the production set is specified.     

The duality theorem between the t-singular homology and the ws-singular cohomology of orbifolds

In the present paper, we prove that for an n-dimensional compact orbifold with an s-homological orientation, the duality of the ws-singular cohomology group and the t-singular homology group holds. The key tools are “the t-modification of the cap product” for giving the duality homomorphism and “the Convex Suborbifold Theorem” for extending the local duality isomorphism to the global one. The duality theorem proved in the present paper is a naturally required consequence of the preceding works of the authors.     

The distance to strong stability

The notion of “strong stability” has been introduced in a recent paper [12]. This notion is relevant for state-space models described by physical variables and prohibits overshooting trajectories in the state-space transient response for arbitrary initial conditions. Thus, “strong stability” is a stronger notion compared to alternative definitions (e.g. stability in the sense of Lyapunov or asymptotic stability). This paper defines two distance measures to strong stability under absolute (additive) and relative (multiplicative) matrix perturbations, formulated in terms of the spectral and the Frobenius norm. Both symmetric and non-symmetric perturbations are considered. Closed-form or algorithmic solutions to these distance problems are derived and interesting connections are established with various areas in matrix theory, such as the field of values of a matrix, the cone of positive semi-definite matrices and the Lyapunov cone of Hurwitz matrices. The results of the paper are illustrated by numerous computational examples.     

Duality for location problems with unbounded unit balls

Given an optimization problem with a composite of a convex and componentwise increasing function with a convex vector function as objective function, by means of the conjugacy approach based on the perturbation theory, we determine a dual to it. Necessary and sufficient optimality conditions are derived using strong duality. Furthermore, as special case of this problem, we consider a location problem, where the “distances” are measured by gauges of closed convex sets. We prove that the geometric characterization of the set of optimal solutions for this location problem given by Hinojosa and Puerto in a recently published paper can be obtained via the presented dual problem. Finally, the Weber and the minmax location problems with gauges are given as applications.     

Note: continuous-time linear programming problems revisited

This note is aimed to correct the strong duality theorem of previous paper regarding the continuous-time linear programming problems. The argument presented in the previous paper can only be used to prove the case of piecewise continuous functions in which the discontinuities are the left-continuities.     

一类非光滑规划问题的最优性和对偶

研究一类非光滑多目标规划问题,给出了该规划问题的三个最优性充分条件.同时,研究了该问题的对偶问题,给出了相应的弱对偶定理和强对偶定理.     

对偶定理在三角教与学中的应用

数理逻辑中的对偶定理在计算中已经有广泛的应用，笔用对偶定理作为指导思想在三角证明题的构造，在条件等式的证明和三角化简求值中都有广泛的应用。可见对定理可以开拓研究领域，还可以使研究的三角题扩大一倍，更可以创造更多的三角题。     

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 destination optimality in asymmetric distance Fermat-Weber problems

This paper introduces skewed norms, i.e. norms perturbed by a linear function, which are useful for modelling asymmetric distance measures. The Fermat-Weber problem with mixed skewed norms is then considered. Using subdifferential calculus we derive exact conditions for a destination point to be optimal, thereby correcting and completing some recent work on asymmetric distance location problems. Finally the classical dominance theorem is generalized to Fermat-Weber problems with a fixed skewed norm.     

Continuous-time linear programming problems revisited: A perturbation approach

The class of continuous-time linear programming problems under the assumption that the constraints are satisfied almost everywhere in the time interval [0,?T]?is taken into account in this article. Under this assumption, its corresponding discretized problems cannot be formulated by equally dividing the time interval [0,?T]?as subintervals of [0,?T]?. In this article, we also introduce the perturbed continuous-time linear programming problems to prove the strong duality theorem when the constraints are assumed to be satisfied a.e. in [0,?T]?.     

On the solution set of convex problems and its numerical application

The solution set of a convex problem is enough interested. In this paper we have a discussion to determine it. The conditions and proofs in this note essentially differs from the previous well-known works. We also have a new result determining the solution of minimum norm for quadratic problems.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

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.     

Meta-data envelopment analysis: Finding a direction towards marginal profit maximization

This paper discusses a new meta-DEA approach to solve the problem of choosing direction vectors when estimating the directional distance function. The proposed model emphasizes finding the “direction” for productivity improvement rather than estimating the “score” of efficiency; focusing on “planning” over “evaluation”. In fact, the direction towards marginal profit maximization implies a step-by-step improvement and “wait-and-see” decision process, which is more consistent with the practical decision-making process. An empirical study of U.S. coal-fired power plants operating in 2011 validates the proposed model. The results show that the efficiency measure using the proposed direction is consistent with all other indices with the exception of the direction towards the profit-maximized benchmark. We conclude that the marginal profit maximization is a useful guide for determining direction in the directional distance function.     

Strong duality in robust semi-definite linear programming under data uncertainty

This article develops the deterministic approach to duality for semi-definite linear programming problems in the face of data uncertainty. We establish strong duality between the robust counterpart of an uncertain semi-definite linear programming model problem and the optimistic counterpart of its uncertain dual. We prove that strong duality between the deterministic counterparts holds under a characteristic cone condition. We also show that the characteristic cone condition is also necessary for the validity of strong duality for every linear objective function of the original model problem. In addition, we derive that a robust Slater condition alone ensures strong duality for uncertain semi-definite linear programs under spectral norm uncertainty and show, in this case, that the optimistic counterpart is also computationally tractable.     

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.