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
1 answer

Does positive second derivative means the function is strictly convex?

I know that non negative second derivative means the function is convex but does positive second derivative means the function is strictly convex ? I could not find references to this and even my professor said he need to check and was not sure.…
Tomer
  • 434
0
votes
1 answer

Why does this convex combination work?

Take a concave function e.g. the quadratic below (picture attached). Why does the chord between two values $f(x₁)$ & $f(x₂)$ give us the linear relationship between the convex combination of the two points $x(λ) = (1-λ)x₁ + (λ)x₂$, and the convex…
CormJack
  • 422
0
votes
0 answers

Showing that a minimization problem is unbounded

Let $s^*=\mathrm{inf}\Bigl\lbrace{\frac{1}{2}x^TMx+v^Tx+w:x \in \mathbb{R}^n\Bigr\rbrace}$ be a minimization problem with $M \in \mathbb{R}^{n \times n}$ symmetric, $v \in \mathbb{R}^n$ and $w \in \mathbb{R}$. How to show: If $M$ is positive…
Tartulop
  • 543
  • 2
  • 8
0
votes
0 answers

Equivalent definitions of strongly convex functions

i am looking for a short proof for a theorem of a book: $f\in S^2_\mu(\mathbb{R}^n)$ means that f is strongly convex with parameter $\mu$ i.e 2.1.17 you can find in theorem 2.1.11 says i just have to apply 2.1.17 but i don't know how to do…
Felix Wilde
  • 43
0
votes
1 answer

how to prove the following question about extreme points. Can I proof by contradiction?

let S={x:Ax$\le$b} and $x_o$ satisfies A$x_0$<0. Show that $x_0$ cannot be an extreme point of S. The question is posted by the professor when we were learning about the chapter 2 of NONLINEAR PROGRAMMING Theory and Algorithms
DAN
  • 23
0
votes
1 answer

Why must all of the sublevel sets of a real, continuous function in Rn, where ()→ +∞ as ‖‖→+∞, be compact?

I was reviewing the answer to this problem here and am trying to understand why condition 3 holds. That is: why does a real, continuous function in $\mathbb{R}^n $, where ()→ +∞ as ‖‖→+∞, have compact sublevel sets? I can picture sublevel sets in a…
Math927
  • 1
0
votes
0 answers

True or false: convex function

True or false: if $f: \mathbb R^n \rightarrow \mathbb R$ is a convex function, $y \in \mathbb R^n$ is such that $f(y)=\min_x f(x)$, and $z \in \mathbb R^n$ is such that $\nabla f(z)=0$, then $y=z$. This was a question on my exam, and i answered it…
Narti
  • 23
0
votes
0 answers

is LICQ necessary for strong duality?

I know that if an arbitrary constraint qualification holds in our convex problem, then strong duality holds. However, does every convex problem which strong duality holds for that should satisfy any CQ? especially LICQ? if no, please provide a…
Phillip A. Hendrick
  • 9
0
votes
0 answers

linear programming and the number of equality constraints

I am reading a paper on solving a problem using LP methods, it says "The linear problem has $n$ variables and $m$ constraints. From linear programming theory, we know that there is an optimal solution at which the number of constraints having…
Jayboy
  • 447
0
votes
1 answer

Prove feasible set is convex iff constraints are concave.

I am able to prove concave constraints imply convex feasible set. But not other way round. Is other way round true? Given: Feasible set S={$x:g_i(x)\ge 0 \forall i$} is convex. Show that the functions $g_i(x)$ is concave $\forall i$. Take x, y in S.…
Bully Maguire
  • 153
  • 8
0
votes
1 answer

Visualizing solution of optimization problem

So, we have the problem for $n=2$: minimize $c^Tx$ subject to $x\geq 0$ and $x_1+x_2=1$ and we are asked to visualize the solution (optimal x) for $c=\begin{bmatrix} 1 \\ 1\end{bmatrix}$. I know that, generally, we have to plot some level sets of…
TrapTengu
  • 1
0
votes
1 answer

Is the value function convex wrt a parameter if linear in that parameter and not in constraint?

For a convex optimization problem with equality constraints: Max $f(\boldsymbol{x},a)$ subject to $g(\boldsymbol{x})=0$. $a$ is a parameter and the function $f(\boldsymbol{x},a)$ is convex in $x_i$. Note the parameter $a$ is not in the…
Ashley
  • 1
  • 1
0
votes
0 answers

Convex set as a set of numbers only?

Can a set of numbers (not tuples) be called a convex set? I have read this article: on the medium.com website where at the beginning is written an underlined text, saying that "where the domain of $f$ is a convex set" ("convex set" there is…
Jan
  • 1
0
votes
2 answers

why polyhedron was defined by linear equalities and inequalities?

I am learning convex optimization, and confused by the definition of polyhedron. it's easy understanding the polyhedron is defined as the solution of a finite number of linear inequalities. But why there is also linear equalities in the definition…
LucasYang
  • 5
0
votes
1 answer

why $\sum_{i=1}^{n} p_{i} = 1$ defines a hyperplane?

I am doing exercise 2.15 of "convex optimization". While the solution confused me a lot. as indicated by the solution: $\sum_{i=1}^{n} p_i =1$ defines a hyperplane. while it's different from the dinition of hyperplane in page 27, 2.2.1 of the…
LucasYang
  • 5
1 2 3
…
24 25