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

Gauss-Newton convergence for constant Hessian

If I use Gauss-Newton to solve a least square optimization problem and $\mathbf{J}^H\mathbf{J}$ is constant does it imply that I will reach the solution in one iteration?
trienko
  • 407
1
vote
0 answers

What's the difference between this proximal method and subgradient projection?

http://stanford.edu/~boyd/papers/pdf/prox_algs.pdf In the link above it is proposed that the nonsmooth separable resource allocation problem $$\min \sum f_i(x_i) \ \ \text{s.t.} \ \ \textbf{1}^Tx = b, x_i \geq 0$$ can be solved efficiently by the…
Benjamin Lindqvist
  • 3,112
1
vote
1 answer

what does separable convex program mean?

In literature,a separable program is formulated like this: $$\min_{x_{1},...x_{n}}\sum_{i=1}^{n}f_{i}(x_{i})$$ where $f_{i}$ is a closed proper convex function. My question is what does 'closed' mean? and is the following problem…
yang
  • 957
1
vote
0 answers

Is there any software to solve this large scale convex optimization problem?

I want to solve the following large scale convex problem: $min\ \ ||A$u-b$||_2^{2}+ ||$U$_{(1)}||_*+||$U$_{(2)}||_*+||$U$_{(3)}||_*$ where U is a three order tensor, U$_{(i)}$ is a matrix whose column are the mode-$i$ fibers of U(i=1,2,3),u is…
yang
  • 957
1
vote
1 answer

Is every optimization problem with a piece-wise affine objective function the dual of some differentiable problem?

It is well known that a problem can have a $C^1$ objective function and a convex feasible set, while the dual problem can be piece-wise $C^1$ only. So I'm wondering - if you have a piece-wise affine, concave objective function that you want to…
Benjamin Lindqvist
  • 3,112
1
vote
1 answer

For a non-convex function f, how to find a function g such that $g\circ f$ is strictly convex?

The following function $f(x)={1\over (1+e^{-x})}$ is non-convex but $\ln(f(x))$ is convex. Given a non-convex function $f$, can we find a function $g$ such that $g\circ f$ is strictly convex? If yes, how to find such a g? If not, what property…
Tianqi Tang
  • 19
1
vote
0 answers

Transform a nonconvex constraint into a convex one

I am solving an optimization problem and I need to formulate it as a convex optimization problem. Is there any way to write the constraint $$ 1 - e^{z} - \frac{e^{-r}}{1+r} \leq 0 $$ as a convex constraint?
alex14204
  • 49
1
vote
0 answers

Compressed sensing: converse of a theorem

Theorem: Suppose that the signal length $N$ is a prime integer. Let $\Omega$ be a subset of $\{ 0, \ldots , N-1 \}$ and let $f$ be a vector supported on $T$ such that $|T| < \dfrac{1}{2}|\Omega|$ then $f$ can be constructed uniquely from the set…
Ronnie
  • 11
1
vote
1 answer

Convexity preservation and global optimality

This is a question I've had a tough time getting a good answer to. Consider the problem to minimize $f(x)$. Assume $f$ is differentiable and nice in every way, but we do not know if $f$ is convex. A common approach is to instead minimize $g(y)$…
Benjamin Lindqvist
  • 3,112
1
vote
1 answer

Efficient solution for a quadratic + norm objective.

I want to minimize an objective function of the following form: $$ \begin{split} \text{Minimize} \quad & x^T D_x x + y^T D_y y + z^T D_z z + q_x^T x + q_y^T y + q_z^T z + \lambda \cdot…
Alex Shtoff
  • 12
1
vote
1 answer

Huber penalty function in linear programming form

I am trying to solve problem 6.3(b) of Boyd & Vandenberghe's Convex Optimization: Express the following minimization as a QP, LP, SOCP or SDP $$ \min_{\mathbf{x}}\sum\limits_{i=0}^K \phi(\mathbf{a}_i^T \mathbf{x}-\mathbf{b})$$ where $$\phi(u) =…
Karthik Upadhya
  • 734
  • 7
  • 15
0
votes
1 answer

An optimal solution that is also smooth

I am given a vector x. My objective is to find an optimal y (minimize $||y-x||_2^2$). With the constraint $y(c) = a$ (a and c are known scalars). $$\text{minimize}_y ||y-x||_2^2 \\ \text{subject to}\ \ y(c) = a $$ Further, I am confused about how to…
mkuse
  • 195
0
votes
0 answers

Solving with Newton's Optimization Method

I am aware of how to implement the Newton's method for minimization for a smooth analytic function. I am also aware of log-barrier for constraint minimization. Now, I am looking to solve the the minimization of L-2 norm with L-1 regularization.…
mkuse
  • 195
0
votes
0 answers

How to show this empirical risk minimization problem has a specific optimum?

I'm trying to show for general regularized empirical risk minimization problem that the minimizing $w$ for $$ \frac{1}{n}\sum_{i=1}^n \textrm{loss}(w^T y_i,x_i) + \mu \lVert{w\rVert}^2, $$ where the loss function is convex in the first argument and…
Kashif
  • 1,497
0
votes
1 answer

Complexity of convex optimization problem with interior-point

Assume I have a matrix $Q \in \mathbb{R}^{n \times n}$ which is positiv definite and symmetric, and I want to minimize $$ \frac{1}{2} x^T Q x + x^T f $$ on a non-empty convex set $x\in D=\{ v \in \mathbb{R}^n \mid Av\leq 0,\, Bv = c\} $. Such a…
Adam
  • 3,679
1 2 3
…
24 25