Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function. Linear Programming is a special case. Convex Optimization problems as a class are easier to solve numerically than general mathematical optimization problems.

The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:

  • Least squares
  • Linear programming
  • Convex quadratic minimization with linear constraints
  • Quadratic minimization with convex quadratic constraints
  • Conic optimization
  • Geometric programming
  • Second order cone programming
  • Semidefinite programming
  • Entropy maximization with appropriate constraints
7419 questions
0
votes
0 answers

'Meaning' and interpretation of convex conjugate

In the field of convex optimization, and in particular on prof. Stephen Boyd's lecture slides, the conjugate $f^*$ of a function $f$ is defined to be $$ f^*(y) = \sup_{x \in domf} (y^Tx - f(x))$$ I'm just trying to better understand this definition…
James Arten
  • 1,953
  • 1
  • 8
  • 20
0
votes
1 answer

Max of a concave function

Given a concave function $f(x)$ over a convex set $S$, so $f(a)+f(b) \leq 2 \times f (\frac{a+b}{2})$. Here, $a$ and $b$ lies in the same convex set $S$. I know that the maximum value of $f(a)+f(b)$ is possible when $a=b$. But I don't know how to…
maths123456
  • 13
0
votes
0 answers

Convex Sets and Conic Sets and Functions

It appears as though all convex sets are conic. But is every conic set convex? I can't seem to think of an edge case where a conic set isn't convex. Moreover, from the definition of a cone and conic combination: From the definition of a cone: Let…
David
  • 117
0
votes
0 answers

Lagrangian (Convex Optimization)

In our lectures notes, we had: Definition: The function $$L: X \times Y^{*} \rightarrow \mathbb{R}_{\infty},$$ $$-L(x, p^{*}) = \sup_{p\in Y}\left\{ \langle p \vert x \rangle - \Phi(x, p)\right\}$$ is called the Lagrangian of problem…
Hermi
  • 692
0
votes
0 answers

Boyd & Vandenberghe, 9.2 — how was this derived?

I'm studying convex optimization and saw the solution to the question. However I can't understand how they ended up in the last equation which I've highlighted in yellow. I have tried putting $x_1$ and $x_2$ in but can't get the last one. Could…
Cherry Hill St.
  • 21
0
votes
0 answers

Equivalence of two optimization objectives

Consider $$(\hat\beta_0, \hat\beta) = \arg\min_{\beta_0,\beta}\|y-\beta_0 1 - X\beta\|^2$$ and $$(\tilde\beta_0, \tilde\beta) =\arg\min_{\beta_0,\beta} = \left\|y- \left( \beta_0 - \frac{1^T X \beta}{n}\right) 1 - X\beta \right\|^2 $$ Note that $1,…
user5965026
  • 677
0
votes
1 answer

in the derivation of support vector classifier

I was studying the Stephen Boyd's textbook on convex optimization and have a question on the support vector classifier. The book says the following: In linear discrimination, we seek an affine function $f(x) = a^T x - b$ that classifiers the…
DSKim
  • 1,117
  • 4
  • 14
  • 18
0
votes
1 answer

maximum of multivariable convex function

There is a statement that says that every real convex function of one variable on compact convex set attains maximum on its boundary. Is there analogous result for real convex function of more then one variable?
Madara Uchiha
  • 678
0
votes
1 answer

Strict convexity condition

I have an if and only if, and I am having trouble with one of the arrows! Here it is: Let $C \subset \mathbb{R}^n$ such that the interior of $C$, $\operatorname{int} C \neq \emptyset$. $C$ is strictly convex (i.e. $\forall x,y \in C$ then $\lambda x…
Nicolo Canali De Rossi
  • 75
0
votes
1 answer

proving the superlevel set is convex (quasiconcave)

I want to show that $f(x_1, x_2) = x_1x_2$ is quasiconcave. Let $$S_\alpha = \{x_1, x_2 \in \mathbf{R}_{++}\; | \; f(x_1, x_2) = x_1x_2 \ge \alpha \}$$ and $(a_1, b_1), (a_2, b_2) \in S_\alpha$. So $a_1b_1 \ge \alpha$ and $a_2b_2 \ge \alpha$.…
MoneyBall
  • 877
0
votes
2 answers

A convex set plus a constant is still convex

Let $C ⊂ R^n$ be a nonempty convex set and let $b ∈ R^n.$ Then the set given by $b + C = {x + b : x ∈ C}$is a convex set. How do we prove this statement?
codemachine98
  • 165
0
votes
1 answer

developed (simplified) form of a Euclidean projection onto a convex set

$\|\cdot\|$ is Euclidean norm. I minimize a convex and differentiable function $f : \mathbb{R}^d \rightarrow \mathbb{R}$ with constraint. By applying the projected gradient method I get this : \begin{equation} x_{k+1} = \arg\min_{y: \| y - x_1…
K.J Fogang Fokoa
  • 117
  • 4
0
votes
1 answer

How to determine which function generates superlevel, sublevel, or level set?

If I am provided with function such as this $$f(x) =|x_1|+|x_2|,$$ how do I know what kind of level set it generates? Please, generalize the result. Similarly, for $$f(x) =−(x_1−2)^2+|x_2|+ 1.$$ I don't know how to determine which function…
Jimjamlorde
  • 59
0
votes
1 answer

Why is $X = \{x:3x_{1}^{2}-2x_{2}^{2}\geq1, x_{1},x_{2}\geq 0\}$ a convex set

The question is to determine if the set $$X = \{x:3x_{1}^{2}-2x_{2}^{2}\geq1, x_{1},x_{2}\geq 0\}$$ is convex. I have a theorem which states that if $g(x)$ is a convex function then $g(x)\leq b$ also determines a convex function. This makes me want…
user649348
0
votes
0 answers

An example of a strongly convex function whose gradient is Lipschitz and satisfies $0< \mu < L<1$

Can someone please help me give like two examples of a strongly convex function whose gradient is Lipschitz with constant $L$ whose strong convexity parameter is denoted by $\mu$ and satisfies the following condition: $0<\mu
Tony....
  • 35
  • 5
1 2 3
…
24 25