Search

We consider the optimization of pairwise objective functions, i.e., objective functions of the form H (x) = H (x 1 , … , x N) = ∑ 1 ≤ i < j ≤ N H ij (x i , x j) for x i in some continuous state spaces X i . Global optimization in this setting is generally confounded by the possible existence of spurious local minima and the impossibility of global search due to the curse of dimensionality. In this paper, we approach such problems via convex relaxation of the marginal polytope considered in graphical modeling, proceeding in a multiscale fashion which exploits the smoothness of the cost function. We show theoretically that, compared with existing methods, such an approach is advantageous even in simple settings for sensor network localization (SNL). We successfully apply our method to SNL problems, particularly difficult instances with high noise. We also validate performance on the optimization of the Lennard-Jones potential, which is plagued by the existence of many near-optimal configurations. We demonstrate that the proposed algorithm allows us to effectively explore these configurations. [ABSTRACT FROM AUTHOR]

Copyright of Electric Power is the property of Electric Power Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

It is essential for network operators to guarantee required levels of availability in the network without incurring in excessive costs. We address the optimization problem of upgrading links at a given cost, to achieve end‐to‐end availability guarantees in the network, via pairs of working and backup paths. These guarantees are expressed as nonlinear path pair availability constraints which cannot be readily linearized. For this reason, most works have only considered the working path availability or disaggregated models where availability guarantees are considered separately for the working and backup paths. We show that the aggregated models which jointly consider the availabilities of the working and backup paths can provide better solutions than the disaggregated models. Moreover, we present a more efficient aggregated model based on a novel strategy to linearize the path pair availability constraints, and show that it further improves previous results. It is usual to impose that the upgraded links belong to a spanning tree subgraph. We further compare the solutions with and without this imposition and show that relaxing the tree condition can provide better solutions. [ABSTRACT FROM AUTHOR]

We study the Compressed Sensing (CS) problem, which is the problem of finding the most sparse vector that satisfies a set of linear measurements up to some numerical tolerance. CS is a central problem in Statistics, Operations Research and Machine Learning which arises in applications such as signal processing, data compression, image reconstruction, and multi-label learning. We introduce an ℓ 2 regularized formulation of CS which we reformulate as a mixed integer second order cone program. We derive a second order cone relaxation of this problem and show that under mild conditions on the regularization parameter, the resulting relaxation is equivalent to the well studied basis pursuit denoising problem. We present a semidefinite relaxation that strengthens the second order cone relaxation and develop a custom branch-and-bound algorithm that leverages our second order cone relaxation to solve small-scale instances of CS to certifiable optimality. When compared against solutions produced by three state of the art benchmark methods on synthetic data, our numerical results show that our approach produces solutions that are on average 6.22 % more sparse. When compared only against the experiment-wise best performing benchmark method on synthetic data, our approach produces solutions that are on average 3.10 % more sparse. On real world ECG data, for a given ℓ 2 reconstruction error our approach produces solutions that are on average 9.95 % more sparse than benchmark methods ( 3.88 % more sparse if only compared against the best performing benchmark), while for a given sparsity level our approach produces solutions that have on average 10.77 % lower reconstruction error than benchmark methods ( 1.42 % lower error if only compared against the best performing benchmark). When used as a component of a multi-label classification algorithm, our approach achieves greater classification accuracy than benchmark compressed sensing methods. This improved accuracy comes at the cost of an increase in computation time by several orders of magnitude. Thus, for applications where runtime is not of critical importance, leveraging integer optimization can yield sparser and lower error solutions to CS than existing benchmarks. [ABSTRACT FROM AUTHOR]

Integrated energy systems enable the complementary utilization of various forms of energy. With the rapid increase in installed capacity of distributed generations, their intermittency and randomness have posed significant challenges to the operational efficiency and safety of the system. To address the impact of uncertainties in both energy supply and demand on the economic scheduling of building integrated energy systems, this study first models the operational characteristics of each subsystem, including the power grid, natural gas network, and various coupled equipments. Next, a thermal cell model of the building users is constructed based on the quantitative relationship among temperature, thermal radiation, and thermal load. Then, a day-ahead optimization scheduling model for the building integrated energy systems is established with the objective of minimizing the operating cost. A chance-constrained programming approach is employed to convert the non-linear scheduling model into a mixed-integer second-order cone programming problem easy to solve. Finally, simulation analysis is conducted in the Python environment using the CPLEX solver. The results demonstrate that the proposed model and solution method are capable of effectively characterizing and addressing uncertainty risks in the system, facilitating the consumption of renewable energy, and improving the economic efficiency of system operation.

This paper presents an improved method for computing convex and concave relaxations of the parametric solutions of ordinary differential equations (ODEs). These are called state relaxations and are crucial for solving dynamic optimization problems to global optimality via branch-and-bound (B &B). The new method improves upon an existing approach known as relaxation preserving dynamics (RPD). RPD is generally considered to be among the best available methods for computing state relaxations in terms of both efficiency and accuracy. However, it requires the solution of a hybrid dynamical system, whereas other similar methods only require the solution of a simple system of ODEs. This is problematic in the context of branch-and-bound because it leads to higher cost and reduced reliability (i.e., invalid relaxations can result if hybrid mode switches are not detected numerically). Moreover, there is no known sensitivity theory for the RPD hybrid system. This makes it impossible to compute subgradients of the RPD relaxations, which are essential for efficiently solving the associated B &B lower bounding problems. To address these limitations, this paper presents a small but important modification of the RPD theory, and a corresponding modification of its numerical implementation, that crucially allows state relaxations to be computed by solving a system of ODEs rather than a hybrid system. This new RPD method is then compared to the original using two examples and shown to be more efficient, more robust, and of almost identical accuracy. [ABSTRACT FROM AUTHOR]

We describe a "discretize-then-relax" strategy to globally minimize integral functionals over functions u in a So bolev space subject to Dirichlet boundary conditions. The strategy applies whenever the integral functional depends polynomially on u and its derivatives, even if it is nonconvex. The "discretize" step uses a bounded finite element scheme to approximate the integral minimization problem with a convergent hierarchy of polynomial optimization problems over a compact feasible set, indexed by the decreasing size h of the finite element mesh. The "relax" step employs sparse moment-sum-of-squares relaxations to approximate each polynomial optimization problem with a hierarchy of convex semidefinite programs, indexed by an increasing relaxation order w. We prove that, as w → ∞ and h → 0, solutions of such semidefinite programs provide approximate minimizers that converge in a suitable sense (including in certain Lp norms) to the global minimizer of the original integral functional if it is unique. We also report computational experiments showing that our numerical strategy works well even when technical conditions required by our theoretical analysis are not satisfied. [ABSTRACT FROM AUTHOR]

Copyright of Electric Power Engineering Technology is the property of Editorial Department of Electric Power Engineering Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Traditional switching operations require on-site work, and the high voltage generated by arc discharges can pose a risk of injury to the operator. Therefore, a combination of visual servo and robot control is used to localize the switching operation and construct hand–eye calibration equations. The solution to the hand–eye calibration equations is coupled with the rotation matrix and translation vectors, and it depends on the initial value determination. This article presents a convex relaxation global optimization hand–eye calibration algorithm based on dual quaternions. Firstly, the problem model is simplified using the mathematical tools of dual quaternions, and then the linear matrix inequality convex optimization method is used to obtain a rotation matrix with higher accuracy. Afterwards, the calibration equations of the translation vectors are rewritten, and a new objective function is established to solve the coupling influence between them, maintaining positioning precision at approximately 2.9 mm. Considering the impact of noise on the calibration process, Gaussian noise is added to the solutions of the rotation matrix and translation vector to make the data more closely resemble the real scene in order to evaluate the performance of different hand–eye calibration algorithms. Eventually, an experiment comparing different hand–eye calibration methods proves that the proposed algorithm is better than other hand–eye calibration algorithms in terms of calibration accuracy, robustness to noise, and stability, satisfying the accuracy requirements of switching operations. [ABSTRACT FROM AUTHOR]

MINLO (mixed-integer nonlinear optimization) formulations of the disjunction between the origin and a polytope via a binary indicator variable have broad applicability in nonlinear combinatorial optimization, for modeling a fixed cost c associated with carrying out a set of d activities and a convex variable cost function f associated with the levels of the activities. The perspective relaxation is often used to solve such models to optimality in a branch-and-bound context, especially in the context in which f is univariate (e.g., in Markowitz-style portfolio optimization). But such a relaxation typically requires conic solvers and are typically not compatible with general-purpose NLP software which can accommodate additional classes of constraints. This motivates the study of weaker relaxations to investigate when simpler relaxations may be adequate. Comparing the volume (i.e., Lebesgue measure) of the relaxations as means of comparing them, we lift some of the results related to univariate functions f to the multivariate case. Along the way, we survey, connect and extend relevant results on integration over a simplex, some of which we concretely employ, and others of which can be used for further exploration on our main subject. [ABSTRACT FROM AUTHOR]

This paper develops an algorithm for synthesizing negative imaginary (NI) systems with a specified H∞-norm bound by exploiting the convex relaxation technique in the static output-feedback (SOF) control design framework. This scheme improves the robustness objective since the present framework can handle both NI and H∞-norm-bounded unstructured uncertainty of the system. The non-strict inequality involved in the NI system description that creates a major difficulty in the SOF control design, can efficiently be tackled by the developed convex relaxation-based iterative algorithm. The advantages of the algorithm are shown using several examples and the results are compared with the existing works. [ABSTRACT FROM AUTHOR]

To address the scalability limitations of traditional centralized optimal power flow algorithms， a fully distributed algorithm for solving optimal power flow in DC systems with large-scale distributed energy sources is proposed. Firstly， the non-convex optimal power flow model of DC systems is transformed into a second-order cone programming （SOCP） model using convex relaxation methods. Subsequently， a distributed algorithm based on the alternating direction method of multipliers （ADMM） is established to solve this model. The algorithm is then transformed by eliminating consensus variables into an improved fully distributed algorithm for optimal power flow in DC systems. Finally， in simulation tests on enhanced IEEE 13-node and 118-node systems， the algorithm proved capable of achieving a globally optimal solution for optimal power flow in radial and ring DC systems. Notably， this was accomplished without the necessity of a central coordinating unit to synchronize boundary consistency information across regions. Instead， the algorithm relies on parallel optimization within each region and the exchange of minimal boundary node information between adjacent regions.

Calculation of static voltage stability margin (SVSM) of AC/DC power systems with lots of renewable energy sources (RESs) integration requires consideration of uncertain load growth and renewable energy generation output. This paper presents a bi-level optimal power flow (BLOPF) model to identify the worst-case SVSM of an AC/DC power system with line commutation converter-based HVDC and multi-terminal voltage sourced converter-based HVDC transmission lines. Constraints of uncertain load growth's hypercone model and control mode switching of DC converter stations are considered in the BLOPF model. Moreover, uncertain RES output fluctuations are described as intervals, and two three-level optimal power flow (TLOPF) models are established to identify interval bounds of the system worst-case SVSM. The two TLOPF models are both transformed into max-min bi-level optimization models according to independent characteristics of different uncertain variables. Then, transforming the inner level model into its dual form, max-min BLOPF models are simplified to single-level optimization models for direct solution. Calculation results on the modified IEEE-39 bus AC/DC case and an actual large-scale AC/DC case in China indicate correctness and efficiency of the proposed identification method.

Line-commutated converter (LCC)-based high-voltage DC (HVDC) systems have been integrated with bulk AC power grids for interregional transmission of renewable power. The nonlinear LCC model brings additional nonconvexity to optimal power flow (OPF) of hybrid AC-DC power grids. A convexification method for the LCC station model could address such nonconvexity but has rarely been discussed. We devise an equivalent reformulation for classical LCC station models that facilitates second-order cone convex relaxation for the OPF of LCC-based AC-DC power grids. We also propose sufficient conditions for exactness of convex relaxation with its proof. Equivalence of the proposed LCC station models and properties, exactness, and effectiveness of convex relaxation are verified using four numerical simulations. Simulation results demonstrate a globally optimal solution of the original OPF can be efficiently obtained from relaxed model.

Abstract The application of a semi‐definite programming (SDP) approach to the Alternating Current Optimal Power Flow problem has attracted significant attention in recent years. However, the SDP relaxation of optimal power flow (OPF) can be computationally intensive and lead to memory issues when dealing with large‐scale power systems. To overcome these challenges, we have developed APD–SDP, an optimisation solver based on a first‐order primal–dual algorithm. This framework incorporates various acceleration techniques, such as rescaling, step size decay and reset, adaptive line search, and restart, to improve efficiency. To further speed up computations, we have developed a customised eigenvalue decomposition component by exploiting the 3 × 3 block structure in the dual SDP formulation. Experimental results demonstrate that APD–SDP outperforms other commercial and open‐source SDP solvers on large‐scale and high‐dimensional PGLib‐OPF datasets.

Copyright of Zhejiang Electric Power is the property of Zhejiang Electric Power Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Sparse optimization–fitting data with a low-cardinality linear model–is addressed through the minimization of a cardinality-penalized least-squares function, for which dedicated branch-and-bound algorithms clearly outperform generic mixed-integer-programming solvers. Three acceleration techniques are proposed for such algorithms. Convex relaxation problems at each node are addressed with dual approaches, which can early prune suboptimal nodes. Screening methods are implemented, which fix variables to their optimal value during the node evaluation, reducing the subproblem size. Numerical experiments show that the efficiency of such techniques depends on the node cardinality and on the structure of the problem matrix. Last, different exploration strategies are proposed to schedule the nodes. Best-first search is shown to outperform the standard depth-first search used in the related literature. A new strategy is proposed which first explores the nodes with the lowest least-squares value, which is shown to be the best at finding the optimal solution–without proving its optimality. A C++ solver with compiling and usage instructions is made available. [ABSTRACT FROM AUTHOR]

We investigate the optimal portfolio deleveraging (OPD) problem with permanent and temporary price impacts, where the objective is to maximize equity while meeting a prescribed debt/equity requirement. We take the real situation with cross impact among different assets into consideration. The resulting problem is, however, a nonconvex quadratic program with a quadratic constraint and a box constraint, which is known to be NP‐hard. In this paper, we first develop a successive convex optimization (SCO) approach for solving the OPD problem and show that the SCO algorithm converges to a KKT point of its transformed problem. Second, we propose an effective global algorithm for the OPD problem, which integrates the SCO method, simple convex relaxation, and a branch‐and‐bound framework, to identify a global optimal solution to the OPD problem within a prespecified ε‐tolerance. We establish the global convergence of our algorithm and estimate its complexity. We also conduct numerical experiments to demonstrate the effectiveness of our proposed algorithms with both real data and randomly generated medium‐ and large‐scale OPD instances. [ABSTRACT FROM AUTHOR]

We propose a sparse reduced rank Huber regression for analyzing large and complex high-dimensional data with heavy-tailed random noise. The proposed method is based on a convex relaxation of a rank- and sparsity-constrained nonconvex optimization problem, which is then solved using a block coordinate descent and an alternating direction method of multipliers algorithm. We establish nonasymptotic estimation error bounds under both Frobenius and nuclear norms in the high-dimensional setting. This is a major contribution over existing results in reduced rank regression, which mainly focus on rank selection and prediction consistency. Our theoretical results quantify the tradeoff between heavy-tailedness of the random noise and statistical bias. For random noise with bounded (1 + δ) th moment with δ ∈ (0 , 1) , the rate of convergence is a function of δ, and is slower than the sub-Gaussian-type deviation bounds; for random noise with bounded second moment, we obtain a rate of convergence as if sub-Gaussian noise were assumed. We illustrate the performance of the proposed method via extensive numerical studies and a data application. for this article are available online. [ABSTRACT FROM AUTHOR]

In this work, we are interested in an optimal power flow problem with fixed voltage magnitudes in distribution networks. This optimization problem is known to be non-convex and thus difficult to solve. A well-known solution methodology consists in reformulating the objective function and the constraints of the original problem in terms of positive semi-definite matrix traces, to which we add a rank constraint. To convexify the problem, we remove this rank constraint. Our main focus is to provide a strong mathematical proof of the exactness of this convex relaxation technique. To this end, we explore the geometry of the feasible set of the problem via its Pareto-front. We prove that the feasible set of the original problem and the feasible set of its convexification share the same Pareto-front. From a numerical point of view, this exactness result allows to reduce the initial problem to a semi-definite program, which can be solved by more efficient algorithms. [ABSTRACT FROM AUTHOR]

Sparse precision matrix estimation, also known as the estimation of the inverse covariance matrix in statistical contexts, represents a critical challenge in numerous multivariate analysis applications. This challenge becomes notably complex when the dimension of the data is far greater than the capacity of samples. To address this issue, we introduce a convex relaxation model that employs the first-order optimality conditions associated with the lasso-penalized D-trace loss for the purpose of estimating sparse precision matrix. The proposed model is effectively solved through the widely recognized alternating direction method of multipliers. Additionally, we provide closed-form solutions to subproblems in each iteration with a computational complexity of O(np2), and establish the convergence of our proposed algorithm. Numerical investigations demonstrate that our algorithm exhibits the capability to handle large-scale datasets and significantly outperforms the existing methods, particularly when dealing with high-dimensional scenarios characterized by a large dimension p.

Traditional switching operations require on-site work, and the high voltage generated by arc discharges can pose a risk of injury to the operator. Therefore, a combination of visual servo and robot control is used to localize the switching operation and construct hand–eye calibration equations. The solution to the hand–eye calibration equations is coupled with the rotation matrix and translation vectors, and it depends on the initial value determination. This article presents a convex relaxation global optimization hand–eye calibration algorithm based on dual quaternions. Firstly, the problem model is simplified using the mathematical tools of dual quaternions, and then the linear matrix inequality convex optimization method is used to obtain a rotation matrix with higher accuracy. Afterwards, the calibration equations of the translation vectors are rewritten, and a new objective function is established to solve the coupling influence between them, maintaining positioning precision at approximately 2.9 mm. Considering the impact of noise on the calibration process, Gaussian noise is added to the solutions of the rotation matrix and translation vector to make the data more closely resemble the real scene in order to evaluate the performance of different hand–eye calibration algorithms. Eventually, an experiment comparing different hand–eye calibration methods proves that the proposed algorithm is better than other hand–eye calibration algorithms in terms of calibration accuracy, robustness to noise, and stability, satisfying the accuracy requirements of switching operations.

We consider in this paper a separable and nonconvex quadratic program (QP) with a quadratic constraint and a box constraint that arises from application in optimal portfolio deleveraging (OPD) in finance and is known to be NP-hard. We first propose an improved Lagrangian breakpoint search algorithm based on the secant approach (called ILBSSA) for this nonconvex QP, and show that it converges to either a suboptimal solution or a global solution of the problem. We then develop a successive convex optimization (SCO) algorithm to improve the quality of suboptimal solutions derived from ILBSSA, and show that it converges to a KKT point of the problem. Second, we develop a new global algorithm (called ILBSSA-SCO-BB), which integrates the ILBSSA and SCO methods, convex relaxation and branch-and-bound framework, to find a globally optimal solution to the underlying QP within a pre-specified ϵ -tolerance. We establish the convergence of the ILBSSA-SCO-BB algorithm and its complexity. Preliminary numerical results are reported to demonstrate the effectiveness of the ILBSSA-SCO-BB algorithm in finding a globally optimal solution to large-scale OPD instances. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Guangdong University of Technology is the property of Journal of Guangdong University of Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this paper, we investigate effective algorithms for the worst-case linear optimization (WCLO) under polyhedral uncertainty on the right-hand-side of the constraints that arises from a broad range of applications and is known to be strongly NP-hard. We first develop a successive convex optimization (SCO) algorithm for WCLO and show that it converges to a local solution of the transformed problem of WCLO. Second, we develop a global algorithm (called SCOBB) for WCLO that finds a globally optimal solution to the underlying WCLO within a pre-specified ϵ -tolerance by integrating the SCO method, LO relaxation, branch-and-bound framework and initialization. We establish the global convergence of the SCOBB algorithm and estimate its complexity. Finally, we integrate the SCOBB algorithm for WCLO to develop a global algorithm for the two-stage adaptive robust optimization with a polyhedral uncertainty set. Preliminary numerical results illustrate that the SCOBB algorithm can effectively find a global optimal solution to medium and large-scale WCLO instances. [ABSTRACT FROM AUTHOR]

We develop a general framework for selecting a small pool of candidate solutions to maximize the chances that one will be optimal for a combinatorial optimization problem, under a linear and additive random payoff function. We formulate this problem using a two‐stage distributionally robust model, with a mixed 0–1 semidefinite program. This approach allows us to exploit the "diversification" effect inherent in the problem to address how different candidate solutions can be selected to improve the chances that one will attain a high ex post payoff. More interestingly, using this distributionally robust optimization approach, our model recovers the "evil twin" strategy, well known in the field of football pool betting, under appropriate settings. We also address the computational challenges of scaling up our approach to construct a moderate number of candidate solutions to increase the chances of finding one that performs well. To this end, we develop a sequential optimization approach based on a compact semidefinite programming reformulation of the problem. Extensive numerical results show the superiority of our approach over existing methods. [ABSTRACT FROM AUTHOR]

In a two-player noncooperative game framework, we deal with the affine relaxations of the best response algorithm (where a player's strategy is a best response to the strategy of the other player that comes from the previous step), motivated by the first results obtained for convex relaxations in zero-sum games (J. Morgan, Int. J. Comput. Math., 4 (1974), pp. 143-175) and for nonconvex affine relaxations in non-zero-sum games (F. Caruso, M. C. Ceparano, and J. Morgan, SIAM J. Optim., 30 (2020), pp. 1638-1663). In order to be able to specify the convergence of any type of affine relaxation of the best response algorithm, we define a new class of games, called ratiobounded games. This class contains games broadly used in literature (such as weighted potential and zero-sum games), both in finite and infinite dimensional settings. Its definition relies on a unifying property and on three associate key parameters explicitly related to the data. Depending on how the parameters are ordered, we provide a classification of the ratio-bounded games in four subclasses such that, for each of them, the following issues are answered when the strategy sets are real Hilbert spaces: existence and uniqueness of the Nash equilibria, global convergence of the affine relaxations of the best response algorithm, estimation of the related errors, determination of the algorithm with the highest speed of convergence, and comparison with the known results. Moreover, the investigation is supplemented by illustrating numerical examples and by describing a black-box model with a first-order oracle for an implementation of the algorithm. [ABSTRACT FROM AUTHOR]

This article proposes a general fixture layout design framework that directly integrates the system equation with the convex relaxation method. Note that the optimal fixture design problem is a large-scale combinatorial optimization problem; we relax it to a convex Semi-Definite Programming (SDP) problem by adopting sparse learning and SDP relaxation techniques. It can be solved efficiently by existing convex optimization algorithms and thus generates a near-optimal fixture layout. A real case study in the half-to-half fuselage assembly process indicates the superiority of our proposed algorithm compared to the current industry practice and state-of-art methods. [ABSTRACT FROM AUTHOR]

Hydrogen is injected into the existing natural gas network to form hydrogen-rich compressed natural gas (HCNG), effectively addressing the high cost of hydrogen transmission. However, the traditional IES model cannot be used due to the hydrogen injection's effect on gas properties and the vague characteristics of the transport and separation processes. Therefore, this paper proposes an HCNG penetrated integrated energy system (HPIES) optimal dispatching method by comprehensively modelling the injection, transmission, and separation processes of HCNG. An HCNG mass flow rate model considering variable mixing ratio and unknown beginning flow direction is developed to describe the effect of hydrogen injection. Furthermore, the hydrogen separation model is established by introducing a combined membrane and pressure swing adsorption separation process. The tightening McCormick algorithm is proposed to solve quickly HPIES optimal dispatch problem with an acceptable feasibility check. Finally, case studies on the HPIES consisting of IEEE 39-bus power system and 20-node natural gas system validate the effectiveness of the algorithm and model. The results show that the average error is 0.031% for the bilinear term constraint. [Display omitted] • A model of HCNG penetrated integrated energy system (HPIES) is established. • The model considers the process of HCNG production, transport and separation. • An HCNG mass flow rate model is established to track the hydrogen mixing ratio. • Hydrogen separation is modeled based on membranes and pressure swing adsorption. • The HPIES optimal method based on tightening McCormick algorithm is proposed. [ABSTRACT FROM AUTHOR]

We investigate the effectiveness of convex relaxation and nonconvex optimization in solving bilinear systems of equations under two different designs (i.e., a sort of random Fourier design and Gaussian design). Despite the wide applicability, the theoretical understanding about these two paradigms remains largely inadequate in the presence of random noise. The current article makes two contributions by demonstrating that (i) a two-stage nonconvex algorithm attains minimax-optimal accuracy within a logarithmic number of iterations, and (ii) convex relaxation also achieves minimax-optimal statistical accuracy vis-à-vis random noise. Both results significantly improve upon the state-of-the-art theoretical guarantees. for this article are available online. [ABSTRACT FROM AUTHOR]

Triangulation uncertainty is the uncertainty associated when we try to locate an unknown target with the help of three anchor nodes resulting in formation of a triangulated region. Efficient triangulation leads to superior accuracy and lower rate of errors in sensor networks. Although sufficient work has been done to compute localization uncertainties, there is dearth of work pertaining to triangulation uncertainty. The existing problems are: first, localization incurs large computation cost, necessitating some hierarchy or clustering techniques. Second, linear, non-linear and optimization-based solvers invariably simplify the occurrence of errors during estimation of localization. To solve these problems, the present work proposes a range free assistive approach in detecting symmetric triangulations. This approach combined with semidefinite programming of the cost function is shown to exhibit improved localization performance. Numerical results show that the RMS errors is reduced by using triangulation assisted node deployment. The results are compared with the standard weighted least square method for different number of anchor nodes. [ABSTRACT FROM AUTHOR]

The purpose of this paper is the approach of a mathematical model dedicated to planning the consecutive days off of a company’s employees. Companies must find a flexible work schedule between employees, always considering the satisfaction of work tasks as well as guaranteeing consecutive days off. The analysis is based on solving a quadratic programming problem with binary variables. The proposed method uses the properties of the circulant symmetric matrix in the researched model, which allows the transformation of the considered problems into an equivalent separable non-convex optimization problem. A practical continuous convex relaxation approach is proposed. DC Algorithm is used to solve relaxed problems. A solved numerical example is presented.

With the deepening of the coupling degree between power network and natural gas network, the traditional independent optimal scheduling of transmission and distribution integrated electricity–gas systems cannot make full use of the flexible control ability of various resources and the complementary support capabilities between different energy systems. Therefore, this paper puts forward a cooperative optimization scheduling model of transmission–distribution​ integrated electricity–gas systems (TD-IEGS). The coordinated operation of multi-energy coupling devices including gas-fired units, combined heat and power (CHP) units and electric boilers (EB) are considered in this paper to enhance system operation flexibility and economy. The second order cone relaxation (SOCR) method is utilized to tackle the non-linear power and gas flow constraints, and the proposed mixed-integer non-linear programming co-optimization scheduling model is transformed into a mixed integer second order cone programming model (MISOCP). Case studies demonstrate that compared with the independent operation mode, the proposed co-optimization scheduling model of TD-IEGS can reduce total operation cost by about 6.7% under 50% wind power penetration level. Moreover, the co-optimization of TD-IEGS can promote wind power utilization especially in a high share of wind energy.

The Shapley-Folkman theorem shows that Minkowski averages of uniformly bounded sets tend to be convex when the number of terms in the sum becomes much larger than the ambient dimension. In optimization, Aubin and Ekeland show that this produces an a priori bound on the duality gap of separable nonconvex optimization problems involving finite sums. This bound is highly conservative and depends on unstable quantities; we relax it in several directions to show that nonconvexity can have a much milder impact on finite sum minimization problems, such as empirical risk minimization and multitask classification. As a byproduct, we show a new version of Maurey's classical approximate Carathéodory lemma where we sample a significant fraction of the coefficients, without replacement, as well as a result on sampling constraints using an approximate Helly theorem, both of independent interest. Funding: A. d'Aspremont acknowledges support from the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program [Grant ANR-19-P3IA-0001] (PRAIRIE 3IA Institute), the Machine Learning and Optimisation Joint Research Initiative with the Fonds AXA pour la Recherche and Kamet Ventures, as well as a Google focused award. [ABSTRACT FROM AUTHOR]

We formulate the Multi-Constrained Dynamic Traffic Assignment (DTA) problem as an instance of the nonlinear composite problem. To solve the problem, this paper introduces then the penalized nonlinear alternating direction method of multipliers (ADMM), a numerical algorithm that combines the nonlinear ADMM algorithm with the external penalty method. Numerical results are then presented, analyzed and compared against those obtained by applying the Reformulation-Linearization Technique (RLT)-based convex relaxation method together with piecewise linear approximation of the objective function. [ABSTRACT FROM AUTHOR]

We present a method for finding lower bounds on the global infima of integral variational problems, wherein ∫Ωf(x,u(x),∇u(x))dx is minimized over functions u:Ω⊂Rn → Rm satisfying given equality or inequality constraints. Each constraint may be imposed over Ω or its boundary, either pointwise or in an integral sense. These global minimizations are generally nonconvex and intractable. We formulate a particular convex maximization, here called the pointwise dual relaxation (PDR), whose supremum is a lower bound on the infimum of the original problem. The PDR can be derived by dualizing and relaxing the original problem; its constraints are pointwise equalities or inequalities over finite-dimensional sets rather than over infinite-dimensional function spaces. When the original minimization can be specified by polynomial functions of (x,u,∇u), the PDR can be further relaxed by replacing pointwise inequalities with polynomial sum-of-squares (SOS) conditions. The resulting SOS program is computationally tractable when the dimensions m,n and the number of constraints are not too large. The framework presented here generalizes an approach of Valmorbida, Ahmadi, and Papachristodoulou [IEEE Trans. Automat. Control, 61 (2016), pp. 1649-1654]. We prove that the optimal lower bound given by the PDR is sharp for several classes of problems, whose special cases include leading eigenvalues of Sturm-Liouville problems and optimal constants of Poincaré inequalities. For these same classes, we prove that SOS relaxations of the PDR converge to the sharp lower bound as polynomial degrees are increased. Convergence of SOS computations in practice is illustrated for several examples. [ABSTRACT FROM AUTHOR]

Based on a factorization of an input covariance matrix, we define a mild generalization of an upper bound of Nikolov and of Li and Xie for the NP-hard constrained maximum-entropy sampling problem (CMESP). We demonstrate that this factorization bound is invariant under scaling and independent of the particular factorization chosen. We give a variable-fixing methodology that could be used in a branch-and-bound scheme based on the factorization bound for exact solution of CMESP, and we demonstrate that its ability to fix is independent of the factorization chosen. We report on successful experiments with a commercial nonlinear programming solver. We further demonstrate that the known "mixing" technique can be successfully used to combine the factorization bound with the factorization bound of the complementary CMESP and with the "linx bound" of Anstreicher. History: Andrea Lodi, area editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3] and the Air Force Office of Scientific Research [Grant A9550-19-1-0175]. [ABSTRACT FROM AUTHOR]

Skipped median is more robust than median when outliers are not symmetrically distributed. In this work, we propose a novel algorithm to estimate the skipped median. The idea of skipped median and the new algorithm are extended to regression problem, which is called least clipped absolute deviation (LCAD). Since our proposed algorithm for nonconvex LCAD optimization makes use of convex least absolute deviation (LAD) procedure as a subroutine, regularizations developed for LAD can be directly applied, without modification, to LCAD as well. Numerical studies demonstrate that skipped median and LCAD are useful and outperform their counterparts, median and LAD, when outliers intervene asymmetrically. Some extensions of the idea for skipped median and LCAD are discussed. [ABSTRACT FROM AUTHOR]

In this paper, we revisit a biobjective optimization problem arising in software-defined networking with availability guarantees. The problem jointly optimizes the number of controllers and their locations, as well as optimizes a set of links that can be upgraded to achieve intercontroller availability targets. This problem is known to be NP-complete, includes generalized nonlinear flow constraints and includes nonlinear and nonconvex path pair availability constraints. In this paper, we propose an iterative approach for solving the optimization problem. The approach consists in a linear approximation that is obtained through convex relaxation. The linear approximated problem is solved iteratively, and can be tailored to be as close to the original problem as possible at the expense of a greater computational effort. The results obtained using this approach are compared with previously obtained ones. We show how the iterative approach is able to significantly improve most of the tested instances (or find the same solution as previously obtained) within feasible computational effort. [ABSTRACT FROM AUTHOR]

We study the Sparse Plus Low-Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, collaborative filtering, and medical imaging. We introduce a novel formulation for SLR that directly models its underlying discreteness. For this formulation, we develop an alternating minimization heuristic that computes high-quality solutions and a novel semidefinite relaxation that provides meaningful bounds for the solutions returned by our heuristic. We also develop a custom branch-and-bound algorithm that leverages our heuristic and convex relaxations to solve small instances of SLR to certifiable (near) optimality. Given an input n-by-n matrix, our heuristic scales to solve instances where n = 10000 in minutes, our relaxation scales to instances where n = 200 in hours, and our branch-and-bound algorithm scales to instances where n = 25 in minutes. Our numerical results demonstrate that our approach outperforms existing state-of-the-art approaches in terms of rank, sparsity, and mean-square error while maintaining a comparable runtime. [ABSTRACT FROM AUTHOR]

We study mixed-integer nonlinear optimization (MINLO) formulations of the disjunction x ∈ { 0 } ∪ [ ℓ , u ] , where z is a binary indicator for x ∈ [ ℓ , u ] ( 0 ≤ ℓ < u ), and y "captures" f(x), which is assumed to be convex and positive on its domain [ ℓ , u ] , but otherwise y = 0 when x = 0 . This model is very useful in nonlinear combinatorial optimization, where there is a fixed cost c for operating an activity at level x in the operating range [ ℓ , u ] , and then, there is a further (convex) variable cost f(x). So the overall cost is c z + f (x) . In applied situations, there can be N 4-tuples (f , ℓ , u , c) , and associated (x, y, z), and so, the combinatorial nature of the problem is that for any of the 2 N choices of the binary z-variables, the non-convexity associated with each of the (f , ℓ , u) goes away. We study relaxations related to the perspective transformation of a natural piecewise-linear under-estimator of f, obtained by choosing linearization points for f. Using 3-d volume (in (x, y, z)) as a measure of the tightness of a convex relaxation, we investigate relaxation quality as a function of f, ℓ , u, and the linearization points chosen. We make a detailed investigation for convex power functions f (x) : = x p , p > 1 . [ABSTRACT FROM AUTHOR]

Many problems in imaging and low-level vision can be formulated as nonconvex variational problems. A promising class of approaches to tackle such problems are convex relaxation methods, which consider a lifting of the energy functional to a higher-dimensional space. However, they come with increased memory requirements due to the lifting. The present paper is an extended version of the earlier conference paper by Ye et al. (in: DAGM German conference on pattern recognition (GCPR), 2021) which combined two recent approaches to make lifting more scalable: product-space relaxation and sublabel-accurate discretization. Furthermore, it is shown that a simple cutting-plane method can be used to solve the resulting semi-infinite optimization problem. This journal version extends the previous conference work with additional experiments, a more detailed outline of the complete algorithm and a user-friendly introduction to functional lifting methods. [ABSTRACT FROM AUTHOR]