Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

2
votes
1answer
64 views

Got stuck with this $L^2(-1, 1)$ optimization problem. Any ideas where it comes from?

Statement Let $u(x) \in L^2(-1, 1)$. Solve the following optimization problem: $$ \begin{cases} J(u) = 4 \int_{-1}^{1} \sqrt{|x| (1 - |x|)} u(x) dx + \left(\int_{-1}^1 \sin(3\pi x) u(x) dx\right)^2 ...
2
votes
1answer
222 views

Convert Semidefinite program forms

How do I convert the following SDP problem (written in the standard inequality form): $$\min c^T x$$ $$\text{s.t. }F(x)\succeq0$$ When $F(x)\equiv F_{0}+\sum_{i=1}^{m}x_{i}F_{i}$ when $F_{i}\in ...
2
votes
1answer
347 views

Solution to a Quadratic Minimization with Norm Constraint

How do I solve the optimization problem \begin{align} &\min_{\mathbf{x}\in\mathbb{C}^N}\mathbf{x}^H\mathbf{A}\mathbf{x}+2\Re\{\mathbf{b}^H\mathbf{x}\} \\ \mbox{subject to }\\ ...
2
votes
2answers
329 views

What change of variables, if any, transforms this nonconvex problem into a convex one?

I'm looking for a convex reformulation, if any exists, of the following minimisation problem: Let $A$ be a symmetric, positive definite $n \times n$ matrix, and $b \in \mathbb{R}^n$. Minimise ...
2
votes
1answer
52 views

What is the name of this object?

Suppose I have a convex set $K\subset X$, where $X$ is say a real Hilbert space (for simplicity). Then, given some $a\in \Bbb{R}$, let $$ \hat{K}=\{x:\langle x,y\rangle \leq a \;\forall y\in K\} $$ ...
2
votes
2answers
143 views

Prove Convexity of Recursively Defined Function

Let $\mathbf{x}=[x_1, x_2, \dots, x_K]\in\mathbb{R}^K_{++}$ and $E_1>E_2>\dots>E_K>0$ are positive constants. If $$f_i:\mathbb{R}^K_{++}\rightarrow\mathbb{R}_{++}\quad\forall1\leq i\leq ...
2
votes
3answers
83 views

Convex set. Proof.

Prove that if A is convex set and $\alpha, \beta ≥ 0$ then $(\alpha + \beta)A = \alpha A + \beta A$ What came first on my mind is that I have to show that $(\alpha + \beta)A\subset \alpha A + \beta ...
2
votes
2answers
339 views

Finding convex conjugate of a bounded function

The convex conjugate of a function $f:\mathcal{X}\mapsto \mathbb{R}$ is formally defined as $$f^\star\left(y\right)=\sup_{x\in\mathcal{X}}\ \left\langle x,y\right\rangle-f\left(x\right).$$ In cases ...
2
votes
2answers
150 views

Analytical Solution to a simple l1 norm problem

Can we solve this simple optimization problem analytically? $ \min_{w}\dfrac{1}{2}\left(w-c\right)^{2}+\lambda\left|w\right| $ where c is a scalar and w is the scalar optimization variable.
2
votes
2answers
65 views

What are the relations between these two minimizations

What are the relations between the minimization problems $\arg\min_{\mathbf{y}=A\mathbf{x}}\left\Vert \mathbf{x}\right\Vert _{2}$ and $\arg\min_{\mathbf{x}}\left\Vert A\mathbf{x-y}\right\Vert _{2}$ ?
2
votes
2answers
128 views

Constrained maximization problem

I need help with the following optimization problem $$ \max\;\alpha\ln(x(1-y^2))+(1-\alpha)\ln(z) $$ where the maximization is with respect to $x,y,z$, subject to \begin{align} \alpha ...
2
votes
2answers
91 views

Geometric difference between $x^TAx$ and $x^TAx + b^Tx + c$

What is the difference between $x^TAx$ and $x^TAx + b^Tx + c$ geometrically? Some analogous examples from quadriatic equations would be great.
2
votes
2answers
1k views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
2
votes
1answer
154 views

Continuity of solutions to convex optimization problems

Let $x_A$ solve $$ \min J(x) \quad \text{subject to} \quad Ax=b $$ and $x_B$ solve $$ \min J(x) \quad \text{subject to} \quad Bx=b $$ given that $\|A-B\|_\text{operator} \leq \epsilon$ and that $J$ is ...
2
votes
1answer
51 views

Why can't the hyperplane H intersected with polyhedral set S contain any line…

S is the polyhedral set $ S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \} $ and $ H : \mathbf{c}^{T}\mathbf{x} = \beta $ with $ \min_S ( ...
2
votes
1answer
209 views

Proving ellipsoid A is a subset of ellipsoid B iff (B-A) is positive semi-definite

I am reading Boyd's Convex Optimization book and I am stuck on the reasoning behind one of the statements. Specifically, I am looking at page 45, line 3 from the bottom. The statement is: $A \preceq ...
2
votes
1answer
60 views

Calculating the distance function and projection

Let $\Omega=\{x\in\mathbb R^n\mid\langle a,x\rangle=b\}$. We define the distance function and projection as follows $$d(x;\Omega)=\inf\{||x-\omega||\mid\omega\in\Omega\}$$ ...
2
votes
1answer
79 views

Is standard eigenvalue optimization problem convex

For any arbitrary symmetric matrix A , is the standard eigenvalue problem convex $ \lambda_{max}(A)= \max_{\|x\| \leq1} x^{T}Ax$
2
votes
1answer
49 views

A Variant of Gradient Descent

Suppose I have some objective function $f(\beta)$ which I would like to minimize for $\beta$. A standard gradient descent would be $\beta^{(t+1)}=\beta^{(t)}-\alpha \nabla f(\beta^{(t)})$, where ...
2
votes
1answer
41 views

Does $\log(f(X))$ concave implies $\log(f(X^{-1}))$ convex?

One of my professor claims that $\log f(X)$ concave implies that $\log(f(X^{-1}))$ convex where $X$ is symmetric positive definite matrix. $\log(f(X))$ is a function defined on symmetric positive ...
2
votes
1answer
34 views

Constructing a newton sequence

How may I construct the newton sequence for the following: $(1) f(x_1,x_2) = x_1^4 + 2x_1^2x_2^2 + x_2^4$ with $x_0 = (1,1)$ and $x_0 = (1,0)$ $(2) f(t) = t^4 - 32t^2$ and $t_0 = 1$ To find ...
2
votes
1answer
70 views

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 ...
2
votes
2answers
55 views

Interpreting norm definition

Book: Convex Optimization (Author: Stephen Boyd), Appendix A, Topic: A.1.2 Norm,distance, and unit ball Can anyone please help me in understanding the following definition of "norm" $$ \| x \| ...
2
votes
1answer
172 views

Solving L1 regularized Joint Least Squares and Logistic Regression

My objective function that is to be minimized is as follows: $f = -\sum_{n=1}^{N}log~p(y_{n}^{a}|x_{n},w) + \sum_{n=1}^{N}(y_{n}^{b}-w^{T}x_{n})^{2} +\lambda\|w\|_1$ The first term models the ...
2
votes
1answer
66 views

Formulation of convex constrained optimization problem (SVR)

I'm trying to figure out where I'm going wrong with my formulation of a certain problem, as all other instances of it were formulated slightly differently. The problem (SVR problem, If you're ...
2
votes
1answer
90 views

Normal Cone of $\mathbb{R}^n_+$ and $S^n$?

I'm trying to solve the problem $\min_x \{f(x) + \delta_X(x)\}$ where $f$ is a differentiable function and $\delta$ is the indicator function $\delta_X(x) = \begin{array}{l}0, x \in X \\ ...
2
votes
2answers
121 views

Efficiency of a max-min problem for $\sum_{j=1}^m |b_j-a_j|$ with $a_i$, $b_j$ restricted to convex sets

Consider the following optimization problem: $$\max_{\{a=(a_1,a_2,\ldots,a_m)\in A\}}\min_{\{b:=(b_1,\ldots,b_m)\in B\}} \sum_{j=1}^m |b_j-a_j|.$$ Is computing the optimal value of this problem ...
2
votes
1answer
176 views

Sum of k-largest eigenvalues of a symmetric matrix as an SDP

I found the following statement from a google search. If $S_k(\mathbf{X})$ is the sum of the $k$ largest eigenvalues of a symmetric $m\times m$ matrix $\mathbf{X}$, then,$$S_k(\mathbf{X}) \leq t$$ is ...
2
votes
1answer
161 views

Is there a nice representation for KKT conditions for matrix constraints?

I have a convex programming problem: $\min \left\lVert J - R \right\rVert _F$ $J,R$ are matrices. $J$ is given for the problem. One of the constraints is: $R = KQ$ Here, $R,K,Q$ are matrices. $K$ ...
2
votes
1answer
151 views

min : sum of L2 norm and squared-L2 norm.

Is there a closed-form solution of the following convex problem: $$\min_x \| x - u \| + C \| x - v \|^2$$ where $\| \cdot \|$ is the L2 norm.
2
votes
1answer
98 views

Proximal operator, scaling by a matrix

Proximal operator is defined for matrices as a map prox$_f:R^m\times R^n \rightarrow R^m\times R^n$: prox$_f$(X) := argmin$_{Y\in R^m\times R^n}$ $ f(Y) + \frac{1}{2}||Y-X||^2$ In case of vectors, ...
2
votes
1answer
92 views

How to minimize $\max(x_1, x_2)$ and $x_1^2 + 9x_2^2$ subject to constraints?

My textbook came up with a solution without explanation. I'm looking for a systematic way of solving the following optimization problems and similar ones (by hand), because I'm drawing a blank: ...
2
votes
1answer
116 views

Help with a proof of a theorem about convex sets

I'm studying the following theorem: Theorem 1. Let $C$ be a convex set and let $\textbf{y}$ be a point exterior to the closure of $C$. Then there is a vector $\textbf{a}$ such that ...
2
votes
2answers
261 views

Is alpha divergence a convex divergence measure?

Alpha divergence is defined as following : $$ D_\alpha(p||q) = \frac{1}{\alpha (1-\alpha)} \left( 1- \int _x p(x)^{\alpha} q(x)^{(1-\alpha)} dx \right) $$ if the distributions are restricted to ...
2
votes
1answer
159 views

Prove or disprove that the given expression is “always” positive

I have previously asked a question and I tried to solve it by my own and it led to the question below: Prove or disprove that ...
2
votes
2answers
647 views

Linear optimization problem: Minimizing a linear function over an affine set.

The problem is as follows: Give an explicit solution of the linear optimization problem below. $$ \text{minimize}\ c^Tx \\ \text{subject to}\ Ax\ =\ b $$ No other information is given. My ...
2
votes
1answer
3k views

Armijo's rule line search

I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13. The variable is $\beta$ ...
2
votes
2answers
565 views

What does it mean to restricting a function to a line in convex optimization?

In lecture 3 of the course Convex Optimization conducted by Stephen Boyd at 21 minutes mark he says that a function is convex if its convex when we restrict it to a line. What does he mean by ...
2
votes
1answer
107 views

Approximating a function with a convex function

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a continuous, differentiable function. Is there a known algorithm that fits $f$ with $g$, which is an order-$n$ polynomial that is convex, in the least ...
2
votes
1answer
82 views

Are all polytopes also convex hulls?

It seems, at least in the 2-D case, that all polytopes are going to be convex. Does this hold if the dimensions are increased?
2
votes
1answer
77 views

Is this operator monotone?

Consider a convex optimization problem. $$\min_{u\in\Re^k} f(u)$$ s.t. $g_i(u)\leq0,\ i=1,\ldots,m$ Let ...
2
votes
2answers
746 views

Lasso with linear constraints

I want to efficiently solve the following optimization problem: \begin{align} \min &\quad \left\|\mathbf{x}-\mathbf{x}_0\right\|_2^2 + \lambda\left\|\mathbf{x}\right\|_1\\ \text{Subject to}& ...
2
votes
2answers
281 views

Gradient descent vs ternary search

Consider a strictly convex function $f: [0; 1]^n \rightarrow \mathbb{R}$. The question is why people (especially experts in machine learning) use gradient descent in order to find a global minimum of ...
2
votes
1answer
499 views

Moreau-Yosida regularization problem

Let $$F(x)=\min\limits_{y\in \mathbb R^n}\{f(y)+\|x-y\|^2\} ,$$ where $f(y)$ is convex and bounded below. How to show that if $x^*\in \arg \min \{F(x)\}$, then $x^*$ is in the closure of the ...
2
votes
1answer
79 views

Convexity of k points

Let $C \subset \mathbb{R}^n$ be a convex set. Additionally, $x_1, x_2,\dots, x_k \in C$ and $\theta_1,\theta_2,\dots,\theta_k \in \mathbb{R}, \theta_i \ge 0, \sum\theta_i = 1$. I have to proof that ...
2
votes
1answer
159 views

$\epsilon$-normals to convex sets

I am reading the book by B. Mordukhovich, Variational analysis and generalized differentiation I. On page 6 it is stated the following inclusion: $$ \hat{N}_{\varepsilon }\left( \bar{x};\Omega ...
2
votes
1answer
225 views

Maximal mapping of a convex set to the unit disk

EDIT: To make my question more precise i think we can narrow it down to this. Say you have a simple polygon that includes the origin, that is completely contained in the unit disk, we can 'blow up' ...
2
votes
1answer
73 views

Positive Semi-Definiteness of Least Squares Estimator

I am reading Boyd's Convex Optimization Text, and I am curious to know why the following is true: $$F F^T \succeq F^* {F^*}^T,$$ where $F^* {F^*}^T = (A^T A)^{-1}$ and $FA = I.$ I already tried ...
2
votes
1answer
196 views

Non-negative solution to matrix equation

I want to solve $Ax = b$ subject to the constraint that all of the elements of $x$ are non-negative. If such a solution does not exist, I want to find non-negative $x$ such that the quadratic form ...
2
votes
1answer
198 views

study objects of convex analysis and optimization

In the area of convex analysis and the area of optimization in their general sense, are convex subsets assumed to be in vector spaces or topological vector spaces? Are convex functions defined to be ...