Global optimality conditions for quadratic 0-1 optimization problems

In the present work, we intend to derive conditions characterizing globally optimal solutions of quadratic 0-1 programming problems. By specializing the problem of maximizing a convex quadratic function under linear constraints, we find explicit global optimality conditions for quadratic 0-1 programming problems, including necessary and sufficient conditions and some necessary conditions. We also present some global optimality conditions for the problem of minimization of half-products.     

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 Approach for Solving Some Convex Maximization Problems

We are concerned with concave programming or the convex maximization problem. In this paper, we propose a method and algorithm for solving the problem which are based on the global optimality conditions first obtained by Strekalovsky (Soviet Mathematical Doklady, 8(1987)). The method continues approaches given in (Journal of global optimization, 8(1996); Journal of Nolinear and convex Analyses 4(1)(2003)). Under certain assumptions a convergence property of the proposed method has been established. Some computational results are reported. Also, it has been shown that the problem of finding the largest eigenvalue can be found by the proposed method.     

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.      

Mathematical programming in rough environment

Classical mathematics is usually crisp while most real-life problems are not; therefore, classical mathematics is usually not suitable for dealing with real-life problems. In this article, we present a systematic and focused study of the application of rough sets (Z. Pawlak, Rough sets, In. J. Comput. Informa. Sci. 11 (1982), pp. 341–356.) to a basic area of decision theory, namely ‘mathematical programming’. This new framework concerns mathematical programming in a rough environment and is called ‘rough programming’ (L. Baoding, Theory and Practice of Uncertain Programming, 1st ed., Physica-Verlag, Heidelberg, 2002; E.A. Youness, Characterizing solutions of rough programming problems, Eut. J. Oper. Res. 168 (2006), pp. 1019–1029). It implies the existence of the roughness in any part of the problem as a result of the leakage, uncertainty and vagueness in the available information. We classify rough programming problems into three classes according to the place of the roughness. In rough programming, wherever roughness exists, new concepts like rough feasibility and rough optimality come to the front of our interest. The study of convexity for rough programming problems plays a key role in understanding global optimality in a rough environment. For this, a theoretical framework of convexity in rough programming and conceptualization of the solution is created on the lines of their crisp counterparts.     

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

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

Mixed duality without a constraint qualification for minimax fractional programming

Without the need of a constraint qualification, we establish the necessary and sufficient optimality conditions for minimax fractional programming. Using these optimality conditions, we construct a mixed dual model which unifies the Mond–Weir dual, Wolfe dual and a parameter dual models. Several duality theorems are established. Consequently, this article partly solves the problem posed by Lai et al. [H.C. Lai, J.C. Liu and K. Tanaka (1999). Duality without a constraint qualification for minimax fractional programming. Journal of Optimization Theory and Applications, 101, 109–125.].     

Bilinear programming: An exact algorithm

The Bilinear Programming Problem is a structured quadratic programming problem whose objective function is, in general, neither convex nor concave. Making use of the formal linearity of a dual formulation of the problem, we give a necessary and sufficient condition for optimality, and an algorithm to find an optimal solution.Research partially supported by the Office of Naval Research under Contract N00014-69-A-0200-1010 with the University of California.     

Inscribed ball and enclosing box methods for the convex maximization problem

Many important classes of decision models give rise to the problem of finding a global maximum of a convex function over a convex set. This problem is known also as concave minimization, concave programming or convex maximization. Such problems can have many local maxima, therefore finding the global maximum is a computationally difficult problem, since standard nonlinear programming procedures fail. In this article, we provide a very simple and practical approach to find the global solution of quadratic convex maximization problems over a polytope. A convex function achieves its global maximum at extreme points of the feasible domain. Since an inscribed ball does not contain any extreme points of the domain, we use the largest inscribed ball for an inner approximation while a minimal enclosing box is exploited for an outer approximation of the domain. The approach is based on the use of these approximations along with the standard local search algorithm and cutting plane techniques.     

Performance evaluation of fault-tolerant routing algorithms: an optimization problem

In this paper, we present a new theoretical approach for studying the behaviour and the performance of shortest paths fault-tolerant distributed algorithms of a certain class. The behaviour of each processor is modeled by means of a stochastic matrix. We show that achieving the optimal behaviour of Nprocessors is equivalent to solvingan optimization problem of a function of 2N variables under constraints; this function is neither convex nor concave. Solutions for which such a type of algorithms has an optimal behaviour are derived. Using that result, we build a fuzzy set of solutions which provides a global overview (a sort of “relief”): each solution of the fuzzy set has value ? ranging between 0 and 1, which may be regarded as its“bench-mark” so (1 -?) points out the proximity of any solution from the optimal solution     

Greedy primal-dual algorithm for dynamic resource allocation in complex networks

In Stolyar (Queueing Systems 50 (2005) 401–457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several “commodities.”) Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401–457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples. AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12     

Constructive Solution of Inverse Parametric Linear/Quadratic Programming Problems

Parametric convex programming has received a lot of attention, since it has many applications in chemical engineering, control engineering, signal processing, etc. Further, inverse optimality plays an important role in many contexts, e.g., image processing, motion planning. This paper introduces a constructive solution of the inverse optimality problem for the class of continuous piecewise affine functions. The main idea is based on the convex lifting concept. Accordingly, an algorithm to construct convex liftings of a given convexly liftable partition will be put forward. Following this idea, an important result will be presented in this article: Any continuous piecewise affine function defined over a polytopic partition is the solution of a parametric linear/quadratic programming problem. Regarding linear optimal control, it will be shown that any continuous piecewise affine control law can be obtained via a linear optimal control problem with the control horizon at most equal to 2 prediction steps.     

Convex optimization approaches to maximally predictable portfolio selection

In this article we propose a simple heuristic algorithm for approaching the maximally predictable portfolio, which is constructed so that return model of the resulting portfolio would attain the largest goodness-of-fit. It is obtained by solving a fractional program in which a ratio of two convex quadratic functions is maximized, and the number of variables associated with its nonconcavity has been a bottleneck in spite of continuing endeavour for its global optimization. The proposed algorithm can be implemented by simply solving a series of convex quadratic programs, and computational results show that it yields within a few seconds a (near) Karush–Kuhn–Tucker solution to each of the instances which were solved via a global optimization method in [H. Konno, Y. Takaya and R. Yamamoto, A maximal predictability portfolio using dynamic factor selection strategy, Int. J. Theor. Appl. Fin. 13 (2010) pp. 355–366]. In order to confirm the solution accuracy, we also pose a semidefinite programming relaxation approach, which succeeds in ensuring a near global optimality of the proposed approach. Our findings through computational experiments encourage us not to employ the global optimization approach, but to employ the local search algorithm for solving the fractional program of much larger size.     

Study of a special nonlinear problem arising in convex semi-infinite programming

We consider convex problems of semi-infinite programming (SIP) using an approach based on the implicit optimality criterion. This criterion allows one to replace optimality conditions for a feasible solution x ⁰ of the convex SIP problem by such conditions for x ⁰ in some nonlinear programming (NLP) problem denoted by NLP(I(x ⁰)). This nonlinear problem, constructed on the base of special characteristics of the original SIP problem, so-called immobile indices and their immobility orders, has a special structure and a diversity of important properties. We study these properties and use them to obtain efficient explicit optimality conditions for the problem NLP(I(x ⁰)). Application of these conditions, together with the implicit optimality criterion, gives new efficient optimality conditions for convex SIP problems. Special attention is paid to SIP problems whose constraints do not satisfy the Slater condition and to problems with analytic constraint functions for which we obtain optimality conditions in the form of a criterion. Comparison with some known optimality conditions for convex SIP is provided.     

A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems

We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game.     

Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.     

Unboundedness in reverse convex and concave integer programming

In this paper we are concerned with the problem of unboundedness and existence of an optimal solution in reverse convex and concave integer optimization problems. In particular, we present necessary and sufficient conditions for existence of an upper bound for a convex objective function defined over the feasible region contained in ${\mathbb{Z}^n}$ . The conditions for boundedness are provided in a form of an implementable algorithm, showing that for the considered class of functions, the integer programming problem is unbounded if and only if the associated continuous problem is unbounded. We also address the problem of boundedness in the global optimization problem of maximizing a convex function over a set of integers contained in a convex and unbounded region. It is shown in the paper that in both types of integer programming problems, the objective function is either unbounded from above, or it attains its maximum at a feasible integer point.     

Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints

For the problem of maximizing a convex quadratic function under convex quadratic constraints, we derive conditions characterizing a globally optimal solution. The method consists in exploiting the global optimality conditions, expressed in terms of -subdifferentials of convex functions and -normal directions, to convex sets. By specializing the problem of maximizing a convex function over a convex set, we find explicit conditions for optimality.     

Using copositivity for global optimality criteria in concave quadratic programming problems

In this note we specify a necessary and sufficient condition for global optimality in concave quadratic minimization problems. Using this condition, it follows that, from the perspective of worst-case complexity of concave quadratic problems, the difference between local and global optimality conditions is not as large as in general. As an essential ingredient, we here use the-subdifferential calculus via an approach of Hiriart-Urruty and Lemarechal (1990).