lagrangian dual – Optimization Online

A barrier Lagrangian dual method for multi-stage stochastic convex semidefinite optimization

Published: 2022/01/07

Nonlinear Optimization, Semi-definite Programming, Stochastic Programming interior point methods, lagrangian dual, Multi-stage stochastic convex programming, polynomial time complexity, semidefinite programming

In this paper, we present a polynomial-time barrier algorithm for solving multi-stage stochastic convex semidefinite optimization based on the Lagrangian dual method which relaxes the nonanticipativity constraints. We show that the barrier Lagrangian dual functions for our setting form self-concordant families with respect to barrier parameters. We also use the barrier function method to improve … Read more

A Lagrangian Dual Method for Two-Stage Robust Optimization with Binary Uncertainties

Published: 2021/12/24, Updated: 2022/01/14

Anirudh Subramanyam

Robust Optimization binary uncertainty, lagrangian dual, robust optimization, two-stage problems

This paper presents a new exact method to calculate worst-case parameter realizations in two-stage robust optimization problems with categorical or binary-valued uncertain data. Traditional exact algorithms for these problems, notably Benders decomposition and column-and-constraint generation, compute worst-case parameter realizations by solving mixed-integer bilinear optimization subproblems. However, their numerical solution can be computationally expensive not only … Read more

Lagrangian Dual Decision Rules for Multistage Stochastic Mixed Integer Programming

Published: 2019/12/31, Updated: 2022/08/15

Maryam Daryalal

Merve Bodur

James R. Luedtke

Stochastic Programming decision rules, lagrangian dual, multistage stochastic mixed integer programming, sampling, two-stage approximation

Multistage stochastic programs can be approximated by restricting policies to follow decision rules. Directly applying this idea to problems with integer decisions is difficult because of the need for decision rules that lead to integral decisions. In this work, we introduce Lagrangian dual decision rules (LDDRs) for multistage stochastic mixed integer programming (MSMIP) which overcome … Read more

A Polynomial-time Algorithm with Tight Error Bounds for Single-period Unit Commitment Problem

Published: 2019/11/01

(Mixed) Integer Nonlinear Programming, Approximation Algorithms, Scheduling convex relaxation, lagrangian dual, mixed-integer quadratic programming, nonlinear programming, unit commitment problem

This paper proposes a Lagrangian dual based polynomial-time approximation algorithm for solving the single-period unit commitment problem, which can be formulated as a mixed integer quadratic programming problem and proven to be NP-hard. Tight theoretical bounds for the absolute errors and relative errors of the approximate solutions generated by the proposed algorithm are provided. Computational … Read more

Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

Published: 2004/10/30, Updated: 2005/02/03

Constrained Nonlinear Optimization, Global Optimization, Linear, Cone and Semidefinite Programming global optimization, lagrangian dual, lagrangian relaxation, polynomial optimization problem, semidefinite relaxation, sparsity, sums of squares optimization

Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) … Read more

Sums of Squares Relaxations of Polynomial Semidefinite Programs

Published: 2003/11/11, Updated: 2003/11/19

Masakazu Kojima

Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming bilinear matrix inequality, global optimization, lagrangian dual, lagrangian relaxation, penalty function, polynomial optimization problem, semidefinite relaxation, sums of squares optimization

A polynomial SDP (semidefinite program) minimizes a polynomial objective function over a feasible region described by a positive semidefinite constraint of a symmetric matrix whose components are multivariate polynomials. Sums of squares relaxations developed for polynomial optimization problems are extended to propose sums of squares relaxations for polynomial SDPs with an additional constraint for the … Read more

Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems

Published: 2003/09/29

Sunyoung Kim

Masakazu Kojima

Hayato Waki

Global Optimization Theory, Semi-definite Programming global optimization, lagrangian dual, lagrangian relaxation, polynomial optimization problem, semidefinite programming, semidefinite relaxation, sparsity, sums of squares optimization

Sequences of generalized Lagrangian duals and their SOS (sums of squares of polynomials) relaxations for a POP (polynomial optimization problem) are introduced. Sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the … Read more

Lagrangian dual interior-point methods for semidefinite programs

Published: 2001/04/03, Updated: 2004/04/29

Mituhiro Fukuda

Masakazu Kojima

Masayuki Shida

Convex Optimization, Second-Order Cone Programming, Semi-definite Programming bfgs quasi-newton method, central trajectory, conjugate gradient method, lagrangian dual, linear program over convex cones, predictor-corrector method, primal-dual interior-point method, second-order cone program, semidefinite programming

This paper proposes a new predictor-corrector interior-point method for a class of semidefinite programs, which numerically traces the central trajectory in a space of Lagrange multipliers. The distinguished features of the method are full use of the BFGS quasi-Newton method in the corrector procedure and an application of the conjugate gradient method with an effective … Read more