penalty methods – Optimization Online

A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

Published: 2025/06/12

(Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Alternating direction methods, Mixed integer linear bilevel optimization, penalty methods, primal heuristics, Single-level reformulations

Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

Solving a linear program via a single unconstrained minimization

Published: 2025/05/27

Adilet Otemissov

Alina Abdikarimova

Linear Programming, Nonlinear Systems and Least-Squares, Unconstrained Optimization global convergence, linear programming, penalty methods, regularized newton methods, unconstrained minimization, zero residual problem

This paper proposes a novel approach for solving linear programs. We reformulate a primal-dual linear program as an unconstrained minimization of a convex and twice continuously differentiable merit function. When the optimal set of the primal-dual pair is nonempty, its optimal set is equal to the optimal set of the proposed merit function. Minimizing this … Read more

First-order penalty methods for bilevel optimization

Published: 2023/01/04

Zhaosong Lu

Sanyou Mei

Constrained Nonlinear Optimization bilevel optimization, first-order methods, minimax optimization, operation complexity, penalty methods

In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower-level part is a convex optimization problem, while the upper-level part is possibly a nonconvex optimization problem. In particular, we propose penalty methods for solving them, whose subproblems turn out to be a structured minimax problem and are … Read more

A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems

Published: 2022/10/24, Updated: 2023/08/14

(Mixed) Integer Nonlinear Programming, Network Optimization, Optimization of Systems modeled by PDEs Alternating direction methods, gas transport networks, Graph decomposition, Mixed-integer nonlinear optimization, penalty methods

We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel … Read more

A Penalty Branch-and-Bound Method for Mixed-Integer Quadratic Bilevel Problems

Published: 2022/07/14

Horländer Andreas

Martin Schmidt

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities bilevel optimization, Branch-and-Bound, mixed integer optimization, penalty methods

We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of … Read more

A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems

Published: 2021/07/02, Updated: 2022/05/30

(Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Complementarity and Variational Inequalities Branch-and-Bound, linear complementarity problems, mixed-integer linear complementarity problems, mixed-integer programming, penalty methods

Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, … Read more

An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems

Published: 2020/11/20, Updated: 2022/01/11

Carina Moreira Costa

Dennis Kreber

Martin Schmidt

(Mixed) Integer Nonlinear Programming, Finance and Economics, Statistics alternating direction method, best subset selection, cardinality constraints, penalty methods, portfolio optimization

Cardinality-constrained optimization problems are notoriously hard to solve both in theory and practice. However, as famous examples such as the sparse portfolio optimization and best subset selection problems show, this class is extremely important in real-world applications. In this paper, we apply a penalty alternating direction method to these problems. The key idea is to … Read more

Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method

Published: 2019/03/11, Updated: 2019/11/06

Thomas Kleinert

Martin Schmidt

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming alternating direction method, bilevel optimization, mixed-integer bilevel optimization, penalty methods, stationary points

Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain … Read more

Towards an efficient Augmented Lagrangian method for convex quadratic programming

Published: 2019/01/17, Updated: 2019/12/10

Luís Felipe Bueno

Gabriel Haeser

Luiz-Rafael Santos

Constrained Nonlinear Optimization, Linear Programming, Quadratic Programming augmented lagrangian method, convex quadratic programming, interior point methods, linear programming, penalty methods

Interior point methods have attracted most of the attention in the recent decades for solving large scale convex quadratic programming problems. In this paper we take a different route as we present an augmented Lagrangian method for convex quadratic programming based on recent developments for nonlinear programming. In our approach, box constraints are penalized while … Read more

The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems

Published: 2018/08/27, Updated: 2018/08/29

Yura Malitsky

Convex Optimization, Nonsmooth Optimization convergence rate, distributed optimization, first-order methods, linearly constrained optimization problem, penalty methods, primal-dual algorithms

In this work, we show that for linearly constrained optimization problems the primal-dual hybrid gradient algorithm, analyzed by Chambolle and Pock [3], can be written as an entirely primal algorithm. This allows us to prove convergence of the iterates even in the degenerate cases when the linear system is inconsistent or when the strong duality … Read more