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
1
vote
0 answers

How to solve a set of $L_1$ quadratic problems with a simple constraint efficiently?

I have a set of problem each in the following form except with different $i$ in the constraint: $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ $$s.t. \quad x_i = a$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive…
user85361
  • 845
1
vote
1 answer

how can I proof the GLOBAL optimality of a problem where the feasible region is disjoint?

I want to minimize the following function. It has two variable, $x$ and $y$ are real. I want proof the global optimality. But the feasible region of the variables are disjoint. My question is, how can I proof the GLOBAL optimality of the…
fayzur
  • 11
1
vote
1 answer

Clarification on computation complex optimization

This might be a question with a very simple solution but I really don't see where this comes from. In the book on Convex optimization by Boyd and Vandenberghe in the section of examples on duality, the author compute a norm approximation problem.…
user110320
  • 1,083
1
vote
1 answer

Rewriting a set with two parameters as a polyhedron

According to "Convex Optimization" by Boyd and Vandenberghe, a polyhedron is defined as the solution set to a finite number of linear equalities and inequalities: $$P = \{x \: | \: a_j^T \leq b_j, j = 1, \ldots, m, c_j^T x = d_j, j = 1, \ldots,…
Aleksey Bilogur
  • 245
  • 3
  • 9
1
vote
1 answer

Minimum of sum of convex functions: single dimension

Let $g_1(x)$ and $g_2(x)$ be convex functions from $\mathbb{R}\rightarrow \mathbb{R}$, and assume that the global minimum of each $g_i$, denoted $x_i^*$, is unique. with $x_1^*
Jong
  • 236
1
vote
1 answer

Supporting hyperplane theorem and halfspaces

Does the supporting hyperplane theorem imply that closure of any convex set can be expressed as intersection of halfspaces(possibly infinitely many halfspaces). The statement of supporting hyperplane theorem is: For any nonempty convex set $C$, and…
Curious
  • 1,278
1
vote
1 answer

Frontier Equation - Fit a polynomial to the top of a data set

How can I fit a polynomial to an empirical data set such that it fits the "top" of the data -- i.e. for every value of x, the output of function is greater than the largest y at that x. But at the same time it minimizes this such that it hugs the…
j_code_3
  • 11
1
vote
0 answers

Is this a valid proof for showing that the local minimum of a convex function is the global minimum?

I am interested in learning more about optimization problems. I came accross a theorem stating that a local minimum of a convex function is the global minimum of that function. I derived the following proof, but I am not sure whether it is correct…
user3536409
  • 21
1
vote
1 answer

optimization with ellipsoidal constraints

I'm reading a paper recently and encounter a optimization equation which I can't understand: $\max_{x\in\{x|x^TPx\le1\}} c^Tx =(cP^{-1}c^T)^{1/2} $ where $P\succ0$ Anybody knows why the result is $(cP^{-1}c^T)^{1/2} $?
Lantao Xie
  • 11
1
vote
2 answers

Counterexample to show that the set of global minima of a function $f$ is a strict subset of the set of minima of the convex envelope of $f$

Let $f_C$ be the convex envelope of $f$ on a non-empty convex set $C \subset \mathbb{R}^n$ I need to show that $\{ x^∗ \in C : f(x^∗) \leq f(x), \forall x \in C \} \subset \{x^∗ \in C : f_C(x^∗) \leq f_C(x), \forall x \in C \}.$ Right now, I can…
Elements
  • 2,638
1
vote
0 answers

convex optimization: simple conjugate function example

$$ f(x) = \begin{cases} 0 &\text{ if } |u| \le 1 \\ |u|-1 &\text{ if } |u| \gt 1 \end{cases} $$ $$ g(x) = \begin{cases} u^2 &\text{ if } |u| \leqslant 1 \\ …
fordicus
  • 271
1
vote
0 answers

optimization of non-centrality parameter

minimize $\sum_{i=1}^{k}\alpha_{i}^{2}$ subject to $\sum_{i=1}^{k}\alpha_{i}=0$ and $\max_{1\leq i
Satya Prakash
  • 367
1
vote
2 answers

Bounding the residual of a norm approximation problem

Given a norm approximation problem $$\text{minimize}\ \ \lVert Ax-b\rVert$$ and its optimal solution vector $x^*$, it is quite easy to show that $0\leq\lVert Ax^*-b\rVert\leq\lVert b\rVert$. Is it also true that $\lVert Ax^*-b\rVert<\lVert b\rVert$?
Filippo Bistaffa
  • 197
  • 8
1
vote
1 answer

Missing factor of 2 in Newton's decrement

Page 486 of Boyd's Convex Optimization book defines Newton's decrement as $$\lambda(x)=(\nabla f(x)' \nabla^2 f(x)^{-1}\nabla f(x))^{\frac{1}{2}}$$ and then says that squaring this quantity and dividing by 2 gives estimate of how far off from the…
Yaroslav Bulatov
  • 5,327
1
vote
1 answer

boundary and optimization over convex sets

Suppose we are maximizing a concave objective function $f_0$ over a convex set $C$. Must the boundary of $C$ contain a point $x_b^*$ which maximizes our objective function? That is, if $S = \{x: x = \text{argmax} f_0(x), \text{ } x \text{…
jjjjjj
  • 2,671
1 2 3
…
24 25