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

learn more… | top users | synonyms

1
vote
2answers
38 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
44 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 ...
-1
votes
1answer
17 views

Subgradient Method Example [on hold]

can anyone show me an example(function) of subgradient method(unconstrained)? subgradient algorithm https://inst.eecs.berkeley.edu/~ee227a/fa10/login/l_cvx_alg.html ...
0
votes
1answer
33 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
1answer
24 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
126 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 ...
0
votes
1answer
23 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
3answers
30 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
0answers
12 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
12 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
36 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 ...
1
vote
1answer
32 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 ...
1
vote
0answers
29 views

How to solve the following convex optimization problem?

$$\min \|X\|_{*}+u\|Ax-b\|_2^2+v\|Cx\|_2^2$$ where $x$ is vec($X$), $u,v$. is the scalar. Is there any software to do this? Can the software cvx solve it?
0
votes
0answers
28 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
23 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{ ...
0
votes
0answers
11 views

I want to find a maximum of a function by Maple. How to restrict the variables to be integers? [on hold]

For example, I want to find the maximum of $x^2+y^2$ with $0\le x,y\le 10$ in Maple. I can type $$maximize(x^2+y^2,x=0..10,y=0..10).$$ But if I restrict $x$ and $y$ to be both integers, then how can ...
1
vote
0answers
29 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
51 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
0answers
21 views

A min-max problem and convex optimization problem.

Let $x^*$ a solution of the convex programming problem $$ \begin{array}{rl} \max & f_0(x)&\\ \mbox{s.t.} & g(x)\leq 0 \end{array} $$ where $f_0:\mathbb{R}^n\to \mathbb{R}$ and the ...
3
votes
0answers
21 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
21 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
0answers
15 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
0answers
10 views

Analysis of Optimizatiointechniques: Regret Analysis vs. Direct convergence? [closed]

When it comes to convergence rate analysis of optimization algorithms (like gradient descent and its family), there seems to be to be two main: Direct analysis, i.e. bound on $$ |f(x_t) - f(x^*)| ...
0
votes
1answer
11 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
31 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
24 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
46 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
54 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
41 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
60 views

Theorem 6.4.1 Auslender Asymptotic cones and functions in optimization and variational inequalities

In proof of Theorem 6.4.1, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that $\epsilon^{-1}(C-\text{rge}\,A)\subset\text{aff}\,(C-C)$, that I can't verify ...
1
vote
1answer
28 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
15 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*} ...
0
votes
1answer
157 views
+50

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
50 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
16 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
59 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
78 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
42 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
51 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
30 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
25 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
12 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 ...
1
vote
0answers
51 views

Proof that equation is non-convex function

I have a objective function as following $$E(\phi)=\int_{\Omega}(I(x)-m_1)^2H(\phi(x))dx+\int_{\Omega}(I(x)-m_2)^2(1-H(\phi(x)))dx+\int_{\Omega}|\nabla H(\phi(x)|dx$$ where $I$ is an image; $I: \Omega ...
0
votes
1answer
13 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 ...
0
votes
0answers
30 views

Intuition between convex function and convex set

In my text (Luenberger), there is a proposition about convex set Prop: let $f$ be convex function on convex set $\Omega$. The set $\Gamma_c = \{{x: x\in \Omega, f(x) \leq c}\}$ is convex ...
1
vote
0answers
35 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
52 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
23 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
21 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
37 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 ...