Questions tagged [quadratic-programming]
For questions on quadratic programming, methods to solve them and related solvers. Use this tag along with (optimization).
22
questions
1
vote
0answers
68 views
Question on quadratically constrained quadratic program
If the constrained optimization problem is a quadratically constrained quadratic program of the form \begin{align}\min&\quad x^HQx-a(x+x^H)+b|z^Hx|^2\\\text{s.t.}&\quad\|x\|^2\le1\end{align} ...
3
votes
1answer
44 views
Supported pyomo free solvers for (non-convex) quadratic programming
Any one had the chance to use pyomo with free/open-source solvers that handle quadratic optimization problems, which they could be convex or not, but preferably as general as possible.
4
votes
1answer
96 views
Transforming a Quadratic constraint to SOCP
I have a problem similar to Markowitz portfolio optimization that I would like to transform into second-order cone programming. I have a linear objective function with a quadratic constraint (assuming ...
6
votes
2answers
91 views
Ways to strengthen QCQP relaxations
I was wondering what types of methods can be used to strengthen QCQP relaxations.
Our solver has all the standard stuff, like constraint propagation, presolving, etc., but some QCQP problems seem to ...
6
votes
4answers
126 views
Sequential quadratic programming source
What are the good text books to learn SQP? Are there any online courses that you can suggest?
6
votes
2answers
176 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, ...
7
votes
1answer
150 views
Why is there a constant in the objective function of the *best subset selection problem*?
This article presents the following formulation of the best subset selection problem
$$\min_{\|\beta\|_0\leq k}\frac{1}{2}\|y-X\beta\|^2_2$$
I wonder where the $1/2$ comes from. Help appreciated.
8
votes
0answers
83 views
For subset selection regression as a mixed integer program, how tightly should the bounding box be set?
When solving best subset regression as a mixed integer program, how do you decide how tightly to bound the range of values of the $X$ values? When the box is tight, the solver finds a solution ...
11
votes
4answers
624 views
Integer programming problem with simple quadratic objective function in Python
I have $n$ objects that need to be divided among $k$ groups. Each group must receive at least $5$ objects. In addition, the percentage of objects in group $i$ should be as close as possible to $p_i$ ...
9
votes
2answers
261 views
Convexity of a QP
In quadratic programming (QP), you encounter an objective of the following form:
$$x^TQx + c^Tx$$
and often it's desirable to know if the QP is convex. One method to check for convexity is by ...
9
votes
1answer
185 views
How can I model regression with an asymmetric loss function?
Mosek provided a concrete example of using the Huber loss function,
Huber loss, which is great!
One problem I am trying to tackle is to use asymmetric loss, as described in the answer of asymmetric ...
13
votes
1answer
253 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 ...
15
votes
2answers
256 views
Divisibility constraints in integer programming
In the study of a certain pure mathematical problem (related to infinite-dimensional Lie algebras) I found myself in a situation where it would be very desirable to be able to solve an integer ...
11
votes
1answer
145 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 ...
7
votes
2answers
326 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 ...
13
votes
1answer
640 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.
16
votes
3answers
930 views
Bin Packing with Relational Penalization
There are $ N $ bins with equal capacity $ C $. In addition, there are $ N $ objects $x_1, x_2, \dots, x_N $ that need to be accommodated using the least amount of bins. Each object $x_i$ has a volume ...
10
votes
2answers
132 views
Global optimality condition of non-convex quadratic programs
We know that a convex quadratic maximization (not minimization!) on a polyhedron has its global optimal value on a vertex.
Also, I have read in some papers that checking whether a vertex is globally ...
14
votes
4answers
450 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 ...
16
votes
2answers
163 views
Can we replace a binary variable with a continuous variable using a quadratic equality constraint?
Is it possible to replace a binary variable $x$ with a continuous variable that satisfies the quadratic equality constraint $x^2 - x=0$?
The function $f(x) = x^2 -x$ is not a convex function. Can ...
12
votes
2answers
111 views
Where can I find test instances for convex quadratic programming?
I am looking for (sources of) convex quadratic programming instances with linear constraints. I am open for both continuous and mixed integer problems, but do not want randomly generated instances.
...
17
votes
3answers
293 views
How to model nonlinear regression?
As part of my research in statistics, I recently stumbled upon the paper by Wang, 2006, although its primary audience is for those who teach.
For simple linear regression, quadratic programming can ...
