Skip to main content
36 votes

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)...
dantopa's user avatar
  • 10.4k
20 votes

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 ...
user326210's user avatar
  • 17.6k
13 votes
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*}
Donald Splutterwit's user avatar
11 votes

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

If you initialize gradient descent with a point $x_0$ which is a minimizer of the objective function but not a least norm minimizer, then the gradient descent iteration will have $x_k = x_0$ for all $...
littleO's user avatar
  • 52.2k
10 votes
Accepted

Unconstrained quadratic programming problem with positive semidefinite matrix

As I'm sure you know, the solutions are all vectors $x$ satisfying the optimality conditions: $$\nabla f(x) = 0 \quad\Longleftrightarrow\quad Ax + b = 0$$ It's important to note that if $b\not\in\...
Michael Grant's user avatar
10 votes
Accepted

Converting from QP to SOCP

This only works if $A$ is positive definite. In this case, just drop the quadratic part and obtain $$\begin{array}{rcl} \min\limits_{x,y} && y + a^Tx\\ st && Bx\leq b\\ && x^...
wyer33's user avatar
  • 2,572
10 votes

Projection of a point onto a convex polyhedra

As mentioned in other answers and comments, the problem you need to solve is an inequality constrained, strongly convex QP: $$ \begin{aligned} \mathrm{minimize}\ &\tfrac{1}{2}\|x\|^2_2 \\ \...
Lorenzo Stella's user avatar
8 votes
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$ ...
Brian Borchers's user avatar
8 votes
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 ...
Michal Adamaszek's user avatar
7 votes
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)$$ ...
gerw's user avatar
  • 31.5k
5 votes
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 ...
Michiel Stock's user avatar
5 votes

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} & \...
littleO's user avatar
  • 52.2k
5 votes
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....
dohmatob's user avatar
  • 9,565
5 votes
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.
Igor Rivin's user avatar
5 votes
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 ...
Stelios's user avatar
  • 3,092
5 votes

Minimum of the given expression

Let $a=\frac{17}{15}$ and $b=\frac{4}{5}$. Hence, we get a value $\frac{2}{15}$. Thus, it remains to prove that $$(a-b)^2 + (2-a-b)^2 + (2a-3b)^2\geq\frac{2}{15}$$ or $$10(3a-3b-1)^2+3(5b-4)^2\geq0$...
Michael Rozenberg's user avatar
5 votes
Accepted

Linear Matrix Least Squares with Linear Equality Constraint - Minimize $ {\left\| A - B \right\|}_{F}^{2} $ Subject to $ B x = v $

The beginning looks fine. However, note that you need one Lagrange multiplier per constraint. Thus you need a vector $\lambda$. The function to minimize is then $$\operatorname{tr}(A^T-B^T)(A-B) - \...
Fabian's user avatar
  • 23.4k
5 votes
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 ...
Mark L. Stone's user avatar
5 votes
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 "...
Théophile's user avatar
  • 24.6k
5 votes
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 ...
Johan Löfberg's user avatar
5 votes
Accepted

Calculating the maximum value of a quadratic polynomial on several variables with some restrictions

$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, &...
Apass.Jack's user avatar
  • 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 ...
JimmyK4542's user avatar
  • 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 ...
axelle pochet's user avatar
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{...
martini's user avatar
  • 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 \...
LinAlg's user avatar
  • 19.8k
4 votes
Accepted

Minimize pure quadratic subject to linear equality constraint

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. $$ ...
daw's user avatar
  • 49.7k

Only top scored, non community-wiki answers of a minimum length are eligible