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

learn more… | top users | synonyms

0
votes
1answer
28 views

Prove in newton's method

I have to prove, that the direction in Newton's method is a descent direction if the Hessian is positive defnite. My idea: $ direction = -H(x)^{-1}*\nabla f(x)$ Put how can I prove ...
4
votes
1answer
40 views

Prove convexity of three similar sets

given the following 3 sets: $ \{ (x,y,z): x \ge y^2 + z^2, z>0 \} $ $ \{ (x,y,z): x^2 \ge y^2 + z^2, y>0 \} $ $ \{ (x,y,z): x^2 \ge y^2 + z^2, x>0 \} $ The first set is convex because it ...
0
votes
1answer
15 views

Convex or Quasiconvex Relaxed Binary Quadratic Optimization Problem

Let's say I have a quadratic problem with nonnegative triangular matrix Q and binary decision variables x. $$min_{x} f(x) = ...
2
votes
1answer
85 views

How to find the minimum distance from a point to a set?

Let $M=\{x: x_{1}^{2}+x_{2}^{2}+x_{3}^{2}\le4, x_{1}^{2}-4x_{2}\le0\}$ and $y=(1,0,2)^{T}$. Find the minimum distance from $y$ to $M$, the unique minimizing point and a separating plane. Does anyone ...
0
votes
0answers
23 views

How to solve the following optimization problem with projection?

How to solve the following optimization problem with projection? \begin{alignat}{1} &\min_{u_+,u_-,s,l\geq 0} \frac{1}{\lambda} \langle A ,(a +u_+-u_-)(a +u_+-u_-)^\mathsf{T} ...
0
votes
0answers
36 views

how to find the maximum area of a two rectangle under a parabola

Starting from a very basic concept, what is the largest triangle to be drawn under the function $f(x)$ as shown in the figure. Picking an arbitrary point on the x-axis $(x, 0)$ and its mirror $(-x, ...
1
vote
0answers
26 views

How to use Farkas' lemma?

How can I prove, that the set $$P = \{(x, y) \in \mathbb{R}^{n+m} : Ax + By \geq c, \: x \geq 0^n, \: y\geq 0^m \}, $$ where $B \in \mathbb{R}^{m \times m} \;$ is positive semidefinite matrix, $A ...
2
votes
1answer
37 views

BigPicture Lagrangian, KKT, Duality

I have a question regarding the big-picture in the field: Lagrangian, Duality, KKT, sufficient, necessary conditions. 1) Duality is a concept: “The solution to the dual problem provides a lower ...
0
votes
0answers
27 views

Chek the convexity of a set via affine functions

The set: $\{x| x^TPx \leq (c^Tx)^2, c^Tx \geq 0 \}$ where $P \in S^n_+$(SPD matrices) and $c\in R^n$, is convex, since it is the inverse image of the second-order cone, $\{ (z,t) | z^Tz \leq t^2, ...
0
votes
1answer
15 views

A question on notation in convex optimization

$\mu_E$ is a $4 \times 1$ vector composed of known constants, and $\mu$ is a vector of the same dimension but with unknown variables. Let us say $\mu = (x_1, x_2, x_3, x_4)^T$. What is the meaning ...
0
votes
1answer
41 views

Is this combination of convex functional is still convex?

Let $u$, $v\in C_c^\infty$ and $\Omega\subset \mathbb R^N$ is open bounded, smooth boundary. We also assume that $0\leq v\leq 1$. Define $$ F(u,v):=\int_\Omega |\nabla u|^2v^2dx. $$ Do we have ...
2
votes
2answers
53 views

Convexity of variance

How can I prove the following function is convex? Is variance concave or convex? $$\psi (x)=\left(x_1-\frac{x_1+x_2+x_3}{3}\right)^2+ \left(x_2-\frac{x_1+x_2+x_3}{3}\right)^2+ ...
0
votes
1answer
29 views

Supremum over ellipsoid set

In Boyd's Convex Optimization Textbook, page 157, it is stated: $ \mathrm{sup}\{a_i^T x\; |\; a_i\in\mathcal{E}_i \} = \bar a_i^T x + \mathrm{sup}\{u^T P_i^T x\; |\; \lVert u \rVert_2 \leq 1 \} = ...
1
vote
1answer
39 views

the relation between cardinality, L1-norm and L2-norm of a vector

For every $u\in \mathbb{R}^n$, $\textbf{Card}(u)=q$ implies ${\lVert u \rVert}_1 \leq \sqrt{q} {\lVert u \rVert}_2$ where $\textbf{Card}(u)$ is the number of non-zero element (so the L0-norm). Why ...
1
vote
1answer
77 views

Proof of convexity in a quadratic function

I have the following quadratic objective function (almost variance function); where $f_n, i=1,...,n$ are $n$ function and $\overline f$ is the mean of $f_n$ for all $ i=1,...,n$ $$\min ...
2
votes
1answer
31 views

Reverse engineer a matrix multiplication

Here's a puzzle. I'm looking for ideas on how to research solutions. Given: Secret $n\times 1$ vector $x$ Public $m\times n$ matrix $B$ with $m \ll n$ (assume $B$ has rank $m$) Public product $b = ...
0
votes
0answers
18 views

Given Lagrange Optimization

I would like to maximize $P = 2pr + 3pq + 2rq$ given that $p+q+3r=1 \wedge p,q,r \geq 0 \wedge p,q,r \leq 1.$ I was considering to develop $P$ as a function of three variables and using standard ...
1
vote
0answers
65 views

Shadow prices in assignment problems (and their relationship to Lagrange multipliers of LP-relaxation)

Lagrange multipliers for linear programs can be interpreted as shadow prices. Shadow prices typically represent marginal/differential changes in the objective from a marginal loosening of a given ...
1
vote
0answers
44 views

Maximum over Probabilistic Distribution Functions Space

Suppose $P$ is the set of functions where $p\in P: R^{+2}\to R^+$ and $p(t,s)$ is differentiable in $t$. $\forall t, p(t,\cdot)$ is a probability distribution on the positive axis $s\in [0,\infty)$, ...
2
votes
0answers
24 views

Example 2.13 Conditional Probabilities, Convex Optimization by Stephen Boyd

I am reading Stephen Boyd's Convex Optimization. I can't understand the example below: what is the "convex set of joint probabilities" in this example? what is the convex set $C$ here?
2
votes
2answers
57 views

Convexity of log-determinant

I'm having a difficult time determining if the following function is convex: $$f(X) = \log {\rm det}(X^T A X), $$ where $A \in \mathbb{R}^{r \times r}$ is a symmetric positive definite matrix and $X ...
0
votes
1answer
34 views

Polyhedron = polytope + polyhedral cone, how does it look graphically?

We have learned that a polyhedron is the sum of a polytope and a polyhedral cone, but how do you know this graphically? For example if you're a given polyhedron on paper and you have to determine ...
1
vote
0answers
69 views

How to write lagrangian terms related to only one variable in a semidefinite constraint?

I have a semidefinite problem as follows(which is nonconvex) \begin{alignat}{3} &\min_{x_{un}} \min_{t,H,w} &&t+f( w)\cr &\text{s.t. } &&\begin{bmatrix} K\odot H ...
0
votes
0answers
31 views

How to solve following optimization problem?

$$ \begin{eqnarray} & & \min_{X,E} ||X||_* + \lambda ||E||_{\ell 1}\\ & \text{s.t } & \left\{ \begin{split} & x_{ij} \ge 0 \text{ for all the entries of } X \\ & ...
0
votes
2answers
77 views

Prove $\frac{1}{2} \|y-x\|^2$ is a strongly convex function

Get stuck in proving $f(y)=\frac{1}{2} {||y-x||}^2$ is strongly convex function (Assume $x$ is fixed). My Proof: $y_1$, $y_2$ are two variables. \begin{align} & f(\lambda y_1+(1-\lambda) ...
2
votes
1answer
70 views

Minimize $\mathrm{Tr}((G^TG)^{-1})$

I have been trying to minimize $\mathrm{Tr}((G^TG)^{-1})$ using CVX. I have formulated it in the following SDP structure, using Schur Complement. Here is the formulation: $$\mathbf{minimise} \ \ t ...
0
votes
1answer
33 views

optimization with constrained coefitients of linear combination

problem description: Given is: set of $m$ arbitrary real value $n$-dimensional vectors $\vec{a}_j$; $m$ can be both larger or lower than $n$; so matrix $\matrix{A}$ composed of the vectors ...
0
votes
0answers
19 views

normal cone inclusion and non-symmetric matrix and optimization problem

I have the following normal cone inclusion $$-(A x + b) \in \mathcal{N}_\mathcal{C}(x) \qquad (1)$$ where $\mathcal{N}_\mathcal{C}$ denotes the normal cone to the convex set $\mathcal{C}$ at the ...
1
vote
0answers
19 views

How to deal with a convex constraint

I want to deal with a convex constraint \begin{align} F(P)=P^{H}AP_{0}+P_{0}^{H}AP-P_{0}^{H}AP_{0}\succeq 0 \end{align} where $(\cdot)^{H}$ represents Hermitian transpose, $A$ is a positive definite ...
0
votes
0answers
30 views

Show that $f$(sum of log terms) is convex with Jensen's inequality..

We have the equation \begin{equation} f(\mathbf{x})=\mathbf{c}^T\mathbf{x}-\sum_{i=1}^m\log{(b_i-\mathbf{a}_i^T\mathbf{x})} ,\;\;\; \mathbf{x} \in \mathbb{R}^n \text{ and } m>n \end{equation} ...
0
votes
0answers
14 views

How to optimize this? Can Lagrange be used here?

$g_i = argmax_{\alpha_i \in \mathbb{R}} \space\space F(\alpha),$ subject to: $0 <= \alpha_i <= C$ where: 1- $F(\alpha) = \sum_i \alpha_i - {1\over2}\sum_i \sum_j \alpha_i \alpha_j x_i x_j ...
0
votes
0answers
11 views

Determining Euler-Lagrange equations for a nonsmooth functional

Is there any good resource for understanding how to derive the EL equations for non-smooth problems? In particular, I would like to get them for: $\mathcal{J}(u,v)=\iint_{\Omega} \sqrt{u_x^2 + u_y^2 ...
0
votes
0answers
11 views

Affine hull of a linearly constrained set (convex polytope)

For any $A \in \{0,1\}^{m \times n}$ and $r \in \mathbb{R}^m_{>0}$ consider the set $S := \{x \in \mathbb{R}^n_{\geq 0} \ | \ A x = r\}$ of non-negative solutions to the linear system $Ax - r = 0$. ...
1
vote
1answer
57 views

Armijo rule intuition and implementation

I am minimizing a convex function $f(x,y)$ using the steepest descent method: $$\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma \nabla F(\mathbf{x}_n),\ n \ge 0$$ My function is defined over a specific domain ...
0
votes
1answer
18 views

Complementary slackness with Lagrange Multipliers in Convex Optimization

I was perusing the wiki article on the topic of this post https://en.wikipedia.org/wiki/Convex_optimization In particular the section on the Lagrange multipliers: I would appreciate more insight ...
1
vote
1answer
26 views

Generalized Farkas Lemma

Farkas lemma can be stated as follow: If for all $\mu$ such that $\mu^T\cdot a_i \geq 0$ implies that $\mu^T\cdot b \geq 0$ then $b=\sum \lambda_i a_i$ with $\lambda_i \geq 0$ I need a generalized ...
0
votes
2answers
49 views

Steepest descent for a function defined over a specific domain [duplicate]

I am trying to minimize a convex function using the steepest descent method. The function is defined over the domain $D = \{(x, y) \in R^2 : 2x^2+y^2 < 10\}$. The gradient descent iterations: ...
0
votes
0answers
42 views

Recall that in the context of Fenchel–Rockafellar duality, the primal problem is defined by

Let X and Y be two Hilbert spaces. Let $f : X \rightarrow ]-\infty, +\infty]$ be convex and lower semicontinuous, let $A : X \rightarrow Y$ be linear, and let $g: Y \rightarrow ]-\infty,+\infty]$ be ...
0
votes
1answer
34 views

Let $a_1,\ldots,a_m$ be elements of $\mathbb{R}^n.$ Then the convex cone $K_{\Omega}$

I am having a problem with one aspect of the following proof I came across in "An Easy Path to Convex Analysis and Applications" by Mordukhovich and Nam. It is Proposition 3.9 and it is the line ...
1
vote
1answer
56 views

Min problem by using Lagrange method

$$\min x^2+y^2 $$ $$\text{s.t.}\ \ (x-2)^2+(y-3)^2\le 4 \ \ \ \text{and} \ \ \ x^2=4y$$ Please explicitly solve this question by using Lagrange multiplier method. I accept $(x-2)^2+(y-3)^2=4$ ...
0
votes
0answers
32 views

Find the distance between two convex sets

Let's say that ||.|| is an Euclidian norm in $R^3$ and we have two sets in $R^3$ defined by inequalities: $Y = \{y| f(y)<a\}, Z = \{ z| g(z)<b \} $ Let's say that $f$ and $g$ are convex and ...
0
votes
0answers
5 views

Prove or disprove a monotonicity property of a certain convex optimization problem

Let $R = (r_{ij})$ be an $n\times k$ real matrix with only positive entries, and consider the convex optimization problem $\max f(x) = \sum_{i=1}^n \log \sum_{j=1}^k r_{ij} x_j$ such that ...
0
votes
0answers
19 views

(Convex) reformulation of a nonlinear program

Consider the following program: \begin{eqnarray*} \min_{\mathrm x}\sum_{i=1}^{n}{\sum_{j=1}^{n}{\big(x_i(Sx)_i-x_j(Sx)_j\big)^2}}\\ \mathrm{subject\; to}\quad \sum_{i=1}^{n}{x_i}=1 \\ x_i\geq 0 ...
0
votes
0answers
61 views

Explain why the function $f(x)=\frac{1}{2}(x-d)^2+\alpha|x|$ is strictly convex.

Let $d\in\mathbb{R}$ and $\alpha>0$ be given. (i) Explain why the function $f(x)=\dfrac{1}{2}(x-d)^2+\alpha|x|$ is strictly convex. (ii) verify that \begin{equation} ...
1
vote
1answer
23 views

Smoothness of total variation norm with weight

Let me write total variation norm $$ \|u\|_{TV} = \max_{z\in Q} \langle z, Du\rangle, $$ where $Q$ is the unit ball in $\mathbb R^2$ and $D$ is the corresponding gradient matrix. I can smooth TV by ...
1
vote
1answer
49 views

What is the difference between min and max constraint problems?

For example, let's consider these two min max optimization questions (1) $$\max \ \ g(x,y)=xy$$ $$ \text{s.t. } x^2+y^2=1$$ (2) $$\min \ \ g(x,y)=xy$$ $$ \text{s.t. } x^2+y^2=1$$ Solution: By ...
3
votes
0answers
47 views

Variational characterization of nuclear norm

The nuclear norm $||\cdot||_{*}$ of a matrix is defined as the sum of its singular values. Working from the result at the bottom of this blog post, we have, for a matrix $\mathbf{X}$ and its ...
3
votes
1answer
36 views

Constrained nonlinear optimization

I am wondering what is the easiest/best way to find the values of $x_i$ that maximize the expression $\sum_{i=1}^N a_i \ln (x_i)$ under the constraints $\sum_{i=1}^Nx_i = 1$ and $ 0\leq x_i \leq 1$ ...
0
votes
0answers
48 views

Show that $f + g$ is still strictly convex.

Let $d \in X$ and set $$f: X \to \mathbb{R}: x \mapsto \left(\frac{1}{2}\right) \parallel x-d \parallel^2.$$ Use (*) to show that $f$ is strictly convex. Now let $g$ be any convex function. Show that ...
3
votes
0answers
52 views

How to prove the matrix fractional function is convex by definition

It is well known that the matrix fractional function $f(\mathbf{w},\boldsymbol{\Omega})=\mathbf{w}^T\boldsymbol{\Omega}^{-1}\mathbf{w}$ is jointly convex with respect to $\mathbf{w}$ and ...