Questions tagged [quadratic-programming]

For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).

Filter by
Sorted by
Tagged with
16
votes
2answers
506 views

Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?

The closest thing I know is the computer vision problem, in which an image is de-blurred and/or de-noised by quadratizing a quartic problem into a quadratic optimization problem (QUBO) and then the ...
14
votes
4answers
951 views

CPLEX non-convex Quadratic Programming algorithms

CPLEX solves non-convex quadratic problems to global optimality with a global optimality option (in version 12). The relevant pages are this and this. I benchmarked many solvers, and see that CPLEX ...
13
votes
1answer
827 views

What is quadratization?

In the context of discrete optimization, what exactly does it mean to "quadratize" a function? The term seems to be used mainly by operations researchers, in my experience.
6
votes
2answers
399 views

Assignment problem where assignments must be done sequentially

I have a weird planning problem. I think it falls under the assignment category, but I'm not sure because I'm not familiar with assignment problems, and also because there is a "temporal" angle to it, ...
5
votes
1answer
257 views

Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only

I'm totally new to the world of optimization and I have an optimization problem that I think it can be formulated as Mixed Integer Quadratically Constrained Quadratic Program (QCQP) but I'm not sure ...
11
votes
1answer
158 views

Quadratic programming using CPLEX: how to check whether candidate is an extreme point?

I am currently solving an indefinite quadratic program with linear constraints using CPLEX. Moreover, I am trying to determine whether the candidate point CPLEX is feeding my callback function is an ...
8
votes
2answers
177 views

Inverse Ising problem

Inverse Ising Problem The inverse ising problem means fitting the coupling $J_{ij}$ and field $h_{i}$ parameters given a sample of configurations of spins. Each spin $s_{i}$ is either +1 or -1. The ...
7
votes
2answers
377 views

How can I linearize or convexify this binary quadratic optimization problem?

I have an optimization problem as below. I am having a hard time with the last constraint. $\max \eta$ subject to ${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$ here $\bf{A}$ is a Binary ...
5
votes
1answer
196 views

PAVA-like solution to simple QP

Let $l,u\in\mathbb{R}^n$, and consider the QP: $$\min_{l\le x\le u} {(\Delta x)^\top (\Delta x)}$$ where $\Delta x=[x_2-x_1,\,x_3-x_2,\,\dots,\,x_n-x_{n-1}]^\top$. I.e. we want to minimize the squared ...
3
votes
1answer
90 views

How to exponentiate binary variables in QUBO-type problems?

Ising Model In an Ising model, the Hamiltonian of one configuration of spins $\vec{s}$ is: $$ H(\vec{s}, \mathcal{J}, \mathcal{h}) = \sum_{i} h_{i} s_{i} + \sum_{i \ne j}J_{ij} s_{i}s_{j} $$ where ...
3
votes
1answer
139 views

Linearizing power term in objective function

I would like to linearize $x^2$ term in my objective function. I understand this can be solved using quadratic programming solver; however, for my use case linearization is necessary to convert it to ...