More Like this

1. Solving Non-smooth Constrained Programs with Lower Complexity than O(1/ε): A Primal-Dual Homotopy Smoothing Approach

   Wei, Xiaohan; Yu, Hao; Ling, Qing; Neely, Michael J. (December 2018, 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada.)

   We propose a new primal-dual homotopy smoothing algorithm for a linearly constrained convex program, where neither the primal nor the dual function has to be smooth or strongly convex. The best known iteration complexity solving such a non-smooth problem is O(ε−1). In this paper, we show that by leveraging a local error bound condition on the dual function, the proposed algorithm can achieve a better primal convergence time of O 􏰕ε−2/(2+β) log2(ε−1)􏰖, where β ∈ (0, 1] is a local error bound parameter. As an example application of the general algorithm, we show that the distributed geometric median problem, which can be formulated as a constrained convex program, has its dual function non-smooth but satisfying the aforementioned local error bound condition with β = 1/2, therefore enjoying a convergence time of O 􏰕ε−4/5 log2(ε−1)􏰖. This result improves upon the O(ε−1) convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm. 

   more » « less
2. Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization

   https://doi.org/10.1609/aaai.v38i8.28662  

   Zhang, Qi; Zhou, Yi; Prater-Bennette, Ashley; Shen, Lixin; Zou, Shaofeng (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   Distributionally robust optimization (DRO) is a powerful framework for training robust models against data distribution shifts. This paper focuses on constrained DRO, which has an explicit characterization of the robustness level. Existing studies on constrained DRO mostly focus on convex loss function, and exclude the practical and challenging case with non-convex loss function, e.g., neural network. This paper develops a stochastic algorithm and its performance analysis for non-convex constrained DRO. The computational complexity of our stochastic algorithm at each iteration is independent of the overall dataset size, and thus is suitable for large-scale applications. We focus on the general Cressie-Read family divergence defined uncertainty set which includes chi^2-divergences as a special case. We prove that our algorithm finds an epsilon-stationary point with an improved computational complexity than existing methods. Our method also applies to the smoothed conditional value at risk (CVaR) DRO. 

   more » « less
3. Data-driven proximal algorithms for the design of structured optimal feedback gains

   https://doi.org/10.23919/ACC.2019.8815365  

   Hassan-Moghaddam, Sepideh; Jovanovic, Mihailo R.; Meyn, Sean (July 2019, 2019 American Control Conference (ACC))

   Distributed feedback design and complexity constrained control are examples of problems posed within the domain of structured optimal feedback synthesis. The optimal feedback gain is typically a non-convex function of system primitives. However, in recent years, algorithms have been proposed to obtain locally optimal solutions. In applications to large-scale distributed control, the major obstacle is computational complexity. This paper addresses complexity through a combination of linear-algebraic techniques and computational methods adapted from both machine learning and reinforcement learning. It is shown that for general classes of optimal control problems, the objective function and its gradient can be computed from data. Transformations borrowed from the theory of reinforcement learning are adapted to obtain simulation-based algorithms for computing the structured optimal H2 feedback gain. Customized proximal algorithms based on gradient descent and incremental gradient are tested in computational experiments and their relative merits are discussed. 

   more » « less
4. Guaranteeing a physically realizable battery dispatch without charge-discharge complementarity constraints

   https://doi.org/10.1109/TSG.2021.3109805  

   Nazir, Nawaf; Almassalkhi, Mads (September 2021, IEEE Transactions on Smart Grid)

   The non-convex complementarity constraints present a fundamental computational challenge in energy constrained optimization problems. In this work, we present a new, linear, and robust battery optimization formulation that sidesteps the need for battery complementarity constraints and integers and prove analytically that the formulation guarantees that all energy constraints are satisfied which ensures that the optimized battery dispatch is physically realizable. In addition, we bound the worst-case model mismatch and discuss conservativeness. Simulation results further illustrate the effectiveness of this approach. 

   more » « less
5. "Constrained Subspace Estimation via Convex Optimization"

   Santamaria, I.; Via, J.; Kirby, M.; Marrinan, T.; Peterson, C.; Scharf, L. (September 2017, EUSIPCO ...)

   Abstract—Given a collection of M experimentally measured subspaces, and a model-based subspace, this paper addresses the problem of finding a subspace that approximates the collection, under the constraint that it intersects the model-based subspace in a predetermined number of dimensions. This constrained subspace estimation (CSE) problem arises in applications such as beamforming, where the model-based subspace encodes prior information about the direction-of-arrival of some sources impinging on the array. In this paper, we formulate the constrained subspace estimation (CSE) problem, and present an approximation based on a semidefinite relaxation (SDR) of this non-convex problem. The performance of the proposed CSE algorithm is demonstrated via numerical simulation, and its application to beamforming is also discussed. 

   more » « less