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

learn more… | top users | synonyms

1
vote
1answer
42 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
37 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 ...
-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
38 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
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\}$$ ...
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\\ ...
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 ...
0
votes
1answer
31 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 ...
0
votes
1answer
14 views

Concave-Convex Decomposition of a continuous function

In this paper http://www.stat.ucla.edu/~yuille/pubs/optimize_papers/cccp_nips01.pdf they have a theorem that says that a twice continuous differentiable function (an energy function, they say) with ...
0
votes
1answer
53 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
1answer
63 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
2answers
56 views

Is it convex function?

I have a function and I don't know it is whether convex or non-convex: $$J(c,\alpha)=\int_\Omega ( \alpha c-I(x))^2u \, dx+ \|\alpha\|^2$$ where $0 \le u \le 1$, $I(x): \Omega \to R$, $c$ is constant ...
0
votes
1answer
61 views

Algorithms For Large-Scale $\ell_{\infty}$ Minimization

The general problem I want to solve is well studied: $$ \min_x \Vert Ax\Vert_\infty \;\;\; \mathrm{s.t.} \;\;\; Bx=c, $$ which is equivalent to the following linear program: $$ \min_{t,x} \, t ...
0
votes
1answer
94 views

MATLAB: minimize function using x value from previous iteration

I'm trying to develop an algorithm for a proximal point method defined as: $$ \underset{x \in \rm I\!R^n}{\arg\min} f(x) + \lambda g(x) $$ where f(x) is a convex and coercive function and also ...
1
vote
2answers
73 views

proving that $\text{aff}C-\text{aff}C\subset\text{aff}\,(C-C)$

In proof of Theorem 6.4.1 of Auslender's book about asymptotic cones, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that ...
1
vote
1answer
36 views

any good way to approximate this non-convex function with convex function?

There is a non-convex constraint in my optimization problem, which is given by $\displaystyle -xy\log\left(1+\frac{z}{xy}\right)$. Obviously, it is neither convex or concave. Is there any good convex ...
0
votes
0answers
17 views

Help required in solving the lagrangian dual?

I'm trying to write the Lagrangian dual to the following problem \begin{align*} (P) \quad \min\;&\text{Trace}(CG)\\ \text{s.t.}\;&G \succcurlyeq 0\\ & G_{i,i}=I_d (i=1,..,M+1)\end{align*} ...
1
vote
2answers
230 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 ...
0
votes
3answers
54 views

Prove $||\lambda x_1 + (1-\lambda) x_2 - y|| \leq ||x_1 - y||$

Assume we have have $3$ points $x_1, x_2$ and $y$ and $||x_1-y||=||x_2-y||$. How do we prove that the distance between $y$ and the convex combination of $x_1$ and $x_2$ is smaller than that between ...
0
votes
1answer
25 views

Analysis of iterative optimization methods using lyapunov analysis

In analysis of iterative methods, is it possible that we have to use two time-lagged version of the time-varying system to analyze its convergence? (that is, we construct the evolution of x^k, ...
1
vote
1answer
85 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 ...
5
votes
2answers
89 views

Proving $x^4$ is strictly convex

I'm not sure how to prove $f(x) = x^4$ is strictly convex using just the definition of strict convexity: $$f((1-t)x+ty) < (1-t)f(x)+tf(y)$$ for $0<t<1$. Is this just an algebra slog? If so, I ...
0
votes
0answers
45 views

How to prove $f(x_1,\ldots,x_n) = \sum x_i\ln x_i - (\sum x_i )\ln(\sum x_i)$ is convex on R++ [duplicate]

How can i prove $f(x_1,\ldots,x_n) = \sum x_i\ln x_i - (\sum x_i )\ln(\sum x_i)$ is convex on R++
0
votes
2answers
79 views

How to compute primal variable based on dual variables and their multipliers

I edited this question based on information I got from comments. Assume we have an optimization problem (primal problem). we solve it's dual using some kind of primal-dual interior point solver. So, ...
1
vote
0answers
33 views

tangent cone to the set

I'm supposed to solve this problem: Let us consider the set $M=\{(x, \sin{x}):x\in\mathbb{R}\}\cup\{\big(\cos(x)-1,x\big):x\in\mathbb{R}\}$ The question is to find the tangent cone to the set $M$ in ...
0
votes
0answers
59 views

Karush-Kuhn-Tucker conditions for non-linear optimalization

I have the following problem: solve the local conditions (KKT) and find ALL optimal solutions: $$\min f(x,y)$$ subject to $$g(x,y)\le 0$$ $$x\geq0, y\in\mathbb{R}$$ I have some questions to this ...
0
votes
1answer
23 views

Gradient of squared distance to a convex set

I have the following problem: Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$, $f(x)=(\operatorname{dist}(x,D))^2$ where $D$ is a convex, close set in $\mathbb{R}^n$. Prove that $f$ is convex and ...
0
votes
1answer
17 views

Under what hypotheses is a solution to the Lagrangian multiplier equations automatically a global minimum?

Suppose we are minimizing a function $f(x_1,...,x_n)$ under the conditions $g_1(x_1,...,x_n) = g_2(x_1,...,x_n) = 0$. Under what hypotheses is a solution to the Lagrangian multiplier equations ...
1
vote
0answers
37 views

Optimization of sum of logs

I have an optimization problem of the form $$\operatorname*{argmax}_{\mathbf{w}} \sum_i \log(1 + \mathbf{w} \cdot \mathbf{k_i})$$ given some set of vectors, $\mathbf{ \{k_i\} }$. I have tried both ...
1
vote
1answer
104 views

How to project gradient vector to subspace defined by linear constraints

I have the following set of linear constraints: $$\begin {align}\textbf{y}^T\textbf {x} &= 0 \\ \textbf {0} &\leq\textbf {x} \leq C\cdot\textbf {1},\end {align}$$ where $\textbf {y} \in ...
0
votes
1answer
42 views

Is the normalized duality mapping symmetric?

In the area of functional analysis, nonlinear operator theory, the normalized duality mapping on a Banach space $X$ is a set valued map from $J:X\rightarrow 2^{X^*}$ given by \begin{align} ...
0
votes
0answers
34 views

Product of linear and convex function

More specific, how many maxima are there for product of these two functions: $ f(x) = ax + b $, and $ a > 0 $ $ g(x) $ is (strongly) decreasing convex function, $ \lim_{x\rightarrow\infty} g(x) = ...
0
votes
1answer
39 views

A maximization problem within the simplex

Let $\lambda_i$ be an ordered list of $N$ positive numbers, $\lambda_1<\lambda_2<\dots<\lambda_N$. I'm looking for the extrema of the function $$ f=\left(\sum_{i=1}^N p_i \lambda_i ...
0
votes
1answer
16 views

Example of convex subset (unbounded) with $\text {rec} (C) = {0}$

Example of convex subset (unbounded) with $\text {rec} (C) = {0}$ I've proved that for a bounded convex subset $C$ it always holds that $\text {rec} (C) = {0}$. However, now I'm looking for an ...
1
vote
1answer
30 views

How can a second-order cone problem be expressed as a conic problem?

I realize that a second-order cone is a cone, and thus an SOCP is a type of conic problem. However, to me it doesn't seem so apparent, looking at their equations. Could someone explain how one could ...
0
votes
1answer
25 views

Find the edges of a polyhedron P.

Given the polyhedron $P = \{v \in \mathbb R^2 \mid Av \le b\}$ with $A = \begin{bmatrix} -1 & -1 \\ 2 & -1 \\ -1 & 2 \\ 1 & 2 \end{bmatrix}$ and $b = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 2 ...
0
votes
2answers
62 views

How to check if given polyhedron is empty

Consider a polyhedron specified as following set of equalities and inequalities $$ \begin{aligned} &\mathbf{A}\mathbf{x} = \mathbf{b},\\ &\mathbf{x} \geqslant \mathbf{0}. \end{aligned} $$ Are ...
1
vote
0answers
13 views

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, ...
1
vote
1answer
37 views

Proximal Operator of $\ell_{\infty,1}$ norm of a matrix

How can I calculate the proximal operator of mixed norm $\ell_{\infty,1}$ for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_{\infty,1} + \frac{1}{2\tau} ||X-Y||_F^2$ where ...
0
votes
1answer
23 views

Relaxing the elements of a matrix

I try to understand a specific part of the paper "Consistent shape maps via semidefinite programming", where a binary symmetric Input matrix $X^{in}$ is given with $X^{in} \in \{0,1\}^{nm \times nm}$ ...
1
vote
0answers
32 views

Do quasi-Newton methods check the second-order optimality condition?

I have a practical question about quasi-Newton methods. In quasi-Newton methods, Hessian matrix is approximated. It seems to be impossible for them to check the second optimality condition. In ...
0
votes
1answer
46 views

Weighted least squares with nuclear norm minimizaiton, how to optimize?

Nuclear norm minimization is very popularization and formulation is least squares term with nuclear norm term as following, $$\min\limits_{X} ...
2
votes
0answers
22 views

Sion Minmax theorem for integral operators

Suppose $f, g\in S=L^p([0,1],\Sigma,\mu,[0,1])$. The objective $L:S\times S\to R$ is given by $$L(f,g)= \int f (h-g) d\mu, $$ where $h\in S$ is fixed. Could we apply Sion Minmax theorem to conclude ...
2
votes
2answers
50 views

Why a convex cone cannot have more than one extreme point?

The way I define an extreme point is : A point which cannot be defined as a convex combination of two distinct points. I'm not able to extend this and show why a convex cone cannot have more than ...
3
votes
1answer
33 views

Convexity of |y-X'w|^2 given that inverse of X does not exist

Can we say anything about the convexity of the $|y-X^Tw|^2$ if we know that inverse of $X$ does not exist? Hessian is $2XX^T$. Given that X is not invertible, can we conclude that $XX^T$ is ...
0
votes
0answers
22 views

Convergence of backtracking and gradient descent.

I am thinking a bit about the following exercise: Let $f(x) = x_1^2 + x_2^2$ with dom $f = \{ (x_1,x_2):x_1 > 0 \}$. The optimal value of this problem is $p^* =1$, but it is never attained since ...
2
votes
1answer
92 views

Check if convex polygon is completely contained completely within another convex polygon.

How can I determine if a convex polygon is completely contained within another convex polygon where speed is critical? I've thought about doing this, which will only use inequalities: pcp = ...
0
votes
1answer
12 views

If a quadratic form $f$ takes the minimum on a triangle in a vertex, what can I say about min of $f$ on edges of a subdivision?

Let $f(x)=x^2+y^2$ be the Euclidean square-norm and $A,B,C\in\mathbb{R}^2$ be vertices of a triangle $\Delta$ such that $f$ takes the maximum on $\Delta$ in $C$, the minimum in $A$ and takes the ...
0
votes
0answers
37 views

Using semidefinite programming to solve the following problem

I am struggling with the following problem, and wonder is SDP can help: $$\mathrm{maximize\ } \alpha_{10}+\alpha_5+(\alpha_2+\alpha_8)/2 \mathrm{\ subjected\ to\ } \mathrm{T_1}\succeq0, ...
1
vote
1answer
16 views

Convex combination and convex set

From where does $tx + (1-t)x'$ originate from? I am selfstudying an economists book, and this is popping up all of a sudden. I get that it's a line between $x$ and $x'$, but why? And is $tx' + (1-t)x$ ...