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)

1
vote
0answers
23 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} $$ ...
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
16 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 ...
2
votes
1answer
134 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
0
votes
0answers
26 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 ...
2
votes
1answer
16 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 - ...
0
votes
0answers
25 views

Approximate inverse (or fast optimization) of non-linear least squares problem

Problem Statement Let ${\bf x}\in\mathbb{R}^N$ and ${\bf W}\in\mathbb{R}^{K\times N}$, ${\bf V}\in\mathbb{R}^{N\times K}$. We define $${\bf y} = f({\bf x}) = [{\bf V}[{\bf Wx}]_+]_+$$ where $[.]_+ = ...
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. ...
0
votes
0answers
29 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 ...
1
vote
1answer
30 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$$ ...
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 ...
2
votes
1answer
199 views

Regarding Nesterov's smooth minimization

I am currently studying this Nesterov's paper for project purposes, and I am trying to figure out how the smoothing and the minimization algorithm works I have tried looking at the example ...
0
votes
1answer
41 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
vote
1answer
30 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
1answer
40 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 ...
1
vote
3answers
89 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
2answers
50 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 ...
2
votes
5answers
462 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$$ ...
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
48 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
1answer
55 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 ...
2
votes
1answer
30 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
0answers
23 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
35 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
3answers
36 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: ...
1
vote
1answer
22 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 ...
1
vote
1answer
31 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)$. ...
0
votes
0answers
32 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
26 views

Estimate Beam and Ball Problem System Parameters

I'm trying to estimate the parameters of beam and ball problem model. In the problem we have output as ball position and input as gear rotation angle. The issue that i want to ask is that our ...
0
votes
3answers
39 views

What algorithm will maximize utility when assigning of students to practicum locations

I have the following problem: Students from a class of 150 are beginning practicum training. Students have the option of either staying in an urban centre for their practicum, or optionally, they ...
0
votes
1answer
48 views

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove $(1-\lambda)x + \lambda y \in S$ for $x=\lambda'y$, $\lambda' < 0$.

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. I've verified that $x,y \in S$ implies $(1-\lambda)x + \lambda y \in S$ when $x,y$ are linearly independent using Pythagoras and when ...
0
votes
1answer
18 views

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these.

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these. I want to compute all the extreme points of the set $P$ (polyhedron) in $\mathbb R^3$ ...
-4
votes
4answers
120 views

Maximum and minimum of $y = x^4 - 8x^2 + 3$ for $x \in [ -1 , 2 ]$ [closed]

I have an assignment for tomorrow and I am struggling with this. How can we find the maximum and minimum of $y = x^4 - 8x^2 + 3$ for $x \in [ -1 , 2 ]$?
1
vote
1answer
28 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
0answers
19 views

Max-flow-min-cut using LP duality

https://www.cs.oberlin.edu/~asharp/cs365/papers/Approximation-ch12.pdf is a chapter from Vazirani that discusses max cut-min flow using LP duality. The binary min-cut problem is: \begin{align} ...
1
vote
1answer
43 views

Optimizing trigonometric equation

I've come across a problem from an old calculus textbook which goes like A tool shed, $250\space cm$ high and $100\space cm$ deep is build against a wall. Calculate the shortest ladder length that ...
0
votes
1answer
26 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$ ...
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 ...
0
votes
2answers
24 views

Resolve this system:

Im tried to resolve this problem: $$\max\quad f\left( x,y \right) =xy\quad \text{s.a}\quad \begin{cases} x^2 +y^2+z^2 -1=0 \\ x+y+z=0 \end{cases}$$ Well, i form the lagrangian and the respective ...
0
votes
2answers
29 views

Minimum curve for the distance between two points at the plane

The problem is to determine the curve y=y(x) in the plane, the lenght of which is given by the functional: \begin{equation} I(y)=\int_{x_1}^{x_2}\sqrt{1+(y')^2}dx=\int_{x_1}^{x_2}F(x,y,y')dx ...
0
votes
1answer
22 views

For given mean $\mu$ of random variable X in [0,1], what is the probability distribution function $p(X)$ that makes $VAR(X)$ maximum?

Given the conditions $\int_{0}^{1} p(x)dx=1$, $\int_{0}^{1} xp(x)dx=\mu$ and $p(x)\ge0$ for $\forall x \in [0,1]$, What probability distribution function $p(x)$ makes $Var(X)$=$\int_{0}^{1} ...
1
vote
0answers
34 views

Determining the optimal cost through dynamic programming.

There are $n$ houses numbered $\{1, 2, 3, \dots, n\}$. The cost of laying a cable that serves houses $j, j+1, j+2, \dots, j+k $ is $f (j, k)$. One cable can serve a maximum of 10 houses. The ...
0
votes
1answer
17 views

reformulating an integer quadratic problem into a linear integer problem

I am trying to solve an optimization problem, in order to find an optimal runtime schedule for a machine. It involves one boolean variable $x_{t} \in \mathbb{\{0,1\}}$, that describes whetever the ...
1
vote
1answer
21 views

A clarification regarding dynamic programming.

This is a question regarding dynamic programming. The document to which I am referring is this (pg 325). It says that $$v_n(s_n)=\text{Min}\{t_n(s_n)+v_{n-1}(s_{n-1})\}$$ Here $v_n(s_n)$ is the ...
0
votes
1answer
39 views

Iterative method to compute only the positive eigenvalue's and corresponding eignevectors of a very large matrix?

I have a very large dense matrix (~10000 X ~10000) which is not full rank . I want to compute only the positive eigenvalues and corresponding eigenvectors instead of computing all of them. I have ...
1
vote
1answer
38 views

Simple question on maximizing a family of concave functions

Given $x \in [0,1]$, let $f_k(x)$ be concave function in $x$ for all $k= 0,1,...,N$. Is the following two maximization formulations equivalent? $$ \max_{0 \le k \le N} f_k(x) =?= \max \{f_0(x), ...
0
votes
0answers
41 views

Can I perform Maximum likelihood via optimization?

I have two $3 \times 3$ matrices $\mathbf{a}$ and $\mathbf{f}$. $\mathbf {f}$ is completely known to me. Also $a_{ij} \in [+1,-1]$ \begin{equation} \mathbf{f} = \left( \begin{array}{ccc} f_{11} ...
0
votes
1answer
15 views

Can a Convex QCQP Problem with an additional linear constraint be converted to a SOCP?

I have a quadratically constrained quadratic programming problem that I massaged into the form $$ \begin{aligned} & \underset{x}{\text{minimize}} & & x^T Q x \\ & \text{subject to} ...
0
votes
0answers
22 views

A length of fence encloses an area alongside a river — what is the optimal shape to maximize area? [duplicate]

You have $100$ meters of fence . There is a perfectly straight riverbank, much longer than $100$ meters, so you have plenty of room to work with. What is the optimal shape and dimensions that ...