Allocation of resources according to a fractional objective

The problem considered is that of the allocation of resources to activities according to a fractional measure given by the ratio of “return” to “cost”. The return is the sum of returns from the activities, each activity being described by a concave return function. There is a positive fixed cost and a variable cost that depend linearly on the allocations. Properties related to the uniqueness of optimal solutions and the number of non-zero allocations are derived. A method is given by which any set of feasible allocations can be used to derive an upper bound of the optimal value of the objective function: optimal and almost-optimal allocations can be recognized. Allocations can be generated by a fast incremental method that is described. The method utilizes data in sequential order and can be used to solve large problems.     

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     

Resource Allocation with Noise Constraints

In the allocation of resources to activities, each activity is described by a concave return function and the sum of the returns is maximized. There are linear constraints on the available quantity of each essential resource. Existing methods for the incremental generation of almost-optimal allocations and for the evaluation of such allocations are extended to include allocations involving "noise" constraints in addition to the linear constraints on the available quantity of each resource. A noise constraint, which is defined in the paper, may be expressed by any relationship, not necessarily linear. An example is given in which the noise constraints take the form of constraints on additional resources.     

On perfect hashing of numbers with sparse digit representation via multiplication by a constant

Consider the set of vectors over a field having non-zero coefficients only in a fixed sparse set and multiplication defined by convolution, or the set of integers having non-zero digits (in some base b) in a fixed sparse set. We show the existence of an optimal (or almost-optimal, in the latter case) ‘magic’ multiplier constant that provides a perfect hash function which transfers the information from the given sparse coefficients into consecutive digits. Studying the convolution case we also obtain a result of non-degeneracy for Schur functions as polynomials in the elementary symmetric functions in positive characteristic.     

MERIT FUNCTION AND GLOBAL ALGORITHM FOR BOX CONSTRAINED VARIATIONAL INEQUALITIES

1 IntroductionWe consider tlie variational inequality problelll, deuoted by VIP(X, F), wliicli is to find avector x* E X such thatF(X*)"(X -- X-) 2 0, VX E X, (1)where F: R" - R" is any vector-valued f11uction and X is a uonelllpty subset of R'.This problem has important applicatiolls. in equilibriun1 modeIs arising in fields such asecououtics, transportatioll scieuce alld operations research. See [1]. There exist mauy lllethodsfor solviug tlie variational li1equality problem VIP(X. …     

Global Method for Monotone Variational Inequality Problems with Inequality Constraints

We consider optimization methods for monotone variational inequality problems with nonlinear inequality constraints. First, we study the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed, and some desirable properties of the merit function are obtained. Through the merit function, the original variational inequality problem is reformulated as simple bounded minimization. Under certain assumptions, we show that any stationary point of the optimization problem is a solution of the problem considered. Finally, we propose a descent method for the variational inequality problem and prove its global convergence.     

Solving semi-infinite programs by smoothing projected gradient method

In this paper, we study a semi-infinite programming (SIP) problem with a convex set constraint. Using the value function of the lower level problem, we reformulate SIP problem as a nonsmooth optimization problem. Using the theory of nonsmooth Lagrange multiplier rules and Danskin’s theorem, we present constraint qualifications and necessary optimality conditions. We propose a new numerical method for solving the problem. The novelty of our numerical method is to use the integral entropy function to approximate the value function and then solve SIP by the smoothing projected gradient method. Moreover we study the relationships between the approximating problems and the original SIP problem. We derive error bounds between the integral entropy function and the value function, and between locally optimal solutions of the smoothing problem and those for the original problem. Using certain second order sufficient conditions, we derive some estimates for locally optimal solutions of problem. Numerical experiments show that the algorithm is efficient for solving SIP.     

A modified objective function method for solving nonlinear multiobjective fractional programming problems

A new method is used for solving nonlinear multiobjective fractional programming problems having V-invex objective and constraint functions with respect to the same function η. In this approach, an equivalent vector programming problem is constructed by a modification of the objective fractional function in the original nonlinear multiobjective fractional problem. Furthermore, a modified Lagrange function is introduced for a constructed vector optimization problem. By the help of the modified Lagrange function, saddle point results are presented for the original nonlinear fractional programming problem with several ratios. Finally, a Mond-Weir type dual is associated, and weak, strong and converse duality results are established by using the introduced method with a modified function. To obtain these duality results between the original multiobjective fractional programming problem and its original Mond-Weir duals, a modified Mond-Weir vector dual problem with a modified objective function is constructed.     

Exactness Property of the Exact Absolute Value Penalty Function Method for Solving Convex Nondifferentiable Interval-Valued Optimization Problems

In the paper, the classical exact absolute value function method is used for solving a nondifferentiable constrained interval-valued optimization problem with both inequality and equality constraints. The property of exactness of the penalization for the exact absolute value penalty function method is analyzed under assumption that the functions constituting the considered nondifferentiable constrained optimization problem with the interval-valued objective function are convex. The conditions guaranteeing the equivalence of the sets of LU-optimal solutions for the original constrained interval-valued extremum problem and for its associated penalized optimization problem with the interval-valued exact absolute value penalty function are given.     

基于光滑化方法求解非线性l1问题

讨论了求解非线性l1问题的一种新的光滑函数法.通过对非线性l1问题模型的转化,将该问题化为一个不可微优化问题,据此提出了基于BFGS迭代的非线性l1问题的光滑函数法,介绍了非线性l1问题的光滑函数的有关性质、算法步骤及其收敛性.数值仿真显示了提出的光滑函数方法可以避免数值计算的溢出,具有一定的有效性.     

On the Smoothing of the Square-Root Exact Penalty Function for Inequality Constrained Optimization

In this paper we propose two methods for smoothing a nonsmooth square-root exact penalty function for inequality constrained optimization. Error estimations are obtained among the optimal objective function values of the smoothed penalty problem, of the nonsmooth penalty problem and of the original optimization problem. We develop an algorithm for solving the optimization problem based on the smoothed penalty function and prove the convergence of the algorithm. The efficiency of the smoothed penalty function is illustrated with some numerical examples, which show that the algorithm seems efficient.     

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

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

On the application of the residual method for the correction of inconsistent problems of convex programming

For the correction of a convex programming problem with potentially inconsistent constraint system (an improper problem), we apply the residual method, which is a standard regularization procedure for ill-posed optimization models. A problem statement typical for the residual method is reduced to a minimization problem for an appropriate penalty function. We apply two classical penalty functions: the quadratic penalty function and the exact Eremin-Zangwill penalty function. For each of the approaches, we establish convergence conditions and bounds for the approximation error.     

Maximizing a concave function over the efficient or weakly-efficient set

An important approach in multiple criteria linear programming is the optimization of some function over the efficient or weakly-efficient set. This is a very difficult nonconvex optimization problem, even for the case that the function to be optimized is linear. In this article we consider the problem of maximizing a concave function over the efficient or weakly-efficient set. We show that this problem can essentially be formulated as a special global optimization problem in the space of the extreme criteria of the underlying multiple criteria linear program. An algorithm of branch and bound type is proposed for solving the resulting problem.     

Multiobjective duality for convex ratios

In this paper we present a duality approach for a multiobjective fractional programming problem. The components of the vector objective function are particular ratios involving the square of a convex function and a positive concave function. Applying the Fenchel-Rockafellar duality theory for a scalar optimization problem associated to the multiobjective primal, a dual problem is derived. This scalar dual problem is formulated in terms of conjugate functions and its structure gives an idea about how to construct a multiobjective dual problem in a natural way. Weak and strong duality assertions are presented.     

Operator Function Method in the Problem of Normal Waves in an Inhomogeneous Waveguide

The problem of normal waves in a closed (screened) regular waveguiding structure of arbitrary cross-section is considered by reducing it to a boundary value problem for the longitudinal electromagnetic field components in Sobolev spaces. The variational statements of the problem is used to determine the solution. The problem is reduced to studying an operator function. The properties of the operators contained in the operator function necessary to analyze its spectral properties are studied. Theorems on the spectrum discreteness and the distribution of characteristic numbers of the operator function on the complex plane are proved. The problem of completeness of the system of root vectors of the operator function is considered. The theorem on the double completeness of the system of root vectors of the operator function with finite deficiency is proved.     

Deriving the Properties of Linear Bilevel Programming via a Penalty Function Approach

For the linear bilevel programming problem, we propose an assumption weaker than existing assumptions, while achieving similar results via a penalty function approach. The results include: equivalence between (i) existence of a solution to the problem, (ii) existence of an exact penalty function approach for solving the problem, and (iii) achievement of the optimal value of the equivalent form of the problem at some vertex of a certain polyhedral convex set. We prove that the assumption is both necessary and sufficient for the linear bilevel programming problem to admit an exact penalty function formulation, provided that the equivalent form of the problem has a feasible solution. A method is given for computing the minimal penalty function parameter value. This method can be executed by solving a set of linear programming problems. Lagrangian duality is also presented.     

非线性约束优化的光滑化平方根罚函数

介绍一种非线性约束优化的不可微平方根罚函数,为这种非光滑罚函数提出了一个新的光滑化函数和对应的罚优化问题,获得了原问题与光滑化罚优化问题目标之间的误差估计. 基于这种罚函数,提出了一个算法和收敛性证明,数值例子表明算法对解决非线性约束优化具有有效性.     

Deterministic Time-inconsistent Optimal Control Problems - an Essentially Cooperative Approach

A general deterministic time-inconsistent optimal control problem is formulated for ordinary differential equations. To find a time-consistent equilibrium value function and the corresponding time-consistent equilibrium control, a non-cooperative N-person differential game (but essentially cooperative in some sense) is introduced. Under certain conditions, it is proved that the open-loop Nash equilibrium value function of the N -person differential game converges to a time-consistent equilibrium value function of the original problem, which is the value function of a time-consistent optimal control problem. Moreover, it is proved that any optimal control of the time-consistent limit problem is a time-consistent equilibrium control of the original problem.     

Modified Ratio Objective Approach in Mathematical Programming

A new approach to obtaining the optimality conditions for fractional mathematical programming problems involving one objective ratio in the objective function is considered. Using this approach, an equivalent optimization problem is constructed by a modification of the single-ratio objective function in the fractional programming problem. Furthermore, an η-Lagrange function is introduced for a constructed optimization problem and modified saddle-point results are presented.