Extension of M-Convexity and L-Convexity to Polyhedral Convex Functions

The concepts of M-convex and L-convex functions were proposed by Murota in 1996 as two mutually conjugate classes of discrete functions over integer lattice points. M/L-convex functions are deeply connected with the well-solvability in nonlinear combinatorial optimization with integer variables. In this paper, we extend the concept of M-convexity and L-convexity to polyhedral convex functions, aiming at clarifying the well-behaved structure in well-solved nonlinear combinatorial optimization problems in real variables. The extended M/L-convexity often appears in nonlinear combinatorial optimization problems with piecewise-linear convex cost. We investigate the structure of polyhedral M-convex and L-convex functions from the dual viewpoint of analysis and combinatorics and provide some properties and characterizations. It is also shown that polyhedral M/L-convex functions have nice conjugacy relationships.     

Barycentric coordinates for convex sets

In this paper we provide an extension of barycentric coordinates from simplices to arbitrary convex sets. Barycentric coordinates over convex 2D polygons have found numerous applications in various fields as they allow smooth interpolation of data located on vertices. However, no explicit formulation valid for arbitrary convex polytopes has been proposed to extend this interpolation in higher dimensions. Moreover, there has been no attempt to extend these functions into the continuous domain, where barycentric coordinates are related to Green’s functions and construct functions that satisfy a boundary value problem. First, we review the properties and construction of barycentric coordinates in the discrete domain for convex polytopes. Next, we show how these concepts extend into the continuous domain to yield barycentric coordinates for continuous functions. We then provide a proof that our functions satisfy all the desirable properties of barycentric coordinates in arbitrary dimensions. Finally, we provide an example of constructing such barycentric functions over regions bounded by parametric curves and show how they can be used to perform freeform deformations.      

积分凸性及其应用

该文在Banach空间中通过向量值函数的Bochner积分引进集合与泛函的积分凸性以及集合的积分端点等概念. 文章主要证明有限维凸集、开凸集和闭凸集均是积分凸集，下半连续凸泛函与开凸集上的上半连续凸泛函均是积分凸的, 非空紧集具有积分端点, 对紧凸集来说其积分端点集与端点集一致, 最后给出积分凸性在最优化理论方面的两个应用.     

On the second conjugate of several convex functions in general normed vector spaces

When dealing with convex functions defined on a normed vector space X the biconjugate is usually considered with respect to the dual system (X, X ^*), that is, as a function defined on the initial space X. However, it is of interest to consider also the biconjugate as a function defined on the bidual X ^**. It is the aim of this note to calculate the biconjugate of the functions obtained by several operations which preserve convexity. In particular we recover the result of Fitzpatrick and Simons on the biconjugate of the maximum of two convex functions with a much simpler proof.      

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     

αBB: A global optimization method for general constrained nonconvex problems

A branch and bound global optimization method,BB, for general continuous optimization problems involving nonconvexities in the objective function and/or constraints is presented. The nonconvexities are categorized as being either of special structure or generic. A convex relaxation of the original nonconvex problem is obtained by (i) replacing all nonconvex terms of special structure (i.e. bilinear, fractional, signomial) with customized tight convex lower bounding functions and (ii) by utilizing the parameter as defined in [17] to underestimate nonconvex terms of generic structure. The proposed branch and bound type algorithm attains finite-convergence to the global minimum through the successive subdivision of the original region and the subsequent solution of a series of nonlinear convex minimization problems. The global optimization method,BB, is implemented in C and tested on a variety of example problems.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

Duality gap in convex programming

In this paper, we consider general convex programming problems and give a sufficient condition for the equality of the infimum of the original problem and the supremum of its ordinary dual. This condition may be seen as a continuity assumption on the constraint sets (i.e. on the sublevel sets of the constraint function) under linear perturbation. It allows us to generalize as well as treat previous results in a unified framework. Our main result is in fact based on a quite general constraint qualification result for quasiconvex programs involving a convex objective function proven in the setting of a real normed vector space.Mathematics Subject Classification (2000):90C25, 90C26, 90C30, 90C31     

A general construction of barycentric coordinates over convex polygons

Barycentric coordinates are unique for triangles, but there are many possible generalizations to convex polygons. In this paper we derive sharp upper and lower bounds on all barycentric coordinates over convex polygons and use them to show that all such coordinates have the same continuous extension to the boundary. We then present a general approach for constructing such coordinates and use it to show that the Wachspress, mean value, and discrete harmonic coordinates all belong to a unifying one-parameter family of smooth three-point coordinates. We show that the only members of this family that are positive, and therefore barycentric, are the Wachspress and mean value ones. However, our general approach allows us to construct several sets of smooth five-point coordinates, which are positive and therefore barycentric. Dedicated to Charles A. Micchelli on his 60th Birthday Mathematics subject classifications (2000) 26C15, 65D05.     

Complexity of convex optimization using geometry-based measures and a reference point

Our concern lies in solving the following convex optimization problem:where P is a closed convex subset of the n-dimensional vector space X. We bound the complexity of computing an almost-optimal solution of G_P in terms of natural geometry-based measures of the feasible region and the level-set of almost-optimal solutions, relative to a given reference point x^r that might be close to the feasible region and / or the almost-optimal level set. This contrasts with other complexity bounds for convex optimization that rely on data-based condition numbers or algebraic measures, and that do not take into account any a priori reference point information. Mathematics Subject Classification (2000):90C, 90C05, 90C60This research has been partially supported through the Singapore-MIT Alliance. Portions of this research were undertaken when the author was a Visiting Scientist at Delft University of Technology.Received: 1, October 2001     

Cores of games with restricted cooperation

Games with restricted cooperation are cooperativeN-person games with sidepayments, where the collection of feasible coalitions need not comprise all subsets of players and thus is restricted. We study balanced and completely balanced games in this context and derive the corresponding core theorems from a sandwich theorem for set functions within the setting of linear programming. In particular, we discuss general convex games, which Edmonds and Giles (1977) have shown to be of particular importance also in combinatorial optimization.

---

Zusammenfassung Spiele mit beschränkter Kooperation sind kooperativeN-Personenspiele mit Nebenzahlungen, wobei nicht jede Teilmenge von Spielern zulässig zu sein braucht. In diesem Sinn sind die Kooperationsmöglichkeiten beschränkt. Balancierte und vollständig balancierte Spiele werden in diesem Zusammenhang untersucht. Die entsprechenden Sätze über die Existenz von Kernen werden von einem Sandwichsatz über Mengenfunktionen im Rahmen der linearen Programmierung abgeleitet. Insbesondere werden allgemeine konvexe Spiele diskutiert, deren Bedeutung auch für die kombinatorische Optimierung Edmonds and Giles (1977) aufgezeigt haben.

     

E-Convex Sets, E-Convex Functions, and E-Convex Programming

A class of sets and a class of functions called E-convex sets and E-convex functions are introduced by relaxing the definitions of convex sets and convex functions. This kind of generalized convexity is based on the effect of an operator E on the sets and domain of definition of the functions. The optimality results for E-convex programming problems are established.     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

Game representations of classes of piecewise definable functions

We present a general way of defining various reduction games on ω which “represent” corresponding topologically defined classes of functions. In particular, we will show how to construct games for piecewise defined functions, for functions which are pointwise limit of certain sequences of functions and for Γ ‐measurable functions. These games turn out to be useful as a combinatorial tool for the study of general reducibilities for subsets of the Baire space [10] (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A general approach for studying duality in multiobjective optimization

A general duality framework in convex multiobjective optimization is established using the scalarization with K-strongly increasing functions and the conjugate duality for composed convex cone-constrained optimization problems. Other scalarizations used in the literature arise as particular cases and the general duality is specialized for some of them, namely linear scalarization, maximum (-linear) scalarization, set scalarization, (semi)norm scalarization and quadratic scalarization.      

Sufficient global optimality conditions for weakly convex minimization problems

In this paper, we present sufficient global optimality conditions for weakly convex minimization problems using abstract convex analysis theory. By introducing (L,X)-subdifferentials of weakly convex functions using a class of quadratic functions, we first obtain some sufficient conditions for global optimization problems with weakly convex objective functions and weakly convex inequality and equality constraints. Some sufficient optimality conditions for problems with additional box constraints and bivalent constraints are then derived.      

On the relative extrema of a linear combination of elementary symmetric functions

We determine where a linear combination of elementary symmetric functions attains as maximum and minimum over a certain convex set in Rⁿ . We also show that an inequality for elementary symmetric functions proposed by S. Pierce is true.     

On Extensions of the Frank-Wolfe Theorems

In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.     

Conical Partition Algorithm for Maximizing the Sum of dc Ratios

The following problem is considered in this paper: 0, j = 1,\ldots,m,$$" align="middle" border="0"> are d.c. (difference of convex) functions over a convex compact set D in R^n. Specifically, it is reformulated into the problem of maximizing a linear objective function over a feasible region defined by multiple reverse convex functions. Several favorable properties are developed and a branch-and-bound algorithm based on the conical partition and the outer approximation scheme is presented. Preliminary results of numerical experiments are reported on the efficiency of the proposed algorithm.AMS Subject Classifications: 90C32, 90C30, 65K05.The authors were partially supported by a Grant-in-Aid (Yang Dai: C-13650444; Jianming Shi and Shouyang Wang: C-14550405) of the Ministry of Education, Science, Sports and Culture of Japan.