In recent years, crowdsensing has emerged as a cost-effective alternative to traditional fixed-sensor systems for monitoring roadside parking availability, overcoming challenges such as high installation costs, limited scalability, and inadequate coverage in dynamic urban settings. This paper develops a spatio-temporal model of bus dynamics and a system-level optimization framework using integer programming to allocate sensors across a subset of buses. This deterministic baseline provides a foundation that can be extended to hybrid models that incorporate other opportunistic sensing fleets (e.g., taxis and unmanned aerial vehicles). To enhance computational efficiency, we introduce a Self-Trained Cardinality-Branching method, which integrates a novel cutting-plane technique with the traditional row-generation method. System-level simulations based on San Francisco’s street network demonstrate that the optimized allocation plan (545 sensing vehicles) achieves higher coverage rates than a random allocation plan using 1,100 vehicles, reducing the required fleet size by 50.45% on average. The proposed framework offers a scalable solution for sensor allocation in complex urban settings, providing reliable parking information while minimizing infrastructure expenses.

We introduce a framework to accelerate the convergence of gradient-based methods with online learning. The framework learns to scale the gradient at each iteration through an online learning algorithm and provably accelerates gradient-based methods asymptotically. In contrast with previous literature, where convergence is established based on worst-case analysis, our framework provides a strong convergence guarantee with respect to the optimal stepsize for the iteration trajectory. For smooth strongly convex optimization, our framework provides an $\Ocal(\kappa^\star \log(1/\varepsilon)$) asymptotic complexity result, where $\kappa^\star$ is the condition number achievable by the optimal preconditioner, improving on the previous $\Ocal(\sqrt{n}\kappa^\star \log(1/\varepsilon))$ result. For smooth convex optimization, we obtain the first convergence guarantee for the widely used hypergradient descent heuristic.

We propose Adam-mini, an optimizer that achieves on-par or better performance than AdamW with $50$% less memory footprint. Adam-mini reduces memory by cutting down the learning rate resources in Adam (i.e., $1/\sqrt{v}$). By delving into the Hessian structure of neural nets, we find Adam’s $v$ might not function at its full potential as effectively as we expected. We find that $\geq 99.9$% of these learning rates in $v$ could be harmlessly removed if we (1) carefully partition the parameters into blocks following our proposed principle on Hessian structure; (2) assign a single but good learning rate to each parameter block. We then provide one simple way to find good learning rates and propose Adam-mini. Empirically, we verify that Adam-mini performs on par or better than AdamW on various language models sized from 39M to 13B for pre-training, supervised fine-tuning, and RLHF. The reduced memory footprint of Adam-mini also alleviates communication overheads among GPUs, thereby increasing throughput. For instance, Adam-mini achieves $49.6$% higher throughput than AdamW when pre-training Llama 2-7B on $2\times$ A800-80GB GPUs, which saves 33% wall-clock time for pre-training.

This paper investigates the convergence properties of the hypergradient descent method ($\texttt{HDM}$), a 25-year-old heuristic originally proposed for adaptive stepsize selection in stochastic first-order methods. We provide the first rigorous convergence analysis of $\texttt{HDM}$ using the online learning framework and apply this analysis to develop a new state-of-the-art adaptive gradient methods with empirical and theoretical support. Notably, $\texttt{HDM}$ automatically identifies the optimal stepsize for the local optimization landscape and achieves local superlinear convergence. Our analysis explains the instability of $\texttt{HDM}$ reported in the literature and proposes efficient strategies to address it. We also develop two $\texttt{HDM}$ variants with heavy-ball and Nesterov momentum. Experiments on deterministic convex problems show $\texttt{HDM}$ with heavy-ball momentum ($\texttt{HDM-HB}$) exhibits robust performance and significantly outperforms other adaptive first-order methods. Moreover, $\texttt{HDM-HB}$ often matches the performance of $\texttt{L-BFGS}$, an efficient and practical quasi-Newton method, using less memory and cheaper iterations.

Online linear programming (OLP) has found broad applications in revenue management and resource allocation. State-of-the-art OLP algorithms achieve low regret by repeatedly solving linear programming (LP) subproblems that incorporate updated resource information. However, LP-based methods are computationally expensive and often inefficient for large-scale applications. By contrast, recent first-order OLP algorithms are more computationally efficient but typically suffer from weaker regret guarantees. To address these shortcomings, we propose a new algorithm that combines the strengths of LP-based and first-order OLP algorithms. Our algorithm re-solves the LP subproblems periodically at a predefined frequency $f$ and uses the latest dual prices to guide online decision-making. In parallel, a first-order method runs during each interval between LP re-solves and smooths resource consumption. Our algorithm achieves $\mathcal{O}(\log (T/f) + \sqrt{f})$ regret and delivers a "wait-less" online decision-making process that balances computational efficiency and regret guarantees. Extensive experiments demonstrate at least $10$-fold improvements in regret over first-order methods and $100$-fold improvements in runtime over LP-based methods.

Optimization modeling is fundamental to decision-making in fields such as supply chain management, logistics, and financial engineering, but its complexity presents a major barrier to adoption. Automating model creation from natural language is key to improving efficiency and access. However, while Large Language Models (LLMs) are a promising tool for this, they often produce flawed or infeasible results due to errors and hallucinations. To address this issue, we propose Solver-Informed Reinforcement Learning (SIRL), a framework that uses Reinforcement Learning with Verifiable Reward to improve LLMs’ ability to generate accurate and executable optimization models. Specifically, SIRL automatically assesses the executable code and the instance-level mathematical model represented by the associated .lp files. This process yields precise feedback on syntactic validity, feasibility, and solution quality, which serves as a direct reward signal to guide the reinforcement learning process. Furthermore, this verification mechanism also supports our instance-enhanced self-consistency method for creating high-quality training data. Extensive experiments on diverse public benchmarks demonstrate that models trained with our SIRL framework achieve state-of-the-art performance, substantially outperforming existing methods in generating accurate and executable optimization models. Specifically, our SIRL-32B model surpasses DeepSeek-V3 and OpenAI-o3 on the majority of these benchmarks. Our code is publicly available at https://github.com/Cardinal-Operations/SIRL.

The alternating-direction-method-of-multipliers-based (ADMM-based) interior point method, or ABIP method, is a hybrid algorithm that effectively combines interior point method (IPM) and first-order methods to achieve a performance boost in large-scale linear optimization. Different from traditional IPM that relies on computationally intensive Newton steps, the ABIP method applies ADMM to approximately solve the barrier penalized problem. However, similar to other first-order methods, this technique remains sensitive to condition number and inverse precision. In this paper, we provide an enhanced ABIP method with multiple improvements. First, we develop an ABIP method to solve the general linear conic optimization and establish the associated iteration complexity. Second, inspired by some existing methods, we develop different implementation strategies for the ABIP method, which substantially improve its performance in linear optimization. Finally, we conduct extensive numerical experiments in both synthetic and real-world data sets to demonstrate the empirical advantage of our developments. In particular, the enhanced ABIP method achieves a 5.8× reduction in the geometric mean of run time on 105 selected linear optimization instances from Netlib, and it exhibits advantages in certain structured problems, such as support vector machine and PageRank. However, the enhanced ABIP method still falls behind commercial solvers in many benchmarks, especially when high accuracy is desired. We posit that it can serve as a complementary tool alongside well-established solvers. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: This research was supported by the National Natural Science Foundation of China [Grants 72394360, 72394364, 72394365, 72225009, 72171141, and 72150001] and by the Program for Innovative Research Team of Shanghai University of Finance and Economics. 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.0017 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0017 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Identifying optimal basic feasible solutions to linear programming problems is a critical task for mixed integer programming and other applications. The crossover method, which aims at deriving an optimal extreme point from a suboptimal solution (the output of a starting method such as interior-point methods or first-order methods), is crucial in this process. This method, compared with the starting method, frequently represents the primary computational bottleneck in practical applications. We propose approaches to overcome this bottleneck by exploiting problem characteristics and implementing customized strategies. For problems arising from network applications and exhibiting network structures, we take advantage of the graph structure of the problem and the tree structure of the optimal solutions. Based on these structures, we propose a tree-based crossover method, aiming to recovering basic solutions by identifying nearby spanning tree structures. For general linear programs, we propose recovering an optimal basic solution by identifying the optimal face and employing controlled perturbations based on the suboptimal solution provided by interior-point methods. We prove that an optimal solution for the perturbed problem is an extreme point, and its objective value is at least as good as that of the initial interior-point solution. Computational experiments show significant speed-ups achieved by our methods compared with state-of-the-art commercial solvers on classical linear programming problem benchmarks, network flow problem benchmarks, and optimal transport problems. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: D. Ge was supported by the National Natural Science Foundation of China [Grants 72150001, 72225009, 72394360, and 72394365]. 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.2022.0291 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0291 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

HDSDP is a numerical software solving semidefinite programming problems. The main framework of HDSDP resembles the dual-scaling interior point solver DSDP and several new features, including a dual method based on the simplified homogeneous self-dual embedding, have been implemented. The embedding technique enhances the stability of the dual method, and several new heuristics and computational techniques are designed to accelerate its convergence. HDSDP aims to show how the dual-scaling algorithm benefits from the self-dual embedding, and it is developed in parallel to DSDP 5.8. Numerical experiments over several classical benchmark datasets exhibit their robustness and efficiency, particularly their advantages on SDP instances featuring low-rank structure and sparsity. HDSDP is open sourced under an MIT license and available at https://github.com/Gwzwpxz/HDSDP .

Linear programming has been practically solved mainly by simplex and interior point methods. Compared with the weakly polynomial complexity obtained by the interior point methods, the existence of strongly polynomial bounds for the length of the pivot path generated by the simplex methods remains a mystery. In this paper, we propose two novel pivot experts that leverage both global and local information of the linear programming instances for the primal simplex method and show their excellent performance numerically. The experts can be regarded as a benchmark to evaluate the performance of classical pivot rules, although they are hard to directly implement. To tackle this challenge, we employ a graph convolutional neural network model, trained via imitation learning, to mimic the behavior of the pivot expert. Our pivot rule, learned empirically, displays a significant advantage over conventional methods in various linear programming problems, as demonstrated through a series of rigorous experiments.

Value Iteration (VI) is one of the most classic algorithms for solving Markov Decision Processes (MDPs), which lays the foundations for various more advanced reinforcement learning algorithms, such as Q-learning. VI may take a large number of iterations to converge as it is a first-order method. In this paper, we introduce the Newton Value Iteration (NVI) algorithm, which eliminates the impact of action space dimension compared to some previous second-order methods. Consequently, NVI can efficiently handle MDPs with large action spaces. Building upon NVI, we propose a novel approach called Sketched Newton Value Iteration (SNVI) to tackle MDPs with both large state and action spaces. SNVI not only inherits the stability and fast convergence advantages of second-order algorithms, but also significantly reduces computational complexity, making it highly scalable. Extensive experiments demonstrate the superiority of our algorithms over traditional VI and previously proposed second-order VI algorithms.

In many important machine learning applications, the standard assumption of having a globally Lipschitz continuous gradient may fail to hold. This paper delves into a more general (L0, L1)-smoothness setting, which gains particular significance within the realms of deep neural networks and distributionally robust optimization (DRO). We demonstrate the significant advantage of trust region methods for stochastic nonconvex optimization under such generalized smoothness assumption. We show that first-order trust region methods can recover the normalized and clipped stochastic gradient as special cases and then provide a unified analysis to show their convergence to first-order stationary conditions. Motivated by the important application of DRO, we propose a generalized high-order smoothness condition, under which second-order trust region methods can achieve a complexity of O(epsilon(-3.5)) for convergence to second-order stationary points. By incorporating variance reduction, the second-order trust region method obtains an even better complexity of O(epsilon(-3)), matching the optimal bound for standard smooth optimization. To our best knowledge, this is the first work to show convergence beyond the first-order stationary condition for generalized smooth optimization. Preliminary experiments show that our proposed algorithms perform favorably compared with existing methods.

Robust Markov Decision Processes (RMDPs) have recently been recognized as a valuable and promising approach to discovering a policy with creditable performance, particularly in the presence of a dynamic environment and estimation errors in the transition matrix due to limited data. Despite extensive exploration of dynamic programming algorithms for solving RMDPs, there has been a notable upswing in interest in developing efficient algorithms using the policy gradient method. In this paper, we propose the first single-loop robust policy gradient (SRPG) method with the global optimality guarantee for solving RMDPs through its minimax formulation. Moreover, we complement the convergence analysis of the nonconvex-nonconcave min-max optimization problem with the objective function’s gradient dominance property, which is not explored in the prior literature. Numerical experiments validate the efficacy of SRPG, demonstrating its faster and more robust convergence behavior compared to its nested-loop counterpart.

Gradient dominance property is a condition weaker than strong convexity, yet sufficiently ensures global convergence even in non-convex optimization. This property finds wide applications in machine learning, reinforcement learning (RL), and operations management. In this paper, we propose the stochastic homogeneous second-order descent method (SHSODM) for stochastic functions enjoying gradient dominance property based on a recently proposed homogenization approach. Theoretically, we provide its sample complexity analysis, and further present an enhanced result by incorporating variance reduction techniques. Our findings show that SHSODM matches the best-known sample complexity achieved by other second-order methods for gradient-dominated stochastic optimization but without cubic regularization. Empirically, since the homogenization approach only relies on solving extremal eigenvector problem at each iteration instead of Newton-type system, our methods gain the advantage of cheaper computational cost and robustness in ill-conditioned problems. Numerical experiments on several RL tasks demonstrate the better performance of SHSODM compared to other off-the-shelf methods.

In real-world reinforcement learning (RL) systems, various forms of impaired observability can complicate matters. These situations arise when an agent is unable to observe the most recent state of the system due to latency or lossy channels, yet the agent must still make real-time decisions. This paper introduces a theoretical investigation into efficient RL in control systems where agents must act with delayed and missing state observations. We present algorithms and establish near-optimal regret upper and lower bounds, of the form$\tilde {\mathcal {O}}(\sqrt {{\mathrm { poly}}(H) SAK})$, for RL in the delayed and missing observation settings. Here S and A are the sizes of state and action spaces, H is the time horizon and K is the number of episodes. Despite impaired observability posing significant challenges to the policy class and planning, our results demonstrate that learning remains efficient, with the regret bound optimally depending on the state-action size of the original system. Additionally, we provide a characterization of the performance of the optimal policy under impaired observability, comparing it to the optimal value obtained with full observability. Numerical results are provided to support our theory.

SOLNP \(+\) is a derivative-free solver for constrained nonlinear optimization. It starts from SOLve Nonlinear Programming (SOLNP) proposed in 1989 by Ye. The main ideas are to use finite difference to approximate the gradient of the objective function and constraints, and use augmented Lagrangian method and sequential quadratic programming to deal with nonlinear constraints. We incorporate the techniques of implicit filtering, a new restart mechanism, and a modern quadratic programming solver into this new version with an ANSI C implementation. The algorithm exhibits a great advantage in running time and robustness under noise compared with the old version implemented in MATLAB. The numerical experiments show that SOLNP \(+\) is comparable with two widely used solvers, COBYLA and NOMAD. SOLNP \(+\) is available at https://github.com/COPT-Public/SOLNP_plus .

This paper presents fast first-order methods for solving linear programs (LPs) approximately. We adapt online linear programming algorithms to offline LPs and obtain algorithms that avoid any matrix multiplication. We also introduce a variable-duplication technique that copies each variable $K$ times and reduces the optimality gap and constraint violation by a factor of $\sqrt{K}$. Furthermore, we show how online algorithms can be effectively integrated into sifting, a column generation scheme for large-scale LPs. Numerical experiments demonstrate that our methods can serve as either an approximate direct solver, or an initialization subroutine for exact LP solving.

In this paper, we study the bandits with knapsacks (BwK) problem and develop a primal-dual based algorithm that achieves a problem-dependent logarithmic regret bound. The BwK problem extends the multi-arm bandit (MAB) problem to model the resource consumption, and the existing BwK literature has been mainly focused on deriving asymptotically optimal distribution-free regret bounds. We first study the primal and dual linear programs underlying the BwK problem. From this primal-dual perspective, we discover symmetry between arms and knapsacks, and then propose a new notion of suboptimality measure for the BwK problem. The suboptimality measure highlights the important role of knapsacks in determining algorithm regret and inspires the design of our two-phase algorithm. In the first phase, the algorithm identifies the optimal arms and the binding knapsacks, and in the second phase, it exhausts the binding knapsacks via playing the optimal arms through an adaptive procedure. Our regret upper bound involves the proposed suboptimality measure and it has a logarithmic dependence on length of horizon $T$ and a polynomial dependence on $m$ (the numbers of arms) and $d$ (the number of knapsacks). To the best of our knowledge, this is the first problem-dependent logarithmic regret bound for solving the general BwK problem.

In this paper we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with discount factor $\gamma\in(0,1)$ we provide an algorithm that computes an $\epsilon$-optimal strategy with high-probability given $\tilde{O}((1 - \gamma)^{-3} \epsilon^{-2})$ samples from the transition function for each state-action-pair. Our algorithm runs in time nearly linear in the number of samples and uses space nearly linear in the number of state-action pairs. As stochastic games generalize Markov decision processes (MDPs) our runtime and sample complexities are optimal due to \cite{azar2013minimax}. We achieve our results by showing how to generalize a near-optimal Q-learning based algorithms for MDP, in particular \cite{sidford2018near}, to two-player strategy computation algorithms. This overcomes limitations of standard Q-learning and strategy iteration or alternating minimization based approaches and we hope will pave the way for future reinforcement learning results by facilitating the extension of MDP results to multi-agent settings with little loss.

We present an extension of the conditional gradient method to problems whose feasible sets are convex cones. We provide a convergence analysis for the method and for variants with nonconvex objectives, and we extend the analysis to practical cases with effective line search strategies. For the specific case of the positive semidefinite cone, we present a memory-efficient version based on randomized matrix sketches and advocate a heuristic greedy step that greatly improves its practical performance. Numerical results on phase retrieval and matrix completion problems indicate that our method can offer substantial advantages over traditional conditional gradient and Burer-Monteiro approaches.

In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in the general resource allocation problem. The algorithm requires only one single pass through the input data and is free of doing any matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs (one-pass) projected stochastic subgradient descent in the dual space. We analyze the algorithm under two different models, stochastic input and random permutation, with minimal technical assumptions on the input data. The algorithm achieves $O\left(m \sqrt{n}\right)$ expected regret under the stochastic input model and $O\left((m+\log n)\sqrt{n}\right)$ expected regret under the random permutation model, and it achieves $O(m \sqrt{n})$ expected constraint violation under both models, where $n$ is the number of decision variables and $m$ is the number of constraints. In addition, we employ the notion of permutational Rademacher complexity and derive regret bounds for two earlier online LP algorithms for comparison. Both algorithms improve the regret bound with a factor of $\sqrt{m}$ by paying more computational cost. Furthermore, we demonstrate how to convert the possibly infeasible solution to a feasible one through a randomized procedure. Numerical experiments illustrate the general applicability and effectiveness of the algorithms.

Conditional estimation given specific covariate values (i.e., local conditional estimation or functional estimation) is ubiquitously useful with applications in engineering, social and natural sciences. Existing data-driven non-parametric estimators mostly focus on structured homogeneous data (e.g., weakly independently and stationary data), thus they are sensitive to adversarial noise and may perform poorly under a low sample size. To alleviate these issues, we propose a new distributionally robust estimator that generates non-parametric local estimates by minimizing the worst-case conditional expected loss over all adversarial distributions in a Wasserstein ambiguity set. We show that despite being generally intractable, the local estimator can be efficiently found via convex optimization under broadly applicable settings, and it is robust to the corruption and heterogeneity of the data. Various experiments show the competitive performance of this new class of estimator.

We describe the background and an analytical framework for a mathematical optimization model for home energy management systems (HEMS) to manage electricity demand on the smart grid by efficiently shifting electricity loads of households from peak times to off-peak times. We illustrate the flexibility of the model by modularizing various available technologies such as plug-in electric vehicles, battery storage, and automatic windows. First, the analysis shows that the end-user can accrue economic benefits by shifting consumer loads away from higher-priced periods. Specifically, we assessed the most likely sources of value to be derived from demand response technologies. Therefore, wide adoption of such modeling could create significant cost savings for consumers. Second, the findings are promising for the further development of more intelligent HEMS in the residential sector. Third, we formulated a smart grid valuation framework that is helpful for interpreting the model's results concerning the efficiency of current smart appliances and their respective prices. Finally, we explain the model's benefits, the major concerns when the model is applied in the real world, and the possible future areas that can be explored.

Computing the Wasserstein barycenter of a set of probability measures under the optimal transport metric can quickly become prohibitive for traditional second-order algorithms, such as interior-point methods, as the support size of the measures increases. In this paper, we overcome the difficulty by developing a new adapted interior-point method that fully exploits the problem's special matrix structure to reduce the iteration complexity and speed up the Newton procedure. Different from regularization approaches, our method achieves a well-balanced tradeoff between accuracy and speed. A numerical comparison on various distributions with existing algorithms exhibits the computational advantages of our approach. Moreover, we demonstrate the practicality of our algorithm on image benchmark problems including MNIST and Fashion-MNIST.

In this paper, we consider three typical optimization problems with a convex loss function and a nonconvex sparse penalty or constraint. For the sparse penalized problem, we prove that finding an $\mathcal{O}(n^{c_1}d^{c_2})$-optimal solution to an $n\times d$ problem is strongly NP-hard for any $c_1, c_2\in [0,1)$ such that $c_1+c_2<1$. For two constrained versions of the sparse optimization problem, we show that it is intractable to approximately compute a solution path associated with increasing values of some tuning parameter. The hardness results apply to a broad class of loss functions and sparse penalties. They suggest that one cannot even approximately solve these three problems in polynomial time, unless P $=$ NP.

One of the most widely used optimization methods for large-scale machine learning problems is distributed asynchronous stochastic gradient descent (DASGD). However, a key issue that arises here is that of delayed gradients: when a “worker” node asynchronously contributes a gradient update to the “master”, the global model parameter may have changed, rendering this information stale. In massively parallel computing grids, these delays can quickly add up if the computational throughput of a node is saturated, so the convergence of DASGD is uncertain under these conditions. Nevertheless, by using a judiciously chosen quasilinear step-size sequence, we show that it is possible to amortize these delays and achieve global convergence with probability 1, even when the delays grow at a polynomial rate. In this way, our results help reaffirm the successful application of DASGD to large-scale optimization problems.

In this paper we consider the problem of computing an $\epsilon$-optimal policy of a discounted Markov Decision Process (DMDP) provided we can only access its transition function through a generative sampling model that given any state-action pair samples from the transition function in $O(1)$ time. Given such a DMDP with states $\states$, actions $\actions$, discount factor $\gamma\in(0,1)$, and rewards in range $[0, 1]$ we provide an algorithm which computes an $\epsilon$-optimal policy with probability $1 - \delta$ where {\it both} the run time spent and number of sample taken is upper bounded by \[ O\left[\frac{|\cS||\cA|}{(1-\gamma)^3 \epsilon^2} \log \left(\frac{|\cS||\cA|}{(1-\gamma)\delta \epsilon} \right) \log\left(\frac{1}{(1-\gamma)\epsilon}\right)\right] ~. \] For fixed values of $\epsilon$, this improves upon the previous best known bounds by a factor of $(1 - \gamma)^{-1}$ and matches the sample complexity lower bounds proved in \cite{azar2013minimax} up to logarithmic factors. We also extend our method to computing $\epsilon$-optimal policies for finite-horizon MDP with a generative model and provide a nearly matching sample complexity lower bound.

We consider a game-theoretical multi-agent learning problem where the feedback information can be lost during the learning process and rewards are given by a broad class of games known as variationally stable games. We propose a simple variant of the classical online gradient descent algorithm, called reweighted online gradient descent (ROGD) and show that in variationally stable games, if each agent adopts ROGD, then almost sure convergence to the set of Nash equilibria is guaranteed, even when the feedback loss is asynchronous and arbitrarily corrrelated among agents. We then extend the framework to deal with unknown feedback loss probabilities by using an estimator (constructed from past data) in its replacement. Finally, we further extend the framework to accomodate both asynchronous loss and stochastic rewards and establish that multi-agent ROGD learning still converges to the set of Nash equilibria in such settings. Together, these results contribute to the broad lanscape of multi-agent online learning by significantly relaxing the feedback information that is required to achieve desirable outcomes.

In this paper we provide faster algorithms for approximately solving discounted Markov Decision Processes in multiple parameter regimes. Given a discounted Markov Decision Process (DMDP) with |S| states, |A| actions, discount factor γ ∊ (0, 1), and rewards in the range [–M, M], we show how to compute an ∊-optimal policy, with probability 1 – δ in time This contribution reflects the first nearly linear time, nearly linearly convergent algorithm for solving DMDP's for intermediate values of γ. We also show how to obtain improved sublinear time algorithms and provide an algorithm which computes an ∊-optimal policy with probability 1 – δ in time provided we can sample from the transition function in O(1) time. Interestingly, we obtain our results by a careful modification of approximate value iteration. We show how to combine classic approximate value iteration analysis with new techniques in variance reduction. Our fastest algorithms leverage further insights to ensure that our algorithms make monotonic progress towards the optimal value. This paper is one of few instances in using sampling to obtain a linearly convergent linear programming algorithm and we hope that the analysis may be useful more broadly.

Consider the regularized sparse minimization problem, which involves empirical sums of loss functions for $n$ data points (each of dimension $d$) and a nonconvex sparsity penalty. We prove that finding an $\mathcal{O}(n^{c_1}d^{c_2})$-optimal solution to the regularized sparse optimization problem is strongly NP-hard for any $c_1, c_2\in [0,1)$ such that $c_1+c_2<1$. The result applies to a broad class of loss functions and sparse penalty functions. It suggests that one cannot even approximately solve the sparse optimization problem in polynomial time, unless P $=$ NP.

Acoustic source localization has many important applications. Convex relaxation provides a viable approach of obtaining good estimates very efficiently. There are two popular convex relaxation methods using either semi-definite programming (SDP) or second-order cone programming (SOCP). However, the performances of the methods have not been studied properly in the literature and there is no comparison in terms of accuracy and performance. The aims of this article are twofold. First of all, we study and compare several convex relaxation methods. We demonstrate, by numerical examples, that most of the convex relaxation methods cannot localize the source exactly, even in the performance limit when the time difference of arrival (TDOA) information is exact. In addressing this problem, we propose a novel mixed SDP-SOCP relaxation model and study the characteristics of the optimal solutions and its localizable region. Furthermore, an error correction scheme for the proposed SDP-SOCP model is developed so that exact localization can be achieved in the performance limit. Experimental data have been collected in a room with two different array configurations to demonstrate our proposed approach.

The successful deployment and operation of location-aware networks, which have recently found many applications, depends crucially on the accurate localization of the nodes. Currently, a powerful approach to localization is that of convex relaxation. In a typical application of this approach, the localization problem is first formulated as a rank-constrained semidefinite program (SDP), where the rank corresponds to the target dimension in which the nodes should be localized. Then, the non-convex rank constraint is either dropped or replaced by a convex surrogate, thus resulting in a convex optimization problem. In this paper, we explore the use of a non-convex surrogate of the rank function, namely the so-called Schatten quasi- norm, in network localization. Although the resulting optimization problem is non-convex, we show, for the first time, that a first- order critical point can be approximated to arbitrary accuracy in polynomial time by an interior-point algorithm. Moreover, we show that such a first-order point is already sufficient for recovering the node locations in the target dimension if the input instance satisfies certain established uniqueness properties in the literature. Finally, our simulation results show that in many cases, the proposed algorithm can achieve more accurate localization results than standard SDP relaxations of the problem.

We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n3m2 log2 n) iterations if the discount factor is uniform and O(n5m3 log2 n) iterations if each action has a distinct discount factor. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from 1 [Ye11]. Unlike in the discounted case, the algorithm does not greedily converge to the optimum, and we require a more complex measure of progress. We identify a set of layers in which the values of primal variables must lie and show that the simplex method always makes progress optimizing one layer, and when the upper layer is updated the algorithm makes a substantial amount of progress. In the case of nonuniform discounts, we define a polynomial number of “milestone” policies and we prove that, while the objective function may not improve substantially overall, the value of at least one dual variable is always making progress towards some milestone, and the algorithm will reach the next milestone in a polynomial number of steps.

Abstract Finding an informative, structure‐preserving map between two shapes has been a long‐standing problem in geometry processing, involving a variety of solution approaches and applications. However, in many cases, we are given not only two related shapes, but a collection of them, and considering each pairwise map independently does not take full advantage of all existing information. For example, a notorious problem with computing shape maps is the ambiguity introduced by the symmetry problem — for two similar shapes which have reflectional symmetry there exist two maps which are equally favorable, and no intrinsic mapping algorithm can distinguish between them based on these two shapes alone. Another prominent issue with shape mapping algorithms is their relative sensitivity to how “similar” two shapes are — good maps are much easier to obtain when shapes are very similar. Given the context of additional shape maps connecting our collection, we propose to add the constraint of global map consistency, requiring that any composition of maps between two shapes should be independent of the path chosen in the network. This requirement can help us choose among the equally good symmetric alternatives, or help us replace a “bad” pairwise map with the composition of a few “good” maps between shapes that in some sense interpolate the original ones. We show how, given a collection of pairwise shape maps, to define an optimization problem whose output is a set of alternative maps, compositions of those given, which are consistent, and individually at times much better than the original. Our method is general, and can work on any collection of shapes, as long as a seed set of good pairwise maps is provided. We demonstrate the effectiveness of our method for improving maps generated by state‐of‐the‐art mapping methods on various shape databases.

A fundamental problem in wireless ad-hoc and sensor networks is that of determining the positions of nodes. Often, such a problem is complicated by the presence of nodes whose positions cannot be uniquely determined. Most existing work uses the notion of global rigidity from rigidity theory to address the non-uniqueness issue. However, such a notion is not entirely satisfactory, as it has been shown that even if a network localization instance is known to be globally rigid, the problem of determining the node positions is still intractable in general. In this paper, we propose to use the notion of universal rigidity to bridge such disconnect. Although the notion of universal rigidity is more restrictive than that of global rigidity, it captures a large class of networks and is much more relevant to the efficient solvability of the network localization problem. Specifically, we show that both the problem of deciding whether a given network localization instance is universally rigid and the problem of determining the node positions of a universally rigid instance can be solved efficiently using semidefinite programming (SDP). Then, we give various constructions of universally rigid instances. In particular, we show that trilateration graphs are generically universally rigid, thus demonstrating not only the richness of the class of universally rigid instances, but also the fact that trilateration graphs possess much stronger geometric properties than previously known. Finally, we apply our results to design a novel edge sparsification heuristic that can reduce the size of the input network while provably preserving its original localization properties. One of the applications of such heuristic is to speed up existing convex optimization-based localization algorithms. Simulation results show that our speedup approach compares very favorably with existing ones, both in terms of accuracy and computation time.

We consider a robust model proposed by Scarf, 1958, for stochastic optimization when only the marginal probabilities of (binary) random variables are given, and the correlation between the random variables is unknown. In the robust model, the objective is to minimize expected cost against worst possible joint distribution with those marginals. We introduce the concept of correlation gap to compare this model to the stochastic optimization model that ignores correlations and minimizes expected cost under independent Bernoulli distribution. We identify a class of functions, using concepts of summable cost sharing schemes from game theory, for which the correlation gap is well-bounded and the robust model can be approximated closely by the independent distribution model. As a result, we derive efficient approximation factors for many popular cost functions, like submodular functions, facility location, and Steiner tree. As a byproduct, our analysis also yields some new results in the areas of social welfare maximization and existence of Walrasian equilibria, which may be of independent interest.

Previous work has developed algorithms for finding an equitable convex partition that partitions the plane into n convex pieces each containing an equal number of red and blue points. Motivated by a vehicle routing heuristic, we look at a related problem where each piece must contain one point and an equal fraction of the area of some convex polygon. We first show how algorithms for solving the older problem lead to approximate solutions for this new equitable convex partition problem. Then we demonstrate a new algorithm that finds an exact solution to our problem in O ( N n log N ) time or operations, where n is the number of points, m the number of vertices or edges of the polygon, and N := n + m the sum.

Recently, coinciding with and perhaps driving the increased popularity of prediction markets, several novel pari-mutuel mechanisms have been developed such as the logarithmic market scoring rule (LMSR), the cost-function formulation of market makers, and the sequential convex parimutuel mechanism (SCPM). In this work, we present a unified convex optimization framework which connects these seemingly unrelated models for centrally organizing contingent claims markets. The existing mechanisms can be expressed in our unified framework using classic utility functions. We also show that this framework is equivalent to a convex risk minimization model for the market maker. This facilitates a better understanding of the risk attitudes adopted by various mechanisms. The utility framework also leads to easy implementation since we can now find the useful cost function of a market maker in polynomial time through the solution of a simple convex optimization problem.

DSDP implements the dual-scaling algorithm for semidefinite programming. The source code for this interior-point algorithm, written entirely in ANSI C, is freely available under an open source license. The solver can be used as a subroutine library, as a function within the Matlab environment, or as an executable that reads and writes to data files. Initiated in 1997, DSDP has developed into an efficient and robust general-purpose solver for semidefinite programming. Its features include a convergence proof with polynomially bounded worst-case complexity, primal and dual feasible solutions when they exist, certificates of infeasibility when solutions do not exist, initial points that can be feasible or infeasible, relatively low memory requirements for an interior-point method, sparse and low-rank data structures, extensibility that allows applications to customize the solver and improve its performance, a subroutine library that enables it to be linked to larger applications, scalable performance for large problems on parallel architectures, and a well-documented interface and examples of its use. The package has been used in many applications and tested for efficiency, robustness, and ease of use.

We consider the problem of computing the outer‐radii of point sets. In this problem, we are given integers $n, d$, and k, where $k \le d$, and a set P of n points in $\Re^d$. The goal is to compute the outer k‐radius of P, denoted by ${\cal R}_k(P)$, which is the minimum over all $(d-k)$‐dimensional flats F of $\max_{p \in P} d(p,F)$, where $d(p,F)$ is the Euclidean distance between the point p and flat F. Computing the radii of point sets is a fundamental problem in computational convexity with many significant applications. The problem admits a polynomial time algorithm when the dimension d is constant [U. Faigle, W. Kern, and M. Streng, Math. Program., 73 (1996), pp. 1–5]. Here we are interested in the general case in which the dimension d is not fixed and can be as large as n, where the problem becomes NP‐hard even for $k=1$. It is known that $R_k(P)$ can be approximated in polynomial time by a factor of $(1 + \varepsilon)$ for any $\varepsilon > 0$ when $d - k$ is a fixed constant [M. Bădoiu, S. Har‐Peled, and P. Indyk, in Proceedings of the ACM Symposium on the Theory of Computing, 2002; S. Har‐Peled and K. Varadarajan, in Proceedings of the ACM Symposium on Computing Geometry, 2002]. A polynomial time algorithm that guarantees a factor of $O(\sqrt{\log n})$ approximation for $R_1(P)$, the width of the point set P, is implied by the results of Nemirovski, Roos, and Terlaky [Math. Program., 86 (1999), pp. 463–473] and Nesterov [Handbook of Semidefinite Programming Theory, Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000]. In this paper, we show that $R_k(P)$ can be approximated by a ratio of $O(\sqrt{\log n})$ for any $1 \leq k \leq d$, thus matching the previously best known ratio for approximating the special case $R_1 (P)$, the width of point set P. Our algorithm is based on semidefinite programming relaxation with a new mixed deterministic and randomized rounding procedure. We also prove an inapproximability result that gives evidence that our approximation algorithm is doing well for a large range of k. We show that there exists a constant $\delta > 0$ such that the following holds for any $0 < \eps < 1$: there is no polynomial time algorithm that approximates $R_k(P)$ within $(\log n)^{\delta}$ for all k such that $k \leq d - d^{\varepsilon}$ unless NP $\subseteq$ DTIME $[2^{(\log m)^{O(1)}}]$. Our inapproximability result for $R_k(P)$ extends a previously known hardness result of Brieden [Discrete Comput. Geom., 28 (2002), pp. 201–209] and is proved by modifying Brieden’s construction using basic ideas from probabilistically checkable proofs (PCP) theory.

In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities. Both these algorithms improve the best previously known approximation factor for the corresponding problem, and our soft-capacitated facility location algorithm achieves the integrality gap of the standard linear programming relaxation of the problem. Furthermore, we will show, using a result of Thorup, that our algorithms can be implemented in quasi-linear time.

A sensor network localization problem is to determine the positions of the sensor nodes in a network given incomplete and inaccurate pairwise distance measurements. Such distance data may be acquired by a sensor node by communicating with its neighbors. We describe a general semidefinite programming (SDP)-based approach for solving the graph realization problem, of which the sensor network localization problems is a special case. We investigate the performance of this method on problems with noisy distance data. Error bounds are derived from the SDP formulation. The sources of estimation error in the SDP formulation are identified. The SDP solution usually has a rank higher than the underlying physical space which, when projected onto the lower dimensional space, generally results in high estimation error. We describe two improvements to ameliorate such a difficulty. First, we propose a regularization term in the objective function that can help to reduce the rank of the SDP solution. Second, we use the points estimated from the SDP solution as the initial iterate for a gradient-descent method to further refine the estimated points. A lower bound obtained from the optimal SDP objective value can be used to check the solution quality. Experimental results are presented to validate our methods and show that they outperform existing SDP methods. Note to Practitioners—Wireless sensor networks consist of a large number of inexpensive wireless sensors deployed in a geographical area with the ability to communicate with their neighbors within a limited radio range. Wireless sensor networks are finding increasing applicability to a range of monitoring applications in civil and military scenarios, such as biodiversity and geographical monitoring, smart homes, industrial control, surveillance, and traffic monitoring. It is often very useful in the applications of sensor networks to know the locations of the sensors. Global positioning systems suffer from many drawbacks in this scenario, such as high cost, line-of-sight issues, etc. Therefore, there is a need to develop robust and efficient algorithms that can estimate or “localize” sensor positions in a network by using only the mutual distance measures (received signal strength, time of arrival) that the wireless sensors receive from their neighbors. This paper describes an algorithm that solves the sensor network localization problem using advanced optimization techniques. We also study the effect of using very noisy measurements and propose robust methods to deal with high noise. Finally, simulation results for the algorithms are presented to demonstrate their performance in terms of computational effort and accuracy.

An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite program that can be solved efficiently.The basic model is extended in order to account for noisy distance information. In particular, a maximum likelihood based formulation and an interval based formulation are discussed. The SDP solution can then also be used as a starting point for steepest descent based local optimization techniques that can further refine the SDP solution.We also describe the extension of the basic method to develop an iterative distributed SDP method for solving very large scale semidefinite programs that arise out of localization problems for large dense networks and are intractable using centralized methods.The performance evaluation of the technique with regard to estimation accuracy and computation time is also presented by the means of extensive simulations.Our SDP scheme also seems to be applicable to solving other Euclidean geometry problems where points are locally connected.

We describe an SDP relaxation based method for the position estimation problem in wireless sensor networks. The optimization problem is set up so as to minimize the error in sensor positions to fit distance measures. Observable gauges are developed to check the quality of the point estimation of sensors or to detect erroneous sensors. The performance of this technique is highly satisfactory compared to other techniques. Very few anchor nodes are required to accurately estimate the position of all the unknown nodes in a network. Also the estimation errors are minimal even when the anchor nodes are not suitably placed within the network or the distance measurements are noisy.

In this paper we present improved combinatorial approximation algorithms for the k-level facility location problem. First, by modifying the path reduction developed in [A. A. Ageev, Oper. Res. Lett., 30 (2002), pp. 327--332], we obtain a combinatorial algorithm with a performance factor of 3.27 for any k \ge 2, thus improving the previous bound of 4.56 achieved by a combinatorial algorithm. Then we develop another combinatorial algorithm that has a better performance guarantee and uses the first algorithm as a subroutine. The latter algorithm can be recursively implemented and achieves a guarantee factor h(k), where h(k) is strictly less than 3.27 for any k and tends to 3.27 as k goes to $\infty$. The values of h(k) can be easily computed with an arbitrary accuracy: h(2)\approx 2.4211, h(3)\approx 2.8446, h(4)\approx 3.0565, h(5)\approx 3.1678, and so on. Thus, for the cases of k=2 and k=3 the second combinatorial algorithm ensures an approximation factor substantially better than 3, which is currently the best approximation ratio for the k-level problem provided by the noncombinatorial algorithm due to Aardal, Chudak, and Shmoys [Inform. Process. Lett., 72 (1999), pp. 161--167].

The so-called analytic center approach to parameter estimation has been proposed as an alternative to the well-known least squares approach. This new approach offers a parameter estimate that is consistent with the past data observations, has a simple geometric interpretation, and is computable sequentially. We study the asymptotic performance of the analytic center approach and show that the resulting estimate converges to the true parameter asymptotically, provided some mild conditions are satisfied. These conditions involve some weak persistent excitation and independence between noise and regressor, similar to the least squares case. This result is used to derive a new parameter estimation approach which offers both good transient and asymptotic performance.

A class of projective transformations under which potential functions are invariant for linear programming is described. As a result, a new projective algorithm converging in $O(L\sqrt n)$ iterations is developed. The algorithm does not require centering conditions, and its convergence speed is improved by a factor $\sqrt n $ over Karmarkar’s projective algorithm and by a constant over the recent affine potential reduction algorithm.