以變分不等式為限制條件的非線性最佳化問題之性質探討

Abstract

以變分不等式為限制條件的非線性最佳化問題又被稱為帶有均衡限制式的數學規劃問題 (MPEC)，此類問題廣泛的應用在各個學術領域上。而在運輸領域中，路網設計問題、起迄需求量推 估問題、號誌控制問題、擁擠收費問題等皆可利用MPEC 來進行求解。由於變分不等式不具有封閉 形式，因此常用互補限制式將MPEC 模式進行改寫，並利用下列演算法進行求解，包含有平滑法 (Smoothing method)、懲罰法(Penalty method)、序列二次規劃法(Sequential Quadratic Programming)、 內點法(Interior point method)等。但因為MPEC 問題的可行解區域常會有非凸性(Nonconvexity)及不可 微的性質，且互補限制式又含有組合問題(Combinatorial issue)，如何設計有效率的演算法來求解 MPEC 問題仍是一具有挑戰性的研究議題。故本研究嘗試在適當的限制規範(Constraint qualification) 下將MPEC 進行改寫，並對該問題的可行解區域進行分析，進一步提出一有效率的求解演算法。 本研究第一年的工作中，將針對改寫後的MPEC 問題的可行解空間性質進行分析，並探討解的 存在性與唯一性等問題。 第二年將根據該問題設計求解演算法，並討論其收斂性。 第三年將會根據所提出之演算法進行程式撰寫，並應用在數值範例中。

Nonlinear optimization problems with variational inequality constraints, also known as mathematical programs with equilibrium constraints (MPEC), are widely applied to different research fields. In the transportation field, MPEC can be applied to solve various problems, such as network design problems, origin-destination volume estimation, signal control problems, and congestion toll pricing. When solving MPEC, variational inequality constraints are usually replaced by complementarity constraints because of lacking closed form. Several algorithms are proposed to solve the reformulated MPEC, such as smoothing method, penalty method, sequential quadratic programming and interior point method. However, due to the nonconvexity and nondifferentiability of the feasible region of MPEC and the combinatorial issue of complementarity constraints, designing an efficient solution algorithm is still a challenging topic. This research attempts to solve MPEC by 1) reformulate MPEC under appropriate constraint qualifications, 2) analyze the feasible region of the reformulated MPEC, and 3) propose an efficient solution algorithm. In the first year, we will focus on analyzing the properties of feasible region of the reformulated MPEC, including the existence and uniqueness of solution. In the second year, we will design a solution algorithm according to the reformulated MPEC and discuss its convergence. In the third year, we will implement the proposed algorithm and demonstrate a numerical example.