What happens to $\|Ax -b\|^2$ when $x$ is subjected to constraints?

94 Views Asked by At

How do we check if the function still remains convex?

Do we calculate the Hessian under the constraints?

Suppose I put up a constraint on $x$ to have $|x_i| < 1$ for $i \in \{1,2,\dots,n\}$. In the book, it says that now it becomes a quadratic programming problem with an affine constraint. What does it mean in simple terms and how do I approach solving this?

1

There are 1 best solutions below

4
On

I think that part of the confusion here is that the term "convex" is used to describe three different categories of things: convex functions, convex sets or constraints, and convex optimization problems. There are close relationships between these three concepts, so the multiple use of the term "convex" is justified. Nevertheless, it sometimes causes confusion.

A convex function is a function $f(x)$ satisfying $$f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda) f(y) \quad\forall x,y\in\mathop{\textrm{dom}}(f).$$

A convex set is a set $X$ satisfying $$\lambda x + (1-\lambda)y \in X \quad \forall x,y\in X.$$ Hopefully the similarity to the definition of a convex function is obvious. In fact, a function $f$ is convex if and only if its epigraph $\mathop{\textrm{epi}} f \triangleq \{(x,y)\,|\,f(x)\leq y\}$ is a convex set.

A convex constraint is an expression, usually an equation or inequality, that describes a convex set. For instance, each of your constraints $|x_i|\leq 1$ is a convex constraint. The intersection of convex sets is always convex; likewise, the combination of your $n$ constraints describes a convex set---a hypercube, in fact.

Finally, a convex optimization problem involves minimizing a convex function subject to zero or more convex constraints. (There are variations, but for the purposes of this discussion this will suffice.)

So to answer your question: the function did not change just because you now have some constraints you would like to apply. Rather, you have constructed a convex optimization problem that involves minimizing that function subject to $n$ convex constraints. This problem is more difficult to solve in practice than if the constraints weren't there. But your text is correct; this is a quadratic programming problem, and there are a wealth of resources (text and software) that describe these problems and how to solve them.