I'm studying convex optimization using Convex Optimization (Boyd & Vandenberghe) and had a question from an example used in Chapter 4.2: Convex Optimization.

The specific example is as follows:

$\text{minimize}\quad \ f_0(x) = x_1^2 + x_2^2$

$\text{subject to}\quad f_1(x) = \frac{x_1}{1+x_2^2} \le 0$

$\qquad\qquad\quad\ h_1(x) = (x_1 + x_2)^2 = 0$

The textbook states that this problem is not a convex optimization problem because the equality constraint $h_1(x)$ is not affine.

I'm aware that affine functions are linear functions composed with a translation, but when I plotted out the graph for $h_1(x)$ I get a line or plane, which are both affine sets. This led to my confusion as to why the function isn't affine if it's graph is an affine set.

Why isn't it an affine function? Is my understanding of what an affine function is itself wrong?

  • $\begingroup$ Take $x_2 = 0$, then $h_1$ becomes $x_1^2 = 0 \Rightarrow |x_1| = 0$. Can you see now how this is not affine? $\endgroup$ – Wood Jun 11 '19 at 3:48
  • $\begingroup$ It's actually still a bit confusing for me :( If $|x_1| = 0$ then doesn't that mean $h_1(x)$ is a point because $(x_1, x_2) = (0, 0)$? $\endgroup$ – Seankala Jun 11 '19 at 3:54
  • $\begingroup$ The graph of $h_{1}(x)$ is not an affine set! $\endgroup$ – Brian Borchers Jun 11 '19 at 4:46

The function $h_{1}(x)$ is not an affine function because it can't be written in the form $h_{1}(x)=a^{T}x+b$. Or, if you let $x=(1, 1)$ and $y=(2,2)$, you'll see that $(h_{1}(x)+h_{1}(y))/2=10$, while $h_{1}((x+y)/2)=9$. It's true that these points don't satisfy $h_{1}(x)=0$ and $h_{1}(y)=0$, but that doesn't make any difference in whether $h_{1}()$ is itself an affine function.

The definition of "convex optimization problem" being used here requires that the functions $h_{i}(x)$ in the constraints $h_{i}(x)=0$ be affine. That's not the same thing as requiring that the set of $x$ such that $h_{1}(x)=0$ is an affine set.

Under this definition of a convex optimization problem, it's possible (as this example illustrates) that the feasible region of an optimization problem is convex even though the problem is not a convex optimization problem under the definition.

Why use this definition of "convex optimization problem"? One reason is that under this definition we can assume that the $g_{i}(x)$ functions are convex and the $h_{i}(x)$ functions are affine. You'll see these properties used from time to time in proofs later in the book.

  • $\begingroup$ Hello, thanks for the answer. You're right, in the next page the author explains that the feasible set is indeed convex despite the problem itself not being a convex optimization problem. But my question is, why isn't $h_1(x)$ an affine function? Is it simply because it's not a translated linear function? $\endgroup$ – Seankala Jun 11 '19 at 4:10

$$h_1 (\mathrm x) = \left( 1_2^\top \mathrm x \right)^2 = \mathrm x^\top 1_2 1_2^\top \mathrm x$$

is a positive semidefinite quadratic form that vanishes at the line defined by $1_2^\top \mathrm x = 0$. However, function $h_1$ is quadratic and, thus, non-affine. It would be wiser to use the linear equality constraint $1_2^\top \mathrm x = 0$ instead, which would make the optimization problem convex according to the definition.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.