Notes on L-/M-convex functions and the separation theorems

The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis. Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000     

Some characterizations of duality for DC optimization with composite functions

In this paper, by virtue of the epigraph technique, we first introduce some new regularity conditions and then obtain some complete characterizations of the Fenchel–Lagrange duality and the stable Fenchel–Lagrange duality for a new class of DC optimization involving a composite function. Moreover, we apply the strong and stable strong duality results to obtain some extended (stable) Farkas lemmas and (stable) alternative type theorems for this DC optimization problem. As applications, we obtain the corresponding results for a composed convex optimization problem, a DC optimization problem, and a convex optimization problem with a linear operator, respectively.     

熵正则化方法与指数(乘子)罚函数法之间的关系

由于极大极小问题在许多科学与工程中有着重要应用,特别是形如max的函数频繁地出现在各类数值分析和优化问题中,因此对于求解该类问题的算法研究长久不衰,这些算法一般分为两大类：一类是直接法,其算法设计仅以有效地求解原问题（P）为目的;另一类是间接法,其算法以找一个能够替代不可微max函数φ（x）的光滑函数为目的,故这类算法被称为光滑化方法,文[1,2]中的熵正则化方法就属于光滑化方法范畴。     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

Stable strong Fenchel and Lagrange duality for evenly convex optimization problems

By means of a conjugation scheme based on generalized convex conjugation theory instead of Fenchel conjugation, we build an alternative dual problem, using the perturbational approach, for a general optimization one defined on a separated locally convex topological space. Conditions guaranteeing strong duality for primal problems which are perturbed by continuous linear functionals and their respective dual problems, which is named stable strong duality, are established. In these conditions, the fact that the perturbation function is evenly convex will play a fundamental role. Stable strong duality will also be studied in particular for Fenchel and Lagrange primal–dual problems, obtaining a characterization for Fenchel case.     

Extended Farkas’s Lemmas and Strong Dualities for Conic Programming Involving Composite Functions

The paper is devoted to the study of a new class of conic constrained optimization problems with objectives given as differences of a composite function and a convex function. We first introduce some new notions of constraint qualifications in terms of the epigraphs of the conjugates of these functions. Under the new constraint qualifications, we provide necessary and sufficient conditions for several versions of Farkas lemmas to hold. Similarly, we provide characterizations for conic constrained optimization problems to have the strong or stable strong dualities such as Lagrange, Fenchel–Lagrange or Toland–Fenchel–Lagrange duality.     

Vector and matrix apportionment problems and separable convex integer optimization

The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.     

A closedness condition and its applications to DC programs with convex constraints

This paper concerns a closedness condition called (CC) involving a convex function and a convex constrained system. This type of condition has played an important role in the study of convex optimization problems. Our aim is to establish several characterizations of this condition and to apply them to study problems of minimizing a DC function under a cone-convex constraint and a set constraint. First, we establish several so-called ‘Toland–Fenchel–Lagrange’ duality theorems. As consequences, various versions of generalized Farkas lemmas in dual forms for systems involving convex and DC functions are derived. Then, we establish optimality conditions for DC problem under convex constraints. Optimality conditions for convex problems and problems of maximizing a convex function under convex constraints are given as well. Most of the results are established under the (CC) condition. This article serves as a link between several corresponding known ones published recently for DC programs and for convex programs.     

Optimal Potentials for Problems with Changing Sign Data

The main purpose of this paper is to study the duality and penalty method for a constrained nonconvex vector optimization problem. Following along with the image space analysis, a Lagrange-type duality for a constrained nonconvex vector optimization problem is proposed by virtue of the class of vector-valued regular weak separation functions in the image space. Simultaneously, some equivalent characterizations to the zero duality gap property are established including the Lagrange multiplier, the Lagrange saddle point and the regular separation. Moreover, an exact penalization is also obtained by means of a local image regularity condition and a class of particular regular weak separation functions in the image space.     

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization

Bisubmodular functions are a natural “directed”, or “signed”, extension of submodular functions with several applications. Recently Fujishige and Iwata showed how to extend the Iwata, Fleischer, and Fujishige (IFF) algorithm for submodular function minimization (SFM) to bisubmodular function minimization (BSFM). However, they were able to extend only the weakly polynomial version of IFF to BSFM. Here we investigate the difficulty that prevented them from also extending the strongly polynomial version of IFF to BSFM, and we show a way around the difficulty. This new method gives a somewhat simpler strongly polynomial SFM algorithm, as well as the first combinatorial strongly polynomial algorithm for BSFM. This further leads to extending Iwata’s fully combinatorial version of IFF to BSFM. The research of S. T. McCormick was supported by an NSERC Operating Grant. The research of S. Fujishige was supported by a Grant-in-Aid of the Ministry of Education, Culture, Science and Technology of Japan.     

A generalized duality and applications

The aim of this paper is to present a nonconvex duality with a zero gap and its connection with convex duality. Since a convex program can be regarded as a particular case of convex maximization over a convex set, a nonconvex duality can be regarded as a generalization of convex duality. The generalized duality can be obtained on the basis of convex duality and minimax theorems. The duality with a zero gap can be extended to a more general nonconvex problems such as a quasiconvex maximization over a general nonconvex set or a general minimization over the complement of a convex set. Several applications are given.On leave from the Institute of Mathematics, Hanoi, Vietnam.     

一类二层凸规划的对偶二层规划

本文讨论上层目标函数以下层子系统目标函数的最优值作为反馈的一类二层凸规划的对偶规划问题 ,在构成函数满足凸连续可微等条件的假设下 ,建立了二层凸规划的 Lagrange对偶二层规划 ,并证明了基本对偶定理 .     

Duality Theorems for Separable Convex Programming Without Qualifications

In the research of mathematical programming, duality theorems are essential and important elements. Recently, Lagrange duality theorems for separable convex programming have been studied. Tseng proves that there is no duality gap in Lagrange duality for separable convex programming without any qualifications. In other words, although the infimum value of the primal problem equals to the supremum value of the Lagrange dual problem, Lagrange multiplier does not always exist. Jeyakumar and Li prove that Lagrange multiplier always exists without any qualifications for separable sublinear programming. Furthermore, Jeyakumar and Li introduce a necessary and sufficient constraint qualification for Lagrange duality theorem for separable convex programming. However, separable convex constraints do not always satisfy the constraint qualification, that is, Lagrange duality does not always hold for separable convex programming. In this paper, we study duality theorems for separable convex programming without any qualifications. We show that a separable convex inequality system always satisfies the closed cone constraint qualification for quasiconvex programming and investigate a Lagrange-type duality theorem for separable convex programming. In addition, we introduce a duality theorem and a necessary and sufficient optimality condition for a separable convex programming problem, whose constraints do not satisfy the Slater condition.     

Stable and Total Fenchel Duality for Composed Convex Optimization Problems

In this paper, we consider the composed convex optimization problem which consists in minimizing the sum of a convex function and a convex composite function. By using the properties of the epigraph of the conjugate functions and the subdifferentials of convex functions, we give some new constraint qualifications which completely characterize the strong Fenchel duality and the total Fenchel duality for composed convex optimiztion problem in real locally convex Hausdorff topological vector spaces.     

Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions

We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart of the Karush-Kuhn-Tucker condition for convex programs. This work is supported by the Alexander von Humboldt fellowship (1982/83), West Germany.     

Lagrange duality in canonical DC programming

We study Lagrange duality theorems for canonical DC programming problems. We show two types Lagrange duality results by using a decomposition method to infinite convex programming problems and by using a previous result by Lemaire (1998)  [6]. Also we observe these constraint qualifications for the duality theorems.     

Equivalence between a generalized fenchel duality theorem and a saddle-point theorem for fractional programs

The convex case of a fractional program is considered. By the aid of a duality theory for mathematical programming involving a maximum and minimum operator, and by defining new operators, we obtain three equivalent duality theorems for three pairs of primal-dual programs. The second and the third one are the saddle-point theorem and a generalized Fenchel duality theorem, respectively.     

Proximity theorems of discrete convex functions

A proximity theorem is a statement that, given an optimization problem and its relaxation, an optimal solution to the original problem exists in a certain neighborhood of a solution to the relaxation. Proximity theorems have been used successfully, for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for L-convex and M-convex functions, this paper establishes proximity theorems for larger classes of discrete convex functions, L₂-convex functions and M₂-convex functions, that are relevant to the polymatroid intersection problem and the submodular flow problem.Mathematics Subject Classification (2000): 90C27, 05B35     

On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.