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

Find the Nearest Point of $ y $ from a Probability Simplex.

I need to compute the nearest point of $x$ from a probability simplex. Formally, I want to ask if there is a close form for the solution to the following optimization problem: for $y\in \mathbb{R}^k$, $$\min\limits_{x} \|x-y\|^2_2 $$ $$s.t. \…
Yong Ren
  • 51
2
votes
2 answers

Affine hull example

In the textbook "Convex Optimization", S. Boyd says that the affine hull of a set $C\subseteq \mathbb{R}^{^{n}}$ is the smallest affine set that contains C. Moreover, the Ex. 2.2 shows the set $ C=\left \{ x\in \mathbb{R}^{3} |-1\leq x_{1},x_{2}\leq…
Hoping_Blessing
  • 417
2
votes
2 answers

Convex function on nonconvex set and global minimum

Can someone give an example of a convex function $f$ on a path-connected compact nonconvex set where some point $c$ is a local minimum with $\nabla f(c)=0$ but not a global minimum. Thus showing that the set being not convex makes finding global…
user782220
  • 3,195
2
votes
1 answer

Augmented Lagrangian with multiple constraints

I would like to minimise a function, with multiple constraints: $$ \frac{1}{2} \|y-Ax\|_2^2 + \beta \|z\|_1 $$ subject to $$ Bx = 0 $$ and $$ x - z = 0 $$ In my case $(B+I)$ is not a valid matrix. Do I just form the augmented Lagrangian as: $$…
Tom Kealy
  • 282
2
votes
1 answer

Hessian Related convex optimization question

My precise question is from an exercise; Let $f : \mathbb{R}^2 → \mathbb{R}$ be a twice differentiable function. Prove that there exists a $λ ∈ R$ such that $g : \mathbb{R}^2 → \mathbb{R}$ defined as $g(x) := f (x) + (λ/2)||x||^2$ is convex. Hint:…
TonkatsuYum
  • 21
2
votes
0 answers

proving that the ewma is convex

Hi: I know it's true but I don't know how to prove that exponentially weighted moving average when view ed as a function of $\lambda$, is strictly convex. The exponentially weighted moving average for a time series X_t is defined as $(1-\lambda)…
mark leeds
  • 1,514
1
vote
1 answer

Difference between tangent cone and this constraint cone

Define the cone $G(\textbf{x} = \{\textbf{p} \in \mathbb{R}^n | \nabla g_i(\textbf{x}^T \textbf{p} \leq 0, i \in I(\textbf{x})\}$ So this is a cone associated with the inequality constraints that is fulfilled with equality at the point $\textbf{x}$.…
Benjamin Lindqvist
  • 3,112
1
vote
2 answers

$\,f:[0,1)\to\mathbb R$ is a concave differentiable function st $\,f(0)=0$. Show that $g:[0,1),g(z)=f(zx)/z$, for $x > 0$ is decreasing

Question: Suppose that $f : [0, 1) \to\mathbb R$ is a concave differentiable function such that $\,f(0) = 0$. Show that $g : [0, 1) \to\mathbb R$ defined by $g(z) = f(zx)/z$, for some given $x > 0$, is a decreasing function of $z$. Thoughts: I am…
erin
  • 125
1
vote
0 answers

Can this type of constraint be recasted to a convex constraint?

I have an optimization problem where all the constraints are linear but some of the type: $$ y_i = \frac{x_i}{\sum_k x_k} $$ It seems that the equality can be relaxed to an inequality adding the linear constraint: $$ \sum_k y_k =1. $$ I further have…
PabloCM
  • 11
1
vote
2 answers

Help needed on convex optimization!!

Can some please help me in solving the below questions. I want to prove the below functions are convex, concave or neither.
drag88
  • 11
1
vote
1 answer

Sparse representation using overcomplete dictionary - when is L1 norm not good enough?

I am trying to find a sparse representation of a signal consisting of a single sinusoid and a single spike (delta function), via what I think is traditionally called "basis pursuit", using $L_1$ norm minimization. Specifically, I have a…
Maverick007
  • 13
1
vote
1 answer

Hyperplane separating fraction of points

Given a set of points $S$ and a fraction $\alpha$ I would like to find exactly one hyperplane which divides $S$ such that approximately $\alpha$ points lie on one side and $1-\alpha$ points on the other. Can this be formulated as a strictly (maybe…
Manuel Schmidt
  • 840
1
vote
0 answers

Confusion related to proximal newton method

I was reading this method related to proximal newton methods http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2012_0388.pdf. I came across this page I didn't get what this part means $ \frac{1}{2}||y-x||^2_H $ what does H signify here and…
user12331
  • 299
1
vote
0 answers

restricted set of a convex set

Let $S \subset \mathbb R^n$, $S$ is convex and let $||.||$ be a norm on $\mathbb R^n.$ For $a \ge 0$ we define $S_{-a} =\{ x | B(x,a) \in S\}$, where $B(x,a)$ is the ball (in the norm $||.||)$, centered at $x$, with radius $a$. Prove that for any $x…
user
  • 1,391
1
vote
1 answer

Propertise of a Dual Cone

In Convex Optimization by Boyd (P.51) said that " $y\in K^*$ iff $-y$ is the normal of hyperplane that supports $k$ at the origin ($K^*$ is a dual cone of $K$) " what does it mean geometrically? I mean could someone please show me a figure that…
eHH
  • 463
  • 1
  • 4
  • 14
1 2 3
…
24 25