# Tag Info

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

The Moore-Penrose pseudoinverse is a natural consequence from applying the singular value decomposition to the least squares problem. The SVD resolves the least squares problem into two components: (1)...
• 10.4k

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

To answer your questions directly: A loss function is a scoring function used to evaluate how well a given boundary separates the training data. Each loss function represents a different set of ...
• 17.6k
Accepted

### Minimum of the given expression

\begin{eqnarray*} (a-b)^2+(2-a-b)^2+(2a-3b)^2=6a^2-12ab+11b^2-4(a+b)+4 \\ =6\left(a-b-\frac{1}{3}\right)^2+5\left(b-\frac{4}{5}\right)^2+\color{red}{\frac{2}{15}}. \end{eqnarray*}
• 36.7k

• 19.6k
Accepted

Accepted

### Minimization of a convex quadratic form

You have a convex quadratic form to minimize. This can be written in the form: $\min f(x)=\frac{1}{2} x^{T}Ax - b^{T}x + c$ where $A$ is symmetric and positive semidefinite. The gradient of $f$ ...
• 10.7k
Accepted

### Question on bilinear programming

A bilinear problem is an extension of a linear problem, allowing in the objective an expression of the form $x^TQy$, where $x,y$ is a partition of all the problem variables. So you allow mixed ...
• 4,028
Accepted

### Does a convex quadratic program have a unique solution?

Let us define $f(x) = x^\top Q \, x$. In case that $Q$ is PD, it is easy to check that $f$ is strictly convex, i.e., $$f( \lambda \, x + (1-\lambda ) \, y) < \lambda \, f(x) + (1-\lambda) \, f(y)$$ ...
• 31.5k
Accepted

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

As Rahul has shown, both problems are equivalent from a mathematical point of view: the Constrained Linear Least Squares problem is a specific instance of the Quadratic Programming (QP) problem. There ...

### Converting from QP to SOCP

I'll assume $A$ is positive semidefinite. Let $A = L L^T$ be the Cholesky factorization of $A$. Your optimization problem can be reformulated as \begin{align} \operatorname{minimize}_{x,u,y} & \...
• 52.2k
Accepted

### The best performing (theoretical complexity-wise) algorithm to solve this quadratic program

Your problem corresponds to orthogonally projecting the point $\textbf{v} \in \mathbb R^n$ onto the unit simplex. The problem can be solved analytically in $\mathcal O(n)$ using Kiwiel's algorithm (e....
• 9,565
Accepted

### How to find Lagrange Multipliers in Quadratic Programming problem?

The third constraint is a consequence ( a sum) of the other two, throw it away, and be happy.
• 26k
Accepted

### Rewrite $\|AXBd -c \|^2$ as $\|Qx -c \|^2$ to solve it using standard solvers

Denoting by $\operatorname{vec}:\mathbb{R}^{m\times n} \rightarrow \mathbb{R}^{mn}$ the operator transforming an $m\times n$ matrix into a column vector of $mn$ elements by "stacking" the matrix ...
• 3,092

• 23.4k
Accepted

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

Use a linearly constrained linear least squares solver. For example: lsqlin in MATLAB https://www.mathworks.com/help/optim/ug/lsqlin.html lsei in R https://rdrr.io/rforge/limSolve/man/lsei.html The ...
• 4,516
Accepted

### What does "programming" mean in mathematics?

These optimization problems are called "programs" for historical reasons. The methods were developed in the 1940s, some time before there was a more standard usage of the term "...
• 24.6k
Accepted

### Maximizing $\mathbf{x}^T A \mathbf{x}$ subject to $| \mathbf{x} | \preceq \mathbf{1}$

Maximization of a convex quadratic over the hypercube is a classical intractable problem, and you will not be able to device an algorithm which, in the worst case, performs much better than simply ...
• 9,537
Accepted

$f(x)=-5$ when $x=(x_1, x_2, x_3,x_4, x_5,x_6,x_7)$ is one of the following 16 tuples, $$\begin{array}{rrrrrrr} &(55, &28, &11, &16, &8, &1, &0) \\ &(57, &28, &... • 13.4k 4 votes Accepted ### Is a sinc-distance matrix positive semidefinite? In the arXiv paper "Schoenberg matrices of radial positive definite functions and Riesz sequences in L^2(\mathbb{R}^n)" by L. Golinskii, M. Malamud and L. Oridoroga, Definition 1.1 states Let n ... • 54.4k 4 votes Accepted ### Why use two slack variables in the support vector regression formulation? I ran into the same question studying SVR, and even if this post is 2 years old maybe it can help others so here is an answer. The slack variables in SVR are defined as such: -> ξi+ is 0 if the ... 4 votes Accepted ### Analytical solution of quadratic programming when H is not p.d.? We consider the function$$ f \colon \def\R{\mathbf R}\R^n \to \R, \quad x \mapsto \frac 12 x^tHx + c^t x $$for H\in \def\M{\mathrm{Mat}}\M_n(\R), c \in \R^n. Taking derivatives gives \begin{... • 84.4k 4 votes Accepted ### Sparse \ell_0 solution to constrained quadratic program As for A, I think the statement is trivial. Given the answer to A, the answer to B is found with the KKT conditions for the problem. Consider$$\min_x \{ \sum a_i x_i^2 : \sum x_i \geq 1, x_i \...
• 19.8k
Using Lagrange multipliers, $x$ is a solution of your problem if there is $\mu$ such that $$2Cx + \mu e =0, \ x^Te =1.$$ Solving the first equation for $x$ gives $$x = -\frac\mu2 C^{-1}e.$$ ...