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

learn more… | top users | synonyms

-3
votes
1answer
32 views

Prove a convex function

I have to prove that if $f:A \to \mathbb{R}$ is convex and $c \ge 0$ then $c \cdot f:A \to \mathbb{R}$ is convex. I know that function $f:A \to \mathbb{R}$ is convex if for $\forall x,y \in A$ and ...
0
votes
1answer
21 views

Is the following function concave? (or log of it)

I have a function $f(x_1, x_2, ..., x_M) = \displaystyle \prod_{i = 1}^N \frac{(\sum_{j = 1}^{M} a_jx_jI_{ij})^2}{\sum_{j = 1}^{M} a_jx_j}$ in domain $\{{\bf x} \in {\bf R}^m \setminus {\bf 0} \ ...
2
votes
1answer
38 views

How to solve the convex optimization problem [closed]

$$\min (\|X_{(1)}\|_{*}+\|X_{(2)}\|_{*}+\|X_{(3)}\|_{*})+u\|Ax-b\|_2^2+v\|Cx\|_2^2$$ where $X$ is a three order tensor, $X_{(i)}$ is a matrix whose column are the mode-$i$ fibers of $X$(i=1,2,3),$x$ ...
0
votes
0answers
41 views

how to prove convexity of the function below?

For a graph $G$ consider the following function, $$f=\sum_{(i,j) \in G ,(i,k) \notin G } \max(0,c+ \left\|e_i-e_j\right\|_2^2-\left\|e_i-e_k\right\|_2^2)$$ where $e_i \in\mathbb R^n$ ($n$ dimension ...
0
votes
1answer
20 views

Minimizing nonsmooth single variable functions?

What options is available if one wants to minimize a nonsmooth convex function of one variable? Subgradients would work, but there has to be some nice way of utilizing that we're only searching in 1d. ...
0
votes
2answers
36 views

Convergence of a sequence of projections

Let $C \subset \mathbb{R}^n$ be a compact, convex set, and $P \in \mathbb{R}^{n \times n}$ be a positive definite matrix ($P \succ 0$). Consider the projection $\Pi_P: \mathbb{R}^n \rightarrow C$ ...
0
votes
1answer
49 views

Gradient of a Lagrange dual function

Consider: $$\min_{x \in \mathbb{R}^n} f(x)$$ $$\ \ \ \ \ \ \ \text{s.t. }\ h(x) \leq 0$$ Lagrangian:$\ \ \ L(x,\lambda) = f(x) + \lambda h(x)$ Suppose $x^* = \arg\min_{x} L(x,\lambda)$ ...
0
votes
3answers
30 views

How to show the optimal condition of $f(\alpha) = \frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2\sum_{i=1}^k \alpha_i}$

Consider the following function: ($\alpha>0$) $$f(\alpha) = \frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2\sum_{i=1}^k \alpha_i}$$ It is a quadratic (in $\alpha$) over linear (in $\alpha$); therefore, ...
3
votes
1answer
44 views

Projection of $z$ onto $\{x\mid Ax = b\}$

Suppose $A$ is fat(number of columns > number of rows) and full row rank. The projection of $z$ onto $\{x\mid Ax = b\}$ is (affine) $$P(z) = z - A^T(AA^T)^{-1}(Az-b)$$ How to show this? ...
0
votes
1answer
39 views

KKT conditions for a convex optimization problem with a L1-penalty and box constraints

I am having some trouble deriving / understanding optimality conditions for a convex optimization problem of the form: $$\begin{align} \min_{x\in\mathbb{R}^d}~ & f(x) + C.\|x\|_1 &\\ &x_i ...
0
votes
1answer
36 views

Two duality theorems

Suppose $X$ is a Hilbert space with norm $||.||$ and $K$ is a weak compact and convex subset of $X$. The supporting functional: $$h(x^*)=\sup_{x\in K} \langle x^*, x \rangle$$ The indicator ...
0
votes
0answers
17 views

Intuition on primal convergence in dual subgradient method

It is well known that the subgradient method applied to the Lagrange dual of a convex problem may produce a sequence converging to the dual optimum, but the primal iterates produced by this sequence ...
0
votes
1answer
34 views

How to solve the following non-convex optimization problem?

$$\min \|X\|_{*}+u\|Ax-b\|_2^2+v\|Cx\|_2^2 + wx^THx$$ where $x$ is vec($X$), $u,v$. is constant, H is a symmetric matrix,but it is not semidefinite. Is there any software to do this? Can the ...
1
vote
0answers
49 views

Quadratic optimization problem (inner products) with stochastic constraints

Let the set of feasible solution be the set of all row-stochastic $n \times k$ matrices $P = [p_{ij}]$, that is $\mathcal{P} := \{P \in \mathbb{R}^{n \times k} \ | \ P \mathbf{1} = \mathbf{1}, P \geq ...
0
votes
1answer
51 views

SDP relaxation of a non-convex quadratically constrained quadratic program.

I am very new to SDP and SDP solvers. I have a semi definite program of the following form $$\min_{x,X}\ Q\bullet X+c^Tx$$ $$\text{s.t. } Q^k \bullet X + (c^k)^T x =b^k , \ k=1,2, \dots,m \\ \quad ...
4
votes
2answers
94 views

Describing convex hulls in purely metrical terms

Let $X$ denote a Euclidean space; take $X = \mathbb{R}^n$ for concreteness. Now consider $x,y \in X$. Then the line segment joining $x$ and $y,$ hereafter denoted $[x,y]$, can be described in ...
3
votes
1answer
204 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
1
vote
1answer
154 views

Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P ...
0
votes
1answer
49 views

Gradient in mirror descent

Mirror descent can be in general written as \begin{equation*} \nabla\Phi(x_{t+1})=\nabla\Phi(x_t)-\lambda_t\nabla f(x_t), \end{equation*} where $f$ is the objective function and $\Phi$ is a convex ...
1
vote
2answers
140 views

Removing redundant half-spaces that bound a convex polytope

I am computationally representing a convex polytope in $\mathbb{R}^n$ as a set $A$ of half-spaces that bound it; each such half-space is represented by a row vector $\mathbf{v} = \begin{bmatrix}v_1 ...
1
vote
0answers
23 views

Solution to a nonlinear problem at an extreme point

I have a convex optimization problem of the form: $$ \begin{aligned} \operatorname*{minimize}_{\mathrm{x} = (\mathrm{x}_1, \dots, \mathrm{x}_m) \in \mathbb{R}^{nm}} &\quad f(\mathrm{x}) = ...
0
votes
1answer
28 views

Is this floor function/problem quasiconvex?

I am trying to study an optimisation problem under constraints. The point is that all my constraints are linear as well as all terms of my objective function except one. This guy : $$ \alpha^{\lfloor ...
-1
votes
2answers
37 views

How to prove a function is concave? (Single Variable)

It has been a while after completing the calculus of single variable. Right now I have a function of single variable $f(x)$, and that $f'(x)=-c$ for all $x$. So $f$ is a decreasing function. Bu, ...
0
votes
2answers
69 views

Linear optimization with “max” function (convex) constraint

I am working on a linear optimization problem which has a non-linear constraint. Suppose $x = [x_1 x_2]^T$, the problem is $$ \min_{x} \quad c^T x \\ \mathrm{s.t.} \quad Ax \leq b\\ x \geq 0 \\ ...
2
votes
0answers
59 views

solving the primal problem via dual

On pp. 248 of Boyd and Vandenberghe: suppose 1) strong duality holds, 2) the dual optimal is attained at $(\lambda^*, \nu^*)$, 3) the dual function $L(x, \lambda^*, \nu^*)$ has the unique minimizer ...
0
votes
0answers
45 views

Prove that $\int_{0 \le u \le 1,\Omega}g^2(x)udx$ in term of $u$ is convex

I am having a cost function and I want to know whether convex or not. Could you explain help me my problem? My problem is that given a cost function such as $$F(u)=\int_{0 \le u(x) \le ...
3
votes
1answer
23 views

$\nabla f$ Lipschitz & $f$ Lipschitz

My question is: Which of the following is more restrictive? $\nabla f$ Lipschitz & $f$ Lipschitz I think each one cannot imply the other. For example ($1$D): $$f(x) = \frac {x^2}{3}$$ ...
1
vote
2answers
229 views

Proving that $\text{ri rge}\,A=\text{ri conv rge}\,A$

"If $A:\mathbb R^n\rightrightarrows\mathbb R^n$ is maximal monotone,then $\text{ri rge}\,A$ is convex". This is a proposition in auslender's book about the asymptotic cones. We can prove that ...
1
vote
1answer
29 views

does constant convexity assures global minimum

I have the following question: Consider a function $f:R^n \longrightarrow R$, s.t.: there is a point $x_0 \in R^n$ s.t. $\frac{\partial f}{\partial x^k} =0$ $\forall k$. the hessian matrix ...
0
votes
0answers
162 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
1
vote
2answers
49 views

Why is the constraint $\|w\| = 1$ non-convex?

Related: Why is this function, related to SVM derivation, non-convex? I am studying notes which cover the derivation of SVM. The intuition is the geometric margin should be maximized in order to ...
2
votes
2answers
57 views

What is the interpretation of the following optimization problem?

Suppose we have $N$ variables $x_1,\ldots,x_N$. Let $\mathbf{A}$ a $M \times N$ matrix, and $\mathbf{b}$ a $M \times 1$ vector. I have the following minimization problem: \begin{array}{rl} \min ...
0
votes
1answer
43 views

Express a second-order cone (SOC) inequality as a linear matrix inequality (LMI)

For $y \in \mathbf{R}^n$ and $t \in \mathbf{R}$, show that: $$||y||_2 \leq t ~~\iff~~ F(y) \succeq 0$$ Where $\text{I}$ is the $n \times n$ identity matrix, and $$F(y) = \begin{pmatrix} t ...
1
vote
3answers
41 views

Constrainted optimization involving logarithms

The problem is to minimize $ f(x_1, x_2 ,x_3, x_4):= - \Big[ \log ({\frac{1}{4} + x_1}) + \log ({\frac{1}{2} + x_2})+ \log ({\frac{1}{5} + x_3})+ \log ({\frac{3}{4} + x_4}) \big]$ such that ...
0
votes
1answer
37 views

Why is one of the KKT conditions the same as one of the constraints?

I'm working through an SVM tutorial (from Andrew Ng Stanford course notes). In the brief coverage of Lagrange duality. The primal optimization problem is stated $$ \min_{w} \theta_{\mathcal{P}}(w) = ...
1
vote
1answer
41 views

Why is this function, related to SVM derivation, non-convex?

I'm working through a support vector machines tutorial. In eventually deriving the solvable objective function, the following objective function (to be maximized) was proposed, but dismissed as ...
0
votes
0answers
15 views

Deriving Dual Averaging from (Sub)gradient Descent

Here the presenter tries to derive a simple Dual Averaging from (sub)gradient descent. I have a little problems understanding the steps. (Sub)gradient descent: Loop through: $$ x_{k+1} = x_k - t_k ...
0
votes
0answers
17 views

Convergence analysis of gradient descent method

From the following: Convex Optimization (S. Boyd) p.467 Content: We will see that the gradient method does in fact require a large number of iterations when the Hessian of $f$, ...
0
votes
1answer
41 views

Is inequality $tr(A^{-1^T} B) tr(A^T B^{-1}) \leq constant$ correct?

I have the following optimization problem \begin{align} \min_{A} &tr(A^{-1^T} B)\cr \text{subject to} &x^T A x > 0 \cr & A_{ii}=1 \end{align} where $A$ and $B$ are some positive ...
5
votes
1answer
128 views

are elementary symmetric polynomials concave on probability distributions?

Let $S_{n,k}=\sum_{S\subset[n],|S|=k}\prod_{i\in S} x_i$ be the elementary symmetric polynomial of degree $k$ on $n$ variables. Consider this polynomial as a function, in particular a function on ...
0
votes
0answers
35 views

Is convex or non convex function?$J(u,c)=\int K(x).u.(f(x)-c)^2dx$

I have a function such as $$J(u,c)=\int K(x).u.(f(x)-c)^2dx$$ where $f(x):\Omega \to R$; c is constant; $0 \le u \le 1$; and K(.) is gaussian kernel. My question is that : Is J convex or non-convex ...
8
votes
2answers
5k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value ...
1
vote
1answer
81 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
-2
votes
1answer
24 views

Inversion of a matrix in a system of linear inequalities

I would like to know if someone knows sufficient conditions on $A\in\mathbb{R}^{n\times n}$ and $b\in\mathbb{R}^{n}$ such that for all $x\in\mathbb{R}^{n}$: $$Ax\leq b \Rightarrow x\leq A^{-1}b \text{ ...
1
vote
0answers
34 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
2
votes
1answer
59 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\}$$ ...
0
votes
1answer
25 views

Supporting lines of closed Jordan curve

Given a simple closed Jordan (i.e. continuous) curve $\gamma:[a,b]\to\mathbb{R}^2,\ \gamma([a,b])=C_\gamma$, how can I prove that $D_\gamma$ (the set of all interior points of $\gamma$ toghether with ...
1
vote
1answer
52 views

Dual residual for linearized ADMM

I am using linearized ADMM for a problem with a (non-smooth) convex loss function $f(x)$, and a hard constraint $x \in E$, where $E$ is an ellipsoid in $R^d$. I have encoded the hard constraint as $A ...
1
vote
1answer
48 views

Is $f(X) = \| Y - XX^T \|_F$ convex given fixed $Y$?

In the scene of nonnegative matrix factorization, $f(X_1, X_2) = \| Y - X_1 X_2 \|_F$ is not convex, but both $f(X_1)$ given fixed $X_2$ and $f(X_2)$ given fixed $X_1$ are convex, enabling us to ...
3
votes
0answers
23 views

On the solutions of a system of inequalities avoiding Helly's theorem

Let $a_1,b_1,\cdots,a_4,b_4\in\mathbb{R},r_1,\cdots,r_4\in(0,+\infty)$. Show that, if $\not\exists (x,y)\in\mathbb{R}^2$ such that $$ \begin{cases} (x-a_1)^2+(y-b_1)^2\le r_1\\ ...