Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

2
votes
4answers
86 views

Minimization on compact region

I need to solve the minimization problem $$\begin{matrix} \min & x^2 + 2y^2 + 3z^2 \\ subject\;to & x^2 + y^2 + z^2 =1\\ \; & x+y+z=0 \end{matrix}$$ I was trying to verify the first ...
0
votes
0answers
10 views

Prove that if $e \in \left ( S\to \overline S \right )$ when $\left ( S, \overline S \right )$ is a min-cut, then $f(e) = c(e)$

Given a min-cut $\left( S, \overline S \right )$, we define $\left ( S\to \overline S\right ) =\{\left (u\to v\right )|u \in S, v\in \overline S\}$ and $\left ( \overline S \to S \right )$ similarly. ...
0
votes
0answers
13 views

For which values of $c_1, c_2$ and $c_3$ is (1, 2, -2) a local minimum

Consider the problem $$\left\{\begin{matrix} \min & x^2 -2xy + 2xz +y^2 + 4yz + z^2 + c_1x + c_2y + c_3z \\ s.t & g(x,y,z)=-x^2 -4xy - 4xz -2y^2 -4yz - 2z^2 + x -y+z+4 =0 \\ \; & ...
0
votes
1answer
50 views

Minimal area of triangle

We have the points $A(2, 3-m), B(m+2, -1)$ and $C(m, 2-m)$. Where $m$ is a real number. Find $m$ for which the area of triangle $ABC$ is minimal. So I've tried to find the equation of line $BC$(the ...
0
votes
1answer
12 views

Constrained Optimization: $\min x_1$

Consider the problem $$\left\{\begin{matrix}\min & x_1 \\ s.t & x_2 \geq 0 \\ \; & x_2 \leq x_1^3 \end{matrix}\right.$$ It is asked to find the minimum and show why this does not satisfy ...
0
votes
0answers
26 views

Convex envelopes of bivariate functions

In order to convexify my nonlinear non-convex program I need convex envelopes for the function $(x/y)^2$, both x,y are positive. I am only aware of the convex envelopes of the type $xy$ from here ...
6
votes
2answers
141 views

Find the minimum value of $A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}$

Let $a, b$ and $c$ three positive real numbers such that $a+b+c=3$. Find the minimum value of $$A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}.$$ Here is my attempt. By symmetry we can assume that ...
1
vote
1answer
39 views

Optimizing a function of a matrix

Let \begin{equation} \begin{aligned} W= & \underset{X}{\mathrm{maximize}} & & \log \left|X + K_1\right|- \alpha \log \left|X + K_2\right|\\ & \mathrm{subject \; to} & & 0 ...
0
votes
0answers
25 views

Will the result of this maximization problem be the same for the two considered cases?

Suppose I have $2$ options: option1 and option2. For each option we associate a quantity $q$ that changes each time $t$, namely $q_1(t)$ and $q_2(t)$. Let $\mathbf{q}=(q_1(t),q_2(t))$. The different ...
0
votes
0answers
6 views

Gomory's cut typical running time until the constraint is fractional

I was considering the following problem. Say we are given an linear programming problem $$ \max c^Tx $$ $$ Ax \le b $$ $$ x \ge 0$$ Where instead I consider $i^{th}$ the optimal solution $X_i$ of ...
0
votes
0answers
9 views

what is the dual problem of finding chebyshev's center?

let $a_j$ $(j=1,...,m)$ be a set of points in $R^2$. The problem of finding Chebyshev's center is: min r s.t. $norm(x-a_j)<=r$ $(j=1,...,m)$ Where r is the maximal radius and x is the center ...
0
votes
1answer
1k views

How do I construct the Jacobian for use in a Levenberg-Marquardt algorithm.

I am working on a 3D reconstruction system and I am looking to use a Levenberg-marquardt algorithm to do bundle adjustment. I am not too sure about how LM works and what it requires. The model I am ...
0
votes
2answers
37 views

Optimization Problem: Fence with adjacent sides rather than opposing sides

I'm unsure if I got the following right on a test I just took: A farmer wants to build a rectangular fence using both wood and metal and wants adjacent sides to be of the same material. Metal costs ...
0
votes
0answers
13 views

Convex signal reconstruction for convex generator function?

Let $f : \mathbb{R} \mapsto \mathbb{R}$ be a convex (not affine) function and suppose that $y = f(x)$. We want to reconstruct the input $x$ for a given $y$, and the standard approach would be to ...
4
votes
1answer
358 views

Derivation of Euler-Lagrange equation

Here is a simple (probably trivial) step in the derivation of the Euler-Lagrange equation. If we denote $Y(x) = y(x) + \epsilon \eta(x) $, I want to know why is $\dfrac{\partial ...
1
vote
0answers
19 views

Is there only one set of KKT conditions for a given optimization problem?

Consider an optimization problem $$ \begin{align} \max_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad & g_i(x) \le0,\,i=1,\ldots,m\\ \quad & h_j(x)=0,\,j=1,\ldots,l\\ \end{align} $$ ...
2
votes
1answer
131 views

If $a,b,c>0, a+b+c=3$, minimize $\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{3-c^3}{c}$ [duplicate]

Let $a,b,c$ be positive real numbers such that $a+b+c=3$. Find the minimum value of the expression $A= \frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{3-c^3}{c}$ I tried solving it, but I got nothing
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 ...
0
votes
0answers
11 views

How to optimize a generalized trace problem in dimensionality reduction

I know how to solve this problem in dimensionality reduction. $argmax_{X}$ $Trace[XLX^T]$ with $XX^T=I$ ,where $L$ is symmetric, $X$ is unitary, and $I$ is identity matrix. But I'd like to know how ...
1
vote
0answers
13 views

closed form solution to best invertible matrix which minimizes product

Let $U, X \in \mathbb{R}^{n_1 \times r}$ and let $V, Y \in \mathbb{R}^{n_2 \times r}$. Consider the optimization problem $$ \begin{align*} \min_{A, B, \Sigma \in \mathbb{R}^{r \times r}} \left\{ \| ...
-1
votes
2answers
18 views

Determine vector which maximizes the given function

Determine vector x $\in R^3$ with $\|x\|^2=x^Tx=1$ which maximizes the function below $$ f(x) = 2x_1^2 +2x_2^2-x_3^2+2x_1x_2$$ If someone can show me how to tackle this problem then I have at least ...
0
votes
1answer
39 views

Minimization involving equality constraints

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \underset{\mathbf{x},\mathbf{y}}{\text{minimize}} \hspace{4mm} \big(\left( \mathbf{y}^T ...
-1
votes
0answers
10 views

How to solve “and-or” constrained optimization problems in MATLAB? [closed]

The typical constrained optimization problem that I am facing is: minimize ||y-z|| (y is a given vector of say, length 10) subject to the following constraints on z: (1) z1 <= max(z2,z3,z6), (2) z3 ...
2
votes
0answers
156 views

Up and Downtime Constraints - An Optimization Problem

I am working on a project and have run into a roadblock, any help will be greatly appreciated: We are trying to minimize cost of running a series of generators. Each generator has a unique cost of ...
2
votes
1answer
15 views

Proving that a local maximum of a given bounded function is global.

I am studying a certain maximisation problem (coming from some sort of likelyhood estimations); after a number of generalisations I need to examine $$f(x_1, x_2,y) = a_1\ln x_1 +a_2 \ln x_2 + \ln y - ...
2
votes
1answer
28 views

optimization network models

This is a question from Wane Winston 's Book. I don't understand how to do this. I tried to do it this way but it doesn't seem to work. Let $C_{ij}$ be the cost of using box of i $ i>=j$ Then ...
0
votes
1answer
41 views

Optimization problem in flight scheduling

I found this question here The question is I wrote the LP problem as this: Let $x_{ij}$ be the maximum no.of flights between city i and city j. Let $a_0$ be the artificial link and $x_0$ be the ...
0
votes
1answer
15 views

How to optimally cut kitchen worktops (countertops) from slabs of material

Given a number N of rectangular kitchen worktops, of variable dimensions to be cut from slabs of material of fixed dimensions Determine an optimal fit to minimise wastage and number of slabs used. ...
5
votes
1answer
398 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
0
votes
2answers
56 views

Calculus,Lagrange Multipliers

Can anybody help me with the following question, Use the method of Lagrange multipliers to find $\max$ and $\min$ values for $f(x,y,z)=x^2+y^2+z^2$ subject to the constraint $4x^2 + y^2 + 9z^2=36$. ...
0
votes
1answer
22 views

Unique minimizer of $\|x\|_{\mathcal A}$ subject to $\Phi x=\Phi x_0$

I'm trying to understand the proof of Lemma 2.3 of the paper Simple bounds for recovering low-complexity models. The authors want to find bounds on the numbers of rows $m$ of $\Phi$ to ensure that ...
1
vote
1answer
24 views

Multivariable optimization- Nature of critical points when det of hessian matrix = 0

I'm struggling a bit with my multivariable optimization. Assuming the determinant of the hessian matrix ≠ 0 I have no issue, though when the det = 0 I get stumped. Example- $$f(x,y)=x^4+y^4-(x+y)^2$$ ...
1
vote
1answer
27 views

Multivariable Linear Optimisation

I've been stewing on a problem for a week or so. I'm trying to work out an optimisation problem. Similar to the basic linear optimisation problems we used to look at with two variables, but I'm ...
1
vote
1answer
29 views

The optimal function value in linear programming has analytic solution

Consider the following linear programming problem: $\min c'x$ subject to $Ax=b$ and $x\geq0$, where $A$ is $m\times n$ with rank$A=m$. The dual is $\max -b'v$ subject to $A'v+c=\lambda$ and ...
1
vote
3answers
76 views

Maximize the following sum

Let $a, b, c, d, e$ be nonnegative integers such that $625a + 250b + 100c + 40d + 16e = 15^3$ . What is the maximum possible value of $a + b + c + d + e$? Quick arithmetic gives: ...
2
votes
1answer
1k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
2
votes
2answers
44 views

How to determine a function of a matrix is increasing or decreasing

We know that the derivative of a function can be used to determine whether the function is increasing or decreasing on any intervals in its domain. If $f'(x) > 0 $ at certain interval I, then the ...
0
votes
1answer
25 views

How do I show that the set $S$ in $\mathbb R^3$ defined by linear inequalities is a $3$-simplex?

Consider the set $S$ in $\mathbb R^3$ defined by the inequalities: $x+y+z \ge 1$ $-x+y+z \le 1$ $x-y+z \le 1$ $x+y-z \le 1$ How can I show that $S$ is a $3$-simplex ? (Convex hull of $3 + 1$ ...
2
votes
5answers
450 views

Find the maximum possible area of a certain right triangle

I want to find the maximum possible area of a right triangle with hypotenuse $=10$. My approach so far: let $x,y$ be the lengths of the two sides adjacent to the right angle; then $$100=x^2+y^2$$ ...
1
vote
1answer
21 views

Complexity of finding M nodes in a graph to maximize the pairwise minimum distance between nodes

I want to know the complexity of finding a set of M nodes, $\{U_1,\dots,U_M\}$, in a given graph $G$, to maximize $d(U_i,U_j)$ over all pairs $i\neq j$, where $d(\cdot,\cdot)$ is the length of the ...
0
votes
1answer
23 views

Functional Lifting in Optimisation - Reference Request

I'm looking to learn about the use of (functional) lifting applied to a non-convex optimisation problem to give a (larger) convex problem. Unfortunately, I'm having a great deal of trouble finding ...
1
vote
0answers
46 views

Minimizing the max function

Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in ...
0
votes
0answers
20 views

strengths and weaknesses of analytical method

I was wondering if anyone could suggest any books or paper that explain/discuss the advantages and drawbacks of analytical methods for optimization. Also, if we have a convex objective function ...
0
votes
0answers
34 views

What does $\frac{d^k h}{dx^k}$ mean in the context of vectors and regularization in machine learning?

I was watching a machine learning videos from the caltech course CS 156 and they have a slide where they talk about how radial basis functions (RBFs) can be derived from the following variational ...
1
vote
1answer
30 views

Find min/max values of $f(x,y)=x^3-y^3+3xy$ in the set $K=[0,4]\times[-4,0]$

Find the biggest and the smallest values of the function $f(x,y)=x^3-y^3+3xy$ in the set $K=[0,4]\times[-4,0]$. So using partial derivatives we find that the critical points are $(0,0)$ and $(1,-1)$. ...
1
vote
3answers
34 views

Finding extrema.

Find the minimum distance between point $M(0,-2)$ and points $(x,y)$ such that: $y=\frac{16}{\sqrt{3}\,x^{3}}-2$ for $x>0$ . I used the formula for distance between two points in a plane to get: ...
3
votes
2answers
119 views

finding maximum of a function on a closed set

I need to find the maximum of the function $\ f(x,y,z) = y $ on the following closed set : $\ y^2+x^2 + z^2 = 3 $ $\ y+ x + z=1$ But I don't have a clue on how to do it ... Trivially ...
0
votes
0answers
31 views

Expected probability maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like $$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$ Here $f(k,x)$ is actually a probability coming from a ...
0
votes
0answers
20 views

Invex function? How can I show?

Let $\mathbb{S}^m_+$ and $\mathbb{M}^{(m,n)}$, respectively, be the closed cone of positive semidefinite matrices and space of $m\times n$-dimensional matrices. Define function $F$ as ...
0
votes
1answer
98 views

How do I show that $B$ has an infinite number of extreme points, but no faces (sides) of dimension $1$ or $2$?

Let $B = \{ (x,y,z) \in \mathbb R^3 \mid x^2 + y^2 + z^2 \le 1\}$. How do I show that $B$ has an infinite number of extreme points, but no faces (sides) of dimension $1$ or $2$ ? I've been thinking ...