Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 37 for “"duality gap"”.
-
Worst-case bounds for bin-packing heuristics with applications to the duality gap of the one-dimensional cutting stock problem
… bin-packing problem, and their relationship. The duality gap of the former is investigated and a characterisation of a class of cutting stock problems with the next round-up property is given. It is shown that worst-case bounds for bin-packing heuristics can be and are best expressed in terms of …
-
New duality results for separable optimization problems in infinite dimensions : applications to optimal control theory
… constraint qualifications for obtaining strong duality and zero duality gap for this separable optimization problem. The second part is devoted to the application of duality theory to optimal control problems, namely, to control-constrained linear quadratic programming problems (LQ).
-
Optimal scheduling of hydro-thermal power generation systems
… closely from the dual solution using the duality gap as a termination criterion. A heuristic is used to construct nearly optimal solutions to the primal problem based on the information provided by the dual problem. The decomposition is such as to allow an implementation on a transputer …
-
Analysis of Convex Relaxations for Nonconvex Optimization
… ways of obtaining convex relaxations: Lagrangian duality and semidefinite programming. The difference between the optimal value of the convex relaxation and that of the original problem is measured by the integrality gap or duality gap, which is of central importance in convex relaxation including …
-
EFFICIENT DATA ASSOCIATION ALGORITHMS FOR MULTI-TARGET TRACKING
… a su cient and necessary condition for the duality gap to be zero, or equivalently, for the Lagrangian relaxation approach to nd the optimal solution to the assignment problem with a guarantee. Also, we establish a mild and easy-to-check condition, under which the dual problem is equivalent …
-
Convex relaxation methods in optimisation and robust control
… algorithm is proposed for breaching the gap between the Quadratic Integer Programming (QIP) and its convex relaxation which is closely related to the structured singular value problem. It is shown that the duality gap can be reduced, provided a Reduced Rank Quadratic Integer Problem …
-
Solving Combinatorial Optimization Problems using Statistical Learning
… competent solutions (in terms of runtime versus duality gap), not necessarily incumbent, to the capacitated vehicle routing problem and the bin packing problem—which have non-deterministic polynomial computational complexity. The core idea is based on learning to approximate the decisions made by …
-
A MODEL-FREE ANALYSIS OF DISCRETE TIME FINANCIAL MARKETS
… the choice of S. We also provide a superhedging duality theorem. We show that the initial cost of the cheapest portfolio that dominates a contingent claim on every possible path, might be strictly greater than the upper bound of the no-arbitrage prices. We therefore characterize the subset of …
-
Convex relaxation based locational marginal prices for electricity markets
… the nonconvex economic dispatch problem has zero duality gap, the RLMPs exhibit properties similar to locational marginal prices with linearized power flow equations. Otherwise, they behave similarly to convex hull prices. Restricted to radial distribution networks, RLMPs reduce to second-order …
-
Empirical risk minimization with f-divergence regularization for machine learning
… function, it is demonstrated that the duality gap is zero, and insights from the dual formulation are used to derive explicit expressions for the generalization error of general statistical learning algorithms in terms of f-divergence-regularized learning frameworks.
-
Modelling and solution methods for renewables-driven energy markets
… obtain an arbitrary precise solution in case of duality gap absence and ii) embedding these techniques within a duality-based branching strategy that would ensure solving to optimality even in the presence of duality gap. The models in this dissertation serve as a support for decision-makers …
-
Relaxações tratáveis para problemas de otimização cúbicos restritos à esfera
… since it has a concave dual problem with no duality gap. In the literature, several relaxation techniques have been studied to polynomials problems, based on RLT inequalities and via Semidefinite Programming, obtaining good results in quadratic programming, and recently extended for programs …
-
First-order methods for structured optimization
… the elegant safe-screening rule that depends on duality gap to atomic-norm regularized problems. In the second part, we study online mirror descent (OMD) with unknown time horizon and unbounded domain, which is known to suffer from linear regret. We provide a stabilization technique and show that …
-
An Algorithm for Reliable Shortest Path Problem with Travel Time Correlations
… efficiency of the algorithm in terms of relative duality gap and computational time. Besides, there is evidence showing that, though having longer computational time, the ellipsoid updating method tends to obtain better solutions compared with the sub-gradient method. The proposed algorithm …
-
Regularities in variational analysis and their applications in nonconvex optimization
… operators are also established. Asymmetry and duality gap occur in this process as consequences of Bregman distance.
-
Differential-algebraic equations in primal dual interior point optimization methods: A new approach to the parameterization of the central trajectory.
… parameterization of the central trajectory. The duality gap depends linearly on the barrier parameter for the points in the central trajectory. In this research, a new approach to the parameterization of the central trajectory for primal dual IPMs is proposed. A continuous dynamical system that …
-
Interior-point algorithms for solving linear complementarity problems and their applications
… the accuracy parameter and the starting point’s duality gap. In Chapter 3, we propose another class of AET functions leading to a predictor-corrector (PC) IPA for solving P∗(κ)-LCPs and prove that it has the same complexity as the currently known best ones for IPAs. Chapter 4 extends our research …
-
Duality in stochastic and dynamic optimization
The main theme in this dissertation is convex duality in stochastic and dynamic optimization. The analysis is based on the conjugate duality framework of Rockafellar and on the theory of convex integral functionals. The dissertation consists of an overview and of three articles. In the first …
-
Farkas - type results for convex and non - convex inequality systems
… be able to use the fruitful Fenchel - Lagrange duality approach, to the primal problem we attach an equivalent problem which is a convex optimization problem. After giving a dual problem to the problem we initially treat, we provide weak necessary conditions which secure strong duality, i.e., …
-
Energy efficient and secure wireless communication systems
… of perturbation function, we show that the duality gap in the considered system is always zero under some general conditions, despite the non-convexity of the primal problem. Thus, an efficient closed-form power allocation solution for maximization of the energy efficiency of data …
Page 1 of 2