Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCausality, Passivity and Optimization: Strong Duality in Quadratically Constrained Quadratic Programs for Waves
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove that a special variety of quadratically constrained quadratic programs, occurring frequently in conjunction with the design of wave systems obeying causality and passivity (i.e. systems with bounded response), universally exhibit strong duality. Directly, the problem of continuum (grayscale or effective medium) device design for any (complex) quadratic wave objective governed by independent quadratic constraints can be solved as a convex program. The result guarantees that performance limits for many common physical objectives can be made nearly tight, and suggests far-reaching implications for problems in optics, acoustics, and quantum mechanics.
rate research
Read More
We study nonconvex homogeneous quadratically constrained quadratic optimization with one or two constraints, denoted by (QQ1) and (QQ2), respectively. (QQ2) contains (QQ1), trust region subproblem (TRS) and ellipsoid regularized total least squares problem as special cases. It is known that there is a necessary and sufficient optimality condition for the global minimizer of (QQ2). In this paper, we first show that any local minimizer of (QQ1) is globally optimal. Unlike its special case (TRS) with at most one local non-global minimizer, (QQ2) may have infinitely many local non-global minimizers. At any local non-global minimizer of (QQ2), both linearly independent constraint qualification and strict complementary condition hold, and the Hessian of the Lagrangian has exactly one negative eigenvalue. As a main contribution, we prove that the standard second-order sufficient optimality condition for any strict local non-global minimizer of (QQ2) remains necessary. Applications and the impossibility of further extension are discussed.
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 of a stochastic function. 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 to popular alternatives.
We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadratic constraint into a linear form by sampling a set of low-discrepancy points. The transformed problem can then be solved by applying any state-of-the-art large-scale quadratic programming solvers. We show the convergence of our approximate solution to the true solution as well as some finite sample error bounds. Experimental results are also shown to prove scalability as well as improved quality of approximation in practice.
We propose a sigmoidal approximation for the value-at-risk (that we call SigVaR) and we use this approximation to tackle nonlinear programs (NLPs) with chance constraints. We prove that the approximation is conservative and that the level of conservatism can be made arbitrarily small for limiting parameter values. The SigVar approximation brings scalability benefits over exact mixed-integer reformulations because its sample average approximation can be cast as a standard NLP. We also establish explicit connections between SigVaR and other smooth sigmoidal approximations recently reported in the literature. We show that a key benefit of SigVaR over such approximations is that one can establish an explicit connection with the conditional value at risk (CVaR) approximation and exploit this connection to obtain initial guesses for the approximation parameters. We present small- and large-scale numerical studies to illustrate the developments.
We use the technique of information relaxation to develop a duality-driven iterative approach to obtaining and improving confidence interval estimates for the true value of finite-horizon stochastic dynamic programming problems. We show that the sequence of dual value estimates yielded from the proposed approach in principle monotonically converges to the true value function in a finite number of dual iterations. Aiming to overcome the curse of dimensionality in various applications, we also introduce a regression-based Monte Carlo algorithm for implementation. The new approach can be used not only to assess the quality of heuristic policies, but also to improve them if we find that their duality gap is large. We obtain the convergence rate of our Monte Carlo method in terms of the amounts of both basis functions and the sampled states. Finally, we demonstrate the effectiveness of our method in an optimal order execution problem with market friction and in an inventory management problem in the presence of lost sale and lead time. Both examples are well known in the literature to be difficult to solve for optimality. The experiments show that our method can significantly improve the heuristics suggested in the literature and obtain new policies with a satisfactory performance guarantee.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
