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

learn more… | top users | synonyms

5
votes
0answers
87 views

Optimization of approximate functions using varying objective function

Let $g(\theta;x)$ and $f(\theta;x)$ be two convex functions such that $g$ asymptotically approximates $f$: $g(\theta;x)\approx f(\theta;x)$, specifically: $$ |g(\theta;x)-f(\theta;x)| \leq ...
0
votes
1answer
30 views

On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?

Please refer to Boyd et al.'s convergence analysis of ADMM (Chapter 3 and Appendix A). My question is: Why do we need $f$ and $g$ to be convex? I don't see the need of this assumption. If the ...
1
vote
1answer
35 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
0
votes
0answers
34 views

How to deal with an $xy\le 1$ constraint?

I have to solve the following optimization problem: $$ \begin{align*} \min_{x,y} &\{-x-y\} \\ \text{such that} \\ y &\ge 3 \\ y &\le 30 \\ x &\ge 0 \\ xy &\le 1 \\ \end{align*} $$ ...
0
votes
1answer
20 views

Convexify $x\le a+by^2$

I have the following non-convex constraint: $$ x\le a+by^2\quad\text{where}\quad a,b>0,\,y\in[0,y_{max}]\text{ and }a\approx by_{max}^2 $$ On a drawing, it looks something like this: The above ...
0
votes
0answers
20 views

Coordinate descent with equality and inequality constraints

I have an intuitive understanding of why the simple method of coordinate descent does not work with linearly coupled constraints such as; $$\min_x\sum_if_i(x_i)$$ $$s.t.$$ $$Ax=b$$ If we try to ...
0
votes
0answers
9 views

How to compute norm bound error in robust approximation

I am reading convex optimization, and I am little confused about the following two prolems in norm bound error of robust approximation. How to compute $\{\|\bar{A}X-b+Ux\| | \|U\|\le a\}$ ? For the ...
0
votes
0answers
11 views

reference for convex function results

Here is a simple property of a concave function from $\mathbb{R}$ to $\mathbb{R}$, Given $x,x'\in \mathbb{R}$ with $x'>x$, if $\exists \kappa'\in (0,1)$ such that ...
0
votes
1answer
25 views

Subgradients of non-convex functions

In these notes (section 2.3), it is stated that: A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial ...
-2
votes
0answers
47 views

Please help… is this a convex function?

Kindly help me. What can we say about the function $f$ shown in below? is it convex or non-convex over the variables $x_1, x_2,.., x_{n+1}, y_1,y_2$? \begin{align} f(x_1, x_2,.., x_{n+1}, ...
1
vote
1answer
59 views

Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 ...
2
votes
1answer
29 views

Use of binary variables in LP problems

I can't figure out how to write the following condition to an LP. I have four nonnegative variables: $X_A$, $X_B$, $X_C$, and $X_D$. The condition which should be satisfied is this: If $X_A$ and ...
0
votes
0answers
14 views

Impact of removing active constraints in convex optimization

In active set methods for non negative least squares, we remove variables from the passive set to active set if the least squares solution gives negative values on those variables. What's the impact ...
1
vote
1answer
14 views

Chebyshev's approximation understanding

I am reading Boyd's book on convex optimization. Could you assisst me in understanding what this expression means: $$\text{minimize} \ \ \text{max}_{i=1,...,k}|a_i^Tx-b_i|$$ This is what I think ...
0
votes
0answers
25 views

Is the minimum point of a strictly convex function stable?

This is a problem I figured out after seeing the definition of minimum stable point and I think the following tense is true: Let $f(x)$ be a strictly convex function whose minimum values is ...
1
vote
0answers
58 views

When does a variable goes out with the revised Simplex method?

Let be the following linear program. \begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 ...
3
votes
2answers
76 views

Can you prove that this function is convex? $\sqrt{2x_1^2+3x_2^2+x_3^2+4x_1x_2+7} + (x_1^2+x_2^2+x_3^2+1)^2$.

My analysis: The second term can be proven to be convex as follows. It is basically a composition of norm with an affine transformation to the power of four: $(x_1^2+x_2^2+x_3^2+1)^2 = \|(x_1^2, ...
0
votes
0answers
11 views

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
0
votes
0answers
31 views

Residual norm of active set method in non negative least squares

I am having trouble with understanding one of the statements in active set methods done for non negative least squares given in Book written by Lawson. The quadratic problem can be written as ...
1
vote
0answers
12 views

Variant of conjugate function: $V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$

Consider one variant of conjugate function: $$V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$$ You can think $s$ as a linear functional. If I do the following steps: ...
0
votes
0answers
28 views

How to form a dual problem in convex optimization (in a broad view)

After reading some papers, this problem confuses me. There are different forms of dual problem to the primal problem: $$\underset{x}\min \ \ f(x)$$ where $f(x)$ is a convex function. By ...
0
votes
1answer
31 views

characteristic cone of polyhedral

Let $$Q=\{x ∶ Ax ≤ b \}≠∅$$ If $Q = P + C$, where $P$ is a polytope and $C$ is a polyhedral cone, prove that $$\{y|Ay ≤ 0\} = \{y|x + y ∈ Q, ∀ x ∈ Q\}$$ The cone $C = \{y|Ay ≤ 0\}$ is ...
0
votes
2answers
57 views

$\big\langle\nabla f(x)-\nabla f(y),\,(x-y)\big\rangle\ge m\,\left\| x-y\right\|^2,\;m>0\;$ for strictly and strong convex function [on hold]

Prove that $\,\big\langle\nabla f(x) - \nabla f(y),\, (x-y)\big\rangle \geq m\,\left\lVert x-y\right\rVert^2, \;\,m > 0\,$ for strong convex function $f: \mathbb R^n \to\mathbb R$. Is it true ...
1
vote
0answers
24 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
1
vote
0answers
83 views

Some intuition on the support function of a convex set

I have some doubts on the interpretation and properties of the support function of a convex subset of $\mathbb{R}^d$. (1)Let $K$ be a convex set in $\mathbb{R}^d$. (2) The support function of $K$ is ...
1
vote
2answers
30 views

Is a convex cone a convex polyhedron?

Say that I have a convex cone $C=\{t|Ax = t, x\geq 0\}$. where $x\in R^n$, and $t\in R^m$, $A\in R^m\times R^n$. Can I say that this is a convex polyhedron? and why? EDIT: Just in order to avoid ...
0
votes
0answers
27 views

Is this the correct proximal operator?

I'm supposed implementing certain optimization algorithms (ISTA, FISTA) to minimize: $$\frac12 ||Ax-(Ax_0+z)||_2^2 + \lambda ||x||_1.$$ $A$ is a matrix, $x$ is a vector, $z$ is some noise filled with ...
0
votes
1answer
35 views

Convex optimization: Piece-wise, quadratic objective

This question is about convex optimization with a convex objective function, which is defined piecewise. We have two functions, a concave function A(x) and a strictly convex, increasing function B(x), ...
0
votes
2answers
30 views

$\max 2x_1 +x_2$ unbounded or unfeasible with the constraint $sx_1 +tx_2\le-1$

\begin{cases} \max & 2x_1 &{}+x_2\\ & sx_1 &{}+tx_2&\le-1\\ & x_1,x_2&&\ge 0 \end{cases} Find out when this program is not feasible, bounded Feasibility It ...
0
votes
1answer
26 views

Show convexity of $f(x,y,z)= x^2+y^2+z^2+xyz$

Let $f(x,y,z)= x^2+y^2+z^2+xyz$. Show that $f$ is convex on $\Omega=${$(x,y,z)\in R^3 : x^2+y^2+z^2<\frac{5}{2}$}. To prove it, I want to show that $\nabla^2f(x,y,z)$ is positive definite. I ...
0
votes
0answers
13 views

Is the sum of a bivariate convex function Schur convex?

A well known fact is: Let $f(x)$ be a convex function. Then $g(\vec{x})=\sum_{i=1}^N f(x_i)$ is Schur convex in $\vec{x}$. Supose $f(\vec{z})$ is a convex function of $\vec{z}=(x,y)$. How to ...
1
vote
1answer
33 views

Choosing $\lambda$ to yield sparse solution

I'm supposed implementing certain optimization algorithms (ISTA, FISTA) to minimize: $$\frac12 ||Ax-(Ax_0+z)||_2^2 + \lambda ||x||_1.$$ $A$ is a matrix, $x$ is a vector, $z$ is some noise filled with ...
0
votes
0answers
37 views

Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
-1
votes
1answer
23 views

Where does the duality comes from in linear programing and can we get the optimal basis from it?

$$\begin{cases} \max & c^Tx\\ & Ax\le b\\ & x\ge 0 \end{cases}\Leftrightarrow \begin{cases} \min & y^Tb\\ & y^TA\ge c^T\\ & y^T\ge 0 \end{cases}$$ Then we come to the ...
0
votes
0answers
9 views

Finding the lower bound of a linear program with the duality method

The issue I have some difficulties understanding the lower bound of a program when applying the duality method. It seems that it comes from $$c^T\underbrace{\le}_{x\ge 0\\y^TA\ge c^T} ...
0
votes
0answers
21 views

Can the constrained optimization problem (1) be transformed into the unconstrained form (2)

(1) \begin{equation}\label{constrained} \begin{array}{cl} \arg \min \limits_{\mathcal{C}_k} & \text{rank}(\mathcal{C}_k)\\ \mathrm{s.t.} & \mathcal{E}(\phi_{j}^{k})\le \epsilon ...
0
votes
0answers
20 views

general framework for proof of convexity in least square problem

Let $f(x_i,\theta) : X \times \Theta \rightarrow Z$ be a parametric function with parameter $\theta$ that we wish to fit to set of samples $S =\{(x_i,z_i)\}_{i=1}^N$, where $(x_i, z_i) \in X \times ...
3
votes
1answer
47 views

Convex set: extreme points and distance to the origin

I'm fairly sure the following is true, although I wouldn't mind being proven wrong. If true, I would like to see an elegant proof, as my attempts are kind of messy. Let $K\subset\mathbb R^2$ be a ...
0
votes
0answers
13 views

Equality constraints into inequalities constraints through elimination

I read here in Section 10.1.2 of this text that a way to eliminate linear equality constraints of the type $$Ax = b$$ in convex optimization problems is to parameterize the related affine space as a ...
0
votes
0answers
26 views

Are the constrained optimization problem equal to the unconstrained one?

(1) \begin{equation}\label{constrained} \begin{array}{cl} \arg \min \limits_{x} & \|Ax-b\|_2\\ \mathrm{s.t.} & \|x\|_1\le \epsilon \end{array} \end{equation} (2) ...
1
vote
0answers
29 views

Why the trace norm of a tensor is a good approximation to its rank?

In many literature, they use the trace norm of a tensor to approximate its rank, which is defined as follows: $$\|\mathcal{X}\|_{\ast}:=\sum_{i=1}^{n}\alpha_i\|X_{(i)}\|_{\ast}$$ where ${\alpha_i}'s$ ...
0
votes
0answers
8 views

Lower bound of averaging gradient method (Prof. Yurii Nesterov's paper)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The last inequality confuses me: (p.231) Note: 1. The ...
2
votes
0answers
25 views

How to efficiently solve a quadratic program repeatedly?

I have a quadratic problem, \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} ($Q$ is semidefinite) which I want to solve repeatedly, with the slight change of p and Q, ...
0
votes
1answer
25 views

A ratio of two convex functions with different minima cannot be monotone. Proof?

Let $\lambda(x)=\frac{f(x)}{g(x)}$ where $f(x)$ is a differentiable function minimized at $x=x_1$ and $g(x)$ is a differentiable function minimized at $x=x_2\neq x_1$. How can I show that $\lambda(x)$ ...
2
votes
1answer
39 views

What aspects of convex optimization are used in artificial intelligence, if any?

I work on convex optimization with Stephen Boyd's book. As an example, support vector machines are mentioned as an application of separating hyperplanes theorem. I am wondering if there is any other ...
0
votes
0answers
6 views

Who proved that the equilibrium problem is equivalent to a monotone inclusion problem?

I'm looking for the original reference where it was proved that given a subset $X$ of a space $E$ and a function $f:E \times E \mapsto \mathbb{R}$, the equilibrium problem of finding $x \in X$ such ...
1
vote
0answers
22 views

Expressing $\forall$ in linear programing

I'm doing a linear program to a game and I don't know how to express $\forall$ in linear programing (or if I had the right intuition to do it). Here is the problem: I have several vessels that are ...
0
votes
1answer
33 views

Show non-convexity of a function with vector input

How does one go about proving non-convexity of the function d? $$ d(v) = 1/2*||F(v)- p||^2 $$ $$ F(v)=\sum_{i=1}^n l_i*\begin{pmatrix} cos(\sum_{j=1}^i v_j) \\ sin(\sum_{j=1}^i v_j \end{pmatrix} $$ ...
0
votes
1answer
30 views

Gradient and Hessian of a function defined in terms of matrix inverse

Let $\mathbf{I}_m$ be the $m$-dimensional identity matrix and $\mathbf{0}_m$ be the $m$-dimensional zero matrix. The matrix $D(\mathbb{x})$, where $\mathbb{x} = (x_1, \dots, x_n)^T$, is defined as: $$ ...
0
votes
0answers
24 views

Subdifferential optimality conditions

I need help with subdifferential optimality. Let $f(x_1, x_2)=x_1^2 + x_2^2 + |x_1 -x_2 - y|$. Find: \begin{align} \min_{x_1, x_2} f(x_1, x_2) \end{align} This is convex, so must have unique ...