Convexification, Concavification and Monotonization in Global Optimization

We show in this paper that via certain convexification, concavification and monotonization schemes a nonconvex optimization problem over a simplex can be always converted into an equivalent better-structured nonconvex optimization problem, e.g., a concave optimization problem or a D.C. programming problem, thus facilitating the search of a global optimum by using the existing methods in concave minimization and D.C. programming. We first prove that a monotone optimization problem (with a monotone objective function and monotone constraints) can be transformed into a concave minimization problem over a convex set or a D.C. programming problem via pth power transformation. We then prove that a class of nonconvex minimization problems can be always reduced to a monotone optimization problem, thus a concave minimization problem or a D.C. programming problem.     

Concave solutions of a general self-similar boundary layer problem for power-law fluids

In this paper, we give a rigorous mathematical analysis for a third order nonlinear boundary value problem. The boundary value problem can be applied to steady free convection around a vertical impermeable flat plate in a fluid-saturated porous medium, or steady flow of a power-law fluid induced by impermeable stretching walls in the frame of boundary layer approximation. We establish the uniqueness, existence and nonexistence of (normal) concave solutions or generalized concave solutions to the problem, and obtain some results about boundedness and asymptotic behavior of the (normal) concave solution or the generalized concave solution.     

Allocating procurement to capacitated suppliers with concave quantity discounts

We consider a procurement problem where suppliers offer concave quantity discounts. The resulting continuous knapsack problem involves the minimization of a sum of separable concave functions. We identify polynomially solvable special cases of this NP-hard problem, and provide a fully polynomial-time approximation scheme for the general problem.     

一些类型的数学规划问题的全局最优解

本文对严格单调函数给出了几个凸化和凹化的方法，利用这些方法可将一个严格单调的规划问题转化为一个等价的标准D．C．规划或凹极小问题．本文还对只有一个严格单调的约束的非单调规划问题给出了目标函数的一个凸化和凹化方法，利用这些方法可将只有一个严格单调约束的非单调规划问题转化为一个等价的凹极小问题．再利用已有的关于D．C．规划和凹极小的算法，可以求得原问题的全局最优解．     

一些约束规划问题的近似全局最优解

首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题．最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解．     

Unconstrained 0–1 nonlinear programming: A nondifferentiable approach

The purpose of this paper is to give new formulations for the unconstrained 0–1 nonlinear problem. The unconstrained 0–1 nonlinear problem is reduced to nonlinear continuous problems where the objective functions are piecewise linear. In the first formulation, the objective function is a difference of two convex functions while the other formulations lead to concave problems. It is shown that the concave problems we obtain have fewer integer local minima than has the classical concave formulation of the 0–1 unconstrained 0–1 nonlinear problem.     

Valid inequalities for concave piecewise linear regression

We consider the problem of fitting a concave piecewise linear function to multivariate data using the Least Absolute Deviation objective. We propose new valid inequalities for the problem using the properties of concave functions. Results with univariate data show that the proposed valid inequalities improve the root relaxation lower bound, permitting significant improvements in solution time.     

Linear Programs With an Additional Separable Concave Constraint

In this paper, we develop two algorithms for globally optimizing a special class of linear programs with an additional concave constraint. We assume that the concave constraint is defined by a separable concave function. Exploiting this special structure, we apply Falk-Soland's branch-and-bound algorithm for concave minimization in both direct and indirect manners. In the direct application, we solve the problem alternating local search and branch-and-bound. In the indirect application, we carry out the bounding operation using a parametric right-hand-side simplex algorithm.     

On the solution of concave knapsack problems

We consider a version of the knapsack problem which gives rise to a separable concave minimization problem subject to bounds on the variables and one equality constraint. We characterize strict local miniimizers of concave minimization problems subject to linear constraints, and use this characterization to show that although the problem of determining a global minimizer of the concave knapsack problem is NP-hard, it is possible to determine a local minimizer of this problem with at most O(n logn) operations and 1+[logn] evaluations of the function. If the function is quadratic this algorithm requires at most O(n logn) operations.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.Work supported in part by a Fannie and John Hertz Foundation graduate fellowship.     

Maximization of the Choquet integral over a convex set and its application to resource allocation problems

We study the problem of the Choquet integral maximization over a convex set. The problem is shown to be generally non-convex (and non-differentiable). We analyze the problem structure, and propose local and global search algorithms. The special case when the problem becomes concave is analyzed separately. For the non-convex case we propose a decomposition scheme which allows to reduce a non-convex problem to several concave ones. Decomposition is performed by finding the coarsest partition of a capacity into disjunction of totally monotone measures. We discuss its effectiveness and prove that the scheme is optimal for 2-additive capacities. An application of the developed methods to resource allocation problems concludes the article.     

Optimal Financial Portfolios

The classes of reward‐risk optimization problems that arise from different choices of reward and risk measures are considered. In certain examples the generic problem reduces to linear or quadratic programming problems. An algorithm based on a sequence of convex feasibility problems is given for the general quasi‐concave ratio problem. Reward‐risk ratios that are appropriate in particular for non‐normal assets return distributions and are not quasi‐concave are also considered.     

An exact algorithm for graph partitioning

An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes.     

On Optimization over the Efficient Set in Linear Multicriteria Programming

The efficient set of a linear multicriteria programming problem can be represented by a reverse convex constraint of the form g(z)≤0, where g is a concave function. Consequently, the problem of optimizing some real function over the efficient set belongs to an important problem class of global optimization called reverse convex programming. Since the concave function used in the literature is only defined on some set containing the feasible set of the underlying multicriteria programming problem, most global optimization techniques for handling this kind of reverse convex constraint cannot be applied. The main purpose of our article is to present a method for overcoming this disadvantage. We construct a concave function which is finitely defined on the whole space and can be considered as an extension of the existing function. Different forms of the linear multicriteria programming problem are discussed, including the minimum maximal flow problem as an example. The research was partly done while the third author was visiting the Department of Mathematics, University of Trier with the support by the Alexander von Humboldt Foundation. He thanks the university as well as the foundation.     

A numerical method for a class of continuous concave programming problems

The problem under consideration consists in maximizing a separable concave objective functional on a class of non-negative Lebesgue integrable functions satisfying a system of linear constraints. The problem is approximated by two sequences of concave separable programming problems with linear constraints. The convergence of the sequences of optimum values of these problems is investigated in the general case and the convergence of the sequences of optimum solutions in a special case. A numerical example is given.     

Resource Allocation with Wobbly Functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximisation version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with functions that are not necessarily concave is difficult.In this article, we focus on a large class of problem instances, with objective functions that are close to a concave function or some other smooth function, but with small irregularities in their shape. It is described that these properties are important in many practical situations.The irregularities make it hard or impossible to use known, efficient resource allocation techniques. We show that, for this class of functions the optimal solution can be computed efficiently. We support our claims by experimental evidence. Our experiments show that our algorithm in hard and practically relevant cases runs up to 40–60 times faster than the standard method.     

New results on the equivalence between zero-one programming and continuous concave programming

In this work, we study continuous reformulations of zero-one concave programming problems. We introduce new concave penalty functions and we prove, using general equivalence results here derived, that the obtained continuous problems are equivalent to the original combinatorial problem.     

Some results on the strength of relaxations of multilinear functions

We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term independently. We show that for a multilinear function having a single product term, this approach yields the convex and concave envelopes if the bounds on all variables are symmetric around zero. We then review and extend some results on conditions when the concave envelope of a multilinear function can be written as a sum of concave envelopes of its individual terms. Finally, for bilinear functions we prove that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is always within a constant of the difference between the concave and convex envelopes. These results, along with numerical examples we provide, give insight into how to construct strong relaxations of multilinear functions.     

关于凹函数性质的探讨

从凹函数的一个问题出发,给出了该问题的反例以及问题结论成立的充要条件和充分条件.     

A note on the solution of bilinear programming problems by reduction to concave minimization

We present a new algorithm for solving the bilinear programming problem by reduction to concave minimization. This algorithm is finite, does not assume the boundedness of the constraint set, and uses an efficient procedure for checking whether a concave function is bounded below on a given halfline. Some preliminary computational experience with a computer code for implementing the algorithm on a microcomputer is also reported.     

Classifying convex extremum problems over linear topologies having separation properties

It is shown that any convex or concave extremum problem possesses a subsidiary extremum problem which has certain homogeneous properties. Analogous to the given problem, the “homogenized” extremum problem seeks the minimum of a convex function or the maximum of a concave function over a convex domain. By using homogenized extremum problems, new relationships are developed between any given convex extremum problem (P) and a concave extremum problem (P¹) (also having a convex domain), called the “dual” problem of (P). This is achieved by combining all possibilities in tabular form of (1) the values of the extremum functions and (2) the nature of the convex domains including perturbations of all problems (P), (P¹), and each of their respective homogenized extremum problems.This detailed and refined classification is contrasted to the relationships obtainable by combining only the possible values of the extremum functions of the problems (P) and (P¹) and the possible limiting values of these functions stemming from perturbations of the convex constraint domains of (P) and (P¹), respectively.The extremum problems in this paper and classification results are set forth in real topologically paired vector spaces having the Hahn-Banach separation property.