The continuous network design problem (CNDP) has been recognized as one of the most challenging issues in the field of transportation. Existing approaches to solving the CNDP are primarily heuristic without convergence guarantee or suitable for handling small networks because of the inherent nonconvexity arising from its bilevel hierarchical structure. An efficient and convergent approach for solving the CNDP on large networks has been fervently sought. In this paper, we present a novel convergent approach centered around exploiting the inherent convexity-related structure within the CNDP. We first demonstrate that the CNDP can be equivalently formulated as a difference of convex (DC) program with all involved functions being either convex functions or DC functions. Then, by exploiting the DC structure, we give a convex programming approximation for the CNDP and subsequently propose a penalized sequential convex programming approach. Finally, we show that the proposed method can yield an approximately stationary point under commonly used conditions. A numerical study is conducted on some real networks from a reputable network repository for transportation research. The numerical results demonstrate that the proposed method achieves better solutions with faster computational speed, particularly on larger networks, as compared with two heuristic approaches and two convergent approaches. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: This research was supported by the National Science Foundation of China [Grants 72131007, 72140006, 12271161, 12222106, and 12326605], the Natural Science Foundation of Shanghai [Grant 22ZR1415900], and Guangdong Basic and Applied Basic Research Foundation [Grant 2022B1515020082]. 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.2024.0737 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0737 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Constrained bilevel optimization tackles nested structures present in constrained learning tasks like constrained meta-learning, adversarial learning, and distributed bilevel optimization. However, existing bilevel optimization methods mostly are typically restricted to specific constraint settings, such as linear lower-level constraints. In this work, we overcome this limitation and develop a new single-loop, Hessian-free constrained bilevel algorithm capable of handling more general lower-level constraints. We achieve this by employing a doubly regularized gap function tailored to the constrained lower-level problem, transforming constrained bilevel optimization into an equivalent single-level optimization problem with a single smooth constraint. We rigorously establish the non-asymptotic convergence analysis of the proposed algorithm under the convexity of lower-level problem, avoiding the need for strong convexity assumptions on the lower-level objective or coupling convexity assumptions on lower-level constraints found in existing literature. Additionally, the generality of our method allows for its extension to bilevel optimization with minimax lower-level problem. We evaluate the effectiveness and efficiency of our algorithm on various synthetic problems, typical hyperparameter learning tasks, and generative adversarial network.

This brief aims to provide theoretical guarantee and practical guidance on constructing a type of graphs from input data via distance preserving criterion. Unlike the graphs constructed by other methods, the targeted graphs are hidden through estimating a density function of latent variables such that the pairwise distances in both the input space and the latent space are retained, and they have been successfully applied to various learning scenarios. However, previous work heuristically treated the multipliers in the dual as the graph weights, so the interpretation of this graph from a theoretical perspective is still missing. In this brief, we fill up this gap by presenting a detailed interpretation based on optimality conditions and their connections to neighborhood graphs. We further provide a systematic way to set up proper hyperparameters to prevent trivial graphs and achieve varied levels of sparsity. Three extensions are explored to leverage different measure functions, refine/reweigh an initial graph, and reduce computation cost for medium-sized graph. Extensive experiments on both synthetic and real datasets were conducted and experimental results verify our theoretical findings and the showcase of the studied graph in semisupervised learning provides competitive results to those of compared methods with their best graph.

Existing gradient-based optimization methods for hyperparameter tuning can only guarantee theoretical convergence to stationary solutions when the bilevel program satisfies the condition that for fixed upper-level variables, the lower-level is strongly convex (LLSC) and smooth (LLS). This condition is not satisfied for bilevel programs arising from tuning hyperparameters in many machine learning algorithms. In this work, we develop a sequentially convergent Value Function based Difference-of-Convex Algorithm with inexactness (VF-iDCA). We then ask: can this algorithm achieve stationary solutions without LLSC and LLS assumptions? We provide a positive answer to this question for bilevel programs from a broad class of hyperparameter tuning applications. Extensive experiments justify our theoretical results and demonstrate the superiority of the proposed VF-iDCA when applied to tune hyperparameters.