Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints

A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed convex polytopes contains the feasible region. No geometric tolerance parameters are required.Research supported by National Science Foundation Grant ENG 76-12250     

Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization,reverse convex constraints,DC-programming,and Lipschitzian optimization

A crucial problem for many global optimization methods is how to handle partition sets whose feasibility is not known. This problem is solved for broad classes of feasible sets including convex sets, sets defined by finitely many convex and reverse convex constraints, and sets defined by Lipschitzian inequalities. Moreover, a fairly general theory of bounding is presented and applied to concave objective functions, to functions representable as differences of two convex functions, and to Lipschitzian functions. The resulting algorithms allow one to solve any global optimization problem whose objective function is of one of these forms and whose feasible set belongs to one of the above classes. In this way, several new fields of optimization are opened to the application of global methods.     

On the construction of test problems for concave minimization algorithms

We construct some classes of test problems of minimizing a concave or, more general, quasiconcave function over a polyhedral set. These test problems fulfil the general requirement that they have a global solution at a known point which is suitably chosen on the boundary of the feasible set.     

On the theory of Lagrangian duality

It is shown that a general Lagrangian duality theory for constrained extremum problems can be drawn from a separation scheme in the Image Space, namely in the space where the functions of the given problem run.     

Conical algorithm for the global minimization of linearly constrained decomposable concave minimization problems

In this paper, we are concerned with the linearly constrained global minimization of the sum of a concave function defined on ap-dimensional space and a linear function defined on aq-dimensional space, whereq may be much larger thanp. It is shown that a conical algorithm can be applied in a space of dimensionp + 1 that involves only linear programming subproblems in a space of dimensionp +q + 1. Some computational results are given.This research was accomplished while the second author was a Fellow of the Alexander von Humboldt Foundation, University of Trier, Trier, Germany.     

Vector optimization and generalized Lagrangian duality

In this paper, foundations of a new approach for solving vector optimization problems are introduced. Generalized Lagrangian duality, related for the first time with vector optimization, provides new scalarization techniques and allows for the generation of efficient solutions for problems which are not required to satisfy any convexity assumptions.     

Conditions for boundedness in concave programming under reverse convex and convex constraints

In this paper, we are concerned with the problem of boundedness in the constrained global maximization of a convex function. In particular, we present necessary and sufficient conditions for boundedness of a feasible region defined by reverse convex constraints and we establish sufficient and necessary conditions for existence of an upper bound for a convex objective function defined over the system of concave inequality constraints. We also address the problem of boundedness in the global maximization problem when a feasible region is convex and unbounded.     

A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization

Based on a review of existing algorithms, a general branch-and-bound concept in global optimization is presented. A sufficient and necessary convergence condition is established, and a broad class of realizations is derived that include existing and several new approaches for concave minimization problems.     

Maximum likelihood estimation via duality for cell probabilities subject to convex and log-convex constraints

This article proposes a method for fitting models subject to a convex and log-convex constraint on the probability vector of a product multinomial （binomial） distribution. We present an iterative algorithm for finding the restricted maximum likelihood estimates （MLEs） of the probability vector and show that the algorithm converges to the true solution. Some examples are discussed to illustrate the method.     

A finite concave minimization algorithm using branch and bound and neighbor generation

In this article we present a new finite algorithm for globally minimizing a concave function over a compact polyhedron. The algorithm combines a branch and bound search with a new process called neighbor generation. It is guaranteed to find an exact, extreme point optimal solution, does not require the objective function to be separable or even analytically defined, requires no nonlinear computations, and requires no determinations of convex envelopes or underestimating functions. Linear programs are solved in the branch and bound search which do not grow in size and differ from one another in only one column of data. Some preliminary computational experience is also presented.     

The Newton Bracketing method for the minimization of convex functions subject to affine constraints

The Newton Bracketing method [Y. Levin, A. Ben-Israel, The Newton Bracketing method for convex minimization, Comput. Optimiz. Appl. 21 (2002) 213-229] for the minimization of convex functions f:Rⁿ→R is extended to affinely constrained convex minimization problems. The results are illustrated for affinely constrained Fermat-Weber location problems.     

Subdivision of simplices relative to a cutting plane and finite concave minimization

In this article, our primary concern is the classical problem of minimizing globally a concave function over a compact polyhedron (Problem (P)). We present a new simplicial branch and bound approach, which combines triangulations of intersections of simplices with halfspaces and ideas from outer approximation in such a way, that a class of finite algorithms for solving (P) results. For arbitrary compact convex feasible sets one obtains a not necessarily finite but convergent algorithm. Theoretical investigations include determination of the number of simplices in each applied triangulation step and bounds on the number of iterations in the resulting algorithms. Preliminary numerical results are given, and additional applications are sketched.     

A simplicial branch-and-bound algorithm conscious of special structures in concave minimization problems

In this paper, we develop a simplicial branch-and-bound algorithm for generating globally optimal solutions to concave minimization problems with low rank nonconvex structures. We propose to remove all additional constraints imposed on the usual linear programming relaxed problem. Therefore, in each bounding operation, we solve a linear programming problem whose constraints are exactly the same as the target problem. Although the lower bound worsens as a natural consequence, we offset this weakness by using an inexpensive bound tightening procedure based on Lagrangian relaxation. After giving a proof of the convergence, we report a numerical comparison with existing algorithms. T. Kuno was partially supported by the Grand-in-Aid for Scientific Research (C) 17560050 from the Japan Society for the Promotion of Sciences.     

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.     

Global minimization of a generalized convex multiplicative function

This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.     

Linearly constrained global minimization of functions with concave minorants

In this note, we show how a recent approach for solving linearly constrained multivariate Lipschitz optimization problems and corresponding systems of inequalities can be generalized to solve optimization problems where the objective function is only assumed to possess a concave minorant at each point. This class of functions includes not only Lipschitz functions and some generalizations, such as certain -convex functions and Hölder functions with exponent greater than one, but also all functions which can be expressed as differences of two convex functions (d.c. functions). Thus, in particular, a new approach is obtained for the important problem of minimizing a d.c. function over a polytope.     

Quasi-relative interior-type constraint qualifications ensuring strong Lagrange duality for optimization problems with cone and affine constraints

In this article we provide weak sufficient strong duality conditions for a convex optimization problem with cone and affine constraints, stated in infinite dimensional spaces, and its Lagrange dual problem. Our results are given by using the notions of quasi-relative interior and quasi-interior for convex sets. The main strong duality theorem is accompanied by several stronger, yet easier to verify in practice, versions of it. As exemplification we treat a problem which is inspired from network equilibrium. Our results come as corrections and improvements to Daniele and Giuffré (2007) [9].     

Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint

In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems.