The application of semidefinite programming to the optimal power flow (OPF) problem has recently attracted significant research interest. This paper provides advances in modeling and computation ...required for solving the OPF problem for large-scale, general power system models. Specifically, a semidefinite programming relaxation of the OPF problem is presented that incorporates multiple generators at the same bus and parallel lines. Recent research in matrix completion techniques that decompose a single large matrix constrained to be positive semidefinite into many smaller matrices has made solution of OPF problems using semidefinite programming computationally tractable for large system models. We provide three advances to existing decomposition techniques: a matrix combination algorithm that further decreases solver time, a modification to an existing decomposition technique that extends its applicability to general power system networks, and a method for obtaining the optimal voltage profile from the solution to a decomposed semidefinite program.
•We consider row layout, unequal-areas layout, and multifloor layout problems.•We focus on the application of mathematical optimization techniques.•We propose a general formulation for multifloor ...layout to motivate further research.•We also discuss symmetry breaking and valid inequalities.
Facility layout problems are an important class of operations research problems that has been studied for several decades. Most variants of facility layout are NP-hard, therefore global optimal solutions are difficult or impossible to compute in reasonable time. Mathematical optimization approaches that guarantee global optimality of solutions or tight bounds on the global optimal value have nevertheless been successfully applied to several variants of facility layout. This review covers three classes of layout problems, namely row layout, unequal-areas layout, and multifloor layout. We summarize the main contributions to the area made using mathematical optimization, mostly mixed integer linear optimization and conic optimization. For each class of problems, we also briefly discuss directions that remain open for future research.
Convex relaxations of non-convex optimal power flow (OPF) problems have recently attracted significant interest. While existing relaxations globally solve many OPF problems, there are practical ...problems for which existing relaxations fail to yield physically meaningful solutions. This paper applies moment relaxations to solve many of these OPF problems. The moment relaxations are developed from the Lasserre hierarchy for solving generalized moment problems. Increasing the relaxation order in this hierarchy results in "tighter" relaxations at the computational cost of larger semidefinite programs. Low-order moment relaxations are capable of globally solving many small OPF problems for which existing relaxations fail. By exploiting sparsity and only applying the higher-order relaxation to specific buses, global solutions to larger problems are computationally tractable through the use of an iterative algorithm informed by a heuristic for choosing where to apply the higher-order constraints. With standard semidefinite programming solvers, the algorithm globally solves many test systems with up to 300 buses for which the existing semidefinite relaxation fails to yield globally optimal solutions.
Chordal and factor-width decomposition methods for semidefinite programming and polynomial optimization have recently enabled the analysis and control of large-scale linear systems and medium-scale ...nonlinear systems. Chordal decomposition exploits the sparsity of semidefinite matrices in a semidefinite program (SDP), in order to formulate an equivalent SDP with smaller semidefinite constraints that can be solved more efficiently. Factor-width decompositions, instead, relax or strengthen SDPs with dense semidefinite matrices into more tractable problems, trading feasibility or optimality for lower computational complexity. This article reviews recent advances in large-scale semidefinite and polynomial optimization enabled by these two types of decomposition, highlighting connections and differences between them. We also demonstrate that chordal and factor-width decompositions allow for significant computational savings on a range of classical problems from control theory, and on more recent problems from machine learning. Finally, we outline possible directions for future research that have the potential to facilitate the efficient optimization-based study of increasingly complex large-scale dynamical systems.
In this paper, we will improve the practical performance of an interior points algorithm for convex nonlinear semi-definite optimization, where to minimize a nonlinear convex objective function ...subject to nonlinear convex constraints. We will propose a new method for solving this kind of problem by using a straightforward kernel function and the iterative Newton directions combined with the Broyden-Fletcher-Goldfarb-Shanno (BFGS in short) quasi-Newton method. Further, a best polynomial complexity for solving nonlinear convex problems will be found until now.
Many central problems throughout optimization, machine learning, and statistics are equivalent to optimizing a low-rank matrix over a convex set. However, although rank constraints offer unparalleled ...modeling flexibility, no generic code currently solves these problems to certifiable optimality at even moderate sizes. Instead, low-rank optimization problems are solved via convex relaxations or heuristics that do not enjoy optimality guarantees. In “Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints,” Bertsimas, Cory-Wright, and Pauphilet propose a new approach for modeling and optimizing over rank constraints. They generalize mixed-integer optimization by replacing binary variables
z
that satisfy
z
2
=
z
with orthogonal projection matrices
Y
that satisfy
Y
2
=
Y
. This approach offers the following contributions: First, it supplies certificates of (near) optimality for low-rank problems. Second, it demonstrates that some of the best ideas in mixed-integer optimization, such as decomposition methods, cutting planes, relaxations, and random rounding schemes, admit straightforward extensions to mixed-projection optimization.
We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy
Y
2
=
Y
, the matrix analog of binary variables that satisfy
z
2
=
z
, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields convex optimization problems over the nonconvex set of orthogonal projection matrices. Furthermore, we design outer-approximation algorithms to solve low-rank problems to certifiable optimality, compute lower bounds via their semidefinite relaxations, and provide near optimal solutions through rounding and local search techniques. We implement these numerical ingredients and, to our knowledge, for the first time solve low-rank optimization problems to certifiable optimality. Our algorithms also supply certifiably near-optimal solutions for larger problem sizes and outperform existing heuristics by deriving an alternative to the popular nuclear norm relaxation. Using currently available spatial branch-and-bound codes, not tailored to projection matrices, we can scale our exact (respectively, near-exact) algorithms to matrices with up to 30 (600) rows/columns. All in all, our framework, which we name
mixed-projection conic optimization
, solves low-rank problems to certifiable optimality in a tractable and unified fashion.
Supplemental Material:
The online appendix is available at
https://doi.org/10.1287/opre.2021.2182
.
We study a cutting-plane method for semidefinite optimization problems, and supply a proof of the method’s convergence, under a boundedness assumption. By relating the method’s rate of convergence to ...an initial outer approximation’s diameter, we argue the method performs well when initialized with a second-order cone approximation, instead of a linear approximation. We invoke the method to provide bound gaps of 0.5–6.5% for sparse PCA problems with 1000s of covariates, and solve nuclear norm problems over 500 × 500 matrices.
PDF
