Search NASA⌕ Search

SEARCH · Search NASA

Results for “Semidefinite optimization”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Quantum Interior Point Methods for Semidefinite Optimization

We present two quantum interior point methods for semidefinite optimization problems, building on recent advances in quantum linear system algorithms. The first scheme, more similar to a classical solution algorithm, computes an inexact search direction and is not guaranteed to explore only feasible points; the second scheme uses a nullspace representation of the Newton linear system to ensure feasibility even with inexact search directions. The second is a novel scheme that might seem impractical in the classical world, but it is well-suited for a hybrid quantum-classical setting. We show that both schemes converge to an optimal solution of the semidefinite optimization problem under standard assumptions. By comparing the theoretical performance of classical and quantum interior point methods with respect to various input parameters, we show that our second scheme obtains a speedup over classical algorithms in terms of the dimension of the problem n , but has worse dependence on other numerical parameters.

Augustino, Brandon↗
DOE OSTI2023

On relaxations of the max k -cut problem formulations

Here, a tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Flexible dynamic boundary microgrid operation considering network and load unbalances

Flexible microgrids with dynamic boundaries have recently been introduced in the literature. With the ability to reconfigure the topology of the microgrids dynamically through remotely controlled switches, flexible microgrids with dynamic boundaries can further improve the resiliency and energy efficiency of microgrids with distributed energy resources (DERs). This paper focuses on the optimal operation considering one of the predominant characteristics of microgrids and distribution systems – unbalanced networks and loads. In existing literature, balanced modeling of microgrids is more common due to its attractive simplicity. The three-phase power unbalance has not been considered as a constraint on the generation units in a microgrid. Further, negative sequence constraints have also been neglected. In this article, we propose a set of constraints that is specifically related to the capabilities of inverter interfaced resources to supply unbalanced current/power when the microgrid is islanded from the main distribution grid. We incorporate the new set of constraints into two optimization formulations leveraging two convex relaxations of the three-phase power flow equations: mixed-integer linear programming (MILP) and mixed-integer semidefinite programming (MISDP) that optimize the dispatch of controllable switches and DERs in the microgrid. The algorithms are then extended to networked microgrids with grid-forming sources. We test the algorithms on a realistic community microgrid model in Puerto Rico as well as standardized IEEE distribution test feeders. The testing results demonstrate the performance of the proposed algorithms. The MILP is fast and scalable, and the MISDP enforces the negative sequence voltage constraints.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

Virtual-Voltage Partition-Based Approach to Optimal Transmission Switching

This article deals with optimal transmission switching (OTS) problems involving binary decisions about network topology and nonconvex power flow constraints. We adopt a semidefinite programming formulation for the optimal power flow (OPF) problem that, however, remains nonconvex due to the presence of discrete variables and bilinear products between the decision variables. To tackle the latter, we introduce a physically inspired, virtual-voltage approximation that leads to provable lower and upper bounds on the solution of the original problem. To deal with the exponential complexity caused by the discrete variables, we introduce a graph partition-based algorithm that breaks the problem into several parallel mixed-integer subproblems of smaller size. Simulations on the IEEE bus test cases demonstrate the high degree of accuracy and affordable computational requirements of our approach.

42 ENGINEERING↗
DOE OSTI2019

Distributionally robust polynomial chance-constraints under mixture ambiguity sets

Given $\mathrm{X}\subset\mathbb{R}^n, ε \in (0,1)$, a parametrized family of probability distributions $(μ_a)_{a\in \mathrm{A}}$ on $\mathrm{Ω}\subset \mathbb{R}^p$, we consider the feasible set $\mathrm{X}^*_ε \subset\mathrm{X}$ associated with the distributionally robust chance-constraint $\mathrm{X}^*_ε = \mathrm{x \in X : Prob}_μ[f(\mathrm{x}, ω) >0] > 1 - ε, \forall μ \in \mathscr{M}_{\mathrm{a}}$}, where $\mathscr{M}_{\mathrm{a}}$ is the set of all possibles mixtures of distributions $μ_{\mathrm{a}}, \mathrm{a \in A}$. For instance and typically, the family $\mathscr{M}_{\mathrm{a}}$ is the set of all mixtures of Gaussian distributions on $\mathbb{R}$ with mean and standard deviation $\mathrm{a}=(a,σ)$ in some compact set $\mathrm{A}\subset \mathbb{R}^2$. We provide a sequence of inner approximations $\mathrm{X}^d_ε = {\mathrm{x \in X} : w_d(\mathrm{x}) < ε}, d \in \mathbb{N}$, where $w_d$ is a polynomial of degree d whose vector of coefficients is an optimal solution of a semidefinite program. The size of the latter increases with the degree d. We also obtain the strong and highly desirable asymptotic guarantee that $λ(\mathrm{X}^*_ε$\$\mathrm{X}^d_ε$) → 0 as d increases, where λ is the Lebesgue measure on X. Same results are also obtained for the more intricated case of distributionally robust “joint” chance-constraints. Finally, there is a price to pay for this strong asymptotic guarantee which is the scalability of such a numerical scheme, and so far this important drawback makes it limited to problems of modest dimension.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Ancilla-Free Quantum Error Correction Codes for Quantum Metrology

Quantum error correction has recently emerged as a tool to enhance quantum sensing under Markovian noise. It works by correcting errors in a sensor while letting a signal imprint on the logical state. This approach typically requires a specialized error-correcting code, as most existing codes correct away both the dominant errors and the signal. To date, however, few such specialized codes are known, among which most require noiseless, controllable ancillas. We show here that such ancillas are not needed when the signal Hamiltonian and the error operators commute, a common limiting type of decoherence in quantum sensors. We give a semidefinite program for finding optimal ancilla-free sensing codes in general, as well as closed-form codes for two common sensing scenarios: qubits undergoing dephasing, and a lossy bosonic mode. Lastly, we analyze the sensitivity enhancement offered by the qubit code under arbitrary spatial noise correlations, beyond the ideal limit of orthogonal signal and noise operators.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2019

Orbital angular momentum constraints in the variational optimization of the two-electron reduced-density matrix

The direct variational determination of the two-electron reduced-density matrix (2-RDM) corresponding to an atomic or molecular system is usually carried out in a basis of real-valued atom-centered Gaussian basis functions, under the assumption that the 2-RDM is a real-valued quantity. Furthermore, for systems that possess orbital angular momentum symmetry, the description of states with a well-defined, nonzero z projection of the orbital angular momentum requires a computational framework generalized to include either complex basis functions or a complex-valued 2-RDM. We consider a semidefinite program suitable for the direct optimization of a complex-valued 2-RDM and explore the role of orbital angular momentum constraints in systems that possess the relevant symmetries. For atomic systems, constraints on the expectation values of the square and z projection of the orbital angular momentum operator allow one to optimize 2-RDMs for multiple orbital angular momentum states. Similarly, in linear molecules, orbital angular momentum projection constraints enable the description of multiple electronic states and, moreover, the application of such constraints is essential for a qualitatively correct description of the electronic structure. For example, in the case of molecular oxygen, we demonstrate that orbital angular momentum constraints are necessary to recover the correct energy ordering of the lowest-energy singlet and triplet states near the equilibrium geometry. However, care must still be taken in the description of the dissociation limit, because the 2-RDM-based approach is not size consistent, and the size-consistency error varies dramatically, depending on the z projections of the spin and orbital angular momenta.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2020

Inexact convex relaxations for AC optimal power flow: Towards AC feasibility

Convex relaxations of AC optimal power flow (AC-OPF) problems have attracted significant interest as in several instances they provably yield the global optimum to the original non-convex problem. If, however, the relaxation is inexact, the obtained solution is not AC-feasible. The quality of the obtained solution is essential for several practical applications of AC-OPF, but detailed analyses are lacking in existing literature. Here, this paper aims to cover this gap. We provide an in-depth investigation of the solution characteristics when convex relaxations are inexact, we assess the most promising AC feasibility recovery methods for large-scale systems, and we propose two new metrics that lead to a better understanding of the quality of the identified solutions. We perform a comprehensive assessment on 96 different test cases, ranging from 14 to 3120 buses, and we show the following: (i) Despite an optimality gap of less than 1%, several test cases still exhibit substantial distances to both AC feasibility and local optimality and the newly proposed metrics characterize these deviations. (ii) Penalization methods fail to recover an AC-feasible solution in 15 out of 45 test cases. (iii) The computational benefits of warm-starting non-convex solvers have significant variation, but a computational speedup exists in over 75% of cases.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2026

Universal Optimization and Tighter Fidelity Bounds for Approximate Quantum Error Correction

Approximate quantum error correction (AQEC) not only dictates the performance of discrete- and continuous-variable quantum error correction codes but also serves as a unifying framework across various physical disciplines. Identifying the optimal recovery channel to maximize the entanglement fidelity via standard semidefinite programming is computationally bottlenecked by the exponentially growing number of Kraus operators with system size, rendering large-scale optimization prohibitive. While analytical near-optimal maps exist, they typically work only when the Knill-Laflamme conditions are nearly satisfied. In this Letter, we establish an efficient framework by leveraging the duality between recovery and environment decoupling. This framework yields a tighter analytical lower bound on entanglement fidelity than the conventional limit set by the transpose channel. Furthermore, by exploiting the decayed weights of noise Kraus operators, we introduce a framework based on principal component analysis to reduce the dimension. In thermal loss channels where the weights decay exponentially, our approach achieves a 33-fold computational speedup while maintaining rigorous accuracy. Our approach enables high-precision optimization for AQEC codes that were previously intractable due to the curse of dimensionality.

Wu, Jing [Fermilab] (ORCID:0000000249460732)↗
DOE OSTI2023

Multi-output multilevel best linear unbiased estimators via semidefinite programming

Multifidelity forward uncertainty quantification (UQ) problems often involve multiple quantities of interest and heterogeneous models (e.g., different grids, equations, dimensions, physics, surrogate and reduced-order models). While computational efficiency is key in this context, multi-output strategies in multilevel/multifidelity methods are either sub-optimal or non-existent. In this paper we extend multilevel best linear unbiased estimators (MLBLUE) to multi-output forward UQ problems and we present new semidefinite programming formulations for their optimal setup. Not only do these formulations yield the optimal number of samples required, but also the optimal selection of low-fidelity models to use. While existing MLBLUE approaches are single-output only and require a non-trivial nonlinear optimization procedure, the new multi-output formulations can be solved reliably and efficiently. Here, we demonstrate the efficacy of the new methods and formulations in practical UQ problems with model heterogeneity.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Variational Quantum Algorithms for Semidefinite Programming

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N " M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Variational Quantum Algorithms for Semidefinite Programming

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N$\gg$M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Pareto-optimal target definition for multi-axis random vibration testing

In random vibration testing with multiple control channels, existing control laws require specification of a complete spectral density matrix at each control frequency. Spectral density matrices include autospectral densities on the diagonal and cross-spectral densities on the off-diagonal. In practice, the off-diagonal terms are often unknown, and recent vibration testing research has focused on fixing the diagonal and specifying the off-diagonal to minimize the required control energy, subject to a constraint that the target matrix is positive semidefinite. This paper shows that, even with a fixed diagonal, off-diagonal terms strongly affect control residuals. This overlooked effect occurs in both square and rectangular systems. By jointly considering input energy and control residuals, open-loop inputs are derived directly from the diagonal without specifying the off-diagonal terms. Vibration targets that can be used in closed-loop control are then derived using the optimal inputs, with positive semidefinite constraints applied during the derivation. The result is a set of Pareto-optimal control solutions. For each solution in the set, any other possible solution produces greater control error, greater input energy, or both. A balanced solution is selected automatically, though others can be chosen based on test needs. Simulations and experiments show that the proposed method outperforms state-of-the-art energy-minimizing approaches, achieving significant reductions in both control error and input energy.

Autospectral density↗
DOE OSTI2020

Toward a scalable robust security-constrained optimal power flow using a proximal projection bundle method

Robust security-constrained optimal power flow (rSCOPF) aims to find the worst-case contingencies of alternating current optimal power flow (ACOPF) in power systems. With the rise of GPU architectures on the upcoming supercomputer architectures, optimization algorithms that rely on sparse linear algebra and indefinite linear systems are becoming increasingly hard to solve efficiently (e.g. interior-point method). To address this we revisit a maximin optimization formulation of the rSCOPF and the single-level mixed-integer semidefinite programming (MISDP) reformulation, which is obtained by taking the Lagrangian relaxation of the inner minimization ACOPF problem. In this paper, we focus on the development of a proximal projection bundle method (PPBM) for solving continuous relaxation node subproblems of the MISDP problem, based primarily on the well-known alternating direction method of multipliers. Cutting planes reminiscent of bundle method ideas are also applied in coordination with updates of the proximal parameter. The cutting-plane method can generate a large number of linear inequalities, leading to a large scale but decomposable quadratic programming (QP) subproblem that is amenable to GPUs. We present the numerical results on the IEEE 30, 57, 118, and 300-bus systems by using our PBMM method. We discuss the main computational bottleneck of our method, which is the time taken to solve each iteration of a QP subproblem instance of the PPBM, and how GPU architectures can accelerate this solution process.

bundle method↗
DOE OSTI2019

Coordinating Multiple Sources for Service Restoration to Enhance Resilience of Distribution Systems

When a major outage occurs on a distribution system due to extreme events, microgrids, distributed generators, storage devices, and other local resources can be used to restore critical loads and enhance resiliency. This paper proposes a decision-making method to determine the optimal restoration strategy coordinating multiple sources to serve critical loads after a major outage. The critical load restoration problem is formulated as a mixed -integer semidefinite program. The objective is maximizing the number of loads restored, weighted by their priority. The unbalanced three-phase power flow constraint and operational constraints are considered. An iterative algorithm is proposed to deal with integer variables and can attain the global optimum of the critical load restoration problem by solving a few semidefinite programs under mild conditions. The effectiveness of the proposed models and algorithm is validated by numerical simulation with the modified IEEE 13-node test feeder and the modified IEEE123-node test feeder under a large number of scenarios. The results indicate that the optimal restoration strategy can be determined efficiently in most scenarios

Wang, Ying↗
DOE OSTI2021

A Bilevel Approach for Identifying the Worst Contingencies for Nonconvex Alternating Current Power Systems

We address the bilevel optimization problem of identifying the most critical attacks to an alternating current (AC) power flow network. The upper-level binary maximization problem consists of choosing an attack that is treated as a parameter in the lower-level defender minimization problem. Instances of the lower-level global minimization problem by themselves are NP-hard due to the nonconvex AC power flow constraints, and bilevel solution approaches commonly apply a convex relaxation or approximation to allow for tractable bilevel reformulations at the cost of underestimating some power system vulnerabilities. Our main contribution is to provide an alternative branch-and-bound algorithm whose upper bounding mechanism (in a maximization context) is based on a reformulation that avoids relaxation of the AC power flow constraints in the lower-level defender problem. Lower bounding is provided with semidefinite programming (SDP) relaxed solutions to the lower-level problem. We establish finite termination with guarantees of either a globally optimal solution to the original bilevel problem, or a globally optimal solution to the SDP-relaxed bilevel problem which is included in a vetted list of upper-level attack solutions, at least one of which is a globally optimal solution to the bilevel problem. We demonstrate through computational experiments applied to IEEE case instances both the relevance of our contribution, and the effectiveness of our contributed algorithm for identifying power system vulnerabilities without resorting to convex relaxations of the lower-level problem. We conclude with a discussion of future extensions and improvements.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets

We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match decision-dependent empirical ones, respectively. For both sets, we show that the subproblem in each stage can be recast as a mixed-integer linear program (MILP). Moreover, we extend the general moment-based ambiguity set in to the multistage decision-dependent setting, and derive mixed-integer semidefinite programming (MISDP) reformulations of stage-wise subproblems. We develop methods for attaining lower and upper bounds of the optimal objective value of the multistage MISDPs, and approximate them using a series of MILPs. We deploy the Stochastic Dual Dynamic integer Programming (SDDiP) method for solving the problem under the three ambiguity sets with risk-neutral or risk-averse objective functions, and conduct numerical studies on multistage facility-location instances having diverse sizes under different parameter and uncertainty settings. Furthermore, our results show that the SDDiP quickly finds optimal solutions for moderate-sized instances under the first two ambiguity sets, and also finds good approximate bounds for the multistage MISDPs derived under the third ambiguity set. We also demonstrate the efficacy of incorporating decision-dependent distributional ambiguity in multistage decision-making processes.

97 MATHEMATICS AND COMPUTING↗