Mathematical programs with multiobjective generalized Nash equilibrium problems in the constraints

This paper considers a class of mathematical programs that include multiobjective generalized Nash equilibrium problems in the constraints. Little research can be found in the literature although it has some interesting applications. We present a single level reformulation for this kind of problems and show their equivalence in terms of global and local minimizers. We find that the reformulation is a special case of the so-called mathematical program with equilibrium constraints which is extensively studied in the literature.     

Sensitivity Analysis Based Method for Optimal Road Network Pricing

Road pricing is an important economic measure for optimal management of transportation networks. The optimization objectives can be the total travel time or total cost incurred by all the travelers, or some other environmental objective such as minimum emission of dioxide, an so on. Suppose a certain toll is posed on some link on the network, this will give an impact on flows over the whole network and brings about a new equilibrium state. An equilibrium state is a state of traffic network at which no traveler could decrease the perceived travel cost by unilaterally changing the route. The aim of the toll setting is to achieve such an equilibrium state that a certain objective function is optimized. The problem can be formulated as a mathematical program with equilibrium constraints (MPEC). A key step for solving such a MPEC problem is the sensitivity analysis of traffic flows with respect to the change of link characteristics such as the toll prices. In this paper a sensitivity analysis based method is proposed for solving optimal road pricing problems.     

工程力学中的互补问题:模型

对互补问题在非线性力学中的一些应用情况给出了较概括的介绍，重点放在了静态接触问题、弹塑性问题以及结构优化问题的互补模型上。将力学问题写成互补模型的好处主要有两点：一是使力学问题有更自然、更精确的数学描述；二是可以考虑用互补问题的有效和强健的数值算法来求解。     

An MPEC formulation and its cutting constraint algorithm for continuous network design problem with multi-user classes

Continuous network design problem (CNDP) is to determine the set of link capacity expansions and the corresponding equilibrium flows for which the measures of performance index for the network is optimal. Conventionally, CNDP assumed users to be homogeneous, that is, all travelers on the same link of the network are identical insofar as congestion effect and they have the same value of time (VOT). In fact, it does not accord with the real situation that all have the same VOT. So, multiple user classes with different VOT should be considered. This paper examines the CNDP with different VOT for multiple user classes, which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). Then, the cut constraint algorithm (CCA) is presented to solve the problem. The numerical experiments on the examples from the literature are illustrated to demonstrate that our model and algorithm are feasible.     

Robust strategic bidding in auction-based markets

In this paper, we propose an alternative methodology for devising revenue-maximizing strategic bids under uncertainty in the competitors’ bidding strategy. We focus on markets endowed with a sealed-bid uniform-price auction with multiple divisible products. On recognizing that the bids of competitors may deviate from equilibrium and are of difficult statistical characterization, we proposed a two-stage robust optimization model with equilibrium constraints aiming to devise risk-averse strategic bids. The proposed model is a trilevel optimization problem that can be recast as a particular instance of a bilevel program with equilibrium constraints. Reformulation procedures are proposed to find a single-level equivalent formulation suitable for column-and-constraint generation (CCG) algorithm. Results show that even for the case in which an imprecision of 1% is observed on the rivals’ bids in the equilibrium point, the robust solution provides a significant risk reduction (of 79.9%) in out-of-sample tests. They also indicate that the best strategy against high levels of uncertainty on competitors’ bid approaches to a price-taker offer, i.e., bid maximum capacity at marginal cost.     

Extension of Quasi-Newton Methods to Mathematical Programs with Complementarity Constraints

Quasi-Newton methods in conjunction with the piecewise sequential quadratic programming are investigated for solving mathematical programming with equilibrium constraints, in particular for problems with complementarity constraints. Local convergence as well as superlinear convergence of these quasi-Newton methods can be established under suitable assumptions. In particular, several well-known quasi-Newton methods such as BFGS and DFP are proved to exhibit the local and superlinear convergence.     

非线性均衡问题一个超线性收敛的光滑逼近SQP算法

研究非线性均衡问题,引入一个磨光算子将原问题转化为光滑问题,并用此光滑问题来逼近原来的问题而求解.在每步迭代中,通过转轴运算,求解一个线性约束二次规划问题和显式修正方向来得到主方向,并通过一个显式公式来得到高阶修正方向使得算法避免Maratos效应.在不需要上层互补条件下证明了算法具有全局收敛性和强收敛性且具有超线性收敛速度.     

非线性互补约束均衡问题的一个滤子SQP算法

提出了—个求解非线性互补约束均衡问题的滤子SQP算法.借助Fischer-Burmeister函数把均衡约束转化为—个非光滑方程组,然后利用逐步逼近和分裂思想,给出—个与原问题近似的一般的约束优化.引入滤子思想,避免了罚函数法在选择罚因子上的困难.在适当的条件下证明了算法的全局收敛性,部分的数值结果表明算法是有效的.     

Dynamic Slope Scaling Procedure and Lagrangian Relaxation with Subproblem Approximation

The dynamic slope scaling procedure (DSSP) is an efficient heuristic algorithm that provides good solutions to the fixed-charge transportation or network flow problem. However, the procedure is graphically motivated and appears unrelated to other optimization techniques. In this paper, we formulate the fixed-charge problem as a mathematical program with complementarity constraints (MPCC) and show that DSSP is equivalent to solving MPCC using Lagrangian relaxation with subproblem approximation.     

支持向量机中一种参数优化选取方法

本文给出一种支持向量机中的参数优化选取方法. 它是通过遗传算法和确定性算法相结合解平衡约束优化问题,求出二分类支持向量机(SVM)中的正则参数C,本文将C作为优化问题中的变量来处理.遗传算法用来求解以C为变量的优化问题, 而确定性算法对每一个C值求解约束.数值计算的结果表明,用文中所述的方法求得的C值能明显提高支持向量机的泛化性能.