# Tagged Questions

This is for questions on Quadratic Programming (QP). A QP problem is the problem of minimising or maximising a quadratic objective function subject to affine constraints.

41 views

39 views

### Prioritized solution of a linear system subject to inequality constraints

Consider the following linear system $$y = A_1 x_1 + A_2 x_2$$ subject to the linear constrains $$C_1 x_1 + C_2 x_2 \leq d$$ I am looking ...
150 views

67 views

### How to obtain the optimal Lagrange multiplier vectors if the globally optimal solution for a nonconvex QCQP is found?

I am using a black-box solver to solve the following non-convex QCQP to global optimality. $$\min_x x^TQ_0x + c^T x \\ s.t. \quad x^TQ_1x+c_1^Tx=b_1 \\ Ax=b \\ l\leq x\leq u$$ where $Q_0$ is ...
10 views

I have the following problem: $$\min_{w,\theta\ge0}\frac{1}{2}\|w-w_t\|^2+(\theta-\theta_t)^2 \text{ s.t. } w^\top(\hat n\hat z-nz)+\theta w^\top(z-\hat z)+1 \le 0,\theta-1\le 0$$ Notice that $w$ is ...
108 views

### Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix B)...
50 views

12 views

15 views

### Tree-width of a quadratic pseudo-Boolean function

A pseudo-Boolean function $f : \mathbb{B}^n \mapsto \mathbb{R}$ is of the following form. $$f \left(x_1, \ldots, x_n\right) = \sum_{S\subseteq V} c_S \prod_{j \in S} x_j$$ Here $c_S \in \mathbb{R}$,...
34 views

### Residual norm of active set method in non negative least squares

I am having trouble with understanding one of the statements in active set methods done for non negative least squares given in Book written by Lawson. The quadratic problem can be written as \begin{...
22 views

### Quadratization of $5 x_1 x_2 โ 7 x_1 x_2 x_3 x_4 + 2 x_1 x_2 x_3 x_5$ using Rosenberg's algorithm

In section 4.4 of Pseudo-Boolean Optimization by Boros et al., the authors have reproduced Rosenberg's quadratization algorithm as follows. Then they have given an example of implementing the ...
10 views

### Bipartite Matching with quadratic objective

I'm looking for the best way to formulate and solve the following bipartite matching problem: I have n nodes on the left hand side of the diagram, partitioned into ...
46 views

### Convex optimization: Piece-wise, quadratic objective

This question is about convex optimization with a convex objective function, which is defined piecewise. We have two functions, a concave function A(x) and a strictly convex, increasing function B(x), ...
13 views

### Matrix inversion vs. iterative scheme in quadratic programming problem for high dimensions

According to this entry about quadratic programming problems with equality constraints the system will not be positive definite any longer for higher dimensions. For lower dimensions this system could ...
26 views

### How to efficiently solve a quadratic program repeatedly?

I have a quadratic problem, \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} ($Q$ is semidefinite) which I want to solve repeatedly, with the slight change of p and Q, ...