Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.

784 questions
Filter by
Sorted by
Tagged with
28 views

### Closed-form solution to linear regression under positive semi-definite constraint

Let $X,Y\in \mathbb{R}^{d\times n}$ and $W\in\mathbb{R}^{d\times d}$. Is there a closed-form solution to the following minimization problem? $$\min_W \|WX - Y\|_F^2, \quad W \succeq 0.$$
• 391
13 views

### Computational Time of Interior Point Methods Per Iteration for Nonconvex QP [closed]

The title is pretty much self-explanatory. I am trying to find the computational time of interior point methods per iteration for nonconvex QP. As far as I know, it is $\mathcal {O}(n^3)$ for a ...
1 vote
40 views

### solving trace minimization problem in quadratic programming

I'd like to minimize the trace of $P - XHP - PH^T X^T + XSX^T$ with the constraints that every entry of $X \geq 0$ here $P$ is $n$ by $n$ positive definite, $H$ is $m$ by $n$, S is $m$ by $m$ positive ...
• 179
26 views

### What am I missing in deriving the dual of this soft margin support vector machine?

I am trying to derive the dual form of a support vector machine from its primal form (see top of section "Kernel SVM"). While missing from the formulation linked above, I've proceeded thus ...
• 1,964
1 vote
23 views

### Quadratic Optimization with positivity, equality constraints - Literature Review?

I'm trying to solve a problem of the form $\min x^T Q x$ such that $Ax = b$ and $x_i \ge 0$ for all components $i$; $x, b$ are vectors; and $Q, A$ are matrices. In this case $Q$ is square and positive ...
• 1,300
34 views

• 5,267
48 views

### Book/Notes Recommendation for Quadratic Optimization

While self-studying and planning on doing some small-time research/fun based on Philip Wolf's "The Simplex Method for Quadratic Programming", I got interested in the notion of quadratic ...
• 2,011
21 views

• 5,967
82 views

### Find the max and min of $(a \mathbf{x} + c)(b \mathbf{x} + d)$, where $\mathbf{x}$ is a vector with linear constraints.

Suppose there is a $n$-dimensional column vector $\mathbf{x}$, and an objective function $f(\mathbf{x}) = (a \mathbf{x} + c)(b \mathbf{x} + d)$, where $a$ and $b$ are $n$-dimensional row vector; $c$ ...
72 views

### Proving that a set of quadratic constraints have no solution

I want to prove that a given set of quadratic and linear inequalities has no solution. The set size is of 13 equations, or, including the positiveness constrain, 21 equations. I already used a python ...
• 23
39 views

### How to handle the equality constraint that cannot be satisfied?

Given an optimization problem $$\text{min} \space x^T M x \\ \text{s.t.} \space Ax = b$$ where an analytical solution called weighted general inverse exists. However, we now know that Ax = b some ...
56 views

### Quadratic programming with the non-negativity constraint

Let us assume that $B$ is a symmetric positive semi-definite matrix in $\mathbb{R}^{m\times m}$. What is the optimum solution for the following constrained quadratic programming problem: min_{X>=...
• 662
1 vote
113 views

### Quadratic programming: maximizing the euclidean norm

The setting is the following, I have a full-dimensional polytope $\mathcal{F}: A \cdot x \leq \vec{b}$ that has been transformed such that it contains the origin: $\vec{0} \in \mathcal{F}$. I need to ...
• 133
1 vote
210 views

### Proof for the equivalence of the convex optimization problem in Kernel Fisher LDA paper.

All, I am trying to understand the convex optimization move made from eqns. 3 -> eqns. 4 in the Kernel Fisher LDA paper. The authors mention that the proof of equivalence is straightforward, and ...
• 61
35 views

### Linear vs Quadratic integer programming on the example spread vs variance

I consider the following two instances of the same problem, computing the spread as the difference of the highest and lowest occurrence of something in a set. Further, I compute the variance of the ...
• 255
1 vote
I am reading about SVMs and want to confirm that I understand the optimality conditions. Details below: Consider the $n$ points $x_1, x_2, \dots, x_n$, each with $d$ dimensions, and consider $n$ ...