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

How to prove the dual of a norm

I am studying convex optimization and saw the following. How do I prove it ? I would use what i learnt - lagrangian multipliers to formulate the dual but I don't know how to do it. There are no constraints on the original function. And every website…
Kong
  • 884
0
votes
1 answer

How to show that a function is convex?

Let $f:\mathbb R^n \rightarrow [-\infty,+\infty]$. show that the perspectie of $f$ defined via $$ g(x,y)=yf(x/y),\qquad x\in \mathbb R^n,y\in \mathbb R_+ $$ is convex iff $f(x)$ is a convex function. $$\nabla g(x,y)=\left(\frac{\partial yf(x/y)…
jester
  • 324
0
votes
0 answers

Dual of a differentiable $\ell_1$-norm approximation

I'm considering Problem 6.4 of Boyd's Convex Optimization. In the problem, we're using $\phi(u) = (u^2 + \epsilon)^{1/2}$ to solve the problem $$ \min \sum_{i=1}^m \phi(a_i^Tx-b_i) $$ in place of the true $\ell_1$ minimization problem $\inf_{x \in…
user83387
0
votes
1 answer

Numerically solving linear equation and optimization

I have to solve for $x$ in the linear equation $Ax=B$. However, $A$ has singular values that are close to zero (very small). So direct inversion is not a good idea. I wanted to solve for $ x$ using one of the numerical equation solvers? Does any one…
SPB
  • 51
0
votes
1 answer

Solving minimization problem $L_2$ IRLS

In the article ''' Chartrand, Rick, and Wotao Yin. "Iteratively reweighted algorithms for compressive sensing." Acoustics, speech and signal processing, 2008. ICASSP 2008. IEEE international conference on. IEEE, 2008. ''' It is given that one…
seeker
  • 17
0
votes
0 answers

Is this Lagrangian function correct?

I am trying to formulate the Lagrangian function for the following problem and constraints: $$f(x,y,z)= \sum_{n=1}^N x_{nk}\log(1+y_{nk})+\sum_{m=1}^Mz_{mk}C,$$ and maximize $\sum_{k=1}^Kf(x,y,z)$ subject to$$f_k(x,y,z)\geq b_k,\forall k,\…
Fawad
  • 23
0
votes
2 answers

Where do these problems fall in the "convex problem class" hierarchy?

I've been going through some notes on convex optimization which partition the space of convex optimization problems into: Linear programs Quadratic programs Semi-definite programs Conic programs with each tier containing the problems in the…
ted
  • 1,725
0
votes
1 answer

what's the meaning for the upper tilt symbol in convex optimization for?

I am kind of confused by the h with upper tilt symbol here: property Thank you!
XJY95
  • 19
0
votes
1 answer

How to understand the convex of the multiplication of PSDmatrix and its transpose?

$$C = conv\{xx^T | x\succeq0\}$$ As far as I know, $x\succeq0$ means x is a symmetric, positive semidefinite matrix, therefore the $xx^T$ here is also symmetric and positive semidefinite. As the "Positive Semedefinite Cone" is defined…
XJY95
  • 19
0
votes
1 answer

Is negative quadratic function quasiconvex?

I read in book (Convex Optimization, boyd) that quasiconvex (or unimodal) if its domain and all its sublevel sets $S_α = \{x ∈ dom f | f(x) ≤ α\}$, for $α ∈ R$, are convex. And if and only if $f(x)$ is non-decreasing or non-increasing, $f(x)$ is…
Newb
  • 3
0
votes
1 answer

Convexity of a function 3

I have following function: \begin{equation} \lambda(\xi;\mu) = \mu^{T}\left\{M(\xi) - M(\xi)JM(\xi)\right\}\mu, \end{equation} where $M(\xi) ={\rm{diag}}(\xi_{1},\ldots,\xi_{K})$, and $ J = \mathbf{1}\mathbf{1}^{T}$, where $\mathbf{1}$ is a vector…
Satya Prakash
  • 367
0
votes
0 answers

Definition of first-order information

I'm working on an article about optimization and it has the expression "first order information". I can't find the meaning of that... could you please send for me a definition of it? It's emergency:)
salma.shah
  • 1
  • 1
0
votes
0 answers

Dual optimum not attained

I am solving problem 5.22 b) from Boyd and Vanderberghe "Convex Optimization". The problem is that given the optimization problem $$\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & x \\ & \text{subject to} & & x^2 \leq…
user110320
  • 1,083
0
votes
1 answer

Comparative Static on Min of Sum of Two Convex Functions

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
0
votes
0 answers

Optimize a convex problem with separable objective function

Consider the following convex problem. $\min{\mathbf{x}_1,\cdots,\mathbf{x}_N\in\mathbb{R}^K}\sum_{n=1}^Na_n f(\mathbf{x}_n)\\ s.t.\quad \sum_{n=1}^N\mathbf{x}_n=\mathbf{c},\\ 0\le \mathbf{x}_n \le 1$ where $f(\mathbf{x}_n)$ is convex w.r.t.…
Dave
  • 576
1 2 3
…
24 25