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

782 questions
Filter by
Sorted by
Tagged with
13k views

### How does the SVD solve the least squares problem?

How do I prove that the least-squares solution for $$\text{minimize} \quad \|Ax-b\|_2$$ is $A^{+} b$, where $A^{+}$ is the pseudoinverse of $A$?
• 639
989 views

### Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$

Let $x_1,x_2,\ldots,x_n$ be $n$ non-negative numbers ($n>2$) with a fixed sum $S$. What is the maximum of $x_1 x_2 + x_2 x_3 + \dots + x_n x_1$?
11k views

### Are "constrained linear least squares" and "quadratic programming" the same thing?

A Quadratic Programming problem is to minimize: $f(\mathbf{x}) = \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}$ subject to $A\mathbf{x} \leq \mathbf b$; $C\mathbf{x} = \mathbf d$; ...
• 273
10k views

### Does gradient descent converge to a minimum-norm solution in least-squares problems?

Consider running gradient descent (GD) on the following optimization problem: $$\arg\min_{\mathbf x \in \mathbb R^n} \| A\mathbf x-\mathbf b \|_2^2$$ where $\mathbf b$ lies in the column space of $A$...
• 3,145
4k views

### Linear programming with one quadratic equality constraint

I have a problem that can be formulated as a linear program with one quadratic equality constraint: where variable $x$ is an $n$-dimensional vector and $H$ is a positive semidefinite $n \times n$ ...
• 111
20k views

### How do you minimize "hinge-loss"?

A lot of material on the web regarding Loss functions talk about "minimizing the Hinge Loss". However, nobody actually explains it, or at least gives some example. The best material I found is here ...
• 1,652
3k views

### Analog of Simplex Method for Quadratic Programming

It happened so I need to work with an algorithm for solving QP problems. The main issue here is that I can't find any references to this algorithms (at least no references in sources in english). ...
7k views

• 321
9k views

### Quadratic function must be positive definite to have a unique minimum

Let $$V(x):=a+b^{T}x+\frac{1}{2}x^{T}Cx$$ for some $a \in \mathbb{R}$, $b \in \mathbb{R}^{n}$, $C \in \mathbb{R}^{nxn}$ that for $V$ to have a strict unique minimum it is imperative that $C>0$. I ...
3k views

### Solving box-constrained least-squares

I have a linear least squares problem with linear constraints: $$\min_x \| A x - b \|^2 \quad\text{subject to}\quad k_1 \leq x_i \leq k_2$$ Should quadratic programming be used here? If so, what would ...
• 71
897 views

• 1,720
834 views

### Minimum volume covering ellipse

Given a convex polygon in the plane, consider the smallest-area ellipse that contains this polygon. This is the "minimal volume covering ellipsoid" or "minimal volume enclosing ellipsoid" (MVEE), and ...
• 487
434 views

### Transform an optimisation problem into a linearly-constrained quadratic program?

I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
• 278
2k views

• 1,120
2k views

### How to Solve Linear Least Squares with Matrix Inequality Constraint

I need to solve the following inequality-constrained least-squares problem in vector $x$ $$\min_{Ax \geq 0} \frac{1}{2} \|Ax-b\|_2^2$$ where matrix $A$ and vector $b$ are given. I am totally ...
• 641
3k views

I am trying to maximize a (semi) convex quadratic function over a convex (box constraints) set, however I don't know if it is possible to solve (in not too long computation time). The problem is \... • 291 4 votes 2 answers 2k views ### A standard quadratic minimization problem Consider the "Complex" Quadratic minimization problem \begin{align} \min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~\mathbf{{x}}^H\mathbf{Q}\mathbf{x}-2~\Re{(\mathbf{x}^H\mathbf{b})}+1 \end{align} \Re(... • 8,947 4 votes 2 answers 4k views ### Linear Least Squares with Non Negativity Constraint I am interested in the linear least squares problem:\min_x \|Ax-b\|^2$$Without constraint, the problem can be directly solved. With an additional linear equality constraint, the problem can be ... • 1,963 4 votes 1 answer 227 views ### Show that (A^TA)^{-1} A^T minimizes \mbox{Tr}(X^T X) over all matrices X such that XA = I How can I show that (A^TA)^{-1} A^T minimizes \mathbf{Tr}(X^TX) over all matrices X such that XA = I? [Note that A is an m \times n matrix.] I've tried rearranging the trace, and ... • 3,979 4 votes 2 answers 1k views ### indicator function in objective function with L_2 norm I am trying to solve an optimization problem. The objective function is as follow arg\ min \lVert\mathbb{A}\mathbf{x} - \mathbf{b}\rVert^2 + other\ linear\ least\ squares\ terms + \mathcal{I}(\... • 131 4 votes 2 answers 170 views ### What does "programming" mean in mathematics? In the past few years, I have came across some topics in Math and CS that have the word "programming" in them. For example, there are linear programming, quadratic programming and dynamic ... • 252 4 votes 1 answer 113 views ### Portfolio optimization I prepare Markowitz optimization model for 4 different local companies with Excel functions and Solver. And I get confusing result for me, maybe somebody will explain it. So, from historic information ... • 480 4 votes 2 answers 1k views ### Different behaviour of Newton's method for finding minimum of a function Given the following function of two variables$$f(x, y) = 2x^2 − 2xy + y^2 + 2x − 2y$$I wanted to use Newton's method to find a minimum of this function. I started from (x_1, y_1) = (0, 0) and ... • 761 4 votes 1 answer 1k views ### Solving an equality-constrained convex quadratic program There's this convex optimization problem which I got stuck after writing the Lagrange equation. I simply couldn't find a way to eliminate the Lagrange multiplier.$$\begin{array}{ll} \text{minimize} &...
• 143
I would like to solve the support vector regression problem. The formula for the optimization is the following: a_1^*, a_2^* = \max\sum_{i=1}^{n} (a_{1i}-a_{2i})y_{i} - eta\sum_{i=1}^{n}(a_{1i}+a_{...