More Like this

1. Inequality constrained stochastic nonlinear optimization via active-set sequential quadratic programming

   https://doi.org/10.1007/s10107-023-01935-7  

   Na, Sen ; Anitescu, Mihai ; Kolar, Mladen ( March 2023 , Mathematical Programming)

   We study nonlinear optimization problems with a stochastic objective and deterministic equality and inequality constraints, which emerge in numerous applications including finance, manufacturing, power systems and, recently, deep neural networks. We propose an active-set stochastic sequential quadratic programming (StoSQP) algorithm that utilizes a differentiable exact augmented Lagrangian as the merit function. The algorithm adaptively selects the penalty parameters of the augmented Lagrangian, and performs a stochastic line search to decide the stepsize. The global convergence is established: for any initialization, the KKT residuals converge to zeroalmost surely. Our algorithm and analysis further develop the prior work of Na et al. (Math Program, 2022.https://doi.org/10.1007/s10107-022-01846-z). Specifically, we allow nonlinear inequality constraintswithoutrequiring the strict complementary condition; refine some of designs in Na et al. (2022) such as the feasibility error condition and the monotonically increasing sample size; strengthen the global convergence guarantee; and improve the sample complexity on the objective Hessian. We demonstrate the performance of the designed algorithm on a subset of nonlinear problems collected in CUTEst test set and on constrained logistic regression problems.

    

   more » « less
2. A Parallel Approximation Algorithm for Maximizing Submodular b-Matching

   https://doi.org/10.1137/1.9781611976830.5  

   Ferdous, S ; Pothen, A ; Khan, A. ; Panyala, A. ; Halappanavar, M. ( August 2021 , Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21))

   Bender, M. ; Gilbert, J. ; Hendrickson, B. ; Sullivan, B. (Ed.)

   We design new serial and parallel approximation algorithms for computing a maximum weight b-matching in an edge-weighted graph with a submodular objective function. This problem is NP-hard; the new algorithms have approximation ratio 1/3, and are relaxations of the Greedy algorithm that rely only on local information in the graph, making them parallelizable. We have designed and implemented Local Lazy Greedy algorithms for both serial and parallel computers. We have applied the approximate submodular b-matching algorithm to assign tasks to processors in the computation of Fock matrices in quantum chemistry on parallel computers. The assignment seeks to reduce the run time by balancing the computational load on the processors and bounding the number of messages that each processor sends. We show that the new assignment of tasks to processors provides a four fold speedup over the currently used assignment in the NWChemEx software on 8000 processors on the Summit supercomputer at Oak Ridge National Lab. 

   more » « less
3. Structure and Long-Term Stability of the Microbiome in Diverse Diatom Cultures

   https://doi.org/10.1128/Spectrum.00269-21  

   Barreto Filho, Marcelo Malisano ; Walker, Melissa ; Ashworth, Matt P. ; Morris, J. Jeffrey ( September 2021 , Microbiology Spectrum)

   Gralnick, Jeffrey A. (Ed.)

   ABSTRACT Microalgal cultures are often maintained in xenic conditions, i.e., with associated bacteria, and many studies indicate that these communities both are complex and have significant impacts on the physiology of the target photoautotroph. Here, we investigated the structure and stability of microbiomes associated with a diverse sampling of diatoms during long-term maintenance in serial batch culture. We found that, counter to our initial expectation, evenness diversity increased with time since cultivation, driven by a decrease in dominance by the most abundant taxa in each culture. We also found that the site from which and time at which a culture was initially collected had a stronger impact on microbiome structure than the diatom species; however, some bacterial taxa were commonly present in most cultures despite having widely geographically separated collection sites. Our results support the conclusion that stochastic initial conditions (i.e., the local microbial community at the collection site) are important for the long-term structure of these microbiomes, but deterministic forces such as negative frequency dependence and natural selection exerted by the diatom are also at work. IMPORTANCE Natural microbial communities are extremely complex, with many more species coexisting in the same place than there are different resources to support them. Understanding the forces that allow this high level of diversity has been a central focus of ecological and evolutionary theory for many decades. Here, we used stock cultures of diatoms, which were maintained for years in continuous growth alongside populations of bacteria, as proxies for natural communities. We show that the bacterial communities remained relatively stable for years, and there is evidence that ecological forces worked to stabilize coexistence instead of favoring competition and exclusion. We also show evidence that, despite some important regional differences in bacterial communities, there was a globally present core microbiome potentially selected for in these diatom cultures. Understanding interactions between bacteria and diatoms is important both for basic ecological science and for practical science, such as industrial biofuel production. 

   more » « less
4. A global algorithm for AC optimal power flow based on successive linear conic optimization

   https://doi.org/10.1109/PESGM.2017.8273957  

   Barati, Masoud ; Kargarian, Amin ( July 2017 , 2017 IEEE Power & Energy Society General Meeting)

   Newly, there has been significant research interest in the exact solution of the AC optimal power flow (AC-OPF) problem. A semideflnite relaxation solves many OPF problems globally. However, the real problem exists in which the semidefinite relaxation fails to yield the global solution. The appropriation of relaxation for AC-OPF depends on the success or unfulflllment of the SDP relaxation. This paper demonstrates a quadratic AC-OPF problem with a single negative eigenvalue in objective function subject to linear and conic constraints. The proposed solution method for AC-OPF model covers the classical AC economic dispatch problem that is known to be NP-hard. In this paper, by combining successive linear conic optimization (SLCO), convex relaxation and line search technique, we present a global algorithm for AC-OPF which can locate a globally optimal solution to the underlying AC-OPF within given tolerance of global optimum solution via solving linear conic optimization problems. The proposed algorithm is examined on modified IEEE 6-bus test system. The promising numerical results are described. 

   more » « less
5. A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear-Equality-Constrained Optimization with Rank-Deficient Jacobians

   https://doi.org/10.1287/moor.2021.0154  

   Berahas, Albert S. ; Curtis, Frank E. ; O’Neill, Michael J. ; Robinson, Daniel P. ( October 2023 , Mathematics of Operations Research)

   A sequential quadratic optimization algorithm is proposed for solving smooth nonlinear-equality-constrained optimization problems in which the objective function is defined by an expectation. The algorithmic structure of the proposed method is based on a step decomposition strategy that is known in the literature to be widely effective in practice, wherein each search direction is computed as the sum of a normal step (toward linearized feasibility) and a tangential step (toward objective decrease in the null space of the constraint Jacobian). However, the proposed method is unique from others in the literature in that it both allows the use of stochastic objective gradient estimates and possesses convergence guarantees even in the setting in which the constraint Jacobians may be rank-deficient. The results of numerical experiments demonstrate that the algorithm offers superior performance when compared with popular alternatives. 

   more » « less