A note on “A LP-based heuristic for a time-constrained routing problem”

In their paper, Avella et al. (2006) investigate a time-constrained routing problem. The core of the proposed solution approach is a large-scale linear program that grows both row- and column-wise when new variables are introduced. Thus, a column-and-row generation algorithm is proposed to solve this linear program optimally, and an optimality condition is presented to terminate the column-and-row generation algorithm. We demonstrate by using Lagrangian duality that this optimality condition is incorrect and may lead to a suboptimal solution at termination.     

A Branch and Bound Method for Solving Integer Separable Concave Problems

A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported.     

多目标半定规划的最优性条件及对偶理论

在不变凸的假设下来讨论多目标半定规划的最优性条件、对偶理论以及非凸半定规划的最优性条件．首先给出了非凸半定规划的一个KKT条件成立的充分必要条件, 并利用此定理证明了其最优性必要条件．其次讨论了多目标半定规划的最优性必要条件、充分条件, 并对其建立Wolfe对偶模型, 证明了弱对偶定理和强对偶定理．     

Sequential Lagrangian Conditions for Convex Programs with Applications to Semidefinite Programming

In this paper it is shown that, in the absence of any regularity condition, sequential Lagrangian optimality conditions as well as a sequential duality results hold for abstract convex programs. The significance of the results is that they yield the standard optimality and duality results for convex programs under a simple closed-cone condition that is much weaker than the well-known constraint qualifications. As an application, a sequential Lagrangian duality, saddle-point conditions, and stability results are derived for convex semidefinite programs.The authors are grateful to the referee and Professor Franco Giannessi for valuable comments and constructive suggestions which have contributed to the final preparation of the paper.     

On duality in linear fractional programming

In this paper, a dual of a given linear fractional program is defined and the weak, direct and converse duality theorems are proved. Both the primal and the dual are linear fractional programs. This duality theory leads to necessary and sufficient conditions for the optimality of a given feasible solution. A unmerical example is presented to illustrate the theory in this connection. The equivalence of Charnes and Cooper dual and Dinkelbach’s parametric dual of a linear fractional program is also established.     

线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

On zero duality gap in nonconvex quadratic programming problems

We present in this paper new sufficient conditions for verifying zero duality gap in nonconvex quadratically/linearly constrained quadratic programs (QP). Based on saddle point condition and conic duality theorem, we first derive a sufficient condition for the zero duality gap between a quadratically constrained QP and its Lagrangian dual or SDP relaxation. We then use a distance measure to characterize the duality gap for nonconvex QP with linear constraints. We show that this distance can be computed via cell enumeration technique in discrete geometry. Finally, we revisit two sufficient optimality conditions in the literature for two classes of nonconvex QPs and show that these conditions actually imply zero duality gap.     

Multiobjective Control Approximation Problems: Duality and Optimality

A general convex multiobjective control approximation problem is considered with respect to duality. The single objectives contain linear functionals and powers of norms as parts, measuring the distance between linear mappings of the control variable and the state variables. Moreover, linear inequality constraints are included. A dual problem is established, and weak and strong duality properties as well as necessary and sufficient optimality conditions are derived. Point-objective location problems and linear vector optimization problems turn out to be special cases of the problem investigated. Therefore, well-known duality results for linear vector optimization are obtained as special cases.     

On interior and convexity conditions,development of dual problems and saddlepoint optimality criteria in abstract mathematical programming

In this paper, duality is studied as a consequence of separating certain derived sets related to optimization problems. The interior and convexity conditions used and two groups of related derived sets are studied and a new interior condition for duality arises quite naturally. Several dual problems are presented and the paper is concluded by presentation of saddlepoint optimality criteria for the problems considered.     

Duality for Algebraic Linear Programming

A duality theory for algebraic linear (integer) programming (ALP) is developed which is of the same importance for linear (integer) programming with linear algebraic objectives as linear programming duality is for classical LP. In particular, optimality criteria for primal, primal-dual, and dual methods are given which generalize feasibility and complementarity criteria of classical LP. Strong duality results are given for special combinatorial problems. Further, the validity and finiteness of a primal simplex method based on a feasibility criterion are proved in the case of nondiscrete variables. In this case a strong duality result is shown.     

Nonlinear Lagrangian Theory for Nonconvex Optimization

The Lagrangian function in the conventional theory for solving constrained optimization problems is a linear combination of the cost and constraint functions. Typically, the optimality conditions based on linear Lagrangian theory are either necessary or sufficient, but not both unless the underlying cost and constraint functions are also convex.We propose a somewhat different approach for solving a nonconvex inequality constrained optimization problem based on a nonlinear Lagrangian function. This leads to optimality conditions which are both sufficient and necessary, without any convexity assumption. Subsequently, under appropriate assumptions, the optimality conditions derived from the new nonlinear Lagrangian approach are used to obtain an equivalent root-finding problem. By appropriately defining a dual optimization problem and an alternative dual problem, we show that zero duality gap will hold always regardless of convexity, contrary to the case of linear Lagrangian duality.     

非凸分式优化问题的最优性充分条件和对偶

通过引入广义弧连通概念,在Rn空间中,研究极大极小非凸分式规划问题的最优性充分条件及其对偶问题.首先获得了极大极小非凸分式规划问题的最优性充分条件;然后建立分式规划问题的一个对偶模型并得到了弱对偶定理,强对偶定理和逆对偶定理.     

Duality of Nonscalarized Multiobjective Linear Programs: Dual Balance,Level Sets,and Dual Clusters of Optimal Vectors

A new concept of duality is proposed for multiobjective linear programs. It is based on a set expansion process for the computation of optimal solutions without scalarization. The duality gap qualifications are investigated; the primal–dual balance set and level set equations are derived. It is demonstrated that the nonscalarized dual problem presents a cluster of optimal dual vectors that corresponds to a unique optimal primal vector. Comparisons are made with linear utility, minmax and minmin scalarizations. Connections to Pareto optimality are studied and relations to sensitivity and parametric programming are discussed. The ideas are illustrated by examples.     

Introduction to duality in optimization theory

A systematic exposition of duality theory is given on what appears to be the optimal level of generality. A condition is offered which implies that the ideal of duality theory is achieved. For the case of linear programming, our approach leads to two novel features. In the first place, primal and dual LP-problems and complementarity conditions are defined canonically, without choosing a matrix form. In the second place, without deriving the explicit form of the dual problem, we show that the following well-known fact implies that the condition mentioned above holds: the polyhedral set property is invariant under linear maps. We give a new quick algorithmic proof of this fact.The author would like to thank Jan Boone for his helpful comments on a preliminary version of this paper.     

First and second order analysis of nonlinear semidefinite programs

In this paper we study nonlinear semidefinite programming problems. Convexity, duality and first-order optimality conditions for such problems are presented. A second-order analysis is also given. Second-order necessary and sufficient optimality conditions are derived. Finally, sensitivity analysis of such programs is discussed.     

Optimality Conditions and Lagrange Duality for Vector Extremum Problems with Set Constraint

The necessary and sufficient optimality conditions for vector extremum problems with set constraint in an ordered linear topological space are given. Finally, Lagrange duality is established.     

Sufficient conditions for optimality for differential inclusions of parabolic type and duality

Sufficient conditions for optimality are derived for partial differential inclusions of parabolic type on the basis of the apparatus of locally conjugate mapping, and duality theorems are proved. The duality theorems proved allow one to conclude that a sufficient condition for an extremum is an extremal relation for the direct and dual problems.      

Conjugate Duality and the Control of Linear Discrete Systems

In this paper we deal with the minimization of a convex function over the solution set of a range inclusion problem determined by a multivalued operator with convex graph. We attach a dual problem to it, provide regularity conditions guaranteeing strong duality and derive for the resulting primal–dual pair necessary and sufficient optimality conditions. We also discuss the existence of optimal solutions for the primal and dual problems by using duality arguments. The theoretical results are applied in the context of the control of linear discrete systems.     

超有效意义下向量集值优化修整的Lagrange乘子型对偶

给出了一类加细的向量集值优化超有效解的最优性条件,由此给出了一种改进的Lagrange乘子型对偶,并建立了对偶的弱定理,正定理及逆定理。