7 January 2015 in Journal of Optimization Theory and Applications
1 May 2022 in Mathematics of Operations Research
We propose a new augmented Lagrangian (AL) method for solving the mathematical program with complementarity constraints (MPCC), where the complementarity constraints are left out of the AL function and treated directly. Two observations motivate us to propose this method: The AL subproblems are closer to the original problem in terms of the constraint structure; and the AL subproblems can be solved efficiently by a nonmonotone projected gradient method, in which we have closed-form solutions at each iteration. The former property helps us show that the proposed method converges globally to an M-stationary (better than C-stationary) point under MPCC relaxed constant positive linear dependence condition. Theoretical comparison with existing AL methods demonstrates that the proposed method is superior in terms of the quality of accumulation points and the strength of assumptions. Numerical comparison, based on problems in MacMPEC, validates the theoretical results.
1 February 2021 in Mathematics of Operations Research
We introduce a unified algorithmic framework, called the proximal-like incremental aggregated gradient (PLIAG) method, for minimizing the sum of a convex function that consists of additive relatively smooth convex components and a proper lower semicontinuous convex regularization function over an abstract feasible set whose geometry can be captured by using the domain of a Legendre function. The PLIAG method includes many existing algorithms in the literature as special cases, such as the proximal gradient method, the Bregman proximal gradient method (also called the NoLips algorithm), the incremental aggregated gradient method, the incremental aggregated proximal method, and the proximal incremental aggregated gradient method. It also includes some novel interesting iteration schemes. First, we show that the PLIAG method is globally sublinearly convergent without requiring a growth condition, which extends the sublinear convergence result for the proximal gradient algorithm to incremental aggregated-type first-order methods. Then, by embedding a so-called Bregman distance growth condition into a descent-type lemma to construct a special Lyapunov function, we show that the PLIAG method is globally linearly convergent in terms of both function values and Bregman distances to the optimal solution set, provided that the step size is not greater than some positive constant. The convergence results derived in this paper are all established beyond the standard assumptions in the literature (i.e., without requiring the strong convexity and the Lipschitz gradient continuity of the smooth part of the objective). When specialized to many existing algorithms, our results recover or supplement their convergence results under strictly weaker conditions.
18 May 2022 in Optimization
The mathematical program with switching constraints (MPSC), which has been introduced recently, is a difficult class of optimization problems since standard constraint qualifications are very likely to fail at local minimizers. Due to the failure of standard constraint qualifications, it is reasonable to propose some constraint qualifications for local minimizers to satisfy some stationarity conditions that are generally weaker than Karush-Kuhn-Tucker stationarity such as Mordukhovich (M-) stationarity. First, we propose the weakest constraint qualification for M-stationarity of MPSC to hold at local minimizers. Then we extend some weak verifiable constraint qualifications for nonlinear programming to allow the existence of switching constraints, which are all strictly weaker than MPSC linear independence constraint qualification and/or MPSC Mangasarian-Fromovitz constraint qualification used in the literature. We show that most of the newly introduced constraint qualifications are sufficient for local minimizers to be M-stationary. Finally, the relations among MPSC tailored constraint qualifications are discussed.
1 November 2025 in INFORMS Journal on Computing
The second-best congestion pricing (SBCP) problem is one of the most challenging problems in transportation because of its two-level hierarchical structure. In spite of various intriguing attempts at solving SBCP, existing solution methods are either heuristic without a convergence guarantee or suitable for solving SBCP on small networks only. In this paper, we first reveal some convexity-based structural properties of the marginal value function reformation of SBCP, and then, by effectively exploiting these structural properties, we propose two dedicated decomposition methods for solving SBCP on large-scale networks, which are different from existing methods in that they avoid linearizing nonconvex functions. We establish the convergence of the two decomposition methods under commonly used conditions and provide the maximum number of iterations for deriving an approximate stationary solution. The computational experiments based on a collection of real road networks show that in comparison with three existing popular methods, the two proposed methods are capable of solving SBCP on larger-scale networks, and for instances that can be solved by existing methods, the two proposed methods are substantially faster. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods and Analysis. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72032001, 72431007, 72131007, 72021002, and 12271161]. L. Guo was also supported by the Natural Science Foundation of Shanghai [Grant 22ZR1415900]. X. Wang was also supported by the Fundamental Research Funds for the Central Universities and CCF-DiDi GAIA Collaborative Research Funds for Young Scholars. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0144 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0144 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
7 August 2022 in Journal of Management Analytics
The command-and-control regulation is likely inefficient and costly. This study investigates a regional pollution control scheme with tax (RPCST) under which the central government sets the tax rate under a given pollutant reduction quota and local governments determine their pollution removal rates based on the central government’s policy. First, a one-leader-multi-follower (OLMF) Stackelberg game model is formulated, in which the central government is the leader and the local governments are the followers. Then, a procedure based on bilevel programming and relaxation method is applied to solve the OLMF model. Finally, a case study analyzing the SO2 reduction of the Yangtze River Delta in China is conducted to demonstrate the effectiveness of the RPCST. The results show that RPCST works better than the current command-and-control scheme. Our analysis provides a guideline for governments to design optimal tax schemes to effectively solve the regional air pollution crisis.