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

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

Maximum Principles of Markov Regime-Switching Forward–Backward Stochastic Differential Equations with Jumps and Partial Information

This paper presents three versions of maximum principle for a stochastic optimal control problem of Markov regime-switching forward–backward stochastic differential equations with jumps. First, a general sufficient maximum principle for optimal control for a system, driven by a Markov regime-switching forward–backward jump–diffusion model, is developed. In the regime-switching case, it might happen that the associated Hamiltonian is not concave and hence the classical maximum principle cannot be applied. Hence, an equivalent type maximum principle is introduced and proved. In view of solving an optimal control problem when the Hamiltonian is not concave, we use a third approach based on Malliavin calculus to derive a general stochastic maximum principle. This approach also enables us to derive an explicit solution of a control problem when the concavity assumption is not satisfied. In addition, the framework we propose allows us to apply our results to solve a recursive utility maximization problem.     

Sufficiency of Kuhn-Tucker optimality conditions for a fractional programming problem

The problem considered is that of maximizing the ratio of a concave function to a convex function subject to constraints in terms of upper bounds on convex functions and with each variable occurring in a single constraint. It is demonstrated that the Kuhn-Tucker conditions are sufficient for a feasible solution to be optimal.     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

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     

Minimizing the maximum network flow: models and algorithms with resource synergy considerations

In this paper, we model and solve the network interdiction problem of minimizing the maximum flow through a network from a given source node to a terminus node, while incorporating different forms of superadditive synergy effects of the resources applied to the arcs in the network. Within this context, we examine linear, concave, and convex–concave synergy relationships, illustrate their relative effect on optimal solution characteristics, and accordingly develop and test effective solution procedures for the underlying problems. For a concave synergy relationship, which yields a convex programme, we propose an inner-linearization procedure that significantly outperforms the competitive commercial solver SBB by improving the quality of solutions found by the latter by 6.2% (within a time limit of 1800 CPU?s), while saving 84.5% of the required computational effort. For general non-concave synergy relationships, we develop an outer-approximation-based heuristic that achieves solutions of objective value 0.20% better than the commercial global optimization software BARON, with a 99.3% reduction in computational effort for the subset of test problems for which BARON could identify a feasible solution within the set time limit.     

Optimal Consumption and Portfolio with Ambiguity to Markovian Switching

This paper considers the problem of maximizing expected utility from consumption and terminal wealth under model uncertainty for a general semimartingale market, where the agent with an initial capital and a random endowment can invest. To find a solution to the investment problem we use the martingale method. We first prove that under appropriate assumptions a unique solution to the investment problem exists. Then we deduce that the value functions of primal problem and dual problem are convex conjugate functions. Furthermore we consider a diffusion-jump-model where the coefficients depend on the state of a Markov chain and the investor is ambiguity to the intensity of the underlying Poisson process. Finally, for an agent with the logarithmic utility function, we use the stochastic control method to derive the Hamilton-Jacobi-Bellmann (HJB) equation. And the solution to this HJB equation can be determined numerically. We also show how thereby the optimal investment strategy can be computed.     

Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

单调全局最优化问题的凸化外逼近算法

单调优化是指目标函数与约束函数均为单调函数的全局优化问题．本文提出一种新的凸化变换方法把单调函数化为凸函数，进而把单调优化问题化为等价的凸极大或凹极小问题，然后采用Hoffman的外逼近方法来求得问题的全局最优解．我们把这种凸化方法同Tuy的Polyblock外逼近方法作了比较，通过数值比较可以看出本文提出的凸化的方法在收敛速度上明显优于Polyblock方法．     

基于极大极小方法的一类非线性系统的自适应控制

研究一类具有非线性不确定参数的非线性系统的自适应模型参考跟踪问题.假设系统的非线性项关于不确定参数是凸或凹的.去掉了在先前有关研究中要求参考模型矩阵有小于零的实特征值的条件.既考虑了状态反馈控制方式,也考虑了输出反馈控制方式.在采用输出反馈控制时,假设非线性项满足李普希兹条件,但李普希兹常数未知.基于一种极大极小方法,提出了一种自适应控制器的设计方法.控制器是连续的,能保证闭环系统的所有变量有界,并且渐近精确跟踪参考模型.举例说明了本结论的有用性.     

Convex-concave fractional programming with each variable occurring in a single constraint

The problem considered is that of maximizing the ratio of a concave and a convex function under the assumption that each variable occurs in exactly one component constraint. Such problems occur in the allocation of resources to activities. It is demonstrated that the problem is separable and that componentwise optimization can be applied to determine a solution. A method is given that can be used to evaluate the quality of any feasible solution in terms of an associated upper bound of the optimal value of the objective function: optimal and almost optimal solutions can be recognized. A fast incremental method of generating feasible solutions is described.     

Aanwendung des erweiterungsprinzips zur lösung konkayer optimierungsaufgaben

For the problem of minimizing a concave function over a convex polyedral-set an algorithm is given, which is based on the extension principle developed by Schoch. This algorithm yields after a finite number of steps an exact optimal solution of the problem. On the other hand one can find out throughout the algorithm an approximate optimal solution with any given precision.     

Hidden convexity in some nonconvex quadratically constrained quadratic programming

We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs. This author's work was partially supported by GIF, the German-Israeli Foundation for Scientific Research and Development and by the Binational Science Foundation. This author's work was partially supported by National Science Foundation Grants DMS-9201297 and DMS-9401871.     

Relaxation in nonconvex optimal control problems with subdifferential operators

We consider the minimization problem of an integral functional in a separable Hilbert space with integrand not convex in the control defined on solutions of the control system described by nonlinear evolutionary equations with mixed nonconvex constraints. The evolutionary operator of the system is the subdifferential of a proper, convex, lower semicontinuous function depending on time. Along with the initial problem, the author considers the relaxed problem with the convexicated control constraint and the integrand convexicated with respect to the control. Under sufficiently general assumptions, it is proved that the relaxed problem has an optimal solution, and for any optimal solution, there exists a minimizing sequence of the initial problem converging to the optimal solution with respect to trajectories and the functional. An example of a controlled parabolic variational inequality with obstacle is considered in detail. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 26, Nonlinear Dynamics, 2005.     

An Outer Approximation Algorithm Guaranteeing Feasibility of Solutions and Approximate Accuracy of Optimality

We treat a concave programming problem with a compact convex feasible set. Assuming the differentiability of the convex functions which define the feasible set, we propose two solution methods. Those methods utilize the convexity of the feasible set and the property of the normal cone to the feasible set at each point over the boundary. Based on the proposed two methods, we propose a solution algorithm. This algorithm takes advantages over classical methods: (1) the obtained approximate solution is always feasible, (2) the error of such approximate value can be evaluated properly for the optimal value of such problem, (3) the algorithm does not have any redundant iterations.     

Canonical dual approach to solving the maximum cut problem

This paper presents a canonical dual approach for finding either an optimal or approximate solution to the maximum cut problem (MAX CUT). We show that, by introducing a linear perturbation term to the objective function, the maximum cut problem is perturbed to have a dual problem which is a concave maximization problem over a convex feasible domain under certain conditions. Consequently, some global optimality conditions are derived for finding an optimal or approximate solution. A gradient decent algorithm is proposed for this purpose and computational examples are provided to illustrate the proposed approach.     

Viscosity solutions for the dynamic programming equations

In a previous paper the author has introduced a new notion of a (generalized) viscosity solution for Hamilton-Jacobi equations with an unbounded nonlinear term. It is proved here that the minimal time function (resp. the optimal value function) for time optimal control problems (resp. optimal control problems) governed by evolution equations is a (generalized) viscosity solution for the Bellman equation (resp. the dynamic programming equation). It is also proved that the Neumann problem in convex domains may be viewed as a Hamilton-Jacobi equation with a suitable unbounded nonlinear term.     

Optimal arrival rate and service rate control of multi-server queues

We consider the problem of optimal control of a multi-server queue with controllable arrival and service rates. This study is motivated by its potential application to the design and control of data centers. The cost structure includes customer holding cost which is a non-decreasing convex function of the number of customers in the system, server operating cost which is a non-decreasing convex function of the chosen service rate, and system operating reward which is a non-decreasing concave function of the chosen arrival rate. We formulate the problem as a continuous-time Markov decision process and derive structural properties of the optimal control policies under both discounted cost and average cost criterions.     

Optimal control and long-run dynamics for a spatial economic growth model with physical capital accumulation and pollution diffusion

In this work we analyze the large-time behavior of a spatially structured economic growth model coupling physical capital accumulation and pollution diffusion. This model extends other results in the literature along different directions. Alongside the classical Cobb–Douglas production function, a convex–concave production function is considered. We add a negative feedback to the production function in order to describe the (negative) influence of pollution on output, and therefore on capital accumulation. We also present an optimal control problem for the above model.